PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View

Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, Xu Sun

arXiv:1909.03211v2cs.LGcs.SIstat.ML

TL;DR

GNN over-smoothing can make representations of nodes from different classes indistinguishable, yet why and how it occurs has been little studied. This paper quantifies the problem and proposes regularization and topology-adjustment methods; experiments report reduced over-smoothing and improved performance across multiple GNNs and datasets.

  • Problem

    Over-smoothing makes representations of nodes from different classes indistinguishable, while explanations of why and how it occurs remain limited.

    Source: Introduction · p. 1

  • Method

    The paper measures smoothness and over-smoothness with MAD and MADGap, then proposes MADReg and prediction-based AdaEdge graph adjustment.

    Source: Introduction · pp. 1–2

  • Results

    Across multiple GNNs and datasets, the proposed methods significantly reduce over-smoothing and improve model performance.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The findings identify graph topology as a factor related to information-to-noise ratio and graph-representation smoothness.

    Source: Conclusion and Future Work · p. 7

    AdaEdge can make incorrect graph-adjustment operations, and reducing these operations remains a research direction.

    Source: Conclusion and Future Work · p. 7

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have achieved promising performance on a wide range of graph-based tasks. Despite their success, one severe limitation of GNNs is the over-smoothing issue (indistinguishable representations of nodes in different classes). In this work, we present a systematic and quantitative study on the over-smoothing issue of GNNs. First, we introduce two quantitative metrics, MAD and MADGap, to measure the smoothness and over-smoothness of the graph nodes representations, respectively. Then, we verify that smoothing is the nature of GNNs and the critical factor leading to over-smoothness is the low information-to-noise ratio of the message received by the nodes, which is partially determined by the graph topology. Finally, we propose two methods to alleviate the over-smoothing issue from the topological view: (1) MADReg which adds a MADGap-based regularizer to the training objective;(2) AdaGraph which optimizes the graph topology based on the model predictions. Extensive experiments on 7 widely-used graph datasets with 10 typical GNN models show that the two proposed methods are effective for relieving the over-smoothing issue, thus improving the performance of various GNN models.

Introduction

The paper studies why GNN representations become over-smoothed and identifies graph topology and the information-to-noise ratio as key factors. It introduces metrics and two topology-based methods to measure and alleviate the problem.

Motivation

  • The study examines over-smoothing across 7 widely used graph datasets and 10 typical GNN models, addressing a limitation in explaining why and how it occurs.Over-smoothing makes representations of nodes from different classes indistinguishable and can hurt model performance.Source: Introduction · pp. 1–2

Metrics

  • MAD measures representation smoothness, while MADGap estimates over-smoothness across classes and has a significantly high correlation with model performance.MADGap distinguishes neighboring from remote nodes using their topological distance.Source: Introduction · pp. 1–2

Findings

  • As GNN layers increase, node representations become closer, supporting the paper’s claim that smoothing is an essential nature of GNNs.The authors observe decreasing MAD values as the number of GNN layers increases.Source: Introduction · p. 1

Mechanism

  • Low information-to-noise ratio drives over-smoothing: inter-class edges can inject harmful messages, and topology mismatched to task objectives can increase that noise.Removing inter-class edges and adding intra-class edges based on gold labels was effective in relieving over-smoothing and improving performance.Source: Introduction · pp. 1–2

Contributions

  • MADReg adds a MADGap-based training regularizer, while AdaEdge adaptively removes and adds edges based on predictions; both reduce over-smoothing and improve GNN performance.The introduction reports effectiveness across multiple GNNs and datasets.Source: Introduction · p. 2

Datasets and Models

Experiments use node classification across seven public datasets and ten typical GNN models, with detailed analysis focused on the three citation networks.

Datasets and Models

  • The experiments cover seven public datasets: three citation networks, two coauthor networks, and two Amazon product networks, with detailed analysis on the citation datasets.The datasets are CORA, CiteSeer, PubMed; CS, Physics; and Computers, Photo, respectively.Source: Datasets and Models · p. 2
  • Ten typical GNN models are used to support generalizability, with propagation methods categorized according to Zhou et al. (2018).Baseline implementations are partly based on Fey and Lenssen (2019) and Maehara (2019).Source: Datasets and Models · p. 2

Measuring Over-smoothing Problem from the Topological View

The section defines MAD and MADGap to quantify representation smoothness and over-smoothing, linking over-smoothing to low information-to-noise messages shaped by graph topology. It finds that topology edits can relieve over-smoothing and improve model performance.

MAD: Metric for Smoothness

  • MAD averages cosine distances between selected node representations; across 10 typical GNNs on CORA, MAD fell toward zero as layers increased, indicating increasingly indistinguishable representations.Cosine distance is unaffected by the absolute magnitude of node vectors, making it a measure of representation smoothness.Source: Figure 2 · p. 3, MAD: Metric for Smoothness · p. 3

Information-to-noise Ratio Largely Affects Over-smoothness

  • As neighborhood order increases, the information-to-noise ratio declines, so high-order messages can dilute useful same-class information with cross-class noise and cause over-smoothing.The ratio is defined as the proportion of intra-class pairs among node pairs reachable through the GNN’s propagation steps.Source: Information-to-noise Ratio Largely… · pp. 3–4, Figure 3 · p. 4
  • MADGap compares representation distances for remote and neighboring nodes; higher values indicate useful information outweighs noise, and MADGap correlates strongly with prediction accuracy.Small or negative MADGap indicates over-smoothing and inferior performance; the authors also propose it as a topology-based performance indicator that does not require gold labels.Source: Information-to-noise Ratio Largely… · p. 4, Table 2 · p. 4

Topology Affects the Information-to-noise Ratio

  • Removing inter-class edges or adding intra-class edges raises MADGap and improves model performance on CORA, supporting topology optimization as a way to relieve over-smoothing.The topology-adjustment experiment used gold labels and evaluated GCN, GAT, GraphSAGE, and ChebGCN.Source: Topology Affects the… · pp. 4–5, Figure 5 · p. 5

Topological View

The section presents MADReg and AdaEdge as architecture-agnostic topological interventions for over-smoothing and reports that they improve performance, with gains depending on model depth and topology-edit accuracy.

Topological View

  • MADReg adds a MADGap-based regularizer to the training objective, and AdaEdge adaptively updates graph topology from model predictions; neither is restricted to a specific GNN architecture.Experiments demonstrate their effectiveness across a variety of GNNs.Source: Topological View · p. 5

MADReg: MADGap as Regularizer

  • MADReg uses MADGap to encourage nodes to receive more useful information and less interference noise, calculating the gap on training data alongside cross-entropy loss.The regularization coefficient controls MADReg's influence on the training objective.Source: MADReg: MADGap as Regularizer · p. 5

Relieving Over-smoothing in High-order Layers

AdaEdge: Adaptive Edge Optimization

  • AdaEdge repeatedly trains a GNN, deletes predicted inter-class edges and adds intra-class edges, then retrains from scratch on the updated graph.This self-training procedure adapts topology to the task objective using model predictions.Source: AdaEdge: Adaptive Edge Optimization · p. 6

Improving Performance of GNNs

  • Across 7 datasets, AdaEdge improves performance in most cases, while MADReg helps chiefly as network depth makes over-smoothing more severe.Incorrect topology edits can interfere with training and limit AdaEdge's gains; AdaEdge generalizes better when over-smoothing is not severe.Source: Improving Performance of GNNs · p. 6

Related Work

Prior GNN work largely refines information propagation on static graphs, while related over-smoothing research describes the phenomenon without systematic quantitative analysis. This paper positions topology optimization and an information-to-noise account as its response.

Graph Neural Networks (GNNs)

  • Related GNN architectures improve propagation or aggregation on static graphs but pay less attention to topology (Veličković et al. 2018; Hamilton, Ying, and Leskovec 2017; Xu et al. 2018).Examples include attention-based neighbor aggregation, sampling and aggregation, and using higher-order neighbors.Source: Graph Neural Networks (GNNs) · p. 7
  • AdaEdge targets topology by adding intra-class and removing inter-class edges, unlike DropEdge’s random per-epoch edge dropping (Rong et al. 2019).Other approaches rely on model adaptivity or specialized architectures, whereas AdaEdge is designed for general GNN architectures (Pareja et al. 2019; Fey 2019; Yang et al. 2019b).Source: Graph Neural Networks (GNNs) · p. 7

Over-smoothing Problem in GNNs

  • Prior work identifies over-smoothing in GNNs, characterizes GCN convolution as Laplacian smoothing, encourages output smoothness, or addresses topology-induced misclassification (Li, Han, and Wu 2018; Zhou et al. 2018; Deng, Dong, and Zhu 2019; Yang et al. 2019a).Source: Over-smoothing Problem in GNNs · p. 7
  • This work treats smoothing as essential and distinguishes reasonable smoothing from over-smoothing by information-to-noise ratio, addressing the lack of systematic quantitative research.Deng, Dong, and Zhu (2019) encourage reasonable smoothing, Yang et al. (2019a) address over-smoothing, and Li et al. (2019a) use LSTMs for text classification.Source: Over-smoothing Problem in GNNs · p. 7

Conclusion and Future Work

The study quantifies GNN over-smoothing, links it to information mixing and graph topology, and proposes methods that generally relieve it and improve performance. It identifies wrong graph-adjustment operations in AdaEdge as a limitation and reducing them as future work.

Conclusion

  • MADReg and AdaEdge effectively relieve over-smoothing and generally improve GNN performance.The conclusion reports this result across the study’s extensive experiments.Source: Conclusion and Future Work · p. 7
  • MAD and MADGap measurements indicate that smoothing is inherent to GNNs, over-smoothing arises from over-mixing information and noise, and MADGap correlates highly with model performance.Source: Conclusion and Future Work · p. 7
  • The information-to-noise ratio is related to graph topology, which can be optimized for downstream tasks to relieve over-smoothing.Source: Conclusion and Future Work · p. 7

Future Work

A Experimental Settings … Notations Used in This Paper

The paper's experimental setup spans seven node-classification datasets, specifies repeated split-and-seed evaluation, and defines graph, feature, label, prediction, and layer-state notation.

A Experimental Settings

Experiment Dataset

  • The seven node-classification datasets span citation, coauthor, and Amazon networks; their statistics appear in Table 4, and all graphs are undirected and unweighted.Source: Experiment Dataset · p. 9, Table 4 · p. 9
  • CORA, CiteSeer, and PubMed citation graphs represent papers, with citation edges, bag-of-words title features, and paper-category labels.Source: Experiment Dataset · p. 9
  • Coauthor CS and Coauthor Physics connect coauthors, use authors' paper-keyword features, and label authors by their most active study fields.Source: Experiment Dataset · p. 9
  • Amazon Computers and Amazon Photo connect frequently co-purchased goods, use bag-of-words review features, and label products by category.Source: Experiment Dataset · p. 9

Experimental Details

  • Five random 20/30/rest splits are each run with 10 random seeds, and results are averaged across all 50 runs.Each category contributes 20 training nodes and 30 validation nodes; the remaining nodes are test data.Source: Experimental Details · p. 9
  • Controlled comparisons use the same randomly generated split and seed list for baseline and proposed methods, while holding other hyperparameters fixed.Source: Experimental Details · p. 9

Notations Used in This Paper

  • Notation defines G=(V,E), adjacency A, node features X, class labels l, GNN_k, predicted labels, and layer-j states H_j and h_ji.In semi-supervised node classification, training labels are known and test labels are predicted.Source: Notations Used in This Paper · p. 9

B MAD Global Values on More Datasets

Across CiteSeer and PubMed, MAD values decrease as baseline GNN models gain layers.

B MAD Global Values on More Datasets

  • On CiteSeer and PubMed, MAD values for all baseline GNN models decrease as the number of layers increases.Figure 9 displays MAD values for various GNNs with different layer counts on both datasets.Source: B MAD Global Values on More Datasets · p. 9

C Infomation-to-noise Ratio Experiment on More Datasets · D AdaEdge Algorithm

Across CiteSeer and PubMed, model performance and MADGap rise with the intra-class node ratio in four GNN models; AdaEdge adjusts graph topology using prediction and node-degree heuristics.

C Infomation-to-noise Ratio Experiment on More Datasets

  • In CiteSeer and PubMed, performance and MADGap rise with intra-class node ratio across four GNN models, supporting its importance to over-smoothing and performance.The experiment examines node sets with different information-to-noise ratios among 2-order neighbors.Source: C Infomation-to-noise Ratio Experiment… · p. 9

D AdaEdge Algorithm

  • AdaEdge operates on edges for nodes with high prediction confidence, measured by the maximum softmax value.The paper presents the algorithm in Algorithm 1 and lists heuristics for adjusting graph topology.Source: D AdaEdge Algorithm · p. 9
  • AdaEdge operates on edges for nodes belonging to classes with high prediction precision.Source: D AdaEdge Algorithm · p. 9
  • AdaEdge skips edge operations with a certain probability to control the sparsity of added and removed edges.Source: D AdaEdge Algorithm · p. 9
  • AdaEdge also uses node degree to determine which nodes receive edge operations.Source: D AdaEdge Algorithm · p. 9
  • Table 5 reports MADReg results for GCNs with different layer counts on CORA, CiteSeer, and PubMed; darker color denotes larger improvement over baseline.Source: Table 5 · p. 10

E Supplementary Result of Relieving Over-smoothing

Figure 8 presents supplementary results on relieving over-smoothing in high-layer GNNs across additional models.

F Error Analysis of MADReg

MADReg alleviates over-smoothing and improves deeper GCN performance, while shallow GCN gains little because it is already well trained and has less severe over-smoothing.

F Error Analysis of MADReg

  • MADReg relieves over-smoothing and improves GCN performance especially at greater depths, but offers little improvement for shallow GCNs with less severe over-smoothing.The paper attributes the shallow-model result to the model already being well trained.Source: F Error Analysis of MADReg · p. 10
  • For four-layer models on CORA, CiteSeer, and PubMed, both proposed methods relieve over-smoothing and improve performance in most cases.Figure 8 summarizes prediction accuracy and MADGap using means and standard deviations.Source: Figure 8 · p. 11

Related papers

Loading 1909.03211v2…