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

Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index
Aug 14, 2026Jian 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
Scalable Subgraph Sampling via Resistance Curvature
Sep 23, 2026Chaoqun Fei, Tinglve Zhou, Tianyong Hao +1Graph Neural Networks Importance Sampling
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
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
Oct 6, 2026Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt +7Graph Sparsification Graph Neural Networks
University of Texas at Dallas · Pacific Northwest National Laboratory · Adobe Research +3

Aug 14, 2026J/K move · Enter open · S save

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

Jian Xu, Delu Zeng, John Paisley, Qibin Zhao

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

Open paper AskPDF arXiv

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\%

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