PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature

Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, Tan Nguyen

arXiv:2211.15779v3cs.LGstat.ML

TL;DR

GNNs struggle with over-smoothing and over-squashing, limiting their ability to model complex interactions involving distant information. This paper studies both problems through local Ollivier-Ricci curvature and proposes BORF, a curvature-based rewiring method. It links positive curvature with over-smoothing and negative curvature with over-squashing, and reports that BORF improves GNN performance while addressing both.

  • Problem

    Over-smoothing and over-squashing limit GNNs’ ability to model complex interactions and take distant information into account.

    Source: §1 · p. 1

  • Method

    The paper analyzes both phenomena at a local scale using Ollivier-Ricci curvature and proposes BORF, a curvature-based rewiring method.

    Source: §1 · p. 2

  • Results

    Positive graph curvature is associated with over-smoothing and negative graph curvature with over-squashing; BORF outperforms other methods on every node-classification task with GCN and GIN and achieves higher test accuracy in most graph-classification settings.

    Source: §6 · p. 8, §7 · p. 9

  • Takeaways & Limitations

    The paper presents local curvature as a common framework for studying both GNN problems and a basis for a rewiring method that addresses them together.

    Source: §1 · p. 2

    The theory relates over-squashing to negative Ollivier-Ricci curvature only at a local scale and under constraints on graph structure and GNN design.

    Source: §7 · p. 9

Abstract

from arXiv · show

Graph Neural Networks (GNNs) had been demonstrated to be inherently susceptible to the problems of over-smoothing and over-squashing. These issues prohibit the ability of GNNs to model complex graph interactions by limiting their effectiveness in taking into account distant information. Our study reveals the key connection between the local graph geometry and the occurrence of both of these issues, thereby providing a unified framework for studying them at a local scale using the Ollivier-Ricci curvature. Specifically, we demonstrate that over-smoothing is linked to positive graph curvature while over-squashing is linked to negative graph curvature. Based on our theory, we propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.

1. Introduction

GNNs face over-smoothing and over-squashing that limit their ability to model complex, long-range interactions. The paper uses local Ollivier-Ricci curvature to connect both problems and proposes BORF, a rewiring method designed to address them simultaneously.

1. Introduction

  • Over-smoothing makes node features indistinguishable as GNN depth increases, while over-squashing compresses growing amounts of information into fixed-size features.Both problems hinder modeling complex relationships or processing distant information.Source: §1 · p. 1
  • Prior work linked local graph structure and curvature to over-squashing, but the authors identify a lack of a common framework for both problems.They present a unified local-geometry framework using Ollivier-Ricci curvature.Source: §1 · pp. 1–2
  • The authors prove that very positively curved edges cause node representations to become similar, linking high edge curvature with over-smoothing.Source: §1 · p. 2
  • They connect low curvature with graph bottlenecks and over-squashing, then propose BORF to mitigate both issues through curvature-based rewiring.Source: §1 · p. 2

2. Related Work

Related work covers approaches to over-smoothing and over-squashing, alongside graph-curvature methods. It situates the paper among research on GNN feature mixing, graph bottlenecks, and curvature-based analysis.

Over-smoothing

Over-squashing

Graph curvature

3. Preliminaries

This section formulates GNNs as neighborhood message-passing systems, characterizes over-smoothing and over-squashing, and introduces Ollivier-Ricci curvature on graphs.

3.1. Message Passing Neural Networks

  • MPNNs aggregate information from local neighborhoods, and Equation (1) encompasses popular architectures including GCN, GraphSAGE, GAT, and GIN.Table 1 summarizes their choices of message, update, and aggregation functions.Source: §3.1 · pp. 2–3, Table 1 · p. 3
  • Graph rewiring modifies a graph’s edge set as a preprocessing step before learning on the modified graph.The section briefly introduces SDRF and FoSR as rewiring algorithms.Source: §3.1 · p. 3

3.2. The Over-smoothing and Over-squashing Issues of GNNs

  • Over-smoothing occurs as node features become similar with increasing depth; repeated mean aggregation makes initially distinct node classes virtually indistinguishable by layer 3.The section also gives local and global formulations of this feature-similarity behavior.Source: §3.2 · p. 3
  • Over-squashing occurs when graph bottlenecks impede propagation: receptive fields grow exponentially with depth, compressing messages from many distant vertices into fixed-size vectors.Bottlenecks provide minimal connections between the two sides even as receptive fields expand.Source: §3.2 · pp. 3–4

3.3. Ollivier-Ricci Curvature on Graph

  • Ollivier-Ricci curvature compares the Wasserstein distance between nearby vertices’ random walks with their graph distance; positive, zero, and negative values indicate convergence, equal spacing, and divergence.The graph formulation uses a uniform one-step random walk, matching the smallest graph neighborhood radius.Source: §3.3 · p. 4

4. Analysis Based on Graph Curvature

The analysis links local Ollivier-Ricci curvature to both GNN failure modes: positive curvature is linked to over-smoothing, while negative curvature characterizes bottlenecks linked to over-squashing.

4. Analysis Based on Graph Curvature

  • Positive curvature is associated with overlapping neighborhoods and low transport cost, while sparse connections between neighborhoods yield negative curvature and bottlenecks.Figure 3 illustrates the different local structures associated with edge curvature.Source: §4 · pp. 4–5, Figure 3 · p. 5

4.1. Positive Graph Curvature and Over-smoothing

  • The positive-curvature result covers a wide range of GNNs but excludes GAT; the authors expect it to hold when attention-weight variance is low.GAT's learnable weighted-mean aggregator motivates the exception.Source: §4.1 · p. 5
  • Very positively curved edges force local node features to become similar, and an abundance of such edges can explain over-smoothing in shallow GNNs.The paper links this effect to neighborhoods incorporating roughly the same information and diminishing feature variance.Source: §4.1 · p. 5
  • In regular graphs with edge curvature bounded below by a positive constant and the stated update assumptions, features of any node pair exponentially converge to zero in a typical GNN.The result extends local positive-curvature effects to long-term global behavior under the regular-graph assumption.Source: §4.1 · pp. 5–6

4.2. Negative Graph Curvature and Over-squashing

  • Very negative edge curvature restricts information pathways between neighborhoods and marks local bottlenecks, which are linked to over-squashing.The paper notes that an adequate measure of over-squashing is currently lacking in the literature.Source: §4.2 · pp. 6–7
  • When neighborhood connections are sparse, messages from a neighboring neighborhood can have little effect on a node even at distance two; concentrated links can also create new bottlenecks.The paper identifies effective pathways as connections that do not exacerbate the neighborhood degree ratio.Source: §4.2 · pp. 6–7

5. BORF: Batch Ollivier-Ricci Flow

BORF rewires graphs using Ollivier-Ricci curvature to address over-smoothing and over-squashing together. Its batch design can add or remove edges, while faster curvature approximations remain a direction for future work.

5. BORF: Batch Ollivier-Ricci Flow

  • BORF rewires the graph to suppress over-smoothing and alleviate over-squashing-inducing edges by limiting both ends of the curvature spectrum.Depending on data characteristics, it can add, remove, or leave the total number of edges unchanged.Source: §5 · p. 7
  • In each batch, BORF selects h minimally curved edges and k maximally curved edges, adds connections for the former using reused transport plans, then removes the latter.For each minimally curved edge, the added connection joins the nodes contributing most to its transport cost.Source: §5 · p. 7
  • Wasserstein-distance computation is BORF's computational bottleneck, and incorporating faster approximations to calculate curvature is left for future work.The paper notes that proposed approximations could significantly reduce BORF's computational cost.Source: §5 · pp. 7–8
  • Unlike SDRF and FoSR, BORF can remove edges; its batch rewiring also distributes changes across the graph rather than repeatedly targeting a small outlier subgraph.The paper says this helps preserve graph topology and avoid leaving other regions without geometrical improvement.Source: §5 · p. 8

6. Experiments

Across the reported tasks, BORF performs best on every node-classification task for both GCN and GIN, and on most graph-classification settings. Rewiring improves learning across depths, while the ablation compares edge-removal and edge-addition choices.

Experiment details

  • Experiments compare preprocessing rewiring methods with GCN and GIN using shared model and optimization settings, selecting configurations by validation accuracy.Test accuracy is averaged over 100 random trials with 95% confidence intervals.Source: §6 · p. 8

Ablation study on edge addition/removal

  • The high-depth ablation compares full BORF with edge-removal-only, edge-addition-only, and equal edge-addition/removal variants on GCN.The reported comparison uses the best BORF settings from previous experiments on Cornell and Mutag.Source: §6 · pp. 8–9, Table 4 · p. 9

Results

  • BORF outperforms all alternatives on every node-classification task for both GCN and GIN, and on most graph-classification settings.The reported 95% confidence interval for BORF is almost always smaller than for other methods.Source: §6 · p. 8, Table 2 · p. 9, Table 3 · p. 9
  • At all tested depths, rewired datasets support more effective learning, and unrewired datasets perform worst in five of six scenarios.The authors report that alleviating either over-smoothing or over-squashing alone can still improve learning.Source: §6 · p. 9

7. Conclusion

The conclusion connects local Ollivier-Ricci curvature with both over-smoothing and over-squashing, then proposes BORF to address them together. The authors limit their over-squashing result to a local setting under constraints on graph structure and GNN design.

Conclusion

  • The paper associates positive graph curvature with over-smoothing and negative graph curvature with over-squashing.It presents this as a correspondence between Ollivier-Ricci curvature and both GNN issues.Source: §7 · p. 9
  • BORF is a curvature-based rewiring method proposed to improve GNN performance by addressing both issues simultaneously.Different definitions of the random walk μu may capture different local graph behaviors through curvature.Source: §7 · p. 9

Limitations and societal impacts

  • The over-squashing result is local and depends on constraints on graph structure and GNN design; a more general treatment is left for future work.Source: §7 · p. 9

Supplement for “Revisiting Over-smoothing and Over-squashing using

The supplement outlines message-passing formulations, discusses how over-squashing has been measured, and supplies proof material for the paper’s results. It also notes limits of a Jacobian-based measure and a curvature argument in prior work.

A. Message Passing Neural Networks

  • A message-passing neural-network layer combines message, aggregation, and update functions, with a skip connection optionally supplying the node’s own features.The supplement describes self-loops as one implementation of the skip connection and lists sum, mean, weighted-mean, and max aggregators.Source: A. Message Passing Neural Networks · p. 14

B. Measuring Over-squashing

  • The supplement notes that the Jacobian-based measure of distant-node influence applies only to GNN aggregators with a natural decay effect, such as GCNs.It contrasts this with sum aggregation in GIN, where the described dilution does not occur.Source: B. Measuring Over-squashing · p. 15
  • The authors describe influence distribution as a way to quantify vertices’ relative importance, but say its definition is unwieldy for analysis.Source: B. Measuring Over-squashing · p. 15

C. Proofs

  • The proof appendix invokes an optimal transport plan that leaves mass in place when the source measure is no greater than the target measure at a vertex.The accompanying proof assumes n ≥ m and uses a plan satisfying that condition.Source: C. Proofs · p. 15, §C.1 · p. 15

C.2. Proof of Theorem 4.2

  • For neighboring vertices, the proof bounds the symmetric difference of their extended neighborhoods by 2(1−κ(u, v))n.This bound follows from bounding each one-sided difference by (1−κ(u, v))n.Source: §C.2 · p. 16

C.3. Proof of Proposition 4.3

These supplement sections prove bounds on feature differences and transport-plan counts, then relate message transmission to path counts. The hyperparameter appendix records which rewiring settings were tuned and how rewiring amounts are reported.

C.3. Proof of Proposition 4.3

  • For graphs whose edge curvature is positive and bounded below by δ, the proof uses a diameter bound of ⌊2/δ⌋ to extend a neighboring-node inequality along shortest paths.Source: §C.3 · p. 18

C.4. Proof of Proposition 4.4

  • The transport-plan proof counts matching neighbor pairs and derives the stronger bound 3n0 + 2n1 ≤ n(κ(u, v) + 2).The passage identifies n0 and n1 as counts of two pair types in the construction.Source: §C.4 · pp. 18–19

C.5. Proof of Theorem 4.5

  • The proof of Theorem 4.5 connects Jacobian terms to distinct paths, including paths with self-loops, between vertices.For one path count, the supplement bounds paths without self-loops by |S| and raises the bound to |S| + 2 when self-loops are included.Source: §C.5 · p. 19

D.1. Rewiring hyper-parameters

  • BORF tuning varies the number of batches and the edges added and removed per batch; rewiring totals are reported by graph or for each smaller graph, depending on task type.SDRF tuning varies its curvature upper bound and iteration count, while FoSR tuning varies its iteration count.Source: §D.1 · pp. 19–20

D.2. Architecture and experiment settings

The experiments use fixed GNN architectures across datasets, with three layers for node classification and four for graph classification. Results average 100 random train/validation/test splits, using validation accuracy for model selection and early stopping.

D.2. Architecture and experiment settings

  • Node classification uses three GNN layers and graph classification uses four, with fixed architectures and hidden dimensions within intermediate layers.Each layer is followed by dropout and an activation layer; task-specific settings are listed in Table 9.Source: §D.2 · p. 20, Table 9 · p. 21
  • Mean test accuracy and 95% confidence intervals are computed over 100 random data splits, selecting each trial’s test result by its best validation accuracy.Training stops when validation accuracy fails to improve for 100 epochs.Source: §D.2 · p. 20, Table 8 · p. 21

E.1. Ablation study - Effect of edge addition/removal

BORF’s results vary by comparison: it improves high-depth GCN performance even when restricted to edge addition or removal, performs competitively on Peptides-func, and changes topology less drastically than FoSR. The experiments also compare rewiring options and characterize their effects on degree distributions.

E.1. Ablation study - Effect of edge addition/removal

  • Un-rewired datasets perform worst in most high-depth scenarios, while BORF improves performance even when limited to only edge removal or only edge addition.The ablation compares the best settings with removal-only, addition-only, and equal addition/removal; its depth-specific rewiring hyperparameters were not tuned.Source: §E.1 · p. 21

E.2. Experiment results on long-range graph benchmark

  • On Peptides-func, BORF matches FoSR on GCN while both significantly outperform the baseline and SDRF; BORF performs best on GIN.The table reports comparisons for GCN and GIN rewiring settings.Source: §E.2 · p. 22, Table 12 · p. 22

E.3. Graph topology changes by different rewiring algorithms

  • BORF and SDRF minimally change graph topology by the L1 Wasserstein degree-density measure, whereas FoSR can produce a much more drastic change.The comparison uses kernel densities of base-2 logarithms of node degrees before and after rewiring.Source: §E.3 · p. 23, Figure 5 · p. 23

F. Dataset Statistics

The paper reports dataset statistics and mean and standard deviation of Ollivier-Ricci curvature for datasets used in node and graph classification. Experiments ran on two local servers, with their specifications listed separately.

F. Dataset Statistics

  • The dataset statistics include mean and standard deviation of Ollivier-Ricci curvature, measured on edge values for node classification and per-graph mean curvature for graph classification.The statistics are reported separately for node-classification and graph-classification datasets.Source: F. Dataset Statistics · p. 23, Table 14 · p. 24, Table 15 · p. 24

G. Hardware Specifications and Libraries

Loading 2211.15779v3…