Moment-guided edge sampling

Weibin Cai; Reza Zafarani

cs.LGSep 24, 2026

Moment-guided edge sampling

Authors: Weibin Cai, Reza Zafarani

Organizations: Data Lab, Department of EECS Syracuse University Syracuse, NY, USA

Abstract

Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: how can the effect of a local edge edit (i.e., edge addition or removal) on global graph structure be quantified and controlled? We address this challenge with a moment-guided edge sampling framework based on spectral moments of the random-walk transition matrix. We compute exact moment changes through two complementary methods: a combinatorial method with closed-form updates for low-order moments, and a low-rank method that exploits locality and cyclic trace invariance to compress computations to edited endpoints, supporting arbitrary moment orders and batched edits. For single-edge edits at fixed moment orders, the low-rank method reduces the cost from $O(mn)$ to $O(m)$ , while the combinatorial method evaluates low-order changes in constant time given maintained local statistics. These moment changes provide interpretable structural signatures of local edge motifs that aggregate into graph-level fingerprints. This structural meaning motivates us to ask whether preserving moments also preserves the graph properties. We further derive and validate that moment-preserving sampling can retain related structural properties, including triangle-weighted clustering coefficient. These structural insights enable analysis and improvement of graph learning: different edge structures have distinct effects on supervised node classification, while moment-guided augmentation is competitive for graph contrastive learning. Together, these findings establish moments as an interpretable and controllable bridge from local edge edits to global graph structure and learning.

Figures & tables

Figure 1: Edge distributions of classic graphs in the

(\Delta m_{2},\Delta m_{3})

space. Outer examples show representative edge-centered motifs along different moment-change directions, with the red edge indicating the deleted edge. Inner profiles show the smoothed edge distributions for classic graphs.

Figure 2: Moment-change fingerprints of real-world graphs. Each profile shows the smoothed edge distribution in the normalized

(\Delta m_{2}(e),\Delta m_{3}(e))

space. Similar profiles indicate similar distributions of local edge-centered motifs. Visualization details are provided in Appendix C.1 .

Figure 3: Preservation of four structural properties under moment-preserving edge sampling: normalized spectrum , triangle-weighted clustering , neighbor inverse degree , and normalized Estrada index . Moment-preserving sampling yields smaller deviations than uniform random edge removal across all four properties. For the spectrum, preserving more moment orders further reduces RMSE.

Panel of Figure 4 — Figure 4: Effect of removing edges from different moment-change directions on supervised node classification. Edges are divided into eight directions ( $D0$ – $D7$ ), each associated with a representative motif. The radius indicates the deletion ratio within each direction, and the heatmap shows the test–accuracy difference from uniform random edge removal under the same budget. Edges connecting training nodes with the same label are excluded from deletion.

Method	Citeseer	Cora
GRACE	$71.15\pm 0.73$	$82.99\pm 1.53$
MVGRL	$72.41\pm 1.30$	$84.18\pm 0.98$
GCL-SPAN	$71.94\pm 0.68$	$84.07\pm 0.59$
Ours	$\mathbf{72.65\pm 0.65}$	$\mathbf{84.58\pm 0.56}$

Table 1: Unsupervised node classification accuracy (%) on Citeseer and Cora. Results are reported as mean

\pm

standard deviation.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Structural-property preservation under original full-rescoring method and lazy top-

K

candidate rescoring. The anchor_m2_m3_m4 curve denotes the original method, using the same moment-preserving setting as in Figure 3 . Each lazy variant preserve the same moment orders but only rescoring only the top-

K

candidates at each steo. Lazy top-

K

closely tracks original method, with larger

K

yielding closer agreement;

K=25

already nearly matches the original baseline. Random edge removal produces substantially deviations.

Moment orders	Backend	Lazy top- $K$	Time cost (s)		Speedup
Moment orders	Backend	Lazy top- $K$	Preprocessing	Per deletion	Speedup
$(m_{2},m_{3})$	Direct trace	–	0.197	50.16513	–
	Combinatory	–	0.100	0.00067	–
		5	0.101	0.00028	$2.37\times$
		25	0.098	0.00036	$1.86\times$
		50	0.100	0.00041	$1.62\times$

Appendix

Table 2: Sampling efficiency on Cora using a single CPU thread. Direct trace computes edge-wise moment changes by directly evaluating the trace difference in Eq. 1 ; due to its high cost, it is measured over two sequential deletions, while the other methods are evaluated over 100 deletion. Per-deletion time excludes preprocessing. Hybrid uses the combinatorial method for

m_{2},m_{3}

and the low-rank method for

m_{4}

. A dash in the lazt top-

K

column denotes the original full-rescoring method, while a numeric

K

denotes lazy top-

K

rescoring. Speedup is measured relative to the corresponding full-rescoring configuration using the same backend and moment orders.

Panel of Figure 6 — Figure 6: Moment-preserving sampling preserve four graph properties across datasets.

Panel of Figure 7 — Figure 7: Accuracy landscapes over different target moment profiles. Each point corresponds to an augmented view generated toward a target $(m_{2},m_{3})$ profile under the same edge-edit budget. The blue star marks the original moment profile, while the red star marks the target with the highest mean test accuracy.

Spectral Methods

Spectral methods use eigenvalues, eigenvectors, and frequency decompositions to analyze data, graphs, operators, and learning algorithms.

See all 238 papers

Aug 14, 2026

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump. When the sampled fraction

s

is known by design the total edge count follows from

\hat e=e_s/s^2

and no model is needed. We treat the case where

s

is unknown and the population size is known. Our main result is a reduction: under a sparse exchangeable (graphex) model the expected non-isolated fraction obeys

n_s/n_1\to s^{1+σ}

, so the sampling rate becomes estimable once the tail index

σ

is, and substituting it back gives

e_s(n_1/n_s)^{2/(1+σ)}

-- the same estimator, with the design quantity inferred. Estimating global edge cardinality in a sparse graph is therefore, in expectation, tail-index estimation, and the quadratic graphon estimator is the case

σ=0

: it fails by an identity rather than by a fit (

260\%

median error against

27\%

). We bound the finite-size error of the substitution and show the reduction is modular in the tail-index estimator --- filled with a published closed-form one it reaches

21.7\%

over

13

networks and

39

sampling budgets with no fitting at all. Fitting a full graphex additionally returns the degree distribution at any size and a generative object, in a representation where sparsity is a coordinate and the interpolation path is dictated rather than chosen. Two limits are exact: rank-one graphexes have transitivity fixed by the degree profile, so high-clustering graphs lie outside the class; and under snowball or random-walk crawls every method here fails, the design-based oracle worst of all (

7.8\%

588\%

Jian Xu, Delu Zeng, John Paisley +1

RIKEN iTHEMS, Wako, Japan · RIKEN Center for Advanced Intelligence Project (AIP), Tokyo, Japan · South China University of Technology, Guangzhou, China +1

Topic pending

Ask PDF

Sep 23, 2026

Scalable Subgraph Sampling via Resistance Curvature

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.

Chaoqun Fei, Tinglve Zhou, Tianyong Hao +1

School of Artificial Intelligence, South China Normal University · School of Computer Science, South China Normal University · Academy of Mathematics and Systems Science, Chinese Academy of Sciences

Graph Neural Networks Importance Sampling

Ask PDF

Oct 6, 2026

EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

Sparse GNN training reduces computation, but deciding which edges to keep can be costly. Reusing one sparse graph is cheap, but locks training to a fixed topology, while varying it across epochs can require repeated sampling or recomputation. We introduce EDiS (Edge-Disjoint Subgraph sparsification framework), which separates one-time structural extraction from per-epoch graph composition. EDiS decomposes the graph once into cacheable edge-disjoint subgraphs, then recombines them into graphs with edge-budget constraints across epochs and retention ratios without re-extracting structure. Our default construction uses feature-based scores and successive maximum score covering forests, while the same composition mechanism also supports alternative edge selection rules. We provide a combinatorial analysis of the per-epoch sampler, the composition step that draws a training graph from the cached decomposition. We show that, under the default covering-forest selector, the stored decomposition deterministically preserves high-score cut edges, and we derive a selector-agnostic conditional bound on high-score cut survival in composed training graphs. Across 19 homophilic, heterophilic, and large-scale node classification benchmarks against 17 baselines under the same edge budget, EDiS achieves the highest mean benchmark score (accuracy/ROC-AUC) and the lowest average rank and gap-to-best among ranked methods. Ablations show the clearest benefits of structural decomposition and epoch variation at tight edge budgets.

Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt +7

University of Texas at Dallas · Pacific Northwest National Laboratory · Adobe Research +3

Graph Sparsification Graph Neural Networks

Ask PDF

Abstract

Spectral Methods

Explore similar work

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index

Scalable Subgraph Sampling via Resistance Curvature

EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks