SGC: Simple Graph Convolution
Published:
The GCN Formula Revisited
A GCN with \(K\) layers applies:
with \(H^{(0)} = X\) and \(\sigma\) the ReLU.
Each layer does three things: (1) aggregate from neighbours, \(\hat{A} H^{(l)}\); (2) apply a linear transformation \(W^{(l)}\); (3) apply the nonlinearity \(\sigma\).
The nonlinearity couples the graph propagation and the linear transformation — you cannot commute them past each other, so nothing can be pre-computed.
The SGC Simplification
SGC (Simple Graph Convolution) makes two changes:
- Remove all intermediate nonlinearities
- Collapse all weight matrices into one
Once the ReLUs are gone, the layers become \(\hat{A}(\hat{A}(\hat{A}XW^{(0)})W^{(1)})W^{(2)}\cdots\), and since \(\hat{A}\) commutes with the right-multiplications, this is \(\hat{A}^K X (W^{(0)}W^{(1)}\cdots W^{(K-1)})\). The product of weight matrices is itself just some matrix \(W\):
The entire model is now:
- Pre-compute \(\hat{A}^K X\) (\(K\) steps of feature propagation — a fixed, parameter-free linear operation)
- Apply a single linear classifier \(W\) to the smoothed features
- Softmax for probabilities
Concrete example showing the collapse. For a 3-layer GCN with weight matrices \(W^{(0)}, W^{(1)}, W^{(2)}\) and ReLU activations:
GCN (3 layers):
H¹ = ReLU( Â · X · W⁰ ) ← cannot pre-compute (W⁰ is inside ReLU)
H² = ReLU( Â · H¹ · W¹ ) ← depends on H¹
H³ = ReLU( Â · H² · W² ) ← depends on H²
SGC (K=3): remove all intermediate nonlinearities, collapse all W:
X̃ = ³ · X ← pre-compute ONCE (no parameters!)
Ŷ = softmax( X̃ · W ) ← single linear layer trained on cached X̃
Pre-computation: \(K\) sparse products \(\hat{A}\cdot(\text{dense } N\times d)\), i.e. \(O(K\lvert E\rvert d)\), run once before training. Per-epoch cost afterwards: \(O(N d C)\) for \(C\) classes — logistic-regression speed.
Pre-Computation: The Key Efficiency Gain
Because \(\hat{A}^K X\) involves no learned parameters, it can be computed once before training and cached. Training then reduces to logistic regression on the pre-computed features.
Computational cost comparison (training, \(N\) nodes, \(K=2\)):
| Model | Forward pass cost |
|---|---|
| GCN (2 layers) | \(O(\lvert E\rvert d_1 + N d_1 d_2)\) per epoch |
| SGC (\(K=2\)) | \(O(K\lvert E\rvert d)\) once, then \(O(N d C)\) per epoch |
The speed-up comes from removing the graph from the training loop entirely: after pre-computation, no epoch ever touches an edge. The size of the gain depends on the graph, the feature dimension and the hidden width, so it is best measured on your own data rather than quoted as a single number — but on the standard citation benchmarks the reported gap is large, spanning roughly one to two orders of magnitude in training time.
Theoretical Interpretation
\(\hat{A}^K X\) is a \(K\)-step smoothing of node features. The operator \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) is not itself a random-walk matrix, but it is similar to one: \(\hat{A} = \tilde{D}^{1/2}\left(\tilde{D}^{-1}\tilde{A}\right)\tilde{D}^{-1/2}\), so it has the same eigenvalues as the lazy random walk on the self-looped graph, and \(K\) applications behave like \(K\) steps of that walk in a degree-reweighted coordinate system. After \(K\) steps each node’s feature is a weighted average over its \(K\)-hop neighbourhood.
Spectrally, writing \(\hat{A} = I - \tilde{L}_{\mathrm{sym}}\) with \(\tilde{L}_{\mathrm{sym}}\) the normalised Laplacian of the self-looped graph, SGC applies the fixed filter \(h(\tilde\lambda) = (1-\tilde\lambda)^K\) to every frequency. This is the crux of what SGC keeps and what it throws away.
What SGC does not lose. The receptive field: \(\hat{A}^K X\) still reaches every node within \(K\) hops. And in the linear regime it loses nothing at all relative to a linear GCN — the collapse above is an identity, not an approximation, so any linear multi-layer GCN has an exactly equivalent SGC.
What SGC does lose. Three things:
- Feature-dependent, nonlinear interactions between propagation steps. A ReLU GCN can gate what gets propagated; SGC cannot. Whatever a deep MLP-per-layer could express beyond one linear map is gone.
- Filter shape. \((1-\tilde\lambda)^K\) is a fixed low-pass response with no free parameters. ChebNet can learn band-pass or high-pass filters; SGC cannot represent any of them at any \(K\).
- Adaptivity of depth. \(K\) is a hyperparameter chosen before training, not something the model can trade off internally.
SGC then applies a linear classifier on the smoothed representation — analogous to a linear classifier on bag-of-words features, where the “bag” is the \(K\)-hop neighbourhood.
When Nonlinearities Do Matter
SGC’s simplification works on homophilic graphs (Cora, CiteSeer, Pubmed). On these, \(K\)-step averaging makes same-class nodes progressively more similar — which is exactly what a linear classifier needs.
SGC is expected to do relatively worse than GCN when:
- The graph is heterophilic: the class signal lives at high graph frequency, and a purely low-pass filter attenuates precisely the component that carries it
- The task is structural: the pattern is in local topology rather than smooth features
- Propagation is deep: with no nonlinearity to counteract it, \((1-\tilde\lambda)^K \to 0\) for every \(\tilde\lambda > 0\), so large \(K\) drives all embeddings toward the same degree-weighted mean — over-smoothing arrives quickly
SGC as Logistic Regression
After pre-computing \(\tilde{X} = \hat{A}^K X\), the SGC model is:
This is exactly multinomial logistic regression on pre-computed graph-smoothed features. The model has no architecture hyperparameters beyond \(K\). There is no depth, no hidden layers, no dropout decisions. The objective is convex in \(W\), so training has a single global optimum.
This makes SGC a sharp ablation baseline: if SGC matches your GNN on your data, the extra complexity is not buying you anything there.
SGC Variants and Successors
- SIGN (2020): use several powers of \(\hat{A}\) simultaneously — concatenate \([X, \hat{A}X, \hat{A}^2X, \dots]\) — then apply an MLP. More expressive than SGC while keeping the propagation pre-computable, and it is no longer restricted to a single fixed low-pass response.
- APPNP: separates propagation from transformation using personalised PageRank, which keeps a non-zero response at every frequency.
- GAMLP: large-scale variant that learns how to combine multiple propagated feature sets.
Summary
| Property | GCN | SGC |
|---|---|---|
| Per-layer nonlinearity | Yes (ReLU) | No |
| Weight matrices | \(K\) separate \(W^{(l)}\) | Single \(W\) |
| Spectral filter | One fixed low-pass step per layer, with nonlinearity between | Fixed \((1-\tilde\lambda)^K\), no free shape |
| Propagation pre-computable | No | Yes |
| Training cost | High (full forward pass each epoch) | Low (convex logistic regression) |
| Accuracy (homophilic citation graphs) | Comparable | Comparable |
| Accuracy (heterophilic) | Weak | Weak, for the same low-pass reason |
SGC reveals that on homophilic benchmarks, graph neural networks are largely doing one thing: low-pass filtering features over the graph and then classifying. That the sophistication of multi-layer nonlinear GNNs can sometimes be dropped without loss says something real about those benchmarks — and it is also a warning about how much a benchmark result can tell you about an architecture.
References
- Wu, F., Zhang, T., de Souza Jr., A. H., Fifty, C., Yu, T., & Weinberger, K. Q. (2019). Simplifying Graph Convolutional Networks. ICML 2019.
- Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017.