arXiv paper2026-09-23· graph machine learning· method paper

Scalable Subgraph Sampling via Resistance Curvature

Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li

cs.LG · cs.AI

Quick verdict

ERC-LG uses JL projections + batched CG for curvature-guided GNN subgraph sampling; credible scaling results, but accuracy wins are mostly within noise.

Summary

This paper introduces ERC-LG, a scalable approximation of effective resistance curvature (ERC) for large graphs, and uses it to guide subgraph sampling for GNN training. Building on the authors' earlier perturbation-based ERC scheme, ERC-LG replaces explicit Laplacian pseudoinversion with Johnson–Lindenstrauss projections that reduce the number of linear systems, solves these with a regularized multi-GPU batched conjugate gradient solver, and accumulates edge distances in a streaming fashion to avoid storing full embeddings. On a stochastic block model, agreement with pseudoinverse-based ERC improves with projection dimension, reaching MAE 0.00937, Spearman correlation 0.9687, and 92.39% sign agreement at K=4096. Compared with a CG-only ablation, ERC-LG is 9.4× faster on Flickr and 34.5× faster on ogbn-arxiv, and completes Reddit in 1382 s where the ablation times out; it also processes ogbn-products in 11366 s on 4 GPUs. The resulting curvature feeds node- and edge-sampling weights, used both in GraphSAINT-style training and as drop-in estimators inside the LC-sub and ORG-sub frameworks. With a shared two-layer GCN, ERC-LG-based variants post the highest mean accuracy on six of seven datasets, though several margins (e.g., 93.83±0.30 vs 93.76±0.09 on Amazon Photo) lie within one standard deviation, no significance tests are reported, and REGNN wins Reddit. Main limitations: unreported hyperparameters behind the accuracy table, unanalyzed curvature sign errors, no timing baselines for competing curvature methods, and incremental novelty over Spielman–Srivastava.

Review complete

Assessment at a glance

graph machine learning

risk flags identified

● high 0

● medium 3

● low 2

Reproducibility readinessmedium

Code & data availableyes

Review confidencehigh

AI text signal0/20 passages flagged

Deep research viableCode-reproducibleNeeds GPU

4 strengths · 5 weaknesses · 5 author questions

AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.

Levels reflect verification complexity — not a quality score. Evolve never rates your paper.

Key claims under review

ERC-LG approximates pseudoinverse-based effective resistance curvature on large graphs by combining JL projections with regularized multi-GPU batched CG, without explicit pseudoinverse computation or full embedding storage.
On an SBM, ERC-LG reaches MAE 0.00937, Spearman correlation 0.9687, and 92.39% sign agreement with the pseudoinverse reference at projection dimension K=4096.
Against a CG-only ablation, ERC-LG is ~9.4× faster on Flickr and ~34.5× faster on ogbn-arxiv, and completes Reddit in 1382 s where the ablation times out.
ERC-LG-based sampling variants achieve the highest mean node-classification accuracy on six of seven datasets with a shared two-layer GCN.

Strengths

Genuine scalability engineering with memory-aware design
Streaming projection generation and per-batch distance accumulation avoid materializing the n×K embedding (Sec. 3.1.3, Algorithm 1); Table 3 shows batch-size scaling from b=512 to 256 cuts Reddit per-GPU memory from 14,689 to 10,118 MB, and ogbn-products (~2.4M nodes) completes in 11366 s on 4 GPUs at the memory-limited b=76.
Honest internal ablation of the pipeline
Table 3 quantifies the JL-projection benefit against the authors' own CG-only variant: 9.4× on Flickr and 34.5× on ogbn-arxiv, and candidly reports ERC-CG timing out on Reddit while ERC-LG finishes in 1382 s (P=2, b=256, K=2048).
Curvature accuracy validated against a reference with K-scaling
Two integration paths tested, regressions disclosed

Weaknesses

Headline accuracy claim statistically fragile
Curvature substitution is dataset-inconsistent
Efficiency claims lack external baselines
Key configuration for the main table unreported
Unquantified error sources and incremental novelty

Full Review Report

$1.99 · one-time

Unlock the complete preliminary analysis Evolve produced for this paper.

Report preview

Scope & Claims

This is a method paper (short conference format) proposing ERC-LG, a scalable approximation of effective resistance curvature (ERC) for large graphs, plus two curvature-guided subgraph sampling schemes for GNN training. Central claims: (1) JL projections plus regularized multi-GPU batched CG approximate pseudoinverse-based ERC without explicit inversion or full embedding storage (Sec. 3.1, Algorithm 1); (2) agreement with the pseudoinverse reference improves with projection dimension K, reaching MAE 0.00937, Spearman 0.9687, and 92.39% sign agreement at K=4096 on an SBM (Table 2); (3) runtime drops 9.4× on Flickr and 34.5× on ogbn-arxiv versus a CG-only ablation, with Reddit completed in 1382 s where the ablation times out (Table 3); (4) ERC-LG-based sampling variants achieve the highest mean accuracy on six of seven datasets (Table 1). The paper is openly positioned as an extension of the authors' perturbation-based ERC scheme [5] and of Spielman–Srivastava's JL resistance estimation [11].

Methodology Assessment

The algorithmic design is sensible: rewriting R_uv as a squared embedding distance (Eq. 3), drawing K Rademacher JL columns, solving (L+εI)Z=Y by column-batched CG over P GPUs, and accumulating per-batch squared edge distances so the n×K embedding is never materialized. Complexity O((n+m)K(T+1)) and per-GPU memory O(n+m+nb) are stated (Sec. 3.3). Two gaps stand out. First, the two error sources are treated only qualitatively: the regularization bias from finite ε is acknowledged (Sec. 3.1.3) with no bound or in-text ε sweep, and Spielman–Srivastava's JL dimension the

The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.

All 4 strengths & 5 weaknesses, analyzed in detail
5 risk flags with severity, section & reviewer questions
Methods & statistical evidence assessment
5 questions a peer reviewer would ask
Full six-dimension evaluation report & recommendations

One-time purchase · this paper only

One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.

Frequently asked questions

What is ERC-LG in this paper?

ERC-LG is a method for approximating effective resistance curvature (an edge-level geometric quantity for graphs) on very large graphs. It uses Johnson–Lindenstrauss random projections to reduce the number of linear systems to solve, a regularized conjugate gradient solver distributed across multiple GPUs, and streaming accumulation of edge distances so the full embedding matrix is never stored — avoiding the O(n²) cost of explicitly computing the Laplacian pseudoinverse.

Does curvature-guided sampling actually improve GNN accuracy?

Modestly, at best. With a shared two-layer GCN, the paper's ERC-LG-based samplers post the highest mean accuracy on six of seven datasets (Table 1), but several winning margins are below 0.1 accuracy points and within one standard deviation of the baseline (e.g., 93.83±0.30 vs 93.76±0.09 on Amazon Photo), no significance tests are reported, and the REGNN baseline wins on Reddit. The larger, more reliable gains are on Flickr (52.06 vs 51.68) and ogbn-arxiv (66.67 vs 65.87).

Is code or data available for this paper?

The paper states that ERC-LG code, additional results, and parameter sensitivity analyses are publicly available at github.com/cqfei/ERC-large-graph. All seven evaluation datasets are standard public benchmarks (PubMed, Amazon Photo, Coauthor CS, Flickr, ogbn-arxiv, Reddit, ogbn-products), though the exact hyperparameters used for the main accuracy table are not stated in the paper itself.

How much faster is ERC-LG than alternatives?

The reported speedups are against the authors' own CG-only ablation (same pipeline without JL projection): about 9.4× on Flickr and 34.5× on ogbn-arxiv, with Reddit finishing in 1382 seconds where the ablation times out (2 GPUs, batch 256, K=2048). The paper does not report wall-clock comparisons against Ollivier-Ricci or 3-cycle curvature methods on these graphs.

About this review

This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.

Fig. 1 (multi-GPU runtime scaling) is analyzable only via its caption; per-GPU-count speedup values cannot be extracted from text.
Parameter sensitivity analyses (K, b, ε) and implementation details are deferred to the linked repository/supplementary material and are not in the extracted text.
Tables 1–3 were flattened during text extraction; values were transcribed as printed, and dataset splits/protocol descriptions were taken at face value.

Go deeper on this paper

Wrote a paper? Stress-test it before reviewers do.

Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.

Scan your paper