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 () and a feature matrix (); 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 eigendecomposition. ChebNet (Defferrard, Bresson and Vandergheynst, 2016) replaced the eigenbasis by Chebyshev polynomials of the Laplacian, giving -hop filters with no eigendecomposition.
The layer
- node features at layer , ;
- adjacency with self-loops, so a node keeps its own features
- diagonal degree matrix of (degree + 1)
- weights shared by all nodes
- ReLU between layers, softmax over classes at the output
Per node this is . 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; layers give each node a receptive field of hops.
Where the formula comes from
A spectral filter on a graph signal is , where . ChebNet approximates with a degree- polynomial. Kipf and Welling take , assume and tie the two coefficients ():
- eigenvalues in ; repeated application can blow up or vanish
- the renormalisation trick: eigenvalues in , so stacking layers is stable
On the 5-node graph above, has eigenvalues ; the renormalised has . The paper's model is two such layers:
- , precomputed once as a sparse matrix
- indices of the labelled nodes; unlabelled nodes still pass messages
Training is full-batch: every epoch multiplies the whole sparse , at a cost of per layer. The gradient from the 140 labelled nodes flows through into the features of their 2-hop neighbourhoods. That is how unlabelled nodes shape the classifier.
| Dataset | Nodes | Edges | Features | Classes | Label rate | GCN | Planetoid |
|---|---|---|---|---|---|---|---|
| Cora | 2,708 | 5,429 | 1,433 | 7 | 0.052 | 81.5 | 75.7 |
| Citeseer | 3,327 | 4,732 | 3,703 | 6 | 0.036 | 70.3 | 64.7 |
| Pubmed | 19,717 | 44,338 | 500 | 3 | 0.003 | 79.0 | 77.2 |
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 and and a -layer GCN is , a low-pass filter on the graph. Simplifying Graph Convolution (SGC; Wu et al., 2019) trains just a logistic regression on 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, converges to with , so every row loses all information except its degree. This is over-smoothing.
The speed of collapse is set by the second-largest eigenvalue of , here at the defaults. The class signal decays like , so it lasts about ten steps and is gone by thirty. With 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 and compute (that is, , no ):
| Node | Ñ(i) incl. self | d̃ᵢ | Weights | (Âx)ᵢ |
|---|---|---|---|---|
| 1 | 1, 2, 3, 4 | 4 | 0.25, 0.354, 0.289, 0.25 | 0.5 + 0 + 0.289 − 0.25 = 0.539 |
| 2 | 2, 1 | 2 | 0.5, 0.354 | 0 + 0.707 = 0.707 |
| 3 | 3, 1, 4 | 3 | 0.333, 0.289, 0.289 | 0.333 + 0.577 − 0.289 = 0.622 |
| 4 | 4, 1, 3, 5 | 4 | 0.25, 0.25, 0.289, 0.354 | −0.25 + 0.5 + 0.289 + 1.061 = 1.599 |
| 5 | 5, 4 | 2 | 0.5, 0.354 | 1.5 − 0.354 = 1.146 |
After one step node 1 has not seen node 5's value. After two steps , so node 5 contributes to node 1's new value of 0.964.
1import numpy as np23def 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.08 d = A.sum(1)9 return A / np.sqrt(np.outer(d, d))1011def gcn_forward(A_hat, X, W0, W1):12 H = np.maximum(A_hat @ X @ W0, 0) # layer 1 + ReLU13 Z = A_hat @ H @ W1 # layer 2 logits14 Z = np.exp(Z - Z.max(1, keepdims=True))15 return Z / Z.sum(1, keepdims=True) # row-wise softmax1617edges = [(0, 1), (0, 2), (0, 3), (2, 3), (3, 4)] # the 5-node example, 0-indexed18A_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]2122rng = np.random.default_rng(0)23X = rng.normal(size=(5, 8)) # 8 input features24W0 = rng.normal(size=(8, 16)) * np.sqrt(2 / 24) # Glorot scale, 16 hidden units25W1 = rng.normal(size=(16, 3)) * np.sqrt(2 / 19) # 3 classes26print(gcn_forward(A_hat, X, W0, W1).shape) # (5, 3)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: ; edge weight , 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.
- ✓ is a low-pass filter: a few steps denoise, many steps over-smooth every node towards times a shared vector.