# Higher-Order Expander Graph Propagation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 14 Nov 2023.

## Builds on (most cited first, 22 of 22)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [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)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Knowledge Transfer for Out-of-Knowledge-Base Entities: A Graph Neural Network Approach](https://mlsanity.com/paper/1706.05674/) (2017)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Oversquashing in GNNs through the lens of information contraction and graph expansion](https://mlsanity.com/paper/2208.03471/) (2022)
- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Message passing all the way up](https://mlsanity.com/paper/2202.11097/) (2022)
- [Shortest Path Networks for Graph Property Prediction](https://mlsanity.com/paper/2206.01003/) (2022)
- [Dual Graph Attention Networks for Deep Latent Representation of Multifaceted Social Effects in Recommender Systems](https://mlsanity.com/paper/1903.10433/) (2019)
- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [Identifying critical higher-order interactions in complex networks](https://mlsanity.com/paper/2105.02763/) (2021)

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

- [Cayley Graph Propagation](https://mlsanity.com/paper/2410.03424/) (2024)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [What makes a good feedforward computational graph?](https://mlsanity.com/paper/2502.06751/) (2025)
- [Commute-Time-Optimised Graphs for GNNs](https://mlsanity.com/paper/2407.08762/) (2024)

## Abstract (arXiv)

Graph neural networks operate on graph-structured data via exchanging messages along edges. One limitation of this message passing paradigm is the over-squashing problem. Over-squashing occurs when messages from a node's expanded receptive field are compressed into fixed-size vectors, potentially causing information loss. To address this issue, recent works have explored using expander graphs, which are highly-connected sparse graphs with low diameters, to perform message passing. However, current methods on expander graph propagation only consider pair-wise interactions, ignoring higher-order structures in complex data. To explore the benefits of capturing these higher-order correlations while still leveraging expander graphs, we introduce higher-order expander graph propagation. We propose two methods for constructing bipartite expanders and evaluate their performance on both synthetic and real-world datasets.