Graph Convolutional Network (GCN)

GCN (Kipf & Welling, ICLR 2017) updates every node as H′ = σ(D̃^−½(A+I)D̃^−½HW): a degree-normalised average over itself and its neighbours; two layers with 16 hidden units reach 81.5% on Cora from 140 labels.

8 min read773 wordscore0 viewsupdated 2026-10-21

Definition

Graph Convolutional Network (GCN) is a neural network layer for graphs in which every node's new feature vector is a degree-normalised sum of its own and its neighbours' vectors, followed by a shared linear map and a nonlinearity. Kipf and Welling introduced it in "Semi-Supervised Classification with Graph Convolutional Networks" (ICLR 2017) and derived it as a first-order approximation of spectral graph convolutions.

The task in the paper is semi-supervised Node classification: one graph, features for every node, labels for a few. On Cora, 140 of 2,708 papers are labelled and the model must label the rest. The input is an adjacency matrix AA (N×NN\times N) and a feature matrix XX (N×FN\times F); the output is a class distribution per node.

A CNN filter needs a fixed grid and a fixed neighbour order. Graph nodes have no order and a variable number of neighbours, so the layer must be permutation equivariant: relabelling the nodes must relabel the output in the same way. Earlier methods either regularised a classifier with a graph-Laplacian smoothness term (label propagation, manifold regularisation) or learned node embeddings from random walks (DeepWalk, Planetoid). Spectral CNNs (Bruna et al., 2014) filtered in the Laplacian's eigenbasis, which costs an O(N3)O(N^3) eigendecomposition. ChebNet (Defferrard, Bresson and Vandergheynst, 2016) replaced the eigenbasis by Chebyshev polynomials of the Laplacian, giving KK-hop filters with no eigendecomposition.

The layer

H(l+1)=σ ⁣(D~−1/2A~ D~−1/2H(l)W(l)),A~=A+IN,D~ii=∑jA~ijH^{(l+1)}=\sigma\!\left(\tilde D^{-1/2}\tilde A\,\tilde D^{-1/2}H^{(l)}W^{(l)}\right),\qquad \tilde A=A+I_N,\quad \tilde D_{ii}=\textstyle\sum_j\tilde A_{ij}
H(l)H^{(l)}
node features at layer ll, N×FlN\times F_l; H(0)=XH^{(0)}=X
A~\tilde A
adjacency with self-loops, so a node keeps its own features
D~\tilde D
diagonal degree matrix of A~\tilde A (degree + 1)
W(l)W^{(l)}
Fl×Fl+1F_l\times F_{l+1} weights shared by all nodes
σ\sigma
ReLU between layers, softmax over classes at the output

Per node this is hi′=σ(∑j∈N(i)∪{i}1d~id~j hjW)h_i'=\sigma\big(\sum_{j\in\mathcal N(i)\cup\{i\}}\frac{1}{\sqrt{\tilde d_i\tilde d_j}}\,h_jW\big). Each edge's weight shrinks when either endpoint has many neighbours, so a hub neither dominates its neighbours nor gets an exploding sum. One layer mixes 1-hop neighbourhoods; LL layers give each node a receptive field of LL hops.

one layer: H′ = σ(D̃^−½ à D̃^−½ H W), à = A + I1/√8 = 0.3541/√12 = 0.2891/√16 = 0.25self 1/4 = 0.251d̃=42d̃=23d̃=34d̃=45d̃=22 hops awayh′₁ = σ( [0.25 h₁ + 0.354 h₂ + 0.289 h₃ + 0.25 h₄] W )edge weight 1/√(d̃ᵢd̃ⱼ), d̃ includes the self-loopnode 5 reaches node 1 only in layer 2two-layer GCN on Cora (N 2708, F 1433, C 7)X 2708 × 1433bag-of-words node features X W⁽⁰⁾ W⁽⁰⁾: 1433 × 16ReLU, dropout 0.5 → H 2708 × 16 H W⁽¹⁾ W⁽¹⁾: 16 × 7row-wise softmaxZ 2708 × 7class probabilities per nodecross-entropy on 140 labelled nodes20 per class; all 2708 nodes propagate = D̃^−½ à D̃^−½ is computed once and stays sparse;a layer costs O(|E| · F · C) for F inputs and C outputs
fig.Left: one GCN layer on a 5-node graph. Node 1 (self-loop degree 4) sums itself (1/4) and neighbours 2, 3, 4 with weights 1/√(d̃ᵢd̃ⱼ) = 0.354, 0.289, 0.25, then applies W and σ. Node 5 is two hops away and reaches node 1 only through the second layer. Right: the two-layer model on Cora, with shapes 2708 × 1433 → 2708 × 16 → 2708 × 7 and a loss on the 140 labelled nodes only.

Where the formula comes from

A spectral filter on a graph signal xx is gθ⋆x=Ugθ(Λ)U⊤xg_\theta\star x=Ug_\theta(\Lambda)U^\top x, where L=I−D−1/2AD−1/2=UΛU⊤L=I-D^{-1/2}AD^{-1/2}=U\Lambda U^\top. ChebNet approximates gθg_\theta with a degree-KK polynomial. Kipf and Welling take K=1K=1, assume λmax⁡≈2\lambda_{\max}\approx2 and tie the two coefficients (θ=θ0=−θ1\theta=\theta_0=-\theta_1):

gθ⋆x≈θ(IN+D−1/2AD−1/2)x    →renormalise    θ D~−1/2A~ D~−1/2xg_\theta\star x\approx\theta\left(I_N+D^{-1/2}AD^{-1/2}\right)x\;\;\xrightarrow{\text{renormalise}}\;\;\theta\,\tilde D^{-1/2}\tilde A\,\tilde D^{-1/2}x
IN+D−1/2AD−1/2I_N+D^{-1/2}AD^{-1/2}
eigenvalues in [0,2][0,2]; repeated application can blow up or vanish
D~−1/2A~D~−1/2\tilde D^{-1/2}\tilde A\tilde D^{-1/2}
the renormalisation trick: eigenvalues in (−1,1](-1,1], so stacking layers is stable

On the 5-node graph above, I+D−1/2AD−1/2I+D^{-1/2}AD^{-1/2} has eigenvalues 0.232, 0.333, 1, 1.434, 20.232,\,0.333,\,1,\,1.434,\,2; the renormalised A^\hat A has −0.183, −0.097, 0.430, 0.683, 1-0.183,\,-0.097,\,0.430,\,0.683,\,1. The paper's model is two such layers:

Z=softmax⁡ ⁣(A^ ReLU⁡(A^XW(0)) W(1)),L=−∑l∈YL∑f=1CYlfln⁡ZlfZ=\operatorname{softmax}\!\left(\hat A\,\operatorname{ReLU}(\hat A XW^{(0)})\,W^{(1)}\right),\qquad \mathcal L=-\sum_{l\in\mathcal Y_L}\sum_{f=1}^{C}Y_{lf}\ln Z_{lf}
A^\hat A
D~−1/2A~D~−1/2\tilde D^{-1/2}\tilde A\tilde D^{-1/2}, precomputed once as a sparse matrix
YL\mathcal Y_L
indices of the labelled nodes; unlabelled nodes still pass messages

Training is full-batch: every epoch multiplies the whole sparse A^\hat A, at a cost of O(∣E∣ F C)O(|E|\,F\,C) per layer. The gradient from the 140 labelled nodes flows through A^\hat A into the features of their 2-hop neighbourhoods. That is how unlabelled nodes shape the classifier.

DatasetNodesEdgesFeaturesClassesLabel rateGCNPlanetoid
Cora2,7085,4291,43370.05281.575.7
Citeseer3,3274,7323,70360.03670.364.7
Pubmed19,71744,33850030.00379.077.2
Citation benchmarks in the paper (Planetoid splits: 20 labels per class, 500 validation and 1,000 test nodes). Test accuracy in %.

Training setup (citation datasets)

Model
2 layers, 16 hidden units, ReLU, softmax output
Regularisation
Dropout 0.5; L2 weight decay 5 × 10⁻⁴ on the first layer
Optimiser
Adam, learning rate 0.01, up to 200 epochs, early stopping on validation loss with a window of 10 epochs; Glorot initialisation
Depth
an appendix experiment varied 1–10 layers; 2–3 layers were best, and deeper models trained poorly without residual connections

Propagation, denoising and over-smoothing

Strip out WW and σ\sigma and a KK-layer GCN is A^KX\hat A^KX, a low-pass filter on the graph. Simplifying Graph Convolution (SGC; Wu et al., 2019) trains just a logistic regression on A^KX\hat A^KX and comes close to GCN on the citation sets. Each step averages over neighbours, which removes noise when neighbours share the label (homophily). Li, Han and Wu (2018) showed the layer is a form of Laplacian smoothing. On a connected graph, A^K\hat A^K converges to uu⊤u u^\top with ui∝d~iu_i\propto\sqrt{\tilde d_i}, so every row loses all information except its degree. This is over-smoothing.

H(K) = Â^K X, Â = D̃^−½ Ã D̃^−½, K = 2class 0 (20 nodes)class 1 (20 nodes)153 edges, 18 cross-class (rose) · fill = sign of h₁ · ringed = labellednode features (h₁, h₂), rescaled ×1/0.67h₁00.5108162432accuracy (34 unlabelled) and separation / max vs Kpropagation steps Kat K = 2accuracy97.1%separation4.28max ‖h‖0.75separation = class-meangap / within-class RMS
operator
fig.Two communities of 20 nodes with noisy 2-D features (class means ±0.6, noise σ = 1), propagated K times by Â, then classified by nearest centroid from 3 labelled nodes per class. Defaults (p_out = 0.06: 153 edges, 18 cross-class): K = 0 gives 70.6% (24/34) and separation 0.82; K = 2 gives 97.1% and 4.28. Accuracy is 100% for K = 3–11 and separation peaks at 7.92 (K = 7); at K = 32 it falls to 41.2% with separation 0.18. Raise p_out to 0.15 (44 cross edges) and the collapse starts by K ≈ 8. Switch to raw Ã: max ‖h‖ grows to 1.24 × 10⁷ by K = 8.

The speed of collapse is set by the second-largest eigenvalue of A^\hat A, here 0.8360.836 at the defaults. The class signal decays like 0.836K0.836^K, so it lasts about ten steps and is gone by thirty. With pout=0p_\text{out}=0 only one bridge joins the communities, the second eigenvalue is close to 1, and the separation still stands at 18.2 after 32 steps.

Worked example: one propagation step

On the 5-node graph of the diagram (edges 1–2, 1–3, 1–4, 3–4, 4–5), give each node a scalar feature x=(2,0,1,−1,3)x=(2,0,1,-1,3) and compute A^x\hat Ax (that is, W=1W=1, no σ\sigma):

NodeÑ(i) incl. selfd̃ᵢWeights(Âx)ᵢ
11, 2, 3, 440.25, 0.354, 0.289, 0.250.5 + 0 + 0.289 − 0.25 = 0.539
22, 120.5, 0.3540 + 0.707 = 0.707
33, 1, 430.333, 0.289, 0.2890.333 + 0.577 − 0.289 = 0.622
44, 1, 3, 540.25, 0.25, 0.289, 0.354−0.25 + 0.5 + 0.289 + 1.061 = 1.599
55, 420.5, 0.3541.5 − 0.354 = 1.146
Self-loop degrees d̃ = degree + 1; weights 1/√(d̃ᵢd̃ⱼ), self term first

After one step node 1 has not seen node 5's value. After two steps (A^2)15=0.088(\hat A^2)_{15}=0.088, so node 5 contributes 0.088⋅3=0.2650.088\cdot3=0.265 to node 1's new value of 0.964.

python
1import numpy as np
2
3def gcn_norm(edges, n):
4 """Â = D̃^-1/2 (A + I) D̃^-1/2 for an undirected edge list."""
5 A = np.eye(n)
6 for i, j in edges:
7 A[i, j] = A[j, i] = 1.0
8 d = A.sum(1)
9 return A / np.sqrt(np.outer(d, d))
10
11def gcn_forward(A_hat, X, W0, W1):
12 H = np.maximum(A_hat @ X @ W0, 0) # layer 1 + ReLU
13 Z = A_hat @ H @ W1 # layer 2 logits
14 Z = np.exp(Z - Z.max(1, keepdims=True))
15 return Z / Z.sum(1, keepdims=True) # row-wise softmax
16
17edges = [(0, 1), (0, 2), (0, 3), (2, 3), (3, 4)] # the 5-node example, 0-indexed
18A_hat = gcn_norm(edges, 5)
19x = np.array([2.0, 0.0, 1.0, -1.0, 3.0])
20print(np.round(A_hat @ x, 3)) # [0.539 0.707 0.622 1.599 1.146]
21
22rng = np.random.default_rng(0)
23X = rng.normal(size=(5, 8)) # 8 input features
24W0 = rng.normal(size=(8, 16)) * np.sqrt(2 / 24) # Glorot scale, 16 hidden units
25W1 = rng.normal(size=(16, 3)) * np.sqrt(2 / 19) # 3 classes
26print(gcn_forward(A_hat, X, W0, W1).shape) # (5, 3)
 and a two-layer GCN forward pass in numpy (runs as is); torch_geometric.nn.GCNConv applies the same normalisation, with self-loops added by default

Use when

  • +One sparse matrix product per layer: linear in the number of edges.
  • +Few parameters (W is F × F′, shared by all nodes); strong with very few labels.
  • +Weights do not depend on N, so a trained model can be applied to a new graph.

Avoid when

  • −Fixed, structure-only neighbour weights: no way to down-weight an irrelevant neighbour.
  • −Over-smoothing limits useful depth to about 2–3 layers without residual connections.
  • −Sum-like aggregation with degree normalisation is no more expressive than the 1-WL test (see Graph Isomorphism Network (GIN)).

Check yourself

Why does GCN use D̃^−½(A + I)D̃^−½ rather than I + D^−½AD^−½?

Check yourself

A 2-layer GCN is trained on Cora with 140 labelled nodes. Which nodes influence the prediction for a labelled node v?

Remember

  • ✓Layer: H′=σ(D~−1/2(A+I)D~−1/2HW)H'=\sigma(\tilde D^{-1/2}(A+I)\tilde D^{-1/2}HW); edge weight 1/d~id~j1/\sqrt{\tilde d_i\tilde d_j}, weights shared by all nodes.
  • ✓Derived as a first-order Chebyshev (ChebNet) filter with one parameter per feature pair; the renormalisation trick bounds the spectrum by 1.
  • ✓Two layers, 16 hidden units, dropout 0.5: 81.5% Cora, 70.3% Citeseer, 79.0% Pubmed with 20 labels per class.
  • ✓Cost O(|E|·F·C) per layer, full-batch; L layers see L hops.
  • ✓A^K\hat A^K is a low-pass filter: a few steps denoise, many steps over-smooth every node towards d~i\sqrt{\tilde d_i} times a shared vector.
← back to Deep Learning roadmap