source/example_paper.tex

%%%%%%%% ICML 2026 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%

\documentclass{article}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{booktabs} % for professional tables

% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{icml2026} with \usepackage[nohyperref]{icml2026} above.
\usepackage{hyperref}


% Attempt to make hyperref and algorithmic work together better:
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Use the following line for the initial blind version submitted for review:
% \usepackage{icml2026}

% For preprint, use
% \usepackage[preprint]{icml2026}

% If accepted, instead use the following line for the camera-ready submission:
\usepackage[accepted]{icml2026}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}


% if you use cleveref..
\usepackage[capitalize,noabbrev]{cleveref}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% THEOREMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

% Todonotes is useful during development; simply uncomment the next line
%    and comment out the line below the next line to turn off comments
%\usepackage[disable,textsize=tiny]{todonotes}
\usepackage[textsize=tiny]{todonotes}





% \AtBeginDocument{%
% 	\providecommand\BibTeX{{%
% 			\normalfont B\kern-0.5em{\scshape i\kern-0.25em b}\kern-0.8em\TeX}}}
% \usepackage{fancyhdr}
% %\pagestyle{empty}
% \settopmatter{printacmref=false} % Removes citation information below abstract
% \renewcommand\footnotetextcopyrightpermission[1]{} % removes footnote with conference information in first column
%  \pagestyle{plain} % removes running headers

\usepackage{amsmath}
\let\Bbbk\relax
\usepackage{tcolorbox}
%\allowdisplaybreaks
\usepackage{amssymb}
%\usepackage{citehack}
%\usepackage{latexsym}
\usepackage{bm}
\usepackage{nicefrac}
\usepackage{booktabs}
\usepackage{array}
\usepackage{multirow}
\usepackage{threeparttable}
\usepackage{makecell}
% \usepackage[procnumbered,ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{siunitx}
\usepackage{stfloats}
\usepackage{graphicx}
% \usepackage{subfigure}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{enumitem}

% \newtheorem{problem}{Problem}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{lemma}[theorem]{Lemma}
% \newtheorem{observation}[theorem]{Observation}
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem{claim}[theorem]{Claim}
% \newtheorem{fact}[theorem]{Fact}
% \newtheorem{assumption}[theorem]{Assumption}
%\newtheorem{warning}[theorem]{Warning}
% \def\proof{{\bf Proof.}\hskip 0.3truecm}
% \def\endproof{\quad $\Box$}

% \newtheorem{definition}[theorem]{Definition}
% \newtheorem{remark}[theorem]{Remark}

% \newenvironment{fminipage}%
% {\begin{Sbox}\begin{minipage}}%
% 		{\end{minipage}\end{Sbox}\fbox{\TheSbox}}

% \newenvironment{algbox}[0]{\sskip 0.2in
% 	\noindent
% 	\begin{fminipage}{6.3in}
% 	}{
% 	\end{fminipage}
% 	\sskip 0.2in
% }

\def\pleq{\preccurlyeq}
\def\pgeq{\succcurlyeq}
\def\pge{\succ}
\def\ple{\prec}

\def\Approx#1{\approx_{#1}}


\def\defeq{\stackrel{\mathrm{def}}{=}}
\def\setof#1{\left\{#1  \right\}}
\def\sizeof#1{\left|#1  \right|}

\def\eps{\epsilon}


\def\trace#1{\mathrm{Tr} \left(#1 \right)}
\def\norm#1{\left\| #1 \right\|}
%\def\norm#1{\| #1 \|}
\def\smallnorm#1{\| #1 \|}

\def\calC{\mathcal{C}}
%\def\calE{\mathcal{E}}
\def\calG{\mathcal{G}}
\def\calH{\mathcal{H}}
\def\calK{\mathcal{K}}
\def\calL{\mathcal{L}}
\def\calS{\mathcal{S}}
\def\calN{\mathcal{N}}
\def\calT{\mathcal{T}}
\def\calF{\mathcal{F}}
\def\calR{\mathcal{R}}
\def\calM{\mathcal{M}}
%\def\,{,}

\newcommand\Ppsi{\boldsymbol{\mathit{\Psi}}}
\newcommand\PPsi{\boldsymbol{\mathit{\Psi}}}
\newcommand\ppsi{\boldsymbol{\mathit{\psi}}}
\newcommand\pphi{\boldsymbol{\mathit{\phi}}}
\newcommand\Llambda{\boldsymbol{\mathit{\Lambda}}}
\newcommand\PPi{\boldsymbol{\Pi}}

\newcommand\ppi{\boldsymbol{\pi}}
\newcommand\cchi{\boldsymbol{\chi}}
\newcommand\aalpha{\boldsymbol{\alpha}}
\newcommand\bbeta{\boldsymbol{\beta}}
\newcommand\ggamma{\boldsymbol{\gamma}}
\newcommand\ddelta{\boldsymbol{\delta}}

\newcommand\er{R_{eff}}

\newtheorem{property}{Property}[section]
%\newtheorem{proof}{Proof}

% my commands
%\newcommand{\note}[1]{}
%\newcommand{\note}[1]{\textbf{\color{red}(#1)}}

\newcommand{\expec}[1]{\textbf{E} \left\{ #1 \right\} }
\newcommand{\var}[1]{\textbf{var} \left\{ #1 \right\} }

\newcommand{\UV}[1]{\ensuremath{\mathbf{I}_{#1}}}

\newcommand{\Lap}{\ensuremath{\mathbf{L}}}
\newcommand{\A}{\ensuremath{\mathbf{A}}}
\newcommand{\D}{\ensuremath{\mathbf{D}}}
\newcommand{\Prj}{\ensuremath{\mathbf{\Pi}}}
\newcommand{\T}{\ensuremath{\top}}
\newcommand{\Limg}{\ensuremath{\lim_{g\rightarrow\infty}}}

%\newfont{\nset}{msbm10}

\def\bfE{\mbox{\boldmath$E$}}
\def\bfG{\mbox{\boldmath$G$}}

\def\Com{\ns C}
\def\Fou{{\cal F}}
\def\N{\ns N}
\def\Q{\ns Q}
\def\R{\ns{R}}
\def\Z{\ns Z}


\def\att{{\tt a}}
\def\d{\partial}
\def\dgr{\mathop{\rm dgr}\nolimits}
\def\dist{\mathop{\rm dist}\nolimits}

\def\norm#1{\left\| #1 \right\|}
\def\len#1{\left\lVert #1 \right\rVert}
\def\kh#1{\left( #1 \right)}
\def\floor#1{\left\lfloor #1 \right\rfloor}
\def\ceil#1{\left\lceil #1 \right\rceil}


\def\norm#1{\| #1 \|}\def\kh#1{\left( #1 \right)}
\def\fkh#1{\left[ #1 \right]}
\def\norm#1{\| #1 \|}
% \def\len#1{\left\| #1 \right\|}
\def\len#1{\left| #1 \right|}
% \def\SET#1{\left\{ #1 \right\} }

\def\defeq{\stackrel{\mathrm{def}}{=}}

\newcommand{\removelatexerror}{\let\@latex@error\@gobble}
\newcommand\ci{C_{\mathrm{I}}}
\newcommand\ccc{C_{\mathrm{CC}}}

\newcommand{\rea}{\mathbb{R}}
\newcommand{\LaplSolver}{\textsc{LaplSolve}}
\newcommand{\ApproxKemeny}{\textsc{ApproxKemeny}}

\newcommand\LL{\bm{\mathit{L}}}
\newcommand\Otil{\widetilde{O}}

% \def\defeq{\stackrel{\mathrm{def}}{=}}
% \def\trace#1{\mathrm{Tr} \left(#1 \right)}
% \def\sizeof#1{\left|#1  \right|}
% \def\setof#1{\left\{#1  \right\}}

% \def\expec#1#2{{\mathbb{E}}_{#1}\left[ #2 \right]}


% \def\Pcum{{\cal{P}}_{\mbox{\scriptsize cum}}}

% \newtheorem{theo}{Theorem}[section]

% \newtheorem{Th}{Theorem}
% %\newtheorem{Lemma}[Th]{Lemma}
% \newtheorem{Puzzle}{Puzzle}

\def\proof{{\bf Proof.}\hskip 0.3truecm}
\def\endproof{\quad $\Box$}
\def\aa{\pmb{\mathit{a}}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\GainsEst}{\textsc{GainsEst}}
\newcommand{\FGainsEst}{\textsc{F-GainsEst}}
\newcommand{\wmax}{w_{{\max}}}
\newcommand{\wmin}{w_{{\min}}}
\newcommand{\ExactSM}{\textsc{ExactSM}}
\newcommand{\ApproxiSM}{\textsc{ApproxiSM}}
\newcommand{\VReffComp}{\textsc{VReffComp}}
\newcommand\WW{\boldsymbol{\mathit{W}}}
\newcommand\XX{\boldsymbol{\mathit{X}}}
\newcommand\yy{\boldsymbol{\mathit{y}}}
\newcommand\zz{\boldsymbol{\mathit{z}}}
\newcommand\xx{\boldsymbol{\mathit{x}}}
\newcommand\ff{\boldsymbol{\mathit{f}}}
\newcommand\aaa{\boldsymbol{\mathit{a}}}
\newcommand\zeov{\boldsymbol{\mathit{0}}}
\newcommand\bb{\boldsymbol{\mathit{b}}}
\newcommand\cc{\boldsymbol{\mathit{c}}}
\newcommand\dd{\boldsymbol{\mathit{d}}}
\newcommand\ee{\boldsymbol{\mathit{e}}}
\newcommand\pp{\boldsymbol{\mathit{p}}}
\newcommand\qq{\boldsymbol{\mathit{q}}}
\newcommand\rr{\boldsymbol{\mathit{r}}}
\newcommand\uu{\boldsymbol{\mathit{u}}}
\newcommand\sss{\boldsymbol{\mathit{s}}}
\newcommand\hh{\boldsymbol{\mathit{h}}}
\newcommand\ww{\boldsymbol{\mathit{w}}}
\renewcommand\SS{\boldsymbol{\mathit{S}}}
\renewcommand\AA{\boldsymbol{\mathit{A}}}
\newcommand\BB{\boldsymbol{\mathit{B}}}
\newcommand\bBB{\bar{\BB}}
\newcommand\CC{\boldsymbol{\mathit{C}}}
\newcommand\JJ{\boldsymbol{\mathit{J}}}
\newcommand\DD{\boldsymbol{\mathit{D}}}
\newcommand\HH{\boldsymbol{\mathit{H}}}
\newcommand\EE{\boldsymbol{\mathit{E}}}
\newcommand\PP{\boldsymbol{\mathit{P}}}
\newcommand\MM{\boldsymbol{\mathit{M}}}
\newcommand\TT{\boldsymbol{\mathit{T}}}
\newcommand\YY{\boldsymbol{\mathit{Y}}}
\newcommand\ZZ{\boldsymbol{\mathit{Z}}}
\newcommand\RR{\boldsymbol{\mathit{R}}}
\newcommand\QQ{\boldsymbol{\mathit{Q}}}
\newcommand\NN{\boldsymbol{\mathit{N}}}
\newcommand\II{\boldsymbol{\mathit{I}}}
\newcommand\OO{\boldsymbol{\mathit{O}}}
\newcommand\vvv{\boldsymbol{\mathit{v}}}
\newcommand{\SDDMSolver}{\textsc{Solve}}
\newcommand\ZZtil{\widetilde{\boldsymbol{\mathit{Z}}}}
\newcommand\zztil{\widetilde{\boldsymbol{\mathit{z}}}}
\newcommand\AAhat{\boldsymbol{\widehat{\mathit{A}}}}
\newcommand\AAapprox{\boldsymbol{\widetilde{\mathit{A}}}}
\newcommand\DDhat{\boldsymbol{\widehat{\mathit{D}}}}
\newcommand\DDapprox{\boldsymbol{\widetilde{\mathit{D}}}}
\newcommand\LLhat{\boldsymbol{\widehat{\mathit{L}}}}
\newcommand\LLapprox{\boldsymbol{\widetilde{\mathit{L}}}}
\newcommand\MMhat{\boldsymbol{\widehat{\mathit{M}}}}
\newcommand\MMapprox{\boldsymbol{\widetilde{\mathit{M}}}}
\newcommand\ZZhat{\boldsymbol{\widehat{\mathit{Z}}}}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\DeclareMathOperator*{\argmin}{arg\,min}
% \DeclareMathOperator*{\argmax}{arg\,max}

% % algorithm2e
% \DontPrintSemicolon
% \SetKw{KwAnd}{and}
% %\SetProcnameSty{textsc}
% \SetFuncSty{textsc}
% \SetKwInOut{Input}{Input\ \ \ \ }
% %\SetKwInOut{Input}{Input}

% \SetKwInOut{Output}{Output}

% %\usepackage[marginal]{footmisc}
% \usepackage{tabularx}
% \usepackage{stfloats}



% % algorithm2e
% \DontPrintSemicolon
% \SetKw{KwAnd}{and}
% %\SetProcnameSty{textsc}
% \SetFuncSty{textsc}
% \SetKwInOut{Input}{Input\ \ \ \ }
% \SetKwInOut{Output}{Output}


% \usepackage{tabularx}
% \usepackage{stfloats}


























% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Fast Estimation for Forest Matrix of Signed Graphs}

\begin{document}

\twocolumn[
  \icmltitle{Fast Estimation for Forest Matrix of Signed Graphs}

  % It is OKAY to include author information, even for blind submissions: the
  % style file will automatically remove it for you unless you've provided
  % the [accepted] option to the icml2026 package.

  % List of affiliations: The first argument should be a (short) identifier you
  % will use later to specify author affiliations Academic affiliations
  % should list Department, University, City, Region, Country Industry
  % affiliations should list Company, City, Region, Country

  % You can specify symbols, otherwise they are numbered in order. Ideally, you
  % should not use this facility. Affiliations will be numbered in order of
  % appearance and this is the preferred way.
  \icmlsetsymbol{equal}{*}


\begin{icmlauthorlist}
  \icmlauthor{Haoxin Sun}{fudan}
  \icmlauthor{Zhongzhi Zhang}{fudan}
\end{icmlauthorlist}

\icmlaffiliation{fudan}{
  College of Computer Science and Artificial Intelligence,
  Fudan University,
  Shanghai, China}

\icmlcorrespondingauthor{Zhongzhi Zhang}{zhangzz@fudan.edu.cn}


  % \begin{icmlauthorlist}
  %   \icmlauthor{Firstname1 Lastname1}{equal,yyy}
  %   \icmlauthor{Firstname2 Lastname2}{equal,yyy,comp}
  %   \icmlauthor{Firstname3 Lastname3}{comp}
  %   \icmlauthor{Firstname4 Lastname4}{sch}
  %   \icmlauthor{Firstname5 Lastname5}{yyy}
  %   \icmlauthor{Firstname6 Lastname6}{sch,yyy,comp}
  %   \icmlauthor{Firstname7 Lastname7}{comp}
  %   %\icmlauthor{}{sch}
  %   \icmlauthor{Firstname8 Lastname8}{sch}
  %   \icmlauthor{Firstname8 Lastname8}{yyy,comp}
  %   %\icmlauthor{}{sch}
  %   %\icmlauthor{}{sch}
  % \end{icmlauthorlist}

  % \icmlaffiliation{yyy}{Department of XXX, University of YYY, Location, Country}
  % \icmlaffiliation{comp}{Company Name, Location, Country}
  % \icmlaffiliation{sch}{School of ZZZ, Institute of WWW, Location, Country}

  % \icmlcorrespondingauthor{Firstname1 Lastname1}{first1.last1@xxx.edu}
  % \icmlcorrespondingauthor{Firstname2 Lastname2}{first2.last2@www.uk}

  % You may provide any keywords that you find helpful for describing your
  % paper; these are used to populate the "keywords" metadata in the PDF but
  % will not be shown in the document
  \icmlkeywords{Machine Learning, ICML}

  \vskip 0.3in
]

% this must go after the closing bracket ] following \twocolumn[ ...

% This command actually creates the footnote in the first column listing the
% affiliations and the copyright notice. The command takes one argument, which
% is text to display at the start of the footnote. The \icmlEqualContribution
% command is standard text for equal contribution. Remove it (just {}) if you
% do not need this facility.

% Use ONE of the following lines. DO NOT remove the command.
% If you have no special notice, KEEP empty braces:
\printAffiliationsAndNotice{}  % no special notice (required even if empty)
% Or, if applicable, use the standard equal contribution text:
% \printAffiliationsAndNotice{\icmlEqualContribution}

\begin{abstract}
% The forest matrix of a signed graph has far-reaching implications in network science and social opinion dynamics. Current state-of-the-art algorithms for computing the forest matrix are primarily designed for unsigned graphs and face challenges when extended to signed graphs. In this paper, we study the problem of efficiently estimating the forest matrix of signed graphs with \(n\) nodes. We first introduce the signed forest matrix theorem, which establishes the foundational relationship between generalized spanning converging forests and the forest matrix. Then, we propose a novel algorithm  $\textsc{GSCF}$ to generate a  generalized spanning converging forest. This algorithm is based on a variant of the loop-erased random walk, and we demonstrate that its expected running time is $O(n)$, making it highly efficient for practical applications. After that,   We develop two efficient sampling algorithms, $\textsc{FMDE}$ and $\textsc{FMDE+}$, designed to estimate the diagonal of the forest matrix. Both algorithms operate with a time complexity of \(O(ln)\), where \(l\) is the number of samples. Compared with   $\textsc{FMDE}$, $\textsc{FMDE+}$ incorporates additional information which results in superior theoretical and experimental performance. 
% Moreover, we propose an algorithm \textsc{FJOE} to estimate the expressed opinion. Algorithm \textsc{FJOE} takes $O(l)$ time to query the expressed opinion of each node.
% Finally, we conduct extensive experiments on various signed graphs, which shows that our algorithms not only achieve high estimation accuracy but also significantly improve computational efficiency. Additionally, our approaches are scalable to massive graphs, effectively handling networks with more than twenty million nodes.




The forest matrix of a signed graph plays an important role in network science and social opinion dynamics, yet existing algorithms are mainly designed for unsigned graphs and are difficult to extend to signed graphs. In this paper, we study the problem of efficiently estimating the forest matrix of signed graphs with \(n\) nodes and introduce the signed forest matrix theorem, which establishes the relationship between generalized spanning converging forests and the forest matrix. Based on this result, we propose a novel algorithm \textsc{GSCF}, built on a variant of loop-erased random walks, to generate generalized spanning converging forests in expected \(O(n)\) time. We further develop two sampling algorithms, \textsc{FMDE} and \textsc{FMDE+}, for estimating the diagonal of the forest matrix, both with time complexity \(O(ln)\), where \(l\) is the number of samples. Extensive experiments on various signed graphs show that our methods achieve high estimation accuracy, significantly improve computational efficiency, and scale to graphs with over twenty million nodes. Our source code is publicly available on \url{https://github.com/HaoxinSun98/SignedForestDiagonal}.



\end{abstract}



\section{Introduction}


% Research in signed graphs has been both extensive and diverse, covering a wide range of topics. Significant efforts have been made in identifying conflicting groups within these networks~\cite{TzOrGi20}, examining the phenomenon of polarization~\cite{XiOrGi20}, and detecting community structures~\cite{BoGaGiOrRu19, SuChWaZhWa20}. The area of signed cliques has also seen notable advancements, with various algorithms being developed for their computation and enumeration~\cite{YaChQi22, SuWuChWaZhLi22, LiDaQiWaXiYuQi19}. In addition, the process of influence diffusion in signed networks has been a subject of study, revealing unique aspects of these networks~\cite{LiLi19, YiHuChYuLi19, KaKhDaKuKh22}. However, the aforementioned studies on signed graphs are not applicable to the leader selection problem on Altafini model within signed networks.


The forest matrix,  denoted as $\QQ = (\II+\LL)^{-1}$, where $\LL$ is the Laplacian matrix, is  a powerful tool in network science. Its properties and applications have been  studied in extensive studies such as~\cite{ChSh95,ChSh97,ChSh98,ChSh06}. In recent years, the scope of applications for the forest matrix and its variants has expanded significantly, influencing fields  such as  opinion dynamics~\cite{GiTeTs13,SuZh23,ZhSuXuLiZh24,XuBaZh21,NeDoPe24,sunfast}, graph signal processing~\cite{PiAmBaTr21,PiAmBaTr20} and Markov processes~\cite{AvLuGaAl18,AvCaGaMe18}. In particular, the diagonal entries of $\QQ $ are crucial and have recently been the subject of studies focusing on their efficient computation~\cite{JiBaZh19, GrAnPrMe21,SuZh24}. The entries of the forest matrix are also pivotal for determining the forest closeness centrality of networks~\cite{JiBaZh19, GrAnPrMe21} and have been closely associated with determinantal point processes in machine learning~\cite{KuTa12}. Additionally, they provide valuable insights through electrical interpretations in multi-agent and network-based problems~\cite{RoFrFa17}.
 


With the growing recognition of competitive interactions in real systems, signed graphs have attracted significant scholarly attention~\cite{HaBhPa24,SuWuChWaZhLi22,SuChWaZhWa20,XiOrGi20,TzOrGi20,SiAd17,FrJo90,CaFaHe25}. The introduction of negative edges modifies the properties and computational challenges related to the forest matrix in these graphs. For instance, the forest matrix in signed graphs is no longer row-stochastic,  and the conventional forest matrix theorem~\cite{ChSh06,ChSh98}, which links the forest matrix to spanning forests, no longer applies. The forest matrix is central to the signed Friedkin-Johnsen (FJ) model, an influential model in opinion dynamics that addresses both cooperative and antagonistic relationships, offering a nuanced view of human relational dynamics~\cite{XuHuWu20,RaHo21,HeZhLiRu20,HeZeZhLi22, TaChAgLi16,HaBhPa24}. Particularly, the diagonal elements of the forest matrix in the signed FJ model determine the weight each agent assigns to their initial opinions at equilibrium, with great significance in node ranking and centrality measures. In addition, the forest matrix elements are also closely related to the expressed opinions of the individuals in the signed FJ model, which is the basis for the study of opinion dynamics. However, existing algorithms~\cite{JiBaZh19, GrAnPrMe21,SuZh24} fail to effectively estimate the elements of the forest matrix in signed graphs due to these altered properties. Specifically, the methods proposed in~\cite{JiBaZh19, GrAnPrMe21} rely on fast Laplacian solvers~\cite{CoKyMiPaPeRaSu14}, which are not applicable to signed graphs. Additionally, the sampling method developed in~\cite{SuZh24} fails to run, as it relies on the forest matrix theorem for unsigned graphs, which does not hold in the signed case. Consequently, a theoretically guaranteed estimation algorithm for approximating the elements of the forest matrix  of signed graphs is imperative.
 

 
 

In this paper, we delve deeply into the problem of efficiently computing the forest matrix in signed digraphs with \(n\) nodes, aiming to address the challenges and limitations of existing algorithms. The primary contributions of this work are summarized as follows:

(i) We introduce a new forest matrix theorem specifically tailored for signed graphs. This theorem establishes the foundational relationship between generalized spanning converging forests and the forest matrix, and elucidates several key properties of the forest matrix in the context of signed graphs.

(ii) To generate a generalized spanning converging forest, we propose a novel algorithm, denoted as $\textsc{GSCF}$. This algorithm is based on a variant of the loop-erased random walk, and we demonstrate that its expected running time is \(O(n)\), making it highly efficient for practical applications.

(iii) We develop two rapid sampling algorithms, $\textsc{FMDE}$ and $\textsc{FMDE+}$, designed to estimate the diagonal of the forest matrix. Both algorithms operate with a time complexity of \(O(ln)\), where \(l\) is the number of samples. $\textsc{FMDE+}$, an enhancement over $\textsc{FMDE}$, incorporates additional information that results in superior theoretical and experimental performance. We also develop an algorithm \textsc{FJOE}, to estimate the expressed opinion of the signed FJ model as an application of our proposed methods.

(iv)  Through extensive experiments conducted on various signed graphs, we demonstrate that our algorithms not only achieve high estimation accuracy but also significantly enhance computational efficiency. Additionally, our approaches are scalable to massive graphs, effectively handling networks with more than twenty million nodes.

   

\section{Related Work}
 % In this section, we briefly review the existing work related to ours.


The forest matrix is closely related to spanning rooted forests in graphs, as established by the forest matrix theorem~\cite{ChSh06,ChSh97,ChSh98}. Recent research has increasingly focused on computing quantities or solving optimization problems associated with the forest matrix and its variants. For instance, efforts have been made to compute the PageRank vector~\cite{LiLiDaChQiWa23PageRank, LiLiDaWa22}, solve linear systems in graph signal processing~\cite{PiAmBaTr21, PiAmBaTr20}, address optimization problems in opinion dynamics~\cite{SuZh23}, and estimate the trace of the forest matrix~\cite{PiAmBaTr22trace, PiAmBaTr22}. The algorithms developed for these problems are predominantly sampling-based, relying on the theoretical foundation of the forest matrix theorem and utilizing variants of Wilson's algorithm for loop-erased random walks to sample spanning trees or forests~\cite{Wi96}. 


Efficient computation of the diagonal elements of the forest matrix has recently attracted significant interest due to its close association with issues such as forest closeness centrality of networks~\cite{JiBaZh19, GrAnPrMe21}, determinantal point processes in machine learning~\cite{KuTa12}, and multi-agent and network-based problems~\cite{RoFrFa17}. A nearly linear time algorithm combining the Johnson-Lindenstrauss lemma~\cite{JoLi84, Ac03} with a fast Laplacian solver was proposed in~\cite{JiBaZh19}. This was followed by an approach in~\cite{GrAnPrMe21} that integrated a single instance of the Laplacian solver with uniform spanning tree sampling. More recently, forest sampling algorithms introducing novel variance reduction techniques were developed, offering better theoretical guarantees than prior methods~\cite{SuZh24}. 

 
 However, when applied to signed graphs, where the forest matrix remains central to many problems~\cite{HaBhPa24, LiChZh22, XuHuWu20, ZhSuXuLiZh24}, existing algorithms falter. This limitation stems from the fact that fast Laplacian solvers are not adaptable to signed contexts, and the traditional forest matrix theorem does not hold, rendering all forest sampling-based algorithms ineffective. Consequently, the introduction of a forest matrix theorem tailored for signed graphs, along with the development of a novel sampling-based method for efficiently estimating the diagonal of the forest matrix in such graphs, constitutes the primary focus of this paper.












\section{Preliminaries}
% In this section, we will provide a general overview of the notations and signed graphs and their related matrices.
%, and FJ models on unsigned and signed graphs used in the paper. 
%We will explain what these concepts are and how they are used to represent and analyze data and relationships.

%In this section, we introduce some useful notations and FJ model and its varient, signed FJ model, for

%for the convenience of description and analysis of the problems and algorithms.

% \subsection{Notations}

% %We use normal lowercase letters like $ a,b,c $ to denote scalars in set of real numbers, normal uppercase letters like $ A,B,C $ to denote sets, bold lowercase letters like $ \aaa,  \bb, \cc$ to denote column vectors, and bold uppercase letters like $ \AA,\BB,\CC $ to denote matrices.  
% %We use $\AA^{\top}$ and  $\aaa^{\top}$ to represent the transpose of matrix $\AA$ and vector $\aaa$, respectively. Let $\ee_i$  denote the column vector of appropriate dimension, where the $i$-th element is $1$, and other elements are $0$. Let $\mathbf{0}$ be an appropriate-dimension column vector with all entries being zeros, and let $\mathbf{1}$ be an appropriate-dimension column vector with all entries being ones. Let $\II$ denote an appropriate-dimension identity matrix. For a matrix $\AA$, $\AA_{i,j}$ denotes its element at $i$-th row and $j$-th column. Similarly, for a vector $\aaa$, we use $\aaa_i$ to denote its $i$-th element. For any vector $\xx$ and matrix $\AA$, we use $\norm{\xx}_2=\sqrt{\sum_i \xx_i^2}$ to denote its $\ell_2$ norm, and $\norm{\xx}_{\AA} = \sqrt{\xx^\top \AA \xx}$ to denote its norm.
% The vector $\ee_i$ is a vector of appropriate dimension, where the $i$-th element is 1 and all other elements are 0. The  vector $\mathbf{0}$ (or $\mathbf{1}$)  is a vector of appropriate dimension with all entries equal to 0 (or 1). The identity matrix is denoted as $\II$. For a matrix $\AA$, the element at the $i$-th row and $j$-th column is $\AA_{ij}$. Similarly, for a vector $\aaa$, its $i$-th element is $\aaa_i$. We use $\AA^{\top}$ and $\aaa^{\top}$ to denote the transpose of matrix $\AA$ and vector $\aaa$, respectively. The $\ell_2$ norm of a vector $\aaa$ is $\norm{\aaa}_2 = \sqrt{\sum_i \aaa_i^2}$, the $\ell_0$ norm of a vector $\aaa$, denoted as $\norm{\aaa}_0$, is defined as the number of nonzero elements in $\aaa$, and the norm of a vector $\aaa$ with respect to a matrix $\AA$ is $\norm{\aaa}_{\AA} = \sqrt{\aaa^\top \AA \aaa}$.
% %For a matrix $\AA$, $\AA_{H,F}$ denotes the submatrix of $\AA $ with row indices in set $H$ and column indices in set $ F$, and $ A_{-H} $ denotes the submatrix of $ \AA $ obtained from $ \AA $ by deleting rows and columns corresponding to nodes in set $ H $. Similarly, for a vector $ \aaa $, we use $ \aaa_{-H} $ to denote the vector obtained from $ \aaa $ by deleting elements in set $H$. If $ H $ contains only a single element $i$, we use $ \AA_{-i}$ and $\aaa_{-i}$ to denote, respectively, $ \AA_{-\{i\}} $ and $ \aaa_{-\{i\}} $ for simplicity.

% %Let $a, b \geq 0$ be nonnegative scalars. We say that $a$ is an $\eps$-approximation of $b$, denoted by $a \approx_{\eps} b$, if $(1-\eps) a \leq b \leq (1+\eps) a$, where $0 < \eps < 1/2$. For two positive semidefinite matrices $\XX$ and $\YY$, we say that $\XX \preceq \YY$ if $\YY - \XX$ is positive semidefinite, meaning that $\xx^\top \XX \xx \leq \xx^\top \YY \xx$ holds for all real vectors $\xx$.





% \subsection{Signed Graph and  Related Matrices}



We define a directed   signed graph $\calG= (V,E,w)$ with $n=|V|$ nodes, $m=|E|$ edges,  where $V=\{v_1,v_2,\ldots,v_n\}$ is the set of nodes,  $E=\{(v_i, v_j)\in V \times V \}$ is the set of directed edges, and $w : E \mapsto \{ +1, -1\}$ is the edge weight function, with the weight of an edge $e=(i,j)$ denoted by $w_{ij}$.  We call an edge $e=(i,j) $ a positive (or negative) edge if   its weight $w_{ij}$ is $+1$ (or $-1$). The edge sign represents the relationship between node $i$ and node $j$, which can be cooperative or competitive. In what follows, $v_i$ and $i$ are used interchangeably to represent node $v_i$ if incurring no confusion. A path $P$ from node $v_1 $ to node $ v_j $ is an alternating sequence of nodes and edges $v_1$,$(v_1,v_2)$,$v_2$,$\ldots$, $v_{j-1},(v_{j-1}$,$v_j)$, $v_j$, where nodes are distinct. A loop  is a path plus an arc from the ending node to the starting node. 

For a directed signed graph $\calG=(V, E,w)$, let $C=\{1,2,\ldots, k\}$ be the cycle with nodes $1$ to $k$ and edges $(1,2),(2,3),\ldots,(k,1)$. A cycle with only one node is called a trivial cycle. A non-trivial cycle  is called negative (or positive) if the sign of the product of its arcs  is negative (or positive). The graph $\calG = (V, E, w)$ is defined as a balanced signed graph if either all its edges are positive or the vertices can be partitioned into two subsets such that each positive edge joins vertices in the same subset and each negative edge joins vertices in different subsets. Notably, balanced signed graphs do not contain any negative cycles.

% The connections  of  a graph  $\calG= (V,E,w)$ are encoded in its extended adjacency matrix $\AA=(w_{ij})_{n \times n}$, with the element $w_{ij}$ at row $i$ and column $j$ representing the strength of edge  $ (v_i,v_j) $ or  $(i, j)$  linking  nodes $i$ and $j$. If nodes $i$ and $j$ are directly connected by an edge $e$ with weight $w_e$, then $w_{ij}= w_{ji}= w_e $; $w_{ij}=w_{ji}=0$ otherwise.  Let $N(i)$ denote the set of neighbors of node $i$. Then the weighted degree $d_i$ of  node $i$ is $d_i=\sum_{j=1}^n w_{ij}=\sum_{j\in N_i} w_{ij}$. A graph is called $p$-regular if every edge has a unit weight and  every node has the same degree $p$. The weighted diagonal degree matrix of  $\calG$ is defined as ${\DD} = {\rm diag}(d_1, d_2, \ldots, d_n)$, and the Laplacian matrix of $\calG$ is defined to be ${\LL}={\DD}-{\AA}$, which is symmetric.  By definition, the sum of all entries in each row or column of $\LL$ is equal to $0$ obeying relations  $\LL\mathbf{1}=\mathbf{0}$ and $\mathbf{1}^{\top} \LL=\mathbf{0}^{\top}$.


Let $N(i) $ denote the set of nodes that can be accessed by node $ i $. In other words, $N(i) =\{ j: (i,j)\in E\}$. We define the degree of a node $i$ as $d_i=\sum_{j\in N(i)} |w_{ij}|$. We use a diagonal matrix $\DD=\text{diag}\{d_1,d_2,\ldots,d_n\}$ to denote the degree matrix, and matrix $\AA \in \mathcal{R}^{n \times n}$ to denote the signed adjacency matrix corresponding to the signed graph $\calG=(V,E,w)$ with $\AA_{ij} = w_{ij}$ for any edge $(i,j)\in E$, and $\AA_{ij} = 0 $ otherwise. Let $\AA^+\in \mathcal{R}^{n \times n}$ be the positive adjacency matrix defined as $\AA^+_{ij} = w_{ij}$ if $w_{ij}>0$, and $\AA^+_{ij} = 0 $ otherwise. The negative adjacency matrix $\AA^-$ is defined as $\AA^- = \AA-\AA^+$. Then we define the signed Laplacian matrix as $\LL=\DD-\AA$. 


% By definition, the sum of all entries in each row of $\LL$ is no less than $0$ obeying  $\LL\mathbf{1} \geq \mathbf{0}$.


% We fix an arbitrary orientation for all edges in $\calG$, and then we can define the edge-node incidence matrix $\BB_{m\times n}$ of graph $\calG$, whose entries are defined as follows: $\BB_{e,u}=1$ if node $u$ is the head of edge $e$, $\BB_{e,v}=-w(e)$ if node $v$ is the tail of $e$, and $\BB_{e,t}=0$ otherwise. Then $\LL$ can also be written as $\LL=\BB^\top \BB$, implying that the signed Laplacian matrix $\LL$ is symmetric and positive semidefinite.

% We can then divide $i$'s neighbor set $N_i$ into two disjoint subsets: the friend set $N^F_i$ and the enemy set $N^E_i$. The node in the friend set has a positive edge with $i$, while the node in the enemy set has a negative edge with $i$.

%We define the degree of a node $i$ as $d_i=\sum_{j\in N_i} |w(i,j)|$, and we use a diagonal matrix $\DD=\text{diag}{d_1,d_2,\ldots,d_n}$ to denote the degree matrix. We use matrix $\AA \in \mathcal{R}^{n \times n}$ to denote the signed adjacency matrix corresponding to the graph $\calG$ with $\AA_{i,j} = w(i,j)$ for any edge $(i,j)\in E$. The signed Laplacian matrix is $\LL=\DD-\AA$, which is symmetric and positive semi-definite. If the graph contains no negative edges, it is an unsigned graph and its correlated matrices defined above correspond to their unsigned counterparts. If we fix an arbitrary orientation for all edges in $\calG$, then we can define the edge-node incidence matrix $\BB_{m\times n}$ of graph $\calG$, whose entries are defined as follows: $\BB_{e,u}=1$ if node $u$ is the head of edge $e$, $\BB_{e,v}=-w(e)$ if node $v$ is the tail of $e$, and $\BB_{e,t}=0$ otherwise. Then $\LL$ can be written as $\LL=\BB^\top \BB$.
%If the graph contains no negative edges, it is an unsigned graph and its correlated matrices defined above correspond to their unsigned counterparts.



% Considering the sign of the edges, we can divide the graph $\calG$ into two parts: the positive graph $\calG^+=(V,E^+,w^+)$ and the negative graph $\calG^-=(V,E^-,w^-)$, where $E=E^+ \cup E^-$ and $w^+(e)=1$ if $e\in E^+$ and $w^-(e)=1$ if $e\in E^-$. Both graphs share the same node set $V$ as the graph $\calG$. The former graph contains all positive edges, while the latter graph contains all negative edges. The adjacency matrices of these two graphs are non-negative matrix $\AA^+$ and non-positive matrix $\AA^-$, respectively. Similarly, we can define degree matrices $\DD^+$ and $\DD^-$, incidence matrices $\BB^+$ and $\BB^-$, and Laplacian matrices $\LL^+$ and $\LL^-$ on both positive and negative graphs, respectively.

% We also provide some useful matrix inequalities involving the signed Laplacian matrix $\LL$ in the following fact, which will be used in the proofs later.
% \begin{fact}
%     We have $\LL^+ \preceq \LL$, $\LL^- \preceq \LL$, $\II \preceq \II + \LL$,  $\LL \preceq \II + \LL$, $ \II + \LL \preceq 2n \II$, and $ \frac{1}{2n}\LL \preceq \II$.
% \end{fact}

%We use $d_i=\sum_{j \in V} |\AA_{i,j}|$ to denote the degree of node $i$ and matrix $\DD=\text{diag}\{d_1,d_2,\ldots,d_n\}$ to denote the degree matrix. Then we define the signed Laplacian matrix $\LL=\DD-\AA$, which is symmetric.

% Let $w_{\rm max}$ and $w_{\rm min}$ denote, respectively, the maximum and minimum weight among all edges in $E$. In what follows, $v_i$ and $i$ are used interchangeably to represent node $v_i$ if incurring no confusion.  We also use $ (v_i,v_j) $ or $ (v_j,v_i) $ to represent the edge linking nodes $ v_i $ and $ v_j $. An isolated node is a node with no other nodes having an edge connected to it.  A path $P$ from node $v_1 $ to node $ v_k $ is an alternating sequence of nodes and edges $v_1$,$(v_1,v_2)$,$v_2$,$\ldots$, $v_{j-1},(v_{j-1}$,$v_j)$, $v_j$, where nodes are distinct.  A loop is a path plus an edge linking the ending node and the starting node. A tree is a connected graph but has no loops, and an isolated node is considered as a tree.  A forest is a particular graph that is a disjoint union of trees.


%The connections  of  a graph  $\calG= (V,E,w)$ are encoded in its extended adjacency matrix $\AA=(w_{ij})_{n \times n}$, with the element $w_{ij}$ at row $i$ and column $j$ representing the strength of edge  $ (v_i,v_j) $ or  $(i, j)$  linking  nodes $i$ and $j$. If nodes $i$ and $j$ are directly connected by an edge $e$ with weight $w_e$, then $w_{ij}= w_{ji}= w_e $; $w_{ij}=w_{ji}=0$ otherwise.  Let $N(i)$ denote the set of neighbors of node $i$. Then the weighted degree $d_i$ of  node $i$ is $d_i=\sum_{j=1}^n w_{ij}=\sum_{j\in N_i} w_{ij}$. A graph is called $p$-regular if every edge has a unit weight and  every node has the same degree $p$. The weighted diagonal degree matrix of  $\calG$ is defined as ${\DD} = {\rm diag}(d_1, d_2, \ldots, d_n)$, and the Laplacian matrix of $\calG$ is defined to be ${\LL}={\DD}-{\AA}$, which is symmetric.  By definition, the sum of all entries in each row or column of $\LL$ is equal to $0$ obeying relations  $\LL\mathbf{1}=\mathbf{0}$ and $\mathbf{1}^{\top} \LL=\mathbf{0}^{\top}$.


%\section{Friedkin-Johnsen Model and its Interpretation}

\iffalse
In this section, we introduce the Friedkin-Johnsen model~\cite{FrJo90} and its signed version~\cite{XuHuWu20}. Then, we provide an interpretation of the equilibrium opinions on the signed FJ model.

\subsection{Friedkin-Johnsen Model}
The FJ model is a mathematical framework that allows us to represent and analyze individual interactions within a system. In the standard FJ model~\cite{FrJo90}, each node or agent $i\in V$ is associated with two opinions: an internal opinion $\sss_i$, which is a constant value in the interval $[-1,1]$ and reflects the intrinsic position of node $i$ on a certain topic, and an expressed opinion $\zz_i(t)$ at time $t$, which evolves according to the following equation:% \eqref{FJ}. %A higher value of $\sss_i$ indicates that node $i$ is more favorable towards the topic, while a lower value signifies the opposite.
\begin{equation}\label{FJ}
	\zz_i(t+1) = \frac{\sss_i +\sum_{j\in N_i}\AA_{ij}\zz_j(t)}{1+\sum_{j\in N_i} \AA_{ij}}.
\end{equation}
In this system, the expressed opinion $\zz_i(t+1)$ for node $i$ at time $t+1$ is updated by averaging its initial opinion $\sss_i$ and its neighbors' expressed opinions at time $t$. We define the initial opinion vector as $\sss = (\sss_1,\sss_2,\ldots,\sss_n)^\top$, and define the vector of expressed opinions at time $t$ as $\zz(t) = (\zz_1(t),\zz_2(t),\ldots,\zz_n(t))^\top$. The expressed opinion vector converges to an equilibrium vector $\zz = (\zz_1,\zz_2,\ldots,\zz_n)^\top = \lim_{t \to \infty} \zz(t)$ satisfying $\zz = (\II+\LL)^{-1}\sss$ for large $t$~\cite{BiKlOr15}, where $\LL$ is the Laplacian matrix of a unsigned graph.

%It has been shown~\cite{BiKlOr11} that as $t$ approaches infinity, $\zz(t)$ converges to
%\begin{equation}\label{FJz}
%\zz = (\II+\LL)^{-1}\sss\,.
%\end{equation}

%The FJ model is a mathematical framework that allows us to represent and analyze the interactions between different individuals in a system. We first introduce the standard FJ model~\cite{FrJo90}.
 

%For the FJ opinion model on an unsigned graph $\calG=(V,E,w)$, each node/agent  $i\in V$ is associated with two opinions: one is the initial (internal) opinion $\sss_i$, the other is the expressed (external) opinion $\zz_i(t)$ at time $t$. The internal opinion $s_i$ is in the  interval $(-1,1)$, reflecting the intrinsic position of node $i$ on a certain topic. A higher value of $\sss_i$ signifies that node $i$ is more favorable toward the topic and vice versa. During the process of opinion evolution, the internal opinion $\sss_i$ remains constant, while the expressed opinion $\zz_i(t)$ evolves in the following way:

%In other words, at time $t+1$, the expressed opinion  $z_i(t+1)$ for node $i$ is influenced by both of its initial opinion $s_i$ and the expressed opinions of its neighbours at time $t$. Let $\sss = (\sss_1,\sss_2,\ldots,\sss_n)^\top$ denote the vector of initial opinions, and let $\zz(t) = (\zz_1(t),\zz_2(t),\ldots,\zz_n(t))^\top$ denote the vector of expressed opinions at time $ t $. It was shown~\cite{BiKlOr11} that as $t$ approaches infinity, $\zz(t)$ converges to an equilibrium vector  $\zz = (\zz_1,\zz_2,\ldots,\zz_n)^\top$ satisfying

\subsection{Signed Friedkin-Johnsen Model}
Next, we introduce the signed FJ model~\cite{XuHuWu20}, which uses signed graphs to represent the relationships between individuals in the system, with positive and negative signs indicating trust and distrust, respectively.

Using similar notations as mentioned in the standard FJ model, the following equation describes the dynamics of the signed FJ model.
\begin{equation}\label{sFJ}
	\zz_i(t+1) = \frac{\sss_i +\sum_{j\in N_i}\AA_{ij}\zz_j(t)}{1+\sum_{j\in N_i} |\AA_{ij}|}.
\end{equation}
%In Equation (\ref{sFJ}), $\zz_i(t+1)$ represents the expressed opinion of individual $i$ at time $t+1$, $\sss_i$ is the internal opinion of individual $i$, $N_i$ is the set of neighbours of $i$, and $\AA_{i,j}$ is the edge sign of edge $e=(i,j)$.

At equilibrium, the expressed opinion $\zz$ can be solved by 
\begin{equation}
    \zz=(\II+\LL)^{-1}\sss,
\end{equation}
where $\LL$ is the signed Laplacian matrix of the signed graph $\calG=(V,E,w)$~\cite{XuHuWu20}. This result provides an intuitive way to compute the equilibrium opinion in the signed FJ model.

In~\cite{GiTeTs13,MaTeTs17}, matrix $(\II+\LL)^{-1}$ is called the fundamental matrix of the FJ model, which is a doubly stochastic matrix. However, this property does not hold in the signed FJ model, and the expressed
opinion is no longer a convex combination of the internal opinions of
all nodes as in the standard FJ model. In the following, let matrix $\QQ$ denote the fundamental matrix of the signed FJ model, that is  $\QQ = (\II+\LL)^{-1}. $

\fi 



\section{Forest Matrix Theorem on Signed Graphs}
 % In this section, we introduce the signed forest matrix theorem to establish the relationship between the forest matrix and generalized spanning converging forests.


\subsection{Forest Matrix on Signed Graphs  }

The forest matrix $\QQ = (q_{ij})_{n\times n}$ is defined as $\QQ = (\II+\LL)^{-1}$. The properties of the forest matrix in unsigned graphs have been extensively studied in~\cite{ChSh97,ChSh98,ChSh06,SuZh23,SuZh24}. For example, in unsigned directed graphs, the forest matrix is row stochastic, with all its components in the interval $[0,1]$, and the diagonal elements in each column exceed the other elements.

 
In signed graphs, the forest matrix serves as the fundamental matrix in the signed opinion propagation Friedkin-Johnsen model~\cite{XuHuWu20,HaBhPa24}. However, its properties differ from those in the unsigned case. The forest matrix is no longer row stochastic, and the non-diagonal elements may be less than zero. As we will show later, for any $i, j \in V$ with $i \neq j$, we have $0 \leq |q_{ij}| \leq q_{jj} \leq 1$.

\subsection{Generalized  Spanning Converging Forests}
In this subsection, we introduce the concept of generalized spanning converging forests.   A spanning subgraph of $\calG$  is a subgraph of  $\calG$ with the node set being $V$ and the edge set being a subset of $E$.   A generalized spanning converging forest  is a spanning subgraph of  $\calG$, where the out-degree of each node  is no more than $1$, and all cycles are negative. Let $\calF $ be the set of all generalized  spanning converging forests of digraph $ \calG $. For any generalized spanning forest $\phi \in \calF$, the root nodes of $\phi$ are those with an out-degree of $0$. The root set  $\mathcal{R}(\phi )$  is defined as  $\mathcal{R}(\phi ) = \{i:(i,j) \notin \phi$, for any $j\in V  \}$.  We use $n^-(\phi)$  to denote the number of non-trivial negative cycles in $\phi$.

A generalized spanning converging forest $\phi$ may comprise several connected components. Let \( \kappa(\phi) \) denote the number of connected components in $\phi$.   By definition, each connected component   in $\phi$ is either a rooted converging tree or a structure containing a negative cycle. Consequently, the relationship between the number of root nodes and the number of components is given by $|\mathcal{R}(\phi)| \leq \kappa(\phi) \leq n$. The lower bound, $|\mathcal{R}(\phi)| \leq \kappa(\phi)$, is achieved when there are no cycles within $\phi$. The upper bound, $\kappa(\phi) \leq n$, is reached when each node in $\phi$ is isolated, resulting in the absence of any edges within $\phi$. To effectively distinguish between the two possible scenarios within each connected component and to simplify notation, we define the function \( r_{\phi} \) for each node \( i \) in \(\phi\) as follows: $r_{\phi}(i)=i$ if $i \in \mathcal{R}(\phi)$; $r_{\phi}(i)=0$ if $i$ belongs to a cycle; otherwise, if $(i,j)\in E_{\phi}$ and $i$ does not belong to a cycle, we recursively define $r_{\phi}(i)=r_{\phi}(j)$.


 
% , with each component labeled as $C_1, \cdots, C_{\kappa(\phi)}$. 



% \begin{equation}
%     r_{\phi}(i) = \left\{\begin{matrix}
%  i & if \ i\in \mathcal{R}(\phi ),\\
%  0 & if \ i\ belongs\ to\ a\ cycle,\\
% r_{\phi}(j)  & if \ (i,j)\in E_\phi, i\ not\ belongs\ to\ a\ cycle.
% \end{matrix}\right.
% \end{equation}
From this definition, we observe that for any node $i \in \phi$, if the connected component containing $i$ includes a negative cycle, then $r_{\phi}(i) = 0$. Conversely, if the connected component containing $i$ is a rooted converging tree, then the function $r_{\phi}$ maps the node $i$ to its root in its connected component.

For nodes $i,j\in V$, define $ \calF_{ij} $ to be the set of those generalized spanning converging forests, where node $j$ is the root, and there is a path from node $i$ to node $j$. Then the function $r_{\phi} $ maps node $i$ to $j$, that is, $\calF_{ij} = \{\phi: r_{\phi}(i) = j,  \phi \in \calF\}$. Then, for node $i\in V$,  we have $\calF_{ii} = \{\phi: i\in \calR(\phi),   \phi \in \calF\}$. For a generalized spanning converging forest  $\phi $, its weight $w(\phi)$ is defined as  $     w(\phi) = 2^{n^-(\phi)} \prod_{(i,j) \in E_\phi} \abs {w_{ij}} = 2^{n^-(\phi)}$.
 % \begin{equation}
 %     w(\phi) = 2^{n^-(\phi)} \prod_{(i,j) \in E_\phi} \abs {w_{ij}} = 2^{n^-(\phi)}. 
 % \end{equation}

 


 
 If there is no edge in $ \phi $, its weight is defined to be $ 1 $.
 Define the weight of set $\calF$ as $w(\calF) = \sum_{\phi\in \calF} w(\phi)$. Similarly, define $w(\calF_{ii}) = \sum_{\phi\in \calF_{ii}} w(\phi)$.  There is something different when we define 
$w(\calF_{ij}) = \sum_{\phi\in \calF_{ij}}{\rm sign}(P_{ij}) w(\phi)$, where ${\rm sign}(P_{ij})$ is the sign of the product of the weights of the arcs in the path from node $i$ to node $j$ in $\phi$. 

For example, we present a toy graph, $\calG_0$, comprising $3$ nodes and $4$ edges, including two positive and two negative edges. We list  all its $12$ generalized spanning converging forests $\phi_1,\phi_2,\cdots,\phi_{12}$. Notably, the last three forests, highlighted with a yellow background in Figure \ref{f0}, contain negative cycles. Following the definition provided, the weight \( w(\phi_i) \) is assigned as $1$ for \(i=1,\cdots,9\) and $2$ for \(i = 10,11,12\).

\begin{figure}[htbp!]
	\centering
	\includegraphics[width=1\columnwidth]{toy1}
	\caption{A toy signed graph $\calG_0$ with its $12$ generalized spanning converging forests. Blue nodes are roots.}\label{f0}	
\end{figure}


  

\subsection{ Signed Forest Matrix Theorem}
In this subsection, we introduce the forest matrix theorem in signed graphs. We extend the forest matrix theorem from the unsigned case~\cite{ChSh06, ChSh97, ChSh98} to accommodate signed graphs. First, we propose two lemmas that establish the relationship between the determinant of the matrix $\II+\LL$ and its submatrices, obtained by deleting one column and one row, with the weights of specific generalized spanning converging forests.


\begin{lemma}\label{th-wF}
    For a directed signed graph $\calG=(V, E,w)$, the determinant of matrix $\II+\LL$ is equal to the sum of the weights of all the generalized spanning converging forests: $ \det(\II+\LL) = w(\calF).$
    % \begin{equation}
    %     \det(\II+\LL) = w(\calF).
    % \end{equation}
\end{lemma}
\iffalse
\begin{proof}
    We define the function $\pi : V \mapsto V$ as a permutation of the node set $V=\{1,\ldots,n\}$, and use $\mathcal{P}(V)$ to denote the set of all permutations of set $V$.  We use $N(\pi)$ to denote the inversion number of $\pi$, that is $N(\pi) = |\{(i,j): i< j, \pi(i) > \pi(j)\}|$. Each permutation $\pi$ can be decomposed into disjoint cycles $C_1,\ldots,C_{n(\pi)}$, where $n(\pi)$ represents the number of cycles in the decomposition. Let $n^-(\pi)$ and $n^+(\pi)$ denote the number of non-trivial negative and positive cycles in $\pi$, respectively.

    From the definition of determinant, we obtain that 
        \begin{equation}\label{th1-eq2}
 \det(\II+\LL) = \sum_{\pi\in\mathcal{P}(V)} (-1)^{N(\pi)}\prod_{i\in V, \pi(i)=j}\ee_{i}^{\top}(\II+\LL)\ee_{j}. 
    \end{equation}
 For a cycle $C_i$ belonging to $\pi$, its inversion number is ${|C_i|-1}$, and we have $ (-1)^{N(\pi)} = \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1} $. Rewriting the determinant, we obtain:
        \begin{equation}
 = \sum_{\pi\in\mathcal{P}(V)} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}\prod_{i: \pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i: \pi(i)=j,i\neq j}(-w_{ij})
    \end{equation}
We simplify the product terms further:
\begin{equation}
\begin{aligned}
&= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^-(\pi)+n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}w_{ij}\\
        &= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}\abs{w_{ij}}\\ 
\end{aligned}
\end{equation}
For a permutation $\pi$, let $P(\pi) = \{i\in V:\pi(i) = i\} $ be the  set of fixed points. We now define a set of mappings $\mathcal{M}(\pi)$. For a mapping $\widehat{\pi}\in \mathcal{M}(\pi), \widehat{\pi}: V\mapsto V$, it satisfies that 
    \begin{equation}\label{eq3}
         \widehat{\pi}(i)= \left\{\begin{matrix}
j   & i\in P(\pi), j \in \{i\}\cup N_i,\\
\pi(i)  & i\notin P(\pi).
\end{matrix}\right.
    \end{equation} 
For each permutation $\pi \in \mathcal{P}(V)$ and corresponding mapping $\widehat{\pi} \in \mathcal{M}(\pi)$, we define an induced spanning subgraph $\widehat{\calG}(\widehat{\pi}) = (V, E(\widehat{\pi}), w)$, where $E(\widehat{\pi}) = {(i, j) : \widehat{\pi}(i) = j, i \neq j, i \in V}$. We can then express the determinant as follows:
\begin{equation}
\begin{aligned}
        \det(\II+\LL) &=  \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}\prod_{i:\widehat{\pi}(i)=j,i\neq j} \abs{w_{ij}}\\& = \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}  .
\end{aligned}
\end{equation}
We then rearrange the sum order of $\pi$ and $\widehat{\pi}$:
\begin{equation}
=\sum_{\widehat{\pi}} \sum_{\pi: \widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}. 
\end{equation}

For any non-trivial cycles in $\widehat{\calG}(\widehat{\pi})$, either they belong to the decomposition of $\pi$ or not. Let $n^+(\widehat{\pi})$ and $n^-(\widehat{\pi})$ denote the number of non-trivial positive and negative cycles in $\widehat{\calG}(\widehat{\pi})$, respectively. Summing over the non-trivial positive and negative cycles in the decompositions, we find:
\begin{equation}\label{eq4}
\begin{aligned}
       &\sum_{\pi: \widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)} = \sum_{i=1}^{n^+(\widehat{\pi})}\binom{n^+(\widehat{\pi})}{i}(-1)^{i}\sum_{j=1}^{n^-(\widehat{\pi})}\binom{n^-(\widehat{\pi})}{j} 
\\&=  (1-1)^{n^+(\widehat{\pi})}(1+1)^{n^-(\widehat{\pi})}=\left\{\begin{matrix}
 0 & n^+(\widehat{\pi})\neq 0, \\
 2^{n^-(\widehat{\pi})} &n^+(\widehat{\pi})=0 .
\end{matrix}\right.
\end{aligned}
\end{equation}
This implies that for a fixed $\widehat{\pi}$,the expression $\sum_{\pi : \widehat{\pi} \in \mathcal{M}(\pi)} (-1)^{n^+(\pi)}$ equals $2^{n^-(\widehat{\pi})}$ if and only if $n^+(\widehat{\pi}) = 0$. In this scenario, the induced graph $\widehat{\calG}(\widehat{\pi})$ corresponds to the generalized spanning converging forest previously defined. Hence, we conclude:

\begin{equation}
        \det(\II+\LL)    =\sum_{\widehat{\pi}:n^+(\widehat{\pi})=0 }   2^{n^-(\widehat{\pi})} = \sum_{\phi\in \calF} w(\phi) = w(\calF),
\end{equation}
which finished the proof.\end{proof}
\fi
\iffalse
With above equations \eqref{eq1},\eqref{eq2},\eqref{eq3}, \eqref{eq4}, according to the definition of determinant,  we obtain that
    \begin{equation}
       \begin{aligned}
           &\quad \quad \det(\II+\LL) = \sum_{\pi\in\mathcal{P}(V)} (-1)^{N(\pi)}\prod_{i\in V, \pi(i)=j}\ee_{i}^{\top}(\II+\LL)\ee_{j}\\
        &=\sum_{\pi\in\mathcal{P}(V)} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}\prod_{i: \pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i: \pi(i)=j,i\neq j}(-w_{ij})\\
        &= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^-(\pi)+n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}w_{ij}\\
        &= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}\abs{w_{ij}}\\
        &= \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}\prod_{i:\widehat{\pi}(i)=j,i\neq j} \abs{w_{ij}}\\
        &= \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)} w(\widehat{\pi})      =\sum_{\widehat{\pi}} \sum_{\pi: \widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}w(\widehat{\pi})\\
        &= \sum_{\phi\in \calF} w(\phi) = w(\calF),
    \end{aligned} 
    \end{equation}

    \fi

% \begin{theorem}
% For a directed signed graph $\calG=(V, E,w)$, let $(\II+\LL)_{-i,-i}$ denote the matrix obtained by deleting the $j$-th row and column. Then  the determinant of matrix $(\II+\LL)_{-i,-i}$  is related to the generalized spanning converging forests as follows:
% \begin{equation}
% 		\det(\II+\LL)_{-i,-i} =w(\calF_{ii}).
% 	\end{equation}
% \end{theorem} 





\begin{lemma}\label{th-wFij}
For a directed signed graph $\calG=(V, E,w)$, let $(\II+\LL)_{-j,-i}$ denote the matrix obtained by deleting the $j$-th row and $i$-th column. Then  the determinant of matrix $(\II+\LL)_{-j,-i}$  is related to the generalized spanning converging forests as  $\det(\II+\LL)_{-j,-i} =(-1)^{i+j}w(\calF_{ij})$.
% \begin{equation}
% 		\det(\II+\LL)_{-j,-i} =(-1)^{i+j}w(\calF_{ij}).
% 	\end{equation}
\end{lemma} 
\iffalse
\begin{proof}
Similarly to the proof of Lemma~\ref{th-wF}, We now define the function $\pi$ as a  bijection from the node set $V\setminus\{j\}$ to the node set $V\setminus\{i\}$.  We use $N(\pi)$ to denote the inversion number of $\pi$. Notice that the permutation $\pi$ can be  decomposed into a path $P_{ij}$ from node $i$ to node $j$ and disjoint cycles $C_1,\ldots, C_{n(\pi)}$, where $n(\pi)$ denotes the number of cycles in the decomposition. Let $n(P_{ij})$ be the number of nodes in $P_{ij}$. Let $n^-(\pi)$ and $n^+(\pi)$ be the number of non-trivial negative and positive cycles of $\pi$ respectively. And we use ${\rm sign}(P_{ij})$ to denote the sign of the product of the arcs in the path $P_{ij}$. Then one obtains that,
    \begin{equation}
        \prod_{i:\pi(i)=j,i\neq j}w_{ij} =  {\rm sign}(P_{ij})(-1)^{n^-(\pi)}\prod_{i:\pi(i)=j,i\neq j}\abs{w_{ij}}.
    \end{equation}
To obtain the  inversion number of $\pi$, we first define a mapping $\pi'$ mapping the node $j$ to node $i$. Then the mapping $\pi\oplus\pi'$ is a permutation of set $V$. And one obtains that
   \begin{equation}
       (-1)^{N(\pi\oplus\pi')} =(-1)^{n(P_{ij})} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}.
   \end{equation}
Since the change of inversion number after adding $\pi'$ has the same parity as $i+j-1$, one obtains that 
   \begin{equation}
       (-1)^{N(\pi)} =(-1)^{i+j}(-1)^{n(P_{ij})-1} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}.
   \end{equation}
Then following the similar steps in the proof of Lemma~\ref{th-wF}, one obtains that
\begin{equation}
     \det(\II+\LL)_{-j,-i} = (-1)^{i+j}\sum_{\phi\in\calF_{ij}}{\rm sign}(P_{ij})w(\phi) = (-1)^{i+j}w(\calF_{ij}),
\end{equation}
which completes the proof.
\end{proof}
\fi

An illustrative example can be seen in Figure~\ref{f0}, where the determinant of the toy graph $\calG_0$'s matrix $\II+\LL$ is calculated to be 15, aligning with the combined weights of all generalized spanning converging forests: $\phi_1$ to $\phi_9$ each have a weight of 1, while $\phi_{10}$ to $\phi_{12}$ each have a weight of 2.

Building on these foundations, we can now state the Signed Forest Matrix Theorem:
\begin{theorem}[Signed Forest Matrix Theorem]\label{th-qij}
For a directed signed graph $\calG=(V, E,w)$, the entry of the forest matrix $\QQ = (\II+\LL)^{-1} = (q_{ij})_{n\times n} $  is related to the generalized spanning converging forests as  $q_{ij} = \frac{w(\calF_{ij})}{w(\calF)} $.
% \begin{equation}
% 		q_{ij} = \frac{w(\calF_{ij})}{w(\calF)}.
% \end{equation}
\end{theorem} 





% \begin{proof}
% According to Lemma~\ref{th-wF} and Lemma~\ref{th-wFij}, we obtain  that
% \begin{equation}
%     q_{ij} = \frac{(-1)^{i+j}\det(\II+\LL)_{-j,-i}}{\det(\II+\LL)} = \frac{w(\calF_{ij})}{w(\calF)},
% \end{equation}
% which finishes the proof.
% \end{proof}


Theorem~\ref{th-qij} shows that in a signed graph, the entry \(q_{ij}\) of the forest matrix \(\QQ\) represents the ratio of the sum of weights of the generalized spanning converging forests— where the root of node \(i\) is   node \(j\)  —relative to the sum of weights of all generalized spanning converging forests. Notably, when all edges are positive, this finding is consistent with the forest matrix theorem for unsigned graphs  in prior studies~\cite{ChSh06,ChSh98}. Building on the insights provided by Theorem~\ref{th-qij}, we introduce the following lemma, which details specific properties of the entries of the forest matrix in signed graphs:

 
 
 

\begin{lemma}\label{le-pro}
    For a signed graph $\calG = (V,E,w)$, and any distinct nodes $i, j \in V$, the inequality $0 \leq |q_{ij}| \leq q_{jj} \leq 1$ holds. When $\calG$ is a balanced signed graph,  the sum of the absolute values of the entries in any row $i$ equals 1, that is $\sum_{j=1}^n |q_{ij}| = 1$. Moreover, in this scenario, the $i$-th diagonal element $q_{ii}$ satisfies $\frac{1}{1+d_i} \leq q_{ii}\leq \frac{2}{2+d_i}.$ 
\end{lemma}
\iffalse
\begin{proof}
According to Theorem~\ref{th-qij}, it is straightforward to derive that for any distinct nodes $i, j \in V$, the inequality $0 \leq |q_{ij}| \leq q_{jj} \leq 1$ holds. In scenarios where $\calG = (V, E, w)$ constitutes a balanced signed graph, the graph contains no non-trivial cycles. Under such circumstances, the path sign between any pair of nodes $i, j \in V$ is uniformly positive or negative, leading to the equation $\sum_{j=1}^n |q_{ij}| = \frac{\sum_{j=1}^n |w(\calF_{ij})|}{w(\calF)} = 1$. Moreover, leveraging the equation $\QQ(\II+\LL) = 1$, we  obtain that for any node $i\in V$, $1 = (1+d_i)q_{ii} - \sum_{k\neq i} q_{ik}w_{ki}$. That is, $q_{ii } = \frac{1}{1+d_i}(1+\sum_{k\neq i}q_{ik}w_{ki}) \leq \frac{1}{1+d_i}(1+\sum_{k\neq i}|q_{ik}|) =  \frac{1}{1+d_i}(1+q_{ii})$, which can be simplified to $q_{ii}\leq \frac{2}{2+d_i}$. Moreover,  in this case, $q_{ik}w_{ki}$ must be non-negative, leading to the fact that $q_{ii}\geq \frac{1}{1+d_i}$, which finishes the proof. 
\end{proof}
\fi


\section{Positive Loop-Erased Random Walks }
% In this section, we introduce the positive loop-erased random walk on signed graphs, based on which we propose a  sampling algorithm to generate a generalized spanning converging forest. 

\subsection{ Generating a Generalized Spanning Converging Forest Based on Random Walk}
In this subsection, we introduce a random walk approach to  generate a generalized spanning converging forest on signed graphs. Before that, we briefly review the  loop-erasure operation on a random walk~\cite{La80}, since it plays an important role in our algorithm. Concretely, for a random walk $P=v_1,(v_1,v_2),v_2,\ldots,v_{j-1},(v_{j-1},v_j),v_j$, the loop-erasure operation $P_{\rm LE}$ on $P$ is an alternating sequence  $\widetilde{v}_1,(\widetilde{v}_1, \widetilde{v}_2), \widetilde{v}_2\ldots, \widetilde{v}_{q-1}$, $(\widetilde{v}_{q-1}, \widetilde{v}_q),\widetilde{v}_q$ of nodes and edges, which is  obtained inductively  as follows. First, set $\widetilde{v}_1= v_1$ and append $ \widetilde{v}_1$ to $P_{\rm LE}$. Suppose that sequence $\widetilde{v}_1$, $(\widetilde{v}_1, \widetilde{v}_2)$, $\widetilde{v}_2$, $\ldots$, $\widetilde{v}_{h-1}$, $(\widetilde{v}_{h-1},\widetilde{v}_h)$, $\widetilde{v}_h$ has been added to $P_{\rm LE}$ for some $h\geq 1$. If $\widetilde{v}_h=v_j$, then $q= h$ and $\widetilde{v}_h$ is the last node in $P_{\rm LE}$. Otherwise, define $ \widetilde{v}_{h+1}= v_{r+1}$, where $ r = \max\{i:v_i = \widetilde{v }_h \}$. %Then, the extended  Wilson algorithm generating a spanning  rooted forest  $\phi  \in \calF^H$ includes  the following steps.


%Wilson proposed a algorithm  based on loop-erased random walk to get a  spanning tree rooted at a given node~\cite{Wi96}. For a path $ P $, its loop erasure~\cite{LaFr79} is a simple path created by removing all cycles of $ P  $ in chronological order. More precisely, given a path $ P  =  v_1,(v_1,v_2),v_2,\ldots, v_{k-1},(v_{j-1},v_j), v_j $. We use $ V_P = (v_1,v_2,\ldots,v_j) $ to denote the nodes in path $ P $ in order, which we can think of as the first $ j + 1  $ nodes visited by some randomwalk, we define the loop-erasure $ LE(P) $ to be the sequence $ (\widetilde{v}_1,\ldots,\widetilde{v}_q) $ obtained inductively.First set $ \widetilde{v}_1 = v_1 $ and append $ \widetilde{v}_1 $ to $ LE(P) $. Suppose now $ \widetilde{v}_1,\ldots,\widetilde{v}_h $ have been added to  $ LE(P) $ for some $ h\geq 1 $. If $ \widetilde{v}_h  = v_j $, then $ q = h $ and $ \widetilde{v}_h $ is the last node in the sequence $ LE(P) $.  Otherwise, define $ \widetilde{v}_{h+1}  = v_{r+1} $, where $ r = \max\{i:v_i = \widetilde{v_h}  \} $.	



%Wilson proposed a algorithm  based on loop-erased random walk to get a  spanning tree rooted at a given node~\cite{Wi96}. Following the  steps below,  we will give a brief introduction of Wilson's algorithm~\cite{Wi96} to get a spanning tree $\tau $ rooted at node $ u $. 
Wilson proposed an algorithm for generating a spanning tree rooted at a given node based on the loop-erasure operation on a random walk \cite{Wi96}.  However, adapting the conventional loop-erased random walk method to generate a generalized spanning converging forest for signed graphs is challenging, owing to the differences between the signed forest matrix Theorem~\ref{th-qij} and the unsigned case. Negative cycles are allowed in generalized spanning forests for signed graphs, and thus, the traditional loop-erased random walk approach requires modification. To address these challenges, we propose an extension of the traditional loop-erased random walk algorithm to generate a generalized spanning converging forest for signed graphs. Specifically, we describe the steps for generating a generalized spanning converging forest $\phi=(V_\phi,E_\phi)$ in a signed digraph $\mathcal{G}=(V,E,w)$ as follows:

% Since then, the loop-erased random walk has been applied in various fields such as signal processing \cite{LiLiDaWa22}, computation of Pagerank centrality \cite{AvLuGaAl18}, and theoretical probability science \cite{PiAmBaTr21}.


(i) Set $\phi=(V_ {\phi}, E_ {\phi}) = (\emptyset,\emptyset)$. 

(ii) Choose a node $i$ from $ V \setminus V_{\phi } $ and create a random walk $P = v_i$ starting at node $i$ in $ \calG$. 


(iii) At each time step, let $u$ denote the current node of the random walk $P$.  The walk either terminates with probability $\frac{1}{1+d_u}$, in which case node $u$ is added to the set of root nodes of $\phi$, or jumps to a random neighbor $j$ of the current position $u$.  If the former case occurs, proceed to step (v). Otherwise, if the walk jumps from $u$ to $j$, add edge $(u,j)$ and node $j$ to $P$ and proceed to step (iv).

(iv) Suppose that now the random walk  $P$  starts at node $i$ and ends at node $j$. If $j$ is already in the set  $V_{\phi}$, proceed to step (v). Otherwise, check if there exists a negative cycle $C$ in $P$ that includes node $j$. If such a cycle is found, proceed to step (vi). Otherwise, continue the random walk according to step (iii).


(v) Perform loop-erasure operation on the random walk $P$ to get $P_{\rm LE}$, and add the nodes and edges in $P_{\rm LE}$ to $\phi$. Then update $V_{\phi} $ and $E_{\phi}$. If $V_{\phi }  \neq V $, repeat step (ii); otherwise terminate the loop.

(vi) Assume that the current random walk $P$ goes from node $i$ to node $j$, and $j$ belongs to a negative cycle $C$. We can partition $P$ into two parts, namely $P'$ and $C$, where $P'$ is the portion of the walk preceding the negative cycle. The loop-erasure operation is then performed on the path $P'$ to obtain $P'_{\rm LE}$, and the resulting path $(P'_{\rm LE}, C)$, which connects the end of $P'_{\rm LE}$ to the cycle $C$, is added to the graph $\phi$.  The sets of vertices and edges in $\phi$, $V_{\phi}$ and $E_{\phi}$, are then updated accordingly. If $V_{\phi} \neq V$, the circulation starts again from step (ii); otherwise the algorithm terminates.

In Algorithm~\ref{alg-grf}, we provide a detailed description of the pseudocode for algorithm \textsc{GSCF}. It is evident that this algorithm produces a generalized spanning converging forest. In the following subsection, we will delve into the algorithm's workings and prove that its expected running time is independent of the order in which nodes are selected.


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% % algorithm 1
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% \begin{algorithm}[htbp!]
% 	\caption{$\textsc{GSCF}(\calG)$}
% 	\label{alg-grf}
% 	\Input{ $\calG$ : a signed graph	
% 	}
% 	\Output{ $\phi$ : a generalized spanning converging forest}
% 	\textbf{Initialize} :	
%  $\phi\leftarrow \emptyset$\\
% 	\For{$ i = 1 $ to $ n $ }
% 	{$ u \leftarrow i $\; 
%         Create a branch $P \leftarrow \emptyset$\\
% 		\While{ $u\notin V_{\phi}$}{
% 			seed $ \leftarrow $ \textsc{Rand}$(0,1)$  \; 
% 			\If{seed  $\leq {1}/{(1+d_u)} $}{
% 				Mark $u$ as the root node\\
%                 \textbf{break} the circulation
% 			}
% 			\Else{
% 				Select a random neighbor node $v$ from $N(u)$  \\
%                 Add edge $(u,v)$ to  $P$\\
%                 \If{$P$ has a negative cycle $C $}{
%                 \textbf{break} the circulation
% 			}\Else{$u  \leftarrow v$\;}
%                 }
				
% 			}
		
%             \If{ $P$ has a negative cycle $C $}{
%             Partition $P$ into $P'$ and $C$\\
%             Perform loop-erasure operation on $P'$ and get $P'_{\rm LE}$\\
%             Add $P'_{\rm LE}$ and $C$ to $\phi$ and update $V_\phi, E_{\phi}$\\
%             }\Else{
%             Perform loop-erasure operation on $P$ and get $P_{\rm LE}$\\
%             Add $P_{\rm LE}$ to $\phi$ and update $V_\phi, E_{\phi}$\\
%             }
% }
% 	\textbf{return} $ \phi$\;
% \end{algorithm}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	




% \begin{algorithm}[t!]
% \caption{$\textsc{GSCF}(\calG)$}
% \label{alg-grf}
% \begin{algorithmic}[1]
% \STATE {\bfseries Input:} Signed graph $\calG=(V,E)$ with $|V|=n$
% \STATE {\bfseries Output:} Generalized spanning converging forest $\phi$
% \STATE {\bfseries Initialize:} $\phi \leftarrow \emptyset$; $V_\phi \leftarrow \emptyset$; $E_\phi \leftarrow \emptyset$
% \FOR{$i=1,2,\cdots,n$}
%     \STATE $u \leftarrow i$
%     \STATE Create a branch $P \leftarrow \emptyset$
%     \WHILE{$u \notin V_\phi$}
%         \STATE ${\rm seed} \leftarrow \textsc{Rand}(0,1)$
%         \IF{${\rm seed} \le \frac{1}{1+d_u}$}
%             \STATE Mark $u$ as the root node
%             \STATE {\bfseries break}  \COMMENT{break the circulation}
%         \ELSE
%             \STATE Select a random neighbor $v \in N(u)$
%             \STATE Add edge $(u,v)$ to $P$
%             \IF{$P$ has a negative cycle $C$}
%                 \STATE {\bfseries break}  \COMMENT{break the circulation}
%             \ELSE
%                 \STATE $u \leftarrow v$
%             \ENDIF
%         \ENDIF
%     \ENDWHILE
%     \IF{$P$ has a negative cycle $C$}
%         \STATE Partition $P$ into $P'$ and $C$
%         \STATE Perform loop-erasure on $P'$ and obtain $P'_{\rm LE}$
%         \STATE Add $P'_{\rm LE}$ and $C$ to $\phi$; update $V_\phi$ and $E_\phi$
%     \ELSE
%         \STATE Perform loop-erasure on $P$ and obtain $P_{\rm LE}$
%         \STATE Add $P_{\rm LE}$ to $\phi$; update $V_\phi$ and $E_\phi$
%     \ENDIF
% \ENDFOR
% \STATE {\bfseries return} $\phi$
% \end{algorithmic}
% \end{algorithm}




\subsection{ Running Time Analysis   }
In this subsection, we present an analysis of the expected time complexity of Algorithm~\ref{alg-grf}. 


\iffalse
Before doing so, we first introduce some notations. For a signed graph $\mathcal{G} = (V,E,w)$ and a node $i\in V$, we define $t_i$ as a random variable that takes values from the set $\{-1\}\cup N(i)$, where the probability of $t_i = -1$ is $\frac{1}{1+d_i}$, and the probability of $t_i = u$ for any node $u\in N(i)$ is also $\frac{1}{1+d_i}$.  Then we define a matrix $\TT^L = (t^L_{ij})_{n\times L}$.  The entry $t^L_{ij}$ in row $i$ and column $j$ of the matrix $\TT^L$ is a random variable that is independently and identically distributed with $t_i$.

We can utilize the matrix $\TT^L$ to determine the next node to visit during the random walk process in Algorithm~\ref{alg-grf}. To be more specific, we begin by defining a vector $\hh = (h_i)_{n\times 1}$, where $h_i$ is initialized to $1$ at the start of our algorithm. During the random walk process, suppose the walk is currently at node $i$, and we need to select the next target node. We set $j=h_i$, and then look at the $j$-th column of the matrix $\TT^L$ corresponding to node $i$. The entry $t^L_{ij}$ in this column represents the next node to visit. If $t_{ij}^L=-1$, we designate node $i$ as the new root node. Otherwise, if $t_{ij}^L=u$, where $u$ is a node adjacent to $i$, we proceed to node $u$ for the next step of the walk. After selecting the next target node, we update $h_i$ to $h_i + 1$. When Algorithm~\ref{alg-grf} terminates, we obtain a vector $\hh$. We can measure the time complexity of Algorithm~\ref{alg-grf} by computing the $\ell_1$-norm of $\hh$, denoted by $\norm{\hh}_1$, which is simply the sum of all elements in $\hh$, i.e., $\sum_{i=1}^n h_i$.



In Algorithm~\ref{alg-grf}, we perform the loop-erasure operation if a non-trivial positive cycle exists. A cycle with the same nodes may be traversed several times during the algorithm so that it may be erased many times. However, since we use matrix $\TT^L$ to determine the next node to visit, every entry in matrix $\TT^L$ can only form one positive cycle and be erased once.

To denote the cycle $C$ and its position in matrix $\TT^L$, we use the $n$-dimensional vector $\cc = (c_1,\cdots,c_n)^\top$. For any $i\in V$, we have $c_i\in \{0,1,\cdots,L\}$. If $c_i\neq 0$, it means that node $i$ is in the cycle and vice versa. To be more specific, $C$ is composed of edges $(i,t^L_{ic_i})$ for any node $i$ that satisfies $c_i\neq 0$. That is, $C = \bigcup_{i:c_i\neq 0} (i,t^L_{ic_i})$. 


\fi
In Algorithm~\ref{alg-grf}, each time a branch is added to $\phi$ in line 25 or 28, the random walk  restarts from a new node by going back to line 4. Therefore, it is necessary to specify a predetermined order in which the nodes are selected in line 4 of the algorithm. In the following, we present a lemma, demonstrating  that the expected time complexity of Algorithm~\ref{alg-grf} is independent of the order in which the nodes are selected in line 4 of the algorithm.




\begin{lemma}\label{le-indpdt}
For a given graph $\calG=(V,E,w)$, the expected time complexity of Algorithm~\ref{alg-grf} is independent of the order in which the random walk starts at each node.
\end{lemma}

% \begin{proof}
%     Consider two different permutations of the node set $V$, denoted as $\pi_1$ and $\pi_2$. Given a fixed matrix $\TT^L$ with sufficiently large $L$, we apply Algorithm~\ref{alg-grf} twice using $\TT^L$ to determine the next node to visit. In line 2, we choose the new node based on the order of $\pi_1$ and $\pi_2$, respectively. Once Algorithm~\ref{alg-grf} terminates, we obtain two vectors $\hh$ and $\widehat{\hh}$. We claim that $\hh = \widehat{\hh}$.


% Suppose that we erase non-trivial positive cycles  $C^1,\cdots,C^{k}$ in order when we choose the new node based on the order of $\pi_1$.  If $k = 0$, then there is no need for erasing cycles, and in this case  $\hh = \widehat{\hh}$. Now we consider $k>0$, that is, there is at least one positive cycle  to be erased.    For $i = 1,\cdots,k$, we use $\cc^i = (c^i_1,\cdots,c^i_n)^\top$ to denote the  position of cycle $C^i$ in matrix $\TT$. Then for $i\in\{1,\cdots,k-1\}$ and $j\in V$, we have 
% \begin{equation}
% c^{i+1}_j =\left\{\begin{matrix}
%  0 & \text{ if } j\notin C^{i+1}, \\
%  \max\{c^{1}_{j},\cdots,c^{i}_{j}\}+1 & \text{ if } j\in C^{i+1}.
% \end{matrix}\right.    
% \end{equation}
% Moreover, for $i\in V$, we have that $h_i = \max\{c^{1}_{i},\cdots,c^{k}_{i}\}+1$.

% Now, suppose we choose the new node based on the order of $\pi_2$, and the first non-trivial positive cycle to be erased is $\widehat{C}^1$. Let $\widehat{\cc}^1 = (\widehat{c}^1_1,\cdots,\widehat{c}^1_n)^\top$ denote the position of $\widehat{C}^1$ in matrix $\TT^L$. For $i\in V$, either $\widehat{c}^1_i = 0$ and node $i$ is not in cycle $\widehat{C}^1$, or $\widehat{c}^1_i = 1$ and node $i$ belongs to cycle $\widehat{C}^1$. Since $\widehat{C}^1$ is a non-trivial positive cycle, there exists $i\in \widehat{C}^1$ such that $h_i > 1$. This implies that $\widehat{C}^1$ must have some common nodes with cycles $C^1, \cdots, C^k$ that have the same position in matrix $T$. Suppose $C^i$ is the first cycle that has some common nodes with $\widehat{C}^1$. If $\widehat{\cc}^1 \neq \cc^i$, then there is a common node $j\in \widehat{C}^1 \cap C^i$ such that $\widehat{c}^1_j = 1 \neq c^i_j$. This implies that $c^i_j > 1$, which contradicts the fact that $C^i$ is the first cycle having some common nodes with $\widehat{C}^1$. Therefore, $\widehat{C}$ and $C^i$ must be the same cycle, and $\widehat{\cc}^1 = \cc^i$. In other words, $\widehat{C}^1\in{C^1,\cdots,C^k}$.


% Suppose we have erased non-trivial positive cycles $\widehat{C}^1, \ldots, \widehat{C}^u$ based on the order of $\pi_2$, and for $i=1,\ldots,u$, we have $\widehat{C}^i \in {C^1,\ldots,C^k}$. If $u<k$, then the algorithm will not terminate and the next positive cycle to be erased is $\widehat{C}^{u+1}$. Following the previous proof, we can show that $\widehat{C}^{u+1} \in {C^1,\ldots,C^k}$. If $u=k$, then the algorithm terminates. Therefore, if we choose new nodes based on the order of $\pi_2$, only the order of positive loop-erasure will be changed, and we will still have $\hh = \widehat{\hh}$.

% As a result, given a fixed matrix $\TT^L$ with sufficiently large $L$, the random walk order will not affect the time complexity or the return result of Algorithm~\ref{alg-grf}. Thus, if we randomly generate $T$, the expected time complexity of Algorithm~\ref{alg-grf} is independent of the random walk order.
% \end{proof}

 
Next, we present Theorem~\ref{th-Own}, which provides insight into the expected time complexity of Algorithm~\ref{alg-grf}.

\begin{theorem}\label{th-Own}
    The expected time complexity of Algorithm~\ref{alg-grf} is  $O( n)$.
\end{theorem}

% \begin{proof}
% The expected time complexity of Algorithm~\ref{alg-grf} can be expressed as the expected value of the $\ell_1$-norm of $\hh$ when performing Algorithm~\ref{alg-grf} over all possible matrices $\TT^L$. This can be written as $\mathbb{E}\left(\sum_{i=1}^n h_i\right) = \sum_{i=1}^n \mathbb{E}(h_i)$, where the equality follows from the linearity of the expectation. As shown in the proof of Lemma~\ref{le-indpdt}, the expected value of $h_i$, denoted by $\mathbb{E}(h_i)$, is independent of the order in which the random walk starts at each node.






% Suppose that  the random walk starts at node $v_1$. We can estimate $\mathbb{E}( h_1)$ as the expected number of times the walk visits node $v_1$ before terminating. Recall that termination occurs either when a negative cycle is encountered or when a root node is added to the branch at a node $u$, with probability $\frac{1}{1+d_u}$. We can derive an upper bound for $\mathbb{E}( h_1)$ by considering the case where the walk only stops when a root node is added,  ignoring the possibility of stopping at negative cycles. In this case, the probability transition matrix is $\PP = (\II+\DD)^{-1}(\AA^+-\AA^-)$. The expected number of visits to node $v_1$ until termination can be calculated as $\lim_{t\rightarrow\infty}\sum_{i=1}^t \ee_1^\top(\II+\PP+\cdots+\PP^t)\ee_1$. Since the walk in Algorithm~\ref{alg-grf} also terminates when encountering negative cycles, we have the following upper bound:
% \begin{equation}
% \begin{aligned}
%         \mathbb{E}( h_1) &\leq \lim _{t\rightarrow \infty}\sum_{i=1}^t \ee_{1}^\top(\II+\PP+\cdots+\PP^t)\ee_{1} \\ &= \ee_{1}^T(\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD)\ee_{1}.
% \end{aligned}
% \end{equation}





% After summing the expected number of visits for all nodes, we obtain: $    \sum_{i=1}^n \mathbb{E}( h_i) \leq {\rm trace}((\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD)).$

% Let $\widehat{\LL}$ be the matrix $\DD-\AA^++\AA^-$, which is the Laplacian matrix of an unsigned directed graph $\widehat{\calG} = (V,E,\widehat{w})$, where $\widehat{w}_{ij} = \abs{w_{ij}} = 1$. The entry at row $i$ and column $j$ of $\widehat{\LL}$ is denoted by $l_{ij}$. We have $l_{ii} = d_i$ and $l_{ij} = 0$ or $- 1$. Furthermore, the sum of all entries in each row of $\widehat{\LL}$ is equal to $0$. 


 
% Matrix $\widehat{\QQ} = (\II +\widehat{\LL})^{-1} = (\widehat{q}_{ij})_{n\times n}$ is the forest matrix on unsigned graph  $\widehat{\calG}$.  From~\cite{SuZh23}, we have $\frac{1}{1+d_i}\leq \widehat{q}_{ii} \leq \frac{2}{2+d_i}$. Then we can derive the following inequality:
% \begin{equation}
% \begin{aligned}
%           \sum_{i=1}^n \mathbb{E}( h_i) &\leq {\rm trace}((\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD))\\ &= \sum_{i=1}^n \widehat{q}_{ii}(1+d_i) \leq \frac{2(1+d_i)}{2+d_{i} } \leq 2n.
% \end{aligned}
% \end{equation}
%  As a result,   the expected time complexity of algorithm \ref{alg-grf} is at most $O( n)$.
% \end{proof}



\section{Forest Sampling  Algorithm for  Estimating the Forest Matrix}
% In this section, we introduce an efficient sampling-based algorithm to estimate the forest matrix.

\subsection{Estimator for the Entry of Forest Matrix}
In this subsection, we propose estimators for the entries of the forest matrix, leveraging the Signed Forest Matrix Theorem~\ref{th-qij} and the positive loop-erased random walk introduced in Algorithm~\ref{alg-grf}. 
 

Consider a directed signed graph $\calG = (V, E, w)$ with its corresponding forest matrix $\QQ$.  Our goal is to  give an estimation for $\widehat{q}_{ij}$ for the entry $q_{ij}$ for $i,j\in V$. Directly inverting the matrix $\II + \LL$ to obtain $\QQ$ incurs a time complexity of \(O(n^3)\), which is infeasible for   large-scale graphs. According to Theorem~\ref{th-qij}, for any pair of nodes $i, j \in V$, the $(i, j)$-th element $q_{ij}$ of the forest matrix $\QQ$ can be represented as: 
\begin{equation}\label{eq-qij}
    q_{ij} = \frac{w(\calF_{ij})}{w(\calF)} = \frac{\sum_{\phi\in \calF_{ij}}{\rm sign}(P_{ij}) 2^{n^-(\phi)}}{\sum_{\phi \in \calF} 2^{n^-(\phi)}}.
\end{equation}

% For the special case where $i = j$,  the \(i\)-th diagonal element \(q_{ii}\) of the forest matrix $\QQ$ can be expressed as:
% \begin{equation}\label{eq-qii}
%     q_{ii} = \frac{w(\calF_{ii})}{w(\calF)} = \frac{\sum_{\phi \in \calF_{ii}} 2^{n^-(\phi)}}{\sum_{\phi \in \calF} 2^{n^-(\phi)}}.
% \end{equation}

From Equation~\eqref{eq-qij}, the entries of the forest matrix in signed graphs can be interpreted as the ratio of the total weight of forests in $\calF_{ij}$ to the total weight of all forests in $\calF$. Specifically, $\calF_{ij}$ consists of forests where nodes $i$ and $j$ belong to the same connected component, with $j$ serving as the root, that is $\calF_{ij} = \{\phi: r_{\phi}(i) = j,  \phi \in \calF\}$.  In Algorithm~\ref{alg-grf}, a generalized spanning converging forest is generated using a positive loop-erased random walk. To estimate $q_{ij}$, we propose sampling $l$ forests using Algorithm~\ref{alg-grf}. Before defining the estimator, we establish a lemma to demonstrate that the generalized spanning converging forests generated by Algorithm~\ref{alg-grf} are uniformly sampled from the set $\calF$.
\begin{lemma}\label{le-uniform}
    Suppose that $\phi_0\in \calF$ is a fixed generalized spanning converging forest, and Algorithm~\ref{alg-grf} returns a generalized spanning converging forest $\phi$. Then we have $\mathbb{P}(\phi = \phi_0) = \frac{1}{ | \calF |}.$
\end{lemma}

\iffalse
\begin{proof}
In Algorithm~\ref{alg-grf}, suppose that the random walk is currently at node $i$, and a new step is needed. There are two possible scenarios: either node $i$ becomes a root node,  or the walk moves from node $i$ to a random neighbor $j$. Both events occur with a probability of $\frac{1}{1+d_i}$. Consequently, the probability of obtaining any particular generalized spanning converging forest $\phi_0$ from $\calF$ using Algorithm~\ref{alg-grf} is proportional to $\prod_{i=1}^n \frac{1}{1+d_i}$. Therefore, each forest $\phi_0 \in \calF$ can be generated with equal likelihood, which completes the proof.
\end{proof}
\fi
 

With Lemma~\ref{le-uniform}, now we suppose that we execute Algorithm~\ref{alg-grf}  $l$ times to generate $l$ generalized spanning converging forests $\phi_1, \cdots, \phi_l$. Define the estimator    $\widehat{w}_l({\calF} )$  as $ \widehat{w}_l({\calF} ) = \frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)}$. And define the estimator $ \widehat{w}_l({\calF_{ij}} )$ as $    \widehat{w}_l({\calF_{ij}} ) = \frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}}$.
% \begin{equation}
%     \widehat{w}_l({\calF_{ij}} ) = \frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}}.
% \end{equation}
Here, $\mathbb{I}$ denotes the indicator function, and $\mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}}$ takes the value $1$ if node $j$  is the root in forest $\phi_k$, and $0$ otherwise. Then we have the following lemma:
  
\begin{lemma}\label{le-omegal}
       For nodes $i,j\in V$ and $l$ generalized  spanning converging forests   generated from Algorithm~\ref{alg-grf}, the variables $\widehat{w}_l({\calF} )$  and $ \widehat{w}_l({\calF_{ij}} )$  are unbiased estimators of $w(\calF)$ and $w(\calF_{ij})$, respectively. 
\end{lemma}
 \iffalse
\begin{proof}
With Lemma~\ref{le-uniform}, we establish that for each $k = 1, \cdots, l$, the forest $\phi_k$ is uniformly sampled from $\calF$. Consequently, the expected value of the estimator $\widehat{w}_l(\calF)$ is given by:
\begin{equation}
\mathbb{E}(\widehat{w}_l({\calF} ))  =    \mathbb{E}(\frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)})  = \sum_{\phi \in \calF} 2^{n^-(\phi)} = w(\calF).
\end{equation}

Similarly, the expected value of $\widehat{w}_l(\calF_{ij})$ is calculated as follows:
\begin{equation}
\begin{aligned}
\mathbb{E}(\widehat{w}_l({\calF_{ij}} ))  &=    \mathbb{E}(\frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}})  \\ &= \sum_{\phi \in \calF} 2^{n^-(\phi )} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi }(i) = j \}} \\&=  \sum_{\phi \in \calF_{ij}}2^{n^-(\phi)} {\rm sign}(P_{ij})   =  w(\calF_{ij}).
\end{aligned}
\end{equation}
This computation confirms that $\widehat{w}_l(\calF)$ and $\widehat{w}_l(\calF_{ij})$ are indeed unbiased estimators for $w(\calF)$ and $w(\calF_{ij})$, respectively, which  completes the proof. \end{proof}
 \fi
 


According to Lemma~\ref{le-omegal} and equation~\eqref{eq-qij}, we can rewrite the entry $q_{ij}$ as $q_{ij} = {\mathbb{E}(\widehat{w}_l({\calF_{ij}} ))}/{\mathbb{E}(\widehat{w}_l({\calF} )) }$. For each pair of nodes $i,j\in V$, we define the variable $\widehat{q}_{ij} = {\widehat{w}_l({\calF_{ij}} )}/{\widehat{w}_l({\calF} )}$.  Using this sampling-based estimator, we can efficiently approximate the entries of the forest matrix $\QQ$, as well as compute linear combinations of its entries. 


\subsection{Estimation for the Diagonal of Forest Matrix}
In this subsection, we propose an efficient algorithm for estimating the diagonal vector of the forest matrix, which is denoted as $\qq = (q_{11}, \cdots, q_{nn})^\top$.

The diagonal elements of the forest matrix are significant as node centrality measures in unsigned graphs~\cite{JiBaZh19, SuZh23}. In the context of signed graphs, the diagonal entry $q_{ii}$ remains important. Specifically, $q_{ii}$ represents the ratio of the total weight of generalized spanning converging forests rooted at node $i$ to the total weight of all forests in the graph, as shown in Theorem~\ref{th-qij}. Unlike in unsigned graphs, where the lower bound of $q_{ii}$ is $\frac{1}{1 + d_i}$, in signed graphs, $q_{ii}$ can be smaller but remains strictly positive. Furthermore, while off-diagonal entries $q_{ij}$ of the forest matrix can take both positive and negative values, the diagonal entries $q_{ii}$ are always positive, as established in Lemma~\ref{le-pro}.

Signed graphs exhibit a more complex structure due to the presence of negative edges. As a result, existing methods for unsigned graphs~\cite{JiBaZh19, GrAnPrMe21, SuZh24} fail to extend effectively to signed graphs. To address this limitation, we use the vector  $\widehat{\qq} = (\widehat{q}_{11}, \cdots, \widehat{q}_{nn})^\top$, to estimate the diagonal vector $\qq$ of the forest matrix, where each diagonal entry is estimated as $\widehat{q}_{ii} = {\widehat{w}_l({\calF_{ii}} )}/{\widehat{w}_l({\calF} )}$. To efficiently estimate the diagonal vector $\qq$ of the forest matrix $\QQ$, we  sample $l$ generalized spanning converging forests to compute the estimator $\widehat{\qq}$.





% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% % algorithm 2
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% \begin{algorithm}[htbp! ]
% 	\caption{$\textsc{FMDE}(\calG,\sss,l)$}
% 	\label{alg-FMDE}
% 	\Input{ $\calG$ : a signed graph\quad
% $l$: number of samples
% 	}
% 	\Output{ $\widehat{\qq}$ : a vector approximating the diagonal elements
% of the forest matrix}
% 	\textbf{Initialize} :	
%  $\widehat{\qq}[i] \leftarrow 0$, $i=1,\cdots,n$ \quad $\omega \leftarrow 0$\\
% 	\For{$ t = 1 $ to $ l $ }
% 	{$\phi \leftarrow {\rm GSCF}(\calG)$\; 
%          $\omega \leftarrow \omega + 2^{n^-(\phi)}$\\
%          \For{$ i = 1 $ to $ n $ }{
%         \If{$ r_{\phi}(i)  = i$}{
%          $\widehat{\qq}[i] \leftarrow \widehat{\qq}[i] + 2^{n^-(\phi)} $
%         }

%      }
% }
% $ \widehat{\qq} \leftarrow \widehat{\qq}/\omega$\\
% 	\textbf{return} $ \widehat{\qq}$\;
% \end{algorithm}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	





 


However, because the estimator $\widehat{\qq}$ primarily focuses on identifying root nodes, it may overlook additional informative aspects of the network structure. We now propose an alternative expression for the diagonal element $q_{ii}$. Leveraging the equation $\QQ(\II+\LL) = \II$, we  obtain that for any node $i\in V$, $1 = (1+d_i)q_{ii} - \sum_{k\neq i} q_{ik}w_{ki}$. That is, $q_{ii } = \frac{1}{1+d_i}(1+\sum_{k\neq i}q_{ik}w_{ki})$. Accordingly, we define $\widetilde{q}_{ ii}$ as $\widetilde{q}_{ ii} = \frac{1}{1+d_i}(1+\sum_{k\neq i}\widehat{q}_{ik}w_{ki})$, and we use $\widetilde{q}_{ii}$ to estimate $q_{ii}$. Below, we outline the pseudocode for our two algorithms, named \textsc{Forest Matrix Diagonal Estimator  (FMDE)} and \textsc{Forest Matrix Diagonal Estimator Plus (FMDE+)}. The pseudocodes are provided in  Appendix.

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% % algorithm 2
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% \begin{algorithm}[hbtp!  ]
% 	\caption{$\textsc{FMDE+}(\calG,\sss,l)$}
% 	\label{alg-FMDE+}
% 	\Input{ $\calG$ : a signed graph\quad
% $l$: number of samples
% 	}
% 	\Output{ $\widetilde{\qq}$ : a vector approximating the diagonal elements of the forest matrix}
% 	\textbf{Initialize} :	
%  $\widetilde{\qq}[i] \leftarrow 0$, $i=1,\cdots,n$ \quad $\omega \leftarrow 0$\\
% 	\For{$ t = 1 $ to $ l $ }
% 	{$\phi \leftarrow {\rm GSCF}(\calG)$\; 
%          $\omega \leftarrow \omega + 2^{n^-(\phi)}$\\
%          \For{$ i = 1 $ to $ n $ }{
%         $j = r_{\phi}(i)$\\
%         \If{$ j> 0\And i\in N(j)$ }{
%          $\widetilde{\qq}[i] \leftarrow \widetilde{\qq}[i] + {\rm sign}(P_{ij})\omega_{ji}2^{n^-(\phi)} $
%         }
%      }
% }
% \For{$ i = 1 $ to $ n $  }{ 
% $\widetilde{\qq}[i] \leftarrow  \frac{\widetilde{\qq}[i]}{\omega(1+d_i)} + \frac{1}{1+d_i}  $

% }
% \textbf{return} $ \widetilde{\qq}$\;
% \end{algorithm}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% % Combined Algorithm: FMDE/FMDE+
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	
% \begin{algorithm}[htbp!]
% 	\caption{\textsc{FMDE/FMDE+}($\calG$, $l$)}
% 	\label{alg-FMDE}
% 	\Input{ 
% 	    $\calG$ : a signed graph\\
% 	    $l$: number of samples
% 	}
% 	\Output{ 
% 	    $\widehat{\qq}$, $\widetilde{\qq}$ : estimator from \textsc{FMDE} and \textsc{FMDE+}
% 	}
% 	\textbf{Initialize}:\\
% 	$\widehat{\qq}[i], \widetilde{\qq}[i] \leftarrow 0$, for $i = 1, \cdots, n$, 	$\gamma \leftarrow 0$\\

% 	\For{$t = 1$ to $l$}{
% 	    $\phi \leftarrow {\rm GSCF}(\calG)$\\
% 	    $\gamma \leftarrow \gamma + 2^{n^-(\phi)}$\\
	    
% 	    \For{$i = 1$ to $n$}{
%                     $j \leftarrow r_{\phi}(i)$\\
% 	        \If{$j = i$}{
% 	            $\widehat{\qq}[i] \leftarrow \widehat{\qq}[i] + 2^{n^-(\phi)}$
% 	        }
	        
	        
% 	        \If{$j > 0 \And i \in N(j)$}{
% 	            $\widetilde{\qq}[i] \leftarrow \widetilde{\qq}[i] + {\rm sign}(P_{ij}) w_{ji} 2^{n^-(\phi)}$
% 	        }
% 	    }
% 	}

% 	$\widehat{\qq} \leftarrow \widehat{\qq} / \gamma$\\

% 	\For{$i = 1$ to $n$}{
% 	    $\widetilde{\qq}[i] \leftarrow \frac{\widetilde{\qq}[i]}{\gamma(1 + d_i)} + \frac{1}{1 + d_i}$
% 	}

% 	\textbf{return} $\widehat{\qq}, \widetilde{\qq}$
% \end{algorithm}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



% \begin{algorithm}
% \caption{\textsc{FMDE/FMDE+}($\calG,l$)}
% \label{alg-FMDE}
% \begin{algorithmic}[1]
% \STATE {\bfseries Input:} Signed graph $\calG$; sample number $l$
% \STATE {\bfseries Output:} $\widehat{\qq}$ (\textsc{FMDE} estimator), $\widetilde{\qq}$ (\textsc{FMDE+} estimator)
% \STATE {\bfseries Initialize:} $\widehat{\qq}[i]\leftarrow 0$, $\widetilde{\qq}[i]\leftarrow 0$ for $i=1,\ldots,n$; $\gamma \leftarrow 0$
% \FOR{$t=1,2,\ldots,l$}
%     \STATE $\phi \leftarrow \textsc{GSCF}(\calG)$
%     \STATE $\gamma \leftarrow \gamma + 2^{n^{-}(\phi)}$
%     \FOR{$i=1,2,\ldots,n$}
%         \STATE $j \leftarrow r_{\phi}(i)$
%         \IF{$j=i$}
%             \STATE $\widehat{\qq}[i] \leftarrow \widehat{\qq}[i] + 2^{n^{-}(\phi)}$
%         \ENDIF
%         \IF{$j>0$ {\bfseries and} $i\in N(j)$}
%             \STATE $\widetilde{\qq}[i] \leftarrow \widetilde{\qq}[i] + {\rm sign}(P_{ij})\, w_{ji}\, 2^{n^{-}(\phi)}$
%         \ENDIF
%     \ENDFOR
% \ENDFOR
% \STATE $\widehat{\qq} \leftarrow \widehat{\qq} / \gamma$
% \FOR{$i=1,2,\ldots,n$}
%     \STATE $\widetilde{\qq}[i] \leftarrow \frac{\widetilde{\qq}[i]}{\gamma(1+d_i)} + \frac{1}{1+d_i}$
% \ENDFOR
% \STATE {\bfseries return} $\widehat{\qq}, \widetilde{\qq}$
% \end{algorithmic}
% \end{algorithm}





We now introduce Theorem~\ref{th-var} that highlights the efficiency of the estimator \( \widetilde{q}_{ii}\) compared to \( \widehat{q}_{ii}\) within the context of balanced signed graphs.

\begin{theorem}\label{th-var}
In a balanced signed graph $\calG$, the variance of  estimator   $\widetilde{q}_{ii}$ is lower than that of  $\widehat{q}_{ii}$. This suggests that, for a fixed number of samples \(l\), \( \widetilde{q}_{ii}\) is likely to yield a closer approximation to the true value   \(q_{ii}\) than \( \widehat{q}_{ii}\).
\end{theorem}

 
% \begin{proof}
%    In a balanced signed graph $\calG$, there are no negative cycles. Then we have  $\widehat{q}_{ij} =  \frac{1}{l} \sum_{k=1}^l   {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}},$ $\widehat{q}_{ii} = \frac{1}{l}   \sum_{j=1}^l  \mathbb{I}_{\{i\in \calR(\phi_j)\}},$  $\widetilde{q}_{ii} = \frac{1}{1+d_i}(1+\sum_{k\neq i}\widehat{q}_{ik}w_{ki}).$ Since $\phi_1,\phi_2,\cdots,\phi_l$ are independently and uniformly sampled from the set $\calF$, the sample size $l$ does not influence the relative variances \( \widetilde{q}_{ii}\) and \( \widehat{q}_{ii}\). For simplicity, we assume $l=1$ for the remainder of this proof. Under this assumption, the variance of $\widehat{q}_{ii}$ is $ {\rm Var}(\widehat{q}_{ii}) = q_{ii} - q_{ii}^2$. 
%     The variance of $\widetilde{q}_{ii}$ can be derived as follows:
%     \begin{equation}\label{varvar}
%     \begin{aligned}
%     &\quad {\rm Var}(\widetilde{q}_{ii})= \mathbb{E}(\widetilde{q}_{ii})^2 - (\mathbb{E}(\widetilde{q}_{ii}))^2 = \frac{1}{(1+d_i)^2}\mathbb{E}(( 1+ \sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
%      \\ &= \frac{1}{(1+d_i)^2}\mathbb{E}(1+2\sum_{k\neq i}\widehat{q}_{ik}w_{ki}+ (\sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
%      \\ &= \frac{1+3\sum_{k\neq i}{q}_{ik}w_{ki}}{(1+d_i)^2}-q_{ii}^2  =  \frac{1+3((1+d_i)q_{ii}-1)}{(1+d_i)^2} - q_{ii}^2 \\ &=\frac{3q_{ii}}{1+d_i} - \frac{2}{(1+d_i)^2}  -q_{ii}^2.
%     \end{aligned}
% \end{equation}
% The simplification uses the assumptions that $\mathbb{E}(\widehat{q}_{ik}\widehat{q}_{is}) = 0$ for any $k\neq s\neq i$ and $\mathbb{E}(\widehat{q}_{ik}^2)= |q_{ik}| ={q}_{ik}w_{ki} $ in balanced signed graphs.
% Then we get the following equality:
% \begin{equation}
%         {\rm Var}\{\widehat{q}_{ii}\} - {\rm Var}\{\widetilde{q}_{ii}\}    =\frac{2(1-q_{ii})}{(1+d_i)^2}+ \frac{d_{i}(d_i-1)q_{ii}}{(1+d_i)^2}\geq 0.
% \end{equation}
% It shows that the variance of $\widetilde{q}_{ii}$  is no more than  the variance of the estimator $\widehat{q}_{ii}$, which completes the proof.
% \end{proof}

Theorem~\ref{th-var} theoretically demonstrates that in balanced signed graphs, the \textsc{FMDE+} algorithm outperforms \textsc{FMDE} due to its use of estimators with reduced variance. In the experimental section below, we will show that \textsc{FMDE+} also achieves superior accuracy compared to \textsc{FMDE} even in unbalanced signed graphs.


Utilizing Theorem~\ref{th-Own},  the time complexity of Algorithm~\ref{alg-FMDE} is $O(ln)$, where $l$ is the number of  generalized spanning converging forests.  As we increase the number of sampled  forests $l $, we observe a corresponding decrease in the estimation error between $\widehat{\qq}[i]$ and the actual value $q_{ii}$. To quantify this relationship, we introduce Theorem~\ref{th-l}, which specifies the necessary size of $l$ to achieve a necessary  error guarantee with a high probability.  


\begin{theorem}\label{th-l}
    Define $\alpha   = \max \{2^{n^-(\phi)} : \phi \in \calF \}$ and $\beta = {\sum_{\phi \in \calF}  2^{n^-(\phi)}}/{|\calF|}$.   For any node $i\in V$, and parameters $\epsilon, \delta \in (0,1)$, if $l$ is chosen obeying $l = \left \lceil \frac{1}{2} \frac{\alpha^2}{\beta^2} (\frac{\epsilon +2 }{\epsilon})^2 \log(\frac{2}{\delta})   \right \rceil$, then the following inequalities hold with probability at least $1 - \delta$:  
    \begin{equation}\label{ineq1}
        \mathbb{P}(|\widehat{w}_l(\calF)-w(\calF)| \ge |\calF| \frac{\epsilon \beta }{ 2+ \epsilon }) < \delta.
    \end{equation}
    \begin{equation}\label{ineq2}
        \mathbb{P}(|\widehat{w}_l(\calF_{ii})-w(\calF_{ii})| \ge |\calF| \frac{\epsilon \beta }{ 2+ \epsilon }) < \delta.
    \end{equation}
 If the following inequalities hold, then the approximation $\widehat{  \qq  }[i]$ of $ q_{ii}$  returned by  Algorithm~\ref{alg-FMDE} satisfies the following relation: $q_{ii}	- \epsilon \leq 	\widehat{\qq}[i]   \leq    q_{ii} + \epsilon$.
	% \begin{equation}\label{eq-omegaii}
	% 	 q_{ii}	- \epsilon \leq 	\widehat{\qq}[i]   \leq    q_{ii} + \epsilon.
	% \end{equation} 
\end{theorem}
\iffalse
\begin{proof}
Setting $a = 0$ and $b = |\calF| \alpha$, and choosing $l$ as previously specified,  we can prove the inequalities~\eqref{ineq1} and~\eqref{ineq2} directly by utilizing Hoeffding's inequality. Assuming the above inequalities hold, the error in the estimated ratio can be bounded as   
    \begin{equation}
        \begin{aligned}
             &\quad \left | \widehat{\qq}[i] - q_{ii} \right | =     \left | \frac{\widehat{w}_l(\calF_{ii})}{ \widehat{w}_l(\calF)} - \frac{w(\calF_{ii})}{w(\calF)}\right | \\& = \left | \frac{w(\calF_{ii})(\widehat{w}_l(\calF )-w(\calF)) + w(\calF) (w(\calF_{ii}) - \widehat{w}_l(\calF_{ii})  )  }{\widehat{w}_l(\calF)w(\calF)}\right | \\& \leq 
              \frac{w(\calF_{ii})|\widehat{w}_l(\calF )-w(\calF)|+ w(\calF) |w(\calF_{ii}) - \widehat{w}_l(\calF_{ii}) |  }{\widehat{w}_l(\calF)w(\calF)} \\ & \leq \frac{\frac{\epsilon \beta }{ 2+ \epsilon } (w(\calF_{ii}) + w(\calF))|\calF|}{\widehat{w}_l(\calF)w(\calF)} \leq \frac{\frac{2\epsilon\beta}{2+\epsilon}}{\beta-\frac{\epsilon\beta}{2+\epsilon}} = \epsilon,
        \end{aligned}
    \end{equation}
where the last inequality holds since $w(\calF_{ii}) \leq w(\calF)$, $w(\calF) = |\calF|\beta $, and $\widehat{w}_l(\calF) \leq w(\calF)-|\calF| \frac{\epsilon \beta }{ 2+ \epsilon }$. This finishes the proof.
\end{proof}
\fi
In real-life networks, the percentage of negative edges is extremely small~\cite{ChHsNaDhTe14}. Moreover, it is believed that a signed social network evolves towards a balanced state; otherwise, a state of unbalance will produce tension~\cite{SiAd17}. Note that when there are no negative edges or $\calG$ constitutes a balanced signed graph, the factor $\alpha/\beta $ equals 1. Consequently, according to Theorem~\ref{th-l}, the required sample size \(l\) will not become excessively large due to an expansion in the ratio $\alpha/\beta$. This ensures that our sampling algorithm remains efficient and practical for applications in real-life networks. 
 

\subsection{Expressed Opinion Estimation in Signed Friedkin-Johnsen Model}

The Friedkin-Johnsen (FJ) model is a popular model for analyzing opinion evolution and formation on graphs~\cite{FrJo90,BiKlOr15,HeZhLiRu20,RaHo21}. In the signed FJ model, each node  $i\in V$ is associated with two types of opinions: the internal opinion and the expressed opinion. In the signed FJ model, each node \( i \in V \) has an internal opinion \( s_i \in [-1,1] \) and an expressed opinion \( z_i(t) \) at time \( t \). At time $t+1$, the expressed opinion evolves according to $z_i(t+1) = \frac{1}{1+d_i}({s_i +\sum_{j\in N(i)}w_{ij}z_j(t)}) $.
% \begin{equation}\label{FJ}
% 	\zz_i(t+1) = \frac{\sss_i +\sum_{j\in N(i)}w_{ij}\zz_j(t)}{1+d_i}.
% \end{equation}
Let \( \sss = (s_1, s_2, \ldots, s_n)^\top \) be the internal opinion vector. The expressed opinion vector converges to an equilibrium \( \zz = (z_1, z_2, \ldots, z_n)^\top \) satisfying $\zz = (\II+\LL)^{-1}\sss = \QQ\sss$. 

While the signed FJ model has been widely studied~\cite{XuHuWu20,RaHo21,HeZhLiRu20,HeZeZhLi22,TaChAgLi16,HaBhPa24}, efficient algorithms for estimating expressed opinions in directed signed graphs are lacking due to the difficulty of estimating the forest matrix.

Using the predefined estimator, we can approximate the $i$-th expressed opinion $z_i$. Since $z_i = \sum_{j=1}^n q_{ij} s_j$ and $\widehat{q}_{ij}$ serves as an estimator for $q_{ij}$, we define $\widehat{z_i} = \sum_{j=1}^n \widehat{q}_{ij} s_j$ as the estimator for $z_i$. Specifically, we first sample a set of $l$ generalized spanning converging forests, stored in a forest list $L$, using Algorithm~\ref{alg-grf}. This sampling procedure incurs a time and space complexity of $O(ln)$.

To estimate the expressed opinion of a specific node, we traverse the forest list to compute $\widehat{z_i}$, which requires only $O(l)$ time. This process is detailed in the following algorithm, \textsc{FJOE} (Friedkin-Johnsen Opinion Estimation). Notably, while the internal opinion vector $s$ may change, resampling the forest is unnecessary as long as the graph structure remains unchanged. This allows our algorithm to efficiently query the expressed opinion.
 

%  \begin{algorithm}[htbp!]
%     \caption{\textsc{FJOE}($L$, $i$, $\sss$)}
%     \label{alg-opinion-estimation}
%     \Input{
%         $L$: a list of $l$ generalized spanning converging forests\\
%         $i$: node to query,  $\sss$: internal opinion vector
%     }
%     \Output{
%         $\widehat{z_i}$: estimated expressed opinion for node $i$
%     }

%     \textbf{Initialize}:\\
%     $\widehat{z_i}, \gamma \leftarrow 0$\\
 
%     \ForEach{$\phi \in L$}{
%         $\gamma \leftarrow \gamma + 2^{n^-(\phi)}$\\
%         \For{$j = 1$ to $n$}{
%             $k \leftarrow r_{\phi}(j)$\\
%             $\widehat{z_i} \leftarrow \widehat{z_i}  + {\rm sign}(P_{jk})   2^{n^-(\phi)}s_k$\\
%         }
%     }
    
%     $\widehat{z_i} \leftarrow \widehat{z_i} / \gamma$ 

%     \textbf{return} $\widehat{z_i}$
% \end{algorithm}


% \begin{algorithm}
% \caption{\textsc{FJOE}($L,i,\sss$)}
% \label{alg:opinion-estimation}
% \begin{algorithmic}[1]
% \STATE {\bfseries Input:} 
% List $L$ of $l$ generalized spanning converging forests; node index $i$; internal opinion vector $\sss$
% \STATE {\bfseries Output:} Estimated expressed opinion $\widehat{z_i}$ for node $i$
% \STATE {\bfseries Initialize:} $\widehat{z_i} \leftarrow 0$; $\gamma \leftarrow 0$
% \FORALL{$\phi \in L$}
%     \STATE $\gamma \leftarrow \gamma + 2^{n^{-}(\phi)}$
%     \FOR{$j=1,2,\ldots,n$}
%         \STATE $k \leftarrow r_{\phi}(j)$
%         \STATE $\widehat{z_i} \leftarrow \widehat{z_i} + {\rm sign}(P_{jk})\, 2^{n^{-}(\phi)}\, s_k$
%     \ENDFOR
% \ENDFOR
% \STATE $\widehat{z_i} \leftarrow \widehat{z_i} / \gamma$
% \STATE {\bfseries return} $\widehat{z_i}$
% \end{algorithmic}
% \end{algorithm}





By setting $l = O(\frac{\alpha^2}{\beta^2} \cdot \frac{1}{\epsilon^2} \log\left(\frac{1}{\delta}\right))$, following the approach  in Theorem~\ref{th-l}, we can guarantee that the estimation error satisfies  $|\widehat{z_i} - z_i| \leq \epsilon$ with a probability of at least $1 - \delta$.

  


\section{Experiments}
% In this section, we conduct extensive experiments on various real-life networks in order to evaluate the performance of our algorithms, in terms of accuracy and efficiency.  Our source code is publicly available on \url{https://anonymous.4open.science/r/SignedForestDiagonal-FA09}.
 \subsection{Setup}
 \textbf{Dataset.}
 The datasets of selected real networks are publicly available in the KONECT~\cite{Ku13} and SNAP~\cite{LeSo16}.  Our experiments are conducted on a diverse range of networks. Details of these datasets are presented in Table~\ref{datasets}. We utilize both original signed graphs and modified signed graphs for our experiments. The modified signed graphs are generated from real unsigned graphs by randomly assigning a negative sign to each edge with a probability of 0.2. These  modified signed graphs are denoted with a superscript asterisk in Table~\ref{datasets}.
 

% All experiments are conducted using the Julia programming language in a computational environment equipped with a 2.10 GHz Intel(R) Xeon(R) Platinum 8352V CPU and 256GB of primary memory.
 
  
% \begin{table}[htbp!]\fontsize{8}{11}\caption{Datasets used in experiments. }\label{datasets}
% \begin{tabular}{cccc}
% \hline
% Type                                                                                    & Network         & Nodes      & Edges       \\ \hline
% \multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Small\\ Graphs\end{tabular}}                 & Adolesent$^*$   & 2,539      & 12,969      \\ & Bitcoinotc      & 5,881      & 35,592      \\    & Gnutella08$^*$    & 6,301      & 20,777      \\   & Wikielec   & 7,118      & 103,675     \\   & Wikipedia$^*$  & 17,649     & 296,918     \\   & SlashdotZoo   & 79,120     & 515,397     \\ \hline
% \multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Medium \\ and\\ Large\\ Graphs\end{tabular}} & Epinions        & 131,828    & 841,372     \\   & WikiL           & 258,259    & 3,187,096   \\   & Youtube$^*$         & 1,134,890  & 2,987,624   \\   & Dblp$^*$            & 5,624,219  & 12,282,055  \\   & Livejournal$^*$     & 7,489,073  & 112,307,315 \\   & FullUSA$^*$         & 23,947,300 & 57,708,600  \\ \hline
% \end{tabular}
% \end{table}


 
\noindent\textbf{Algorithms.}
To evaluate the performance of our algorithms in estimating the diagonal elements for forest matrix of signed graphs, we compare our two proposed algorithms, \textsc{FMDE} and \textsc{FMDE+}, against the ground truth, which is obtained by directly inverting the matrix $\II+\LL$.  Additionally, we evaluate the accuracy of \textsc{FJOE} by performing 100 random queries and comparing the results with the ground truth. 
 


\subsection{  Forest Matrix Diagonal Estimation }
\subsubsection{Accuracy} We first   evaluate the accuracy of our algorithms \textsc{FMDE} and \textsc{FMDE+} with the ground truth. To this end, we conduct experiments on six small-sized networks, as obtaining the ground truth by inverting the matrix $\II+\LL$ is computationally intensive and memory-consuming for larger graphs. The details of these networks: Adolescent$^*$, Bitcoinotc, Gnutella08$^*$, Wikielec,  Wikipedia$^*$, and SlashdotZoo are listed in Table~\ref{datasets}. Of these, three are original signed graphs, while the remaining three, marked with a superscript asterisk, are modified signed graphs.


 To evaluate the accuracy of our two algorithms, we use the average relative error across all nodes. For each signed graph $\calG=(V,E,w)$, we initially compute the forest matrix $\QQ = (\II+\LL)^{-1}$ to obtain its diagonal $\qq$.  Our algorithms, \textsc{FMDE} and \textsc{FMDE+}, then estimate the diagonal, resulting in $\widehat{\qq}$ and $\widetilde{\qq}$, respectively. The average relative error for algorithm \textsc{FMDE} is calculated using $\frac{1}{n}\sum_{i=1}^n\frac{|\qq_i - \widehat{\qq}_i|}{\qq_i}$, and similarly for \textsc{FMDE+}. We set $\epsilon = 0.1, 0.2, 0.3$ to examine performance under these settings, with the results depicted in Figure~\ref{f1}.


  


\begin{figure}[htbp!]
	\centering
	\includegraphics[width=1\columnwidth]{bar1}
	\caption{Comparison of  average   relative errors of the diagonals for  algorithms \textsc{FMDE} and \textsc{FMDE+} on six   graphs: Bitcoinotc(a), Wikielec(b), SlashdotZoo(c), Adolescent$^*$(d),  Gnutella08$^*$(e), Wikipedia$^*$(f)  across three different settings of  $\epsilon$.  }\label{f1}	
\end{figure}
 

The results displayed in Figure~\ref{f1} demonstrate that as \(\epsilon\) decreases, the number of samples increases, which consequently reduces the average relative error. This trend is consistent for both algorithms, \textsc{FMDE} and \textsc{FMDE+}. Furthermore, despite the distinction between original signed graphs (a), (b), (c) and modified signed graphs (d), (e), (f), the performance outcomes are comparably robust. Notably, \textsc{FMDE+} significantly outperforms \textsc{FMDE} in terms of accuracy, achieving results approximately ten times better. Specifically, the average relative error for \textsc{FMDE+} remains below 0.01 across all tested graphs. In particular instances, such as in graphs (b) and (f), the error margin even drops below 0.001 for all three \(\epsilon\) settings. This marked improvement is attributed to the enhancements incorporated in \textsc{FMDE+}, which employs a superior estimator as theoretically detailed in previous sections. In conclusion, the results returned by the \textsc{FMDE+} algorithm are more convincing and exhibit high accuracy.



 
\subsubsection{Efficiency and Scalability} We now demonstrate that our algorithms, \textsc{FMDE} and \textsc{FMDE+}, are more efficient than the direct matrix inversion method, referred to here as \textsc{EXACT}. To illustrate this, Table~\ref{tb-time} compares the performance of \textsc{EXACT}, \textsc{FMDE}, and \textsc{FMDE+}. The results indicate that for the first six small-sized graphs, both \textsc{FMDE} and \textsc{FMDE+} significantly outperform \textsc{EXACT} in terms of computational speed for all three \(\epsilon\) settings chosen. Furthermore, it is observed that as \(\epsilon\) decreases, the running time increases. Besides, algorithm \textsc{FMDE+}, requires slightly more time than \textsc{FMDE} for a fixed \(\epsilon\) due to its need to collect additional information, as outlined in Algorithm~\ref{alg-FMDE}.



\begin{table}[htbp!]\small\fontsize{7}{12}\caption{Running time (seconds)  of algorithms \textsc{EXACT}, \textsc{FMDE} and \textsc{FMDE+}.  }\label{tb-time}
\setlength{\tabcolsep}{.8 mm} 
\begin{tabular}{cccccccc}
\hline
\multirow{3}{*}{Network} & \multicolumn{7}{c}{Time(seconds)}                                                     \\ \cline{2-8} 
                         & \multirow{2}{*}{EXACT} & \multicolumn{3}{c}{FMDE}         & \multicolumn{3}{c}{FMDE+} \\ \cline{3-8} 
                         &                        & $\epsilon$ = 0.3 & 0.2   & 0.1   & 0.3     & 0.2    & 0.1    \\ \hline
Adolescent          & 0.30                   & 0.019            & 0.023 & 0.031 & 0.046   & 0.063  & 0.095  \\
Bitcoinotc               & 1.87                   & 0.039            & 0.055 & 0.070 & 0.072   & 0.118  & 0.165  \\
Gnutella08           & 2.28                   & 0.025            & 0.041 & 0.060 & 0.032   & 0.044  & 0.064  \\
Wikielec            & 3.01                   & 0.031            & 0.045 & 0.062 & 0.041   & 0.052  & 0.098  \\
Wikipedia           & 22.96                  & 0.066            & 0.106 & 0.131 & 0.410   & 0.677  & 0.874  \\
SlashdotZoo              & 991.5                  & 0.361            & 0.464 & 0.791 & 0.487   & 0.833  & 1.033  \\
Epinions                 & -                      & 0.377            & 0.587 & 0.854 & 0.345   & 0.616  & 1.141  \\
WikiL                    & -                      & 0.701            & 1.535 & 2.036 & 0.732   & 1.577  & 2.222  \\
Youtube                  & -                      & 4.656            & 10.19 & 11.45 & 6.378   & 13.68  & 22.13  \\
Dblp                     & -                      & 53.55            & 168.8 & 269.3 & 108.2   & 325.5  & 518.0  \\
Livejournal              & -                      & 459.0            & 1031  & 1623  & 604.1   & 1311   & 2114   \\
FullUSA                  & -                      & 918.8            & 1832  & 2803  & 1204    & 2015   & 3598   \\ \hline
\end{tabular}
\end{table}




However, for the large graphs \textsc{EXACT} is  unable to execute due to time and memory constraints. In contrast, \textsc{FMDE} and \textsc{FMDE+} continue to perform efficiently on these networks. Notably, both algorithms are scalable to  massive networks with more than twenty million nodes, such as FullUSA, which has over \(2.3 \times 10^7\) nodes. Remarkably,  both algorithms deliver results for our three $\epsilon$ settings within at most one hour.  Thus, \textsc{FMDE} and \textsc{FMDE+} not only provide accurate estimation of the diagonal elements of the forest matrix but also demonstrate remarkable efficiency and scalability to extensive graph sizes.



\subsection{   Opinion Estimation in   Signed FJ Model }
In this subsection, we evaluate the accuracy of \textsc{FJOE} by performing 100 random queries and comparing the results with the ground truth. We vary the $\epsilon$ values at 0.3, 0.2, and 0.1, and determine $l$ based on Theorem~\ref{th-l}. The \textsc{FJOE} algorithm requires pre-sampling of $l$ generalized spanning converging forests, and its running time is comparable to that of FMDE, as shown in Table~\ref{tb-time}. The ground truth is obtained via matrix inversion, with computational time similar to that of EXACT in Table~\ref{tb-time}.  We present the running time of \textsc{FJOE} along with the average absolute error of the opinions computed over 100 random queries. The details are summarized in Table~\ref{tb-time1}.
 
\begin{table}[htbp!]\fontsize{8}{12}\caption{Running time($\times 10^{-4}$ seconds) and absolute error ($\times 10^{-2}$) of algorithm \textsc{FJOE}   }\label{tb-time1}
\setlength{\tabcolsep}{1.2 mm} 
 \begin{tabular}{ccccccccc}
\hline
\multirow{2}{*}{Network} &  & \multicolumn{3}{c}{Time for FJOE } &  & \multicolumn{3}{c}{Absolute Error } \\ \cline{3-5} \cline{7-9} 
                         &  & $\epsilon$ =0.3         & 0.2         & 0.1          &  & 0.3              & 0.2             & 0.1             \\ \hline
Adolescent                &  & 1.1                     & 3.2         & 7.3          &  & 2.1              & 1.5             & 0.9             \\
Bitcoinotc               &  & 1.2                     & 4.2         & 9.5          &  & 3.2              & 2.3             & 1.6             \\
Gnutella08           &  & 1.1                     & 3.2         & 8.5          &  & 0.7              & 0.2             & 0.1             \\
Wikielec            &  & 2.0                     & 5.2         & 7.4          &  & 1.2              & 0.9             & 0.7             \\
Wikipedia           &  & 2.5                     & 6.1         & 8.2          &  & 3.1              & 2.9             & 1.5             \\
SlashdotZoo              &  & 2.1                     & 5.0         & 7.2          &  & 2.1              & 1.2             & 0.4             \\
Epinions                 &  & 2.4                     & 4.9         & 8.2          &  & -                & -               & -               \\
WikiL                    &  & 1.9                     & 5.1         & 9.5          &  & -                & -               & -               \\
Youtube                  &  & 2.5                     & 6.5         & 10.2         &  & -                & -               & -               \\
Dblp                     &  & 2.8                     & 5.8         & 9.8          &  & -                & -               & -               \\
Livejournal              &  & 2.7                     & 6.0         & 10.2         &  & -                & -               & -               \\
FullUSA                  &  & 2.9                     & 7.2         & 11.5         &  & -                & -               & -               \\ \hline
\end{tabular}
\end{table}
 % \vspace{-0.5em}
Table~\ref{tb-time1} shows that as $\epsilon$ decreases, the corresponding $l$ increases, leading to smaller absolute errors. Our algorithm, \textsc{FJOE}, operates with a time complexity of $O(l)$ and demonstrates exceptionally fast performance. For instance, on the largest graph, FullUSA, the running time is less than $3 \times 10^{-4}$ seconds when $\epsilon = 0.3$. This indicates that the algorithm's efficiency remains largely unaffected by the growth in graph size. Furthermore, the absolute error remains under $2\times10^{-2}$  for the first six graphs when $\epsilon = 0.1$, demonstrating that the algorithm achieves high accuracy even on diverse network structures.

\section{Conclusions}
In this paper, we addressed the problem of fast estimation of the forest matrix of a signed graph.  We first  introduced the signed  forest matrix  theorem, which provides crucial insights into the properties of the forest matrix. Then we  proposed  a novel algorithm  $\textsc{GSCF}$  for generating generalized spanning converging forests, serving as the cornerstone for subsequent algorithms.  Furthermore we developed two efficient sampling algorithms, $\textsc{FMDE}$ and $\textsc{FMDE+}$, designed to estimate the diagonal of the forest matrix. $\textsc{FMDE+}$, in particular, incorporates more comprehensive information, resulting in superior performance both theoretically and experimentally. We also proposed an algorithm \textsc{FJOE} to estimate the expressed opinion of individuals in the signed FJ model.
Finally, we conducted   extensive experiments   on various signed graphs, which demonstrated that our algorithms are not only effective and efficient but also scalable to massive networks   with more than twenty million nodes. 

In future work, we aim to extend our algorithms to address additional challenges on signed graphs, including optimization problems related to the forest matrix and graph embedding tasks for signed networks. These extensions will further enhance the utility of our framework for understanding and modeling complex signed interactions in large-scale social and information networks.



\section*{Acknowledgements}
The work was supported by the National Natural Science Foundation of China (Nos. 62372112 and 61872093).


\section*{Impact Statement}

This paper advances the efficient analysis of signed graphs and signed network models. The proposed methods provide scalable tools for estimating forest matrix quantities and studying opinion dynamics in networks with positive and negative relationships. We do not identify specific ethical or societal risks beyond those generally associated with machine learning, network analysis, and computational social science.




\iffalse

\section{Electronic }

Submission to ICML 2026 will be entirely electronic, via a web site
(not email). Information about the submission process and \LaTeX\ templates
are available on the conference web site at:
\begin{center}
  \texttt{http://icml.cc/}
\end{center}

The guidelines below will be enforced for initial submissions and
camera-ready copies. Here is a brief summary:
\begin{itemize}
  \item Submissions must be in PDF\@.
  \item If your paper has appendices, submit the appendix together with the
        main body and the references \textbf{as a single file}. Reviewers will not
        look for appendices as a separate PDF file. So if you submit such an extra
        file, reviewers will very likely miss it.
  \item Page limit: The main body of the paper has to be fitted to 8 pages,
        excluding references and appendices; the space for the latter two is not
        limited in pages, but the total file size may not exceed 10MB. For the
        final version of the paper, authors can add one extra page to the main
        body.
  \item \textbf{Do not include author information or acknowledgements} in your
        initial submission.
  \item Your paper should be in \textbf{10 point Times font}.
  \item Make sure your PDF file only uses Type-1 fonts.
  \item Place figure captions \emph{under} the figure (and omit titles from
        inside the graphic file itself). Place table captions \emph{over} the
        table.
  \item References must include page numbers whenever possible and be as
        complete as possible. Place multiple citations in chronological order.
  \item Do not alter the style template; in particular, do not compress the
        paper format by reducing the vertical spaces.
  \item Keep your abstract brief and self-contained, one paragraph and roughly
        4--6 sentences. Gross violations will require correction at the
        camera-ready phase. The title should have content words capitalized.
\end{itemize}

\subsection{Submitting Papers}

\textbf{Anonymous Submission:} ICML uses double-blind review: no identifying
author information may appear on the title page or in the paper
itself. \cref{author info} gives further details.

\medskip

Authors must provide their manuscripts in \textbf{PDF} format.
Furthermore, please make sure that files contain only embedded Type-1 fonts
(e.g.,~using the program \texttt{pdffonts} in linux or using
File/DocumentProperties/Fonts in Acrobat). Other fonts (like Type-3)
might come from graphics files imported into the document.

Authors using \textbf{Word} must convert their document to PDF\@. Most
of the latest versions of Word have the facility to do this
automatically. Submissions will not be accepted in Word format or any
format other than PDF\@. Really. We're not joking. Don't send Word.

Those who use \textbf{\LaTeX} should avoid including Type-3 fonts.
Those using \texttt{latex} and \texttt{dvips} may need the following
two commands:

{\footnotesize
\begin{verbatim}
dvips -Ppdf -tletter -G0 -o paper.ps paper.dvi
ps2pdf paper.ps
\end{verbatim}}
It is a zero following the ``-G'', which tells dvips to use
the config.pdf file. Newer \TeX\ distributions don't always need this
option.

Using \texttt{pdflatex} rather than \texttt{latex}, often gives better
results. This program avoids the Type-3 font problem, and supports more
advanced features in the \texttt{microtype} package.

\textbf{Graphics files} should be a reasonable size, and included from
an appropriate format. Use vector formats (.eps/.pdf) for plots,
lossless bitmap formats (.png) for raster graphics with sharp lines, and
jpeg for photo-like images.

The style file uses the \texttt{hyperref} package to make clickable
links in documents. If this causes problems for you, add
\texttt{nohyperref} as one of the options to the \texttt{icml2026}
usepackage statement.

\subsection{Submitting Final Camera-Ready Copy}

The final versions of papers accepted for publication should follow the
same format and naming convention as initial submissions, except that
author information (names and affiliations) should be given. See
\cref{final author} for formatting instructions.

The footnote, ``Preliminary work. Under review by the International
Conference on Machine Learning (ICML). Do not distribute.'' must be
modified to ``\textit{Proceedings of the
  $\mathit{43}^{rd}$ International Conference on Machine Learning},
Seoul, South Korea, PMLR 306, 2026.
Copyright 2026 by the author(s).''

For those using the \textbf{\LaTeX} style file, this change (and others) is
handled automatically by simply changing
$\mathtt{\backslash usepackage\{icml2026\}}$ to
$$\mathtt{\backslash usepackage[accepted]\{icml2026\}}$$
Authors using \textbf{Word} must edit the
footnote on the first page of the document themselves.

Camera-ready copies should have the title of the paper as running head
on each page except the first one. The running title consists of a
single line centered above a horizontal rule which is $1$~point thick.
The running head should be centered, bold and in $9$~point type. The
rule should be $10$~points above the main text. For those using the
\textbf{\LaTeX} style file, the original title is automatically set as running
head using the \texttt{fancyhdr} package which is included in the ICML
2026 style file package. In case that the original title exceeds the
size restrictions, a shorter form can be supplied by using

\verb|\icmltitlerunning{...}|

just before $\mathtt{\backslash begin\{document\}}$.
Authors using \textbf{Word} must edit the header of the document themselves.

\section{Format of the Paper}

All submissions must follow the specified format.

\subsection{Dimensions}

The text of the paper should be formatted in two columns, with an
overall width of 6.75~inches, height of 9.0~inches, and 0.25~inches
between the columns. The left margin should be 0.75~inches and the top
margin 1.0~inch (2.54~cm). The right and bottom margins will depend on
whether you print on US letter or A4 paper, but all final versions
must be produced for US letter size.
Do not write anything on the margins.

The paper body should be set in 10~point type with a vertical spacing
of 11~points. Please use Times typeface throughout the text.

\subsection{Title}

The paper title should be set in 14~point bold type and centered
between two horizontal rules that are 1~point thick, with 1.0~inch
between the top rule and the top edge of the page. Capitalize the
first letter of content words and put the rest of the title in lower
case.
You can use TeX math in the title (we suggest sparingly),
but no custom macros, images, or other TeX commands.
Please make sure that accents, special characters, etc., are entered using
TeX commands and not using non-English characters.

\subsection{Author Information for Submission}
\label{author info}

ICML uses double-blind review, so author information must not appear. If
you are using \LaTeX\/ and the \texttt{icml2026.sty} file, use
\verb+\icmlauthor{...}+ to specify authors and \verb+\icmlaffiliation{...}+
to specify affiliations. (Read the TeX code used to produce this document for
an example usage.) The author information will not be printed unless
\texttt{accepted} is passed as an argument to the style file. Submissions that
include the author information will not be reviewed.

\subsubsection{Self-Citations}

If you are citing published papers for which you are an author, refer
to yourself in the third person. In particular, do not use phrases
that reveal your identity (e.g., ``in previous work \cite{langley00}, we
have shown \ldots'').

Do not anonymize citations in the reference section. The only exception are manuscripts that are
not yet published (e.g., under submission). If you choose to refer to
such unpublished manuscripts \cite{anonymous}, anonymized copies have
to be submitted
as Supplementary Material via OpenReview\@. However, keep in mind that an ICML
paper should be self contained and should contain sufficient detail
for the reviewers to evaluate the work. In particular, reviewers are
not required to look at the Supplementary Material when writing their
review (they are not required to look at more than the first $8$ pages of the submitted document).

\subsubsection{Camera-Ready Author Information}
\label{final author}

If a paper is accepted, a final camera-ready copy must be prepared.
%
For camera-ready papers, author information should start 0.3~inches below the
bottom rule surrounding the title. The authors' names should appear in 10~point
bold type, in a row, separated by white space, and centered. Author names should
not be broken across lines. Unbolded superscripted numbers, starting 1, should
be used to refer to affiliations.

Affiliations should be numbered in the order of appearance. A single footnote
block of text should be used to list all the affiliations. (Academic
affiliations should list Department, University, City, State/Region, Country.
Similarly for industrial affiliations.)

Each distinct affiliations should be listed once. If an author has multiple
affiliations, multiple superscripts should be placed after the name, separated
by thin spaces. If the authors would like to highlight equal contribution by
multiple first authors, those authors should have an asterisk placed after their
name in superscript, and the term ``\textsuperscript{*}Equal contribution"
should be placed in the footnote block ahead of the list of affiliations. A
list of corresponding authors and their emails (in the format Full Name
\textless{}email@domain.com\textgreater{}) can follow the list of affiliations.
Ideally only one or two names should be listed.

A sample file with author names is included in the ICML2026 style file
package. Turn on the \texttt{[accepted]} option to the stylefile to
see the names rendered. All of the guidelines above are implemented
by the \LaTeX\ style file.

\subsection{Abstract}

The paper abstract should begin in the left column, 0.4~inches below the final
address. The heading `Abstract' should be centered, bold, and in 11~point type.
The abstract body should use 10~point type, with a vertical spacing of
11~points, and should be indented 0.25~inches more than normal on left-hand and
right-hand margins. Insert 0.4~inches of blank space after the body. Keep your
abstract brief and self-contained, limiting it to one paragraph and roughly 4--6
sentences. Gross violations will require correction at the camera-ready phase.

\subsection{Partitioning the Text}

You should organize your paper into sections and paragraphs to help readers
place a structure on the material and understand its contributions.

\subsubsection{Sections and Subsections}

Section headings should be numbered, flush left, and set in 11~pt bold type
with the content words capitalized. Leave 0.25~inches of space before the
heading and 0.15~inches after the heading.

Similarly, subsection headings should be numbered, flush left, and set in 10~pt
bold type with the content words capitalized. Leave
0.2~inches of space before the heading and 0.13~inches afterward.

Finally, subsubsection headings should be numbered, flush left, and set in
10~pt small caps with the content words capitalized. Leave
0.18~inches of space before the heading and 0.1~inches after the heading.

Please use no more than three levels of headings.

\subsubsection{Paragraphs and Footnotes}

Within each section or subsection, you should further partition the paper into
paragraphs. Do not indent the first line of a given paragraph, but insert a
blank line between succeeding ones.

You can use footnotes\footnote{Footnotes should be complete sentences.}
to provide readers with additional information about a topic without
interrupting the flow of the paper. Indicate footnotes with a number in the
text where the point is most relevant. Place the footnote in 9~point type at
the bottom of the column in which it appears. Precede the first footnote in a
column with a horizontal rule of 0.8~inches.\footnote{Multiple footnotes can
  appear in each column, in the same order as they appear in the text,
  but spread them across columns and pages if possible.}

\begin{figure}[ht]
  \vskip 0.2in
  \begin{center}
    \centerline{\includegraphics[width=\columnwidth]{icml_numpapers}}
    \caption{
      Historical locations and number of accepted papers for International
      Machine Learning Conferences (ICML 1993 -- ICML 2008) and International
      Workshops on Machine Learning (ML 1988 -- ML 1992). At the time this
      figure was produced, the number of accepted papers for ICML 2008 was
      unknown and instead estimated.
    }
    \label{icml-historical}
  \end{center}
\end{figure}

\subsection{Figures}

You may want to include figures in the paper to illustrate your approach and
results. Such artwork should be centered, legible, and separated from the text.
Lines should be dark and at least 0.5~points thick for purposes of
reproduction, and text should not appear on a gray background.

Label all distinct components of each figure. If the figure takes the form of a
graph, then give a name for each axis and include a legend that briefly
describes each curve. Do not include a title inside the figure; instead, the
caption should serve this function.

Number figures sequentially, placing the figure number and caption \emph{after}
the graphics, with at least 0.1~inches of space before the caption and
0.1~inches after it, as in \cref{icml-historical}. The figure caption should be
set in 9~point type and centered unless it runs two or more lines, in which
case it should be flush left. You may float figures to the top or bottom of a
column, and you may set wide figures across both columns (use the environment
\texttt{figure*} in \LaTeX). Always place two-column figures at the top or
bottom of the page.

\subsection{Algorithms}

If you are using \LaTeX, please use the ``algorithm'' and ``algorithmic''
environments to format pseudocode. These require the corresponding stylefiles,
algorithm.sty and algorithmic.sty, which are supplied with this package.
\cref{alg:example} shows an example.

\begin{algorithm}[tb]
  \caption{Bubble Sort}
  \label{alg:example}
  \begin{algorithmic}
    \STATE {\bfseries Input:} data $x_i$, size $m$
    \REPEAT
    \STATE Initialize $noChange = true$.
    \FOR{$i=1$ {\bfseries to} $m-1$}
    \IF{$x_i > x_{i+1}$}
    \STATE Swap $x_i$ and $x_{i+1}$
    \STATE $noChange = false$
    \ENDIF
    \ENDFOR
    \UNTIL{$noChange$ is $true$}
  \end{algorithmic}
\end{algorithm}


\subsection{Tables}

You may also want to include tables that summarize material. Like figures,
these should be centered, legible, and numbered consecutively. However, place
the title \emph{above} the table with at least 0.1~inches of space before the
title and the same after it, as in \cref{sample-table}. The table title should
be set in 9~point type and centered unless it runs two or more lines, in which
case it should be flush left.

% Note use of \abovespace and \belowspace to get reasonable spacing
% above and below tabular lines.

\begin{table}[t]
  \caption{Classification accuracies for naive Bayes and flexible
    Bayes on various data sets.}
  \label{sample-table}
  \begin{center}
    \begin{small}
      \begin{sc}
        \begin{tabular}{lcccr}
          \toprule
          Data set  & Naive         & Flexible      & Better?  \\
          \midrule
          Breast    & 95.9$\pm$ 0.2 & 96.7$\pm$ 0.2 & $\surd$  \\
          Cleveland & 83.3$\pm$ 0.6 & 80.0$\pm$ 0.6 & $\times$ \\
          Glass2    & 61.9$\pm$ 1.4 & 83.8$\pm$ 0.7 & $\surd$  \\
          Credit    & 74.8$\pm$ 0.5 & 78.3$\pm$ 0.6 &          \\
          Horse     & 73.3$\pm$ 0.9 & 69.7$\pm$ 1.0 & $\times$ \\
          Meta      & 67.1$\pm$ 0.6 & 76.5$\pm$ 0.5 & $\surd$  \\
          Pima      & 75.1$\pm$ 0.6 & 73.9$\pm$ 0.5 &          \\
          Vehicle   & 44.9$\pm$ 0.6 & 61.5$\pm$ 0.4 & $\surd$  \\
          \bottomrule
        \end{tabular}
      \end{sc}
    \end{small}
  \end{center}
  \vskip -0.1in
\end{table}

Tables contain textual material, whereas figures contain graphical material.
Specify the contents of each row and column in the table's topmost row. Again,
you may float tables to a column's top or bottom, and set wide tables across
both columns. Place two-column tables at the top or bottom of the page.

\subsection{Theorems and Such}
The preferred way is to number definitions, propositions, lemmas, etc.
consecutively, within sections, as shown below.
\begin{definition}
  \label{def:inj}
  A function $f:X \to Y$ is injective if for any $x,y\in X$ different, $f(x)\ne
    f(y)$.
\end{definition}
Using \cref{def:inj} we immediate get the following result:
\begin{proposition}
  If $f$ is injective mapping a set $X$ to another set $Y$,
  the cardinality of $Y$ is at least as large as that of $X$
\end{proposition}
\begin{proof}
  Left as an exercise to the reader.
\end{proof}
\cref{lem:usefullemma} stated next will prove to be useful.
\begin{lemma}
  \label{lem:usefullemma}
  For any $f:X \to Y$ and $g:Y\to Z$ injective functions, $f \circ g$ is
  injective.
\end{lemma}
\begin{theorem}
  \label{thm:bigtheorem}
  If $f:X\to Y$ is bijective, the cardinality of $X$ and $Y$ are the same.
\end{theorem}
An easy corollary of \cref{thm:bigtheorem} is the following:
\begin{corollary}
  If $f:X\to Y$ is bijective,
  the cardinality of $X$ is at least as large as that of $Y$.
\end{corollary}
\begin{assumption}
  The set $X$ is finite.
  \label{ass:xfinite}
\end{assumption}
\begin{remark}
  According to some, it is only the finite case (cf. \cref{ass:xfinite}) that
  is interesting.
\end{remark}
%restatable

\subsection{Citations and References}

Please use APA reference format regardless of your formatter or word processor.
If you rely on the \LaTeX\/ bibliographic facility, use \texttt{natbib.sty} and
\texttt{icml2026.bst} included in the style-file package to obtain this format.

Citations within the text should include the authors' last names and year. If
the authors' names are included in the sentence, place only the year in
parentheses, for example when referencing Arthur Samuel's pioneering work
\yrcite{Samuel59}. Otherwise place the entire reference in parentheses with the
authors and year separated by a comma \cite{Samuel59}. List multiple references
separated by semicolons \cite{kearns89,Samuel59,mitchell80}. Use the `et~al.'
construct only for citations with three or more authors or after listing all
authors to a publication in an earlier reference \cite{MachineLearningI}.

Authors should cite their own work in the third person in the initial version
of their paper submitted for blind review. Please refer to \cref{author info}
for detailed instructions on how to cite your own papers.

Use an unnumbered first-level section heading for the references, and use a
hanging indent style, with the first line of the reference flush against the
left margin and subsequent lines indented by 10 points. The references at the
end of this document give examples for journal articles \cite{Samuel59},
conference publications \cite{langley00}, book chapters \cite{Newell81}, books
\cite{DudaHart2nd}, edited volumes \cite{MachineLearningI}, technical reports
\cite{mitchell80}, and dissertations \cite{kearns89}.

Alphabetize references by the surnames of the first authors, with single author
entries preceding multiple author entries. Order references for the same
authors by year of publication, with the earliest first. Make sure that each
reference includes all relevant information (e.g., page numbers).

Please put some effort into making references complete, presentable, and
consistent, e.g. use the actual current name of authors. If using bibtex,
please protect capital letters of names and abbreviations in titles, for
example, use \{B\}ayesian or \{L\}ipschitz in your .bib file.

\section*{Accessibility}

Authors are kindly asked to make their submissions as accessible as possible
for everyone including people with disabilities and sensory or neurological
differences. Tips of how to achieve this and what to pay attention to will be
provided on the conference website \url{http://icml.cc/}.

\section*{Software and Data}

If a paper is accepted, we strongly encourage the publication of software and
data with the camera-ready version of the paper whenever appropriate. This can
be done by including a URL in the camera-ready copy. However, \textbf{do not}
include URLs that reveal your institution or identity in your submission for
review. Instead, provide an anonymous URL or upload the material as
``Supplementary Material'' into the OpenReview reviewing system. Note that
reviewers are not required to look at this material when writing their review.

% Acknowledgements should only appear in the accepted version.
\section*{Acknowledgements}

\textbf{Do not} include acknowledgements in the initial version of the paper
submitted for blind review.

If a paper is accepted, the final camera-ready version can (and usually should)
include acknowledgements.  Such acknowledgements should be placed at the end of
the section, in an unnumbered section that does not count towards the paper
page limit. Typically, this will include thanks to reviewers who gave useful
comments, to colleagues who contributed to the ideas, and to funding agencies
and corporate sponsors that provided financial support.

\section*{Impact Statement}

Authors are \textbf{required} to include a statement of the potential broader
impact of their work, including its ethical aspects and future societal
consequences. This statement should be in an unnumbered section at the end of
the paper (co-located with Acknowledgements -- the two may appear in either
order, but both must be before References), and does not count toward the paper
page limit. In many cases, where the ethical impacts and expected societal
implications are those that are well established when advancing the field of
Machine Learning, substantial discussion is not required, and a simple
statement such as the following will suffice:

``This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.''

The above statement can be used verbatim in such cases, but we encourage
authors to think about whether there is content which does warrant further
discussion, as this statement will be apparent if the paper is later flagged
for ethics review.

% In the unusual situation where you want a paper to appear in the
% references without citing it in the main text, use \nocite
\nocite{langley00}



\fi


\bibliography{signFJ,kedges,newref,expressedopinion}
\bibliographystyle{icml2026}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\appendix
\onecolumn





\section{Proofs}
In this section, we provide proofs of selected lemmas and theorems.

 


\subsection{Proof of Lemma~\ref{th-wF}}
\begin{proof}
    We define the function $\pi : V \mapsto V$ as a permutation of the node set $V=\{1,\ldots,n\}$, and use $\mathcal{P}(V)$ to denote the set of all permutations of set $V$.  We use $N(\pi)$ to denote the inversion number of $\pi$, that is $N(\pi) = |\{(i,j): i< j, \pi(i) > \pi(j)\}|$. Each permutation $\pi$ can be decomposed into disjoint cycles $C_1,C_2\ldots,C_{n(\pi)}$, where $n(\pi)$ represents the number of cycles in the decomposition. Let $n^-(\pi)$ and $n^+(\pi)$ denote the number of non-trivial negative and positive cycles in $\pi$, respectively.

    From the definition of determinant, we obtain that 
        \begin{equation}\label{th1-eq2}
 \det(\II+\LL) = \sum_{\pi\in\mathcal{P}(V)} (-1)^{N(\pi)}\prod_{i\in V, \pi(i)=j}\ee_{i}^{\top}(\II+\LL)\ee_{j}. 
    \end{equation}
 For a cycle $C_i$ belonging to $\pi$, its inversion number is ${|C_i|-1}$. Then we have $ (-1)^{N(\pi)} = \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1} $. Rewriting the determinant we obtain:
        \begin{equation}
 = \sum_{\pi\in\mathcal{P}(V)} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}\prod_{i: \pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i: \pi(i)=j,i\neq j}(-w_{ij}).
    \end{equation}
We simplify the product terms further:
\begin{equation}
\begin{aligned}
&= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^-(\pi)+n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}w_{ij}\\
        &= \sum_{\pi\in\mathcal{P}(V)}(-1)^{n^+(\pi)}\prod_{i:\pi(i)=i}(1+ \sum_{j\neq i}\abs{w_{ij}})\prod_{i:\pi(i)=j,i\neq j}\abs{w_{ij}}\\ 
\end{aligned}
\end{equation}
For a permutation $\pi$, let $P(\pi) = \{i\in V:\pi(i) = i\} $ be the  set of fixed points. We now define a set of mappings $\mathcal{M}(\pi)$. For a mapping $\widehat{\pi}\in \mathcal{M}(\pi), \widehat{\pi}: V\mapsto V$, it satisfies 
    \begin{equation}\label{eq3}
         \widehat{\pi}(i)= \left\{\begin{matrix}
j   & i\in P(\pi), j \in \{i\}\cup N_i,\\
\pi(i)  & i\notin P(\pi).
\end{matrix}\right.
    \end{equation} 
For each permutation $\pi \in \mathcal{P}(V)$ and corresponding mapping $\widehat{\pi} \in \mathcal{M}(\pi)$, we define an induced spanning subgraph $\widehat{\calG}(\widehat{\pi}) = (V, E(\widehat{\pi}), w)$, where $E(\widehat{\pi}) = {(i, j) : \widehat{\pi}(i) = j, i \neq j, i \in V}$. We can then express the determinant as follows:
\begin{equation}
\begin{aligned}
        \det(\II+\LL) &=  \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}\prod_{i:\widehat{\pi}(i)=j,i\neq j} \abs{w_{ij}}\\& = \sum_{\pi\in\mathcal{P}(V)}\sum_{\widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}  .
\end{aligned}
\end{equation}
We then rearrange the sum order of $\pi$ and $\widehat{\pi}$:
\begin{equation}
=\sum_{\widehat{\pi}} \sum_{\pi: \widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)}. 
\end{equation}

For any non-trivial cycle in $\widehat{\calG}(\widehat{\pi})$, it either  belongs to the decomposition of $\pi$ or not. Let $n^+(\widehat{\pi})$ and $n^-(\widehat{\pi})$ denote the number of non-trivial positive and negative cycles in $\widehat{\calG}(\widehat{\pi})$, respectively. Summing over the non-trivial positive and negative cycles in the decompositions, we find
\begin{equation}\label{eq4}
\begin{aligned}
       &\sum_{\pi: \widehat{\pi}\in \mathcal{M}(\pi)}(-1)^{n^+(\pi)} = \sum_{i=0}^{n^+(\widehat{\pi})}\binom{n^+(\widehat{\pi})}{i}(-1)^{i}\sum_{j=0}^{n^-(\widehat{\pi})}\binom{n^-(\widehat{\pi})}{j} 
\\&=  (1-1)^{n^+(\widehat{\pi})}(1+1)^{n^-(\widehat{\pi})}=\left\{\begin{matrix}
 0 & n^+(\widehat{\pi})\neq 0, \\
 2^{n^-(\widehat{\pi})} &n^+(\widehat{\pi})=0 .
\end{matrix}\right.
\end{aligned}
\end{equation}
This implies that for a fixed $\widehat{\pi}$,the expression $\sum_{\pi : \widehat{\pi} \in \mathcal{M}(\pi)} (-1)^{n^+(\pi)}$ equals $2^{n^-(\widehat{\pi})}$ if and only if $n^+(\widehat{\pi}) = 0$. In this scenario, the induced graph $\widehat{\calG}(\widehat{\pi})$ corresponds to the generalized spanning converging forest previously defined. Hence, we conclude

\begin{equation}
        \det(\II+\LL)    =\sum_{\widehat{\pi}:n^+(\widehat{\pi})=0 }   2^{n^-(\widehat{\pi})} = \sum_{\phi\in \calF} w(\phi) = w(\calF),
\end{equation}
which finishes the proof.\end{proof}



\subsection{Proof of Lemma~\ref{th-wFij}}


\begin{proof}
Similarly to the proof of Lemma~\ref{th-wF}, we now define the function $\pi$ as a  bijection from the node set $V\setminus\{j\}$ to the node set $V\setminus\{i\}$.  We use $N(\pi)$ to denote the inversion number of $\pi$. Notice that the permutation $\pi$ can be  decomposed into a path $P_{ij}$ from node $i$ to node $j$ and disjoint cycles $C_1,C_2\ldots, C_{n(\pi)}$, where $n(\pi)$ denotes the number of cycles in the decomposition. Let $n(P_{ij})$ be the number of nodes in $P_{ij}$. Let $n^-(\pi)$ and $n^+(\pi)$ be the number of non-trivial negative and positive cycles of $\pi$ respectively. We use ${\rm sign}(P_{ij})$ to denote the sign of the product of the arcs in the path $P_{ij}$. Then we obtain  that,
    \begin{equation}
        \prod_{i:\pi(i)=j,i\neq j}w_{ij} =  {\rm sign}(P_{ij})(-1)^{n^-(\pi)}\prod_{i:\pi(i)=j,i\neq j}\abs{w_{ij}}.
    \end{equation}
To obtain the  inversion number of $\pi$, we first define a mapping $\pi'$ mapping   node $j$ to node $i$. Then the mapping $\pi\oplus\pi'$ is a permutation of set $V$. Thus one obtains that
   \begin{equation}
       (-1)^{N(\pi\oplus\pi')} =(-1)^{n(P_{ij})} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}.
   \end{equation}
Since the change of inversion number after adding $\pi'$ has the same parity as $i+j-1$, one has
   \begin{equation}
       (-1)^{N(\pi)} =(-1)^{i+j}(-1)^{n(P_{ij})-1} \prod_{k = 1}^{n(\pi)}(-1)^{|C_k|-1}.
   \end{equation}
Following   similar steps in the proof of Lemma~\ref{th-wF}, one gets that
\begin{equation}
     \det(\II+\LL)_{-j,-i} = (-1)^{i+j}\sum_{\phi\in\calF_{ij}}{\rm sign}(P_{ij})w(\phi) = (-1)^{i+j}w(\calF_{ij}),
\end{equation}
which completes the proof.
\end{proof}



% \subsection{Proof of Theorem~\ref{th-qij}}

% \begin{proof}
% According to Lemma~\ref{th-wF} and Lemma~\ref{th-wFij}, one obtains that
% \begin{equation}
%     q_{ij} = \frac{(-1)^{i+j}\det(\II+\LL)_{-j,-i}}{\det(\II+\LL)} = \frac{w(\calF_{ij})}{w(\calF)},
% \end{equation}
% which finishes the proof.
% \end{proof}



\subsection{Proof of Lemma~\ref{le-pro}}

\begin{proof}
According to Theorem~\ref{th-qij}, it is straightforward to derive that for any distinct nodes $i, j \in V$, the inequality $0 \leq |q_{ij}| \leq q_{jj} \leq 1$ holds. In scenarios where $\calG = (V, E, w)$ constitutes a balanced signed graph, the graph contains no non-trivial negative cycles. Under such circumstances, the path sign between any pair of nodes $i, j \in V$ is uniformly positive or negative, leading to the equation $\sum_{j=1}^n |q_{ij}| = \frac{\sum_{j=1}^n |w(\calF_{ij})|}{w(\calF)} = 1$. Moreover, leveraging the relation $\QQ(\II+\LL) = \II$, we  obtain that for any node $i\in V$, $1 = (1+d_i)q_{ii} - \sum_{k\neq i} q_{ik}w_{ki}$. That is, $q_{ii } = \frac{1}{1+d_i}(1+\sum_{k\neq i}q_{ik}w_{ki}) \leq \frac{1}{1+d_i}(1+\sum_{k\neq i}|q_{ik}|) =  \frac{1}{1+d_i}(1+q_{ii})$, which can be simplified to $q_{ii}\leq \frac{2}{2+d_i}$. Moreover,  in this case, $q_{ik}w_{ki}$ must be non-negative, leading to the fact that $q_{ii}\geq \frac{1}{1+d_i}$, which finishes the proof. 
\end{proof}

\subsection{Proof of Theorem~\ref{th-qij}}

% \begin{theorem}[Signed Forest Matrix Theorem]\label{th-qij}
% For a directed signed graph $\calG=(V, E,w)$, the entry of the forest matrix $\QQ = (\II+\LL)^{-1} = (q_{ij})_{n\times n} $  is related to the generalized spanning converging forests as follows:
% \begin{equation}
% 		q_{ij} = \frac{w(\calF_{ij})}{w(\calF)}.
% \end{equation}
% \end{theorem} 





\begin{proof}
According to Lemma~\ref{th-wF} and Lemma~\ref{th-wFij}, we obtain  that
\begin{equation}
    q_{ij} = \frac{(-1)^{i+j}\det(\II+\LL)_{-j,-i}}{\det(\II+\LL)} = \frac{w(\calF_{ij})}{w(\calF)},
\end{equation}
which finishes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{le-indpdt}}


\begin{proof}

We first introduce some notations. For a signed graph $\mathcal{G} = (V,E,w)$ and a node $i\in V$, we define $t_i$ as a random variable that takes values from the set $\{-1\}\cup N(i)$, where the probability of $t_i = -1$ is $\frac{1}{1+d_i}$, and the probability of $t_i = u$ for any node $u\in N(i)$ is also $\frac{1}{1+d_i}$.  Then we define a matrix $\TT^L = (t^L_{ij})_{n\times L}$.  The entry $t^L_{ij}$ in row $i$ and column $j$ of the matrix $\TT^L$ is a random variable that is independently and identically distributed with $t_i$.

We can utilize the matrix $\TT^L$ to determine the next node to visit during the random walk process in Algorithm~\ref{alg-grf}. To be more specific, we begin by defining a vector $\hh = (h_i)_{n\times 1}$, where $h_i$ is initialized to $1$ at the start of our algorithm. During the random walk process, suppose the walk is currently at node $i$, and we need to select the next target node. We set $j=h_i$, and then look at the $j$-th column of the matrix $\TT^L$ corresponding to node $i$. The entry $t^L_{ij}$ in this column represents the next node to visit. If $t_{ij}^L=-1$, we designate node $i$ as the new root node. Otherwise, if $t_{ij}^L=u$, where $u$ is a node adjacent to $i$, we proceed to node $u$ for the next step of the walk. After selecting the next target node, we update $h_i$ to $h_i + 1$. When Algorithm~\ref{alg-grf} terminates, we obtain a vector $\hh$. We can measure the time complexity of Algorithm~\ref{alg-grf} by computing the $\ell_1$-norm of $\hh$, denoted by $\norm{\hh}_1$, which is simply the sum of all elements in $\hh$, i.e., $\sum_{i=1}^n h_i$.



In Algorithm~\ref{alg-grf}, we perform the loop-erasure operation if a non-trivial positive cycle exists. A cycle with the same nodes may be traversed several times during the algorithm so that it may be erased many times. However, since we use matrix $\TT^L$ to determine the next node to visit, every entry in matrix $\TT^L$ can only form one positive cycle and be erased once.

To denote the cycle $C$ and its position in matrix $\TT^L$, we use the $n$-dimensional vector $\cc = (c_1,\cdots,c_n)^\top$. For any $i\in V$, we have $c_i\in \{0,1,\cdots,L\}$. If $c_i\neq 0$, it means that node $i$ is in the cycle and vice versa. To be more specific, $C$ is composed of edges $(i,t^L_{ic_i})$ for any node $i$ that satisfies $c_i\neq 0$. That is, $C = \bigcup_{i:c_i\neq 0} (i,t^L_{ic_i})$. 




    Consider two different permutations of the node set $V$, denoted as $\pi_1$ and $\pi_2$. Given a fixed matrix $\TT^L$ with sufficiently large $L$, we apply Algorithm~\ref{alg-grf} twice using $\TT^L$ to determine the next node to visit. In line 4, we choose the new node based on the order of $\pi_1$ and $\pi_2$, respectively. Once Algorithm~\ref{alg-grf} terminates, we obtain two vectors $\hh$ and $\widehat{\hh}$. We claim that $\hh = \widehat{\hh}$.


Suppose that we erase non-trivial positive cycles  $C^1,\cdots,C^{k}$ in order when we choose the new node based on the order of $\pi_1$.  If $k = 0$, then there is no need for erasing cycles, and in this case  $\hh = \widehat{\hh}$. Now we consider $k>0$, that is, there is at least one positive cycle  to be erased.    For $i = 1,\cdots,k$, we use $\cc^i = (c^i_1,\cdots,c^i_n)^\top$ to denote the  position of cycle $C^i$ in matrix $\TT$. Then for $i\in\{1,\cdots,k-1\}$ and $j\in V$, we have 
\begin{equation}
c^{i+1}_j =\left\{\begin{matrix}
 0 & \text{ if } j\notin C^{i+1}, \\
 \max\{c^{1}_{j},\cdots,c^{i}_{j}\}+1 & \text{ if } j\in C^{i+1}.
\end{matrix}\right.    
\end{equation}
Moreover, for $i\in V$, we have that $h_i = \max\{c^{1}_{i},\cdots,c^{k}_{i}\}+1$.

Now, suppose we choose the new node based on the order of $\pi_2$, and the first non-trivial positive cycle to be erased is $\widehat{C}^1$. Let $\widehat{\cc}^1 = (\widehat{c}^1_1,\cdots,\widehat{c}^1_n)^\top$ denote the position of $\widehat{C}^1$ in matrix $\TT^L$. For $i\in V$, either $\widehat{c}^1_i = 0$ and node $i$ is not in cycle $\widehat{C}^1$, or $\widehat{c}^1_i = 1$ and node $i$ belongs to cycle $\widehat{C}^1$. Since $\widehat{C}^1$ is a non-trivial positive cycle, there exists $i\in \widehat{C}^1$ such that $h_i > 1$. This implies that $\widehat{C}^1$ must have some common nodes with cycles $C^1, \cdots, C^k$ that have the same position in matrix $T$. Suppose $C^i$ is the first cycle that has some common nodes with $\widehat{C}^1$. If $\widehat{\cc}^1 \neq \cc^i$, then there is a common node $j\in \widehat{C}^1 \cap C^i$ such that $\widehat{c}^1_j = 1 \neq c^i_j$. This implies that $c^i_j > 1$, which contradicts the fact that $C^i$ is the first cycle having some common nodes with $\widehat{C}^1$. Therefore, $\widehat{C}$ and $C^i$ must be the same cycle, and $\widehat{\cc}^1 = \cc^i$. In other words, $\widehat{C}^1\in{C^1,\cdots,C^k}$.


Suppose we have erased non-trivial positive cycles $\widehat{C}^1, \ldots, \widehat{C}^u$ based on the order of $\pi_2$, and for $i=1,\ldots,u$, we have $\widehat{C}^i \in {C^1,\ldots,C^k}$. If $u<k$, then the algorithm will not terminate and the next positive cycle to be erased is $\widehat{C}^{u+1}$. Following the previous proof, we can show that $\widehat{C}^{u+1} \in {C^1,\ldots,C^k}$. If $u=k$, then the algorithm terminates. Therefore, if we choose new nodes based on the order of $\pi_2$, only the order of positive loop-erasure will be changed, and we will still have $\hh = \widehat{\hh}$.

As a result, given a fixed matrix $\TT^L$ with sufficiently large $L$, the random walk order will not affect the time complexity or the return result of Algorithm~\ref{alg-grf}. Thus, if we randomly generate $T$, the expected time complexity of Algorithm~\ref{alg-grf} is independent of the random walk order.
\end{proof}

\subsection{Proof of Theorem~\ref{th-Own}}

  

\begin{proof}
The expected time complexity of Algorithm~\ref{alg-grf} can be expressed as the expected value of the $\ell_1$-norm of $\hh$ when performing Algorithm~\ref{alg-grf} over all possible matrices $\TT^L$. This can be written as $\mathbb{E}\left(\sum_{i=1}^n h_i\right) = \sum_{i=1}^n \mathbb{E}(h_i)$, where the equality follows from the linearity of the expectation. As shown in the proof of Lemma~\ref{le-indpdt}, the expected value of $h_i$, denoted by $\mathbb{E}(h_i)$, is independent of the order in which the random walk starts at each node.






Suppose that  the random walk starts at node $v_1$. We can estimate $\mathbb{E}( h_1)$ as the expected number of times the walk visits node $v_1$ before terminating. Recall that termination occurs either when a negative cycle is encountered or when a root node is added to the branch at a node $u$, with probability $\frac{1}{1+d_u}$. We can derive an upper bound for $\mathbb{E}( h_1)$ by considering the case where the walk only stops when a root node is added,  ignoring the possibility of stopping at negative cycles. In this case, the probability transition matrix is $\PP = (\II+\DD)^{-1}(\AA^+-\AA^-)$. The expected number of visits to node $v_1$ until termination can be calculated as $\lim_{t\rightarrow\infty}\sum_{i=1}^t \ee_1^\top(\II+\PP+\cdots+\PP^t)\ee_1$. Since the walk in Algorithm~\ref{alg-grf} also terminates when encountering negative cycles, we have the following upper bound:
\begin{equation}
\begin{aligned}
        \mathbb{E}( h_1) &\leq \lim _{t\rightarrow \infty}  \ee_{1}^\top(\II+\PP+\cdots+\PP^t)\ee_{1} \\ &= \ee_{1}^T(\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD)\ee_{1}.
\end{aligned}
\end{equation}





After summing the expected number of visits for all nodes, we obtain: $    \sum_{i=1}^n \mathbb{E}( h_i) \leq {\rm trace}((\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD)).$

Let $\widehat{\LL}$ be the matrix $\DD-\AA^++\AA^-$, which is the Laplacian matrix of an unsigned directed graph $\widehat{\calG} = (V,E,\widehat{w})$, where $\widehat{w}_{ij} = \abs{w_{ij}} = 1$. The entry at row $i$ and column $j$ of $\widehat{\LL}$ is denoted by $l_{ij}$. We have $l_{ii} = d_i$ and $l_{ij} = 0$ or $- 1$. Furthermore, the sum of all entries in each row of $\widehat{\LL}$ is equal to $0$. 


 
Matrix $\widehat{\QQ} = (\II +\widehat{\LL})^{-1} = (\widehat{q}_{ij})_{n\times n}$ is the forest matrix on unsigned graph  $\widehat{\calG}$.  From~\cite{SuZh23}, we have $\frac{1}{1+d_i}\leq \widehat{q}_{ii} \leq \frac{2}{2+d_i}$. Then we can derive the following inequality:
\begin{equation}
\begin{aligned}
          \sum_{i=1}^n \mathbb{E}( h_i) &\leq {\rm trace}((\II+\DD-\AA^++\AA^-)^{-1}(\II+\DD))\\ &= \sum_{i=1}^n \widehat{q}_{ii}(1+d_i) \leq \sum_{i=1}^n\frac{2(1+d_i)}{2+d_{i} } \leq 2n.
\end{aligned}
\end{equation}
 As a result,   the expected time complexity of algorithm \ref{alg-grf} is at most $O( n)$.
\end{proof}


\subsection{Proof of Lemma~\ref{le-uniform}}
\begin{proof}
In Algorithm~\ref{alg-grf}, suppose that the random walk is currently at node $i$, and a new step is needed. There are two possible scenarios: either node $i$ becomes a root node,  or the walk moves from node $i$ to a random neighbor $j$. Both events occur with a probability of $\frac{1}{1+d_i}$. Consequently, the probability of obtaining any particular generalized spanning converging forest $\phi_0$ from $\calF$ using Algorithm~\ref{alg-grf} is proportional to $\prod_{i=1}^n \frac{1}{1+d_i}$. Therefore, each forest $\phi_0 \in \calF$ can be generated with equal likelihood, which completes the proof.
\end{proof}

\subsection{Proof of Lemma~\ref{le-omegal}}

\begin{proof}
With Lemma~\ref{le-uniform}, we establish that for each $k = 1, \cdots, l$, the forest $\phi_k$ is uniformly sampled from $\calF$. Consequently, the expected value of the estimator $\widehat{w}_l(\calF)$ is given by:
\begin{equation}
\mathbb{E}(\widehat{w}_l({\calF} ))  =    \mathbb{E}(\frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)})  = \sum_{\phi \in \calF} 2^{n^-(\phi)} = w(\calF).
\end{equation}

Similarly, the expected value of $\widehat{w}_l(\calF_{ij})$ is calculated as follows:
\begin{equation}
\begin{aligned}
\mathbb{E}(\widehat{w}_l({\calF_{ij}} ))  &=    \mathbb{E}(\frac{|\calF|}{l} \sum_{k=1}^l 2^{n^-(\phi_k)} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}})  \\ &= \sum_{\phi \in \calF} 2^{n^-(\phi )} {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi }(i) = j \}} \\&=  \sum_{\phi \in \calF_{ij}}2^{n^-(\phi)} {\rm sign}(P_{ij})   =  w(\calF_{ij}).
\end{aligned}
\end{equation}
This computation confirms that $\widehat{w}_l(\calF)$ and $\widehat{w}_l(\calF_{ij})$ are indeed unbiased estimators for $w(\calF)$ and $w(\calF_{ij})$, respectively, which  completes the proof. \end{proof}
% \begin{proof}
% With Lemma~\ref{le-uniform}, we establish that for each $j = 1, 2, \cdots, l$,  forest $\phi_j$ is uniformly sampled from $\calF$. Consequently, the expected value of the estimator $\widehat{w}_l(\calF)$ is given by 
% \begin{equation}
% \mathbb{E}(\widehat{w}_l({\calF} ))  =    \mathbb{E}(\frac{|\calF|}{l} \sum_{j=1}^l 2^{n^-(\phi_j)})  = \sum_{\phi \in \calF} 2^{n^-(\phi)} = w(\calF).
% \end{equation}

% Similarly, the expected value of $\widehat{w}_l(\calF_{ii})$ is calculated as:
% \begin{equation}
% \begin{aligned}
% \mathbb{E}(\widehat{w}_l({\calF_{ii}} ))  &=    \mathbb{E}(\frac{|\calF|}{l} \sum_{j=1}^l 2^{n^-(\phi_j)} \mathbb{I}_{\{i\in \calR(\phi_j)\}})  \\ &= \sum_{\phi \in \calF} 2^{n^-(\phi)}\mathbb{I}_{\{i\in \calR(\phi )\}} =  \sum_{\phi \in \calF_{ii}} 2^{n^-(\phi)}   =  w(\calF_{ii}).
% \end{aligned}
% \end{equation}
% This computation confirms that $\widehat{w}_l(\calF)$ and $\widehat{w}_l(\calF_{ii})$ are indeed unbiased estimators for $w(\calF)$ and $w(\calF_{ii})$,   which  completes the proof. \end{proof}

\subsection{Hoeffding's inequality}

 \begin{lemma}[Hoeffding's inequality~\cite{Ho94}]
Let $x_1,x_2,\cdots, x_l$ be $l$ independent random variables satisfying $a \leq x_i \leq b$ for all $i=1,2,\cdots,n$. Let $x=\frac{1}{l}\sum_{i=1}^l x_i$. Then for any $\epsilon>0$, $\mathbb{P}(|x-\mathbb{E}(x)| \ge \epsilon) \le 2 \, {\rm exp}\left(-\frac{2l \epsilon^2}{(b-a)^2}\right)$. 
\end{lemma}

\subsection{Proof of Theorem~\ref{th-var}}


\begin{proof}
   In a balanced signed graph $\calG$, there are no negative cycles. Then we have  $\widehat{q}_{ij} =  \frac{1}{l} \sum_{k=1}^l   {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}},$ $\widehat{q}_{ii} = \frac{1}{l}   \sum_{j=1}^l  \mathbb{I}_{\{i\in \calR(\phi_j)\}},$  $\widetilde{q}_{ii} = \frac{1}{1+d_i}(1+\sum_{k\neq i}\widehat{q}_{ik}w_{ki}).$ Since $\phi_1,\phi_2,\cdots,\phi_l$ are independently and uniformly sampled from the set $\calF$, the sample size $l$ does not influence the relative variances \( \widetilde{q}_{ii}\) and \( \widehat{q}_{ii}\). For simplicity, we assume $l=1$ for the remainder of this proof. Under this assumption, the variance of $\widehat{q}_{ii}$ is $ {\rm Var}(\widehat{q}_{ii}) = q_{ii} - q_{ii}^2$. 
    The variance of $\widetilde{q}_{ii}$ can be derived as follows:
    \begin{equation}\label{varvar}
    \begin{aligned}
    &\quad {\rm Var}(\widetilde{q}_{ii})= \mathbb{E}(\widetilde{q}_{ii}^2) - (\mathbb{E}(\widetilde{q}_{ii}))^2 = \frac{1}{(1+d_i)^2}\mathbb{E}(( 1+ \sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
     \\ &= \frac{1}{(1+d_i)^2}\mathbb{E}(1+2\sum_{k\neq i}\widehat{q}_{ik}w_{ki}+ (\sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
     \\ &= \frac{1+3\sum_{k\neq i}{q}_{ik}w_{ki}}{(1+d_i)^2}-q_{ii}^2  =  \frac{1+3((1+d_i)q_{ii}-1)}{(1+d_i)^2} - q_{ii}^2 \\ &=\frac{3q_{ii}}{1+d_i} - \frac{2}{(1+d_i)^2}  -q_{ii}^2.
    \end{aligned}
\end{equation}
The simplification uses the assumptions that $\mathbb{E}(\widehat{q}_{ik}\widehat{q}_{is}) = 0$ for any $k\neq s\neq i$ and $\mathbb{E}(\widehat{q}_{ik}^2)= |q_{ik}| ={q}_{ik}w_{ki} $ in balanced signed graphs.
Then we get the following equality:
\begin{equation}
        {\rm Var}\{\widehat{q}_{ii}\} - {\rm Var}\{\widetilde{q}_{ii}\}    =\frac{2(1-q_{ii})}{(1+d_i)^2}+ \frac{d_{i}(d_i-1)q_{ii}}{(1+d_i)^2}\geq 0.
\end{equation}
It shows that the variance of $\widetilde{q}_{ii}$  is no more than  the variance of the estimator $\widehat{q}_{ii}$, which completes the proof. In fact, Theorem~\ref{th-var} extends Lemma 6.1 from~\cite{SuZh24}, as the unsigned case can be viewed as a special case of balanced signed graphs.
\end{proof}






\subsection{Proof of Theorem~\ref{th-l}}


\begin{proof}
Setting $a = 0$ and $b = |\calF| \alpha$, and choosing $l$ as previously specified,  we can prove the inequalities~\eqref{ineq1} and~\eqref{ineq2} directly by utilizing Hoeffding's inequality. Assuming the above inequalities hold, the error in the estimated ratio can be bounded as follows: 
    \begin{equation}
        \begin{aligned}
             &\quad \left | \widehat{\qq}[i] - q_{ii} \right | =     \left | \frac{\widehat{w}_l(\calF_{ii})}{ \widehat{w}_l(\calF)} - \frac{w(\calF_{ii})}{w(\calF)}\right | \\& = \left | \frac{w(\calF_{ii})(\widehat{w}_l(\calF )-w(\calF)) + w(\calF) (w(\calF_{ii}) - \widehat{w}_l(\calF_{ii})  )  }{\widehat{w}_l(\calF)w(\calF)}\right | \\& \leq 
              \frac{w(\calF_{ii})|\widehat{w}_l(\calF )-w(\calF)|+ w(\calF) |w(\calF_{ii}) - \widehat{w}_l(\calF_{ii}) |  }{\widehat{w}_l(\calF)w(\calF)} \\ & \leq \frac{\frac{\epsilon \beta }{ 2+ \epsilon } (w(\calF_{ii}) + w(\calF))|\calF|}{\widehat{w}_l(\calF)w(\calF)} \leq \frac{\frac{2\epsilon\beta}{2+\epsilon}}{\beta-\frac{\epsilon\beta}{2+\epsilon}} = \epsilon,
        \end{aligned}
    \end{equation}
where the last inequality holds since $w(\calF_{ii}) \leq w(\calF)$, $w(\calF) = |\calF|\beta $ and $\widehat{w}_l(\calF) \geq w(\calF)-|\calF| \frac{\epsilon \beta }{ 2+ \epsilon }$, which finishes the proof.
\end{proof}



\iffalse
\subsection{Proof of Theorem~\ref{th-var}}

\begin{proof}
   In a balanced signed graph $\calG$, there is no negative cycles. Then we have $$\widehat{q}_{ii} = \frac{1}{l}   \sum_{j=1}^l  \mathbb{I}_{\{i\in \calR(\phi_j)\}},$$  $$\widehat{q}_{ij} =  \frac{1}{l} \sum_{k=1}^l   {\rm sign}(P_{ij}) \mathbb{I}_{\{ r_{\phi_{k}}(i) = j \}},$$  $$\widetilde{q}_{ii} = \frac{1}{1+d_i}(1+\sum_{k\neq i}\widehat{q}_{ik}w_{ki}).$$ Since $\phi_1,\cdots,\phi_l$ are independently and uniformly sampled from the set $\calF$, the sample size $l$ does not influence the relative variances \( \widetilde{q}_{ii}\) and \( \widehat{q}_{ii}\). For simplicity, we assume $l=1$ for the remainder of this proof. Under this assumption, the variance of $\widehat{q}_{ii}$ is $ {\rm Var}(\widehat{q}_{ii}) = q_{ii} - q_{ii}^2$. 
    The variance of $\widetilde{q}_{ii}$ can be derived as follows:
    \begin{equation}\label{varvar}
    \begin{aligned}
    &\quad {\rm Var}(\widetilde{q}_{ii})= \mathbb{E}(\widetilde{q}_{ii})^2 - (\mathbb{E}(\widetilde{q}_{ii}))^2 \\&= \frac{1}{(1+d_i)^2}\mathbb{E}(( 1+ \sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
     \\ &= \frac{1}{(1+d_i)^2}\mathbb{E}(1+2\sum_{k\neq i}\widehat{q}_{ik}w_{ki}+ (\sum_{k\neq i}\widehat{q}_{ik}w_{ki})^2 ) - q_{ii}^2 
     \\ &= \frac{1+3\sum_{k\neq i}{q}_{ik}w_{ki}}{(1+d_i)^2}-q_{ii}^2  =  \frac{1+3((1+d_i)q_{ii}-1)}{(1+d_i)^2} - q_{ii}^2 \\ &=\frac{3q_{ii}}{1+d_i} - \frac{2}{(1+d_i)^2}  -q_{ii}^2.
    \end{aligned}
\end{equation}
The simplification uses the assumptions that $\mathbb{E}(\widehat{q}_{ik}\widehat{q}_{is}) = 0$ for any $k\neq s\neq i$ and $\mathbb{E}(\widehat{q}_{ik}^2)= |q_{ik}| ={q}_{ik}w_{ki} $ in balanced signed graphs.
Then we get the following equality:
\begin{equation}
        {\rm Var}\{\widehat{q}_{ii}\} - {\rm Var}\{\widetilde{q}_{ii}\}    =\frac{2(1-q_{ii})}{(1+d_i)^2}+ \frac{d_{i}(d_i-1)q_{ii}}{(1+d_i)^2}\geq 0.
\end{equation}
It shows that the variance of $\widetilde{q}_{ii}$  is no more than  the variance of the estimator $\widehat{q}_{ii}$, which completes the proof.
\end{proof}

\fi

\section{Pseudocodes for Algorithms}




\subsection{Pseudocode for Algorithm GSCF}
 


\begin{algorithm}
\caption{$\textsc{GSCF}(\calG)$}
\label{alg-grf}
\begin{algorithmic}[1]
\STATE {\bfseries Input:} Signed graph $\calG=(V,E,w)$ with $|V|=n$
\STATE {\bfseries Output:} Generalized spanning converging forest $\phi$
\STATE {\bfseries Initialize:} $\phi \leftarrow \emptyset$; $V_\phi \leftarrow \emptyset$; $E_\phi \leftarrow \emptyset$
\FOR{$i=1,2,\cdots,n$}
    \STATE $u \leftarrow i$
    \STATE Create a branch $P \leftarrow \emptyset$
    \WHILE{$u \notin V_\phi$}
        \STATE ${\rm seed} \leftarrow \textsc{Rand}(0,1)$
        \IF{${\rm seed} \le \frac{1}{1+d_u}$}
            \STATE Mark $u$ as the root node
            \STATE {\bfseries break}  
        \ELSE
            \STATE Select a random neighbor $v \in N(u)$
            \STATE Add edge $(u,v)$ to $P$
            \IF{$P$ has a negative cycle $C$}
                \STATE {\bfseries break}  
            \ELSE
                \STATE $u \leftarrow v$
            \ENDIF
        \ENDIF
    \ENDWHILE
    \IF{$P$ has a negative cycle $C$}
        \STATE Partition $P$ into $P'$ and $C$
        \STATE Perform loop-erasure on $P'$ and obtain $P'_{\rm LE}$
        \STATE Add $P'_{\rm LE}$ and $C$ to $\phi$; update $V_\phi$ and $E_\phi$
    \ELSE
        \STATE Perform loop-erasure on $P$ and obtain $P_{\rm LE}$
        \STATE Add $P_{\rm LE}$ to $\phi$; update $V_\phi$ and $E_\phi$
    \ENDIF
\ENDFOR
\STATE {\bfseries return} $\phi$
\end{algorithmic}
\end{algorithm}

\newpage


\subsection{Pseudocode for Algorithm FMDE/FMDE+}
 


\begin{algorithm}[h!]
\caption{\textsc{FMDE/FMDE+}($\calG,l$)}
\label{alg-FMDE}
\begin{algorithmic}[1]
\STATE {\bfseries Input:} Signed graph $\calG$; sample number $l$
\STATE {\bfseries Output:} $\widehat{\qq}$ (\textsc{FMDE} estimator), $\widetilde{\qq}$ (\textsc{FMDE+} estimator)
\STATE {\bfseries Initialize:} $\widehat{\qq}[i]\leftarrow 0$, $\widetilde{\qq}[i]\leftarrow 0$ for $i=1,\ldots,n$; $\gamma \leftarrow 0$
\FOR{$t=1,2,\ldots,l$}
    \STATE $\phi \leftarrow \textsc{GSCF}(\calG)$
    \STATE $\gamma \leftarrow \gamma + 2^{n^{-}(\phi)}$
    \FOR{$i=1,2,\ldots,n$}
        \STATE $j \leftarrow r_{\phi}(i)$
        \IF{$j=i$}
            \STATE $\widehat{\qq}[i] \leftarrow \widehat{\qq}[i] + 2^{n^{-}(\phi)}$
        \ENDIF
        \IF{$j>0$ {\bfseries and} $i\in N(j)$}
            \STATE $\widetilde{\qq}[i] \leftarrow \widetilde{\qq}[i] + {\rm sign}(P_{ij})\, w_{ji}\, 2^{n^{-}(\phi)}$
        \ENDIF
    \ENDFOR
\ENDFOR
\STATE $\widehat{\qq} \leftarrow \widehat{\qq} / \gamma$
\FOR{$i=1,2,\ldots,n$}
    \STATE $\widetilde{\qq}[i] \leftarrow \frac{\widetilde{\qq}[i]}{\gamma(1+d_i)} + \frac{1}{1+d_i}$
\ENDFOR
\STATE {\bfseries return} $\widehat{\qq}, \widetilde{\qq}$
\end{algorithmic}
\end{algorithm}



\subsection{Pseudocode for Algorithm FJOE}
 
\begin{algorithm}[h!]
\caption{\textsc{FJOE}($L,i,\sss$)}
\label{alg:opinion-estimation}
\begin{algorithmic}[1]
\STATE {\bfseries Input:} 
List $L$ of $l$ generalized spanning converging forests; node index $i$; internal opinion vector $\sss$
\STATE {\bfseries Output:} Estimated expressed opinion $\widehat{z_i}$ for node $i$
\STATE {\bfseries Initialize:} $\widehat{z_i} \leftarrow 0$; $\gamma \leftarrow 0$
\FORALL{$\phi \in L$}
    \STATE $\eta \leftarrow 2^{n^{-}(\phi)}$
    \STATE $\gamma \leftarrow \gamma + \eta$
    \STATE $k \leftarrow r_{\phi}(i)$
    \IF{$k \neq 0$}
        \STATE $\widehat{z_i} \leftarrow \widehat{z_i} + {\rm sign}(P_{ik})\, \eta\, s_k$
    \ENDIF
\ENDFOR
\STATE $\widehat{z_i} \leftarrow \widehat{z_i} / \gamma$
\STATE {\bfseries return} $\widehat{z_i}$
\end{algorithmic}
\end{algorithm}



\section{Datasets and Equipment }

\subsection{Equipment and Implementation Details}


All experiments are conducted using the Julia programming language in a computational environment equipped with a 2.10 GHz Intel(R) Xeon(R) Platinum 8352V CPU and 256GB of primary memory. For all algorithms, the number of generalized spanning converging forests $l$ is set according to Theorem~\ref{th-l}, with parameters $\delta = 0.01$.  Since real networks usually contain very few negative edges, and in balanced signed graphs $\alpha / \beta = 1$. Since $\alpha$ and $\beta$ are difficult to compute exactly, we set $\alpha / \beta = 2$ as a conservative choice. Moreover, the bound in Theorem~\ref{th-l} is loose in practice; e.g., as shown in Figure 2, when $\epsilon= 0.3$, FMDE+ achieves an average relative error of about 0.01.  Given that our sampling algorithms can be parallelized efficiently, we use 72 computing cores to speed up the process.

\subsection{Datasets}
 The datasets of selected real networks are publicly available in the KONECT~\cite{Ku13} and SNAP~\cite{LeSo16}.  Our experiments are conducted on a diverse range of networks, with node counts ranging from 2,539 to over 23 million and edge counts from 12,969 to 112 million. Details of these datasets are presented in Table~\ref{datasets}, which includes six small graphs along with six medium and large-sized graphs. We utilize both original signed graphs and modified signed graphs for our experiments.  These  modified signed graphs are denoted with a superscript asterisk in Table~\ref{datasets}.
  
\begin{table}[htbp!]\fontsize{8}{11}\caption{Datasets used in experiments. }\label{datasets}\centering
\begin{tabular}{cccc}
\toprule
Type                                                                                    & Network         & Nodes      & Edges       \\ \midrule
\multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Small\\ Graphs\end{tabular}}                 & Adolescent$^*$   & 2,539      & 12,969      \\ & Bitcoinotc      & 5,881      & 35,592      \\    & Gnutella08$^*$    & 6,301      & 20,777      \\   & Wikielec   & 7,118      & 103,675     \\   & Wikipedia$^*$  & 17,649     & 296,918     \\   & SlashdotZoo   & 79,120     & 515,397     \\ \midrule
\multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Medium \\ and\\ Large\\ Graphs\end{tabular}} & Epinions        & 131,828    & 841,372     \\   & WikiL           & 258,259    & 3,187,096   \\   & Youtube$^*$         & 1,134,890  & 2,987,624   \\   & Dblp$^*$            & 5,624,219  & 12,282,055  \\   & Livejournal$^*$     & 7,489,073  & 112,307,315 \\   & FullUSA$^*$         & 23,947,300 & 57,708,600  \\ \bottomrule
\end{tabular}
\end{table}

\newpage


\end{document}

% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This version was created
% by Iain Murray in 2018, and modified by Alexandre Bouchard in
% 2019 and 2021 and by Csaba Szepesvari, Gang Niu and Sivan Sabato in 2022.
% Modified again in 2023 and 2024 by Sivan Sabato and Jonathan Scarlett.
% Previous contributors include Dan Roy, Lise Getoor and Tobias
% Scheffer, which was slightly modified from the 2010 version by
% Thorsten Joachims & Johannes Fuernkranz, slightly modified from the
% 2009 version by Kiri Wagstaff and Sam Roweis's 2008 version, which is
% slightly modified from Prasad Tadepalli's 2007 version which is a
% lightly changed version of the previous year's version by Andrew
% Moore, which was in turn edited from those of Kristian Kersting and
% Codrina Lauth. Alex Smola contributed to the algorithmic style files.