PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks

Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, Fragkiskos D. Malliaros

arXiv:2212.02374v2cs.LGcs.AI

TL;DR

Deep GNNs face over-smoothing and over-squashing, which hinder node representations and distant information propagation, and the paper links both challenges to the Laplacian spectral gap and an unavoidable trade-off. It introduces SJLR, which adds and removes edges during training while preserving the graph at evaluation, and reports strong comparative performance across its SGC and GCN experiments.

  • Problem

    Over-smoothing and over-squashing degrade deep GNN representations and distant information propagation, while their relationship has remained insufficiently analyzed.

    Source: §1 · pp. 1–2

  • Method

    The paper links both challenges to the Laplacian spectral gap and introduces SJLR, which uses curvature-based edge addition and removal during training while keeping the evaluation graph unchanged.

    Source: §1 · p. 2, §5.1 · p. 5

  • Results

    SJLR showed the overall best performance in both SGC and GCN experiments, although GDC led on Cora and Pubmed with GCN.

    Source: §6.3 · p. 7

  • Takeaways & Limitations

    The paper concludes that the spectral-gap relationship imposes a topological trade-off, so both over-smoothing and over-squashing cannot be addressed simultaneously from that perspective.

    Source: §1 · p. 2, §7 · p. 8

    SJLR’s edge-addition bank is based on triangles around edges with the most negative curvature, so it cannot directly connect long-distance nodes.

    Source: §6.5 · p. 8

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have succeeded in various computer science applications, yet deep GNNs underperform their shallow counterparts despite deep learning's success in other domains. Over-smoothing and over-squashing are key challenges when stacking graph convolutional layers, hindering deep representation learning and information propagation from distant nodes. Our work reveals that over-smoothing and over-squashing are intrinsically related to the spectral gap of the graph Laplacian, resulting in an inevitable trade-off between these two issues, as they cannot be alleviated simultaneously. To achieve a suitable compromise, we propose adding and removing edges as a viable approach. We introduce the Stochastic Jost and Liu Curvature Rewiring (SJLR) algorithm, which is computationally efficient and preserves fundamental properties compared to previous curvature-based methods. Unlike existing approaches, SJLR performs edge addition and removal during GNN training while maintaining the graph unchanged during testing. Comprehensive comparisons demonstrate SJLR's competitive performance in addressing over-smoothing and over-squashing.

1 INTRODUCTION

Deep GNNs face over-smoothing and over-squashing, which degrade node representations and distant information propagation; their relationship has remained insufficiently analyzed. The paper links both issues to the Laplacian spectral gap, identifies a trade-off, and introduces SJLR, which rewires edges during training while leaving the graph unchanged at evaluation.

1 INTRODUCTION

  • Over-smoothing makes node features increasingly similar across layers, while over-squashing compresses information through bottleneck edges.These issues are especially relevant to graphs with large diameters and long-range dependencies.Source: §1 · p. 1
  • The Cheeger inequality reveals an inherent trade-off between over-smoothing and over-squashing: improving one aspect worsens the other.The paper relates both problems to the spectral gap of the Laplacian.Source: §1 · p. 2
  • The paper identifies the relationship between the two problems as a fundamental topological connection in deep GNNs.It establishes the connection using random-walk properties, the Laplacian spectral gap, and the Cheeger inequality.Source: §1 · p. 2
  • SJLR adds and removes edges during GNN training while keeping the original graph unchanged during evaluation.It uses Jost and Liu Curvature, a computationally efficient approximation of Ollivier’s Ricci curvature that preserves important theoretical properties.Source: §1 · p. 2
  • Comprehensive benchmarking and analysis provide empirical evidence that SJLR mitigates both over-smoothing and over-squashing.The introduction characterizes its performance as competitive on homophilous and heterophilous graph datasets.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses over-smoothing and over-squashing through graph rewiring, normalization, architectural changes, subgraphs, and transformers. The paper distinguishes its contribution by formally proving a trade-off and arguing for both edge addition and removal.

2 RELATED WORK

  • Prior approaches to over-smoothing include graph rewiring, embedding or weight normalization, architectural changes, and localized-subgraph methods.Examples include PageRank-based preprocessing [18, 19], edge dropping [25] [42], and dilated convolutions or residual and dense connections [32].Source: §2 · p. 2
  • Earlier over-squashing work explored rewiring and theoretical analysis, while graph transformers offer another approach but may have computational and memory limitations.Alon and Yahav [1] add a fully adjacent matrix in the final GNN layer; Topping et al. [48] use Ricci-flow curvature concepts.Source: §2 · pp. 2–3
  • Earlier methods addressing both over-smoothing and over-squashing were empirical; the paper claims a formal trade-off proof and argues that both edge addition and removal are necessary.Karhadkar et al. [27] used edge addition, while Liu et al. used curvature-based edge removal.Source: §2 · p. 2

3 NOTATION AND BACKGROUND

This section establishes notation for undirected, connected, unweighted graphs and introduces the Laplacian, message-passing networks, and the two deep-GNN challenges. The Cheeger constant connects graph bottlenecks to the normalized Laplacian’s spectral gap.

3 NOTATION AND BACKGROUND

  • The paper uses calligraphic letters for sets, bold uppercase letters for matrices, bold lowercase letters for vectors, and N_i for node i’s neighbors.Graphs are represented by vertices and edges; their adjacency, degree, and normalized Laplacian matrices are defined.Source: §3 · p. 3, §3.1 · p. 3

3.2 Cheeger Inequality and Cheeger Constant

  • For graph G, larger λ2 increases h_G, with h_G ≥ λ2/2; the paper relates h_G to the first non-zero eigenvalue of L_sym.Source: §3.2 · p. 3

3.3 Message Passing Neural Networks (MPNNs)

  • A generic MPNN layer uses an augmented normalized adjacency matrix, message functions, and an update function to produce node embeddings.The paper defines the input features and identifies the message and update functions as components of the layer.Source: §3.3 · p. 3

3.4 Over-smoothing

  • Repeated graph-convolution smoothing can mix embeddings from different clusters as layers are stacked.The paper describes this as repeated application of a random-walk transition matrix that converges to a stationary distribution and washes away feature information.Source: §3.4 · p. 3

3.5 Over-squashing

  • Over-squashing concerns distortion of distant-node information as a GNN’s receptive field grows with hop distance.In many graphs the receptive field grows exponentially, requiring an exponential amount of neighboring-node information to be compressed into fixed-size vectors.Source: §3.5 · p. 3

4 UNDERSTANDING THE OVER-SMOOTHING VS. OVER-SQUASHING TRADE-OFF

The analysis ties exponential convergence of deep GNN representations to the Laplacian spectral gap, then relates that gap to a Cheeger-based trade-off between smoothing and bottlenecks. Edge changes shift mixing behavior in opposite directions, while the formal analysis uses linear GNN proxies.

4.1 The Stationary Distribution on Graphs

  • GNN representations converge exponentially toward a stationary distribution, with the convergence rate depending on the Laplacian spectral gap λ2.The paper uses this relationship to connect over-smoothing and over-squashing, and notes that sparsification can alleviate over-smoothing.Source: §4.1 · p. 4
  • Reducing a graph’s maximum degree promotes smaller λ2 values, which increase the number of steps needed to approach the stationary distribution.The passage links this effect to making the graph sparser.Source: §4.1 · p. 4

4.2 Over-smoothing and Over-squashing

  • Theorem 3 connects mixing steps s with the Cheeger constant h_G: faster convergence corresponds to less bottleneckness, while bottlenecks delay convergence.The paper describes these directions as an inherent trade-off: reducing over-squashing by accelerating convergence worsens over-smoothing, and avoiding over-smoothing through bottlenecks worsens over-squashing.Source: §4.2 · p. 4
  • Removing edges raises mixing steps, favoring less over-smoothing, whereas adding edges raises λ2, favoring less over-squashing; these changes create a topological trade-off.Figure 2 compares mixing steps against numbers of removed or added edges in one two-cluster stochastic block model and one Erdős-Rényi graph.Source: Figure 2 · p. 4, §4.2 · p. 4
  • The theoretical connection is studied using SGC as a proxy, so the results apply to linear-based GNNs; analysis of more complex architectures is left for future work.SGC removes projection parameters and nonlinear activations between layers.Source: §4.2 · p. 4

5 CURVATURE REWIRING ALGORITHM

The section motivates curvature-based rewiring through links between curvature, graph bottlenecks, and receptive-field growth. SJLR uses JLC and node features to add and remove edges stochastically during training, seeking a dataset-specific balance while leaving the graph unchanged at test time.

5 CURVATURE REWIRING ALGORITHM

  • Positive curvature bounds the spectral gap and Cheeger constant, while increasing curvature makes the graph less bottlenecked.The section also connects positive JLC to polynomial rather than exponential receptive-field growth.Source: §5 · p. 5
  • JLC is less computationally complex than BFC while retaining the same theoretical properties for polynomial receptive-field growth.BFC requires counting triangles and 4-cycles, making it computationally intensive.Source: §5 · p. 5

5.1 Stochastic Jost and Liu Curvature Rewiring Details

  • During training, SJLR stochastically adds and drops edges using JLC and node-embedding information, while leaving the initial graph unchanged during testing.Validation-selected p_A, p_D, and α let SJLR favor more additions or removals for a dataset’s trade-off.Source: §5.1 · p. 5, Figure 3 · p. 5
  • SJLR ranks edges by JLC, builds candidate additions from missing edges that form triangles with low-JLC edges, and scores each candidate by average JLC improvement.The improvement is computed for existing edges forming triangles with the candidate edge in the augmented graph.Source: §5.1 · pp. 5–6
  • Potential edge additions can be partially parallelized, and SJLR is architecture-agnostic, although the experiments test only SGCs and GCNs.The algorithm normalizes JLC and improvement scores before using distances and probabilities to make edge changes during each layer’s training.Source: §5.1 · p. 6

6 EXPERIMENTAL FRAMEWORK AND RESULTS

Across SGC and GCN experiments, SJLR showed the overall best performance, with results also indicating a trade-off between adding and removing edges. The section reports the experimental setup, runtime comparison, ablation findings, and implementation limitations.

6.1 Experiments

  • Experiments compared eight methods across nine datasets, using SGC and GCN backbones and test accuracies with bootstrapped 95% confidence intervals.For Cora, Citeseer, and Pubmed, 1,500 nodes formed the development set; other datasets used 60/20/20 train-validation-test splits.Source: §6.1 · pp. 6–7

6.2 Implementation Details

  • Methods used shared architectural components and were trained for 1,000 epochs; SDRF was implemented with JLC rather than BFC because BFC made hyperparameter optimization computationally demanding.Hyperparameters were optimized separately for dataset-preprocessing combinations by random search over 100 data splits.Source: §6.1 · p. 6, §6.2 · p. 7

6.3 Results

  • SJLR showed overall best performance with both SGC and GCN; rewiring methods dominated most SGC datasets, while GDC led on homophilous Cora and Pubmed with GCN.SJLR also outperformed SDRF and FoSR on all datasets; the authors note their theoretical analysis assumes no nonlinear activations.Source: §6.3 · p. 7, Table 2 · p. 7, Table 3 · p. 7
  • GDC and Fully-Adjacent layers require specific architectural changes; GDC results were achieved only with weight decay in the first graph convolutional layer.The authors note their theoretical results assume no nonlinear activation functions, potentially missing nuances for GCN.Source: §6.3 · pp. 7–8
  • Across ten repetitions, JLC had a large computation-time advantage over BFC as node counts varied, making JLC more suitable in practice.Figure 4 compares average running time for the two curvature metrics.Source: §6.3 · p. 8, Figure 4 · p. 8

6.4 Ablation Study

  • The ablation findings indicate that adding and removing edges are complementary: using both generally outperformed either strategy alone, supporting a compromise between over-smoothing and over-squashing.The authors contrast this with recent methods that only add or only remove edges.Source: §6.4 · p. 8, Table 4 · p. 8

6.5 Limitations

  • SJLR’s expanded hyperparameter search makes optimization harder, and its edge-addition bank cannot directly connect long-distance nodes.The authors note that distance-weighted curvature metrics could address the latter limitation, but their computational cost makes them impractical for large-scale graphs.Source: §6.5 · p. 8

7 CONCLUSIONS

The paper links over-smoothing and over-squashing through the normalized Laplacian’s spectral gap and uses the Cheeger inequality to establish a topological trade-off. It introduces SJLR, reports improved node-classification performance across homophilous and heterophilous datasets, and points to hyperparameter optimization as a future research direction.

7 CONCLUSIONS

  • The normalized Laplacian’s spectral gap connects over-smoothing and over-squashing, and the Cheeger inequality reveals a trade-off that limits simultaneous topological alleviation.The paper describes this as an inherent limitation of addressing both problems from a topological perspective.Source: §7 · p. 8
  • SJLR uses a bound of Ollivier’s Ricci curvature and outperformed previous methods on homophilous and heterophilous graph datasets for node classification.The conclusion describes SJLR as computationally efficient compared with previous methods such as SDRF while preserving essential theoretical properties.Source: §7 · p. 8
  • The paper identifies neural architecture search as a possible way to facilitate SJLR hyperparameter optimization.This is presented as one direction for future work on curvature-based methods.Source: §7 · p. 8

A PROOF OF THEOREM 3

The proof relates convergence of a random walk to its eigenvalues and derives a modified-weight bound for convergence in ℓ2 distance. It also identifies the step count needed to approach the stationary distribution within ε.

A PROOF OF THEOREM 3

  • The proof expands f^T D^-1/2 in the orthonormal eigenfunctions associated with the graph’s eigenvalues.Source: A PROOF OF THEOREM 3 · pp. 8–9
  • For a weighted graph, the weights can be modified by a constant c; the lazy walk corresponds to c = 1.The proof describes the eigenvalues of the weighted graph after modification.Source: A PROOF OF THEOREM 3 · p. 9
  • The modified random walk corresponding to weights w′ has an improved bound for convergence rate in ℓ2 distance.The proof first considers the distance between f^T P^s and the stationary distribution, then derives a step count s for distance at most ε.Source: A PROOF OF THEOREM 3 · pp. 8–9

B MIXING TIME AND CHEEGER CONSTANT

This section relates mixing time to the Cheeger constant for ergodic, reversible Markov chains. It also describes how the step count and Cheeger constant vary in opposite limiting regimes.

B MIXING TIME AND CHEEGER CONSTANT

  • The section gives an upper bound on mixing time τ(ε) for an ergodic Markov chain in terms of its Cheeger constant.The stated theorem applies to ergodic and reversible chains and defines π* as the minimum stationary probability over the state space.Source: B MIXING TIME AND CHEEGER CONSTANT · p. 9
  • A Markov chain can be represented as a random walk on a weighted directed graph, and mixing time measures approach to its stationary distribution.Source: B MIXING TIME AND CHEEGER CONSTANT · p. 9
  • The section states that s tends to infinity if and only if h_G tends to zero, while h_G tending to infinity corresponds to s tending to zero.Source: B MIXING TIME AND CHEEGER CONSTANT · p. 9

C SWEET POINT

The section formulates an optimization problem for a compromise in the over-smoothing–over-squashing trade-off, then motivates SJLR as a heuristic instead of solving it directly.

C SWEET POINT

  • The optimization seeks a “sweet point” in the over-smoothing versus over-squashing trade-off.The formulation uses a regularization parameter and a hyperparameter ε, with the spectral gap of G′ identified in the accompanying text.Source: C SWEET POINT · p. 9
  • The optimization faces structural, computational, and tuning challenges: E′ may differ substantially from E, computing the Cheeger constant is NP-hard, and ρ and ε require task-specific data-driven tuning.The text notes that repeated Cheeger-constant calculations may be required.Source: C SWEET POINT · p. 9
  • Solving the combinatorial optimization problem is described as practically infeasible, so the section proposes SJLR as a heuristic.SJLR relates indirectly to the Cheeger constant through the JLC metric and to the mixing step through Lemma 2 when dropping edges.Source: C SWEET POINT · p. 9

Related papers

Loading 2212.02374v2…