GCN: Graph Convolutional Networks

From Spectral Theory to a Practical Layer

As explained in the Graph Laplacian post, spectral graph convolution filters signals using the Laplacian’s eigenvectors. But computing eigenvectors is O(N³) — completely infeasible for large graphs.

Kipf & Welling (2016) made two elegant simplifications:

1. Localise: approximate the spectral filter as a first-order polynomial in the Laplacian \(L\) — only immediate neighbours matter.
2. Normalise: use symmetric normalisation to prevent large-degree nodes from dominating.

The result is a layer that can be computed with simple sparse matrix multiplication.

The GCN Formula

Where:

• \(H^{(l)} \in \mathbb{R}^{N \times F_l}\) — node features at layer \(l\), one row per node; \(H^{(0)} = X\) is the input feature matrix.
• \(A \in \{0,1\}^{N \times N}\) — the plain adjacency matrix of the graph.
• \(\tilde{A} = A + I\) — the adjacency with self-loops added.
• \(\tilde{D}\) — the diagonal degree matrix of \(\tilde{A}\), i.e. \(\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}\).
• \(\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\) — the symmetrically normalised propagation matrix. This is the object the layer actually multiplies by; \(\tilde{A}\) alone is not normalised.
• \(W^{(l)} \in \mathbb{R}^{F_l \times F_{l+1}}\) — the learned weight matrix for layer \(l\).
• \(\sigma\) — an elementwise activation function (ReLU).

Throughout this post \(\tilde{A}\) always means \(A + I\) and \(\hat{A}\) always means the normalised propagation matrix — they are two different matrices.

Breaking It Down Step by Step

Let’s trace what happens for a single node \(v\) with neighbours labelled A, B and C (plain labels — not to be confused with the adjacency matrix \(A\)):

Step 1: Add self-loops. \(\tilde{A} = A + I\) ensures \(v\) attends to itself too, not just its neighbours. Without this, a node’s own features would be excluded from the aggregation.

Step 2: Compute normalisation weights. The weight on the edge \(u \to v\) is

This is the symmetric normalisation. It down-weights edges touching high-degree “hub” nodes (which would otherwise dominate).

Step 3: Aggregate. Row \(v\) of \(\hat{A} H^{(l)}\) is a weighted sum of the features of \(v\) and all its neighbours:

Step 4: Transform. Multiply by \(W^{(l)}\): a linear projection to a new feature space.

Step 5: Activate. Apply ReLU (or another non-linearity).

Concrete Numerical Example: One GCN Layer

Consider a 3-node path graph \(1 - 2 - 3\), with node features \(h_1 = [2,0]\), \(h_2 = [0,4]\), \(h_3 = [1,1]\).

Step 1 — Add self-loops: \(\tilde{A} = A + I\), so every node gains a self-edge. The degrees of \(\tilde{A}\) are \(\tilde{d}_1 = 2\), \(\tilde{d}_2 = 3\), \(\tilde{d}_3 = 2\).

Step 2 — Compute the entries of \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\):

• Edge \((1,2)\): \(1/\sqrt{2 \times 3} \approx 0.408\)
• Edge \((2,3)\): \(1/\sqrt{3 \times 2} \approx 0.408\)
• Self-loop at node 1: \(1/\sqrt{2 \times 2} = 0.5\)
• Self-loop at node 2: \(1/\sqrt{3 \times 3} \approx 0.333\)
• Self-loop at node 3: \(1/\sqrt{2 \times 2} = 0.5\)

Step 3 — Aggregate for node 2 (whose closed neighbourhood is \(\{1, 2, 3\}\)):

Step 4 — Apply the weight matrix \(W\) and a ReLU:

The weight matrix \(W\) is shared across all nodes and learned by backpropagation.

What GCN Is in MPNN Terms

• MSG: send the neighbour’s features scaled by the normalisation weight, \(\operatorname{MSG}(h_v, h_u) = \hat{A}_{vu} h_u\).
• AGGREGATE: a weighted sum over the closed neighbourhood \(\mathcal{N}(v) \cup \{v\}\) — exactly what multiplying by \(\hat{A}\) does.
• UPDATE: apply a single linear layer \(W^{(l)}\) followed by \(\sigma\).

Stacking Layers and the Oversmoothing Problem

With \(k\) GCN layers, each node’s representation captures its \(k\)-hop neighbourhood.

• \(k = 2\): captures 2-hop information (good for most citation/social graph tasks).
• \(k \gg 1\): oversmoothing — repeatedly applying \(\hat{A}\) acts like a random walk that converges towards its stationary distribution, so node representations lose their differences and drift towards a common vector, making nodes indistinguishable.

This is GCN’s main limitation. GAT, GPRGNN, and JK-Nets propose various solutions.