The authors define mixing time and minimax fidelity for feedforward graphs, use them to design a recursive sparse graph (FS) with polylogarithmic mixing time, and show it matches dense attention on parity and retrieval tasks.
Higher-Order Expander Graph Propagation
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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.
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
What makes a good feedforward computational graph?
The authors define mixing time and minimax fidelity for feedforward graphs, use them to design a recursive sparse graph (FS) with polylogarithmic mixing time, and show it matches dense attention on parity and retrieval tasks.