- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Ollivier–Ricci Graph Coarsening (ORGC), which uses local curvature scores to guide node contraction through a Kruskal-style greedy algorithm. The authors introduce Ricci Geometric Coherence (RGC) to measure within-cluster geometric similarity, derive a forest-based lower bound that can be optimized exactly, and establish a conditional boundary-preservation guarantee. Experiments evaluate structural fidelity, graph classification, molecular regression, and runtime scaling on synthetic graphs with up to 5,000 nodes. The results show that ORGC generally achieves better structural preservation and competitive downstream performance compared with the selected graph coarsening baselines, with relatively efficient computation for the depth-one variant.
Critical strengths
-
ORGC provides a simple but interesting method based on curvature-guided greedy contraction.
-
The paper introduces an RGC objective and establishes greedy optimality for its lower bound and a conditional boundary-preservation guarantee.
-
ORGC achieves strong structural fidelity and competitive downstream performance compared with the evaluated baselines.
Critical weaknesses
-
The paper does not sufficiently explain why Ollivier–Ricci curvature is particularly suitable for graph coarsening. Although high curvature may indicate structurally similar neighborhoods, the connection between curvature-guided contraction and the preservation of graph properties or downstream performance remains unclear.
-
ORGC relies solely on graph structure and does not incorporate node features when determining contractions, limiting its applicability to attributed graphs where node semantics are important.
-
Several relevant published studies are not adequately compared or discussed. For example, Graph Pooling via Ricci Flow (TMLR 2024) proposes ORC-Pool, which also employs Ollivier–Ricci curvature for graph coarsening and pooling. Although cited, it is not included in the experimental comparisons. Other relevant studies should be discussed, including Curvature-based Clustering on Graphs (JMLR 2025) , which also investigates curvature-guided graph clustering (coarsening), and Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms (ICML 2026), which also addresses graph coarsening guided by topological properties.
-
Insufficient evaluation of large-scale graphs. One of the primary applications of graph coarsening, extensively investigated in prior work, is to compress large-scale graphs and accelerate downstream computation, such as GNN training. However, the experiments in this paper mainly focus on structural preservation, graph classification on relatively small graphs, and molecular regression. The largest runtime experiment involves only 5,000 nodes on synthetic graphs, and no end-to-end acceleration results are provided for downstream applications. Furthermore, the depth-2 variant incurs substantial computational overhead compared with simpler baselines, raising concerns about scalability.
Questions for authors
-
Can ORGC be practically used to accelerate GNN training for node or link level tasks?
-
The proposed algorithm exactly maximizes a forest-based lower bound of the RGC objective, but this bound may become loose as more edges are contracted. Can the authors discuss the tightness of this bound or establish conditions under which optimizing it yields a near-optimal RGC partition?
-
The depth-2 variant incurs substantially higher computational costs but provides relatively limited improvements over depth-1. In what scenarios is depth-2 curvature necessary or particularly beneficial? How should one balance computational efficiency and coarsening effectiveness when choosing the curvature depth?
6 comments
Response to Reviewer W6Ji (Part 2 / 2)
Q4: Large-graph training.
We evaluate GRACE and GraphSAGE on PubMed in Planetoid format (19,717 nodes, 44,324 undirected edges, 500-dimensional attributes), with 30% retention and ORGC-d1.
Following official configurations, GRACE uses attributes for contrastive learning [5], while GraphSAGE uses node-ID embeddings for structure-only learning [6]. Logistic-regression evaluation shares the same data splits across methods. Detailed settings are provided in Appendix C.3.1 (Lines 1352–1374).
The table lists GRACE / GraphSAGE means over three runs on the same hardware, with costs in seconds and accuracy in %. FULL is excluded from ranking.
| Method | Coarsening cost | Training cost | Total cost | Accuracy |
|---|---|---|---|---|
| FULL | 0 / 0 | 552.69 / 101.57 | 552.7 / 101.6 | 86.20 / 48.90 |
| ORGC | 12.17 / 11.95 | 57.79 / 30.16 | 70.0 / 42.1 | 81.48 / 65.62 |
| VEGC | 69.29 / 71.08 | 68.59 / 38.93 | 137.9 / 110.0 | 55.67 / 44.54 |
| VNGC | 13.57 / 13.45 | 69.69 / 33.99 | / | / |
Including coarsening, ORGC achieves 7.90× / 2.41× speedups over FULL, with higher mean accuracy and lower total cost than the listed coarsening baselines in both tasks.
Q5: RGC approximation and gap bound.
Thank you for raising this question. We quantify the gap between the RGC attained by maximizing the forest lower bound and the optimal RGC at the same node budget. For fixed , a connected unweighted simple graph, and , write for the RGC of ORGC's output partition and for the optimal RGC. Our RGC Optimality Gap Bound (Section 3.4 Theorem 4 Lines 303–323) constructs an upper bound on and a lower bound on , satisfying
Thus, guarantees additive optimality. Intuitively, ORGC is near-optimal when it can complete the required contractions using high-curvature edges, while paths restricted to these edges remain nearly as short as in the original graph. The guarantee becomes tighter when the minimum curvature of these edges is closer to and the additional path length is smaller. The constructions and proof are in Appendix B.4 (Lines 970–1079).
On 58 connected graphs with at most 12 nodes, we compare the bound , actual gap , and exact optimum. Scores and gaps are graph means; Mass (%) is the mean RGC achieved by ORGC divided by the mean optimal RGC, multiplied by 100. An output is counted as optimal within a numerical tolerance of . Each depth is evaluated against its own objective.
| Depth | Retention | Bound | Gap | Mass (%) | Optima | ||
|---|---|---|---|---|---|---|---|
| ORGC-d1 | 30% | 0.369137 | 0.403675 | 0.096858 | 0.034537 | 91.44% | 19/58 |
| 50% | 0.389400 | 0.416330 | 0.077421 | 0.026930 | 93.53% | 19/58 | |
| 70% | 0.431863 | 0.445155 | 0.021553 | 0.013292 | 97.01% | 37/58 | |
| ORGC-d2 | 30% | 0.455778 | 0.478759 | 0.076415 | 0.022982 | 95.20% | 23/58 |
| 50% | 0.481959 | 0.494870 | 0.055856 | 0.012911 | 97.39% | 25/58 | |
| 70% | 0.521840 | 0.523563 | 0.008362 | 0.001722 | 99.67% | 50/58 |
The optimality-gap bound approaches the actual gap as retention increases. ORGC remains close to the optimum and often attains it, supporting its effectiveness.
Q6: Depth selection.
Depth two adds non-backtracking two-hop context, distinguishing nodes with similar one-hop neighborhoods but different two-hop structures. This can reduce tie ambiguity at the cost of larger transport supports and more computation. We report relative fluctuations over five score perturbations on 58 connected graphs, measured as 100 × range / absolute average of the cross-graph means.
| Depth | Retention | RGC | REE | RE |
|---|---|---|---|---|
| ORGC-d1 | 30% | 2.39 | 4.15 | 2.31 |
| 50% | 0.59 | 1.66 | 0.96 | |
| 70% | 1.24 | 1.57 | 1.17 | |
| ORGC-d2 | 30% | 0.03 | 0.12 | 1.69 |
| 50% | 0.39 | 1.34 | 1.12 | |
| 70% | 0.21 | 1.16 | 1.09 |
All fluctuations of cross-graph means are below 5%, with lower RGC and REE fluctuations for d2. Use d1 when efficiency is the priority; select d2 through validation when one-hop scores discriminate poorly and additional computation is affordable.
In summary, we hope the above response resolves your concerns and helps you re-evaluate our work. Feel free to contact us if you have any other questions.
References
[1] Optimal Transport: Old and New. 2009.
[2] Graph Pooling via Ricci Flow. 2024.
[3] Curvature-based Clustering on Graphs. 2025.
[4] Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms. 2026.
[5] Deep Graph Contrastive Representation Learning. 2020.
[6] Inductive Representation Learning on Large Graphs. 2017.
Gentle Reminder
Dear Reviewer W6Ji,
As the discussion period is drawing to a close, please let us know whether our responses and additional experiments have resolved your concerns and helped you reconsider your assessment of our work.
Thank you again for your time and thoughtful consideration.
Response to Reviewer W6Ji (Part 1 / 2)
Thank you for your thoughtful feedback. Below, we provide responses to your comments in the following section and we have modified the manuscript to address these issues. (Changes are highlighted in blue in the updated PDF.)
Q1: Why Ricci curvature?
Ollivier–Ricci curvature measures geometric similarity between local Markov distributions, identifying redundancy suitable for contraction. High-curvature edges tend to lie within the same region, as illustrated in Figure 1(a). At a fixed node distance, higher curvature means lower neighborhood transport cost, incorporating both mass distributions and graph distances beyond adjacency.
From a signal perspective, for any 1-Lipschitz function f under the original-graph metric,
\le W_{1,d_G}(m_u^{\alpha,h},m_v^{\alpha,h}) =\bigl(1-\kappa_{\alpha,h}(u,v)\bigr)d_G(u,v).$$ High curvature controls local Markov-response differences; RGC aggregates this agreement within clusters, and the forest lower bound supplies an efficiently optimizable surrogate. The score ablations further support this choice: within the same Kruskal framework at 20% node retention, both ORGC configurations achieve lower REE than CN, Jaccard, and Forman on all six datasets (Table 5, Section 4.5, Lines 489–504). **Q2: Extension to node attributes.** Thank you for pointing this out. As stated in Section 2.1 (Line 119), “We primarily assess whether coarsening preserves graph structure.” Structure-based coarsening is a classical setting, and our comparisons are restricted to this scope. This does not limit the extension of ORGC, since Wasserstein distance **naturally accommodates feature information**. On a connected graph, we combine graph distance and a normalized attribute metric to define the fused ground metric: $$d_\lambda(u,v)=(1-\lambda)d_G(u,v)+\lambda d_X(u,v),\qquad 0\le\lambda<1.$$ Here, $d_X$ is a normalized metric on node attributes. The resulting fused Wasserstein distance $W_{1,d_\lambda}$ is a metric on probability measures by standard Wasserstein theory [1]. Retaining the structural Markov measures $m_u^{\alpha,h}$, we define the fused Ollivier–Ricci curvature as $$\kappa_{\alpha,h}^{\lambda}(u,v) =1-\frac{W_{1,d_\lambda}(m_u^{\alpha,h},m_v^{\alpha,h})}{d_\lambda(u,v)}.$$ This curvature can be used to formulate an analogous RGC optimization problem, and $\lambda=0$ recovers the original curvature. Since theoretical guarantees for this fused extension remain to be established, we do not include it in the current method and regard it as an important direction for future work. We have added the corresponding definitions and discussion in Appendix D.2 (Lines 1429–1448). **Q3: Related work and baselines.** We have added a discussion of ORC-Pool [2], Curvature-based Clustering [3], and Topology-Preserving Graph Coarsening [4] in Appendix D.1 (Lines 1406–1427), clarifying how their objectives, contraction mechanisms, and guarantees differ from those of ORGC. We evaluate a standalone spectral adaptation of ORC-Pool at 20% retention. We have also added STPGC [4], using its official implementation, to this comparison. The table reports accuracy (%) ↑ / REE ↓; Mean weights the six datasets equally. |Method|MUTAG|PTC|PROTEINS|MSRC|IMDB|Tumblr|Mean| |-|-|-|-|-|-|-|-| |ORGC-d1|**84.67**/1.648|53.10/1.382|**65.26**/$\underline{0.983}$|16.69/$\underline{1.150}$|$\underline{66.28}$/**0.147**|$\underline{50.85}$/**0.432**|$\underline{56.14}$/$\underline{0.957}$| |ORGC-d2|$\underline{83.48}$/**1.467**|**55.35**/**1.117**|$\underline{63.85}$/**0.899**|$\underline{17.36}$/**1.083**|**66.48**/$\underline{0.152}$|**51.74**/$\underline{0.463}$|**56.38**/**0.864**| |ORC-Pool|78.71/$\underline{1.595}$|53.35/$\underline{1.176}$|63.46/2.024|16.41/1.238|65.46/0.407|48.35/0.488|54.29/1.155| |STPGC|77.45/2.520|$\underline{53.63}$/2.437|63.62/2.723|**18.54**/1.371|58.99/1.657|50.15/0.935|53.73/1.940| ORGC leads in most individual comparisons, with higher mean accuracy and lower mean REE.