Moment guided edge sampling links local edits to global graph structure
Moment-guided edge sampling
Machine LearningSocial and Information Networks
Summary
Graphs are networks made of points connected by lines, and changing one line can affect the whole network’s shape. The authors develop a way to measure how adding or removing a single connection changes important overall features of the graph, called moments, that reflect patterns like triangles. They show how to quickly calculate these changes and use them to keep the graph’s key properties intact. This helps understand which connections matter for tasks like classifying nodes and can improve graph-based machine learning.
What this means in practice
- •For machine learning engineers: Maintain graph structural features during data augmentation to improve performance and robustness of node classification models.
- •For graph analytics teams: Quantify and control the impact of local edge edits on global graph properties to preserve meaningful patterns during graph simplification or sampling.
Authors
Weibin Cai, Reza Zafarani
Abstract
Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: \textit{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 \textit{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 \textit{locality} and \textit{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 \textbf{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 \textbf{retain related structural properties}, including triangle-weighted clustering coefficient. These structural insights enable \textbf{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.