- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes using spectral moments of the random-walk transition matrix, , as a graph-level summary, and the per-edge change induced by an edge addition/deletion as an edge-level signal for sampling. Two exact computation routes are given: (i) a combinatorial method for with closed-form updates from maintained local statistics (, , ), claimed per candidate; (ii) a low-rank method that writes an edit batch as (rank ), expands via cyclic trace invariance, and compresses it to products of matrices , giving per single-edge edit instead of . A greedy sampler then selects edits that move the current moment profile toward a target. Appendix B adds a locality proposition ( zero interaction), an interaction bound (Theorem 4), an endpoint-local implementation, and a lazy top- rescoring heuristic. Empirically, the paper (a) visualizes as edge “signatures” and graph “fingerprints”; (b) shows moment-preserving deletion preserves four moment-related properties better than uniform random deletion on five small graphs; (c) runs two case studies on Cora/Citeseer: direction-wise deletion effects on supervised GCN accuracy, and a moment-preserving augmentation view for graph contrastive learning that matches GRACE/MVGRL/GCL-SPAN.
Critical strengths
Clean, exact, and verifiable derivations. The closed forms (Eqs. 4–5, 26–27) are correct, and the low-rank trace expansion (Eqs. 13–16) with the cyclic multiplicity is a neat, exact reduction that I checked against . The locality proposition and the bilinear-interpolation proof of Theorem 4 are correct and self-contained.
Interpretability. Connecting / to concrete edge motifs (triangle edges, bridges, dyads) is intuitive and the fingerprint visualization is a nice idea.
Practical engineering. The endpoint-local computation (App. B.6.1) and the lazy top- heap are sensible, with measured speedups; code is released as a pip-installable library with reproduction scripts.
Breadth of framing. Linking moments to heat trace, PPR trace, Estrada index, and clustering gives a coherent story about what moment preservation controls.
Critical weaknesses
-
The core structural-preservation evaluation is close to circular. Section 5 optimizes and then reports that four properties are preserved: neighbor inverse degree (which is exactly, Eq. 76), the normalized Estrada index of (which is , dominated by low-order terms), triangle-weighted clustering (which is up to the approximation in Eq. 74), and spectral RMSE (which finitely many moments constrain by construction). Showing that a method optimizing moments preserves functions of those moments better than uniform random removal establishes very little. The interesting question — whether moment preservation retains standard properties that practitioners care about (raw degree distribution, standard clustering coefficient, community structure/modularity, diameter, spectral gap, effective resistances) — is not tested.
-
Only one baseline, and it is the weakest possible. Uniform random edge removal is the sole comparator in Section 5. The paper cites spectral sparsification by effective resistance (Spielman & Srivastava), Leskovec & Faloutsos’ sampling methods, and the sparsification benchmark of Chen et al. (2023), yet compares to none of them. Effective-resistance sampling comes with spectral guarantees and would be the natural competitor for the spectral-RMSE claim; edge betweenness, Jaccard/common-neighbor scores, or degree-preserving rewiring are obvious alternatives for the clustering and degree claims. Without these, the empirical contribution is not established.
-
“Global structure” is overstated: the moments used are local. All experiments use . is a one-hop degree statistic, a degree-weighted triangle count, counts 4-closed-walks. These are local motif statistics, not global structure. The “bridge from local edge edits to global graph structure” framing holds only for large , which the method cannot afford: Eq. 16 has trace-product terms (acknowledged as in B.7.1), so “arbitrary moment orders” is practical only for small . The paper should either demonstrate meaningfully high orders or temper the global-structure claim.
-
Test-set selection in the contrastive-learning experiment. Appendix C.3.2 and Figure 7 sweep 36 target moment profiles and mark the “Best test accuracy” target; the landscape axes are explicitly “Test accuracy”. It is unclear whether Table 1’s “Ours” is the moment-preserving target (main text) or the best point of this test-accuracy landscape. If the latter, the comparison is invalid. Even if the former, the landscape analysis as presented selects on test data and should be redone on validation. Additionally, GCL-SPAN was “tuned” by the authors because hyperparameters were unavailable, while “Ours” sits inside the GCL-SPAN pipeline with one view replaced — the gains (0.2–0.4 points, within one std) do not support the “competitive” claim beyond “roughly equal”.
Questions for authors
Please add effective-resistance spectral sparsification, edge-betweenness/Jaccard-based deletion, and at least one sampler from Leskovec & Faloutsos as baselines in Section 5, and report standard properties (raw degree W1, standard clustering coefficient, modularity/community preservation, spectral gap) rather than only moment-derived quantities.
Since is exactly the neighbor inverse-degree statistic and the Estrada index is , what in Section 5 is not a direct consequence of the optimization objective?
What is the largest for which the low-rank method is practical, given the terms in Eq. 16? Can you show that preserving, say, or changes which properties are retained?
What are the per-step costs (including rescoring and local-statistic updates) as a function of and max degree, and how do they scale on a graph with edges or heavy-tailed degrees (e.g., ogbn-arxiv, a social network)?
In Table 2, is “per deletion” the time to evaluate one candidate or to complete one greedy step over the whole candidate set?