Source-linked AI summary
A Survey on Oversmoothing in Graph Neural Networks
T. Konstantin Rusch, Michael M. Bronstein, Siddhartha Mishra
TL;DR
Deep GNNs face over-smoothing, in which node features become increasingly similar with depth, limiting the construction of expressive deep models. The survey axiomatically defines the phenomenon through exponential convergence of suitable similarity measures, reviews and evaluates measures and mitigation methods, and extends the definition to continuous-time GNNs. Its studies show that mitigating over-smoothing is necessary but not sufficient: deep GNNs must also preserve expressive power and feature diversity.
Problem
Deep GNNs face over-smoothing as node features converge toward a non-informative common value with increasing depth, while existing measures lack a unified formal definition.
Method
The survey constructs an axiomatic definition, reviews and empirically evaluates over-smoothing measures and mitigation approaches, and extends the framework to continuous-time GNNs.
Results
Standard GCN, GAT, and GraphSAGE models show exponential convergence of over-smoothing measures to zero, while mitigation methods can preserve similarity measures without preserving performance or expressivity.
Takeaways & Limitations
Mitigating over-smoothing is necessary but not sufficient for expressive deep GNNs; successful designs must balance feature diversity with expressive power.
Takeaways & Limitations
The survey’s illustrative mitigation experiments show that approximately constant Dirichlet energy can coexist with failure to outperform an over-smoothing baseline on Cora.
Abstract
from arXiv · showhide
Node features of graph neural networks (GNNs) tend to become more similar with the increase of the network depth. This effect is known as over-smoothing, which we axiomatically define as the exponential convergence of suitable similarity measures on the node features. Our definition unifies previous approaches and gives rise to new quantitative measures of over-smoothing. Moreover, we empirically demonstrate this behavior for several over-smoothing measures on different graphs (small-, medium-, and large-scale). We also review several approaches for mitigating over-smoothing and empirically test their effectiveness on real-world graph datasets. Through illustrative examples, we demonstrate that mitigating over-smoothing is a necessary but not sufficient condition for building deep GNNs that are expressive on a wide range of graph learning tasks. Finally, we extend our definition of over-smoothing to the rapidly emerging field of continuous-time GNNs.
1 Introduction
Deep GNNs are difficult to develop despite depth often benefiting neural-network performance, because over-smoothing causes node features to converge exponentially toward a non-informative common value. The survey formalizes this phenomenon, unifies existing approaches, evaluates mitigation methods, and emphasizes that preserving feature diversity alone may not preserve expressivity.
- Motivation: Depth is often crucial for neural-network performance, yet practical GNNs remain relatively shallow because deep models face graph bottlenecks, over-squashing, and over-smoothing.The survey focuses on over-smoothing among these challenges.
- Motivation: Over-smoothing loosely denotes the exponential convergence of all node features toward the same constant value as GNN depth increases.Excessive smoothing produces a non-informative limit, although small amounts can benefit regression and classification.
- Research gap: Existing studies use measures including graph Dirichlet energy, cosine similarity, and related scores, but lack a unified general definition of over-smoothing.The survey identifies this conceptual gap as a motivation for its formal treatment.
- Contributions: The survey introduces an axiomatic, formal, and tractable definition intended to unify recent approaches and evaluates methods for mitigating over-smoothing.It also rules out problematic measures such as Mean Average Distance.
2 Definition of over-smoothing
The paper models GNN layers as local message-passing updates and defines over-smoothing through axioms on node-similarity measures. Over-smoothing occurs when such a measure converges exponentially to zero across layers, representing convergence of node features toward constant values.
- Message-passing formulation: A message-passing GNN updates hidden node features layer by layer using a learnable function, graph structure, and an element-wise nonlinear activation.The layer index runs from the input layer through total depth N, with local coupling over each node’s 1-neighborhood.
- Message-passing formulation: The update operates on each node together with the multiset of its 1-neighbors, covering graph convolutions and attentional message passing.This specifies the local relational information used by the layer function.
- Axiomatic definition: The axiomatic framework unifies existing measures while addressing the insufficiency of prior approaches to quantify over-smoothing rigorously.The survey motivates a unified definition because previous measures lacked a formal definition or sufficient quantification criteria.
- Axiomatic definition: A node-similarity measure is required to vanish exactly when all node features equal one constant vector, with further axioms formalizing similarity behavior.The definition assumes without loss of generality that the measure converges to zero.
- Axiomatic definition: Over-smoothing is defined as layer-wise exponential convergence of a node-similarity measure to zero.A quantitative condition is µ(X_n) ≤ C1e^-C2n for n = 0, ..., N, with C1, C2 > 0.
3 Over-smoothing measures
The paper evaluates graph-based similarity measures for over-smoothing, favoring Dirichlet energy over MAD because it satisfies the formal conditions and is numerically more stable. Experiments show exponential convergence of both measures across multiple GNN architectures and graph scales.
- Dirichlet energy satisfies the required node-similarity conditions and is numerically more stable than MAD.The paper refers to the square root of Dirichlet energy simply as Dirichlet energy thereafter.
- MAD can be zero without sufficient over-smoothing, especially in the scalar case when all node features share the same sign.In multidimensional settings, MAD may still converge exponentially under over-smoothing, but requires careful interpretation.
- Using Lp norms with p > 1 provides alternatives that can also satisfy the node-similarity framework.The paper presents Dirichlet energy as a canonical choice while allowing other Lp-based constructions.
- All three tested GNNs—GCN, GAT, and GraphSAGE—show exponential convergence of Dirichlet energy and MAD toward zero on Texas, Cora, and Cornell5.The evaluation uses 128-dimensional random input and hidden features to examine measure dynamics across layers.
- 64 layers is the maximum depth at which the tested models’ Dirichlet energy reaches machine-precision zero, whereas linear convergence would remain around 1 after 128 layers from an initial value around 100.This comparison motivates requiring exponential rather than merely algebraic convergence in the definition.
4 Reducing over-smoothing
The survey groups over-smoothing mitigation methods into normalization and regularization, changed GNN dynamics, and residual connections, then evaluates representative methods across graph scales. These approaches modify propagation, training, or feature reuse to reduce the convergence of node similarities.
- Normalization and Regularization: Normalization and regularization reduce over-smoothing by penalizing similarity-measure deviations, normalizing node embeddings, or adding optimization noise.Examples include EGNNs, Differentiable Group Normalization, and NodeNorm.
- Change of GNN dynamics: Changing GNN dynamics replaces diffusion-like propagation with alternatives such as graph-coupled oscillators, wave-type PDEs, attractive-repulsive forces, or node-wise gradient gating.GraphCON uses nonlinear oscillators, while G2 implements learnable node-wise early stopping through graph-gradient gating.
- Residual connections: Residual connections reuse earlier node features to support very deep GCNs, with GCNII adding a scaled residual connection from the initial features at every layer.Related architectures aggregate features from multiple layers at the final layer.
- Mitigation methods fall into three classes: normalization and regularization, changed GNN dynamics, and residual connections.The evaluation selects DropEdge and PairNorm, GraphCON and G2, and Res-GCN and GCNII as representatives.
- Empirical evaluation: Figure 2 compares layer-wise Dirichlet energy for six mitigation methods across small-scale Texas, medium-scale Cora, and large-scale Facebook graphs.The compared methods are G2-GCN, GraphCON-GCN, PairNorm, GCNII, DropEdge-GCN, and Res-GCN.
5 Risk of sacrificing expressivity to mitigate over-smoothing
The paper tests whether preventing node-feature similarity measures from vanishing is enough to make deep GNNs expressive. Its examples show that constant Dirichlet energy alone can coexist with severe accuracy loss, whereas G2-GCN maintains energy and performance as depth increases.
- Keeping the Dirichlet energy constant is not sufficient for constructing deep GNNs that perform well on learning tasks.A deep GCN with shared parameters and a bias term keeps energy approximately constant but performs poorly as depth increases.
- A bias vector makes a shared-parameter deep GCN’s layer-wise Dirichlet energy approximately constant, while test accuracy still decreases drastically with depth.The comparison spans increasing layer counts in the fully supervised Cora experiment.
- PairNorm also keeps Dirichlet energy approximately constant around 1, yet its Cora test accuracy drops exponentially beyond 32 layers.This contrasts energy preservation with task performance under increasing depth.
- G2-GCN maintains approximately constant layer-wise Dirichlet energy while its performance does not decrease and increases slightly as layer count grows.Among the considered models, the paper identifies G2 as combining over-smoothing mitigation with increasing expressive power.
- The paper concludes that mitigating over-smoothing is necessary but not sufficient because preserving node-feature similarity can sacrifice expressive power.The conclusion is based on experiments comparing energy behavior and performance across deep models.
6 Extension to continuous-time GNNs
The paper extends its definition of over-smoothing to continuous-time GNNs, whose propagation is modeled by graph dynamical systems. In this setting, over-smoothing is exponential convergence over time of a node-similarity measure.
- Continuous-time GNNs: Continuous-time GNNs formulate message passing with graph ODEs or PDEs, making propagation continuous in depth.Different vector fields yield different architectures, and discretized graph differential operators can produce PDE-inspired models.
- Continuous-time GNNs: Continuous-time GNNs include GDE, CGNN, GraphCON, GRAND, BLEND, NSD, and GRAFF.
- Continuous-time over-smoothing: Over-smoothing in continuous-time GNNs is defined as the exponential convergence in time of a node-similarity measure to zero.The definition applies to hidden node features X(t) on an undirected, connected graph.
7 Conclusion
Deep GNNs are needed for long-range interactions, but over-smoothing remains a central challenge. The survey finds that mitigation must preserve expressive power, because reducing feature convergence alone can coincide with declining accuracy.
- Conclusion: Deep GNNs are necessary for effectively processing higher-order long-range interactions, especially in heterophilic graphs.Over-smoothing is one of several problems that complicate constructing deep GNNs.
- Conclusion: Standard GCN, GAT, and GraphSAGE models show exponential convergence to zero for all tested over-smoothing measures across Texas, Cora, and Cornell5 graphs.The evaluation covers small-, medium-, and large-scale graph datasets.
- Conclusion: Mitigating over-smoothing does not necessarily preserve expressive power or accuracy as GNN depth increases.Several methods maintain approximately constant over-smoothing measures while accuracy drops significantly; G2 is reported as an exception.
- Conclusion: Deep GNN design therefore requires balancing over-smoothing mitigation with the expressive power of the underlying model.