- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes a learning-based graph coarsening framework that directly optimizes structural preservation objectives. A GNN predicts edge contraction scores, and a maximum-weight forest is constructed to produce connected supernodes with a prescribed reduction ratio. To enable end-to-end training through discrete contraction operations, the authors combine score perturbation with a straight-through estimator. The framework is evaluated on Laplacian spectral preservation across nine graph datasets and three reduction ratios. Experimental results show that the proposed method generally outperforms classical coarsening baselines, particularly at higher reduction ratios, while best-of-K inference further improves spectral preservation.
Critical strengths
1.The paper investigates the important problem of learning graph coarsening operators that adapt to different preservation objectives. It proposes a GNN-based edge contraction framework that combines maximum-weight forest construction with a straight-through estimator, enabling the learning of discrete coarsening decisions while ensuring connected supernodes and exact control over the reduction ratio.
2.The proposed method achieves promising results across nine graph datasets and three reduction ratios, outperforming the best classical coarsening baseline in 24 of 27 settings with best-of-K inference.
Critical weaknesses
-
The paper has several presentation issues. The Introduction is unnecessarily long, particularly the general background on graph coarsening, the extensive discussion of existing methods, and the largely repetitive optimization formulations in Eqs. (1) and (2). These parts could be condensed. In contrast, the key technical motivations and contributions are not sufficiently emphasized. The experimental setup contains excessive implementation details. More importantly, the overall method pipeline figure is placed in the appendix rather than the main paper, making the proposed framework harder to understand. The Statements can be placed outside the nine-page main-text limit to free up valuable space. The authors should streamline the presentation and reorganize the content to better highlight the key technical contributions.
-
The experimental evaluation primarily compares against classical graph coarsening algorithms and GOREN (2021). Although the paper cites more recent work on spectral graph coarsening, such as the ICML 2023 method, it does not include direct experimental comparisons with these approaches. Relevant graph coarsening studies published in three years should be discussed or compared in the experimental comparisons.
Questions for authors
-
The evaluated graphs are relatively small, and the current implementation requires cubic-time spectral preprocessing. How does the end-to-end runtime and coarsening quality compare with classical baselines on graphs with thousands of nodes?
-
Some classical baselines do not achieve the prescribed reduction ratio exactly. Do the performance advantages persist when all methods produce the same number of supernodes?
-
Does the performance advantage of best-of-K inference remain significant under comparable computational budgets, considering the cost of evaluating 128 candidates using the eigenerror metric?
2 comments
As the discussion period is ending soon, we would like to thank you again for the detailed review and the concrete suggestions, especially on clarity. Looking at the paper again, we agree that the introduction of the submitted version was unnecessarily long, and we think the revised version is much clearer and nicer to read.
We especially want to thank you for pointing out the exact reduction size, which we had overlooked and which put our method at an unnecessary disadvantage. With the same number of supernodes for all methods, our gains are even clearer.
If you agree with our assessment, we would be very happy if you would reconsider your score.
Thank you for the time you invested in reviewing our work and for the constructive comments. We had of course hoped for a higher score, but we appreciate the clear critique. We addressed each point below, and we think the revision is clearly better for it, especially in clarity. We would much appreciate hearing whether you agree, and we’re happy to follow up on any remaining concerns.
Presentation
We agree that the main idea was difficult to find in the submitted version. We shortened the introduction, combined the repeated optimization formulations and moved the pipeline figure to the beginning of the method section. We also moved several implementation details to the appendix.
Comparison with recent methods
Following your suggestion, we compared our method with the official KGC and KGC(A) implementations on all datasets and reduction ratios. Our deterministic method is better in 19/27 settings, while the best-of-K method is better in 24/27. KGC uses a different optimization objective, which we now state more clearly in the paper.
Performance on larger graphs
We applied the trained models, which only saw graphs of about 250 nodes, without retraining to graphs with 1,000 to 19,717 nodes. At a reduction ratio of 75%, our deterministic method beats the strongest classical method in 12/15 settings. On our hardware (one NVIDIA H100 GPU), coarsening takes at most 0.21 s per graph, 40 to 180 times faster than Variation Neighborhoods on CPU. On the same CPU, we are still 3 to 15 times faster. The cubic preprocessing came only from computing the positional encodings with a dense eigendecomposition. We now compute only the first 10 eigenvectors with a sparse solver, which the spectral classical methods need as well. Thanks for raising this point, it’s an important test for a learned method.
Exact reduction size
Thanks for raising this. Our method always produces exactly the requested number of supernodes, while the classical methods return too many in 23% of the cases, which puts our method at a disadvantage. When we compare only graphs where both reach the exact target, our results get slightly better: the deterministic method wins in 20/27 settings (18/27 before) and best-of-K in 24/27 (23/27 before). We added this comparison to the revision.
Computational costs
We agree that the costs of best-of-K inference were missing, thanks for pointing this out. On our hardware (one NVIDIA H100 GPU), deterministic inference takes 7 to 9 ms per graph and best-of-128 takes 0.2 to 0.5 s, including the eigenerror of all candidates. The classical methods only run on CPU, so we also ran our method on the same CPU. There, deterministic inference takes 5 to 17 ms per graph and is faster than the best classical method in 25/27 settings. Best-of-128 takes about 6 times as long as the classical method (median). With the same time budget, our method can evaluate about 8 candidates and still has lower error in 19/27 settings.