Moment-guided Edge Sampling

Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This raises a fundamental challenge: how can the global structural impact of removing an individual edge be quantified and controlled? We address this challenge with a moment-guided edge sampling framework that summarizes global graph structure using spectral moments of the random-walk transition matrix and quantifies each edge removal through its induced moment changes. To compute moment changes efficiently, we develop two complementary methods: a combinatorial method with closed-form updates for low-order moments, and a low-rank method that reduces computation based on the endpoints of removed edges, supporting arbitrary moment orders as well as batched removals. For single-edge removal using fixed number of moments, 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.