Scalable Subgraph Sampling via Resistance Curvature

# Scalable Subgraph Sampling via Resistance Curvature
Source: [https://arxiv.org/html/2609.27209](https://arxiv.org/html/2609.27209)
Tinglve ZhouTianyong HaoYangyang Li††thanks:\*Corresponding author: Yangyang Li\.

###### Abstract

Subgraph sampling reduces the training cost of large\-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges\. We propose a resistance\-curvature\-guided sampling framework built on ERC\-LG, a curvature approximation method for large\-scale graphs\. ERC\-LG combines Johnson\-Lindenstrauss projections with regularized multi\-GPU batched conjugate gradient solvers, avoiding explicit Laplacian pseudoinverse computation and full embedding storage\. The resulting curvature informs node\- and edge\-sampling probabilities for constructing GNN training subgraphs\. Experiments show numerical agreement with pseudoinverse\-based curvature and reduced runtime compared with CG\-only computation\. ERC\-LG\-based sampling variants achieve the highest mean accuracy on six of seven real\-world datasets in downstream node classification\.

###### Index Terms:

Effective Resistance Curvature, JL Projection, batched CG, Subgraph sampling

††address:1School of Artificial Intelligence, South China Normal University
2School of Computer Science, South China Normal University
3Academy of Mathematics and Systems Science, Chinese Academy of Sciences## 1Introduction

Graph neural networks \(GNNs\) face substantial memory and computational costs when trained on large graphs\. Neighborhood\[[8](https://arxiv.org/html/2609.27209#bib.bib1)\], layer\-wise\[[1](https://arxiv.org/html/2609.27209#bib.bib2)\], and subgraph\[[2](https://arxiv.org/html/2609.27209#bib.bib3)\]sampling provide scalable alternatives to full\-graph training\. However, sampling may discard connections important for information propagation, motivating sampling criteria that account for the structural roles of edges\.

Discrete graph curvature provides edge\-level geometric information for distinguishing redundant connections from potential bottlenecks and bridges\. ORG\-sub\[[14](https://arxiv.org/html/2609.27209#bib.bib12)\]uses Ollivier\-Ricci curvature to guide sampling and improve small\-community coverage\. However, it focuses on community analysis rather than GNN training, and its scalability on massive graphs remains unverified\. Moreover, exact Ollivier\-Ricci curvature requires edge\-wise optimal transport computations, making graph\-wide evaluation expensive\.

Our previous work introduced an efficient effective resistance curvature computation scheme\[[7](https://arxiv.org/html/2609.27209#bib.bib10)\]\. Effective resistance curvature \(ERC\) uses effective resistance to capture multipath connectivity without optimal transport\. By replacing Laplacian pseudoinversion with diagonally perturbed matrix inversion, the scheme achieved speedups of up to approximately1,000×1\{,\}000\\times\. It maintained near\-identical curvature values to the pseudoinverse\-based reference and comparable performance to Ollivier\-Ricci curvature in structural discrimination and graph representation learning\. Nevertheless, explicit matrix inversion retains quadratic storage requirements, limiting its applicability to larger graphs\.

To address this bottleneck, we propose an efficient approximation method for large\-scale graphs short for ERC\-LG\. The key idea is to use Johnson–Lindenstrauss \(JL\) projections to reduce the number of linear systems required for resistance estimation\. Regularized multi\-GPU batched CG avoids explicit pseudoinversion, while streaming distance accumulation avoids storing the full embedding\. We further design ERC\-LG\-based sampling methods for GNN training\.

Our main contributions are as follows:

1. 1\)We develop ERC\-LG by adapting JL\-based effective resistance approximation to ERC computation, together with regularized multi\-GPU batched CG and streaming edge\-distance accumulation, avoiding explicit pseudoinverse computation and full embedding storage\.
2. 2\)We design ERC\-LG\-based node and edge sampling methods that incorporate edge\-level geometric information into sampling probabilities for GNN training\-subgraph construction\.
3. 3\)We evaluate numerical agreement, computational efficiency, and downstream node classification\. ERC\-LG\-based sampling variants achieve the highest mean accuracy on six of seven real\-world datasets\.

## 2Related Work

### 2\.1Sampling for Large\-Scale Graph Neural Networks

Existing GNN sampling methods mainly include neighbor sampling, layer\-wise sampling, and subgraph sampling\. GraphSAGE\[[8](https://arxiv.org/html/2609.27209#bib.bib1)\]controls computational cost by sampling a fixed number of neighbors at each layer\. FastGCN\[[1](https://arxiv.org/html/2609.27209#bib.bib2)\]interprets graph convolution as an integral transform and applies layer\-wise importance sampling\. Subgraph sampling instead directly constructs minibatch training graphs\. ClusterGCN\[[2](https://arxiv.org/html/2609.27209#bib.bib3)\]organizes training batches through graph clustering, while GraphSAINT\[[15](https://arxiv.org/html/2609.27209#bib.bib4)\]combines subgraph sampling with normalization corrections to reduce training cost and control sampling bias\. REGNN\[[4](https://arxiv.org/html/2609.27209#bib.bib9)\]combines random\-walk sampling and historical embeddings to enable scalable mini\-batch GNN training\.

### 2\.2Graph Learning with Discrete Curvature

Discrete graph curvature provides geometric information for analyzing and adapting graph structures in representation learning\. Topping et al\.\[[13](https://arxiv.org/html/2609.27209#bib.bib5)\]use curvature\-guided rewiring to address oversquashing\. RicciPool\[[5](https://arxiv.org/html/2609.27209#bib.bib13)\]combines Ollivier\-Ricci flow with spectral clustering for graph pooling\. ORG\-sub\[[14](https://arxiv.org/html/2609.27209#bib.bib12)\]uses Ollivier\-Ricci curvature to improve small\-community coverage, while LC\-sub\[[11](https://arxiv.org/html/2609.27209#bib.bib8)\]employs a 3\-cycle\-based curvature approximation for combinatorial subgraph sampling\. Spielman and Srivastava\[[12](https://arxiv.org/html/2609.27209#bib.bib6)\]approximate effective resistance through random projections and Laplacian solves for spectral sparsification, whereas we adapt this idea to graph\-wide ERC estimation and GNN sampling\. Devriendt and Lambiotte\[[3](https://arxiv.org/html/2609.27209#bib.bib7)\]define node and edge resistance curvatures\. Our previous work accelerates ERC computation through matrix perturbation\[[7](https://arxiv.org/html/2609.27209#bib.bib10)\], while DGSL\-RCF\[[6](https://arxiv.org/html/2609.27209#bib.bib11)\]uses resistance curvature flow for iterative graph refinement\.

## 3Method

We approximate ERC using JL projections and multi\-GPU batched CG, then use the resulting edge geometry to guide node and edge sampling\.

### 3\.1ERC Approximation for Large\-Scale Graphs

#### 3\.1\.1Resistance curvature

For an undirected graphG=\(V,E\)G=\(V,E\)withnnnodes andmmedges, letL=D−A=B⊤​W​BL=D\-A=B^\{\\top\}WB, whereB∈Rm×nB\\in\{R\}^\{m\\times n\}is an oriented incidence matrix andW=diag⁡\(we\)W=\\operatorname\{diag\}\(w\_\{e\}\)contains positive edge weights \(W=IW=Ifor unweighted graphs\)\. Letbu​v=eu−evb\_\{uv\}=e\_\{u\}\-e\_\{v\}, effective resistanceRu​vR\_\{uv\}, node curvaturepup\_\{u\}and edge curvatureκu​v\\kappa\_\{uv\}\[[3](https://arxiv.org/html/2609.27209#bib.bib7)\]are defined as below:

Ru​v\\displaystyle R\_\{uv\}=bu​v⊤​L†​bu​v\.\\displaystyle=b\_\{uv\}^\{\\top\}L^\{\\dagger\}b\_\{uv\}\.\(1\)pu\\displaystyle p\_\{u\}=1−12∑v∈𝒩⁡\(u\)wu​vRu​v,κu​v=2​\(pu\+pv\)Ru​v\.\\displaystyle=1\-\\tfrac\{1\}\{2\}\\sum\_\{v\\in\\mathcal\{N\}\(u\)\}w\_\{uv\}R\_\{uv\},\\quad\\kappa\_\{uv\}=\\frac\{2\(p\_\{u\}\+p\_\{v\}\)\}\{R\_\{uv\}\}\.\(2\)Here,L†L^\{\\dagger\}is the Moore\-Penrose pseudoinverse ofLL, andκu​v\\kappa\_\{uv\}denotes the ERC of edge\(u,v\)\(u,v\)\.

#### 3\.1\.2Johnson\-Lindenstrauss embedding

UtilizingL†​L​L†=L†L^\{\\dagger\}LL^\{\\dagger\}=L^\{\\dagger\}, the effective resistance can be rewritten as a squared embedding distance:

Ru​v=‖bu​v⊤​L†​B⊤​W1/2‖22\.R\_\{uv\}=\\\|b\_\{uv\}^\{\\top\}L^\{\\dagger\}B^\{\\top\}W^\{1/2\}\\\|\_\{2\}^\{2\}\.\(3\)Following\[[12](https://arxiv.org/html/2609.27209#bib.bib6)\], we use JL projections\[[10](https://arxiv.org/html/2609.27209#bib.bib14)\]to approximately preserve such pairwise distances, eliminating the need to store the full set of embedding coordinates\. LetQ∈Rm×KQ\\in\{R\}^\{m\\times K\}have independent entries uniformly sampled from\{±1/K\}\\\{\\pm 1/\\sqrt\{K\}\\\}, and defineY=B⊤​W1/2​QY=B^\{\\top\}W^\{1/2\}Q\. Since each column ofYYlies in the range ofLL, the low\-dimensional embedding and its associated system satisfy

Z=L†​Y,L​Z=L​L†​Y=Y\.Z=L^\{\\dagger\}Y,\\qquad LZ=LL^\{\\dagger\}Y=Y\.\\vskip\-5\.0pt\(4\)Thus, computing the embedding requires solvingKKlinear systems sharing the coefficient matrixLL, without explicitly forming the pseudoinverse\.

#### 3\.1\.3Regularization and Parallel Solution

The coefficient matrixLLin Eq\. \([4](https://arxiv.org/html/2609.27209#S3.E4)\) is singular\. To construct a symmetric positive definite system suitable for standard CG, we follow the diagonal perturbation approach in our prior work\[[7](https://arxiv.org/html/2609.27209#bib.bib10)\]and introduceε\>0\\varepsilon\>0, replacing the original system with

Lε=L\+ε​I,Lε​Zε=Y\.L\_\{\\varepsilon\}=L\+\\varepsilon I,\\qquad L\_\{\\varepsilon\}Z\_\{\\varepsilon\}=Y\.\(5\)Since the columns ofYYlie in the range ofLL,ZεZ\_\{\\varepsilon\}approaches the target embeddingZ=L†​YZ=L^\{\\dagger\}Yasε→0\\varepsilon\\to 0and finite perturbation introduces regularization bias\.

We distribute theKKindependent right\-hand sides across GPUs and perform column\-wise CG\[[9](https://arxiv.org/html/2609.27209#bib.bib15)\]in batches on each device\. Each GPU maintains a local sparse graph copy and evaluates matrix products throughLε​X=L​X\+ε​XL\_\{\\varepsilon\}X=LX\+\\varepsilon X, without explicit inversion\. LetZ^ε\\widehat\{Z\}\_\{\\varepsilon\}denote the approximate embedding computed by CG\. Effective resistances on the original edges are estimated as

R^u​v=∥Z^ε,u,:−Z^ε,v,:∥22\.\\widehat\{R\}\_\{uv\}=\\\|\\widehat\{Z\}\_\{\\varepsilon,u,:\}\-\\widehat\{Z\}\_\{\\varepsilon,v,:\}\\\|\_\{2\}^\{2\}\.\(6\)
After accumulating each batch’s squared\-distance contributions, its workspace is released, avoiding storage of the full embedding\. Finally, contributions from all GPUs are aggregated, and curvature is computed using Eq\. \([2](https://arxiv.org/html/2609.27209#S3.E2)\)\. Algorithm[1](https://arxiv.org/html/2609.27209#alg1)summarizes the procedure\.

Algorithm 1ERC Approximation for Large\-scale Graphs1:Graph

GG, dimension

KK, regularization

ε\\varepsilon, GPUs

PP, batch size

bb, CG tolerance

τ\\tau
2:Edge curvatures

κ^\\widehat\{\\kappa\}
3:Construct sparse

LLand define

Lε​X=L​X\+ε​XL\_\{\\varepsilon\}X=LX\+\\varepsilon X; partition the

KKprojection columns across

PPGPUs

4:forGPU

g=1,…,Pg=1,\\ldots,Pin paralleldo

5:Store local sparse graph operators;

r\(g\)←𝟎∈Rmr^\{\(g\)\}\\leftarrow\\mathbf\{0\}\\in\{R\}^\{m\}
6:foreach assigned column batch

ttof size at most

bbdo

7:Form

Y\(t\)=B⊤​W1/2​Q\(t\)Y^\{\(t\)\}=B^\{\\top\}W^\{1/2\}Q^\{\(t\)\}from streamed independent

Qi​j\(t\)∼Unif\{±1/K\}Q\_\{ij\}^\{\(t\)\}\\sim\\operatorname\{Unif\}\\\{\\pm 1/\\sqrt\{K\}\\\}
8:Solve

Lε​Z^ε\(t\)=Y\(t\)L\_\{\\varepsilon\}\\widehat\{Z\}\_\{\\varepsilon\}^\{\(t\)\}=Y^\{\(t\)\}by batched column\-wise CG to relative residual tolerance

τ\\tau
9:Add this batch’s squared edge distances to

r\(g\)r^\{\(g\)\}in edge blocks, using Eq\. \([6](https://arxiv.org/html/2609.27209#S3.E6)\)

10:Release batch workspace

11:endfor

12:endfor

13:Aggregate

R^←∑gr\(g\)\\widehat\{R\}\\leftarrow\\sum\_\{g\}r^\{\(g\)\}; return

κ^\\widehat\{\\kappa\}using Eq\. \([2](https://arxiv.org/html/2609.27209#S3.E2)\)

### 3\.2Resistance\-Curvature\-Guided Subgraph Sampling

Node sampling and edge sampling are two basic approaches to large\-graph sampling, drawing nodes or edges according to probability distributions\. We use ERC\-LG to construct these distributions and develop curvature\-guided node and edge sampling strategies\.

#### 3\.2\.1Curvature\-guided Node sampling

Higher\-curvature edges often occur in densely interconnected regions\. We aggregate their normalized scores to favor seed nodes representing such local structures:

qunode=∑v∈𝒩⁡\(u\)κ^u​v−κminκmax−κmin\+η,q\_\{u\}^\{\\mathrm\{node\}\}=\\sum\_\{v\\in\\mathcal\{N\}\(u\)\}\\frac\{\\widehat\{\\kappa\}\_\{uv\}\-\\kappa\_\{\\min\}\}\{\\kappa\_\{\\max\}\-\\kappa\_\{\\min\}\+\\eta\},\(7\)whereκmin\\kappa\_\{\\min\}andκmax\\kappa\_\{\\max\}are the extrema of approximate edge curvature, andη\>0\\eta\>0ensures numerical stability\. By summing curvature\-based scores over incident edges, the aggregation implicitly captures both node degree and local edge geometry, guiding the selection of seed nodes whose neighborhoods form training subgraphs\. If all weights vanish, sampling is uniform over nonisolated nodes\.

#### 3\.2\.2Curvature\-guided Edge sampling

Lower\-curvature edges may indicate bottlenecks or inter\-region connections with limited alternative paths\. To increase their retention probability, we use decreasing curvature weights:

qu​vedge=m​a​x​\(−κ^u​v\+2​κmax,0\)\+1\.q\_\{uv\}^\{\\mathrm\{edge\}\}=\\sqrt\{max\(\-\\widehat\{\\kappa\}\_\{uv\}\+2\\kappa\_\{\\max\},0\)\}\+1\.\(8\)The square\-root transformation moderates weight differences while favoring lower\-curvature connections\. Selected edges and their endpoints form the sampled subgraph\.

Thus, node sampling emphasizes local structural representation, while edge sampling emphasizes potentially critical connections\. Sampling probabilities are obtained by normalizing these weights over all nodes or edges, respectively\.

### 3\.3Complexity and Memory

ForTTaverage CG iterations per right\-hand side, total curvature computation costsO⁡\(\(n\+m\)​K​\(T\+1\)\)O\(\(n\+m\)K\(T\+1\)\)\. Under balanced workloads, ideal parallel time isO⁡\(\(n\+m\)​K​\(T\+1\)P\+n\+m\)\+TcommO\\\!\\left\(\\frac\{\(n\+m\)K\(T\+1\)\}\{P\}\+n\+m\\right\)\+T\_\{\\mathrm\{comm\}\}, whereTcommT\_\{\\mathrm\{comm\}\}accounts for data distribution and result aggregation\.

Table 1:Node classification results \(%\) of different sampling methods\. The best results are marked in bold\.Streaming projection generation and distance accumulation limit peak memory per GPU toO⁡\(n\+m\+n​b\)O\(n\+m\+nb\), including sparse graph operators, edge accumulators, and CG workspace\. This excludes downstream GNN features and activations\. Each GPU retains anO⁡\(n\+m\)O\(n\+m\)graph copy; increasingPPdistributes computation but does not reduce this storage requirement\. Constructing the curvature\-based sampling weights takesO⁡\(n\+m\)O\(n\+m\)time\.

## 4Experiments

Our experiments address three questions:RQ1\. How does the proposed curvature\-guided sampling framework perform on large\-scale graphs for downstream node classification?RQ2\. How closely does approximate ERC agree with the pseudoinverse\-based reference in numerical values and signs?RQ3\. How efficient is ERC\-LG in runtime and GPU memory, and how does its runtime scale with the number of GPUs? Additional experimental results, parameter sensitivity analyses \(e\.g\.,KK,bb, andε\\varepsilon\), and implementation details, together with the ERC\-LG code, are publicly available at[https://github\.com/cqfei/ERC\-large\-graph](https://github.com/cqfei/ERC-large-graph)\.

### 4\.1Experimental Settings

The datasets used in our experiments consist of medium\-scale datasets including PubMed111https://github\.com/shchur/gnn\-benchmark/tree/master/data/planetoid, Amazon Photo222https://github\.com/shchur/gnn\-benchmark/tree/master/data/npz, and Coauthor CS22footnotemark:2, as well as large\-scale datasets Flickr333https://github\.com/GraphSAINT/GraphSAINT, ogbn\-arxiv444https://github\.com/snap\-stanford/ogb, Reddit555https://snap\.stanford\.edu/graphsage/, and ogbn\-products44footnotemark:4\. We select representative large\-graph GNN methods including ClusterGCN\[[2](https://arxiv.org/html/2609.27209#bib.bib3)\], GraphSAGE\[[8](https://arxiv.org/html/2609.27209#bib.bib1)\], FastGCN\[[1](https://arxiv.org/html/2609.27209#bib.bib2)\], GraphSAINT\[[15](https://arxiv.org/html/2609.27209#bib.bib4)\], and REGNN\[[4](https://arxiv.org/html/2609.27209#bib.bib9)\], as well as the curvature\-aware large\-graph sampling methods ORG\-sub\[[14](https://arxiv.org/html/2609.27209#bib.bib12)\]and LC\-sub\[[11](https://arxiv.org/html/2609.27209#bib.bib8)\]as our baselines\. To compare the impact of sampling quality on downstream tasks, we adopt the same two\-layer GCN as the downstream model for all methods, following the training protocol of GraphSAINT for 200 epochs\. In each epoch, a fixed number of subgraphs are sampled, and mini\-batch training is performed on these sampled subgraphs\. For PubMed, ogbn\-arxiv, and ogbn\-products, we follow the official dataset splits, while 10\-fold cross\-validation is adopted for the remaining datasets\. Performance is evaluated by the mean classification accuracy and standard deviation\. All the models are implemented in PyTorch 1\.12\.0 and Python 3\.9\. Experiments are conducted on a server equipped with an Intel\(R\) Xeon\(R\) Gold 6248R CPU, 8 × NVIDIA RTX 3090 GPUs \(24GB VRAM\), and 256GB RAM\. For ORC666https://github\.com/saibalmars/GraphRicciCurvatureand ERC\-REG777https://github\.com/cqfei/resistance\-curvature, we adopt their public Python implementations, respectively\.

### 4\.2Experimental Results

#### 4\.2\.1Node Classification on Sampled Subgraphs

We evaluate four ERC\-LG\-based sampling variants in two groups\. LC\-sub\(ERC\-LG\) and ORG\-sub\(ERC\-LG\) retain their original sampling frameworks but replace the curvature estimators with ERC\-LG\. ERC\-LG\-sub\(node\) and ERC\-LG\-sub\(edge\) follow GraphSAINT with sampling probabilities proportional to the curvature\-based weights in Eqs\. \([7](https://arxiv.org/html/2609.27209#S3.E7)\) and \([8](https://arxiv.org/html/2609.27209#S3.E8)\), respectively\.

Table[1](https://arxiv.org/html/2609.27209#S3.T1)shows that ERC\-LG\-based variants achieve the highest mean accuracy on six of seven datasets, while REGNN leads on Reddit\. ERC\-LG\-sub\(edge\) ranks first on four datasets and outperforms GraphSAINT\(edge\) on all seven; ERC\-LG\-sub\(node\) performs similarly to GraphSAINT\(node\)\. LC\-sub\(ERC\-LG\) remains close to LC\-sub on six datasets and improves Reddit accuracy\. ORG\-sub\(ERC\-LG\) leads on PubMed and Amazon Photo but underperforms ORG\-sub on ogbn\-arxiv and ogbn\-products, indicating that the benefits of curvature substitution depend on the dataset\.

#### 4\.2\.2Numerical Agreement of Curvature Estimates

We evaluate numerical agreement by comparing ERC\-REG \(diagonal perturbation\), ERC\-JL \(JL projection\), and ERC\-LG against pseudoinverse\-based ERC on stochastic block model \(SBM\)\. Metrics include mean absolute error \(MAE\), Spearman correlation, and sign agreement \(Sign\), withKKdenoting the projection dimension\. Table[2](https://arxiv.org/html/2609.27209#S4.T2)shows that ERC\-REG achieves an MAE of10−510^\{\-5\}\. IncreasingKKimproves ERC\-LG’s agreement, reaching an MAE of 0\.00937, Spearman correlation of 0\.9687, and Sign of 92\.39% atK=4096K=4096\. ERC\-LG and ERC\-JL yield nearly identical metrics across all tested dimensions\. Thus, incorporating CG yields comparable agreement with the reference, while larger projection dimensions improve approximation accuracy\.

Table 2:Curvature approximation results on SBM dataset
#### 4\.2\.3Computational Efficiency and GPU Memory Usage

Table 3:GPU memory and runtimeUpper: memory \(MB\),K=2048K=2048; lower: runtime \(s\),P=2P=2,b=256b=256\. “\-” denotes a timeout\.

Figure 1:Multi\-GPU curvature runtime
Table[1](https://arxiv.org/html/2609.27209#S4.F1)summarizes peak memory usage per GPU \(upper block\) and runtime \(lower block\)\. Reducing the batch size from 512 to 256 lowers memory usage on all three datasets, including a reduction from 14,689 to 10,118 MB on Reddit\.

Compared with ERC\-CG, which uses CG without JL projection, ERC\-LG is approximately9\.4×9\.4\\timesfaster on Flickr and34\.5×34\.5\\timesfaster on ogbn\-arxiv\. It also completes curvature computation on Reddit in 1382 seconds, supporting the computational benefit of JL projection\. On ogbn\-products, the maximum feasible batch size in our implementation isb=76b=76due to the 24 GB GPU memory limit\. ERC\-LG nevertheless completes curvature computation in 11366s on 4 GPUs \(K=2048K=2048\), demonstrating its applicability to graphs beyond the sizes reported in Table[1](https://arxiv.org/html/2609.27209#S4.F1)\.

Figure[1](https://arxiv.org/html/2609.27209#S4.F1)shows that runtime decreases as the GPU count increases from 2 to 8 on all three datasets, for bothK=2048K=2048andK=4096K=4096\. Multi\-GPU execution therefore further reduces curvature computation time\.

## 5Conclusion

We proposed ERC\-LG, combining JL projection and regularized multi\-GPU batched CG to approximate ERC without explicit pseudoinverse computation\. The resulting curvature guides node and edge sampling for GNN training\. Experiments show its numerical accuracy and computational efficiency, with ERC\-LG\-based sampling variants achieving the highest mean classification accuracy on six of seven datasets\. These results support ERC\-LG as a practical means of incorporating resistance geometry into large\-scale graph sampling and representation learning\.

## 6Acknowledgments

This work was supported in part by the National Natural Science Foundation of China \(No\. 62406315\), China Postdoctoral Science Foundation \(2025M771504\), Basic and Applied Basic Research Foundation of Guangdong Province \(2024A1515110108\), Key Research and Development Projects of Shaanxi Province \(2025SF\-YBXM\-023\), and Shaanxi Provincial Public Health Scientific Research Innovation Team Project \(202511\)\.

## References

- \[1\]J\. Chen, T\. Ma, and C\. Xiao\(2018\)FastGCN: fast learning with graph convolutional networks via importance sampling\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.27209#S1.p1.1),[§2\.1](https://arxiv.org/html/2609.27209#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[2\]W\.\-L\. Chiang, X\. Liu, S\. Si, Y\. Li, S\. Bengio, and C\.\-J\. Hsieh\(2019\)Cluster\-gcn: an efficient algorithm for training deep and large graph convolutional networks\.InACM SIGKDD International Conference on Knowledge Discovery & Data Mining,pp\. 257–266\.Cited by:[§1](https://arxiv.org/html/2609.27209#S1.p1.1),[§2\.1](https://arxiv.org/html/2609.27209#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[3\]K\. Devriendt and R\. Lambiotte\(2022\)Discrete curvature on graphs from the effective resistance\.Journal of Physics: Complexity3\(2\),pp\. 025008\.Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1),[§3\.1\.1](https://arxiv.org/html/2609.27209#S3.SS1.SSS1.p1.3)\.
- \[4\]H\. Ding, Z\. Wei, and Y\. Ye\(2025\)Scalable and effective graph neural networks via trainable random walk sampling\.IEEE Transactions on Knowledge and Data Engineering37\(02\),pp\. 896–909\.Cited by:[§2\.1](https://arxiv.org/html/2609.27209#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[5\]C\. Fei, G\. Li, T\. Zhou, C\. Wang, and Y\. Li\(2026\)Geometric flow enhanced graph coarsening\.arXiv:2609\.14962\.Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1)\.
- \[6\]C\. Fei, H\. Liu, T\. Zhou, Y\. Li, and T\. Hao\(2026\)Dynamic graph structure learning via resistance curvature flow\.arXiv:2601\.08149\.Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1)\.
- \[7\]C\. Fei, T\. Zhou, T\. Hao, and Y\. Li\(2025\)Efficient curvature\-aware graph network\.arXiv:2511\.01443\.Cited by:[§1](https://arxiv.org/html/2609.27209#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1),[§3\.1\.3](https://arxiv.org/html/2609.27209#S3.SS1.SSS3.p1.1)\.
- \[8\]W\. Hamilton, Z\. Ying, and J\. Leskovec\(2017\)Inductive representation learning on large graphs\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2609.27209#S1.p1.1),[§2\.1](https://arxiv.org/html/2609.27209#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[9\]M\. R\. Hestenes and E\. Stiefel\(1952\)Methods of conjugate gradients for solving linear systems\.Journal of Research of the National Bureau of Standards49\(6\),pp\. 409–436\.External Links:[Document](https://dx.doi.org/10.6028/jres.049.044)Cited by:[§3\.1\.3](https://arxiv.org/html/2609.27209#S3.SS1.SSS3.p2.1)\.
- \[10\]W\. B\. Johnson and J\. Lindenstrauss\(1984\)Extensions of Lipschitz mappings into a Hilbert space\.InConference on Modern Analysis and Probability,Contemporary Mathematics, Vol\.26,pp\. 189–206\.External Links:[Document](https://dx.doi.org/10.1090/conm/026/737400)Cited by:[§3\.1\.2](https://arxiv.org/html/2609.27209#S3.SS1.SSS2.p1.2)\.
- \[11\]D\. W\. Shu, Y\. Kim, and J\. Kwon\(2023\)Localized curvature\-based combinatorial subgraph sampling for large\-scale graphs\.Pattern Recognition139,pp\. 109475\.Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[12\]D\. A\. Spielman and N\. Srivastava\(2008\)Graph sparsification by effective resistances\.InProceedings of the fortieth annual ACM symposium on Theory of computing,pp\. 563–568\.Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1),[§3\.1\.2](https://arxiv.org/html/2609.27209#S3.SS1.SSS2.p1.2)\.
- \[13\]J\. Topping, F\. Di Giovanni, B\. P\. Chamberlain, X\. Dong, and M\. M\. Bronstein\(2022\)Understanding over\-squashing and bottlenecks on graphs via curvature\.InInternational Conference on Learning Representations,Cited by:[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1)\.
- \[14\]S\. Wu, H\. Cheng, J\. Cai, P\. Ma, and W\. Zhong\(2023\)Subsampling in large graphs using ricci curvature\.InThe Eleventh International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.27209#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.27209#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.
- \[15\]H\. Zeng, H\. Zhou, A\. Srivastava, R\. Kannan, and V\. Prasanna\(2020\)GraphSAINT: graph sampling based inductive learning method\.InInternational Conference on Learning Representations,Cited by:[§2\.1](https://arxiv.org/html/2609.27209#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.27209#S4.SS1.p1.1)\.