Pith. sign in

REVIEW 25 cited by

On the Bottleneck of Graph Neural Networks and its Practical Implications

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2006.05205 v4 pith:4QT4Q6VF submitted 2020-06-09 cs.LG stat.ML

Uri Alon , Eran Yahav This is my paper · ORCID
classification cs.LGstat.ML
keywords bottleneckgnnsover-squashinggraphlong-rangedistantinformationmessages
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Since the proposal of the graph neural network (GNN) by Gori et al. (2005) and Scarselli et al. (2008), one of the major problems in training GNNs was their struggle to propagate information between distant nodes in the graph. We propose a new explanation for this problem: GNNs are susceptible to a bottleneck when aggregating messages across a long path. This bottleneck causes the over-squashing of exponentially growing information into fixed-size vectors. As a result, GNNs fail to propagate messages originating from distant nodes and perform poorly when the prediction task depends on long-range interaction. In this paper, we highlight the inherent problem of over-squashing in GNNs: we demonstrate that the bottleneck hinders popular GNNs from fitting long-range signals in the training data; we further show that GNNs that absorb incoming edges equally, such as GCN and GIN, are more susceptible to over-squashing than GAT and GGNN; finally, we show that prior work, which extensively tuned GNN models of long-range problems, suffers from over-squashing, and that breaking the bottleneck improves their state-of-the-art results without any tuning or additional weights. Our code is available at https://github.com/tech-srl/bottleneck/ .

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 25 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 90 citations worldwide. Full citation record

  1. Provably Overwhelming Transformer Models with Designed Inputs

    cs.LG 2025-02 conditional novelty 7.0 of 10

    A verification algorithm proves that a trained single-layer transformer is 'overwhelmed' by a chosen prefix, meaning its output is insensitive to any appended string of bounded length.

  2. Benchmarking Sheaf Neural Networks for Inductive Tasks

    cs.LG 2026-08 conditional novelty 6.0 of 10

    On 14 inductive graph benchmarks, sheaf neural networks underperform strong GNN baselines, and their performance is driven more by the surrounding architecture than by the sheaf diffusion mechanism.

  3. Schreier-Coset Graph Rewiring

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Adding an SL(2,Z_n)-derived Schreier-Coset expander to GNN inputs reduces effective resistance and improves or matches accuracy on several node and graph benchmarks.

  4. Label-Free Finite-Volume-Residual Training of Attention Graph Neural Networks for Coupled Thermo-Fluid Fields

    physics.flu-dyn 2026-07 conditional novelty 6.0 of 10

    An attention graph neural network trained only against finite-volume residuals predicts coupled 3D thermo-fluid fields without labeled CFD data, matching or beating a supervised baseline on four benchmarks.

  5. EmbeddedKittens: An Evaluation of Code Embeddings for Scratch

    cs.SE 2026-07 conditional novelty 6.0 of 10

    Structure-aware embeddings such as GGNN transfer to Scratch and can support sprite naming and, with weaker evidence, correctness and progress prediction.

  6. GUIDED Network-Agnostic Feature Initialization for Spatial Transferability in GNN-based Models

    cs.LG 2026-07 conditional novelty 6.0 of 10

    A demand-initialization layer that embeds travel demand on virtual links instead of node features lets GNN traffic-flow surrogates transfer across city networks with minimal fine-tuning.

  7. Player-Team Heterogeneous Interaction Graph Transformer for Soccer Outcome Prediction

    cs.LG 2025-07 conditional novelty 6.0 of 10

    HIGFormer predicts soccer match outcomes by jointly modeling player-player event interactions and team-team historical win rates with a heterogeneous graph transformer and graph convolution network.

  8. On Measuring Long-Range Interactions in Graph Neural Networks

    cs.LG 2025-06 conditional novelty 6.0 of 10

    The paper axiomatizes a distance-weighted influence measure of range and uses it to show that LRGB tasks differ sharply in how long-range they really are.

  9. Thickness-aware E(3)-Equivariant 3D Mesh Neural Networks

    cs.CV 2025-05 conditional novelty 6.0 of 10

    A mesh GNN that links opposite surfaces via learned thickness edges improves node-level 3D deformation prediction while a PCA-based canonical coordinate system preserves E(3) equivariance.

  10. DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale

    cs.LG 2025-02 conditional novelty 6.0 of 10

    DeepGate4 scales circuit representation learning to million-gate AIGs by partitioning them into overlapping cones and processing them in level order with a GAT-based sparse transformer, achieving state-of-the-art loss...

  11. Graph Transformers for inverse physics: reconstructing flows around arbitrary 2D airfoils

    cs.LG 2025-01 conditional novelty 6.0 of 10

    A hybrid message-passing and linear-attention Graph Transformer reconstructs 2D airfoil flow fields from surface pressure alone, achieving high test accuracy on a new open dataset.

  12. Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing

    cs.LG 2024-12 conditional novelty 6.0 of 10

    State space models have an inherent recency bias and over-smoothing in deep stacks, and a two-channel polarization fix improves long-range associative recall.

  13. ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment

    cs.LG 2024-12 conditional novelty 6.0 of 10

    ReHub keeps spoke-to-hub attention sparse by connecting each node to only k hubs per layer and reassigning those hubs via hub-hub similarity, reaching O(N) complexity with accuracy on par with its dense variant.

  14. Scalable and Efficient Joint Spiking Embedding Predictive Architecture for Large-Scale Dynamic Graphs

    cs.LG 2026-07 conditional novelty 5.0 of 10

    SG-JEPA applies joint-embedding predictive learning to dynamic graphs, using spiking-neuron context encoders to predict future node embeddings without edge reconstruction or graph augmentation.

  15. GeoFlow: Geo-Aware Modeling of Inter-Area Relationships in Origin-Destination Flow Prediction and Generation

    cs.LG 2026-07 conditional novelty 5.0 of 10

    GeoFlow improves OD flow prediction and generation by augmenting area representations with geospatial attributes and using a geometric-intrinsic fusion encoder with axial-global attention decoder.

  16. Graph Neural Network Reveals the Cortical Morphology of Local Brain Aging in Normal Cognition and Alzheimer's Disease

    q-bio.NC 2026-01 conditional novelty 5.0 of 10

    A graph neural network trained on cortical surface morphometry produces vertex-level local brain age maps that show prefrontal/parietal aging in normal cognition and parahippocampal/temporal aging in Alzheimer's disease.

  17. Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

    cs.LG 2025-09 reject novelty 5.0 of 10

    CAMP updates nodes in centrality-ranked batches to spread information across GNN layers and claims to reduce oversquashing without rewiring, but the proof and evidence are not convincing.

  18. GATE: Graph Attention Neural Networks with Real-Time Edge Construction for Robust Indoor Localization using Mobile Embedded Devices

    cs.LG 2025-07 conditional novelty 5.0 of 10

    A dynamic-graph GNN with element-wise attention (GATE) reports sub-2-meter mean Wi-Fi localization error across heterogeneous phones and buildings, outperforming published baselines.

  19. GITO: Graph-Informed Transformer Operator for Learning Complex Partial Differential Equations

    cs.LG 2025-06 conditional novelty 5.0 of 10

    GITO, a graph-informed transformer operator, reports lower relative L2 errors than existing transformer-based neural operators on Navier-Stokes, heat conduction, and airfoil benchmark datasets.

  20. Transaction Categorization with Relational Deep Learning in QuickBooks

    cs.CE 2025-06 conditional novelty 5.0 of 10

    Rel-Cat predicts transaction categories by converting the QuickBooks relational database into a heterogeneous graph and treating categorization as link prediction, beating production baselines on a private dataset.

  21. FuncGNN: Learning Functional Semantics of Logic Circuits with Graph Neural Networks

    cs.LG 2025-06 conditional novelty 5.0 of 10

    FuncGNN, a GNN with hybrid aggregation, ratio-conditioned normalization, and dense layer fusion, reports state-of-the-art MAE on signal probability and truth-table distance prediction for AIG circuits.

  22. Policy Guided Tree Search for Enhanced LLM Reasoning

    cs.LG 2025-02 conditional novelty 5.0 of 10

    PGTS trains a graph-transformer policy via PPO to guide tree search over LLM reasoning steps, reporting improved accuracy and lower token use than chain-of-thought and MCTS baselines.

  23. DeltaGNN: Graph Neural Network with Information Flow Control

    cs.LG 2025-01 conditional novelty 5.0 of 10

    DeltaGNN introduces a linear-time, embedding-derived information flow score for edge filtering and uses it to mitigate over-smoothing and over-squashing in semi-supervised node classification.

  24. A Metric for the Balance of Information in Graph Learning

    cs.LG 2025-01 reject novelty 4.0 of 10

    NNRD, the log average ratio of performance under feature noise to performance under structure noise, is proposed as a dataset-level indicator of which information source a molecular graph task favors.

  25. GRAINRec: Graph and Attention Integrated Approach for Real-Time Session-Based Item Recommendations

    cs.LG 2024-11 conditional novelty 4.0 of 10

    GRAINRec applies a LESSR-style graph and attention model with a nearest-neighbor candidate matrix to deliver real-time session recommendations, reporting modest offline gains and positive A/B results.

Pith tools