Moment-guided edge sampling

1 INTRODUCTION

• Targeted edge sampling needs a locally computable quantity that reflects how an edge edit changes global graph structure.The introduction notes that an edge’s structural role depends on its surroundings, making its contribution difficult to measure directly.Source: §1 · p. 1
• Spectral moments connect local edge edits to global structure because edits change weighted closed walks and move the graph in moment space.Computing edge-wise changes lets sampling select edits that move the graph toward a desired target profile.Source: §1 · pp. 1–2
• The framework combines exact O(1) low-order combinatorial updates with a low-rank method for arbitrary orders and batched edits.For single-edge edits, the low-rank method reduces computation by a factor of n over direct recomputation.Source: §1 · p. 2
• Edge-wise moment changes act as interpretable signatures of local motifs and aggregate into graph-level fingerprints.The paper also derives connections between moments and properties including triangle-weighted clustering, and validates that moment-preserving sampling can retain structural properties.Source: §1 · p. 2
• Case studies find that edge structures have distinct effects on supervised node classification, while moment-guided augmentation is competitive in graph contrastive learning.The authors present these results as potential support for analyzing and improving graph learning.Source: §1 · p. 2

2 PRELIMINARIES

• For an undirected graph, the random-walk transition matrix is P = AD^-1, with P_ij giving the one-step probability of moving from j to i.P is similar to a symmetric matrix, so its eigenvalues are real and lie in [-1, 1].Source: §2 · p. 2
• The k-th spectral moment is the average k-step return probability over nodes, equivalently a normalized sum of weighted length-k closed walks.The passage gives m1 = 0 for graphs without self-loops and relates m2 to edges and m3 to triangles.Source: §2 · p. 2
• Spectral moments connect to graph diffusion and structural properties, and the paper mainly uses m2 and m3 for interpretation while supporting arbitrary orders.Heat trace and personalized PageRank trace can be expressed as weighted sums of moments.Source: §2 · pp. 2–3

3 MOMENT-GUIDED EDGE SAMPLING

• For a selected set of moment orders, the framework represents each candidate addition or deletion by its induced moment change and selects edits toward a target profile.The combinatorial and low-rank methods provide complementary ways to compute these changes; direct recomputation is prohibitively expensive across many candidates.Source: §3 · p. 3

3.1 COMBINATORIAL MOMENT CHANGE

• The combinatorial method derives exact low-order moment changes from affected closed walks, with m2 determined by edges and m3 by triangles.Maintained local statistics allow constant-time lookups and arithmetic for each candidate; explicit tracking becomes increasingly difficult at higher orders.Source: §3.1 · pp. 3–4

3.2 LOW-RANK MOMENT CHANGE

• The low-rank method uses endpoint locality and cyclic trace invariance to represent batched edits as a low-rank transition-matrix update.Affected walks are anchored at touched endpoints and compressed into products of small endpoint-to-endpoint matrices, supporting arbitrary orders and batched edits.Source: §3.2 · p. 4
• For a single-edge edit, endpoint compression replaces full n × n matrix powers with r × r matrix products to compute the moment change.The resulting computation supports arbitrary moment orders and batched edits.Source: §3.2 · p. 5

3.3 MOMENT-GUIDED EDGE SELECTION

• Candidate edits are scored by the normalized distance between their expected post-edit moment profile and the target; the candidate set can include additions and deletions.The normalization uses the original graph’s moments to keep different moment orders on comparable scales throughout sampling.Source: §3.3 · p. 5
• Figure 2 profiles show smoothed edge distributions in normalized (∆m2(e), ∆m3(e)) space, with similar profiles indicating similar local edge-centered motif distributions.The profiles serve as graph-level fingerprints of structural edge types.Source: Figure 2 · p. 6

4 MOMENT CHANGES AS STRUCTURAL SIGNATURES

• Edges in triangles tend to have negative ∆m3, while bridge-like edges attached to clustered regions can have positive ∆m3.For ∆m2, deleting an internal path edge can increase two-step return probabilities, whereas deleting an isolated dyad edge decreases them.Source: §4 · p. 6
• Classic graphs with homogeneous edges concentrate in a narrow range of moment-change directions, while graphs with multiple edge types can show multiple modes.Figure 1 pairs representative edge-centered motifs with smoothed edge distributions for classic graphs.Source: §4 · p. 6, Figure 1 · p. 6
• Graphs from the same domain often have similar moment-change profiles, while different domains can show distinct profiles that fingerprint their structural edge types.Citation and web-page graphs differ in the second quadrant, where web-page graphs contain more often bridge-like edges connected to clustered regions.Source: §4 · pp. 6–7
• Co-purchase and social networks have similar profiles, a pattern that may reflect shared-neighborhood mechanisms and the dense communities, triangles, and hub–periphery patterns they promote.Products may share transactions or categories, while people may share affiliations, interests, or mutual friends; these mechanisms promote the listed structures (Leskovec et al., 2009).Source: §4 · p. 7

5 MOMENT-PRESERVING SAMPLING RETAIN STRUCTURAL PROPERTIES

• Preserving additional moment orders further reduces spectral RMSE because moments characterize the eigenvalue distribution and constrain the spectrum.RMSE is measured between the eigenvalues of the original and sampled graphs.Source: §5 · p. 7
• The third moment is a degree-weighted sum over triangles, motivating evaluation of the triangle-weighted clustering coefficient’s graph-level mean error.Compared with standard clustering, this coefficient gives greater weight to triangles involving lower-degree neighbors.Source: §5 · p. 7
• The second moment measures average inverse degree among one-hop neighbors; higher even-order moments extend this interpretation to accessibility-weighted inverse degrees of r-step reachable nodes.The experiments use r = 1 for average neighbor inverse degree.Source: §5 · p. 8
• A k-th moment is the average probability that a k-step random walk returns to its start, and the normalized Estrada index aggregates return behavior across walk lengths.The normalized Estrada index is evaluated using absolute error.Source: §5 · p. 8
• Moment-preserving sampling produces smaller deviations than uniform random edge removal across all four studied properties.The properties are normalized spectrum, triangle-weighted clustering, neighbor inverse degree, and normalized Estrada index.Source: §5 · p. 8

6 MOMENT-GUIDED SAMPLING FOR GRAPH LEARNING

• Removing many edges from direction D4 consistently degrades supervised classification performance on both Cora and Citeseer, in association with more isolated nodes.The authors relate the isolation to limited neighborhood aggregation in these homophily graphs.Source: §6 · pp. 8–9
• For unsupervised node classification on Citeseer and Cora, moment-guided augmentation achieves competitive results against GRACE, MVGRL, and GCL-SPAN.The method was not specifically designed for graph contrastive learning.Source: §6 · p. 9

7 RELATED WORK

• Table 1 reports unsupervised node-classification accuracy on Citeseer and Cora as mean ± standard deviation.The caption identifies the evaluation scope but does not provide the results.Source: Table 1 · p. 9
• Existing sampling and sparsification approaches include random edge dropping, subgraph sampling, and graph partitioning, but do not explicitly measure how each edge edit changes a prescribed global representation.The proposed approach measures edge-wise moment changes and selects edits toward a target moment profile.Source: §7 · p. 9
• Prior spectral-moment applications include graph representation, preservation of graph properties, and graph learning through diffusion operators; this work instead uses moment changes for interpretable, controllable sampling.Heat trace and personalized PageRank trace can be expressed as weighted sums of moments.Source: §7 · p. 9

8 CONCLUSION

• Moment-guided sampling connects local edge edits to global structure, retaining properties such as triangle-weighted clustering and yielding competitive contrastive-learning augmentation.The conclusion also reports that edge structures have distinct effects on supervised node-classification performance.Source: §8 · p. 9

B.1 UNIFIED SAMPLING FRAMEWORK

• The unified framework uses interchangeable combinatorial and low-rank modules: the former handles low-order moments, while the latter supports higher orders and batched edits.The combinatorial method needs maintained local statistics; the low-rank method does not require persistent local statistics in the shared procedure.Source: §B.1 · p. 12

B.2 COMBINATORIAL CHANGE FOR LOW-ORDER MOMENTS

• For low-order edge additions, the combinatorial updates account for the new edge or triangles and the reweighting of existing incident edges or triangles.The update formulas use endpoint degrees and maintained local statistics.Source: §B.2 · pp. 12–13

B.3 MAINTAINING LOCAL STATISTICS

• After each edit, the combinatorial method updates degrees, neighborhoods, and local statistics using rules restricted to edited endpoints and their neighborhoods.These updates keep subsequent moment deltas accurate without recomputing the whole graph.Source: §B.3 · p. 13

B.4 LOW-RANK CHANGE FOR GENERAL EDGE EDITS

• For batched edits, the low-rank method captures interactions by applying edits locally before forming transition-column changes for touched endpoints.The supplied passages describe the construction but do not provide a complexity comparison for this subsection.Source: §B.4 · p. 13

B.5 INTERACTIONS AND LOCALITY OF MOMENT CHANGES

• Moment-change interactions are defined through mixed differences, with edge edits affecting transition columns only at their endpoints.The included passages introduce interaction locality but do not provide the proposition’s full bound.Source: §B.5 · pp. 13–14

B.5.1 EXACT LOCALITY

• For selected moment orders K with R = max K, deleting h leaves e’s moment changes unchanged when dG(e, h) > ⌊R/2⌋; for K = {2, 3}, the threshold is distance greater than 1.The radius marks potentially affected edges, not edges guaranteed to change: some within it can have zero interaction.Source: §B.5.1 · p. 14
• Pairwise-separated deletion sets have additive moment changes when every cross-set edge distance exceeds ⌊R/2⌋ for R equal to the largest selected order.The condition prevents a length-k closed walk from visiting endpoints in two different deletion sets.Source: §B.5.1 · p. 14

B.5.2 INTERACTION BOUNDS FOR ARBITRARY MOMENT ORDERS

• For arbitrary moment orders, the interaction bound is parameterized by endpoint-column changes; the section notes that it permits shared endpoints and deletions creating isolated nodes.The supplied passages define se as bounding total column change, αe as bounding the largest column change, and β as the mixed transition-matrix change.Source: §B.5.2 · pp. 15–16

B.6 EFFICIENT IMPLEMENTATION

• The strategy targets two bottlenecks: evaluating candidate moment changes and repeatedly rescoring candidates as the graph evolves.Its motivation combines endpoint structure in the low-rank formulation with locality and bounded interactions among candidates.Source: §B.6 · p. 19

B.6.1 ENDPOINT LOW-RANK COMPUTATION

• For single-edge deletion, the low-rank computation needs only a 2 × 2 endpoint matrix, so the method computes endpoint-to-endpoint transition probabilities rather than propagating the full sparse product.The local propagation is limited to endpoint neighborhoods and, for moment mk, transition probabilities through order k − 1 are sufficient.Source: §B.6.1 · p. 20

B.6.2 LAZY TOP-K CANDIDATE RESCORING

• Lazy top-K rescoring recomputes only the K candidates with smallest cached scores after each edit, reducing evaluations from m candidates to K per step at the cost of exact greedy selection.The remaining candidates retain cached scores until selected for rescoring.Source: §B.6.2 · p. 20

B.7 COMPLEXITY AND EFFICIENCY EVALUATION

• Lazy top-K rescoring achieves over 2× speedup in most settings and up to 6.45×, while retaining comparable structural-property preservation.Figure 5 reports that K = 25 nearly matches the original full-rescoring method.Source: §B.7 · p. 21, Figure 5 · p. 21, §B.7.2 · p. 21

B.7.1 COMPLEXITY ANALYSIS

• With maintained local statistics, the combinatorial method computes low-order moment changes in O(1) time per candidate.The supplied complexity analysis gives its space cost as O(n + |P|), reaching O(n2) in the worst case.Source: §B.7.1 · p. 21
• For single-edge removal at fixed moment orders, the combinatorial method costs O(1) per candidate and the low-rank method O(Km), versus O(Kmn) for direct sparse power computation.The low-rank method’s time ratio to direct sparse computation is O(1/n); the combinatorial method is fastest for m2 and m3.Source: §B.7.1 · p. 21

B.7.3 RUNTIME COMPARISON

• Both combinatorial and low-rank moment-change methods are substantially faster than direct trace recomputation.Table 2 reports Cora sampling efficiency on a single CPU thread; direct trace uses two sequential deletions, while other methods use 100.Source: §B.7.3 · p. 21, Table 2 · p. 22
• Nearly 50× faster for (m2, m3), the combinatorial method benefits from maintained local statistics that enable constant-time candidate evaluation.The comparison concerns low-order moments.Source: §B.7.3 · p. 22

C.1 EDGE MOMENT DIRECTION PROFILES

• Edge-deletion moment changes are normalized relative to the original moments, then represented by magnitude and direction to profile their structural effects.The directional profile smooths directions with a Gaussian kernel and normalizes the distribution over edges with nonzero changes.Source: §C.1 · pp. 23–24

C.2.1 DERIVATIONS OF STRUCTURAL PROPERTIES

• The third spectral moment aligns with triangle-weighted clustering when triangle degrees are comparable and not too small; the associated score weights triangles involving low-degree neighbors more heavily.Source: §C.2.1 · p. 26
• The second spectral moment measures the average inverse degree observed from each node’s local neighborhood.Source: §C.2.1 · p. 26

C.2.2 ADDITIONAL PRESERVATION RESULTS

• Across ca-GrQc, Cora, Citeseer, Wisconsin, and Actor, moment-preserving sampling preserves structural properties better than uniform random edge removal.Source: §C.2.2 · p. 27

C.3 MOMENTS-GUIDED EDGE SAMPLING FOR GRAPH LEARNING

• The supervised-classification experiments examine how edge-deletion directions affect performance and compare direction-specific removal with uniform removal at matched budgets.They use the full split and exclude edges whose endpoints are same-label training nodes.Source: §C.3 · p. 27, §C.3.1 · p. 27

C.3.1 SUPERVISED NODE CLASSIFICATION

• Each direction-and-deletion-ratio setting averages 25 test-accuracy differences, drawn from five seeds and five paired samples per seed.Source: §C.3.1 · p. 27

• For contrastive learning, the moment-preserving view is evaluated against GRACE, MVGRL, and GCL-SPAN using a 20% edge-edit budget and an unchanged remaining training pipeline.The downstream classifier uses a 10%/10%/80% train/validation/test split.Source: §C.3.2 · pp. 27–28
• Reproduced GCL-SPAN results may differ from the original because dataset-specific hyperparameters are not fully provided.The released implementation’s split was corrected to match the stated protocol.Source: §C.3.2 · p. 28
• The target-profile study varies 36 profiles around the original (m2, m3), edits 20% of the original edge count, and averages accuracy over 10 seeds.Source: §C.3.2 · p. 29
• Cora’s best target increases both moments around (m2, m3) = (0.35, 0.033), whereas Citeseer’s best target decreases both around (0.40, 0.0163).The landscapes therefore show graph-specific augmentation preferences rather than a universal optimal rule.Source: §C.3.2 · p. 29, Figure 7 · p. 29