acceptodds
Under review as a conference paper at ICLR 2027

Geometry-Aware Graph Coarsening via Ollivier-Ricci Curvature

Abstract

We introduce Ollivier-Ricci Graph Coarsening (\method), a geometry-aware graph coarsening framework that formulates node contraction through Ricci-curvature optimization.Existing methods commonly use adjacency rules or Laplacian preservation, which do not model metric-measure geometry explicitly.Gromov-Wasserstein coarsening makes this geometry explicit, but its global distance and assignment computations make efficient implementation difficult.ORGC instead adopts Ollivier-Ricci curvature as an efficient geometric primitive for comparing Markov neighborhoods.We define Ricci Geometric Coherence (RGC) over non-singleton coarse clusters, which measures all-pairs curvature agreement among nodes that are actually contracted together.ORGC derives a contraction-forest lower bound for this objective and exactly maximizes this bound through a Kruskal-style greedy algorithm.We further establish a boundary-preservation guarantee for ORGC under a forest-rank separation condition.Experiments on structural fidelity, graph classification, molecular regression, and runtime scaling show that ORGC preserves graph structure and downstream utility while remaining efficient.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Ollivier-Ricci curvature, Graph Coarsening, Wasserstein Distance

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_W6JiOpenReview ↗
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
  1. ORGC provides a simple but interesting method based on curvature-guided greedy contraction.

  2. The paper introduces an RGC objective and establishes greedy optimality for its lower bound and a conditional boundary-preservation guarantee.

  3. ORGC achieves strong structural fidelity and competitive downstream performance compared with the evaluated baselines.

Critical weaknesses
  1. 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.

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

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

  4. 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
  1. Can ORGC be practically used to accelerate GNN training for node or link level tasks?

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

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

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 ff 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.
AuthorsOpenReview ↗

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.

MethodCoarsening costTraining costTotal costAccuracy
FULL0 / 0552.69 / 101.57552.7 / 101.686.20 / 48.90
ORGC12.17 / 11.9557.79 / 30.1670.0 / 42.181.48 / 65.62
VEGC69.29 / 71.0868.59 / 38.93137.9 / 110.055.67 / 44.54
VNGC13.57 / 13.4569.69 / 33.9983.3‾\underline{83.3} / 47.4‾\underline{47.4}81.10‾\underline{81.10} / 58.91‾\underline{58.91}

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 α,h\alpha,h, a connected unweighted simple graph, and 1≤n<N1\le n<N, write JForestJ_{\mathrm{Forest}} for the RGC of ORGC's output partition and J⋆J^\star for the optimal RGC. Our RGC Optimality Gap Bound (Section 3.4 Theorem 4 Lines 303–323) constructs an upper bound J‾Forest\overline J_{\mathrm{Forest}} on J⋆J^\star and a lower bound J‾Forest\underline J_{\mathrm{Forest}} on JForestJ_{\mathrm{Forest}}, satisfying

0≤J⋆−JForest≤J‾Forest−J‾Forest.0\le J^\star-J_{\mathrm{Forest}}\le \overline J_{\mathrm{Forest}}-\underline J_{\mathrm{Forest}}.

Thus, J‾Forest−J‾Forest≤ε\overline J_{\mathrm{Forest}}-\underline J_{\mathrm{Forest}}\le\varepsilon guarantees additive ε\varepsilon 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 J‾Forest\overline J_{\mathrm{Forest}} 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 J‾Forest−J‾Forest\overline J_{\mathrm{Forest}}-\underline J_{\mathrm{Forest}}, actual gap J⋆−JForestJ^\star-J_{\mathrm{Forest}}, 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 2×10−82\times10^{-8}. Each depth is evaluated against its own objective.

DepthRetentionJForestJ_{\mathrm{Forest}}J⋆J^\starBoundGapMass (%)Optima
ORGC-d130%0.3691370.4036750.0968580.03453791.44%19/58
50%0.3894000.4163300.0774210.02693093.53%19/58
70%0.4318630.4451550.0215530.01329297.01%37/58
ORGC-d230%0.4557780.4787590.0764150.02298295.20%23/58
50%0.4819590.4948700.0558560.01291197.39%25/58
70%0.5218400.5235630.0083620.00172299.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.

DepthRetentionRGCREERE
ORGC-d130%2.394.152.31
50%0.591.660.96
70%1.241.571.17
ORGC-d230%0.030.121.69
50%0.391.341.12
70%0.211.161.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.

AuthorsOpenReview ↗

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.

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

The paper proposes a training-free, Ollivier-Ricci Graph Coarsening (ORGC). It is a graph coarsening method that uses Ollivier-Ricci curvature to identify geometrically coherent node contractions. It extends the traditional one-step curvature to depth-h non-backtracking Markov neighborhoods and defines Ricci Geometric Coherence (RGC) as the average pairwise curvature within coarse clusters that are not singleton (Having one element in the set).

Directly optimizing the RGC is combinatorial. Therefore, the authors derive a contraction-forest lower bound and prove that the problem of maximization of it reduces to a maximum-weight forest problem, which is optimally solvable through a Kruskal-style greedy algorithm. They also give a curvature-rank separation based conditional boundary-preservation guarantee.

Authors also perform experiments to test structural fidelity, graph classification, molecular regression, Markov transition consistency, and runtime scaling. ORGC looks promising over aggregate performance against the classical coarsening methods considered in the paper.

Critical strengths

1.⁠ ⁠Proposed method connects a pairwise geometric coherence objective to a tractable edge-selection surrogate. The authors show a global optimality for the surrogate when there is a fixed contraction budget. It also avoids the combinatorial partition search.

2.⁠ ⁠The depth-h non-backtracking stopping measure provides a principled extension of immediate-neighborhood curvature. Authors treat the terminal paths explicitly and the depths 1 and 2 are also compared which makes the formulation very well specified.

3.⁠ ⁠ORGC consistently achieves good empirical performance across several tasks, for eg., it gives the strongest aggregate structural fidelity in evaluations of compressed methods and gives aggregate graph-classification accuracy improvement.

4.⁠ ⁠Supporting diagnostics like markov transition consistency, sensitivity to the stopping parameter, etc. and computational analysis is useful. Larger transport costs are well acknowledged in case of depth-2.

Critical weaknesses

1.⁠ Proposition 1 is correct, but maximizing the forest lower bound doesnt necessarily maximize RGC. Different optimal forests can have significantly different RGC values, making tie-breaking relevant. Appendix B.4 does provide ranking correlations, but the approximation quality is still unclear. Paper decision maybe pushed up, if the approximation quality is shown to be good enough.

2.⁠ ⁠Algorithm 1 combines curvature-based scoring with a standard Kruskal-style contraction procedure. Comparing the same procedure using simpler scores, such as common-neighbor similarity or Forman-Ricci curvature, would show if the Ollivier-Ricci curvature itself is causing the improvements.

3.⁠ ⁠The paper talks about the ORC-Pool but does not evaluate it. although we understand that its different pooling formulation makes direct comparison difficult.

4.⁠ ⁠Appendix B.6 uses an unnormalized assignment matrix in the lifted Laplacian, which makes the reconstruction error sensitive to cluster sizes. It would be useful to show if the conclusions still remain similar with normalized lifting and clarify how RGC is evaluated for disconnected baseline clusters.

Questions for authors

1.⁠ You should show how sensitive are ORGC’s output partitions and eventually the downstream results to tie-breaking between equal-curvature edges? Can you compare greedy optimization with exact RGC maximization on small graphs?

2.⁠ ⁠As suggested in the weakness section, you should experimentally show the performance of the kruskal procedure that is proposed when olliver-ricci curvature is replaced by simpler local similarity or curvature measures, under the same compression budget.

3.⁠ ⁠What cross-validation protocol is used for NetLSD-1NN classification, and how are you statistically evaluating the aggregate improvements that are reported?

4.⁠ ⁠Are the structural fidelity conclusions robust to an orthonormal or cluster-size-normalized Laplacian lift? You should clarify how was RGC evaluated for baseline partitions that contain disconnected clusters?

8 comments
AuthorsOpenReview ↗

Response to Reviewer yh83 (Part 1 / 2)

We thank the reviewer for acknowledging ORGC's geometric objective and empirical performance. We provide a point-by-point response to your concerns below and have incorporated the necessary revisions into the paper. (Changes are highlighted in blue in the updated PDF.)

Q1: Gap to the optimum.

Thank you for raising this issue. We agree that ranking correlations alone do not quantify the approximation gap, so we have added a comparison against exact RGC maximization. We enumerate all connected partitions at each fixed budget on 58 connected graphs with at most 12 nodes from six classification datasets. We evaluate d1 and d2 against the RGC objective at their respective depths.

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 2×10−82\times10^{-8}.

DepthRetentionMean RGCMean optimal RGCMass (%)Optimal solutions (%)
ORGC-d130%0.369140.4036791.4432.76 (19/58)
50%0.389400.4163393.5332.76 (19/58)
70%0.431860.4451697.0163.79 (37/58)
ORGC-d230%0.455780.4787695.2039.66 (23/58)
50%0.481960.4948797.3943.10 (25/58)
70%0.521840.5235699.6786.21 (50/58)

ORGC attains scores close to the optimum and reaches an exact optimum on a substantial fraction of the graphs. Theorem 4 further provides a computable RGC optimality-gap bound (Section 3.4, Lines 304–320).

Q2: Tie sensitivity.

The original algorithm does not use a specialized tie-breaking strategy. Different orderings of tied edges can yield different contractions. We therefore conducted five small score-perturbation runs on the same 58 connected graphs used in the exact comparison, recording RGC, REE, and RE. Relative fluctuation (%) is the range of five cross-graph means divided by their absolute average.

DepthRetentionRGCREERE
ORGC-d130%2.394.152.31
50%0.591.660.96
70%1.241.571.17
ORGC-d230%0.030.121.69
50%0.391.341.12
70%0.211.161.09

All reported relative fluctuations of cross-graph means are below 5%, indicating stability of these aggregate metrics under score perturbations. RGC and REE fluctuate less for d2, supporting the use of broader neighborhood context to reduce sensitivity to tie breaking.

Q3: Score ablations.

We replace curvature with common-neighbor count (CN), Jaccard similarity, or Forman–Ricci curvature in the same Kruskal framework. At 20% retention, the table reports accuracy (%) ↑ / REE ↓; Mean weights datasets equally.

MethodMUTAGPTCPROTEINSMSRCIMDBTumblrMean
ORGC-d184.67/1.64853.10/1.38265.26/0.983‾\underline{0.983}16.69‾\underline{16.69}/1.150‾\underline{1.150}66.28‾\underline{66.28}/0.14750.85/0.43256.14‾\underline{56.14}/0.957‾\underline{0.957}
ORGC-d283.48/1.46755.35/1.11763.85/0.89917.36/1.08366.48/0.152‾\underline{0.152}51.74‾\underline{51.74}/0.463‾\underline{0.463}56.38/0.864
CN83.00/6.49254.96‾\underline{54.96}/5.50265.94‾\underline{65.94}/1.94910.94/3.07363.85/1.51750.13/3.78154.80/3.719
Jaccard83.00/6.49252.96/5.50262.33/1.64714.37/1.81965.71/0.16050.13/3.78154.75/3.234
Forman83.96‾\underline{83.96}/1.87854.30/1.58265.97/3.67210.68/2.49566.04/0.32252.37/1.62055.55/1.928
ORC-Pool78.71/1.595‾\underline{1.595}53.35/1.176‾\underline{1.176}63.46/2.02416.41/1.23865.46/0.40748.35/0.48854.29/1.155

Both ORGC configurations achieve lower REE on all six datasets and higher mean accuracy than the simpler scores.

Q4: ORC-Pool comparison.

Our standalone spectral adaptation of ORC-Pool [1] uses Ricci flow to adjust edge weights, then spectral embedding and K-means to form a hard partition at the prescribed budget. It is evaluated with NetLSD–1NN and REE, without training a full GNN pooling layer. Results at 20% retention are shown in the table in Q3.

ORGC leads in most comparisons and both means. We also include GPC and KGPC [2] in Appendix C.2.1 (Lines 1278–1295).

AuthorsOpenReview ↗

Response to Reviewer yh83 (Part 2 / 2)

Q5: Cross-validation and significance.

We follow the classification framework in [3]. Each graph is a sample, represented by a 250-dimensional NetLSD descriptor of its coarse graph and classified using Euclidean 1NN. We average accuracy over stratified ten-fold cross-validation, repeat the complete procedure with 10 random seeds, and report the mean and sample standard deviation of the 10 run-level accuracies.

To assess the statistical significance of the accuracy gains, we apply two-sided paired tt-tests to the equally weighted mean accuracy across the six fixed datasets, pairing methods by run index over 10 runs. Both ORGC-d1 and ORGC-d2 achieve significantly higher macro-average accuracy than each of the five baselines (p<0.01p<0.01 in all 10 comparisons; Appendix D.6, Lines 1587–1603).

Q6: Normalized reconstruction error.

Thank you for the suggestion. We compare reconstruction error under cluster-size-normalized lifting V=QS−1V=QS^{-1}, where QQ is the assignment matrix and SS contains cluster sizes on its diagonal: $ \operatorname{RE}_{\mathrm{size}}=\frac1N\left|L-VL_cV^\top\right|_F^2. $ The table uses 20% node retention; lower values are better.

MethodMUTAGPTCPROTEINSMSRCIMDBMean
ORGC-d11.28401.34301.21651.11841.05441.2033
ORGC-d21.28571.34081.21451.11461.05411.2019
VNGC1.41791.45231.23591.16631.13411.2813
VEGC1.42351.45761.24101.17791.08641.2773
MGC1.26621.32151.18551.12921.08511.1975
SGC1.34651.35801.22431.15781.05221.2278
KGC1.37941.41351.22641.15821.03531.2426

ORGC yields lower reconstruction error than most baselines under this metric, but has no clear overall advantage over MGC. ORGC uses local transport geometry to guide connected contractions without explicitly incorporating spectral information, and may therefore not achieve optimal performance on every spectral metric. However, the complementary results on reconstruction, classification, REE, and local Markov-transition preservation support ORGC’s value as a geometric coarsening method. We have added these results and discussion in Appendix D.4 (Lines 1517–1543). Further work will investigate the connection between geometric preservation and spectral properties.

Q7: RGC of Disconnected clusters.

We compute curvature using shortest-path distances in the original graph, allowing paths to pass through nodes outside a cluster. Pairs that are unreachable in the original graph are assigned zero curvature. We retain each method’s original partition and do not recompute shortest paths within clusters. RGC first averages over all unordered node pairs within each cluster, including these zeros, and then averages equally over non-singleton clusters.

ORGC’s theoretical results concern connected clusters; the above rule is the common evaluation convention for all methods. We have added this discussion in Appendix A.6 (Lines 844–852).

In summary, we hope that your concerns are resolved by our response, helping you reconsider our paper. Feel free to contact us if there are any other questions.

References

[1] Graph Pooling via Ricci Flow. 2024.

[2] Gromov-Wasserstein Graph Coarsening. 2026.

[3] A Gromov-Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening. 2023.

AuthorsOpenReview ↗

Gentle Reminder

Dear Reviewer yh83,

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.

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

The paper proposes an Ollivier-Ricci Graph Coarsening: a method that coarsens the graph based on Ollivier-Ricci curvature (ORC) of every connected node pair. ORC serves as a metric for quantifying structural similarity between connected nodes. ORC is computed from the Wasserstein distance between the representations of nodes obtained from lazy random walks that characterize the coherence Markov geometry. High ORC implies high structural similarity between the node pair and, hence, that the pair can be merged into a single coarse node. Ricci Geometric Coherence is defined as a function of ORC that quantifies coherence within a cluster, with higher values indicating that the merged nodes within a cluster are structurally compatible. The objective is then to find the target-size graph partition that maximizes the average RGC across clusters. An efficient algorithm for solving this combinatorial problem is proposed, and its optimality is shown. Empirical results are present.

Critical strengths

The idea of coarsening based on Markov geometry is appealing and intuitively clear Theoretically grounded method with an optimal algorithm for RGC lower bound estimation

Critical weaknesses

Many variables are not formally defined, and theoretical results are left without interpretation, which obstructs understanding. Baselines are not described A comparison against a recent relevant baseline (Taveras et al., 2026) cited in the introduction is missing. Graphs are on a small scale, which undermines their practical utility.

Questions for authors

How much runtime gain does ORGC introduce over the FULL baseline? What advantages does ORGC have over approximate Gromov-Wasserstein coarsening methods? What are the disadvantages?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Naqw

We appreciate the reviewer's positive assessment regarding the Markov-geometric coarsening approach and the theoretical foundation of our work. Please find our responses to your questions below, along with corresponding edits in the revised manuscript. (Changes are highlighted in blue in the updated PDF.)

Q1: Notation and presentation.

Thank you for the suggestion. We added a notation table and definitions of the node budget, assignment matrix, and depth-dependent neighborhood distributions (Appendix A.1, Lines 711–736). We also clarify Kruskal optimality for the forest lower bound and sufficient conditions for boundary preservation (Section 3.4, Lines 255–300), and distinguish ORGC from baseline methods (Appendix D.1, Lines 1406–1427).

Q2: Additional baselines.

We compare GPC, KGPC [1], and ORC-Pool [2] at 20% retention using NetLSD–1NN classification and REE. Cells report accuracy (%) ↑ / REE ↓.

MethodMUTAGPTCPROTEINSMSRCIMDBTumblrMean
ORGC-d184.67/1.64853.10/1.38265.26‾\underline{65.26}/0.983‾\underline{0.983}16.69‾\underline{16.69}/1.150‾\underline{1.150}66.28/0.14750.85‾\underline{50.85}/0.43256.14‾\underline{56.14}/0.957‾\underline{0.957}
ORGC-d283.48‾\underline{83.48}/1.46755.35‾\underline{55.35}/1.11763.85/0.89917.36/1.08366.48/0.152‾\underline{0.152}51.74/0.463‾\underline{0.463}56.38/0.864
GPC80.26/5.22255.36/4.86361.90/4.04915.85/2.20964.72/0.43450.00/1.70754.68/3.081
KGPC82.05/2.54654.98/2.53565.61/1.14816.27/1.27066.44‾\underline{66.44}/0.22847.29/1.82855.44/1.593
ORC-Pool78.71/1.595‾\underline{1.595}53.35/1.176‾\underline{1.176}63.46/2.02416.41/1.23865.46/0.40748.35/0.48854.29/1.155

ORGC achieves lower REE in most comparisons and higher mean accuracy than the listed baselines, supporting both spectral preservation and classification performance.

Q3: Large-graph efficiency.

On small graphs, the initial coarsening cost can offset downstream savings, so an end-to-end advantage over FULL may be limited. Our original experiments focus on graph-property preservation, showing advantages in structural fidelity and mean classification accuracy over other coarsening methods. To further evaluate efficiency, we added node representation learning and classification experiments on a large real graph, reporting coarsening and training costs separately.

We use PubMed (19,717 nodes), 30% retention, and ORGC-d1. Following official configurations, GRACE uses attributes for contrastive learning [3], while GraphSAGE uses node-ID embeddings for structure-only learning [4]. Logistic-regression evaluation uses shared splits across methods. The table reports three-run means for GRACE / GraphSAGE (costs in seconds, accuracy in %), excluding FULL from ranking.

MethodCoarsening costTraining costTotal costAccuracy
FULL0 / 0552.69 / 101.57552.7 / 101.686.20 / 48.90
ORGC12.17 / 11.9557.79 / 30.1670.0 / 42.181.48 / 65.62
VEGC69.29 / 71.0868.59 / 38.93137.9 / 110.055.67 / 44.54
VNGC13.57 / 13.4569.69 / 33.9983.3‾\underline{83.3} / 47.4‾\underline{47.4}81.10‾\underline{81.10} / 58.91‾\underline{58.91}

Including coarsening, ORGC is 7.90× / 2.41× faster than FULL and more accurate at lower total cost than the listed coarsening baselines. Coarse-graph reuse amortizes construction costs across runs or compatible tasks.

Q4: GW comparison.

ORGC guides contraction through local neighborhood transport, while GW-based methods globally match graph distances, capturing different geometric properties. Greater depth broadens ORGC’s context at extra cost. Approximate GW methods may deviate from the exact optimum, and spectral distances used by methods such as KGC may align less closely with shortest-path geometry.

To evaluate geometric preservation, we added a numerical shortest-path GW comparison with KGC, GPC, and KGPC on shared connected samples from five datasets at 50% retention, matching actual node budgets and assigning unreachable pairs a common large finite distance MM.

MethodMUTAGPTCPROTEINSMSRCIMDBMean
KGC2.08001.82982.70891.22490.49851.6684
GPC2.40251.79992.43641.34210.32261.6607
KGPC1.6046‾\underline{1.6046}1.46911.69941.12740.35731.2516
ORGC-d11.67651.3314‾\underline{1.3314}1.3950‾\underline{1.3950}1.0136‾\underline{1.0136}0.35811.1549‾\underline{1.1549}
ORGC-d21.53121.29141.22320.99350.3566‾\underline{0.3566}1.0792

ORGC achieves lower GW in most comparisons, supporting geometric preservation through local curvature.

In summary, we hope the above response resolves your concerns and solidifies your support for our paper in the following discussion phases. Thanks again for your consideration.

References

[1] Gromov-Wasserstein Graph Coarsening. 2026.

[2] Graph Pooling via Ricci Flow. 2024.

[3] Deep Graph Contrastive Representation Learning. 2020.

[4] Inductive Representation Learning on Large Graphs. 2017.

I thank the authors for clarifying these points. I remain positive about this paper.

We sincerely thank you for your recognition of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.