pith. sign in

arxiv: 2606.21333 · v2 · pith:DZE2MU2Rnew · submitted 2026-06-19 · 💻 cs.LG · cs.AI

Ramanujan Graph Rewiring with Non Negative Resistance Curvature

Hugo Attali , Rachid El Jouhri This is my paper

Pith reviewed 2026-06-26 14:25 UTC · model grok-4.3

classification 💻 cs.LG cs.AI
keywords graph neural networksgraph rewiringRamanujan graphsresistance curvatureover-squashingmessage passingexpander graphstopological bottlenecks
0
0 comments X

The pith

Ramanujan graphs can be rewired onto input graphs to guarantee non-negative resistance curvature and reduce over-squashing in GNN message passing.

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

The paper establishes that suitably chosen Ramanujan graphs ensure non-negative resistance curvature on the rewired result. This curvature property is shown to ease topological bottlenecks that cause over-squashing during iterative information aggregation in graph neural networks. An algorithmic procedure is given that adds Ramanujan edges while keeping the original graph's local neighborhoods intact. Experiments on standard benchmarks report that the resulting graphs outperform nine existing rewiring methods in downstream tasks.

Core claim

Suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow; an algorithmic framework then constructs a Ramanujan rewired graph that preserves the local connectivity of the original graph, and this construction outperforms nine state-of-the-art rewiring techniques on GNN tasks.

What carries the argument

The Ramanujan rewired graph, formed by adding edges drawn from a Ramanujan graph while preserving the original local connectivity, which carries the non-negative resistance curvature property into the input graph.

If this is right

  • Non-negative resistance curvature directly reduces the compression of large neighborhoods into fixed embeddings during message passing.
  • The rewired graphs support longer-range dependency capture without changing the original node features or local structure.
  • Ramanujan graphs supply a deterministic structural prior that replaces heuristic curvature-based or spectral rewiring rules.
  • The same construction yields a topology-aware message-passing scheme that scales with graph size while remaining local.

Where Pith is reading between the lines

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

  • The same rewiring idea could be tested on directed graphs or hypergraphs where resistance curvature has a natural analogue.
  • If the non-negative curvature bound holds uniformly, it may imply improved mixing times for random walks on the rewired graph, a property left unmeasured in the experiments.
  • The method opens a route to parameter-free topology repair that could be combined with existing attention or positional-encoding layers in GNNs.

Load-bearing premise

An algorithmic framework always exists that can add Ramanujan edges to any input graph while preserving its local connectivity and achieving non-negative resistance curvature.

What would settle it

A concrete input graph on which no such rewiring procedure produces non-negative resistance curvature while keeping local neighborhoods unchanged, or a benchmark where the method fails to match or exceed the nine compared rewiring baselines.

Figures

Figures reproduced from arXiv: 2606.21333 by Hugo Attali, Rachid El Jouhri.

Figure 1
Figure 1. Figure 1: Mean resistance among top high-resistance edges across three datasets on 50 graphs. Ramanujan RN graph achieves the lowest resistance, indicating a better global connectivity. Low Diameter Using Theorem 2 we can show that the Ramanujan RN graph admits low diameter. Corollary 1. Let G be a finite, connected Ramanujan graph on N vertices of degree d with Non-negative resistance curvature. Then diam(G) ≤ 1 + … view at source ↗
Figure 2
Figure 2. Figure 2: Ablation study of classification accuracy on the original graph, a randomly generated Ramanujan graph, and our RNRP method. rectly from [51], and we follow the same evaluation protocol to ensure a fair comparison. 6.4 Ablation Studies In this part we conduct ablation experiments to empirically evaluate (i) the impact of preserving original node proximity during Ramanujan-based rewiring and (ii) assess robu… view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of Dirichlet energy over training epochs for a GCN on the original graph versus the RNRP-rewired graph. Higher values reflect weaker homogenization; RNRP consistently reaches larger energy, reduced over-smoothing relative to the orig￾inal structure. the random Ramanujan RN graph already improves over the original topol￾ogy, indicating that expansion and uniform degree help long-range propagation… view at source ↗
read the original abstract

Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Ramanujan Propagation, a graph rewiring strategy for GNNs that uses Ramanujan graphs to address over-squashing. It asserts that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature to improve information flow, proposes an algorithmic framework for constructing a rewired graph that preserves local connectivity of the input graph, and claims experimental superiority over nine state-of-the-art rewiring methods.

Significance. If the curvature guarantee and the existence of a construction satisfying all three conditions (Ramanujan property, non-negative resistance curvature, and local connectivity preservation) are established with explicit derivations, the work would supply a structural prior with potential theoretical grounding for rewiring, distinguishing it from heuristic approaches. The reported outperformance would then indicate practical relevance for long-range dependency tasks in GNNs.

major comments (2)
  1. [Abstract] Abstract: the assertion that 'suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing' is presented without any derivation, theorem statement, or reference to a specific result establishing the curvature property from the Ramanujan spectral condition. This link is load-bearing for the central claim that the rewiring alleviates topological bottlenecks.
  2. [algorithmic framework] The algorithmic framework paragraph: the manuscript states that an algorithmic framework exists to construct a Ramanujan rewired graph preserving local connectivity while achieving the non-negative resistance curvature property, yet supplies neither pseudocode, an explicit invariant, nor a proof that the output simultaneously satisfies the Ramanujan spectral bound, the curvature guarantee, and retention of original neighborhoods. This is the load-bearing assumption identified in the skeptic note and directly undermines verifiability of the proposed method.
minor comments (2)
  1. [Abstract] The abstract refers to 'nine state-of-the-art rewiring techniques' without naming them or providing citations; a table or section listing the baselines with references is needed for reproducibility.
  2. No dataset descriptions, experimental protocol details, or statistical significance tests are mentioned in the provided text, which affects assessment of the experimental claims.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and agree that the theoretical claims and algorithmic details require more explicit presentation to strengthen verifiability.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that 'suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing' is presented without any derivation, theorem statement, or reference to a specific result establishing the curvature property from the Ramanujan spectral condition. This link is load-bearing for the central claim that the rewiring alleviates topological bottlenecks.

    Authors: We agree that the abstract would benefit from greater explicitness. The full manuscript derives the non-negative resistance curvature from the Ramanujan spectral gap in Section 3 using the definition of resistance curvature and expander mixing properties. In revision we will add an explicit theorem statement to the abstract (or a footnote) with a direct reference to this derivation. revision: yes

  2. Referee: [algorithmic framework] The algorithmic framework paragraph: the manuscript states that an algorithmic framework exists to construct a Ramanujan rewired graph preserving local connectivity while achieving the non-negative resistance curvature property, yet supplies neither pseudocode, an explicit invariant, nor a proof that the output simultaneously satisfies the Ramanujan spectral bound, the curvature guarantee, and retention of original neighborhoods. This is the load-bearing assumption identified in the skeptic note and directly undermines verifiability of the proposed method.

    Authors: We acknowledge the need for greater formality. The manuscript describes the framework at a high level but does not include pseudocode or a formal proof of the joint invariants. We will revise the section to supply pseudocode, state the invariants explicitly (local neighborhood retention, Ramanujan bound, and curvature non-negativity), and include a proof sketch establishing that the output satisfies all three conditions simultaneously. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The abstract and described claims establish a graph-theoretic guarantee for non-negative resistance curvature on suitably chosen Ramanujan graphs, followed by an algorithmic construction that preserves local connectivity. No equations or steps reduce a claimed prediction or result to a fitted parameter, self-definition, or self-citation chain by construction. The framework is presented as a proposed algorithm rather than a statistical fit renamed as prediction, and the curvature-to-over-squashing link is asserted as a consequence of the structural property without evidence of definitional circularity. The paper's central results therefore stand as independent content relative to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; the central claim rests on the unshown mathematical property that Ramanujan graphs possess non-negative resistance curvature and on the existence of a construction algorithm that preserves local connectivity. No free parameters, invented entities, or additional axioms are identifiable from the abstract.

axioms (1)
  • domain assumption Suitably chosen Ramanujan graphs guarantee non-negative resistance curvature
    Invoked as the foundation for mitigating over-squashing (abstract).

pith-pipeline@v0.9.1-grok · 5683 in / 1369 out tokens · 24226 ms · 2026-06-26T14:25:09.169797+00:00 · methodology

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

55 extracted references · 11 canonical work pages · 3 internal anchors

  1. [1]

    In: ICML

    Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyun- yan, H., Ver Steeg, G., Galstyan, A.: Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In: ICML. pp. 21–29 (2019)

    2019

  2. [2]

    In: 25th Annual Symposium onFoundations of Computer Science, 1984

    Alon, N., Milman, V.D.: Eigenvalues, expanders and superconcentrators. In: 25th Annual Symposium onFoundations of Computer Science, 1984. IEEE (1984)

    1984

  3. [3]

    In: International Conference on Learning Representations (2021)

    Alon, U., Yahav, E.: On the bottleneck of graph neural networks and its practical implications. In: International Conference on Learning Representations (2021)

    2021

  4. [4]

    oversquashing

    Arnaiz-Rodriguez, A., Errica, F.: Oversmoothing," oversquashing", heterophily, long-range, and more: Demystifying common beliefs in graph machine learning. arXiv preprint arXiv:2505.15547 (2025)

    work page arXiv 2025

  5. [5]

    In: Forty-first International Conference on Machine Learning (2024),https://openreview.net/forum?id= uyhjKoaIQa

    Attali, H., Buscaldi, D., Pernelle, N.: Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation. In: Forty-first International Conference on Machine Learning (2024),https://openreview.net/forum?id= uyhjKoaIQa

    2024

  6. [6]

    In: Proceedings of the 34th ACM International Conference on Information and Knowledge Management

    Attali, H., Papastergiou, T., Pernelle, N., Malliaros, F.D.: Dynamic triangulation- based graph rewiring for graph neural networks. In: Proceedings of the 34th ACM International Conference on Information and Knowledge Management. pp. 87–97 (2025)

    2025

  7. [7]

    Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

    Attali, H., Pernelle, N., Buscaldi, D., Malliaros, F.D.: Graph rewiring in gnns to mitigate over-squashing and over-smoothing: A survey. arXiv preprint arXiv:2605.00951 (2026)

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    arXiv preprint arXiv:2506.05971 (2025)

    Bamberger, J., Gutteridge, B., Roux, S.l., Bronstein, M.M., Dong, X.: On measuring long-range interactions in graph neural networks. arXiv preprint arXiv:2506.05971 (2025)

    work page arXiv 2025

  9. [9]

    In: 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

    Banerjee,P.K.,Karhadkar,K.,Wang,Y.G.,Alon,U.,Montúfar,G.:Oversquashing in gnns through the lens of information contraction and graph expansion. In: 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton). pp. 1–8. IEEE (2022)

    2022

  10. [10]

    In: The Twelfth International Conference on Learn- ing Representations (2024),https://openreview.net/forum?id=4Ua4hKiAJX

    Barbero, F., Velingker, A., Saberi, A., Bronstein, M.M., Giovanni, F.D.: Locality- aware graph rewiring in GNNs. In: The Twelfth International Conference on Learn- ing Representations (2024),https://openreview.net/forum?id=4Ua4hKiAJX

    2024

  11. [11]

    In: Forty-first International Conference on Machine Learning (2024),https://openreview.net/forum?id=fSNHK7mu3j

    Bechler-Speicher, M., Amos, I., Gilad-Bachrach, R., Globerson, A.: Graph neural networks use graphs when they shouldn’t. In: Forty-first International Conference on Machine Learning (2024),https://openreview.net/forum?id=fSNHK7mu3j

    2024

  12. [12]

    In: International Conference on Machine Learning

    Black, M., Wan, Z., Nayyeri, A., Wang, Y.: Understanding oversquashing in gnns through the lens of effective resistance. In: International Conference on Machine Learning. pp. 2528–2547. PMLR (2023)

    2023

  13. [13]

    In: ICLR (2014)

    Bruna, J., Zaremba, W., Szlam, A., LeCun, Y.: Spectral networks and locally connected networks on graphs. In: ICLR (2014)

    2014

  14. [14]

    In: Proceedings of the twenty-first annual ACM symposium on Theory of computing

    Chandra, A.K., Raghavan, P., Ruzzo, W.L., Smolensky, R.: The electrical resis- tance of a graph captures its commute and cover times. In: Proceedings of the twenty-first annual ACM symposium on Theory of computing. pp. 574–586 (1989) Ramanujan Graph Rewiring 15

    1989

  15. [15]

    Princeton University Press (1970)

    Cheeger,J.:Alowerboundforthesmallesteigenvalueofthelaplacian.In:Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31). Princeton University Press (1970)

    1970

  16. [16]

    In: Proceedings of the AAAI Conference

    Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., Sun, X.: Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In: Proceedings of the AAAI Conference. vol. 34, pp. 3438–3445 (2020)

    2020

  17. [17]

    In: Proceedings of the conference on computer vision and pattern recognition

    Chen, J., Li, Z., Zhu, Y., Zhang, J., Pu, J.: From node interaction to hop interac- tion: New effective and scalable graph learning paradigm. In: Proceedings of the conference on computer vision and pattern recognition. pp. 7876–7885 (2023)

    2023

  18. [18]

    Choi, J., Park, S., Park, S., Cho, S.B., Park, N.: Fractal-inspired message passing neural networks with fractal nodes (2025),https://openreview.net/forum?id= zPoW8CajCN

    2025

  19. [19]

    arXiv preprint arXiv:2406.03671 (2024)

    Choi, J., Park, S., Wi, H., Cho, S.B., Park, N.: Panda: Expanded width-aware message passing beyond rewiring. arXiv preprint arXiv:2406.03671 (2024)

    work page arXiv 2024

  20. [20]

    American Mathematical Soc

    Chung, F.R., Graham, F.C.: Spectral graph theory. American Mathematical Soc. (1997)

    1997

  21. [21]

    In: Learning on Graphs Conference

    Deac, A., Lackenby, M., Veličković, P.: Expander graph propagation. In: Learning on Graphs Conference. pp. 38–1. PMLR (2022)

    2022

  22. [22]

    arXiv preprint arXiv:2410.07756 (2024)

    Devriendt, K.: Graphs with nonnegative resistance curvature. arXiv preprint arXiv:2410.07756 (2024)

    work page arXiv 2024

  23. [23]

    Discrete Applied Mathematics348, 68–78 (2024)

    Devriendt, K., Ottolini, A., Steinerberger, S.: Graph curvature via resistance dis- tance. Discrete Applied Mathematics348, 68–78 (2024)

    2024

  24. [24]

    In: ICML

    Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., Bronstein, M.M.: On over-squashing in message passing neural networks: The impact of width, depth, and topology. In: ICML. pp. 7865–7885. PMLR (2023)

    2023

  25. [25]

    Di Giovanni, F., Rusch, T.K., Bronstein, M.M., Deac, A., Lackenby, M., Mishra, S., Veličković, P.: How does over-squashing affect the power of gnns? arXiv preprint arXiv:2306.03589 (2023)

    work page arXiv 2023

  26. [26]

    arXiv preprint arXiv:2110.07875 (2021)

    Dwivedi, V.P., Luu, A.T., Laurent, T., Bengio, Y., Bresson, X.: Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875 (2021)

    work page arXiv 2021

  27. [27]

    Advances in Neural Information Processing Sys- tems35, 22326–22340 (2022)

    Dwivedi, V.P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A.T., Beaini, D.: Long range graph benchmark. Advances in Neural Information Processing Sys- tems35, 22326–22340 (2022)

    2022

  28. [28]

    In: The Second Learning on Graphs Confer- ence (2023)

    Fesser, L., Weber, M.: Mitigating over-smoothing and over-squashing using aug- mentations of forman-ricci curvature. In: The Second Learning on Graphs Confer- ence (2023)

    2023

  29. [29]

    Forman, R.: Bochner’s method for cell complexes and combinatorial ricci curvature (2003)

    2003

  30. [30]

    In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

    Friedman, J.: A proof of alon’s second eigenvalue conjecture. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pp. 720–724 (2003)

    2003

  31. [31]

    In: International conference on machine learning

    Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: International conference on machine learning. pp. 1263–1272. PMLR (2017)

    2017

  32. [32]

    In: Proceedings of the 32nd ACM international CIKM

    Giraldo,J.H.,Skianis,K.,Bouwmans,T.,Malliaros,F.D.:Onthetrade-offbetween over-smoothing and over-squashing in deep graph neural networks. In: Proceedings of the 32nd ACM international CIKM. pp. 566–576 (2023)

    2023

  33. [33]

    Advances in Mathematics458, 109984 (2024) 16 H

    Glock, S., Correia, D.M., Sudakov, B.: Hamilton cycles in pseudorandom graphs. Advances in Mathematics458, 109984 (2024) 16 H. Attali and R. El Jouhri

    2024

  34. [34]

    In: Proceedings of International Conference on Neural Networks (ICNN’96)

    Goller, C., Kuchler, A.: Learning task-dependent distributed representations by backpropagation through structure. In: Proceedings of International Conference on Neural Networks (ICNN’96). vol. 1, pp. 347–352. IEEE (1996)

    1996

  35. [35]

    In: Proceedings

    Gori, M., Monfardini, G., Scarselli, F.: A new model for learning in graph domains. In: Proceedings. 2005 IEEE International Joint Conference on Neural Networks,

    2005

  36. [36]

    vol. 2, pp. 729–734. IEEE (2005)

    2005

  37. [37]

    In: International Conference on Machine Learning

    Gutteridge, B., Dong, X., Bronstein, M.M., Di Giovanni, F.: Drew: Dynamically rewired message passing with delay. In: International Conference on Machine Learning. pp. 12252–12267. PMLR (2023)

    2023

  38. [38]

    In: International Conference on Learning Representations

    Karhadkar, K., Banerjee, P.K., Montúfar, G.: Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In: International Conference on Learning Representations. ICLR (2023)

    2023

  39. [39]

    In: Proceedings of the International Conference on Learning Represen- tations

    Kipf, T.N., Welling, M.: Semi-Supervised Classification with Graph Convolutional Networks. In: Proceedings of the International Conference on Learning Represen- tations. ICLR (2017)

    2017

  40. [40]

    In: Advances in neural information processing systems

    Klicpera, J., Weißenberger, S., Günnemann, S.: Diffusion improves graph learning. In: Advances in neural information processing systems. NeurIPS (2019)

    2019

  41. [41]

    In: International Conference on Machine Learning

    Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., Qian, W.: Finding global homophily in graph neural networks when meeting heterophily. In: International Conference on Machine Learning. pp. 13242–13256. PMLR (2022)

    2022

  42. [42]

    In: The Thirteenth International Conference on Learning Representations (2025),https://openreview.net/forum?id=zBbZ2vdLzH

    Linkerhägner, J., Shi, C., Dokmanić, I.: Joint graph rewiring and feature denoising via spectral resonance. In: The Thirteenth International Conference on Learning Representations (2025),https://openreview.net/forum?id=zBbZ2vdLzH

    2025

  43. [43]

    Combinatorica8(3), 261–277 (1988)

    Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica8(3), 261–277 (1988)

    1988

  44. [44]

    TUDataset: A collection of benchmark datasets for learning with graphs

    Morris, C., Kriege, N.M., Bause, F., Kersting, K., Mutzel, P., Neumann, M.: Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663 (2020)

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  45. [45]

    In: International Conference on Machine Learning

    Nguyen,K.,Hieu,N.M.,Nguyen,V.D.,Ho,N.,Osher,S.,Nguyen,T.M.:Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In: International Conference on Machine Learning. pp. 25956–25979. PMLR (2023)

    2023

  46. [46]

    Comptes Rendus Mathematique 345(11), 643–646 (2007)

    Ollivier, Y.: Ricci curvature of metric spaces. Comptes Rendus Mathematique 345(11), 643–646 (2007)

    2007

  47. [47]

    Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., Prokhorenkova, L.: A critical look at the evaluation of gnns under heterophily: are we really making progress? In: International Conference on Learning Representations (2023)

    2023

  48. [48]

    arXiv preprint arXiv:2303.10993 , year=

    Rusch, T.K., Bronstein, M.M., Mishra, S.: A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993 (2023)

    work page arXiv 2023

  49. [49]

    In: transactions on neural networks

    Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. In: transactions on neural networks. IEEE (2008)

    2008

  50. [50]

    In: international conference on learning representation (2023)

    Song, Y., Zhou, C., Wang, X., Lin, Z.: Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing. In: international conference on learning representation (2023)

    2023

  51. [51]

    Proceedings of the International Conference on Learning Representations (2022)

    Topping, J., Di Giovanni, F., Chamberlain, B.P., Dong, X., Bronstein, M.M.: Un- derstanding over-squashing and bottlenecks on graphs via curvature. Proceedings of the International Conference on Learning Representations (2022)

    2022

  52. [52]

    arXiv preprint arXiv:2410.03424 (2024)

    Wilson, J., Bechler-Speicher, M., Veličković, P.: Cayley graph propagation. arXiv preprint arXiv:2410.03424 (2024)

    work page arXiv 2024

  53. [53]

    In: IEEE transactions on neural networks and learning systems

    Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. In: IEEE transactions on neural networks and learning systems. vol. 32, pp. 4–24. IEEE (2020) Ramanujan Graph Rewiring 17

    2020

  54. [54]

    Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  55. [55]

    Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., Sun, M.: Graph neural networks: A review of methods and applications. AI open (2020) A Appendix: Proofs of Sections 4 and 5 A.1 Proof of Theorem 1: Commute Time Bound via Resistance Curvature Theorem 1 (Commute time bound via resistance curvature).LetG= (V, E)be a finite, connected...

    2020