REVIEW 8 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 8 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.
-
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.
-
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.
-
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.
Discussion (0). Sign in to comment.