acceptodds
Under review as a conference paper at ICLR 2027

Deep Graph Coarsening: Learning to Contract Edges

Abstract

Graph coarsening reduces the number of nodes in a graph while preserving the structural properties that downstream tasks rely on. Classical coarsening methods are fixed algorithms designed heuristically to preserve a particular property of the graph, such as the low end of the Laplacian spectrum. They do not adapt to the graph domain at hand, and targeting a different property requires designing a new heuristic. We propose to learn the coarsening operator instead, directly from the objective it should optimize. We demonstrate that this is possible. Our general framework lets a graph neural network assign scores to the edges of a graph, and then contract a maximum-weight forest with a given number of edges. To address that the coarsening operation is discrete and non-differentiable, we use a straight-through estimator and smoothen the objective with noise. We evaluate our method using a Laplacian spectrum-preserving objective. Across nine graph datasets and three reduction ratios, the learned operator outperforms the best classical baseline in 24 of 27 settings and on all nine datasets at the highest reduction ratio (). Notably, these include methods explicitly designed for this objective, whereas our method is general.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph coarsening, graph reduction, graph neural networks, spectral graph theory, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_LCfAOpenReview ↗
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
  1. 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.

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

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

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

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.

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.

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

In this work the authors proposed a method which learns a coarsening operator directly from the objective we want to be optimized. By contracting a forest with n-n^hat edges provides n^hat supernodes, the problem becomes essentially learning which edges to contract. A GNN is used to put scoring weights on the edges of a graph, and a greedy algorithm to choose the forest. The training is essentially a passthrough of the discrete choice of forest.

The authors present a discrete graph coarsening operator, and test it for Laplacian spectral preservation, comparing it with a number of classical baselines.

Critical strengths
  • Theoretical foundation, experiments, complexity analysis of the proposed approach are presented in detail.
  • Results show promise of the proposed approach, with many possible future directions (possibly multilevel solvers, multiscale message passing etc.)
Critical weaknesses
  • The paper only looks at better spectrum-preserving coarsening essentially, which doesn't guarantee downstream performance. They only real-case is a single spectral clustering experiment. So applying the method in real-world cases is questionable. I am not saying that the claim of the paper is this, but if that's the case, the paper should make it clear.
  • Reporting mainly eigenerror, and training also on that seems a bit circural.
Questions for authors
  • Any explanation why does the approach performs worse specifically for SBM?
  • Relative eigenvalue error can look good while the eigenvectors are badly misaligned. Did the authors include any way to assure that?
3 comments

Thank you for reviewing our work and the constructive comments. We respond to your points below.

Training objective versus evaluation metric

First of all we want to clarify that we do not train on eigenerror. As the eigenerror is in general not differentiable, our training method uses the differentiable quadratic form loss, which can be seen as an approximation of the eigenerror. The eigenerror is only our evaluation metric. We use it on validation data to pick the checkpoint, and best-of-K uses it to pick a candidate. The deterministic method never computes it on test graphs and still beats the best classical method in 18/27 settings.

Preservation objective

Besides training our method to preserve the eigenvalues, we also trained it to preserve node attributes after replacing each node’s attributes by the mean of its contraction set. The model trained this way beats the same model trained on the spectral objective in 15/15 settings. This shows that the objective can be swapped.

SBM

The strongest baseline on SBM is Variation Neighborhoods. It uses the eigenvectors to choose contractions with low local spectral cost, which works best when only a few contractions are needed. Our results are worse at a reduction ratio of 25%, nearly equal at 50% and better at 75%. The results suggest that learning pays off most when many contraction choices interact.

Eigenvectors

Thanks for raising eigenvector alignment, that’s a good point. We now evaluate it for all methods, using the principal angles between the first 10 eigenvectors of the original graph and the lifted coarse ones. Although our model is trained only to preserve the eigenvalues, it preserves the eigenvectors well too. Deterministic inference is better than random contraction in 22/27 settings and better than the average of the classical methods in 19/27. If the eigenvectors matter, we can also optimize for them. When best-of-K picks the candidate with the lowest eigenvector error, it beats random contraction in 27/27 settings and the average of the classical methods in 23/27. We added this to the revision.

I thank the authors for their response which addresses most of my concerns. I will raise my score accordingly.

Thank you very much for your response and for raising your score!

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

The authors proposed Deep Graph Coarsening, a framework that learns the graph coarsening operator directly from the Laplacian-based energy difference loss instead of relying on fixed heuristics like existing methods. The forward process include three steps: 1) A GNN scorer assigns a score to every edge, 2) a greedy maximum-weight forest construction with a predefined number of edges, then 3) each connected component become the coarsened node. Since the map from scores to partition is piecewise constant, the authors perturb the scores with Gumbel noise to smooth the expected loss. The backward process includes a two-part straight-through estimator: a heuristic norm-based sensitivity signal of the loss w.r.t. the projection matrix, while an Gumbel-Softmax top-k relaxation sampling is used for the forest selection derivative. Forest mask can be used to restrict the backward signal to selected edges during forward phase. Due to the additional noise, two inference modes are proposed: the deterministic forest, or best-of-K selection among perturbed forests by either the training loss or the evaluation metric (relative smallest-nonzero-eigenvalues error). The method is evaluated by relative eigenerror on the 10 smallest nonzero eigenvalues, on nine graph datasets, at three coarsening ratios. The results show the learned operator beats the best classical method while improvement from a learnable baseline (GOREN) is mixed.

Critical strengths
  • Clean and intuitive construction with heuristic,perturbation, and relaxation to make the coarsening process can be trained end-to-end through discrete operations.
  • Diverse baselines (random, classical, learnable), datasets and ablation studies. Different aspects of the method are tested (sampling strategy, searching power, training loss), with detailed experiment settings for reproduceability, with providing honest comment of the limitations.
  • Reuslts show learning does help: deterministic beats a single random forest in all 27 settings, and learned best-of-128 beats random best-of-128 in 26/27 settings.
Critical weaknesses
  • No std reported for table 3, rasing concerns about the significance of the results.
  • Gain from GOREN (learnable method) is mixed with number of wins ranging from 4-6/9 datasets tested.
  • Test datasets are in small scale, even with additional "larger graphs", the maximum number of nodes is 640, which is still small for real-world graphs, limiting the scalibility and practical impact of the method.
  • Strongest results include substantial search power: the 24/27 wins use best-of-128 inference, which requires 128 eigenerror evaluation, versus 20/27 for deterministic inference. Random best-of-128 also beats classical methods on all nine datasets at 75% reduction. Although learned search beats random search in 26/27 settings, inference time for the headline configuration is not reported.
Questions for authors
  • Please report std over the three seeds for every cell of Table 3, if possible, include all performances for each tuple (arm, dataset, ratio).
  • Report the inference time for the best-of-128 inference mode.
  • Analysis on K (Fig 14) stopped at 16 is limited, please include more K values to see if the gain over classical baselines can be further improved
3 comments

Thanks a lot for your very detailed review and for the constructive feedback. We respond to your points below.

Reporting of standard deviations

We reran all experiments with three different seeds and the revision now reports std values everywhere. The typical std is about 5% of the mean. Best-of-K beats the best classical method in 23/27 settings, and in 20 of them the difference is significant (95% bootstrap interval).

Clarification on comparison with GOREN

GOREN takes the coarsened graph from a classical method and then optimizes the edge weights. We don't optimize the edge weights. So the comparison is not exactly apples-to-apples. We view the two methods as complementary, as we can apply GOREN to the output of our method to further improve the coarsened graph. We tried this and were able to reduce the error of our coarsened graphs by another 8% on average (7% for best-of-K), applying GOREN where it lowers the validation error. Thank you for pointing this out. We now clarify this in the revision.

Larger graphs

We applied the trained models, which only saw graphs of about 250 nodes, without retraining to graphs with 1,000 to about 20,000 nodes (PubMed, Amazon Photo and Computers, and BA). At high reduction (r = 0.75), we beat the best classical method in 12/15 settings. On our hardware (one NVIDIA H100 GPU), inference takes at most 0.21 s per graph, not counting the first eigenvectors, which the classical methods need too.

Inference time of best-of-128

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 a direct comparison is hard. We therefore 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). If we give our method the same time as the classical method, it can evaluate about 8 candidates and still has lower error in 19/27 settings.

More candidates

We extended the analysis to K = 128 on all nine datasets. More candidates keep helping, but the gain flattens. From K = 16 to 128 the error drops by about 7%, and the number of settings where we beat the best classical method goes from 20/27 to 23/27.

As the discussion deadline is approaching, we would like to ask whether our response has addressed your concerns. We are happy to follow up on anything in the remaining time. If so, we would be grateful if you would reconsider your score.

In any case, thanks a lot for the clear review and the suggestions! We think the new experiments we added in response to your review, especially on larger graphs and the combination with GOREN, make the results much more convincing.

I thank the authors for the detailed response and the revision. Here is my response:

  • W1/Q1 is addressed: Tables 2-3 now report std and paired bootstrap intervals. However, I did not expect all experiments to be rerun; the changes (e.g., the regenerated ER benchmark and changed classical baselines) are too many to re-verify at this stage, and Tables 4-7 are unchanged from the submission, so they do not reflect the rerun.
  • W2 is partly addressed: the further 8% from adding GOREN is given only as an average, and it is not shown whether the combination outperforms GOREN alone on PROTEINS and ENZYMES.
  • W3 is partly addressed: the larger-graph results (12/15 settings at r = 0.75) are promising, but reported without a table. I suggest keeping the REDDIT-BINARY failure case in the appendix.
  • W4/Q2 and Q3 are addressed for the main benchmark, with one remaining point: the headline 23/27 uses about six times the classical coarsening time (median), and the method wins in 19/27 settings at an equal time budget.

Could you add the tables for (1) the larger graphs: per dataset, the graph sizes and the errors of your method and of the best classical method (and which method), at each ratio if available, and (2) the GOREN combination: your method, your method + GOREN, and GOREN alone, per dataset and ratio? Tables for all new results in Appendix O and Section L1 also help in the final version.

Overall, I appreciate the additional experiments, but given the extent of the changes and the missing or outdated tables, I keep my score for now. The tables above would help me reassess W2 and W3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.