# Cayley Graph Propagation

arXiv: https://arxiv.org/abs/2410.03424 · HTML: https://mlsanity.com/paper/2410.03424/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 63 references that are in the map.
- First posted on arXiv 4 Oct 2024.

## Builds on (most cited first, 30 of 48)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Graph-Coupled Oscillator Networks](https://mlsanity.com/paper/2202.02296/) (2022)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)

## Built on by (most cited first, 21 of 21)

- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [TxPert: Leveraging Biochemical Relationships for Out-of-Distribution Transcriptomic Perturbation Prediction](https://mlsanity.com/paper/2505.14919/) (2025)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2411.17429/) (2024)
- [Deep Equilibrium Algorithmic Reasoning](https://mlsanity.com/paper/2410.15059/) (2024)
- [CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs](https://mlsanity.com/paper/2502.18663/) (2025)
- [What makes a good feedforward computational graph?](https://mlsanity.com/paper/2502.06751/) (2025)
- [Rotary Position Encodings for Graphs](https://mlsanity.com/paper/2509.22259/) (2025)
- [Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks](https://mlsanity.com/paper/2508.20597/) (2025)
- [CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)](https://mlsanity.com/paper/2509.19162/) (2025)
- [Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics](https://mlsanity.com/paper/2510.20556/) (2025)
- [Understanding the Failure Modes of Transformers through the Lens of Graph Neural Networks](https://mlsanity.com/paper/2512.09182/) (2025)
- [Improving LLM Final Representations with Inter-Layer Geometry](https://mlsanity.com/paper/2603.22665/) (2026)
- [Schreier-Coset Graph Propagation](https://mlsanity.com/paper/2505.10392/) (2025)
- [Dynamic Relational Priming Improves Transformer in Multivariate Time Series](https://mlsanity.com/paper/2509.12196/) (2025)
- [On the Runway Cascade of Transformers for Language Modeling](https://mlsanity.com/paper/2601.14522/) (2026)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2605.00951/) (2026)
- [Ramanujan Graph Rewiring with Non Negative Resistance Curvature](https://mlsanity.com/paper/2606.21333/) (2026)
- [Learning the Graphical Nature of Symmetries](https://mlsanity.com/paper/2607.12026/) (2026)
- [Schreier-Coset Graph Rewiring](https://mlsanity.com/paper/2607.27479/) (2026)
- [LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN](https://mlsanity.com/paper/2608.09596/) (2026)
- [Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment](https://mlsanity.com/paper/2608.10619/) (2026)

## Abstract (arXiv)

In spite of the plethora of success stories with graph neural networks (GNNs) on modelling graph-structured data, they are notoriously vulnerable to over-squashing, whereby tasks necessitate the mixing of information between distance pairs of nodes. To address this problem, prior work suggests rewiring the graph structure to improve information flow. Alternatively, a significant body of research has dedicated itself to discovering and precomputing bottleneck-free graph structures to ameliorate over-squashing. One well regarded family of bottleneck-free graphs within the mathematical community are expander graphs, with prior work -- Expander Graph Propagation (EGP) -- proposing the use of a well-known expander graph family -- the Cayley graphs of the SL(2,mathbbZn) special linear group -- as a computational template for GNNs. However, in EGP the computational graphs used are truncated to align with a given input graph. In this work, we show that truncation is detrimental to the coveted expansion properties. Instead, we propose CGP, a method to propagate information over a complete Cayley graph structure, thereby ensuring it is bottleneck-free to better alleviate over-squashing. Our empirical evidence across several real-world datasets not only shows that CGP recovers significant improvements as compared to EGP, but it is also akin to or outperforms computationally complex graph rewiring techniques.