  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.

Machine Learning