REVIEW 21 cited by
Understanding over-squashing and bottlenecks on graphs via curvature
Not yet reviewed by Pith; the record is open.
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
abstract
Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of $k$-hop neighbors grows rapidly with $k$. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.
Forward citations
Cited by 21 Pith papers
-
Markov and lattice bases for Forman-Ricci curvature of graphs
Indispensable Markov moves for sampling graphs with fixed degree and Forman-Ricci curvature sequences have degree at least quadratic in the maximum degree, and degree-3 moves still span the lattice.
-
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
AGDN is a new GNN framework using a MixScore matrix and anisotropic graph diffusion to outperform prior methods on TSP instances across sizes and distributions.
-
Unveiling defect motifs in amorphous GeSe using machine learning interatomic potentials
Two defect motifs, aligned Ge chains and overcoordinated Ge chains, are identified as the origins of conduction-band and valence-band trap states in amorphous GeSe.
-
Schreier-Coset Graph Rewiring
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.
-
Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning
Graph Cascades uses contagion diffusion to rewire graphs by promoting reinforced multi-hop node pairs to direct neighbors, improving GNN performance on heterophilic and moderate-degree homophilic graphs under specifie...
-
TopoGeoScore: A Self-Supervised Source-Only Geometric Framework for OOD Checkpoint Selection
TopoGeoScore combines a torsion-inspired Laplacian log-determinant, Ollivier-Ricci curvature, and higher-order topological summaries from source embeddings, with weights learned via self-supervised invariance to geome...
-
Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
HMH builds soft hierarchies with orthonormal Haar bases and heterophily-aware encoders to apply learnable spectral filters while using skip unpooling to avoid oversmoothing and hub bias on heterophilous graphs.
-
Cheeger--Hodge Contrastive Learning for Structurally Robust Graph Representation Learning
CHCL aligns a Cheeger-Hodge joint signature across graph augmentations to produce embeddings that remain stable under local structural changes.
-
Learning from Historical Activations in Graph Neural Networks
HISTOGRAPH applies unified layer-wise attention followed by node-wise attention over historical GNN activations to improve graph classification, especially in deep models.
-
How Wide and How Deep? Mitigating Over-Squashing of GNNs via Channel Capacity Constrained Estimation
C3E estimates hidden dimensions and depths for GNNs by treating them as communication channels to reduce over-squashing and improve representation learning.
-
GFLC: Graph-based Fairness-aware Label Correction for Fair Classification
GFLC is a new label-correction method that uses confidence scores, graph curvature, and demographic parity to improve both accuracy and fairness under group-dependent label noise.
-
Graph Mamba Operator: A Latent Simulator for Interacting Particle Systems
GraMO couples graph interactions and temporal state updates in one linear recurrence with input-dependent coefficients to simulate N-body, motion, and robotics systems with lower long-horizon error than prior GNN or S...
-
Mesh Based Simulations with Spatial and Temporal awareness
A unified training framework for mesh-based ML surrogates in CFD improves accuracy and long-horizon stability by enforcing spatial derivative consistency via multi-node prediction, using temporal cross-attention corre...
-
Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks
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.
-
On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
Excess risk of SGD and ridge regression on GNNs is characterized through graph spectra, showing graph shape decides which algorithm generalizes better and deeper networks amplify the difference.
-
Few-shot Learning on AMS Circuits and Its Application to Parasitic Capacitance Prediction
A few-shot graph-pretraining pipeline, built from subgraph sampling and a hybrid graph transformer, predicts parasitic coupling capacitance on unseen AMS circuits with substantially lower error than prior graph baselines.
-
On Preserving Geometrical Invariance for Superpixel Image Classification using Graph Transformer
A GraphGPS-style transformer on SLIC RAGs with mean-centered centroids reaches ~80.2% CIFAR-10 accuracy, matching ShapeGNN without boundary-point features and with better low-data stability.
-
Learning the Universe with the 2nd Generation of CAMELS: Varying 35 parameters of the IllustrisTNG model in (50Mpc/h)^3 boxes
New CAMELS simulations in larger (50 Mpc/h)^3 boxes with 35 varied parameters produce tighter neural-network constraints on model parameters than prior smaller-volume runs, with public data release.
-
TopoGeoScore: A Self-Supervised Source-Only Geometric Framework for OOD Checkpoint Selection
TopoGeoScore learns a non-negative linear combination of geometric and topological features from source embeddings via self-supervised invariance to select robust checkpoints for OOD scenarios.
-
Ollivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural Networks
Ollivier-Ricci curvature is extended from manifolds and undirected graphs to directed graphs with applications to graph neural networks.
-
Six Open Questions in Machine-Learned Interatomic Potential Foundation Models
This perspective article develops a definition of foundational MLIPs and poses six open questions that the authors believe will define future research in machine-learned interatomic potentials.
Discussion (0). Sign in to comment.