PaperlayerView exact revision on arXiv

Source-linked AI summary

Simple and Deep Graph Convolutional Networks

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, Yaliang Li

arXiv:2007.02133v1cs.LGstat.ML

TL;DR

Most GCNs are shallow because over-smoothing makes deeper node representations indistinguishable. The paper introduces GCNII, combining initial residual connections with identity mapping, and reports theoretical and empirical evidence that deep GCNII prevents over-smoothing and achieves state-of-the-art results across semi-supervised and full-supervised tasks.

  • Problem

    Most current GCN models are shallow because increasing depth causes over-smoothing, limiting the design of truly deep graph convolutional networks.

  • Method

    GCNII extends vanilla GCN with an initial residual connection to the input layer and an identity mapping added to each layer’s weight matrix.

  • Results

    Deep GCNII prevents over-smoothing, expresses K-order polynomial spectral filters with arbitrary coefficients, and achieves new state-of-the-art results across semi-supervised and full-supervised tasks.

  • Takeaways & Limitations

    The two techniques together enable performance to increase with network depth, supporting deep GCN architectures rather than treating depth solely as a burden.

  • Takeaways & Limitations

    Initial residual connections alone are insufficient for extending GCN to a deep model because repeated nonlinear operations can cause over-fitting and performance drops.

Abstract

from arXiv · show

Graph convolutional networks (GCNs) are a powerful deep learning approach for graph-structured data. Recently, GCNs and subsequent variants have shown superior performance in various application areas on real-world datasets. Despite their success, most of the current GCN models are shallow, due to the {\em over-smoothing} problem. In this paper, we study the problem of designing and analyzing deep graph convolutional networks. We propose the GCNII, an extension of the vanilla GCN model with two simple yet effective techniques: {\em Initial residual} and {\em Identity mapping}. We provide theoretical and empirical evidence that the two techniques effectively relieves the problem of over-smoothing. Our experiments show that the deep GCNII model outperforms the state-of-the-art methods on various semi- and full-supervised tasks. Code is available at https://github.com/chennnM/GCNII .

1. Introduction

GCNs are effective on graph-structured data, but their depth is limited by over-smoothing, which makes node representations indistinguishable. GCNII addresses this open problem with initial residual connections and identity mapping, enabling deep models with strong performance.

  • GCNs generalize CNNs to graph-structured data by applying a shared linear transformation to each node’s neighbors followed by nonlinear activation.
  • Most GCNs perform best with two layers because deeper networks tend to suffer from over-smoothing and lose distinguishable node representations.
  • Existing approaches relieve over-smoothing or capture higher-order information, but remain limited in depth or do not retain deep nonlinear expressive power.
  • GCNII extends vanilla GCN with initial residual connections from the input layer and identity mappings added to each weight matrix.
  • Experiments report that deep GCNII prevents over-smoothing and achieves new state-of-the-art results across semi-supervised and full-supervised tasks.
  • The paper provides theoretical analysis showing that GCNII can express polynomial spectral filters with arbitrary coefficients, unlike the predetermined coefficients of vanilla GCN.

2. Preliminaries

The preliminaries define graph spectral representations, normalized graph convolution, and several approaches to multi-hop propagation. These methods differ in how they control depth, locality, over-smoothing, and representation order.

  • For a self-looped graph, the adjacency and degree matrices are ˜A = A+I and ˜D = D+I, while node features form the matrix X.
  • Graph convolution applies a spectral filter through the Laplacian eigendecomposition, with γ specifying the spectral filter coefficients.
  • Vanilla GCN approximates graph convolution with a first-order polynomial and uses renormalization to obtain the normalized propagation matrix ˜P.
  • A graph convolutional layer applies the normalized propagation operation followed by a weight transformation and ReLU activation.
  • Stacking K vanilla GCN layers corresponds to a fixed Kth-order polynomial filter on the self-looped graph’s spectral domain.
  • APPNP uses Personalized PageRank and truncated power iteration to aggregate multi-hop information while decoupling feature transformation from propagation.
  • JKNet combines representations from previous layers to capture different orders for graph substructures and relieve over-smoothing.
  • DropEdge randomly removes edges and renormalizes the graph convolution matrix to retard the convergence associated with over-smoothing.

3. GCNII Model

GCNII extends GCN with initial residual connections and identity mappings to support deep networks while addressing over-smoothing. The design is motivated theoretically, empirically, and by iterative shrinkage-thresholding.

  • Stacking K GCN layers yields a polynomial filter of order K with fixed coefficients, limiting expressiveness and contributing to over-smoothing.
  • GCNII combines the smoothed representation with the initial representation H(0) and adds an identity matrix to each layer’s weight matrix.The two modifications are controlled by hyperparameters αℓ and βℓ.
  • Initial residual connections preserve at least a fraction αℓ of each node’s input-layer representation after many layers.The paper suggests setting αℓ=0.1 or 0.2 in practice.
  • Initial residual connections alone are insufficient for deep GCNs because repeated nonlinear operations can cause over-fitting and performance degradation.APPNP therefore uses linear combinations across layers and remains shallow.
  • Identity mapping adds In to W(ℓ), while sufficiently small βℓ lets deep GCNII ignore W(ℓ) and essentially simulate APPNP.
  • Regularizing W(ℓ) makes the singular values of (1−βℓ)In+βℓW(ℓ) close to 1, relieving information loss associated with deep GCN convergence.

4. Spectral Analysis

The analysis explains how deep vanilla GCNs converge toward over-smoothed representations and shows that GCNII retains greater spectral expressiveness and information at arbitrary depth.

  • Spectral analysis of multi-layer GCN: The vanilla GCN’s convergence is linked to a lazy random walk whose eventual stationary state leads to over-smoothing.The convergence rate depends on the graph’s spectral gap and node degree.
  • Spectral analysis of multi-layer GCN: As K approaches infinity, the vanilla GCN representation converges to a stationary vector determined by graph degree and the initial signal.This stationary vector carries only degree information and the inner product between the initial signal and a degree-weighted all-one vector.
  • Spectral analysis of multi-layer GCN: Higher-degree nodes are conjectured to converge faster to the stationary state and therefore be more likely to suffer from over-smoothing.The paper states that this conjecture will be tested on real-world datasets.
  • Spectral analysis of GCNII: A K-layer vanilla GCN simulates a fixed-coefficient polynomial filter, limiting its expressive power and contributing to over-smoothing.GCNII instead expresses a K-order polynomial filter with arbitrary coefficients.
  • Spectral analysis of GCNII: Deep GCNII can retain information from both input features and graph structure even as K goes to infinity, preventing over-smoothing under the stated analysis.APPNP and GDC use fixed Personalized PageRank-style coefficients, whereas GCNII learns its coefficient vector from input features and labels and applies ReLU at each layer.

5. Other Related Work

Related work includes spectral, wavelet, attention-based, and sampling-based approaches for improving GCN flexibility, locality, scalability, or graph representation learning.

  • Spectral and attention-based methods: Spectral GCN research includes adaptive graphs, graph wavelet bases, and attention-based edge weighting.These directions target task-driven flexibility, sparseness and locality, or learned use of node information and attributes.
  • Experimental datasets: Table 1 reports statistics for the datasets used in the paper’s experiments.The experimental setup includes citation and web-network datasets for node classification.
  • Sampling-based methods: Sampling-based GCN methods improve scalability through fixed-size neighborhood sampling, importance sampling, or graph-clustered minibatches.The cited methods construct computationally smaller training neighborhoods or minibatches.

6. Experiments

The experiments evaluate GCNII and GCNII* across semi-supervised, full-supervised, and inductive node-classification tasks. Across these settings, the results support deep models using initial residual connections and identity mapping to mitigate over-smoothing.

  • Semi-supervised Node Classification: GCNII and GCNII* achieve new state-of-the-art performance across Cora, Citeseer, and Pubmed semi-supervised node classification.GCNII outperforms previous state-of-the-art methods by at least 2%.
  • Semi-supervised Node Classification: 64-layer GCNII models achieve the reported semi-supervised result, while GCNII performance generally improves with depth on Cora and Citeseer.On Pubmed, the best results occur at 16 layers and remain similar at 64 layers.
  • Full-Supervised Node Classification: GCNII and GCNII* achieve new state-of-the-art results on 6 out of 7 full-supervised datasets.GCNII* outperforms APPNP by over 12% on Wisconsin.
  • Inductive Learning: GCNII and GCNII* achieve new state-of-the-art performance on PPI, with GCNII using a 9-layer model while baselines use at most 5 layers.The PPI evaluation reports Micro-averaged F1 scores.
  • Over-smoothing Analysis: Higher-degree nodes lose classification accuracy more rapidly as GCN depth increases, and 64-layer GCN cannot classify nodes with degrees larger than 100.This experiment examines accuracy by node-degree group on Cora, Citeseer, and Pubmed.
  • Ablation Study: Applying initial residual connections and identity mapping together makes accuracy increase with network depth, whereas either technique alone is insufficient.Identity mapping alone marginally slows over-smoothing; initial residual connections relieve it significantly but retain best performance at two layers.

7. Conclusion

The conclusion presents GCNII as a simple deep GCN that addresses over-smoothing through initial residual connections and identity mapping. Theory and experiments support its expressive power and state-of-the-art performance across semi- and full-supervised tasks.

  • Conclusion: GCNII prevents over-smoothing through initial residual connections and identity mapping.The model extends the vanilla GCN with these two techniques.
  • Conclusion: GCNII can express a K-order polynomial filter with arbitrary coefficients.The conclusion contrasts this expressive property with the fixed behavior of vanilla multi-layer GCNs.
  • Conclusion: Theoretical and empirical evidence indicates that higher-degree nodes are more likely to suffer from over-smoothing in vanilla GCNs.This conclusion is based on the paper’s analysis and experiments.
  • Conclusion: Deep GCNII achieves new state-of-the-art results on various semi- and full-supervised tasks.The paper identifies attention mechanisms and ReLU behavior as directions for future work.

A.1. Proof of Theorem 2

The proof of Theorem 2 establishes that GCNII can represent a K-th order polynomial filter with arbitrary coefficients. It does so by constructing parameters whose resulting coefficients match the target filter.

  • Proof setup: The proof reduces GCNII to a weaker setting with fixed αℓ=0.5 and scalar weight matrices γℓI_n.The input signal is assumed non-negative so the ReLU operation can be removed.
  • Representation: The final GCNII representation is obtained by expressing the propagated signal as the corresponding polynomial filter applied to the input feature.The proof connects the representation, graph filter, and reordered summation expressions.
  • Coefficient matching: The target polynomial filter is represented by an equation system matching its coefficients to the coefficients generated by GCNII.The proof seeks γℓ values for ℓ=0,...,K−1 that make the two coefficient sets equivalent.
  • Coefficient matching: The coefficient equations involve partial products of γ_k over ranges determined by the layer index.This structure is used to solve the parameter system recursively.
  • Conclusion: A K-layer GCNII can express the K-th order polynomial filter with arbitrary coefficients θ.The proof notes a rare case in which the target filter ignores all features from a particular hop and uses a sufficiently large parameter to approximate it.

A.2. Proof of Theorem 1

The proof of Theorem 1 uses a Cheeger-inequality bound for lazy random walks on a connected self-looped graph. This bound controls entries of the K-step transition probability vector and yields the theorem.

  • Random-walk bound: The proof invokes the Cheeger Inequality for lazy random walks on a connected self-looped graph.The spectral gap of the graph appears in the transition-probability bound.
  • Random-walk bound: Lemma 1 bounds the j-th entry of the K-th transition probability vector from node i using node degrees and the spectral gap.The vector is denoted p_i^(K), and λ_{G} denotes the spectral gap.
  • Applying the bound: The proof expresses the transformed input feature as a linear combination of standard basis vectors.Each basis vector is connected to a K-step random-walk transition vector.
  • Applying the bound: Applying Lemma 1 bounds the relevant entries of the resulting representation in terms of the degrees of nodes i and j.The same degree-dependent bound is used after expanding the transformed feature.
  • Conclusion: The theorem follows after substituting the transition-probability bound into the representation derived in the proof.The proof concludes directly after establishing the entrywise bound.

B. Hyper-parameters details

The semi-supervised experiments use Table 6 to specify GCNII training settings, while Table 7 provides full-supervised settings for the models summarized in Table 5.

  • Semi-supervised configuration: Table 6 lists GCNII’s semi-supervised training configuration and covers the hyperparameters used for Table 2.The configuration includes layer count, hidden dimension, dropout, λ, and L2c regularization, with separate weight decay terms for dense and convolutional layers.
  • Full-supervised configuration: Table 7 summarizes the full-supervised training configurations for the models evaluated in Table 5.The listed search space includes layers, dropedge, αℓ, λ, and L2 regularization.
  • Full-supervised configuration: The full-supervised settings use DropEdge hyperparameters for JKNet and IncepGCN on citation networks, while other cases use grid search.The grid-search layer choices are 4, 8, 16, 32, and 64, alongside specified ranges for dropedge, αℓ, λ, and L2 regularization.
Loading 2007.02133v1…