PaperlayerView exact revision on arXiv

Source-linked AI summary

PairNorm: Tackling Oversmoothing in GNNs

Lingxiao Zhao, Leman Akoglu

arXiv:1909.12223v2cs.LGstat.ML

TL;DR

Deep GNNs can lose performance as repeated graph convolutions oversmooth node representations, while the precise effects of oversmoothing require separate characterization. The paper introduces PairNorm, which preserves pairwise feature distances through parameter-free normalization and improves robustness to depth, especially when missing features make deeper propagation useful.

  • Problem

    Deep GNNs suffer performance degradation associated with oversmoothing, while node-wise and feature-wise oversmoothing require distinct quantification.

  • Method

    PairNorm normalizes intermediate representations by preserving total pairwise feature distance across layers without changing network architecture or adding parameters.

  • Results

    PairNorm makes GCN, GAT, and SGC more robust to oversmoothing and significantly outperforms vanilla GNNs when deeper models benefit classification.

  • Takeaways & Limitations

    PairNorm is broadly applicable and provides performance gains when the task benefits from more layers, including semi-supervised node classification with missing vectors.

  • Takeaways & Limitations

    PairNorm can slightly reduce performance when missing-feature rate is 0% because shallow networks and limited smoothing are sufficient in the studied datasets.

Abstract

from arXiv · show

The performance of graph neural nets (GNNs) is known to gradually decrease with increasing number of layers. This decay is partly attributed to oversmoothing, where repeated graph convolutions eventually make node embeddings indistinguishable. We take a closer look at two different interpretations, aiming to quantify oversmoothing. Our main contribution is PairNorm, a novel normalization layer that is based on a careful analysis of the graph convolution operator, which prevents all node embeddings from becoming too similar. What is more, PairNorm is fast, easy to implement without any change to network architecture nor any additional parameters, and is broadly applicable to any GNN. Experiments on real-world graphs demonstrate that PairNorm makes deeper GCN, GAT, and SGC models more robust against oversmoothing, and significantly boosts performance for a new problem setting that benefits from deeper GNNs. Code is available at https://github.com/LingxiaoShawn/PairNorm.

1 INTRODUCTION

Deep GNNs can suffer from oversmoothing, in which repeated graph convolutions make node representations indistinguishable and reduce classification performance. The paper proposes PairNorm, an architecture-independent normalization scheme designed to preserve pairwise feature distances and support deeper models.

  • 1 INTRODUCTION: Deeply stacking GNN layers can cause performance drops through overfitting, vanishing gradients, and oversmoothing.Oversmoothing makes node representations indistinguishable across classes.
  • 1 INTRODUCTION: PairNorm is a normalization layer applied between intermediate GNN layers to prevent distant-node features from becoming indistinguishable.It still allows connected nodes in the same cluster to become more similar.
  • 1 INTRODUCTION: PairNorm keeps total pairwise feature distance constant across layers, reducing feature mixing across clusters.The method targets the similarity increase caused by graph-convolution smoothing.
  • 1 INTRODUCTION: PairNorm uses simple centering and scaling operations, adds no parameters, and applies broadly across GNN architectures.The normalization is applied to each layer’s output except the last one.
  • 1 INTRODUCTION: PairNorm enables deeper models without sacrificing performance, with its strongest gains when the task benefits from more layers.The paper motivates this setting using nodes with missing feature vectors.

2 UNDERSTANDING OVERSMOOTHING

The paper separates oversmoothing into node-wise and feature-wise views: graph convolutions can make node representations too similar and wash feature signals toward a graph-dependent stationary state. Using SGC isolates oversmoothing from parameter growth and gradient problems, while row-diff and col-diff quantify the two effects.

  • 2.1 THE OVERSMOOTHING PROBLEM: GNN depth can reduce performance through overfitting, vanishing gradients, and oversmoothing from repeated graph convolutions.The section focuses on oversmoothing as the least understood factor.
  • 2.1 THE OVERSMOOTHING PROBLEM: Graph convolution performs Laplacian smoothing, averaging each node’s features with its neighbors’ features.This can help within clusters but, at depth, mix representations across different clusters.
  • 2.1 THE OVERSMOOTHING PROBLEM: Repeated Laplacian smoothing drives node features toward a stationary point and washes away feature information.The stationary point depends on graph structure rather than input feature values.
  • 2.1 THE OVERSMOOTHING PROBLEM: Row-diff measures average pairwise distances between node-feature rows, while col-diff measures pairwise distances between L1-normalized representation columns.The two measures quantify node-wise and feature-wise oversmoothing, respectively.
  • 2.2 STUDYING OVERSMOOTHING WITH SGC: SGC removes graph-layer projections and nonlinearities, keeping parameter count fixed as convolutions increase.This isolates oversmoothing from overfitting and vanishing-gradient effects.
  • 2.2 STUDYING OVERSMOOTHING WITH SGC: On Cora, SGC performance improves through K = 4, then oversmoothing hurts performance while row-diff and col-diff continue decreasing.The measures provide supporting evidence that oversmoothing increases with more convolutions.

3 TACKLING OVERSMOOTHING

PAIRNORM addresses oversmoothing by preserving total pairwise feature distances after graph convolution, using a simple center-and-scale normalization layer. It supports deeper GNNs, with especially clear gains in the missing-feature setting.

  • Motivation: Graph convolution smooths features over graph structure, but repeated application can oversmooth nodes from different clusters.The underlying optimization encourages graph smoothness without explicitly preventing excessive similarity between disconnected or differently clustered nodes.
  • PAIRNORM: PAIRNORM applies centering and rescaling to graph-convolution outputs so total pairwise squared distance remains constant across layers.In practice, a dataset-specific constant C can replace the original input TPSD value.
  • PAIRNORM: Centering removes the row-wise mean, reducing TPSD computation to a squared Frobenius norm with O(nd) complexity instead of directly evaluating n^2 pairwise distances.Direct computation costs O(n^2d) and can be time-consuming for large datasets.
  • Variants: PAIRNORM-SI scales each centered node representation individually to the same L2-norm s and was more stable for GCN and GAT than standard PAIRNORM.Both variants worked well for SGC; the stricter normalization may help models with more parameters and greater overfitting risk.
  • Results: On Cora, PAIRNORM made SGC, GCN, and GAT performance decay more slowly as layers increased, improving robustness to deeper models.The benchmark datasets generally require no more than four layers, so robustness does not necessarily translate into higher overall test accuracy there.
  • Results: In SSNC-MV with p = 1 on Cora, PAIRNORM models achieved higher test accuracy than vanilla models, typically at a larger number of layers.This setting removes feature vectors from all unlabeled nodes, making deeper propagation useful for recovering effective representations.

4 EXPERIMENTS

Experiments evaluate PAIRNORM-enhanced SGC, GCN, and GAT on SSNC-MV across benchmark datasets and feature-missing settings. PAIRNORM generally enables deeper models and improves or preserves performance, with SGC-PN often outperforming vanilla SGC.

  • Experimental setup: Experiments evaluate SGC, GCN, and GAT on SSNC-MV using four benchmark datasets and feature-missing rates from 0% to 100%.The experiments use Cora, Citeseer, Pubmed, and CoauthorCS, with repeated runs and reported test accuracy at the layer count yielding best validation accuracy.
  • SGC results: PAIRNORM-enhanced SGC performs similarly or better at 0% missing and significantly outperforms vanilla SGC for most higher missing-rate settings.The advantage is especially pronounced at larger missing rates, where SGC-PN also selects larger optimal layer counts.
  • Model comparison: PAIRNORM-enhanced SGC follows the comparable-or-better accuracy trend of simple SGC relative to PAIRNORM-enhanced GCN and GAT across SSNC-MV settings.The authors identify PAIRNORM-enhanced SGC as a strong baseline because of its simplicity and efficiency.
  • GCN and GAT results: Both residual connections and PAIRNORM-SI enable deeper GCN and GAT models and improve performance under SSNC-MV.GCN-PN and GAT-PN achieve performance comparable to or better than skip connections, while combining both techniques can improve results slightly further.

5 RELATED WORK

Related work addresses GNN oversmoothing through skip connections, personalized PageRank-based propagation, and residual or dense connections.

  • Jumping Knowledge Networks use skip connections for multi-hop message passing and support different neighborhood ranges.
  • Personalized PageRank-based propagation preserves locality through teleports, which prevents oversmoothing.
  • Residual and dense connection approaches build on ResNet ideas to address oversmoothing in GNNs.

6 CONCLUSION

The paper concludes that PAIRNORM improves deep-GNN robustness to oversmoothing while remaining efficient, architecture-independent, and parameter-free. Its performance gains are strongest when tasks benefit from more layers, while shallow settings can incur a slight drop.

  • PAIRNORM boosts the robustness of deep GNNs against oversmoothing and can be applied without changing network architecture or adding parameters.The layer is fast to compute and applicable to any GNN.
  • Experiments on real-world classification tasks show performance gains when the task benefits from using more layers.
  • At 0% missing rate, PAIRNORM causes a slight performance drop because shallow networks and limited smoothing are sufficient for the studied datasets.The authors attribute this small decrease to PAIRNORM’s reversing effect in settings where smoothing through 2–4 layers improves generalization.

A.2 DATASET STATISTICS

Table 4 reports dataset statistics for the benchmark datasets used in the experiments.

  • Table 4 presents statistics for the datasets used in the study.

A.3 ADDITIONAL PERFORMANCE PLOTS WITH INCREASING NUMBER OF LAYERS

Across SGC, GCN, and GAT, PAIRNORM-enhanced models are more robust to performance decay as depth increases. Under SSNC-MV, PAIRNORM boosts overall performance by enabling more robust deep GNNs.

  • PAIRNORM provides improved robustness to SGC performance decay due to oversmoothing with increasing numbers of layers.
  • PAIRNORM provides improved robustness against performance decay with increasing numbers of layers for both GCN and GAT.
  • PAIRNORM boosts overall performance under SSNC-MV by enabling more robust deep SGC, GCN, and GAT models.

A.5 ADDITIONAL EXPERIMENTS UNDER SSNC-MV WITH INCREASING MISSING FRACTION p

Under increasing missing fractions in SSNC-MV, PAIRNORM makes GCN and GAT performance more robust and supports deeper models. Pairwise-distance measurements show that PAIRNORM and PAIRNORM-SI preserve separation between random and connected node pairs, addressing oversmoothing in deep GNNs.

  • PAIRNORM-enhanced no-skip GCN and GAT models perform comparably or better than vanilla models in all missing-fraction cases, especially as p increases.
  • PAIRNORM-enhanced no-skip GCN and GAT models leverage a larger layer range, 2-12, as the missing fraction p increases.
  • Adding skip connections helps unnormalized GCN and GAT, while adding skips on top of PAIRNORM does not seem to introduce notable gains.
  • Without normalization, SGC shows rapidly diminishing random-pair APD and APSD; PAIRNORM keeps APSD constant across layers, while PAIRNORM-SI empirically yields more stable APSD and APD.
  • For SGC, PAIRNORM slows the leftward shrinkage of random-pair distance distributions while preserving similar connected-pair distribution behavior.
  • In a 12-layer GCN, unnormalized pair distances reach zero, whereas PAIRNORM and PAIRNORM-SI keep random pairs relatively apart while connected-pair distances shrink.
  • PAIRNORM-SI is generally more stable than PAIRNORM for GCN and GAT, with near-constant random-pair distances in the reported subfigures.
  • The empirical measurements demonstrate that PAIRNORM and PAIRNORM-SI successfully address oversmoothing in deep GNNs.
Loading 1909.12223v2…