mlsanityData to 14 Oct 2026

Higher-Order Expander Graph Propagation

arXiv 2311.07966 ↗First posted 14 Nov 2023cs.LGcited by 4

Not on the map. Why?

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.

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

22 of 37 references.

References · 22

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  7. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  9. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  10. 2018Hypergraph Neural Networkscited by 488
  11. 2022Long Range Graph Benchmarkcited by 263
  12. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
10 more
  1. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  2. 2017Knowledge Transfer for Out-of-Knowledge-Base Entities: A Graph Neural Network Approachcited by 102
  3. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  4. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 53
  5. 2023How does over-squashing affect the power of GNNs?cited by 53
  6. 2022Message passing all the way upcited by 47
  7. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  8. 2019Dual Graph Attention Networks for Deep Latent Representation of Multifaceted Social Effects in Recommender Systemscited by 41
  9. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 36
  10. 2021Identifying critical higher-order interactions in complex networkscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 2.

4 papers.

  1. 2024Cayley Graph Propagationcited by 21
  2. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 8
  3. 2025What makes a good feedforward computational graph?cited by 5
  4. 2024Commute-Time-Optimised Graphs for GNNscited by 4