acceptodds
Under review as a conference paper at ICLR 2027

Moment-guided Edge Sampling

Abstract

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 to , 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
edge sampling, spectral moments, interpretable structural signatures, preserving graph properties, improving graph learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_wMqSOpenReview ↗
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, mk=1nTr(Pk)m_k = \frac{1}{n}\mathrm{Tr}(P^k), as a graph-level summary, and the per-edge change Δmk(ϵ)\Delta m_k(\epsilon) induced by an edge addition/deletion as an edge-level signal for sampling. Two exact computation routes are given: (i) a combinatorial method for m2,m3m_2, m_3 with closed-form updates from maintained local statistics (WiW_i, MijM_{ij}, HiH_i), claimed O(1)O(1) per candidate; (ii) a low-rank method that writes an edit batch as P′=P+CR⊤P' = P + CR^\top (rank r≤2∣B∣r \le 2|B|), expands Tr((P+Q)k)−Tr(Pk)\mathrm{Tr}((P+Q)^k)-\mathrm{Tr}(P^k) via cyclic trace invariance, and compresses it to products of r×rr \times r matrices Ht=R⊤PtCH_t = R^\top P^t C, giving O(Km)O(Km) per single-edge edit instead of O(Kmn)O(Kmn). A greedy sampler then selects edits that move the current moment profile toward a target. Appendix B adds a locality proposition (2dG(e,h)>k⇒2d_G(e,h) > k \Rightarrow zero interaction), an interaction bound (Theorem 4), an endpoint-local implementation, and a lazy top-KK rescoring heuristic. Empirically, the paper (a) visualizes (Δm2,Δm3)(\Delta m_2, \Delta m_3) 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 m2/m3m_2/m_3 closed forms (Eqs. 4–5, 26–27) are correct, and the low-rank trace expansion (Eqs. 13–16) with the k/ℓk/\ell cyclic multiplicity is a neat, exact reduction that I checked against (kℓ)=kℓ(k−1ℓ−1)\binom{k}{\ell} = \frac{k}{\ell}\binom{k-1}{\ell-1}. The locality proposition and the bilinear-interpolation proof of Theorem 4 are correct and self-contained.

Interpretability. Connecting Δm2\Delta m_2 / Δm3\Delta m_3 to concrete edge motifs (triangle edges, bridges, dyads) is intuitive and the fingerprint visualization is a nice idea.

Practical engineering. The endpoint-local HtH_t computation (App. B.6.1) and the lazy top-KK 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
  1. The core structural-preservation evaluation is close to circular. Section 5 optimizes m2,m3,m4m_2,m_3,m_4 and then reports that four properties are preserved: neighbor inverse degree (which is m2m_2 exactly, Eq. 76), the normalized Estrada index of PP (which is ∑kmk/k!\sum_k m_k/k!, dominated by low-order terms), triangle-weighted clustering (which is m3m_3 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.

  2. 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.

  3. “Global structure” is overstated: the moments used are local. All experiments use K≤4K \le 4. m2m_2 is a one-hop degree statistic, m3m_3 a degree-weighted triangle count, m4m_4 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 kk, which the method cannot afford: Eq. 16 has 2k−12^{k-1} trace-product terms (acknowledged as O(K2Kr3)O(K2^K r^3) in B.7.1), so “arbitrary moment orders” is practical only for small KK. The paper should either demonstrate meaningfully high orders or temper the global-structure claim.

  4. 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 m2m_2 is exactly the neighbor inverse-degree statistic and the Estrada index is ∑kmk/k!\sum_k m_k/k!, what in Section 5 is not a direct consequence of the optimization objective?

What is the largest KK for which the low-rank method is practical, given the 2k−12^{k-1} terms in Eq. 16? Can you show that preserving, say, m8m_8 or m10m_{10} changes which properties are retained?

What are the per-step costs (including rescoring and local-statistic updates) as a function of mm and max degree, and how do they scale on a graph with ≥106\ge 10^6 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?

Reviewer_P5U2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Based on the finding that spectral moments of graphs can represent graph structure, the paper proposes a moment-preserving sampling method that can retain related structural properties. The new algorithm is efficient: by storing related statistics, it can compute changes in the second and third moments in O(1)O(1) time per edge change, and it uses a low-rank method that takes O(Km)O(Km) time for higher-order moments, where KK is the moment order and mm is the number of edges. The paper runs experiments to compare the new method with uniform random sampling, and the method performs better. The method is also used for supervised node classification and graph contrastive learning and gets good performance compared with GRACE, MVGRL, and GCL-SPAN.

Critical strengths

The idea of using moment changes as signatures of edge structure is simple and novel. Many graph sampling methods only sparsify graphs, but this method can both delete and insert edges.

For each edge change, the method can compute changes in the second and third moments in O(1)O(1) time using stored statistics, which is efficient.

It performs better than uniform random sampling in the graph sparsification experiments. The method is also used for supervised node classification and graph contrastive learning, and gets good results compared with GRACE, MVGRL, and GCL-SPAN.

Critical weaknesses

For graph sparsification, many papers seek a sparsifier HH that preserves the Laplacian spectrum by satisfying (1−ε)x⊤LGx≤x⊤LHx≤(1+ε)x⊤LGx(1-\varepsilon)x^\top L_Gx \leq x^\top L_Hx \leq (1+\varepsilon)x^\top L_Gx. Some work also tries to preserve the normalized cut. This paper repeatedly says that it can “retain structural properties,” but it does not give a theoretical guarantee for either of these properties. For spectral preservation, it reports numerical RMSE between the random-walk eigenvalues of the original and sampled graphs. This is weaker than the bound above: that bound guarantees approximate preservation of the Laplacian eigenvalues, but a small eigenvalue RMSE does not imply the bound.

In the structural-preservation experiments, the method is compared only with uniform random edge sampling, which is a simple baseline without a theoretical spectral guarantee. Other sparsification methods do have such guarantees, and comparing with them would be more informative.

The experimental results need to be presented more clearly. For example, Figure 3 does not give the sizes of the original graphs, the number of runs for each setting, and whether the reported statistics are normalized or not. It is also unclear whether each plotted value is a mean or a maximum across runs. Standard deviations are not given.

The paper gives the time complexity of computing the moment change for one edge, but does not report how many edge updates are needed to achieve the same level of precision as other sparsification methods or the overall time complexity.

Questions for authors

See weaknesses.

Reviewer_L5auOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper provides an analysis of a graph using spectral moments of the transition matrix of its random walk. An edge modification is evaluated according to the distance between the edited graph and the desired target moment signature, and the modifications are done in a greedy manner. The key technical aspect is the computation of moment change cheaply using two approaches. First, a closed-form solution solves the problem for m2 and m3 in O(1) time using locally maintained statistics. Second, a low-rank approach tackles all orders and batches, reducing the cost of processing a single edge from O(mn) to O(m). The experiments involve: fingerprint plots of edge-wise moment changes. preservation of moments upon removal vs. random removal on five datasets. two case studies on Cora and Citeseer (node classification and contrastive learning). runtime evaluation on Cora.

Critical strengths
  1. The motivation and generality of the technique are appropriate. Rather than removing edges based on some arbitrary criteria, each local change to the graph is justified by its effect on the graph's spectral moments. This same technique can be used whether we want to preserve or direct the graph towards some particular target, and even supports adding edges.
  2. The computational aspects of the technique are accurate and practical. Closed form equations for updating the low-order moments, a low rank approximation for updating higher order moments and multiple changes at once, and the locality property have all been proven. Combined with the provided code, the moment change calculation technique is reusable outside of this paper.
Critical weaknesses
  1. The evidence for the claim that moment preservation implies structure preservation is mostly circular. All four measures in Section 5 are closely related to the moments which are preserved. For example, neighbor inverse degree equals m2 by the equation (76). There is just one baseline - random removal, so the evidence does not prove anything besides the algorithm being tunining towards its objectives. Measures which are not related to moments, such as connectivity, path lengths or communities, as well as more challenging baselines are necessary to prove the general claim.
  2. The claimed applications are not proven convincingly enough. The performance boost for contrastive learning in comparison with MVGRL (0.24 and 0.40 points) is less than the reported standard deviations. The supervised setting proves some effect under one point without confidence intervals. The motivation of the work is large-scale graph learning, but the runtime is only reported on Cora.
Questions for authors
  1. How does the method perform on properties not derived from the moments, against stronger baselines and on at least one large graph?
  2. What are the full runtime and memory costs on a large graph, including statistic maintenance?
  3. Are the Figure 4 and Table 1 differences statistically significant? Was the Figure 7 target chosen on validation or test?
  4. why is the neighbor inverse-degree error non-zero if it equals the m2 error?
  5. what candidate-set size, normalization scale, number of seeds and GNN setup were used?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.