Moment-guided edge sampling

Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: $\mathit{\text{how}}\mathit{\text{can}}\mathit{\text{the}}\mathit{\text{effect}}\mathit{\text{of}}\mathit{\text{a}}\mathit{\text{local}}\mathit{\text{edge}}\mathit{\text{edit}}\mathit{\text{(i.e.,}}\mathit{\text{edge}}\mathit{\text{addition}}\mathit{\text{or}}\mathit{\text{removal)}}\mathit{\text{on}}\mathit{\text{global}}\mathit{\text{graph}}\mathit{\text{structure}}\mathit{\text{be}}\mathit{\text{quantified}}\mathit{\text{and}}\mathit{\text{controlled?}}$ We address this challenge with a $\mathit{\text{moment-guided}}\mathit{\text{edge}}\mathit{\text{sampling}}\mathit{\text{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 $\mathit{\text{locality}}$ and $\mathit{\text{cyclic}}\mathit{\text{trace}}\mathit{\text{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 $\mathbf{\text{interpretable}}\mathbf{\text{structural}}\mathbf{\text{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 $\mathbf{\text{retain}}\mathbf{\text{related}}\mathbf{\text{structural}}\mathbf{\text{properties}}$, including triangle-weighted clustering coefficient. These structural insights enable $\mathbf{\text{analysis}}\mathbf{\text{and}}\mathbf{\text{improvement}}\mathbf{\text{of}}\mathbf{\text{graph}}\mathbf{\text{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.