Research map / Graph learning / GNN architectures

Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning

NeurIPS 2026 · Graph learning › GNN architectures · approach: Expressive equivariant message passing · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Graph Cascades, a label-free contagion-based (MAS/TAS) mesoscopic rewiring that builds a weighted top-k co-activation graph for GNNs and sparse GTs (plus CR-Graphormer), with theory on reinforcement homophily and effective resistance.

Problem

Standard GNNs and sparse graph transformers miss intermediate-scale structure; on heterophilic graphs same-label nodes are sparsely connected and multiple hops apart, so edge-level aggregation and coarse sparse attention lose task-relevant neighborhoods.

Approach

Run short threshold/maximum-adjacency contagions from each seed, keep the top-k most frequently co-activated nodes as weighted direct neighbors in an auxiliary graph, and analyze when such multi-hop reinforcement is more label-homophilic than adjacency.

Key results

• GCN-TAS improves test accuracy on 10 of 16 DGL graphs, up to +20.16%; NAG-TAS and VCR-MAS/TAS improve 13 of 16 graphs.
• Largest gains on heterophilic graphs, e.g., chameleon +32.74% (MAS) and texas +27.63%, cornell +30.13%.
• Regression of accuracy on homophily, log average degree and connectivity reaches adjusted R^2 up to 0.760 for CR-MAS, versus 0.454 for NAG on original graphs.

Surprising findings

• Cascade rewiring degrades performance on low-degree homophilic graphs (cycle, grid, citeseer, cora) and on Roman-empire for GNN backbones.
• Topology-only, unweighted rewired graph already gives broad gains for sparse-attention GTs, while frequency weights matter more for GNNs.

Limitations

• Less effective on highly regular, low-degree, or bottlenecked graphs such as cycle, grid, and Roman-empire.
• Topology-only by design, so it ignores node features that could help on feature-rich graphs.
• Theory relies on idealized short-walk reinforcement proxies rather than the exact finite-sample MAS/TAS pipeline.

Experimental setup

Datasets: actor chameleon cornell squirrel texas wisconsin cora citeseer pubmed computer photo cycle

Benchmarks: actor chameleon cornell squirrel texas wisconsin cora citeseer pubmed computer photo cycle

Metrics: test accuracy macro-F1 AUROC adjusted R^2

Baselines: GCN GraphSAGE GAT PPRGo GRAND+ GT Graphormer SAN GraphGPS NAGphormer Exphormer SGFormer

Builds on: Graphormer NAGphormer VCR-Graphormer Exphormer GraphGPS FoSR SDRF

Closest papers by meaning

• Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.90)
• GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.89)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.88)
• PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · similarity 0.88)
• The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.87)
• Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.87)