Fast Maximization of Current Flow Group Closeness Centrality Zhongzhi Zhang is the corresponding author. Haisong Xia, Zhongzhi Zhang Abstract Derived from effective resistances, the current flow closeness centrality (CFCC) for a group of nodes measures the importance of node groups in an undirected graph with n n nodes. Given the widespread applications of identifying crucial nodes, we investigate the problem of maximizing CFCC for a node group S S subject to the cardinality constraint | S | = k ≪ n |S|=k\ll n . Despite the proven NP-hardness of this problem, we propose two novel greedy algorithms for its solution. Our algorithms are based on spanning forest sampling and Schur complement, which exhibit nearly linear time complexities and achieve an approximation factor of 1 − k k − 1 ​ 1 e − ϵ 1-\frac{k}{k-1}\frac{1}{\mathrm{e}}-\epsilon for any 0 < ϵ < 1 0<\epsilon<1 . Extensive experiments on real-world graphs illustrate that our algorithms outperform the state-of-the-art method in terms of efficiency and effectiveness, scaling to graphs with millions of nodes. I Introduction As a fundamental problem in the field of complex networks, the identification of crucial nodes has garnered widespread research interest [ 1 , 2 ] . Due to its importance in network analysis, this problem has been applied to various areas, including graph mining [ 3 ] , leader-follower opinion dynamics [ 4 ] , and influence maximization [ 5 , 6 ] . The most intuitive approach to solve this problem is to design a centrality that evaluates the importance of each node, thus transforming the identification problem into a computational one. Previous studies [ 7 , 8 , 9 , 10 ] have proposed various centralities to analyze the roles of nodes in a graph, with a large proportion focusing on closeness centrality. The closeness of a node is defined as the reciprocal of the sum of shortest path distances between it and all other nodes in the graph. Despite its advantage over local centralities, closeness centrality only considers the shortest paths. This sensitivity to noise potentially leads to counterintuitive results [ 11 ] . To address the issue of sensitivity, current flow closeness centrality (CFCC) [ 12 ] is presented based on resistance distance in the corresponding electrical networks. Resistance distance is a crucial metric for solving diverse fundamental problems in the field of graph theory. Specifically, in the data management community, resistance distance is utilized to design effective graph systems and applications [ 13 , 14 , 15 , 16 ] . Many researchers also develop efficient approximation of resistance distance to facilitate data management tasks [ 17 , 18 ] . Since CFCC is defined via resistance distance, it has been applied to analyze the vulnerability of power grids [ 19 , 20 ] and optimize the performance of conductive films [ 21 ] . Additionally, resistance distance considers contributions from all paths between node pairs, which mirrors the propagation of electrical spike signals in brain networks [ 22 ] . This property enables CFCC to identify active neurons in the analysis of brain networks [ 23 ] . In other types of networks, the current flow-based closeness also outperforms classical counterparts in identifying crucial nodes [ 11 ] . While most previous studies focus on identifying individual nodes, many practical problems essentially require finding a group of nodes that is the most important among all node groups with capacity k\ll n , where n denotes the number of all nodes. For instance, how to place resources on k peers in P2P networks for easy access by others [ 24 ] . Meanwhile, placing sensors of wireless networks involves selecting an optimal subset of nodes for sampling physical signals such as radiation or temperature [ 25 , 26 ] . Finally, the challenge of point cloud sampling [ 27 , 28 ] lies in selecting a representative subset of points to preserve the geometric features for reconstruction. Recently, the concept of current flow closeness centrality (CFCC) has been extended from individual nodes to node groups [ 29 ] . Additionally, the problem of selecting a node group of size k , aiming to maximize its CFCC, has been proposed. The state-of-the-art algorithm has been developed to approximately address it, which utilizes a fast Laplacian solver. However, its running time, while nearly linear in the number of edges, remains prohibitively long for large-scale networks with more than 10 million edges. Contributions. In light of this limitation, we establish the connection between Current Flow Closeness Maximization (CFCM) and rooted spanning forests, motivating our proposal of a greedy Monte Carlo algorithm ForestCFCM . Based on sampling forests, ForestCFCM is pleasingly parallelizable while maintaining an approximation factor for solving CFCM. To further enhance efficiency and effectiveness, we develop another greedy algorithm SchurCFCM . Based on the estimation of Schur complement, SchurCFCM accelerates sampling spanning forests and enhances the quality of CFCM solutions, while still preserving an approximation factor. Numerical experiments validate the superiority of SchurCFCM over both ForestCFCM and the state-of-the-art method in terms of efficiency and effectiveness. Our contributions of this work are summarized as follows. • We propose two Monte Carlo algorithms, ForestCFCM and SchurCFCM , for approximately maximizing CFCC C(S) under the cardinality constraint \left|S\right|=k . Both algorithms sample rooted spanning forests, with SchurCFCM additionally leveraging Schur complement. • Both of our algorithms achieve an approximation factor of 1-\frac{k}{k-1}\frac{1}{\mathrm{e}}-\epsilon for 0<\epsilon<1 . Meanwhile, SchurCFCM exhibits a nearly linear time complexity. • We conduct extensive experiments on real-world graphs. The results demonstrate that both of our proposed algorithms are up to 370\times faster than the state-of-the-art method, while maintaining superior effectiveness. II Preliminaries II-A Notations We use normal lowercase letters like a,b,c to denote real scalars, use bold lowercase letters like \bm{a},\bm{b},\bm{c} to denote vectors, and use bold uppercase letters like \bm{A},\bm{B},\bm{C} to denote matrices. To represent specific elements in matrices, we use \bm{A}_{{i}{j}} to denote entry (i,j) of matrix \bm{A} . Moreover, we write sets in subscripts to denote subvectors and submatrices. For the case of subvectors, \bm{a}_{-S} represents the subvector of \bm{a} obtained by removing elements with indices in set S . For the case of submatrices, \bm{A}_{{U}{T}} denotes the submatrix of \bm{A} with row indices in U and column indices in T , and \bm{A}_{-S} represents the submatrix of \bm{A} obtained by removing elements with row indices or column indices in S . Finally, we use \bm{e}_{i} to denote the {i}^{\rm{th}} standard basis vector, and \bm{1} to denote a vector with all elements being 1 . Table I lists the frequently used notations throughout this paper. TABLE I: Frequently used notations. Notation Description G=(V,E) A graph with node set V and edge set E . n,m The number of nodes and edges in G . \tau The diameter of G . d_{\max} The maximum degree of nodes in G . d_{\max}(S) The maximum degree of nodes in the subgraph obtained from G by removing nodes in set S and and their incident edges. {\pi}_{u},\rho_{u} The parent node and root node of u in a spanning forest. {\tilde{\mathcal{N}}}_{u,S}^{{a}\to{b}} The number of sampled forests where path from u to root set S traverses edge \left(a,b\right) from a to b . {\tilde{\mathcal{N}}}\left(\rho_{u}={t}\right) The number of spanning forests where u is rooted at t . \Phi_{u,S}(v) The voltage at v with unit current flowing from u to S . \overline{\Phi}_{u,S}(v) The unbiased estimator of \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{v} . \overline{\varPhi}_{\bm{w},S}(u) The unbiased estimator of \bm{w}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u} . \mathcal{S}_{\scriptscriptstyle T}(\bm{M}) The Schur complement of matrix \bm{M} onto subset T . Since we prove the approximation guarantee of our algorithms in Sections III-E and IV-B , it is necessary to give the definition of approximate factor. Definition II.1 ( \epsilon -approximation) Let x and \tilde{x} be positive scalars, and let \epsilon be an error parameter satisfying \epsilon\in(0,1) . Then \tilde{x} is an \epsilon -approximation of x if (1-\epsilon)x\leq\tilde{x}\leq(1+\epsilon)x holds, which we denote as \tilde{x}\approx_{\epsilon}x . II-B Graphs and Laplacian Matrices We use G=(V,E) to denote connected undirected graph with n=\left|V\right| nodes and m=\left|E\right| edges, where V and E denote, respectively, the node set and edge set of G . We use e=\left(u,v\right) to denote an edge e linking node u and node v . The adjacency matrix of G is denoted as \bm{A}\in\mathbb{R}^{n\times n} : for two nodes i\in V and j\in V , \bm{A}_{{i}{j}}=\bm{A}_{{j}{i}}=1 if i and j are adjacent, and \bm{A}_{{i}{j}}=\bm{A}_{{j}{i}}=0 otherwise. The degree vector of G is defined as \bm{d}=\bm{A}\bm{1}=\left(d_{1},d_{2},\dots,d_{n}\right)^{\top} , where d_{i} represents the degree of node i . If we denote the degree diagonal matrix as \bm{D}=\mathrm{diag}\left(d_{1},d_{2},\cdots,d_{n}\right) , then the Laplacian matrix \bm{L} of G is defined as \bm{L}=\bm{D}-\bm{A} . Since \bm{L} is not invertible due to its null space \bm{1} , we turn to use its pseudoinverse \bm{L}^{\dagger}=\big(\bm{L}+\frac{1}{n}\bm{1}\bm{1}^{\top}\big)^{-1}-\frac{1}{n}\bm{1}\bm{1}^{\top} . \bm{L}^{\dagger} appears in many quantities related to random walks, such as the Kemeny constant [ 30 ] . Moreover, It is easy to verify that Laplacian matrix \bm{L} and its submatrices \bm{L}_{-{S}} are Symmetric Diagonally Dominant (SDD). II-C Spanning Forests and Random Walks For a graph G=(V,E) , a spanning subgraph of G retains all nodes from V while including only a subset of edges from E . A spanning forest is a spanning subgraph of G , whose connected components are trees or isolated nodes. A rooted spanning forest of G is a spanning forest of G where a particular node in each tree is designated as its root. The set of all root nodes forms the root set of this spanning forest. Many studies focus on methods for uniformly sampling rooted spanning forests, including Wilson’s algorithm [ 31 ] based on loop-erased random walks. For a connected graph, a classical random walk is defined by its transition matrix \bm{P} . At each step, if the walker is at node i , it moves to an adjacent node j with equal probability \bm{P}_{{i}{j}} . It follows that \bm{P}=\bm{D}^{-1}\bm{A} . To generate a spanning forest with root set S , the loop-erased random walk is simulated iteratively. Initially \mathcal{F}=S , when the random walker visits a node in \mathcal{F} , the loop-erased path from the source node to this node is added into \mathcal{F} . Notably, it has been proved in [ 31 ] that the distribution of forests sampled by Wilson’s algorithm is independent of the order of source nodes. II-D Resistance Distance and Relevant Centrality For an arbitrary undirected graph G=(V,E) , we define its corresponding electrical network by treating edges as unit resistors and nodes as junctions between resistors [ 32 ] . For graph G , if we denote \Phi_{i,j}(u) as the voltage of node u when a unit current enters at node i and leaves at node j , then the resistance distance R{({i},{j})}\triangleq\Phi_{i,j}(i)-\Phi_{i,j}(j) is defined as the effective resistance between i and j in the corresponding electrical network [ 33 ] . For a connected graph G , the resistance distance R{({i},{j})} between two nodes i and j can be expressed in terms of \bm{L}^{\dagger} [ 33 , 34 ] and the inverse for submatrices of \bm{L} [ 35 ] as: \displaystyle R{({i},{j})}=\bm{L}^{\dagger}_{{i}{i}}+\bm{L}^{\dagger}_{{j}{j}}-2\bm{L}^{\dagger}_{{i}{j}}, (1) \displaystyle R{({i},{j})}=\big(\bm{L}_{-{i}}^{-1}\big)_{{j}{j}}=\big(\bm{L}_{-{j}}^{-1}\big)_{{i}{i}}. (2) Since the resistance distance exhibits properties of a metric, we can use it to represent the proximity between node pairs, and measure the importance of each node by defining relevant centrality, such as the current flow closeness centrality (CFCC) [ 12 ] . For an n -node connected graph, the CFCC of a node u is defined as C(u)\triangleq n/\left(\sum_{v\in V}R{({u},{v})}\right) . According to ( 1 ), we can easily represent C(u) in terms of the diagonal elements of \bm{L}^{\dagger} as C(u)={n}/\big(\mathrm{Tr}\big(\bm{L}^{\dagger}\big)+n\bm{L}^{\dagger}_{{u}{u}}\big) . II-E Group Centrality and Its Maximization To measure the importance of node groups, Li et al. [ 29 ] extended the concept of CFCC to multiple nodes. In defining CFCC for a node group S , all nodes in S are assumed to be grounded, with their voltages being consistently at 0 . Therefore, we denote the voltage of node v when a unit current enters at node u and leaves at an arbitrary node in S as \Phi_{u,S}(v) . According to [ 36 ] , the resistance distance R{({u},{S})} between an individual node u and a grounded node group S is defined as \Phi_{u,S}(u)=\big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} . Therefore, for an n -node graph, the CFCC of a node group S can be defined as [ 29 ] : C(S)\triangleq\frac{n}{\sum_{u\in V}R{({u},{S})}}=\frac{n}{\mathrm{Tr}\big(\bm{L}_{-{S}}^{-1}\big)}. (3) Equation ( 3 ) illustrates that a smaller sum of R{({u},{S})} indicates greater accessibility for a node u\in V\setminus{S} to nodes in S , suggesting that S is more significant in the network. This connection between accessibility and importance forms the basis for terming this measure as group centrality. Therefore, the problem of finding the most important node group with cardinality constraint is naturally given in [ 29 ] : Definition II.2 (Current Flow Closeness Maximization, CFCM) For an n -node graph G=(V,E) and an integer k\ll n , the goal is to find a node group S^{*} of size k that maximizes its CFCC. In other words, S^{*}\triangleq\argmax\limits_{S\subset V,\left|S\right|=k}C(S) . II-F State-of-the-art Method Algorithm Design. As a combinatorial optimization problem, CFCM is proved in [ 29 ] to be NP-hard. Therefore, designing a polynomial-time algorithm to solve CFCM is nearly impossible. However, the reciprocal of CFCC is also proved in [ 29 ] to be monotone and supermodular. These findings indicate that a naive greedy strategy yields a solution with an approximation factor of 1-\frac{k}{k-1}\frac{1}{\mathrm{e}} [ 37 ] . Set S is initially empty, then k nodes from V\setminus{S} are added to S iteratively. For the first iteration, the task is to find the node u\in V with minimum sum of resistance distances, which is expressed as \sum_{v\in V}R{({u},{v})}=\mathrm{Tr}\big(\bm{L}^{\dagger}\big)+n\bm{L}^{\dagger}_{{u}{u}}. (4) For subsequent iterations, the node u\in V\setminus{S} with maximum marginal gain \Delta(u,S) is selected, which is expressed as \small\Delta(u,S)\triangleq\mathrm{Tr}\big(\bm{L}_{-{S}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{(S+u)}}^{-1}\big)=\frac{\big(\bm{L}_{-{S}}^{-2}\big)_{{u}{u}}}{\big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}}}\ (S\neq\varnothing). (5) Equations ( 4 ) and ( 5 ) indicate that computing the marginal gain involves calculating diagonal elements of \bm{L}^{\dagger} for the first iteration and diagonal elements of \bm{L}_{-{S}}^{-1} and \bm{L}_{-{S}}^{-2} for subsequent iterations. Leveraging the Johnson-Lindenstrauss lemma [ 38 ] , the state-of-the-art method ApproxGreedy transforms estimating diagonal elements of matrix inverse into solving linear equations related to the Laplacian matrix. Rather than directly solving linear equations, ApproxGreedy introduces a nearly linear-time Laplacian solver [ 39 ] . Performance Discussion. The key limitation of ApproxGreedy stems from its reliance on Laplacian solver. Each iteration requires solving O(\epsilon^{-1}\log n) linear equations, yielding a time complexity of \tilde{O}(k\epsilon^{-3}m) dominated by the number m of edges. This creates two fundamental bottlenecks. First, for dense graphs where m=O(n^{2}) , the quadratic scaling becomes prohibitive. Second, even on sparse graphs, ApproxGreedy depends on highly optimized implementations of Laplacian solver. This dependency limits deployment in environments where computing resource is constrained or language flexibility is critical. Our proposed algorithms address these limitations by replacing Laplacian solvers with other techniques. Through spanning forest sampling and improvements from Schur complement, the time complexity of our algorithms is nearly linear in the node number n . These approaches enable better scalability to denser graphs, as demonstrated in Section V . III Algorithm Based on Forest Sampling In this section, we propose a greedy algorithm to approximately solve CFCM through sampling rooted spanning forests, addressing the challenge of estimating the marginal gain defined in ( 4 ) and ( 5 ). This section proceeds as follows. We first derive unbiased estimators for entries of \bm{L}_{-{S}}^{-1} via connections between spanning forests and electrical network analysis (Lemma III.3 ). Next, we approximate diagonal elements of \bm{L}_{-{S}}^{-2} by reducing its dimension (Lemma III.4 ). Additionally, we reformulate diagonal elements of \bm{L}^{\dagger} in terms of \bm{L}_{-{S}}^{-1} to overcome weak diagonal dominance (Lemma III.5 ). An adaptive sampling strategy using empirical Bernstein inequality is then introduced to optimize efficiency. Finally, these components culminate in the algorithm ForestCFCM , which achieves nearly linear complexity and rigorous approximation guarantees (Theorem III.11 ). III-A Estimation of Laplacian Submatrix Inverse For an undirected graph G , let N denote the total number of spanning trees. Given two nodes u,v and an edge \left(a,b\right) , we denote {N}_{u,v}^{{a}\to{b}} as the number of spanning trees where the unique path from u to v traverses edge \left(a,b\right) from a to b . According to [ 40 ] , we have Lemma III.1 In the corresponding electrical network of a graph G , suppose a unit current flows from u to v . The current through \left(a,b\right) is then given by \frac{1}{N}\big({N}_{u,v}^{{a}\to{b}}-{N}_{u,v}^{{b}\to{a}}\big) . Since CFCC is defined for node groups, we subsequently extend Lemma III.1 to the case of multiple target nodes. Similarly, we denote \mathcal{N}(S) as the total number of spanning forests with root set S , and let {\mathcal{N}}_{u,S}^{{a}\to{b}} denote the number of spanning forests where the unique path from u to an arbitrary node in S traverses edge \left(a,b\right) in the direction from a to b . Lemma III.2 Let G be a graph with a node group S . For a unit current flowing from u to an arbitrary node in the grounded node group S , the current through \left(a,b\right) is given by \frac{1}{\mathcal{N}(S)}\big({\mathcal{N}}_{u,S}^{{a}\to{b}}-{\mathcal{N}}_{u,S}^{{b}\to{a}}\big) . Proof: To extend Lemma III.1 to multiple targets, we map spanning forests in G to spanning trees in an augmented graph G^{*}=(V\cup\{r^{*}\},E\cup\{\left(r^{*},s\right)|s\in S\}) . Each spanning forest of G rooted at S bijectively corresponds to a spanning tree of G^{*} rooted at r^{*} . Applying Lemma III.1 to G^{*} with unit current from u to r^{*} , the current through edge \left(a,b\right) in E equals \frac{1}{N}({N}_{u,r^{*}}^{{a}\to{b}}-{N}_{u,r^{*}}^{{b}\to{a}}) . Translating via the forest-tree correspondence yields \frac{1}{\mathcal{N}(S)}({\mathcal{N}}_{u,S}^{{a}\to{b}}-{\mathcal{N}}_{u,S}^{{b}\to{a}}) for G , completing the proof. ∎ Given a graph G and a unit current with source node u and grounded target node group S , Lemma III.2 enables us to approximate the current through any edge of G . Leveraging this, we can estimate the voltage of any node in G , yielding an unbiased estimator of \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{v} . Lemma III.3 Let G be a graph with a node group S . Suppose we sample \tilde{\mathcal{N}}(S) spanning forests with root set S , and let {\tilde{\mathcal{N}}}_{u,S}^{{a}\to{b}} denote the number of sampled forests where the unique path from u to an arbitrary node in S traverses edge \left(a,b\right) from a to b . Then the quantity \overline{\Phi}_{u,S}(v)\triangleq\frac{1}{\tilde{\mathcal{N}}(S)}\sum_{\left(a,b\right)\in\mathcal{P}_{{v},{S}}}\big({\tilde{\mathcal{N}}}_{u,S}^{{a}\to{b}}-{\tilde{\mathcal{N}}}_{u,S}^{{b}\to{a}}\big) is an unbiased estimator of \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{v} , where \mathcal{P}_{{v},{S}} denotes edges on paths from v to an arbitrary node in S . Proof: According to [ 36 ] , the voltage \Phi_{u,S}(v) is equal to \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{v}} , which also equals the sum of currents along any path from v to S by Kirchhoff’s law. Recall from Lemma III.2 that \frac{1}{\tilde{\mathcal{N}}(S)}\big({\tilde{\mathcal{N}}}_{u,S}^{{a}\to{b}}-{\tilde{\mathcal{N}}}_{u,S}^{{b}\to{a}}\big) unbiasedly estimates the current in edge \left(a,b\right) , summing these estimators over \mathcal{P}_{{v},{S}} and applying linearity of expectation yields \mathbb{E}\left[\overline{\Phi}_{u,S}(v)\right]=\Phi_{u,S}(v) . ∎ III-B Estimation of Diagonal Elements for Squared Laplacian Submatrix Inverse Despite the relationship between \bm{L}_{-{S}}^{-1} and random spanning forests, there is no obvious physical meaning of \bm{L}_{-{S}}^{-2} . Therefore, we transform estimating the diagonal element \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-2}\bm{e}_{u} into approximating the squared 2 -norm \left\|\bm{L}_{-{S}}^{-1}\bm{e}_{u}\right\|^{2} . However, the time of directly computing one squared 2 -norm in \mathbb{R}^{n} is \Omega(n) . To accelerate this evaluation, we introduce the Johnson-Lindenstrauss Lemma (JL Lemma) [ 38 ] . Lemma III.4 (JL Lemma [ 38 ] ) Given n fixed vectors \bm{v}_{1},\bm{v}_{2},\dots,\bm{v}_{n}\in\mathbb{R}^{d} and 0<\epsilon<1 , let \bm{Q}\in\mathbb{R}^{k\times d} be a matrix with each entry equal to \pm k^{-\nicefrac{{1}}{{2}}} with equal probability. If k\geq 24\epsilon^{-2}\log n , then \left\|\bm{v}_{i}-\bm{v}_{j}\right\|^{2}\approx_{\epsilon}\left\|\bm{Q}\bm{v}_{i}-\bm{Q}\bm{v}_{j}\right\|^{2} holds with probability at least 1-\nicefrac{{1}}{{n}} for all pairs i,j\leq n . Lemma III.4 indicates that the pairwise distances of vectors \bm{v}_{i}\in\mathbb{R}^{d} are almost preserved if we project them into a lower-dimensional space spanned by O(\log n) random vectors. Therefore, we can use this lemma to reduce the dimension of \bm{L}_{-{S}}^{-1}\bm{e}_{u} with bounded error. Concretely, we denote \bm{W}\in\mathbb{R}^{w\times n} as random matrix where w\geq 24\epsilon^{-2}\log n , then we have \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-2}\bm{e}_{u}=\left\|\bm{L}_{-{S}}^{-1}\bm{e}_{u}\right\|^{2}\approx_{\epsilon}\left\|\bm{W}\bm{L}_{-{S}}^{-1}\bm{e}_{u}\right\|^{2}. (6) Incorporating ( 6 ) into Lemma III.3 , we transform estimating \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-2}\bm{e}_{u} into solving linear equations \bm{w}_{i}^{\top}\bm{L}_{-{S}}^{-1} for 1\leq i\leq w . From this, we can further derive the unbiased estimator of \bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-2}\bm{e}_{u} . Specifically, the unbiased estimator for \bm{w}_{i}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u} is defined as \overline{\varPhi}_{\bm{w}_{i},S}(u)\triangleq\sum_{v\in V\setminus{S}}w_{iv}\overline{\Phi}_{v,S}(u) , which is represented as \overline{\varPhi}_{\bm{w}_{i},S}(u)=\frac{1}{\tilde{\mathcal{N}}(S)}\sum_{\left(a,b\right)\in\mathcal{P}_{{u},{S}}}\sum_{v\in V\setminus{S}}w_{iv}\big({\tilde{\mathcal{N}}}_{v,S}^{{a}\to{b}}-{\tilde{\mathcal{N}}}_{v,S}^{{b}\to{a}}\big). III-C Estimation of Diagonal Elements for Laplacian Pseudoinverse The challenge of estimating \bm{L}^{\dagger} arises from the weak diagonal dominance of \bm{L} , which reduces efficiency and effectiveness of approximation algorithms. To address this issue, we represent \bm{e}_{u}^{\top}\bm{L}^{\dagger}\bm{e}_{u} in terms of \bm{L}_{-{S}}^{-1} [ 41 ] , which leads to better diagonal dominance and another unbiased estimator. Lemma III.5 ( [ 41 ] ) When S=\left\{s\right\} , we have \small\bm{e}_{u}^{\top}\bm{L}^{\dagger}\bm{e}_{u}=\begin{cases}\bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u}-\frac{2}{n}\bm{1}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u}+\frac{1}{n^{2}}\bm{1}^{\top}\bm{L}_{-{S}}^{-1}\bm{1}&u\neq s\\ \frac{1}{n^{2}}\bm{1}^{\top}\bm{L}_{-{S}}^{-1}\bm{1}&u=s\end{cases}. Lemma III.5 establishes the connection between diagonal elements of \bm{L}^{\dagger} and elements of \bm{L}_{-{S}}^{-1} , where S contains only one node s . Combining it with Lemma III.3 , we can define the unbiased estimator for \bm{e}_{u}^{\top}\bm{L}^{\dagger}\bm{e}_{u} as linear combinations of \overline{\Phi}_{u,S}(v) . For instance, when S only contains one node s , the unbiased estimator for \bm{1}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u} is defined as \overline{\varPhi}_{\bm{1},S}(u)\triangleq\sum_{v\in V\setminus{S}}\overline{\Phi}_{v,S}(u) , leading to the expression: \overline{\varPhi}_{\bm{1},S}(u)=\frac{1}{\tilde{\mathcal{N}}(S)}\sum_{\left(a,b\right)\in\mathcal{P}_{{u},{S}}}\sum_{v\in V\setminus{S}}\big({\tilde{\mathcal{N}}}_{v,S}^{{a}\to{b}}-{\tilde{\mathcal{N}}}_{v,S}^{{b}\to{a}}\big). (7) Regarding the estimation of \frac{1}{n^{2}}\bm{1}^{\top}\bm{L}_{-{S}}^{-1}\bm{1} , we observe that this term appears in \bm{L}^{\dagger}_{{u}{u}} for every node u\in V . Recall from ( 4 ) that we only need to identify the node u\in V with minimum \bm{L}^{\dagger}_{{u}{u}} , we can omit the computation of this term without introducing any error. III-D Adaptive Forest Sampling After deriving an unbiased estimation of the marginal gain, we need to determine the upper bound of sample size to achieve an approximation factor for solving CFCM. Lemma III.10 uses Hoeffding’s inequality to derive an upper bound. However, this inequality does not consider the variance of random variables, providing a loose theoretical bound. We thus resort to the empirical Bernstein inequality [ 42 ] : Lemma III.6 Let X_{1},X_{2},\dots,X_{n} be n real-valued i.i.d. random variables that satisfy 0\leq X_{i}\leq X_{\mathrm{sup}} . If we denote \bar{X} and X_{\mathrm{var}} as the empirical mean and the empirical variance of X_{i} , then we have \Pr\left(\left|\bar{X}-\mathbb{E}[\bar{X}]\right|\geq f\left(n,X_{\mathrm{var}},X_{\mathrm{sup}},\delta\right)\right)\leq\delta, where f\left(n,X_{\mathrm{var}},X_{\mathrm{sup}},\delta\right)\triangleq\sqrt{\frac{2X_{\mathrm{var}}\log\left(\nicefrac{{3}}{{\delta}}\right)}{n}}+\frac{3X_{\mathrm{sup}}\log\left(\nicefrac{{3}}{{\delta}}\right)}{n} . Lemma III.6 differs from Hoeffding’s inequality in that it incorporates the empirical variance of random variables. While the empirical variance remains unknown a priori, it can be efficiently maintained throughout the sampling process. We introduce the empirical Bernstein inequality while retaining the Hoeffding bound to preserve the theoretical guarantee. Meanwhile, if the empirical error of estimators provided by Lemma III.6 falls below the threshold parameter, we terminate sampling rooted spanning forests. Notably, the approximation factor provided in Theorem III.11 remains unaffected by applying this adaptive strategy. III-E Algorithm Design and Analyses Based on the above analyses, we propose our first approximation algorithm ForestCFCM for solving CFCM, which is depicted in Algorithm 3 . In each subsequent iteration of ForestCFCM , it invokes ForestDelta , which is depicted in Algorithm 2 . Both of them sample random spanning forests through RandomForest , which is depicted in Algorithm 1 . Input : G=(V,E) : an undirected graph; S\subset V : the set of root nodes Output : {\pi}_{u} : the parent node of u\in V\setminus{S} in the random spanning forest \mathcal{F}_{S} of G ; \mathcal{L}_{\textnormal{DFS}} : the list of nodes visited in reverse DFS order on \mathcal{F}_{S} {\pi}_{u}\leftarrow arbitrary value, \textnormal{InForest}_{u}\leftarrow\textnormal{false} for u\in V\setminus{S} 1 \textnormal{InForest}_{s}\leftarrow\textnormal{true} for s\in S , \mathcal{L}_{\textnormal{DFS}}\leftarrow an empty list 2 foreach u\in V\setminus{S} do 3 i\leftarrow u 4 while \textnormal{InForest}_{i}=\textnormal{false} do 5 {\pi}_{i}\leftarrow a randomly selected neighbor of i 6 i\leftarrow{\pi}_{i} 7 i\leftarrow u , \textnormal{chain}\leftarrow an empty list 8 while \textnormal{InForest}_{i}=\textnormal{false} do 9 \textnormal{InForest}_{i}\leftarrow\textnormal{true} 10 Add i to the end of chain 11 i\leftarrow{\pi}_{i} 12 Reversely add elements in chain to the end of \mathcal{L}_{\textnormal{DFS}} 13 Reverse the node order in \mathcal{L}_{\textnormal{DFS}} 14 return \left\{{\pi}_{u}|u\in V\setminus{S}\right\} , \mathcal{L}_{\textnormal{DFS}} Algorithm 1 RandomForest (G,S) III-E 1 RandomForest Based on Wilson’s algorithm [ 31 ] , Algorithm 1 iteratively simulates loop-erased random walks to sample spanning forests with root set S . Starting from a node, each walk comprises two phases: simulation of a random walk (Lines 1 - 1 ) and erasure of loops within the walk path (Lines 1 - 1 ). During loop erasure, nodes are accessed in the order of a chain in the spanning forest. Different from Wilson’s algorithm, Algorithm 1 properly maintains the accessed order of nodes (Lines 1 - 1 ), resulting in a reverse DFS order \mathcal{L}_{\textnormal{DFS}} on the spanning forest. This maintenance stems from the need of ForestDelta and ForestCFCM for both traversing from each node u\in V\setminus{S} to its root. By iterating over \mathcal{L}_{\textnormal{DFS}} , the maximum number of visits for each node can be reduced from \tau to 1 , where \tau denotes the diameter of graph. The time complexity of RandomForest is given in Lemma III.7 . Lemma III.7 For a graph with root set S , the upper bound of time complexity for Algorithm 1 is O\big(\mathrm{Tr}\big({\left(\bm{I}-\bm{P}_{-S}\right)}^{-1}\big)\big) . For a real-world graph with n nodes, this form can be expressed as \tilde{O}(n) , where \tilde{O}(\cdot) omits poly-logarithmic factors. Proof: The time complexity of RandomForest is dominated by the total number of visits to nodes during loop-erased random walks. In the first iteration of walk starting from node i , the expected number of visits to unvisited nodes is {\left(\bm{I}-\bm{P}_{-S}\right)}^{-1}_{{i}{i}} [ 43 ] . According to Wilson’s algorithm [ 31 ] , the sampling distribution is invariant to the order of source nodes, allowing any strategy of selecting the first starting node. Summing over all nodes gives the upper bound \mathrm{Tr}\big({\left(\bm{I}-\bm{P}_{-S}\right)}^{-1}\big) . For real-world graphs, \mathrm{Tr}\big({\left(\bm{I}-\bm{P}_{-S}\right)}^{-1}\big) is bounded by K+H_{s} for any s\in S [ 44 ] , where K denotes Kemeny’s constant and H_{s} denotes absorbing centrality. Both of them scale nearly linearly with n in scale-free networks [ 45 , 46 ] . Given real-world graphs exhibit scale-free [ 47 ] and small-world [ 48 ] properties, the complexity reduces to \tilde{O}(n) . ∎ Input : G=(V,E) : an undirected n -node graph; S\subset V : the node subset; \epsilon : an error parameter Output : \Delta^{\prime}(u,S) : the margin for node u\in V\setminus{S} w\leftarrow\left\lceil 24(\nicefrac{{\epsilon}}{{7}})^{-2}\log n\right\rceil , r\leftarrow{2(\nicefrac{{\epsilon}}{{15}})^{-2}\tau^{2}d_{\max}^{2\tau+2}(S)\log(2n)} 1 {\tilde{\mathcal{N}}}_{u,S}^{{a}\to{b}}\leftarrow 0 for u\in V\setminus{S} and \left(a,b\right)\in E 2 Construct matrix \bm{W}\in\mathbb{R}^{w\times\left|V\setminus{S}\right|} by Lemma III.4 3 \mathcal{L}_{\textnormal{BFS}}\leftarrow the list of nodes visited in BFS order from S 4 for r^{\prime}=1,2,\dots,\left\lceil\log_{2}r\right\rceil do 5 for i=1,2,\dots,2^{r^{\prime}} do in parallel 6 \left\{{\pi}_{v}|v\in V\setminus{S}\right\},\mathcal{L}_{\textnormal{DFS}}\leftarrow RandomForest (G,S) 7 foreach u\in\mathcal{L}_{\textnormal{DFS}} do 8 Update \sum_{v\in V\setminus{S}}\bm{W}_{{j}{v}}{\tilde{\mathcal{N}}}_{v,S}^{{u}\to{{\pi}_{u}}} for j=1,2,\dots,w 9 Update {\tilde{\mathcal{N}}}_{u,S}^{{u}\to{{\pi}_{u}}} 10 // Estimator of \bm{W}\bm{L}_{-{S}}^{-1} \bm{Y}\in\mathbb{R}^{w\times\left|V\setminus{S}\right|}\leftarrow arbitrary value 11 foreach u\in\mathcal{L}_{\textnormal{BFS}} do 12 \bm{Y}_{{j}{u}}\leftarrow\overline{\varPhi}_{\bm{e}_{j}^{\top}\bm{W},S}(u) for j=1,2,\dots,w 13 z_{u}\leftarrow\overline{\Phi}_{u,S}(u) // Estimator of \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} \Delta^{\prime}(u,S)\leftarrow z_{u}^{-1}\left\|\bm{Y}\bm{e}_{u}\right\|^{2} for u\in V\setminus{S} 14 Compute error bound \epsilon^{\prime}_{u} for \Delta^{\prime}(u,S) by Lemma III.6 15 if {\epsilon^{\prime}_{u}}\leq\epsilon(\Delta^{\prime}(u,S)-\epsilon^{\prime}_{u}) for u\in V\setminus S then break 16 return \left\{\Delta^{\prime}(u,S)=z_{u}^{-1}\left\|\bm{Y}\bm{e}_{u}\right\|^{2}\big|u\in V\setminus{S}\right\} Algorithm 2 ForestDelta (G,S,\epsilon) III-E 2 ForestDelta Given a graph G=(V,E) , a node subset S , and an error parameter \epsilon , Algorithm 2 estimates \Delta(u,S)=\frac{\bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-2}\bm{e}_{u}}{\bm{e}_{u}^{\top}\bm{L}_{-{S}}^{-1}\bm{e}_{u}} for u\in V\setminus{S} . To achieve this, ForestDelta samples rooted spanning forests of G (Lines 2 - 2 ). To estimate the numerator and denominator of \Delta(u,S) , ForestDelta efficiently maintains counters of different sampled forests (Lines 2 - 2 ) via DFS order \mathcal{L}_{\textnormal{DFS}} . Based on these counters, ForestDelta computes the unbiased estimators described in Sections III-A and III-B along BFS order. To obtain its relative error bound, we employ Hoeffding’s inequality. Lemma III.8 (Hoeffding’s inequality) Let x_{1},x_{2},\dots,x_{n} be n independent random variables that satisfy a\leq x_{i}\leq b for i=1,2,\dots,n . Let x=\sum_{i=1}^{n}x_{i} , then for any \epsilon>0 , \Pr\left(\left|x-\mathbb{E}\left[x\right]\right|\geq\epsilon\right)\leq 2\exp\left\{-\frac{2\epsilon^{2}}{n\left(b-a\right)^{2}}\right\}. Next, Lemma III.9 provides the relative error bound of ForestDelta . Lemma III.9 For an undirected graph G and the error parameter \epsilon , if the sample size r satisfies r\geq 2(\nicefrac{{\epsilon}}{{15}})^{-2}\tau^{2}d_{\max}^{2\tau+2}(S)\log(2n), (8) Algorithm 2 returns \Delta^{\prime}(u,S)\approx_{\epsilon}\Delta(u,S) for u\in V\setminus S with probability of 1-\nicefrac{{1}}{{n}} . Proof: We bound the denominator \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} and numerator \big(\bm{L}_{-{S}}^{-2}\big)_{{u}{u}} of \Delta(u,S) separately. For \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} , its lower bound d_{u}^{-1} follows from Neumann series expansion of d_{u}^{-1}\big(\bm{I}-\bm{P}_{-S}\big)^{-1}_{{u}{u}} . Since the upper bound of \big|\overline{\Phi}_{u,S}(u)\big| is \tau , applying Hoeffding’s inequality with sample size with ( 8 ) yields: \overline{\Phi}_{u,S}(u)\approx_{\epsilon/3}\big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}}. (9) For the numerator \big(\bm{L}_{-{S}}^{-2}\big)_{{u}{u}}=\left\|\bm{L}_{-{S}}^{-1}\bm{e}_{u}\right\|^{2} , we first apply Lemma III.4 for dimension reduction, which boils down to estimate terms of \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{v}} . Similar to that of \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} , the lower bound d_{\max}^{-\tau-1}(S) for \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{v}} combined with Hoeffding’s inequality and ( 8 ) gives: \overline{\Phi}_{u,S}(v)\approx_{\epsilon/15}\big(\bm{L}_{-{S}}^{-1}\big)_{{u}{v}}. (10) Combining ( 9 ) and ( 10 ) with reduced dimension w\geq 24(\epsilon/7)^{-2}\log n , we obtain \frac{|\Delta^{\prime}(u,S)-\Delta(u,S)|}{\Delta(u,S)}\leq\frac{(1+\epsilon/15)^{2}(1+\epsilon/7)}{1-\epsilon/3}-1\leq\epsilon for any 0<\epsilon<1 , completing the proof. ∎ Combining Lemmas III.7 and III.9 , we can easily derive the performance of ForestDelta as Lemma III.10 . Lemma III.10 For a realistic graph G with n nodes, the time complexity of Algorithm 2 is \tilde{O}(\epsilon^{-2}n\tau^{2}d_{\max}^{2\tau+2}(S)) . Algorithm 2 returns \Delta^{\prime}(u,S)\approx_{\epsilon}\Delta(u,S) for u\in V\setminus S with probability of 1-\nicefrac{{1}}{{n}} . Input : G=(V,E) : an undirected n -node graph; k\ll n : the capacity of node set; \epsilon : an error parameter Output : S_{k} : A subset of V with \left|S_{k}\right|=k s\leftarrow\argmax_{u\in V}d_{u} , r\leftarrow{18\epsilon^{-2}\tau^{2}d_{s}^{2}(1-\nicefrac{{1}}{{n}})^{-4}\log(2n)} 1 {\tilde{\mathcal{N}}}_{u,\left\{s\right\}}^{{a}\to{b}}\leftarrow 0 for u\in V\setminus{\left\{s\right\}} and \left(a,b\right)\in E 2 \mathcal{L}_{\textnormal{BFS}}\leftarrow the list of nodes visited in BFS order from s 3 for r^{\prime}=1,2,\dots,\left\lceil\log_{2}r\right\rceil do 4 for i=1,2,\dots,2^{r^{\prime}} do in parallel 5 \left\{{\pi}_{v}|v\in V\setminus{\left\{s\right\}}\right\},\mathcal{L}_{\textnormal{DFS}}\leftarrow RandomForest (G,\left\{s\right\}) 6 foreach u\in\mathcal{L}_{\textnormal{DFS}} do 7 Update {\tilde{\mathcal{N}}}_{u,\left\{s\right\}}^{{u}\to{{\pi}_{u}}} and \sum_{v\in V\setminus{\left\{s\right\}}}{\tilde{\mathcal{N}}}_{v,\left\{s\right\}}^{{u}\to{{\pi}_{u}}} 8 foreach u\in\mathcal{L}_{\textnormal{BFS}} do 9 // Estimator of \bm{L}^{\dagger}_{{u}{u}} x_{u}\leftarrow\overline{\Phi}_{u,\left\{s\right\}}(u)-\frac{2}{n}\overline{\varPhi}_{\bm{1},\left\{s\right\}}(u) x_{s}\leftarrow 0 10 Compute additive error bound \epsilon^{\prime}_{u} for x_{u} by Lemma III.6 11 if \epsilon^{\prime}_{u}\leq\epsilon(x_{u}-\epsilon^{\prime}_{u}) then break 12 S_{1}\leftarrow\left\{\argmin_{u\in V}\left\{x_{u}\right\}\right\} 13 for i=1,2,\dots,k-1 do 14 \left\{\Delta^{\prime}(u,S_{i})|u\in V\setminus{S_{i}}\right\}\leftarrow ForestDelta (G,S_{i},\epsilon) 15 u^{*}\leftarrow\argmax_{u\in V\setminus{S_{i}}}\left\{\Delta^{\prime}(u,S_{i})\right\} 16 S_{i+1}\leftarrow S_{i}\cup\left\{u^{*}\right\} 17 return S_{k} Algorithm 3 ForestCFCM (G,k,\epsilon) III-E 3 ForestCFCM Given an n -node graph G , an integer k\ll n , and an error parameter \epsilon , Algorithm 3 iteratively adds nodes to the returning set S based on greedy selection. In the first iteration, the node with minimum CFCC is chosen (Lines 3 - 3 ). To estimate CFCC for each node, ForestCFCM also samples rooted spanning forests (Lines 3 - 3 ). Using counters for sampled forests, ForestCFCM calculates the unbiased estimator described in Section III-C via BFS order (Lines 3 - 3 ). After obtaining the first node, ForestCFCM repeatedly invokes ForestDelta to estimate \Delta(u,S) for u\in V\setminus{S} , selecting node u^{*} with maximum \Delta^{\prime}(u,S) . Theorem III.11 analyzes the performance of ForestCFCM . Note that this nearly-linear time complexity is conservative due to Lemma III.6 . Theorem III.11 For a realistic graph G with n nodes, the time complexity for Algorithm 3 is \tilde{O}(k\epsilon^{-2}n\tau^{2}d_{\max}^{2\tau+2}) . Algorithm 3 returns S_{k} as the approximate solution of CFCM that satisfies \displaystyle(1+\epsilon)\mathrm{Tr}\big(\bm{L}_{-{u^{*}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S_{k}}}^{-1}\big) \displaystyle\geq \displaystyle\big(1-\frac{k}{k-1}\frac{1}{\mathrm{e}}-\epsilon\big)\big((1+\epsilon) \displaystyle\mathrm{Tr}\big(\bm{L}_{-{u^{*}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big)\big), with probability of 1-\nicefrac{{1}}{{n}} , where u^{*}\triangleq\argmin_{u\in V}\bm{L}^{\dagger}_{{u}{u}},\ S^{*}\triangleq\argmin_{S\subset V,\left|S\right|=k}\mathrm{Tr}\big(\bm{L}_{-{S}}^{-1}\big). Proof: The time complexity and error guarantee follow directly from the lower bound \bm{L}^{\dagger}_{{u}{u}}\geq d_{\max}^{-1}(1-\nicefrac{{1}}{{n}})^{2} [ 49 ] as well as Lemmas III.7 and III.10 . Plugging Lemma III.10 into the supermodularity of \mathrm{Tr}\big(\bm{L}_{-{S}}^{-1}\big) , we derive for any iteration i : \mathrm{Tr}\big(\bm{L}_{-{S_{i}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S_{i+1}}}^{-1}\big)\geq\frac{1-\epsilon}{k}\left(\mathrm{Tr}\big(\bm{L}_{-{S_{i}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big)\right). Recursive application yields: \displaystyle\mathrm{Tr}\big(\bm{L}_{-{S_{k}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big) \displaystyle\leq \displaystyle\big(1-\frac{1-\epsilon}{k}\big)^{k-1}\big(\mathrm{Tr}\big(\bm{L}_{-{S_{1}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big)\big) \displaystyle\leq \displaystyle\big(\frac{k}{k-1}\frac{1}{\mathrm{e}}+\epsilon\big)\big(\mathrm{Tr}\big(\bm{L}_{-{S_{1}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big)\big). Combining this with \mathrm{Tr}\big(\bm{L}_{-{S_{1}}}^{-1}\big)\leq(1+\epsilon)\mathrm{Tr}\big(\bm{L}_{-{u^{*}}}^{-1}\big) completes the proof. ∎ IV Algorithm Based on Schur Complement To address the scalability and accuracy limitations of ForestCFCM in large networks, we present an enhanced algorithm SchurCFCM . The key motivation lies in leveraging the Schur complement to introduce an auxiliary root set T . By analyzing the Laplacian submatrix \bm{L}_{-{S\cup T}}^{-1} , we observe two advantages. First, the entrywise monotonicity of \bm{L}_{-{S}}^{-1} [ 29 ] ensures reduced complexity of RandomForest . Second, \bm{L}_{-{S\cup T}}^{-1} exhibits stronger diagonal dominance compared to \bm{L}_{-{S}}^{-1} , which enhances approximation accuracy. This section proceeds as follows. We first introduce the concept of Schur complement to improve sampling efficiency by leveraging higher-degree nodes in T (Lemma IV.3 ). Next, we establish connections between the Schur complement and rooted probabilities in spanning forests (Lemma IV.2 ), enabling unbiased estimation of the Schur complement. We then derive spectral sparsification guarantees (Lemma IV.4 ) to ensure accurate approximation with reduced complexity. Finally, we integrate these innovations into SchurCFCM , proving its complexity and approximation guarantee (Theorem IV.7 ). IV-A Schur Complement and Its Properties Definition IV.1 (Schur complement) For a square matrix \bm{M} , we can adjust its index order and rewrite \bm{M} in block form as \bm{M}=\begin{pmatrix}\bm{M}_{{U}{U}}&\bm{M}_{{U}{T}}\\ \bm{M}_{{T}{U}}&\bm{M}_{{T}{T}}\end{pmatrix} . The Schur complement of \bm{M} onto index subset T is then defined as \mathcal{S}_{\scriptscriptstyle T}(\bm{M})\triangleq\bm{M}_{{T}{T}}-\bm{M}_{{T}{U}}\bm{M}_{{U}{U}}^{-1}\bm{M}_{{U}{T}} . For an undirected graph G=(V,E) with non-empty node subsets S\subset V and T\subset V\setminus{S} , we denote V\setminus{(S\cup T)} as U . Then \bm{L}_{-{S}}^{-1} can be represented as [ 50 ] : \small\bm{L}_{-{S}}^{-1}=\begin{pmatrix}\bm{L}_{{U}{U}}^{-1}+\bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top}&\bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\\ \big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top}&\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\end{pmatrix}, (11) where \bm{F} denotes the matrix -\bm{L}_{{U}{U}}^{-1}\bm{L}_{{U}{T}} . Equation ( 11 ) shows that the computation of \bm{L}_{-{S}}^{-1} can be transformed into calculations involving \bm{L}_{{U}{U}}^{-1} , \bm{F} , and \big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1} . While \bm{L}_{{U}{U}}^{-1} can be estimated by sampling spanning forests with root set S\cup T , we will demonstrate that \bm{F} and \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can also be represented by quantities related to random spanning forests. First, we derive the connection between \bm{F} and rooted probability. Lemma IV.2 For random spanning forests of graph G with root set S\cup T , let \Pr\left(\rho_{u}={t}\right) denote the probability that u\in U belongs to the tree whose root is t\in T . Then we have \bm{F}_{{u}{t}}=-\bm{e}_{u}^{\top}\bm{L}_{{U}{U}}^{-1}\bm{L}_{{U}{T}}\bm{e}_{t}=\Pr\left(\rho_{u}={t}\right). (12) Proof: Following the interpretation of absorbing random walk [ 51 ] , \bm{F}_{{u}{t}} equals the probability that a walk starting at u is absorbed at t\in T . In the initial round of loop-erased random walk from node u , the walk behaves identically to an absorbing random walk with target set T . By Wilson’s algorithm [ 31 ] , the sampling distribution is invariant to the order of source nodes, thus \bm{F}_{{u}{t}}=\Pr\left(\rho_{u}={t}\right) holds for all u\in U . ∎ Motivated by Lemma IV.2 , we define an unbiased estimator of \bm{F}_{{u}{t}} . Let \tilde{\mathcal{N}}(S\cup T) be the number of sampled spanning forests with root set S\cup T , and {\tilde{\mathcal{N}}}\left(\rho_{u}={t}\right) denote the number of these forests where node u is rooted at t\in T . Then {\tilde{\mathcal{N}}}\left(\rho_{u}={t}\right)/\tilde{\mathcal{N}}(S\cup T) serves as an unbiased estimator of \bm{F}_{{u}{t}} . Next, we address the approximation of \big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\in\mathbb{R}^{\left|T\right|\times\left|T\right|} . Given that \left|T\right|\ll\left|V\right| is still relatively small, we can efficiently compute the inverse matrix if \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) is obtained. To achieve this, we first provide a relationship between \mathcal{S}_{\scriptscriptstyle T}(\bm{L}) and the Laplacian matrix of another graph, then extend this relationship to the case of \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) . For a graph G=(V,E) with non-empty node subset T\subset V , the Schur complement \mathcal{S}_{\scriptscriptstyle T}(\bm{L}) is also the Laplacian matrix of a weighted graph denoted as \mathcal{S}_{\scriptscriptstyle T}(G) , whose node set is precisely T [ 52 ] . Regarding the Laplacian submatrix \bm{L}_{-{S}} , we establish a connection between \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) and \mathcal{S}_{\scriptscriptstyle(S\cup T)}(G) . Lemma IV.3 For a graph G=(V,E) with non-empty node subsets S\subset V and T\subset V\setminus{S} , the Schur complement of \bm{L}_{-{S}} onto T is equivalent to the Laplacian submatrix of \mathcal{S}_{\scriptscriptstyle(S\cup T)}(G) : \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})=\big(\mathcal{S}_{\scriptscriptstyle(S\cup T)}(\bm{L})\big)_{\scriptscriptstyle-S}. Proof: From [ 52 ] , \mathcal{S}_{\scriptscriptstyle(S\cup T)}(\bm{L}) is the Laplacian matrix of weighted graph \mathcal{S}_{\scriptscriptstyle(S\cup T)}(G) , which can be rewritten as \mathcal{S}_{\scriptscriptstyle(S\cup T)}(\bm{L})=\bm{L}_{{(S\cup T)}{(S\cup T)}}-\bm{L}_{{(S\cup T)}{U}}\bm{L}^{-1}_{{U}{U}}\bm{L}_{{U}{(S\cup T)}}. (13) Additionally, \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can also be represented as \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})=\bm{L}_{{T}{T}}-\bm{L}_{{T}{U}}\bm{L}^{-1}_{{U}{U}}\bm{L}_{{U}{T}}. (14) Combining ( 13 ) with ( 14 ), we observe that \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can be obtained from \mathcal{S}_{\scriptscriptstyle(S\cup T)}(\bm{L}) by removing elements with row indices or column indices in set S , completing the proof. ∎ According to Definition IV.1 , \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can also be represented as \bm{L}_{{T}{T}}+\bm{L}_{{T}{U}}\bm{F} . Combining this expression with Lemma IV.2 , the entry (i,j) of \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can be rewritten as \small\bm{e}_{i}^{\top}\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\bm{e}_{j}=\begin{cases}\bm{L}_{{i}{i}}-\sum_{\left(u,i\right)\in E}\Pr\left(\rho_{u}={i}\right)&i=j\\ \bm{L}_{{i}{j}}-\sum_{\left(u,i\right)\in E}\Pr\left(\rho_{u}={j}\right)&i\neq j\end{cases}. (15) By integrating Lemma IV.2 with ( 11 ) and ( 15 ), we finally demonstrate that \bm{L}_{-{S}}^{-1} can be estimated by sampling spanning forests with root set S\cup T , incorporating the additional approximation of rooted probabilities. Lemma III.7 suggests that replacing root set S with S\cup T enhances the efficiency of forest sampling. IV-B Algorithm Design and Analyses Based on the preceding analyses, we propose a more efficient algorithm SchurCFCM for solving CFCM, which is depicted in Algorithm 5 . In each subsequent iteration, SchurCFCM invokes SchurDelta , as shown in Algorithm 4 . Both of these algorithms utilize RandomForest to sample random spanning forests, which is illustrated in Algorithm 1 . Input : G=(V,E) : an undirected graph; S\subset V : the node subset; T\subset V\setminus{S} : the additional root set; \epsilon : an error parameter Output : \Delta^{\prime}(u,S) : the margin for node u\in V\setminus{S} U\leftarrow V\setminus{(S\cup T)} 1 w\leftarrow\left\lceil 24(\nicefrac{{\epsilon}}{{7}})^{-2}\log n\right\rceil , r\leftarrow{8(\nicefrac{{\epsilon}}{{15}})^{-2}\tau^{2}d_{\max}^{2\tau+2}(S\cup T)\log(2n)} 2 {\tilde{\mathcal{N}}}_{u,S\cup T}^{{a}\to{b}}\leftarrow 0 for u\in U and \left(a,b\right)\in E 3 Construct \bm{W}\in\mathbb{R}^{w\times\left|U\right|} and \bm{Q}\in\mathbb{R}^{w\times\left|T\right|} by Lemma III.4 4 \mathcal{L}_{\textnormal{BFS}}\leftarrow the list of nodes visited in BFS order from S\cup T 5 for r^{\prime}=1,2,\dots,\left\lceil\log_{2}r\right\rceil do 6 for i=1,2,\dots,2^{r^{\prime}} do in parallel 7 \left\{{\pi}_{u}|u\in U\right\},\mathcal{L}_{\textnormal{DFS}}\leftarrow RandomForest (G,S\cup T) 8 foreach u\in\mathcal{L}_{\textnormal{DFS}} do 9 Update \sum_{v\in U}\bm{W}_{{j}{v}}{\tilde{\mathcal{N}}}_{v,S\cup T}^{{u}\to{{\pi}_{u}}} for j=1,2,\dots,w 10 Update {\tilde{\mathcal{N}}}_{u,S\cup T}^{{u}\to{{\pi}_{u}}} \tilde{\bm{F}}_{{u}{t}}\leftarrow{\tilde{\mathcal{N}}}\left(\rho_{u}={t}\right)/\tilde{\mathcal{N}}(S\cup T) for u\in U,v\in T 11 construct \tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) by ( 15 ) 12 \bm{Y}\in\mathbb{R}^{w\times\left|V\setminus{S}\right|}\leftarrow arbitrary value 13 foreach u\in\mathcal{L}_{\textnormal{BFS}} do 14 \bm{Y}_{{j}{u}}\leftarrow\overline{\varPhi}_{\bm{e}_{j}^{\top}\bm{W},S\cup T}(u)+\bm{e}_{j}^{\top}(\bm{W}\tilde{\bm{F}}+\bm{Q})\big(\tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\tilde{\bm{F}}\bm{e}_{u} for j=1,2,\dots,w 15 z_{u}\leftarrow\overline{\Phi}_{u,S\cup T}(u)+\bm{e}_{u}^{\top}\tilde{\bm{F}}\big(\tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\tilde{\bm{F}}\bm{e}_{u} 16 \bm{Y}\bm{e}_{t}\leftarrow(\bm{W}\tilde{\bm{F}}+\bm{Q})\big(\tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{e}_{t} for t\in T 17 z_{t}\leftarrow\bm{e}_{t}^{\top}\big(\tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{e}_{t} for t\in T 18 \Delta^{\prime}(u,S)\leftarrow z_{u}^{-1}\left\|\bm{Y}\bm{e}_{u}\right\|^{2} for u\in V\setminus{S} 19 Compute error bound \epsilon^{\prime}_{u} for \Delta^{\prime}(u,S) by Lemma III.6 20 if {\epsilon^{\prime}_{u}}\leq\epsilon(\Delta^{\prime}(u,S)-\epsilon^{\prime}_{u}) for u\in V\setminus S then break 21 return \left\{\Delta^{\prime}(u,S)=z_{u}^{-1}\left\|\bm{Y}\bm{e}_{u}\right\|^{2}\big|u\in V\setminus{S}\right\} Algorithm 4 SchurDelta (G,S,T,\epsilon) IV-B 1 SchurDelta While SchurDelta shares similarities with ForestDelta in estimating \Delta(u,S) , it additionally accepts the additional root set T . Therefore, the root set of sampled spanning forest becomes S\cup T . Given that \bm{L}_{-{S}}^{-1} has been rewritten as ( 11 ), we need to approximate the matrix of rooted probability \tilde{\bm{F}} , which can be efficiently maintained during the sampling process. Furthermore, we estimate the Schur complement \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) based on \tilde{\bm{F}} (Line 4 ). As \bm{L}_{-{S}}^{-1} has been represented in block form, we finally calculate the estimated value of \Delta(u,S) for u\in U and u\in T respectively. In order to reduce the sample size r without affecting the theoretical guarantee, we still split it into \left\lceil\log_{2}r\right\rceil batches, utilizing Lemma III.6 for possible early termination. To analyze the theoretical accuracy of SchurDelta , we first introduce the following lemma [ 53 ] . Lemma IV.4 Let {\tilde{G}}^{(i)} denote the {i}^{\rm{th}} random multi-subgraph of G with n nodes, where i=1,2,\dots,r . Each generated edge \left(u,v\right) in {\tilde{G}}^{(i)} has weight \nicefrac{{1}}{{r}} . Let \tilde{G} be the weighted graph obtained by summing the graphs {\tilde{G}}^{(i)} . For edge \left(a,b\right) in \tilde{G} , its weight is equivalent to the sum of weight of every edge \left(a,b\right) in {\tilde{G}}^{(i)} . If \tilde{G} is an unbiased estimator of G and the weight of any edge \left(a,b\right)\in{\tilde{G}}^{(i)} is less than \frac{\epsilon^{2}}{R{({a},{b})}\log n} , then \tilde{G} is an \epsilon -spectral sparsifier of G with high probability. In other words, \bm{x}^{\top}\tilde{\bm{L}}\bm{x}\approx_{\epsilon}\bm{x}^{\top}\bm{L}\bm{x} holds for any real vector \bm{x} , where \tilde{\bm{L}} and \bm{L} are Laplacian matrices of \tilde{G} and G , respectively. Next, the relative error guarantee of SchurDelta is given in Lemma IV.5 . Lemma IV.5 For an undirected graph G and the error parameter \epsilon , if the sample size r satisfies r\geq 8(\nicefrac{{\epsilon}}{{15}})^{-2}\tau^{2}d_{\max}^{2\tau+2}(S\cup T)\log(2n), (16) Algorithm 4 returns \Delta^{\prime}(u,S)\approx_{\epsilon}\Delta(u,S) for u\in V\setminus S with probability of 1-\nicefrac{{1}}{{n}} . Proof: We establish the relative error guarantee through three key steps. Step 1: Spectral Sparsification of Schur Complement. From Lemma IV.4 , an \nicefrac{{\epsilon}}{{15}} -spectral sparsifier \tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) of \mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}}) can be constructed with high probability when the sample size satisfies ( 16 ). This follows because: (i) Edge weights in random subgraphs are bounded by \frac{d_{\max}(S\cup T)}{r} via ( 15 ), (ii) Maximum resistance distance R{({a},{b})}\leq\tau ensures that edge weights meet the condition \frac{(\nicefrac{{\epsilon}}{{15}})^{2}}{R{({a},{b})}\log n}\geq\frac{d_{\max}(S\cup T)}{r} . Step 2: Denominator Estimation. Equation ( 11 ) decomposes the denominator \big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}} into three terms:. \displaystyle\big(\bm{L}_{-{S}}^{-1}\big)_{{u}{u}}= \displaystyle\big(\bm{L}_{{U}{U}}^{-1}\big)_{{u}{u}}+\big(\bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top}\big)_{{u}{u}} \displaystyle+\big(\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\big)_{{u}{u}}. For the first term, the sample size satisfying ( 16 ) yields \overline{\Phi}_{u,S\cup T}(u)\approx_{\epsilon/3}\big(\bm{L}_{{U}{U}}^{-1}\big)_{{u}{u}} by Lemma III.10 . For the second term, let X=\big(\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\big)_{{t}{t}} if u roots at t\in T . Then \mathbb{E}[X]=\big(\bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top}\big)_{{u}{u}} and X\leq(1+\nicefrac{{\epsilon}}{{3}})\tau via spectral sparsification. Applying Lemma III.8 with ( 16 ) yields \big(\tilde{\bm{F}}\big(\tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\tilde{\bm{F}}^{\top}\big)_{{u}{u}}\approx_{\nicefrac{{\epsilon}}{{3}}}\big(\bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top}\big)_{{u}{u}}. The third term directly follows from Lemma IV.4 . Step 3: Numerator Estimation. The numerator \|\bm{L}_{-{S}}^{-1}\bm{e}_{u}\|^{2} is estimated via Lemma III.4 . By ( 11 ), this estimation boils down to estimating non-diagonal elements of \bm{L}_{{U}{U}}^{-1} , \big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1} , \bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1} and \bm{F}\big(\mathcal{S}_{\scriptscriptstyle T}(\bm{L}_{-{S}})\big)^{-1}\bm{F}^{\top} , which are similar with aforementioned diagonal ones, except for two differences: (i) Upper bound (1+\nicefrac{{2\epsilon}}{{15}})\tau of \tilde{\mathcal{S}}_{\scriptscriptstyle T}(\bm{L}_{-{S}})_{{t_{1}}{t_{2}}} derived from spectral sparsification, (ii) Lower bound d_{\max}^{-\tau-1}(S\cup T) for \big(\bm{L}_{{U}{U}}^{-1}\big)_{{u_{1}}{u_{2}}} derived from Neumann series expansion. Error Composition. Combining these estimations with w\geq 24(\nicefrac{{\epsilon}}{{7}})^{-2}\log n from Lemma III.4 , we have \displaystyle\frac{|\Delta^{\prime}(u,S)-\Delta(u,S)|}{\Delta(u,S)} \displaystyle\leq\frac{(1+\nicefrac{{\epsilon}}{{15}})^{2}(1+\nicefrac{{\epsilon}}{{7}})}{1-\nicefrac{{\epsilon}}{{3}}}-1 \displaystyle\leq\epsilon\quad\text{for }0<\epsilon<1. Thus, \Delta^{\prime}(u,S)\approx_{\epsilon}\Delta(u,S) holds with probability 1-\nicefrac{{1}}{{n}} . ∎ Finally, the performance of SchurDelta is analyzed: Lemma IV.6 For a graph G , the time complexity for Algorithm 4 is O\big(\mathcal{T}\big) , where \displaystyle\mathcal{T}=\ \displaystyle\epsilon^{-2}\tau^{2}d_{\max}^{2\tau+2}(S\cup T)\log n\mathrm{Tr}\big(\big(\bm{I}-\bm{P}_{-(S\cup T)}\big)^{-1}\big) \displaystyle+\epsilon^{-2}n\log n. Specifically, if G is a real-world graph, this upper bound can be expressed as \tilde{O}(\epsilon^{-2}n\tau^{2}) . Proof: Similar to the proof of Lemma III.10 , we omit analyzing the time complexity of SchurDelta being O(\mathcal{T}) . We next prove that for real-world graphs, the time complexity of SchurDelta scales nearly linearly in the number of nodes. According to Table I , d_{\max}(S\cup T) denotes the maximum degree after removing nodes in S\cup T . Due to the scale-free property of real-world graphs [ 54 ] , removing hub nodes from T reduces d_{\max}(S\cup T) under the average degree, which is typically a small constant for realistic graphs. The empirical upper bound of d_{\max}(S\cup T) is presented in attribute \left|T*\right| of Table II , validating the above analysis. Meanwhile, the diameter \tau of scale-free graphs is O(\log n) or even O(\log\log n) [ 55 ] . Therefore, \tau^{2}d_{\max}^{2\tau+2}(S\cup T) is very small, even less than a poly-log factor for real graphs, preserving the nearly-linear time complexity of Algorithm 4 . ∎ Despite sharing the approach of sampling spanning forests with ForestDelta , SchurDelta exhibits superior theoretical performance, which stems from the additional root set T . As \big(\bm{I}-\bm{P}_{-(S\cup T)}\big)^{-1}_{{i}{i}} can be rewritten as d_{i}\left(\bm{L}_{-{S\cup T}}^{-1}\right)_{{i}{i}} , The entrywise monotonicity of \bm{L}_{-{S}}^{-1} [ 29 ] greatly reduces the complexity of invoking Algorithm 1 when T contains a few nodes. Meanwhile, \bm{L}_{-{S\cup T}}^{-1} has better diagonal dominance than \bm{L}_{-{S}}^{-1} , leading to better accuracy of ForestDelta . Input : G=(V,E) : an undirected graph; k\ll\left|V\right| : the capacity of node set; c\ll\left|V\right| : the capacity of additional root set; \epsilon : an error parameter Output : S_{k} : A subset of V with \left|S_{k}\right|=k Select c nodes with maximum degree to form T 1 s\leftarrow\argmax_{u\in V}d_{u} , r\leftarrow{18\epsilon^{-2}\tau^{2}d_{s}^{2}(1-\nicefrac{{1}}{{n}})^{-4}\log(2n)} 2 {\tilde{\mathcal{N}}}_{u,\left\{s\right\}}^{{a}\to{b}}\leftarrow 0 for u\in V\setminus{\left\{s\right\}} and \left(a,b\right)\in E 3 \mathcal{L}_{\textnormal{BFS}}\leftarrow the list of nodes visited in BFS order from s 4 for r^{\prime}=1,2,\dots,\left\lceil\log_{2}r\right\rceil do 5 for i=1,2,\dots,2^{r^{\prime}} do in parallel 6 \left\{{\pi}_{v}|v\in V\setminus{\left\{s\right\}}\right\},\mathcal{L}_{\textnormal{DFS}}\leftarrow RandomForest (G,\left\{s\right\}) 7 foreach u\in\mathcal{L}_{\textnormal{DFS}} do 8 Update {\tilde{\mathcal{N}}}_{u,\left\{s\right\}}^{{u}\to{{\pi}_{u}}} and \sum_{v\in V\setminus{\left\{s\right\}}}{\tilde{\mathcal{N}}}_{v,\left\{s\right\}}^{{u}\to{{\pi}_{u}}} 9 foreach u\in\mathcal{L}_{\textnormal{BFS}} do 10 // Estimator of \bm{L}^{\dagger}_{{u}{u}} x_{u}\leftarrow\overline{\Phi}_{u,\left\{s\right\}}(u)-\frac{2}{\left|V\right|}\overline{\varPhi}_{\bm{1},\left\{s\right\}}(u) x_{s}\leftarrow 0 11 Compute additive error bound \epsilon^{\prime}_{u} for x_{u} by Lemma III.6 12 if \epsilon^{\prime}_{u}\leq\epsilon(x_{u}-\epsilon^{\prime}_{u}) then break 13 S_{1}\leftarrow\left\{\argmin_{u\in V}\left\{x_{u}\right\}\right\} 14 for i=1,2,\dots,k-1 do 15 \left\{\Delta^{\prime}(u,S_{i})|u\in V\setminus{S_{i}}\right\}\leftarrow SchurDelta (G,S_{i},T\setminus S_{i},\epsilon) 16 u^{*}\leftarrow\argmax_{u\in V\setminus{S_{i}}}\left\{\Delta^{\prime}(u,S_{i})\right\} 17 S_{i+1}\leftarrow S_{i}\cup\left\{u^{*}\right\} 18 return S_{k} Algorithm 5 SchurCFCM (G,k,\epsilon) IV-B 2 SchurCFCM Due to the leverage of Lemma III.4 , the performance bottleneck stems from SchurDelta . We thus do not introduce Schur complement in Algorithm 5 for ease of implementation. However, it remains necessary to determine the nodes of additional root set T . According to the proof of Lemma III.7 , the upper bound of time complexity for sampling a spanning forest depends on the mean hitting time to S\cup T . Enhanced reachability of T leads to improved efficiency of SchurCFCM . Therefore, we repeatedly select the node with maximum degree in the remaining graph, which is both reasonable and efficient for implementation. The performance of SchurCFCM is characterized in Theorem IV.7 . Similar to the analysis of ForestCFCM , this upper bound of time complexity is also conservative due to the application of Lemma III.6 . Theorem IV.7 For a real-world n -node graph G , the upper bound of the time complexity for Algorithm 5 is \tilde{O}(k\epsilon^{-2}n\tau^{2}d_{\max}^{2\tau+2}) . Algorithm 5 returns S_{k} as the approximate solution of CFCM that satisfies \displaystyle(1+\epsilon)\mathrm{Tr}\big(\bm{L}_{-{u^{*}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S_{k}}}^{-1}\big) \displaystyle\geq \displaystyle\bigg(1-\frac{k}{k-1}\frac{1}{\mathrm{e}}-\epsilon\bigg)\big((1+\epsilon) \displaystyle\mathrm{Tr}\big(\bm{L}_{-{u^{*}}}^{-1}\big)-\mathrm{Tr}\big(\bm{L}_{-{S^{*}}}^{-1}\big)\big) with probability of 1-\nicefrac{{1}}{{n}} , where u^{*}\triangleq\argmin_{u\in V}\bm{L}^{\dagger}_{{u}{u}},\ S^{*}\triangleq\argmin_{S\subset V,\left|S\right|=k}\mathrm{Tr}\big(\bm{L}_{-{S}}^{-1}\big). Proof: The time complexity of ForestCFCM and the relative error guarantee for \bm{L}^{\dagger}_{{u}{u}} follow directly from combining Lemmas III.7 and III.10 . To derive the approximation factor of solving CFCM, we observe that SchurCFCM and ForestCFCM differ only in their iterative subroutine: SchurDelta for the former and ForestDelta for the latter. As both subroutines provide an \epsilon -approximation of \Delta(u,S) , the proof of approximation factor for SchurCFCM mirrors that of ForestCFCM . ∎ V Numerical Experiments V-A Experimental Settings Datasets. Our experiments utilize real-world graph data from KONECT [ 56 ] , SNAP [ 57 ] , and Network Repository [ 58 ] . To ensure fair comparison with previous works, we also conduct experiments on several networks examined in [ 29 ] . For networks that are not originally connected, we perform our experiments on their largest connected components (LCCs). Table II presents relevant information about the LCCs of the studied real-world networks, listed in ascending order by node number. The smallest network contains 1039 nodes, while the largest comprises 6 million nodes. TABLE II: The running time (seconds, s ) of Exact , ApproxGreedy ( Approx ), ForestCFCM and SchurCFCM with various \epsilon on real-world graphs. Network Node Edge \tau \left|T^{*}\right| Running time (seconds) Exact Approx ForestCFCM SchurCFCM \epsilon=0.3 \epsilon=0.2 \epsilon=0.15 \epsilon=0.3 \epsilon=0.2 \epsilon=0.15 Euroroads 1,039 1,305 62 7 4.824 8.491 0.328 0.497 0.825 0.283 0.451 0.709 Hamsterster 2,000 16,097 10 58 33.70 34.43 0.747 1.273 1.993 0.532 0.992 1.659 Facebook 4,039 88,234 8 127 274.6 196.2 2.446 4.321 6.901 1.695 3.448 5.608 GR-QC 4,158 13,428 17 34 298.8 60.41 2.876 5.450 9.008 2.404 4.867 8.246 web-EPA 4,253 8,897 10 43 319.1 32.91 2.631 5.024 8.359 2.216 4.513 7.699 Routeviews 6,474 13,895 9 45 1130 39.88 4.440 8.499 14.21 3.938 8.029 13.65 soc-PagesGov 7,057 89,429 10 113 1455 253.4 6.371 11.88 19.94 5.444 10.33 17.42 HEP-Th 8,638 24,827 18 37 2676 157.4 8.125 15.76 25.50 6.679 13.39 22.76 Astro-Ph 17,903 197,031 14 138 24456 1118 22.10 44.24 74.35 18.73 35.69 59.81 CAIDA 26,475 53,381 17 86 81549 392.4 27.41 53.98 91.53 26.37 50.58 84.81 EmailEnron 33,696 180,811 13 177 161354 1247 48.89 92.60 147.6 39.50 79.86 130.3 Brightkite 56,739 212,945 18 146 – 1694 57.17 98.22 179.0 56.97 97.52 154.3 buzznet 101,163 2,763,066 4 664 – 10121 80.79 126.8 196.0 73.59 126.7 176.2 Livemocha 104,103 2,193,083 6 631 – 12364 83.24 149.8 232.1 81.86 128.7 218.4 WordNet 145,145 656,230 16 205 – 6153 142.6 243.7 383.1 112.4 203.0 333.6 Gowalla 196,591 950,327 16 258 – 8900 180.4 314.8 497.6 149.0 271.8 445.3 com-DBLP 317,080 1,049,866 23 131 – 13022 170.1 290.7 444.1 130.6 241.5 396.9 Amazon 334,863 925,872 47 96 – 19252 200.0 356.7 562.9 172.4 311.2 519.3 Actor 374,511 15,014,839 13 1174 – 100333 270.9 480.7 764.5 215.5 403.1 656.3 Dogster 426,485 8,543,321 11 1174 – 43005 221.3 312.9 445.2 150.2 227.3 372.8 FourSquare 639,014 3,214,986 4 201 – – 318.9 414.6 585.4 266.5 403.4 558.6 Skitter 1,694,616 11,094,209 31 965 – – 585.4 774.0 1064 372.0 487.5 750.2 Flixster 2,523,386 7,918,801 7 945 – – 642.0 835.2 1080 292.7 504.0 755.2 Orkut 2,997,166 106,349,209 9 1462 – – 1104 1576 2223 752.3 1125 1707 Youtube 3,216,075 9,369,874 31 892 – – 1009 1307 1796 618.4 903.4 1376 soc-LiveJournal 5,189,808 48,687,945 23 951 – – 2017 2712 3693 1152 1864 2758 sc-rel9 5,921,786 23,667,162 7 125 – – 1474 2058 2920 969.9 1517 2302 Environment. All experiments are conducted on a Linux server equipped with a 72-core 2.1GHz CPU and 256GB of RAM. We implement ApproxGreedy in Julia, maintaining consistency with [ 29 ] , which relies on a Julia-based Laplacian solver [ 39 ] . Our proposed algorithms and other baseline methods are implemented in C++. Given that all algorithms are pleasingly parallelizable, we execute each experiment using 72 threads. Baselines and Parameters. To demonstrate the superiority of our algorithms, we first implement the state-of-the-art method ApproxGreedy [ 29 ] as a baseline. Since this method also utilizes Lemma III.4 , we set the error parameter \epsilon to be 0.2 , matching ForestCFCM and SchurCFCM . We also implement the greedy algorithm Exact , which calculates \bm{L}^{\dagger} and \Delta(u,S) through matrix inversion. To ensure that our greedy algorithms outperform other heuristic strategies in solving CFCM effectively, we implement two additional heuristic methods: Degree and Top-CFCC . Degree selects k nodes with the largest degrees, while Top-CFCC selects top- k nodes with the largest CFCC of single nodes. While the nodes of additional root set T in SchurCFCM are selected according to maximum degree, we also need to determine the size of additional root set T . When \left|T\right| becomes larger, the time of directly inverting the Schur complement grows cubically. When \left|T\right| becomes smaller, the upper bound of SchurDelta increases due to the growing d_{\max}(T) . Therefore, we attempt to reach a balance between these two factors, setting the size as \left|T^{*}\right|=\argmin_{\left|T\right|}\left\{\big|\left|T\right|-d_{\max}(T)\big|\right\} . Table II presents the value of \left|T^{*}\right| for each tested graph, which is very small due to the scale-free property of real-world graphs. V-B Results on Real-world Networks V-B 1 Efficiency We first evaluate the efficiency of our algorithms. For each graph, we solve CFCM with cardinality constraint k=\left|S\right|=20 . Table II reports the running times of our algorithms and baselines. We present results for both of our algorithms with \epsilon\in\left\{0.3,0.2,0.15\right\} . Note that Exact is infeasible for medium-scale graphs due to time-consuming matrix inversion, while ApproxGreedy is infeasible for large-scale graphs, as its running time exceeds 27 hour. Table II shows that for every real-world graph, both of our algorithms outperform all the baselines in efficiency. Notably, the speed-up of our algorithms over ApproxGreedy is more pronounced on denser graphs, such as buzznet and Actor . This observation aligns with our earlier theoretical analysis that the time complexity of ApproxGreedy is dominated by number of edges rather than number of nodes. Meanwhile, although both of our algorithms share the same theoretical upper bound of time complexity, the running time of SchurCFCM is always lower than that of ForestCFCM . This advantage lies in the introduction of Schur complement, letting SchurCFCM sample spanning forests with more root nodes. During the sampling process, the random walker terminates once hitting the former trajectories. As RandomForest is the most time-consuming part of ForestCFCM and SchurCFCM , the walker of SchurCFCM is easier to terminate, significantly reducing running time. Fig. 1: CFCC C(S) of node set S computed by different algorithms on four tiny-scale graphs: Zebra (a), Karate (b), Cont. USA (c) and Dolphins (d). V-B 2 Effectiveness We next evaluate the effectiveness of our algorithms. For tiny-scale graphs, the optimum solution of CFCM can be obtained by exhaustively examining all \binom{n}{k} selections. We compare the solutions from our algorithms with \epsilon=0.2 and other baselines with the optimum solution on four tiny graphs [ 58 ] : Zebra (23 nodes), Karate (34 nodes), Cont. USA (49 nodes) and Dolphins (62 nodes). Fig. 1 reports the results of different algorithms. As shown by Fig. 1 , the solutions provided by Exact and our proposed algorithms are nearly identical, all very close to the optimum solutions. This indicates that the practical approximation ratios of our algorithms significantly outperform their theoretical guarantees. Furthermore, we observe that the approximation ratio of the state-of-the-art method ApproxGreedy is lower than other methods. A similar phenomenon was reported in [ 29 ] , which may be attributed to the inaccuracy of Laplacian solver for small graphs. Fig. 2: CFCC C(S) of node set S computed by different algorithms on small-scale graphs: Hamsterster (a), web-EPA (b), Routeviews (c), soc-PagesGov (d), Astro-Ph (e) and EmailEnron (f). Fig. 3: CFCC C(S) of node set S by different algorithms on large-scale graphs: Livemocha (a), WordNet (b), Gowalla (c) and com-DBLP (d). We further evaluate the performance of our algorithms against heuristic approaches Degree and Top-CFCC described in Section V-A . These methods are executed along with four greedy algorithms on six small-scale graphs. For large-scale networks where direct computation of CFCC and CFCM becomes infeasible, we employ the conjugate gradient method [ 59 ] to examine approximate solutions, excluding Exact . The results presented in Fig. 2 and Fig. 3 reveal three key observations. First, while ForestCFCM achieves superior effectiveness in initial iterations, its CFCC maximization rate is eventually surpassed by other methods. Second, SchurCFCM consistently delivers the most effective solutions throughout all iterations, benefiting from the Schur complement introduced in Lemma IV.3 . Third, the heuristic method Top-CFCC shows comparable or inferior performance to Degree , suggesting that single-node centrality rankings alone cannot effectively identify crucial node groups. V-C Influence of Varying Error Parameter Our analysis of algorithmic efficiency and solution quality reveals significant sensitivity to the error parameter \epsilon . We systematically investigate this relationship by varying \epsilon within [0.15,0.4] and measuring algorithm performance across multiple real-world networks. The evaluation focuses on two metrics: computational time across different graph sizes and relative differences of maximized CFCC compared to Exact . Fig. 4: Running time of different algorithms with varying error parameter \epsilon on real-world graphs: Euroroads (a), soc-PagesGov (b), EmailEnron (c), com-DBLP (d), Skitter (e) and sc-rel9 (f). V-C 1 Effect on efficiency We first assess the impact of varying error parameter on the efficiency of our algorithms. Fig. 4 demonstrates the computational time scaling of our algorithms with various \epsilon . Both of our algorithms exhibit similar growth patterns that align with the factor \epsilon^{-2} of their complexity. Notably, SchurCFCM shows increasing efficiency advantages at smaller \epsilon values, particularly when \epsilon\leq 0.2 . This enhanced performance further validates the improvements of introducing Schur complement by SchurCFCM , as smaller \epsilon leads to more sampled spanning forests. Fig. 5: Relative difference of different algorithms with varying error parameter \epsilon on small-scale graphs: Facebook (a), GR-QC (b), web-EPA (c), Routeviews (d), HEP-Th (e) and CAIDA (f). V-C 2 Effect on effectiveness We next analyze the impact of varying \epsilon on the effectiveness of our algorithms. The results are presented in Fig. 5 . As displayed in Fig. 5 , SchurCFCM maintains superior CFCC maximization across all tested \epsilon values. Although the relative differences of our algorithms with large \epsilon are not ideal, reducing \epsilon to 0.2 or 0.15 significantly decreases their differences to negligible levels. The observed sensitivity to \epsilon variations demonstrates effective parameter governance in both algorithms, with improvements of solution quality saturating beyond \epsilon=0.2 . VI Related Work Computation of resistance distance. As a fundamental metric, resistance distance has found wide applications in the data management community, such as recommendation systems [ 60 ] and graph embedding systems [ 13 ] . Numerous algorithms have been proposed to compute resistance distance efficiently [ 17 , 18 , 61 , 62 ] . However, these approaches are based on the interpretations of resistance distance expressed in ( 2 ), rather than the marginal gain represented in ( 5 ). Therefore, existing methods for computing resistance distance cannot be directly applied to solving CFCM. Other node selection problems. There exist various importance measures of a group of nodes, based on graph structure [ 63 ] or dynamic processes [ 64 ] . As the criteria for identifying crucial node groups are application-dependent [ 65 ] , many previous studies have focused on selecting k nodes to optimize related quantities. Recently, influence maximization (IM) has garnered wide interest, with information spread as the optimized quantity. However, the predominant processes for information diffusion are independent cascade [ 66 , 5 , 6 , 67 ] and linear threshold [ 68 , 69 ] , both of which differ greatly from the electrical network model. Consequently, existing approaches for IM cannot be transferred to solving CFCM. Discussion of edge selection problems. Beyond node selection, significant efforts have been devoted to the problem of adding k edges connecting to a given node to maximize its centrality. This problem has been studied via diverse centrality measures, including betweenness centrality [ 70 ] , information centrality [ 71 ] and absorbing random-walk centrality [ 72 ] . In contrast to single-node scenarios, the problem of maximizing the centrality of a node group by adding k edges connecting nodes within the group has been studied for only a few centralities, such as group betweenness [ 73 ] . Previous works have not solved the edge selection problem for maximizing CFCC, which presents an opportunity for future research. VII Conclusion For real-world graphs with n nodes, we developed two greedy algorithms to approximately maximize the current flow closeness centrality of node groups with cardinality constraint k\ll n . Our first algorithm, ForestCFCM , is based on spanning forest sampling and leverages an adaptive sampling technique. ForestCFCM exhibits a nearly-linear time complexity with respect to n , outperforming the state-of-the-art method. To further improve efficiency and effectiveness, we proposed our second algorithm SchurCFCM , which additionally utilizes the Schur complement. Both of our greedy algorithms achieve a guaranteed approximation factor of 1-\frac{k}{k-1}\frac{1}{\mathrm{e}}-\epsilon for any error parameter 0<\epsilon<1 . Numerical results demonstrate that both algorithms are significantly faster than the state-of-the-art method, scaling to real-world graphs with 3 million nodes. Notably, SchurCFCM outperforms all other approaches in terms of both efficiency and effectiveness.