PaperlayerView exact revision on arXiv

Source-linked AI summary

Simplifying Graph Convolutional Networks

Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, Kilian Q. Weinberger

arXiv:1902.07153v2cs.LGstat.ML

TL;DR

GCNs may carry unnecessary complexity because they lack a simpler linear predecessor. SGC removes nonlinearities and collapses layers, matching or surpassing GCN performance across tasks while training up to two orders of magnitude faster than sampling-based variants.

  • Problem

    GCNs inherit considerable complexity without a simpler linear predecessor, although simpler methods can ease theoretical analysis and understanding.

  • Method

    SGC removes interlayer nonlinearities and collapses GCN layers into one linear transformation, corresponding to fixed graph filtering followed by logistic regression.

  • Results

    SGC rivals or surpasses GCNs across diverse graph-learning tasks and trains up to two orders of magnitude faster than sampling-based GCN variants.

  • Takeaways & Limitations

    SGC offers an interpretable, computationally efficient graph model whose feature extraction is a fixed low-pass-type filter.

  • Takeaways & Limitations

    On graph classification, SGC falls far behind GIN and more advanced models on QM8.

Abstract

from arXiv · show

Graph Convolutional Networks (GCNs) and their variants have experienced significant attention and have become the de facto methods for learning graph representations. GCNs derive inspiration primarily from recent deep learning approaches, and as a result, may inherit unnecessary complexity and redundant computation. In this paper, we reduce this excess complexity through successively removing nonlinearities and collapsing weight matrices between consecutive layers. We theoretically analyze the resulting linear model and show that it corresponds to a fixed low-pass filter followed by a linear classifier. Notably, our experimental evaluation demonstrates that these simplifications do not negatively impact accuracy in many downstream applications. Moreover, the resulting model scales to larger datasets, is naturally interpretable, and yields up to two orders of magnitude speedup over FastGCN.

1. Introduction

GCNs achieve strong graph-learning results but inherit unnecessary deep-learning complexity without a simpler linear predecessor. This paper introduces Simple Graph Convolution (SGC), a linear simplification that retains comparable performance while improving interpretability and computational efficiency.

  • GCNs stack learned first-order spectral filters and nonlinear activations, achieving state-of-the-art results across citation, social, and other application areas.
  • GCNs inherit considerable complexity from deep learning and lack a simpler linear counterpart that could have preceded them.
  • SGC removes inter-layer nonlinearities and collapses the resulting function into a single linear transformation, fitting significantly fewer parameters than GCNs.
  • SGC feature extraction applies a single fixed filter to each feature dimension, making the model intuitively interpretable and theoretically analyzable.Adding self-loops effectively shrinks the graph spectral domain, producing a low-pass-type filter and locally smooth graph features.
  • Up to two orders of magnitude faster than FastGCN on Reddit, SGC achieves comparable performance to GCNs and other state-of-the-art graph neural networks.Its effectiveness also extends to a wide range of downstream tasks.

2. Simple Graph Convolution

GCNs update node representations through neighborhood averaging, learned linear transformations, and pointwise nonlinearities before classification. Simple Graph Convolution removes intermediate nonlinearities and collapses layer weights, yielding a fixed smoothing operation followed by logistic regression.

  • GCN layers: GCN layers then apply a learned weight matrix and a pointwise activation such as ReLU after local smoothing.The three stages are feature propagation, linear transformation, and nonlinear activation.
  • GCN layers: Each GCN layer averages node features with those of its local neighborhood, distinguishing graph convolutions from MLPs through feature propagation.This local smoothing encourages similar predictions among connected nodes.
  • GCN receptive field: After K layers, each node incorporates feature information from nodes up to K hops away through repeated neighborhood averaging.Thus, GCN depth expands the receptive field in addition to building feature hierarchies.
  • Linearization: SGC removes nonlinear transitions between layers while retaining the final softmax, preserving the increased receptive field of a K-layer GCN.Repeated multiplication by S becomes S^K, and layer weights collapse into Θ = Θ(1)Θ(2) . . . Θ(K).
  • Logistic regression: SGC computes fixed smoothed features ¯X = S^KX and feeds them into a linear logistic regression classifier.Because smoothing is parameter-free, training reduces to logistic regression on preprocessed features.

3. Spectral Analysis

SGC corresponds to a fixed spectral filter, and adding self-loops shrinks the normalized Laplacian spectrum. On this scaled spectrum, repeated propagation acts as a low-pass filter that produces smooth graph features.

  • Fixed spectral filter: SGC corresponds to a fixed filter on the graph spectral domain.Graph Fourier analysis defines filters through the eigendecomposition of the graph Laplacian.
  • Fixed spectral filter: First-order propagation produces spectral coefficients ˆg(λi) = (2 − λi)^K from the normalized Laplacian eigenvalues.The propagation matrix is S1-order = I + D−1/2AD−1/2 = 2I − ∆sym.
  • Spectrum shrinking: Adding self-loops replaces the propagation matrix with the augmented normalized adjacency matrix ˜Sadj = ˜D−1/2 ˜A ˜D−1/2, where ˜A = A + I and ˜D = D + I.The corresponding spectral filters are ˆg(˜λi) = (1 − ˜λi)^K.
  • Spectrum shrinking: Theorem 1 shows that adding self-loops γ > 0 makes the largest eigenvalue of the normalized graph Laplacian smaller.The theorem compares the smallest and largest eigenvalues before and after augmentation.
  • Low-pass filtering: On Cora, self-loops shrink the largest eigenvalue from 2 to approximately 1.5, eliminating negative coefficients and enabling K > 1 propagation to act as a low-pass filter.Without self-loops, odd powers yield negative coefficients at frequencies λi > 1.

4. Related Works

Prior work developed graph convolutions from spectral formulations toward simpler first-order propagation, while other studies established the effectiveness of linear models and propagation-based methods. Attention-based graph models achieve strong results but add computational and memory overhead.

  • Spectral Graph Convolutions: Spectral graph convolutions progressed from Laplacian-based formulations to Chebyshev-polynomial filters and then first-order GCN propagation.Bruna et al. introduced spectral graph convolutions; ChebyNets removed costly Laplacian eigendecomposition, and GCNs simplified the filters using a redefined propagation matrix S.
  • Linear Graph Models: Linear or propagation-based models can perform effectively on node and graph classification tasks.Prior work reported competitive linear GCNs, degree-statistics baselines, self-training with linear feature/label propagation, and generalized label propagation with spectral analysis.
  • Graph Attention: Graph attentional models learn feature-dependent edge weights and achieve state-of-the-art results on several graph learning tasks.Their attention mechanisms usually impose significant computation and memory overhead.
  • Graph Methodologies: Graph methodologies can be broadly categorized into graph embedding and graph Laplacian regularization approaches.Embedding methods represent nodes as high-dimensional feature vectors; DeepWalk and Deep Graph Infomax use unsupervised strategies to learn graph embeddings.

5. Experiments and Discussion

Experiments across citation and social networks show that SGC remains competitive with graph-network baselines while substantially improving training efficiency. Across five downstream applications, SGC matches or improves competing methods, with reported speed, runtime, and parameter reductions.

  • Performance: SGC matches GCN and state-of-the-art graph networks on citation networks, outperforming GCN by about 1% on Citeseer.The authors attribute the Citeseer improvement to fewer parameters and less overfitting.
  • Performance: On Reddit, both randomly initialized and trained DGI encoders underperform SGC, suggesting DGI’s extra weights and nonlinearities may be unnecessary or detrimental.The passage reports that randomly initialized DGI nearly matches a trained encoder, while both underperform SGC.
  • Efficiency: SGC trains up to two orders of magnitude faster than fast sampling-based methods with little or no performance drop.Its fixed filter and precomputed SKX reduce memory usage, while sparse-dense multiplication enables efficient computation.
  • Downstream applications: On five text-classification benchmarks, SGC with K = 2 rivals a 2-layer GCN while being up to 83.6× faster.The graph combines documents and words, using PMI word-word edges and normalized TF-IDF word-document edges.
  • Downstream applications: SGC outperforms GCNs with highway connections on three geolocation datasets while saving 30+ hours on TWITTER-WORLD.The reported datasets are GEOTEXT, TWITTER-US, and TWITTER-WORLD.
  • Downstream applications: Replacing GCN with SGC sets a new state-of-the-art on TACRED, improves zero-shot image classification while reducing parameters by 55%, and achieves 71.0% and 76.2% on NCI1 and COLLAB.The relation-extraction model is C-SGC; the graph-classification scores are reported for the NCI1 and COLLAB datasets.

6. Conclusion

The conclusion presents SGC as a simple, efficient, and interpretable graph model whose performance rivals or surpasses GCNs and state-of-the-art graph neural networks. It explains SGC as a low-pass-type filter and attributes GCN expressiveness primarily to repeated graph propagation rather than nonlinear feature extraction.

  • Conclusion: SGC combines graph-based preprocessing with standard multi-class logistic regression while achieving performance that rivals or surpasses GCNs and state-of-the-art graph neural networks across graph-learning tasks.The conclusion characterizes the algorithm as almost trivial.
  • Conclusion: SGC acts as a low-pass-type spectral filter that captures low-frequency signals by smoothing features across a graph.The analysis also explains the empirical boost from the renormalization trick and connects spectral-domain shrinking to this filter.
  • Conclusion: SGC suggests that GCN expressive power primarily comes from repeated graph propagation, which SGC preserves, rather than nonlinear feature extraction, which it removes.This conclusion follows from SGC’s strong performance despite omitting nonlinear feature extraction.
  • Conclusion: The authors argue that SGC is beneficial as a first model, a simple baseline, and a starting point for developing more complex graph-learning models.They emphasize these roles especially for node classification tasks.

(Supplementary Material) · A. The spectrum of ˜∆sym

This supplementary section establishes core spectral properties of the augmented normalized Laplacian ˜∆sym, including symmetry, positive semidefiniteness, and a zero eigenvalue. It also develops eigenvalue relationships used to analyze the operator’s spectrum.

  • A. The spectrum of ˜∆sym: ˜∆sym is a symmetric positive semidefinite matrix.The section states this as Lemma 1 for the augmented normalized Laplacian.
  • A. The spectrum of ˜∆sym: Both ∆sym and ˜∆sym have 0 as an eigenvalue.This is stated directly in Lemma 2.
  • A. The spectrum of ˜∆sym: The all-ones vector v is an eigenvector of the unaugmented Laplacian ∆ with eigenvalue 0.The proof uses ∆v = (D−A)v = 0.
  • A. The spectrum of ˜∆sym: For the augmented operator, v1 = ˜D^1/2v is an eigenvector of ˜∆sym associated with eigenvalue 0.The proof derives ˜∆symv1 = 0 and identifies this as the smallest eigenvalue using non-negativity.
  • A. The spectrum of ˜∆sym: The normalized adjacency matrix D^-1/2AD^-1/2 has largest eigenvalue βn = 1.This follows because 0 is an eigenvalue of ∆sym and D^-1/2AD^-1/2 = I − ∆sym.
  • A. The spectrum of ˜∆sym: The section uses a Rayleigh quotient to derive a lower bound for the smallest eigenvalue α1 of ˜D^-1/2A˜D^-1/2.The construction chooses ∥x∥ = 1 and y = D^1/2˜D^-1/2x, with a bound involving γ and the maximum degree.
  • A. The spectrum of ˜∆sym: The augmented normalized Laplacian is expressed as ˜∆sym = I − γ˜D^-1 − ˜D^-1/2A˜D^-1/2 for the subsequent theorem proof.The theorem proof invokes the spectral results from Lemma 3.

B. Experiment Details

The experiments specify task-specific SGC replacements, feature-processing choices, optimization settings, and hardware configurations. Training-time comparisons use averaged results from Citation Networks and Reddit, with FastGCN evaluated under a shorter early-stopping window.

  • Node Classification: For node classification on Reddit, SGC requires features normalized to zero mean and univariate.This normalization is identified as crucial for the Reddit experiment.
  • Training Time Benchmarking: Training-time benchmarking compares graph neural networks on Citation Networks and Reddit using data reported in Tables 8 and 9.Table 8 reports training time in seconds averaged over 10 runs; Table 9 reports training time in seconds on Reddit.
  • Training Time Benchmarking: FastGCN’s reported CPU training times are difficult to compare numerically across reports, and a 10-epoch early-stopping window reduced its training time.The setup follows Chen et al. (2018), while the authors observed improved FastGCN performance with the smaller early-stopping window.
  • Text Classification: For text classification, SGC normalizes propagated features between 0 and 1, trains with L-BFGS for 3 steps, and tunes weight decay for 60 iterations.TextGCN cannot use this feature normalization because its propagation cannot be precomputed.
  • Task-Specific Experimental Settings: The task-specific setups use K = 3 SGC for user geolocation, K = 2 SGC without intermediate dropout for relation extraction, and K = 6 SGC after a six-layer MLP for zero-shot image classification.User geolocation retains two linear transformations; relation extraction keeps other hyperparameters unchanged; image classification uses learning rate 0.001, weight decay 0.0005, and dropout rate 0.5.

C. Additional Experiments

Additional experiments examine SGC under random training splits, alternative propagation matrices, and reduced training-set sizes. They find that self-loops improve the domain for fixed filters and that SGC remains comparable to GCN, outperforming it with very few training samples.

  • Random Splits for Citation Networks: The study conducts 10 additional experiments using random training splits while keeping the validation and test sets unchanged.These experiments address instability in the relatively small citation networks.
  • Propagation choice: An ablation study evaluates SGC with different choices of propagation matrix.Validation accuracy is compared across propagation matrices.
  • Propagation choice: For non-augmented propagation matrices, negative coefficients distort the signal and reduce accuracy, whereas adding self-loops creates a better domain for fixed filters.The non-augmented matrices have largest eigenvalues of approximately 2; varying K does not degrade augmented propagation matrices.
  • Training dataset size: SGC performs similarly to GCN as the training dataset shrinks and outperforms GCN when fewer than 5 training samples are available.Validation accuracy is averaged over 10 random training splits with equal numbers of training examples per class.
Loading 1902.07153v2…