Pith. sign in

REVIEW 3 major objections 3 minor 81 references

The paper claims a curvature paradox: sparse graphs cannot be positively curved and spectrally expanding at once, and that this unifies oversmoothing and oversquashing as poles of one spectrum.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 04:54 UTC pith:YBJAKX5X

load-bearing objection Ambitious GNN-curvature framework whose two load-bearing theorems don't survive simple checks; the empirical ideas might be worth a look, but the theory needs major repair. the 3 major comments →

arxiv 2607.22381 v1 pith:YBJAKX5X submitted 2026-07-24 cs.LG cs.SIstat.ML

Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature

Rachid Caich , Yassine Abbahaddou This is my paper
classification cs.LG cs.SIstat.ML MSC 05C8168T0760J10
keywords entropic curvaturegraph neural networksoversmoothingoversquashingexpansion paradoxWasserstein geodesicstransport-entropy inequalitygraph rewiring
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Entropic curvature is a global, transport-based analogue of Ricci curvature for graphs, defined by convexity of entropy along W1-Wasserstein geodesics. The paper introduces a computable weak proxy κw that provably lower-bounds it, and shows that positive κw forces a Poincaré inequality, a transport-entropy generalization bound, and—through an expansion paradox—the impossibility of simultaneously having sparsity, strong spectral expansion, and positive curvature in large graphs. A sympathetic reader should care because it turns two separate GNN failure modes, oversmoothing and oversquashing, into opposite ends of a single geometric trade-off, and yields practical mechanisms (an aggregator, a positional encoding, and a rewiring rule) that follow directly from the theory.

Core claim

The central claim is that a single global quantity, weak entropic curvature κw(u) = −2 log H_L(u, S2(u)), controls both oversmoothing and oversquashing in GNNs. κw measures how easily probability mass can be redistributed within two hops; it lower-bounds the true entropic curvature (Theorem 3.3). From positive κw the paper derives a Poincaré-type inequality for graph signals (Theorem S.1), a transport-entropy bound on the train-test gap (Theorem 5.2), and the Expansion Paradox (Theorem 4.2): any sequence of sparse graphs with curvature bounded below by a>0 on all but o(n) vertices must have a positive density of Laplacian eigenvalues accumulating at 1, so it cannot be a strong spectral expan

What carries the argument

The load-bearing object is the weak entropic curvature proxy κw(u) = −2 log H_L(u,S2(u)), where H_L is a supremum over probability weights α on the one-hop neighborhood of a product over two-hop geodesic paths, weighted by relative path weights ℓ. This local functional converts displacement convexity of entropy into a tractable optimization over the simplex; Theorem 3.3 makes it a certified lower bound on the global entropic curvature κ. The proof chain then runs: κw>0 ⇒ modified log-Sobolev inequality (Lemma J.1) ⇒ Poincaré inequality (Theorem S.1) ⇒ Liouville property / zero entropy on local weak limits (Theorem I.14) ⇒ poor spectral expansion (Theorem I.15). This is the mechanism behind t

Load-bearing premise

The argument's load-bearing premise is that positive weak entropic curvature implies a modified log-Sobolev inequality; this bridge relies on an unproved first-variation estimate and cancellation of transport terms, and if it fails the zero-entropy step of the expansion paradox collapses.

What would settle it

Compute κw and the second eigenvalue λ2 on a sequence of bounded-degree Ramanujan graphs: if κw stays bounded above zero while λ2 remains below 1, the expansion paradox is false. More directly, check the first-variation estimate in Lemma J.1 numerically on a small graph; if the implied MLSI constant is much smaller than κw/2, the bridge to zero entropy fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Positive curvature gives a quantitative oversmoothing guarantee: feature variance decays at rate at most 1/κw relative to one-sided Dirichlet energy.
  • The expansion paradox says that any sparse graph with good mixing must contain negatively curved regions, pinpointing where oversquashing happens; rewiring to raise curvature will tend to lower expansion.
  • Generalization gap scales like sqrt(2 Ent/κw) under positive curvature, and stays finite under negative curvature with an exponential penalty in diameter.
  • Adding a midpoint edge for a poorly supported two-hop path provably non-decreases local κw, giving a per-step certificate for rewiring.
  • Curvature-aware aggregation (E-Gate) and encodings (ENT) transfer the geometric signal into accuracy gains on heterophilic benchmarks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the paradox is right, the oversmoothing–oversquashing trade-off is structural: any rewiring that raises spectral expansion lowers the curvature certificate, so depth and graph surgery are constrained by the same quantity. This suggests that adaptive per-node temperature or early stopping, rather than more rewiring, may be the only way to balance both.
  • Because κw is defined relative to a reference measure m, the framework carries a hidden design choice; learning m to maximize curvature would amount to learning a node weighting, which the paper leaves open.
  • The generalization bound needs overlapping train/test supports (finite relative entropy); on standard disjoint splits the bound is infinite, so the practical claim is restricted to soft-split or smoothed settings.
  • A natural stress test: compute κw for Ramanujan graphs; if any bounded-degree expander family has κw ≥ a>0, the paradox's zero-entropy step needs revisiting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes a global entropic curvature for graphs, defined by displacement convexity of entropy along W1-geodesics, and a computable local proxy κw. From κw it derives a Poincaré-type inequality (Theorem S.1), a transport–entropy generalization bound (Theorems 5.2 and 5.3), an 'expansion paradox' stating that sparse, strongly expanding graphs cannot have positive entropic curvature (Theorem 4.2), and a rewiring rule (MCR, Theorem 4.3). The theory is connected to GNNs through an E-Gate aggregator, an ENT structural encoding, and MCR, evaluated on node- and graph-classification benchmarks.

Significance. If the theoretical results were correct, the paper would offer a genuinely unified geometric explanation of oversmoothing and oversquashing, with a tractable curvature proxy and practical GNN mechanisms. The empirical study is extensive for a theory paper, and the idea of using two-hop transport redundancy as a curvature proxy is attractive. However, the three main theoretical pillars — the MLSI/Poincaré bridge, the expansion paradox, and the rewiring monotonicity proof — are either false as stated or rest on unproved continuous-space machinery. Since these pillars are load-bearing for the paper's central claims, the contribution in its current form is not established.

major comments (3)
  1. [Appendix J, Theorem S.1] The Poincaré-type inequality is false as stated. For the 4-cycle with uniform measure and generator L0, κw = 2 ln 2 ≈ 1.386. Taking f = (1,0,0,0), one computes Var_μ(f) = 3/16 and the one-sided Dirichlet energy E(f) = 1/4, so Var/E = 0.75, which exceeds 1/κw ≈ 0.721. Thus the claimed inequality Var ≤ (1/κw)E fails on a finite, connected, positively curved graph. The proof in Lemma J.1 also contains a sign error: Young's inequality produces a positive term (κw/2)Σν0(u)(Σw d(u,w)π(w|u))^2, which cannot cancel the curvature-supplied −(κw/2)W1^2 term; the 'cancellation of transport-cost terms' is asserted, not derived. Since Theorem I.14 and hence Theorem 4.2 rely on Theorem S.1, the expansion paradox and the unifying oversmoothing/oversquashing claim are not established.
  2. [Appendix L, Theorem 4.3] The pointwise dominance argument for the rewiring monotonicity is incorrect. For a target w with k_w = 1 and after adding one midpoint k+_w = 2, the AM-GM-optimal alpha gives f_w(α*) = 1 but f+_w(α*) = 2·(1/1)^{2/2} = 2, so f+_w(α*) ≤ f_w(α*) fails. The displayed chain k+_w·(1/k_w)^{2/k+_w} ≤ ... ≤ 1/k_w is algebraically wrong in this case. Consequently the claimed proof that adding two-hop geodesics non-decreases κw is unsupported. The theorem might be salvageable by a different argument, but as written the derivation is not sound.
  3. [Appendix G, Theorem 5.3] The negative-curvature generalization bound is derived by importing continuous-space Benamou–Brenier formalism, Fisher information, HWI inequalities, and a logarithmic Sobolev constant λ≈K/(2(e^{KD²/8}−1)) without any discrete derivation. The step W1 ≤ W2 and the substitution into the discrete entropy are formal; no justification is given that these continuous identities hold on finite graphs with the W1-geodesic definition used for κw. This is a load-bearing gap because Theorem 5.3 is one of the three main theoretical contributions, and the proof as written is not a proof in the discrete setting.
minor comments (3)
  1. [Section 5, Remark 5.1] The finiteness condition requires overlapping support of µtrain and µtest, which is not the standard disjoint-split node classification setting. The paper acknowledges this and uses overlapping splits in Figure 2, but the scope of the main generalization theorems is narrower than the framing suggests.
  2. [Appendix Q] The complexity analysis claims 'smooth concave maximization' for the general objective, but Appendix Q.4 later notes that in the unweighted case the objective can be a quadratic form with an indefinite matrix and that SLSQP 'finds global optima in practice'. The theoretical global-optimality statement is not fully reconciled with the non-concave cases.
  3. [Section 3, Eq. (3)] The notation ]z,W[ and the product over midpoints is nonstandard and could be defined more carefully, especially since the same symbol is used for open intervals in continuous spaces. This makes the formal definition harder to parse.

Circularity Check

0 steps flagged

No significant circularity: central claims are derived from explicit definitions and external prior results; the only self-citation is non-load-bearing.

full rationale

I traced the derivation chain from Definition 3.2. The weak entropic curvature κw is an explicit local functional; Theorem 3.3's lower bound on global κ is deferred to Appendix E and rests on Theorem 2 and eq. (16) of Rapaport–Samson [60], an external source, not on this paper's conclusions. Lemma F.2 derives the transport-entropy inequality from the κw-convexity premise; Theorem 5.2 then applies that inequality with Lipschitz assumptions. The expansion paradox (Theorem 4.2) follows the structure of Salez [62], with a separate bridge theorem (Theorem I.14 / S.1) converting κw>0 into a Poincaré inequality. That bridge is the fragile step: Appendix J asserts a first-variation formula and a cancellation of transport terms without proof, and the inequality appears numerically false on C4. However, that is a correctness/rigor defect, not a circular reduction: the theorem's conclusion is not assumed in its premise, and the failure does not make any fitted parameter masquerade as a prediction. The only self-citation ([1], Abbahaddou) appears in the definitional remark that L acts as a graph shift operator, alongside two independent citations; nothing in the paradox, generalization bound, or rewiring theorem depends on it. No fitted parameter is hidden in κw; the empirical generalization experiment explicitly acknowledges its confound. Thus no load-bearing step reduces to its own input.

Axiom & Free-Parameter Ledger

1 free parameters · 5 axioms · 1 invented entities

The chain depends on imported characterizations from Samson and Salez, plus an unproved discrete MLSI/LSI step. The only fitted parameter in the architecture is the E-Gate temperature τ, which is not central to the theoretical claims.

free parameters (1)
  • E-Gate temperature τ = learned (initialized at 1.0; no final values reported)
    The scalar τ modulates the curvature gate and is learned during training; ablations show strong sensitivity (τ fixed at 1.0 drops Cora accuracy by 12.9 points), so it is a fitted component of the proposed architecture.
axioms (5)
  • domain assumption The Lott–Sturm–Villani characterization of Ricci curvature via W2-displacement convexity of entropy carries over to finite graphs with W1-geodesics.
    Section 3 and Definition 3.1; the paper relies on [60] and [46] for this transfer, but does not prove the discrete W1 version itself.
  • domain assumption Samson's discrete entropic-curvature characterization (Theorem 2 of [60]) and the inequality sup_S K(S) ≤ sup_z H_L(z,S2(z)) hold under the paper's graph assumptions.
    This is the entire content of Theorem 3.3; imported from prior work, not re-derived.
  • ad hoc to paper Positive κw implies a modified log-Sobolev / Poincaré inequality with the one-sided Dirichlet energy, as stated in Theorem S.1.
    Appendix J gives only a sketch with an unjustified first-variation estimate; this lemma is the bridge from curvature to the Liouville property in Theorem 4.2.
  • ad hoc to paper In Theorem 5.3, a continuous-space logarithmic Sobolev constant λ≈K/(2(e^{KD²/8}−1)) applies to finite graphs under W1-geodesics.
    Appendix G cites 'standard metric-measure theory' without a discrete derivation or a reference; the exponential diameter dependence is not established for graphs.
  • domain assumption The relative entropy Ent_{μtrain}(μtest) is finite, requiring overlapping or smoothed train/test supports.
    Remark 5.1 concedes that standard disjoint splits have infinite entropy; the generalization theorems therefore do not apply to the main node-classification setup used in the experiments.
invented entities (1)
  • Weak entropic curvature κw no independent evidence
    purpose: Local two-hop proxy claimed to lower-bound the global entropic curvature and to control oversmoothing, oversquashing, and generalization.
    It is a new mathematical quantity built from prior entropic-curvature theory. The paper's empirical support is correlational and the authors acknowledge a confound in the SBM experiment.

pith-pipeline@v1.3.0-alltime-deepseek · 36684 in / 11368 out tokens · 136395 ms · 2026-08-01T04:54:33.958399+00:00 · methodology

0 comments
read the original abstract

Curvature notions on graphs, particularly Ollivier-Ricci and Forman, have emerged as powerful tools for addressing fundamental issues in Graph Neural Networks (GNNs) such as oversmoothing and oversquashing, but rely almost exclusively on local edge-level comparisons and therefore fail to certify how information actually propagates over long distances. We introduce Entropic Curvature, a global, transport-based curvature obtained by extending the Lott-Sturm-Villani framework to graphs through the displacement convexity of entropy along Wasserstein geodesics. We define a tractable Weak Entropic Curvature proxy that lower-bounds the global entropic curvature, and from it derive (i) a Poincare-type inequality controlling oversmoothing, (ii) a transport-entropy generalization bound, and (iii) an expansion paradox proving that sparsity, strong spectral expansion, and positive entropic curvature cannot coexist in large graphs, unifying oversmoothing and oversquashing as opposite ends of a single curvature spectrum. We translate the theory into three practical mechanisms, the E-Gate aggregator, the ENT structural encoding, and Midpoint-Completion Rewiring (MCR), and benchmark them against SDRF, FoSR, BORF, LCP, and Graph Ricci Flow on six node-classification benchmarks, and graph-classification.

Figures

Figures reproduced from arXiv: 2607.22381 by Rachid Caich, Yassine Abbahaddou.

Figure 1
Figure 1. Figure 1: Spectral gap improvement ∆λ2 under curvature-guided edge addition (10 edges, 10 seeds, shaded ±1 std). MCR (ours) consistently outperforms ORC and FRC across all six graph families. Curvature-Based Rewiring. The expansion paradox shows that sparse graphs cannot simultaneously be strongly expanding and positively curved in the large-graph regime. This does not mean, however, that negative curvature is fixed… view at source ↗
Figure 2
Figure 2. Figure 2: Empirical correlation between κ¯w and the GNN generalization gap on SBM graphs. A central question in GNN theory is how well a model trained on one part of a graph transfers to an￾other, especially when the training and test nodes occupy different re￾gions of the topology [70]. We for￾malize this discrepancy by viewing the training and test sets as probabil￾ity measures µtrain and µtest on V. The generaliz… view at source ↗
Figure 5
Figure 5. Figure 5: Under the L0 generator and uniform measure, the weak entropic curvature directly reflects the density of the local neighborhood through the following structural characterization, Theorem A.1 (Motzkin–Straus Type Identity; Proof in Appendix D). Let u be a node in G and assume that B2(u) satisfies the condition that any v ∈ S2(u) shares exactly two midpoints with u. Then, HL0 (z, S2(u)) = 1 − 1 g(B2(u)). (5)… view at source ↗
Figure 3
Figure 3. Figure 3: Local weak entropic curvature across various graph motifs. [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Characterization of discrete geometric regimes via Weak Entropic Curvature (κw) under the uniform generator L0. (a) Spherical (κw > 0): High local clustering results in positive curvature, satisfying the lower bound κw(z) ≥ −2 log(1 − 1 deg(z) ). (b) Flat (κw = 0): The Euclidean grid exhibits zero curvature, corresponding to a local functional value HL0 (z, S2(z)) = 1. (c) Hyperbolic (κw < 0): Tree-like st… view at source ↗
Figure 5
Figure 5. Figure 5: A positively curved motif where the entropic functional serves as a signature of local [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Empirical Convergence of Weak Entropic Curvature Optimization [PITH_FULL_IMAGE:figures/full_fig_p035_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Geometric reconfiguration via mass distribution. Changing the reference measure m fundamentally alters the graph’s diffusion dynamics. The choice of the reference measure m and the resulting generator L is a defining feature of the entropic curvature framework, as it dictates the geometry of the mass across the graph. Unlike standard curvature metrics that are fixed by the adjacency matrix, our framework a… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

81 extracted references · 5 linked inside Pith

  1. [1]

    Which graph shift operator? a spectral answer to an empirical question

    Yassine Abbahaddou. Which graph shift operator? a spectral answer to an empirical question. arXiv preprint arXiv:2602.06557, 2026

    arXiv 2026

  2. [2]

    Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

    Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks.Reviews of modern physics, 74(1):47, 2002

    2002

  3. [3]

    Beyond weisfeiler– lehman with local ego-network encodings.Machine Learning and Knowledge Extraction, 5(4):1234–1265, 2023

    Nurudin Alvarez-Gonzalez, Andreas Kaltenbrunner, and Vicenç Gómez. Beyond weisfeiler– lehman with local ego-network encodings.Machine Learning and Knowledge Extraction, 5(4):1234–1265, 2023

    2023

  4. [4]

    Spectra of cayley graphs.Journal of Combinatorial Theory, Series B, 27(2):180– 189, 1979

    László Babai. Spectra of cayley graphs.Journal of Combinatorial Theory, Series B, 27(2):180– 189, 1979

    1979

  5. [5]

    Constant curvature graph convo- lutional networks

    Gregor Bachmann, Gary Bécigneul, and Octavian Ganea. Constant curvature graph convo- lutional networks. InInternational conference on machine learning, pages 486–496. PMLR, 2020

    2020

  6. [6]

    Diffusions hypercontractives

    Dominique Bakry and Michel Émery. Diffusions hypercontractives. InSéminaire de Probabilités XIX 1983/84: Proceedings, pages 177–206. Springer, 2006

    1983

  7. [7]

    Bauer, B

    F. Bauer, B. Hua, and S.-T. Yau. Davies-Gaffney-Grigor’yan lemma on graphs.Comm. Anal. Geom., 23(5):1031–1068, 2015

    2015

  8. [8]

    Bauer, B

    F. Bauer, B. Hua, and S.-T. Yau. Sharp Davies-Gaffney-Grigor’yan lemma on graphs.Math. Ann., 368(3-4):1429–1437, 2017

    2017

  9. [9]

    Bauer, Y

    F. Bauer, Y . Horn P. Lin, G. Lippner, D. Mangoubi, and S.-T. Yau. Li-Yau inequality on graphs. J. Differential Geom., 99(3):359–405, 2015

    2015

  10. [10]

    Laplacian eigenmaps for dimensionality reduction and data representation.Neural computation, 15(6):1373–1396, 2003

    Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation.Neural computation, 15(6):1373–1396, 2003

    2003

  11. [11]

    A computational fluid mechanics solution to the monge-kantorovich mass transfer problem.Numerische Mathematik, 84(3):375–393, 2000

    Jean-David Benamou and Yann Brenier. A computational fluid mechanics solution to the monge-kantorovich mass transfer problem.Numerische Mathematik, 84(3):375–393, 2000

    2000

  12. [12]

    Unimodular random trees.Ergodic Theory Dynam

    Itai Benjamini, Russell Lyons, and Oded Schramm. Unimodular random trees.Ergodic Theory Dynam. Systems, 35(2):359–373, 2015

    2015

  13. [13]

    The aldous–lyons conjecture i: Subgroup tests.arXiv preprint arXiv:2408.00110, 2024

    Lewis Bowen, Michael Chapman, Alexander Lubotzky, and Thomas Vidick. The aldous–lyons conjecture i: Subgroup tests.arXiv preprint arXiv:2408.00110, 2024

    Pith/arXiv arXiv 2024

  14. [14]

    A note on over-smoothing for graph neural networks.arXiv preprint arXiv:2006.13318, 2020

    Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks.arXiv preprint arXiv:2006.13318, 2020

    Pith/arXiv arXiv 2006

  15. [15]

    Graph neural ricci flow: Evolving feature from a curvature perspective

    Jialong Chen, Bowen Deng, Chuan Chen, Zibin Zheng, et al. Graph neural ricci flow: Evolving feature from a curvature perspective. InThe Thirteenth International Conference on Learning Representations, 2025

    2025

  16. [16]

    Chung, Y

    F. Chung, Y . Lin, and S.-T. Yau. Harnack inequalities for graphs with nonnegative Ricci curvature.J. Math. Anal. Appl., 415(1):25–32, 2014

    2014

  17. [17]

    Chung and S.-T

    F. Chung and S.-T. Yau. A strong Harnack inequality for graphs.Comm. Anal. Geom., 25(3):557–588, 2017

    2017

  18. [18]

    American Mathematical Soc., 1997

    Fan RK Chung.Spectral graph theory, volume 92. American Mathematical Soc., 1997

    1997

  19. [19]

    Liouville properties.arXiv preprint arXiv:1902.09366, 2019

    Tobias Holck Colding and William P Minicozzi II. Liouville properties.arXiv preprint arXiv:1902.09366, 2019

    Pith/arXiv arXiv 1902

  20. [20]

    A riemannian interpolation inequality à la borell, brascamp and lieb.Inventiones mathematicae, 146(2):219– 257, 2001

    Dario Cordero-Erausquin, Robert J McCann, and Michael Schmuckenschläger. A riemannian interpolation inequality à la borell, brascamp and lieb.Inventiones mathematicae, 146(2):219– 257, 2001. 11

    2001

  21. [21]

    Learning parametrised graph shift operators

    George Dasoulas, Johannes F Lutzeyer, and Michalis Vazirgiannis. Learning parametrised graph shift operators. InInternational Conference on Learning Representations

  22. [22]

    Springer, 1992

    Manfredo Perdigao Do Carmo and J Flaherty Francis.Riemannian geometry, volume 2. Springer, 1992

    1992

  23. [23]

    Graph anisotropic diffusion for molecules

    Ahmed AA Elhag, Gabriele Corso, Hannes Stärk, and Michael M Bronstein. Graph anisotropic diffusion for molecules. InICLR2022 Machine Learning for Drug Discovery, 2022

    2022

  24. [24]

    Graph positional encoding via random feature propagation

    Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. InInternational conference on machine learning, pages 9202–9223. PMLR, 2023

    2023

  25. [25]

    Über die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten.Mathematische Zeitschrift, 17(1):228–249, 1923

    Michael Fekete. Über die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten.Mathematische Zeitschrift, 17(1):228–249, 1923

    1923

  26. [26]

    How powerful are k-hop message passing graph neural networks.Advances in Neural Information Processing Systems, 35:4776–4790, 2022

    Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks.Advances in Neural Information Processing Systems, 35:4776–4790, 2022

    2022

  27. [27]

    Effective structural encodings via local curvature profiles

    Lukas Fesser and Melanie Weber. Effective structural encodings via local curvature profiles. In The Twelfth International Conference on Learning Representations

  28. [28]

    Mitigating over-smoothing and over-squashing using aug- mentations of forman-ricci curvature

    Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using aug- mentations of forman-ricci curvature. InLearning on Graphs Conference, pages 19–1. PMLR, 2024

    2024

  29. [29]

    Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. InICLR Workshop on Representation Learning on Graphs and Manifolds, 2019

    2019

  30. [30]

    Bochner’s method for cell complexes and combinatorial ricci curvature.Discrete & Computational Geometry, 29:323–374, 2003

    Robin Forman. Bochner’s method for cell complexes and combinatorial ricci curvature.Discrete & Computational Geometry, 29:323–374, 2003

    2003

  31. [31]

    Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature

    Robin Forman. Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature. Discrete & Computational Geometry, 29(3):323–374, 2003

    2003

  32. [32]

    Configuring random graph models with fixed degree sequences.Siam Review, 60(2):315–355, 2018

    Bailey K Fosdick, Daniel B Larremore, Joel Nishimura, and Johan Ugander. Configuring random graph models with fixed degree sequences.Siam Review, 60(2):315–355, 2018

    2018

  33. [33]

    Spectra of expansion graphs.The Electronic Journal of Linear Algebra, 6:2–10, 1999

    Shmuel Friedland and Hans Schneider. Spectra of expansion graphs.The Electronic Journal of Linear Algebra, 6:2–10, 1999

    1999

  34. [34]

    On the shift operator, graph frequency, and optimal filtering in graph signal processing.IEEE Transactions on Signal Processing, 65(23):6303–6318, 2017

    Adnan Gavili and Xiao-Ping Zhang. On the shift operator, graph frequency, and optimal filtering in graph signal processing.IEEE Transactions on Signal Processing, 65(23):6303–6318, 2017

    2017

  35. [35]

    C. Gong, Y . Lin, S. Liu, and S.-T. Yau. Li-Yau inequality for unbounded Laplacian on graphs. Adv. Math., 357:33pp, 2019

    2019

  36. [36]

    Stochastic blockmodels: First steps.Social networks, 5(2):109–137, 1983

    Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps.Social networks, 5(2):109–137, 1983

    1983

  37. [37]

    Ollivier’s ricci curvature, local clustering and curvature-dimension inequalities on graphs.Discrete & Computational Geometry, 51(2):300–322, 2014

    Jürgen Jost and Shiping Liu. Ollivier’s ricci curvature, local clustering and curvature-dimension inequalities on graphs.Discrete & Computational Geometry, 51(2):300–322, 2014

    2014

  38. [38]

    FoSR: First-order spectral rewiring for addressing oversquashing in GNNs

    Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. InThe Eleventh International Conference on Learning Representations, 2023

    2023

  39. [39]

    Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    Diederik P Kingma. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    Pith/arXiv arXiv 2014

  40. [40]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. InInternational Conference on Learning Representations, 2017. 12

    2017

  41. [41]

    John Wiley & Sons, 1996

    Shoshichi Kobayashi and Katsumi Nomizu.Foundations of Differential Geometry, volume 2. John Wiley & Sons, 1996

    1996

  42. [42]

    Curvature graph neural network.Information Sciences, 592:50–66, 2022

    Haifeng Li, Jun Cao, Jiawei Zhu, Yu Liu, Qing Zhu, and Guohua Wu. Curvature graph neural network.Information Sciences, 592:50–66, 2022

    2022

  43. [43]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. InProceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  44. [44]

    Y . Lin, L. Lu, and S.-T. Yau. Ricci curvature of graphs.Tohoku Math. J (2), 63(4):605–627, 2011

    2011

  45. [45]

    Lin and S.-T

    Y . Lin and S.-T. Yau. Ricci curvature and eigenvalue estimate on locally finite graphs.Math. Res. Lett., 17(2):343–356, 2010

    2010

  46. [46]

    Lott and C

    J. Lott and C. Villani. Ricci curvature for metric-measure spaces via optimal transport.Ann. of Math., 169(3):903–991, 2009

    2009

  47. [47]

    Curvature-based clustering on graphs

    Zachary Lubberts, Yu Tian, and Melanie Weber. Curvature-based clustering on graphs. In2024 Joint Mathematics Meetings (JMM 2024). AMS

    2024

  48. [48]

    R. J. McCann. A convexity principle for interacting gases.Adv. Math., 128(1):153–179, 1997

    1997

  49. [49]

    B. Mohar. Isoperimetric numbers of graphs.Journal of Combinatorial Theory, Series B 47(3):274–291, 1989

    1989

  50. [50]

    TUDataset: A collection of benchmark datasets for learning with graphs.ICML 2020 GRL+ Workshop, 2020

    Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs.ICML 2020 GRL+ Workshop, 2020

    2020

  51. [51]

    Maxima for graphs and a new proof of a theorem of turán.Canadian Journal of Mathematics, 17:533–540, 1965

    Theodore S Motzkin and Ernst G Straus. Maxima for graphs and a new proof of a theorem of turán.Canadian Journal of Mathematics, 17:533–540, 1965

    1965

  52. [52]

    Revisiting over-smoothing and over-squashing using ollivier-ricci curvature

    Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pages 25956–25979. PMLR, 2023

    2023

  53. [53]

    Community detection on networks with ricci flow.Scientific reports, 9(1):9984, 2019

    Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow.Scientific reports, 9(1):9984, 2019

    2019

  54. [54]

    Springer, 2006

    Jorge Nocedal and Stephen J Wright.Numerical optimization. Springer, 2006

    2006

  55. [55]

    Ricci curvature of markov chains on metric spaces.Journal of Functional Analysis, 256(3):810–864, 2009

    Yann Ollivier. Ricci curvature of markov chains on metric spaces.Journal of Functional Analysis, 256(3):810–864, 2009

    2009

  56. [56]

    Otto and C

    F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality.J. Funct. Anal., 173(2):361–400, 2000

    2000

  57. [57]

    Master stability functions for synchronized coupled systems.Physical review letters, 80(10):2109, 1998

    Louis M Pecora and Thomas L Carroll. Master stability functions for synchronized coupled systems.Physical review letters, 80(10):2109, 1998

    1998

  58. [58]

    Geom-gcn: Geometric graph convolutional networks

    Hongbin Pei, Bingzhe Wei, Kevin Chen Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. In8th International Conference on Learning Repre- sentations, ICLR 2020, 2020

    2020

  59. [59]

    OUP Oxford, 2003

    Mathew Penrose.Random geometric graphs, volume 5. OUP Oxford, 2003

    2003

  60. [60]

    Criteria for entropic curvature on graph spaces.ArXiv preprint: 2303.15874, 2024

    Martin Rapaport and Paul-Marie Samson. Criteria for entropic curvature on graph spaces.ArXiv preprint: 2303.15874, 2024

    Pith/arXiv arXiv 2024

  61. [61]

    V on Renesse and K.-Th

    M.-K. V on Renesse and K.-Th. Sturm. Transport inequalities, gradient estimates, entropy, and Ricci curvature.Comm. Pure Appl. Math., 58(7):923–940, 2005

    2005

  62. [62]

    Sparse expanders have negative curvature.Geom

    Justin Salez. Sparse expanders have negative curvature.Geom. Funct. Anal, 32:1486–1513, 2022. 13

    2022

  63. [63]

    Entropic curvature on graphs along schrödinger bridges at zero temperature

    Paul-Marie Samson. Entropic curvature on graphs along schrödinger bridges at zero temperature. Probability Theory and Related Fields, 184(3):859–937, 2022

    2022

  64. [64]

    Algorithms, graph theory, and linear equations in laplacian matrices

    Daniel A Spielman. Algorithms, graph theory, and linear equations in laplacian matrices. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, pages 2698–2722. World Scientific, 2010

    2010

  65. [65]

    K.-Th. Sturm. On the geometry of metric measure spaces. I and II.Acta Math., 196(1):65–177, 2006

    2006

  66. [66]

    Towards understanding generalization of graph neural networks

    Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pages 33674–33719. PMLR, 2023

    2023

  67. [67]

    Bronstein

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. InInternational Conference on Learning Representations, 2022

    2022

  68. [68]

    The effectiveness of curvature-based rewiring and the role of hyperparameters in gnns revisited

    Floriano Tori, Vincent Holst, and Vincent Ginis. The effectiveness of curvature-based rewiring and the role of hyperparameters in gnns revisited. InThe Thirteenth International Conference on Learning Representations

  69. [69]

    Scipy 1.0: fundamental algorithms for scientific computing in python.Nature methods, 17(3):261–272, 2020

    Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python.Nature methods, 17(3):261–272, 2020

    2020

  70. [70]

    A manifold perspective on the statistical generalization of graph neural networks

    Zhiyang Wang, Juan Cervino, and Alejandro Ribeiro. A manifold perspective on the statistical generalization of graph neural networks. InForty-second International Conference on Machine Learning

  71. [71]

    The effect of watts-strogatz and barabási-albert graphs on memory formation

    Ethan Wolfe. The effect of watts-strogatz and barabási-albert graphs on memory formation. Master’s thesis, California Polytechnic State University, 2024

    2024

  72. [72]

    Revisiting semi-supervised learning with graph embeddings

    Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. InInternational conference on machine learning, pages 40–48. PMLR, 2016. 14 A Interpreting Weak Entropic Curvature via Local Transport Interpretation of the Local Functional.To provide a geometric interpretation of HL, it is instructive to speci...

    2016

  73. [73]

    •SBM:Stochastic Block Models representing community-structured networks [36]

    Graph Generation:We initialize six distinct random graph models to ensure topological diversity, •Cayley:Dihedral group-based graphs representing highly symmetric structures [4]. •SBM:Stochastic Block Models representing community-structured networks [36]. • Small-World:Watts-Strogatz graphs characterized by high clustering and short path lengths [71]. •R...

  74. [74]

    reasonable

    Statistical Rigor:Each experiment is repeated over 10 different random seeds. We report the mean change in spectral gap, ∆λ2 =λ (t) 2 −λ (0) 2 , where t is the number of added edges. Shaded regions in the figures represent the standard deviation across seeds. C.3 Results and Discussion The results of the edge addition experiment are illustrated in Figure ...

  75. [75]

    Precompute for eachw∈S 2(z)andu∈]z, w[:ℓ(z, u, w)← L(z,u)L(u,w) L(2)(z,w)

  76. [76]

    Define objective functionJ(α)forα∈∆ |S1(z)|: J(α)← P w∈S2(z) L(2)(z, w) Q u∈]z,w[ α(u) L(z,u) 2ℓ(z,u,w)

  77. [77]

    fast-decay

    Solve constrained maximization: H∗ ←sup α J(α)s.t. P u α(u) = 1, α(u)≥0; κ[z]← −2 log(H∗); end if end foreach κw(G)←inf z∈V κ[z]; returnκ, κw(G); M.2 Fast Convergence of the Entropic Optimization To validate the computational tractability of the Weak Entropic Curvature, we empirically analyze the convergence behavior of the underlying optimization problem...

  78. [78]

    • Computation:We compute the exact ORC for every edge (u, v)in the graph using the GraphRicciCurvature library

    Local Curvature Profiles (LCP).Following the standard implementation [ 27], LCP augments node features with statistics derived from the discrete Ollivier-Ricci Curvature (ORC). • Computation:We compute the exact ORC for every edge (u, v)in the graph using the GraphRicciCurvature library. The transport cost is defined based on the shortest path distance be...

  79. [79]

    The positional encoding is formed by the k smallest non-trivial eigenvectors of L

    Laplacian Positional Encodings (LAPE).We compute the graph Laplacian L=I− D−1/2AD−1/2. The positional encoding is formed by the k smallest non-trivial eigenvectors of L. These eigenvectors capture the low-frequency modes of the graph, preserving global distance information

  80. [80]

    The encoding pRWPE u ∈R k is defined by the diagonal entries of the random walk diffusion matrix at various steps: pRWPE u = P1 uu,P 2 uu,

    Random Walk Positional Encodings (RWPE).RWPE captures the structural role of a node by examining the probability of a random walker returning to itself. The encoding pRWPE u ∈R k is defined by the diagonal entries of the random walk diffusion matrix at various steps: pRWPE u = P1 uu,P 2 uu, . . . ,Pk uu ⊤ where P=D −1A is the transition matrix. This encod...

Showing first 80 references.