PaperlayerView exact revision on arXiv

Source-linked AI summary

Tackling Over-Smoothing for General Graph Convolutional Networks

Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, Junzhou Huang

arXiv:2008.09864v5cs.LGstat.ML

TL;DR

Deep GCNs are expected to capture richer graph structure, but over-smoothing limits node distinctions, and the theoretical status of architectural refinements remains unclear. The paper analyzes over-smoothing across four GCN variants and proposes random edge removal during training. It reports consistent performance improvements across shallow and deep GCNs, alongside a theoretical account of their convergence behavior.

  • Problem

    It remains unclear whether refined deep-GCN architectures theoretically relieve over-smoothing, which limits node distinctions and weakens expressive power.

    Source: §1 · p. 1

  • Method

    The paper analyzes the depth-wise behavior of generic GCN, GCN with bias, ResGCN, and APPNP, and proposes randomly dropping graph edges during training.

    Source: §1 · p. 2

  • Results

    DropEdge generally and consistently promotes popular GCNs; on Pubmed, 8-layer GCN with DropEdge (91.0%) outperforms 2-layer GCN without DropEdge (89.5%) by 1.5%.

    Source: §1 · p. 2, §6 · pp. 11–12

  • Takeaways & Limitations

    The analysis explains over-smoothing for general GCN models and provides a theoretical basis for DropEdge as a way to alleviate it.

    Source: §1 · p. 2, §6 · p. 12

    DropEdge’s edge-dropping rate must balance reducing over-smoothing against preserving topology modeling; the paper selects it using validation data.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

Increasing the depth of GCN, which is expected to permit more expressivity, is shown to incur performance detriment especially on node classification. The main cause of this lies in over-smoothing. The over-smoothing issue drives the output of GCN towards a space that contains limited distinguished information among nodes, leading to poor expressivity. Several works on refining the architecture of deep GCN have been proposed, but it is still unknown in theory whether or not these refinements are able to relieve over-smoothing. In this paper, we first theoretically analyze how general GCNs act with the increase in depth, including generic GCN, GCN with bias, ResGCN, and APPNP. We find that all these models are characterized by a universal process: all nodes converging to a cuboid. Upon this theorem, we propose DropEdge to alleviate over-smoothing by randomly removing a certain number of edges at each training epoch. Theoretically, DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by dimension collapse. Experimental evaluations on simulated dataset have visualized the difference in over-smoothing between different GCNs. Moreover, extensive experiments on several real benchmarks support that DropEdge consistently improves the performance on a variety of both shallow and deep GCNs.

1 INTRODUCTION

The introduction frames deep GCNs as a route to richer graph representations, but over-smoothing can erase node distinctions and leave the theoretical guarantees of refined architectures unclear. It analyzes four GCN variants and proposes DropEdge, which randomly removes edges during training to alleviate over-smoothing; experiments support gains across shallow and deep models.

1 INTRODUCTION

  • Deep GCNs are expected to capture richer neighborhood topology, but over-smoothing limits node distinctions and weakens expressivity and trainability.The introduction notes that prior work had not established whether refined deep-GCN architectures theoretically relieve over-smoothing.Source: §1 · pp. 1–2
  • Generic GCN, GCN with bias, ResGCN, and APPNP converge to a cuboid as depth tends to infinity.The introduction says bias yields a non-zero radius, ResGCN slows over-smoothing, and APPNP maintains some input information.Source: §1 · p. 2
  • DropEdge randomly removes a selected rate of input-graph edges during training, reducing message passing to alleviate over-smoothing.The paper says it either slows over-smoothing or reduces information loss, and also treats DropEdge as data augmentation through different randomly deformed graph copies.Source: §1 · p. 2
  • Experiments on four node-classification benchmarks support the theorems and show that DropEdge enhances a variety of shallow and deep GCNs.On Cora, the figure contrasts 4- and 8-layer GCNs with and without DropEdge; the 8-layer model without it fails to converge satisfactorily, while both depths work well with it.Source: §1 · p. 2, Figure 1 · p. 2

2 RELATED WORK

Related work covers GCN development and attempts to support deeper architectures, while noting that the theoretical understanding of over-smoothing has been narrower. It distinguishes DropEdge from prior edge-modification approaches and describes other methods that can complement it.

GCNs

  • GCN research spans spectral and spatial methods, with sampling approaches developed to address scalability on large graphs.The cited approaches include node-wise, layer-wise, and graph-wise sampling.Source: §2 · p. 2

Deep GCNs

  • Prior deep-GCN approaches include residual mechanisms, personalized PageRank, dense connections, and adaptive local-global information balancing.The section also notes that residual GCNs performed worse at depth three and beyond in the cited experiments, while identifies over-smoothing without proposing a remedy.Source: §2 · p. 3
  • Earlier theory established subspace convergence for deep GCNs, while this paper analyzes a broader model family and proposes random edge sampling to alleviate over-smoothing.Activation normalization and doubly residual connections are described as complementary approaches.Source: §2 · p. 3

Other related works

  • DropEdge differs from random graph generation and sparse graph learning because it samples different edge subsets across training iterations rather than fixing one modified graph.The paper says this preserves underlying graph information in a probabilistic sense; it also notes that edge-attention dropout had not explored the relation to over-smoothing.Source: §2 · p. 3

3 PRELIMINARIES

This section establishes graph and spectral notation, then introduces generic GCN, bias, residual, and APPNP variants. Its figure contrasts generic GCN’s subspace convergence with the cuboid convergence of general models.

3.1 Graph denotations and the spectral analysis.

  • The augmented normalized adjacency has a largest-eigenvalue multiplicity equal to the number of connected components, with associated eigenvectors defined from component indicators.The setup uses non-negative edge weights, and defines the augmented normalized Laplacian as I minus the augmented normalized adjacency.Source: §3.1 · p. 3

3.2 Variants of GCN

  • Generic GCN recursively updates hidden node features using a nonlinear function and a layer-specific filter matrix.The analysis uses equal layer dimensions for simplicity; the paper implements the nonlinear function as ReLU.Source: §3.2 · pp. 3–4
  • Figure 2 contrasts generic GCN converging to a multi-dimensional subspace with general models converging to a cuboid.Source: Figure 2 · p. 4
  • GCN with bias adds a layer-specific bias term to the generic GCN propagation.The bias is represented as a 1-by-C vector.Source: §3.2 · p. 4
  • ResGCN carries information from the previous layer’s input through residual connections, with α balancing propagation and residual information.Source: §3.2 · p. 4
  • APPNP adds skip connections from the input layer to each hidden layer, and its update trades off graph propagation against the initial features using β.The original version used here omits nonlinearities and weight matrices in each hidden layer.Source: §3.2 · p. 4

4 ANALYSES AND METHODOLOGIES

The section derives a convergence account for deep GCN variants and presents DropEdge as a way to alleviate over-smoothing. It also compares DropEdge with related techniques and discusses how over-smoothing differs between node and graph classification.

4.1 Over-smoothing of General Models

  • Under the stated v < 1 assumption, the four GCN models converge toward a cuboid O(M, r) around the subspace M.The cuboid consists of representations whose distance from M is at most r.Source: §4.1 · pp. 4–5
  • Generic GCN and ResGCN converge to M, while bias-GCN and APPNP retain radius-r cuboids; residuals slow convergence, and larger APPNP β enlarges r but lowers v.For generic GCN, r = 0; the bias-GCN and APPNP cases have r > 0.Source: §4.1 · p. 5

4.2 DropEdge to Alleviate Over-Smoothing

  • DropEdge randomly removes input-graph edges during training, and its changing edge samples preserve the original aggregation in expectation up to a 1 − p multiplier.With sum-to-one normalization, the multiplier is erased; random graph deformations are also presented as a way to prevent over-fitting.Source: §4.2 · pp. 5–6
  • As p increases, DropEdge raises the bounds on λ and can slow over-smoothing; it also decreases the information loss associated with the convergence subspace.The bounds’ gap decreases with p, and λ may fluctuate initially before increasing as p grows.Source: §4.2 · pp. 5–6
  • Alleviating over-smoothing does not guarantee better classification: dropping every edge reduces GCN to an MLP, so the edge-drop rate must balance smoothing and topology modeling.The paper selects p using validation data.Source: §4.2 · p. 6

4.3 Discussions

  • Unlike Dropout, which perturbs features without changing adjacency, DropEdge targets edges; unlike DropNode, it samples edges directly and can retain all node features.Graph sparsification instead optimizes which edges to remove and keeps the resulting graph fixed; DropEdge samples anew during training.Source: §4.3 · pp. 6–7
  • For graph classification, Theorem 2 applies within each graph, where infinitely deep node activations are distinguishable only by degree; nodes in different graphs may converge to different positions in M.The paper notes that over-smoothing within a graph can still cause input-dimension collapse.Source: §4.3 · p. 7

5 EXPERIMENTS

Experiments use a simulated Small-Cora graph to visualize over-smoothing and four node-classification benchmarks to evaluate DropEdge across GCN backbones. Ablations compare DropEdge with dropout, layer-wise sampling, random graphs, GLASSO, and feature-weighted sampling.

5.1 Visualizing over-smoothing on Small-Cora

  • On Small-Cora, GCN approaches the subspace, GCN-b approaches a surrounding cuboid, ResGCN converges more slowly, and APPNP becomes stationary beyond the subspace.With DropEdge at p = 0.5, convergence to the subspace slows and the number of connected components increases.Source: §5.1 · pp. 7–8, Figure 4 · p. 8

5.2 Evaluating DropEdge on different GCNs

  • DropEdge consistently improves testing accuracy across the evaluated cases; on Citeseer, it also preserves promising performance for ResGCN-64, which otherwise fails to classify meaningfully.Table 2 summarizes testing accuracy across backbones.Source: §5.2 · p. 9, Table 2 · p. 9
  • APPNP+DropEdge performs best on Cora and Citeseer, while JKNet+DropEdge performs best on Pubmed and Reddit; most DropEdge models achieve their best accuracy at depths beyond four.For GCN and GCN-b, the reported peak with DropEdge is at d = 4.Source: §5.2 · pp. 9–10
  • APPNP+DropEdge reaches 89.10% on Cora and 81.30% on Citeseer, exceeding previous best accuracies of 87.44% and 79.7%, respectively.DropEdge-based approaches outperform DropNode variants, and adding DropEdge to DAGNN further boosts performance.Source: §5.2 · p. 10, Table 3 · p. 10

5.3.1 On Compatibility with Dropout

  • DropEdge reduces validation loss more than Dropout on GCN-4, and using both together decreases loss further.Figure 7 compares the validation losses.Source: §5.3.1 · p. 10, Figure 7 · p. 11

5.3.2 On Layer-wise DropEdge

  • Layer-wise DropEdge yields lower training loss than standard DropEdge, but comparable validation values; the authors prefer standard DropEdge to avoid overfitting risk and extra sampling time.Figure 7 compares the layer-wise variant's performance.Source: §5.3.2 · p. 10, Figure 7 · p. 11

5.3.3 On Comparisons with ER-Graph and GLASSO

  • DropEdge outperforms ER-generated graphs and GLASSO on the reported comparisons; GLASSO also adds substantial runtime and produced no reasonable Pubmed result after 40 hours.The ER comparison averages results over 20 runs; Table 5 reports training time over 400 epochs.Source: §5.3.3 · pp. 10–11, Table 4 · p. 10, Table 5 · p. 10

5.3.4 On Comparisons with the Feature-based Sampling

  • Feature-weighted edge dropping performs slightly better than uniform DropEdge only on Citeseer and worse in the other reported cases.The authors interpret this pattern as supporting unbiased sampling in general.Source: §5.3.4 · p. 11, Table 6 · p. 11

6 CONCLUSION

The paper analyzes over-smoothing in four GCN models and reports that DropEdge generally and consistently improves popular GCNs on Cora, Citeseer, Pubmed, and Reddit. The reported gains from deeper DropEdge models are modest but meaningful, alongside the paper’s theoretical account of over-smoothing.

6 CONCLUSION

  • DropEdge generally and consistently improves popular GCNs on Cora, Citeseer, Pubmed, and Reddit.The analysis covers generic GCN, GCN with bias, ResGCN, and APPNP.Source: §6 · p. 11
  • On Pubmed, 8-layer GCN with DropEdge (91.0%) outperforms 2-layer GCN without DropEdge (89.5%) by 1.5%, though deep-model improvements are described as modest.The authors also present their theoretical analyses and experiments as useful for future graph-learning work.Source: §6 · p. 12

Related papers

Loading 2008.09864v5…