AI summaryⓘ
The authors introduce Graph Cascades, a method that changes the graph connections in Graph Neural Networks to better capture relationships that are neither just immediate neighbors nor the entire graph at once. They use a process inspired by how things spread, to add connections between nodes that have strong multiple-step relationships, doing this efficiently. The authors provide theory explaining when this approach helps and when it does not, such as in graphs with certain structural properties. Their experiments show improvements in node classification tasks, especially in graphs where connections are more mixed or nodes have many neighbors. They also note that the method doesn't work well in graphs with very low degrees or bottlenecks, aligning with their theoretical predictions.
Graph Neural NetworksGraph TransformersRewiringContagion-based DiffusionMesoscopic StructureNode ClassificationStochastic Block ModelEffective ResistanceHomophilyGraph Connectivity
Authors
Meher Chaitanya, My Le, Luana Ruiz
Abstract
We introduce Graph Cascades, a mesoscopic rewiring strategy for Graph Neural Networks (GNNs) and Graph Transformers (GTs) that captures intermediate-scale graph structure beyond purely local edges or fully global attention. Using contagion-based diffusion processes, Graph Cascades constructs, in O(|V|+|E|) time, an auxiliary graph where node pairs supported by repeated multi-hop reinforcement are promoted to direct neighbors. We theoretically characterize when reinforcement-based rewiring helps: sufficient conditions under which reinforcement-based edge selection is more label-aligned than direct adjacency, an SBM witness in which two-hop reinforcement is perfectly homophilic, and a formalization of mesoscopic connectivity via graph effective resistance. Empirically, across node-classification benchmarks, Graph Cascades improves multiple GNN and sparse-GT backbones, with the most reliable gains observed on heterophilic and moderate- to high-degree homophilic graphs. The theoretical conditions also identify regimes where mesoscopic rewiring is unlikely to be beneficial -- low-degree regular graphs and graphs with structural bottlenecks -- and these predictions match the observed failures. We additionally observe tight correlations between performance and structural properties in the rewired graphs.