PaperlayerView exact revision on arXiv

Source-linked AI summary

DropEdge: Towards Deep Graph Convolutional Networks on Node Classification

Yu Rong, Wenbing Huang, Tingyang Xu, Junzhou Huang

arXiv:1907.10903v4cs.LGcs.NIstat.ML

TL;DR

Deep GCNs suffer from over-fitting on limited data and over-smoothing as depth increases. DropEdge randomly removes graph edges during training to augment data and reduce message passing, and experiments show consistent gains across multiple GCN backbones and benchmarks.

  • Problem

    Deep GCNs face over-fitting on small graphs and over-smoothing that makes representations independent of input features and complicates training.

  • Method

    DropEdge randomly drops edges during training, acting as graph data augmentation and reducing message passing.

  • Results

    DropEdge generally and consistently improves popular GCN backbones across Cora, Citeseer, Pubmed, and Reddit, including GCN, ResGCN, JKNet, IncepGCN, and GraphSAGE.

  • Takeaways & Limitations

    DropEdge is a flexible technique that can enhance multiple shallow and deep GCN architectures while addressing both over-fitting and over-smoothing.

  • Takeaways & Limitations

    The theoretical over-smoothing analysis assumes all graph convolutional layers share the same perturbed adjacency matrix; layer-wise analysis is left for future work.

Abstract

from arXiv · show

\emph{Over-fitting} and \emph{over-smoothing} are two main obstacles of developing deep Graph Convolutional Networks (GCNs) for node classification. In particular, over-fitting weakens the generalization ability on small dataset, while over-smoothing impedes model training by isolating output representations from the input features with the increase in network depth. This paper proposes DropEdge, a novel and flexible technique to alleviate both issues. At its core, DropEdge randomly removes a certain number of edges from the input graph at each training epoch, acting like a data augmenter and also a message passing reducer. Furthermore, we theoretically demonstrate that DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by it. More importantly, our DropEdge is a general skill that can be equipped with many other backbone models (e.g. GCN, ResGCN, GraphSAGE, and JKNet) for enhanced performance. Extensive experiments on several benchmarks verify that DropEdge consistently improves the performance on a variety of both shallow and deep GCNs. The effect of DropEdge on preventing over-smoothing is empirically visualized and validated as well. Codes are released on~\url{https://github.com/DropEdge/DropEdge}.

1 INTRODUCTION

Deep GCNs face over-fitting on small graphs and over-smoothing at greater depths. DropEdge addresses both by randomly removing edges during training, improving training and validation behavior across GCN depths and backbones.

  • Deep GCNs can over-fit limited graph data, achieving low training error but high validation error.
  • Over-smoothing drives node representations toward a stationary point unrelated to input features and can cause vanishing gradients.
  • DropEdge randomly drops edges from the input graph during training to alleviate both over-fitting and over-smoothing.
  • As data augmentation, DropEdge creates diverse graph perturbations that can reduce over-fitting; as message passing reduction, it addresses over-smoothing.
  • DropEdge enhances GCN, ResGCN, JKNet, and GraphSAGE across several benchmarks, including when combined with JKNet’s dense connections.

2 RELATED WORK

Prior graph convolutional work developed spectral and spatial GCNs, sampling methods, and deeper architectures, but deep GCN training remains constrained by over-smoothing.

  • Spectral GCNs define graph convolution using graph structure, while later work develops improvements, extensions, and approximations.
  • Sampling-based methods improve scalability through node-wise, layer-wise, and layer-dependent graph sampling.
  • DropEdge differs from attention dropout by formally addressing over-smoothing and evaluating the technique across multiple backbone networks.
  • Most previous work focuses on shallow GCNs, while residual GCNs can perform worse at depths of three layers or beyond.

3 NOTATIONS AND PRELIMINARIES

The paper represents graphs with node features, adjacency matrices, and degree matrices, then applies normalized adjacency propagation with learned filters and nonlinearities.

  • The input graph G consists of nodes V and edges E, with node features X represented as an N×C matrix.
  • The adjacency matrix A records edge relationships, while node degrees sum connected edge weights and form the diagonal degree matrix D.
  • GCN propagation recursively transforms hidden node representations using normalized adjacency, a learned filter matrix, and a nonlinear function.
  • A graph convolutional layer is the one-layer GCN computation defined by this propagation rule.

4 OUR METHOD: DROPEDGE

DropEdge randomly perturbs graph connectivity during training and theoretically targets over-fitting and over-smoothing. Its benefits arise from graph data augmentation, reduced message passing, and altered smoothing behavior.

  • 4.1 METHODOLOGY: At each training epoch, DropEdge randomly sets a proportion p of the input graph’s V edges to zero.
  • 4.1 METHODOLOGY: The resulting adjacency matrix Adrop is renormalized and replaces normalized adjacency during propagation and training.
  • 4.1 METHODOLOGY: DropEdge acts as graph data augmentation by producing varying graph deformations and random subset aggregation during GCN training.
  • 4.1 METHODOLOGY: Layer-wise DropEdge independently perturbs adjacency for each layer, introducing additional randomness compared with a shared perturbation.
  • 4.2 TOWARDS PREVENTING OVER-SMOOTHING: Over-smoothing makes deep GCN representations converge toward a subspace independent of input features, reducing expressive power.
  • 4.2 TOWARDS PREVENTING OVER-SMOOTHING: DropEdge either slows over-smoothing convergence or reduces the information loss caused by convergence to a lower-dimensional subspace.
  • 4.3 DISCUSSIONS: Unlike graph sparsification, DropEdge randomly removes edges during training without optimizing which edges to delete or keeping the output graph fixed.

5 EXPERIMENTS

Experiments evaluate DropEdge across benchmark datasets, backbone architectures, depths, and analyses of over-smoothing and training behavior. DropEdge consistently improves accuracy, supports deeper models, and slows over-smoothing while remaining compatible with Dropout and layer-wise variants.

  • Experimental setup: Experiments evaluate five GCN backbones with depths from 2 to 64 on Cora, Citeseer, Pubmed, and Reddit node-classification benchmarks.The benchmarks include transductive citation-graph tasks and an inductive Reddit task.
  • Overall results: DropEdge consistently improves testing accuracy across the reported datasets and backbone architectures.Table 1 reports comparisons with and without DropEdge; the experiments report models at 2, 8, and 32 layers, with other depths provided in supplementary material.
  • Overall results: 13.5% average improvement on Citeseer is achieved at 64 layers, compared with 0.9% at 2 layers.The passage reports average absolute improvement over backbones under different depths.
  • Overall results: A 32-layer IncepGCN without DropEdge incurs out-of-memory failure, whereas the DropEdge model survives by using a sparser adjacency matrix.This result links edge dropping with reduced memory consumption in the reported experiment.
  • Comparison with SOTAs: 97.02% accuracy on Reddit is obtained by JKNet+DropEdge, exceeding the previous ASGCN result of 96.27%.The comparison uses the best DropEdge performance for each backbone against reported SOTA results.
  • On preventing over-smoothing: With edge-drop rate p = 0.8, layer-to-layer output distances remain higher and converge more slowly than with p = 0, indicating less severe over-smoothing.Smaller distance indicates more serious over-smoothing; after training, the distance does not vanish to zero with DropEdge.
  • On compatibility with Dropout: DropEdge and Dropout both facilitate GCN training, their combination decreases validation loss further, and DropEdge provides the larger improvement in the reported ablation.The result supports compatibility between the two techniques.
  • On layer-wise DropEdge: Layer-wise DropEdge achieves lower training loss than standard DropEdge, while validation values are comparable and sampling each layer increases computation.The authors prefer standard DropEdge to reduce over-fitting risk and computational complexity.

6 CONCLUSION

The paper presents DropEdge as an efficient technique for deep GCNs. Experiments across four datasets and multiple backbones show consistent performance improvements, while edge dropping adds input diversity and reduces message passing to address over-fitting and over-smoothing.

  • Conclusion: DropEdge randomly removes edges to add input diversity against over-fitting and reduce message passing against over-smoothing.The technique is applied across GCN, ResGCN, JKNet, IncepGCN, and GraphSAGE.
  • Conclusion: Experiments on Cora, Citeseer, Pubmed, and Reddit show that DropEdge generally and consistently improves popular GCN backbones.The conclusion describes DropEdge as a technique for developing deep GCNs.

A APPENDIX: PROOF OF THEOREM 1

The proof connects DropEdge to spectral and effective-resistance properties of the graph, showing that edge removal can delay over-smoothing or reduce its information loss.

  • Definitions and setup: The proof assumes bounded filter singular values and defines distance from node representations to the limiting subspace M using the Frobenius norm.These definitions support the convergence analysis of deep GCN representations.
  • Spectral convergence: The second-largest eigenvalue λ of the normalized adjacency matrix controls how quickly GCN representations approach the eigenspace associated with the largest eigenvalue.Under the stated conditions, the output exponentially approaches M.
  • Effect of edge removal: The proof uses effective resistance and commute-time results to show that removing suitable edges increases the lower bound of λ.This increase continues until the graph reaches the disconnected case λ = 1.
  • Effect on over-smoothing: Because the smoothing threshold is positively related to λ, edge removal increases the layer count required to reach ϵ-smoothing.The proof expresses this as ˆl(M, ϵ) ≤ ˆl(M′, ϵ) after sufficient edges are removed.
  • Information loss: When edge removal disconnects a component, the limiting subspace dimension increases, reducing the information loss associated with over-smoothing.The proof states this as N − dim(M) > N − dim(M′).

B.1 DATASETS STATISTICS

This appendix identifies the datasets used in the experiments and points to their summarized statistics in Table 3.

  • Dataset statistics: The statistics of all experimental datasets are summarized in Table 3.The supplied appendix material provides the table reference but not its individual dataset values.

B.2 MODELS AND BACKBONES

The appendix describes the backbone implementations, training setup, hyper-parameter search, and validation-loss comparison used to evaluate DropEdge.

  • Backbone architectures: ResGCN, IncepGCN, and JKNet replace convolutional layers in residual, inception, and dense image-classification backbones with graph convolutional layers.The four backbone architectures are illustrated in Figure 5, with input and output graph convolutional layers added to each.
  • Training setup: The implementation includes a self-feature-modeling graph convolution variant and uses Adam with fixed random seeds and 400 training epochs.Experiments are conducted on an NVIDIA Tesla P40 GPU.
  • Validation-loss evaluation: Figure 6 compares validation loss for different backbone depths with and without DropEdge.The notation GCN-n denotes PlainGCN of depth n, with analogous notation for other backbones.

B.4 THE ABLATION STUDY ON CITESEER

The Citeseer ablation appendix compares Dropout and DropEdge configurations and contrasts standard DropEdge with a layer-wise variant, alongside supporting implementation tables.

  • Dropout versus DropEdge: The Citeseer ablation compares four GCN-4 configurations formed by combining DropEdge versus no DropEdge with Dropout versus no Dropout.The four configurations are explicitly listed in the ablation materials.
  • Layer-wise comparison: A separate comparison evaluates the proposed DropEdge against layer-wise DropEdge on Citeseer.The figure distinguishes training and validation curves for both variants.
  • Supporting experiment tables: The appendix includes hyper-parameter, normalization/propagation, and best-accuracy tables supporting the ablation experiments.These materials are identified as Tables 4, 5, and 6, with Table 7 comparing backbones with and without DropEdge.
Loading 1907.10903v4…