# 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.

Source: https://www.mlfoundry.in/learn/graph-convolutional-network-gcn  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: core · 8 min read · updated 2026-10-21

**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 $A$ ($N\times N$) and a feature matrix $X$ ($N\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(N^3)$ eigendecomposition. ChebNet (Defferrard, Bresson and Vandergheynst, 2016) replaced the eigenbasis by Chebyshev polynomials of the Laplacian, giving $K$-hop filters with no eigendecomposition.

## The layer

$$
H^{(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)}$: node features at layer $l$, $N\times F_l$; $H^{(0)}=X$
- $\tilde A$: adjacency with self-loops, so a node keeps its own features
- $\tilde D$: diagonal degree matrix of $\tilde A$ (degree + 1)
- $W^{(l)}$: $F_l\times F_{l+1}$ weights shared by all nodes
- $\sigma$: ReLU between layers, softmax over classes at the output

Per node this is $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; $L$ layers give each node a receptive field of $L$ hops.

> Figure: 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 $x$ is $g_\theta\star x=Ug_\theta(\Lambda)U^\top x$, where $L=I-D^{-1/2}AD^{-1/2}=U\Lambda U^\top$. ChebNet approximates $g_\theta$ with a degree-$K$ polynomial. Kipf and Welling take $K=1$, assume $\lambda_{\max}\approx2$ and tie the two coefficients ($\theta=\theta_0=-\theta_1$):

$$
g_\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
$$

- $I_N+D^{-1/2}AD^{-1/2}$: eigenvalues in $[0,2]$; repeated application can blow up or vanish
- $\tilde D^{-1/2}\tilde A\tilde D^{-1/2}$: the **renormalisation trick**: eigenvalues in $(-1,1]$, so stacking layers is stable

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

$$
Z=\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}
$$

- $\hat A$: $\tilde D^{-1/2}\tilde A\tilde D^{-1/2}$, precomputed once as a sparse matrix
- $\mathcal Y_L$: indices of the labelled nodes; unlabelled nodes still pass messages

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

Citation benchmarks in the paper (Planetoid splits: 20 labels per class, 500 validation and 1,000 test nodes). Test accuracy in %.

| 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 $W$ and $\sigma$ and a $K$-layer GCN is $\hat A^KX$, a low-pass filter on the graph. Simplifying Graph Convolution (SGC; Wu et al., 2019) trains just a logistic regression on $\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, $\hat A^K$ converges to $u u^\top$ with $u_i\propto\sqrt{\tilde d_i}$, so every row loses all information except its degree. This is **over-smoothing**.

> Figure: 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 $\hat A$, here $0.836$ at the defaults. The class signal decays like $0.836^K$, so it lasts about ten steps and is gone by thirty. With $p_\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)$ and compute $\hat Ax$ (that is, $W=1$, no $\sigma$):

Self-loop degrees d̃ = degree + 1; weights 1/√(d̃ᵢd̃ⱼ), self term first

| 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 $(\hat A^2)_{15}=0.088$, so node 5 contributes $0.088\cdot3=0.265$ to node 1's new value of 0.964.

```python
import numpy as np

def gcn_norm(edges, n):
    """Â = D̃^-1/2 (A + I) D̃^-1/2 for an undirected edge list."""
    A = np.eye(n)
    for i, j in edges:
        A[i, j] = A[j, i] = 1.0
    d = A.sum(1)
    return A / np.sqrt(np.outer(d, d))

def gcn_forward(A_hat, X, W0, W1):
    H = np.maximum(A_hat @ X @ W0, 0)              # layer 1 + ReLU
    Z = A_hat @ H @ W1                             # layer 2 logits
    Z = np.exp(Z - Z.max(1, keepdims=True))
    return Z / Z.sum(1, keepdims=True)             # row-wise softmax

edges = [(0, 1), (0, 2), (0, 3), (2, 3), (3, 4)]   # the 5-node example, 0-indexed
A_hat = gcn_norm(edges, 5)
x = np.array([2.0, 0.0, 1.0, -1.0, 3.0])
print(np.round(A_hat @ x, 3))                      # [0.539 0.707 0.622 1.599 1.146]

rng = np.random.default_rng(0)
X = rng.normal(size=(5, 8))                        # 8 input features
W0 = rng.normal(size=(8, 16)) * np.sqrt(2 / 24)    # Glorot scale, 16 hidden units
W1 = rng.normal(size=(16, 3)) * np.sqrt(2 / 19)    # 3 classes
print(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

> **GCN assumes homophily:** The layer averages neighbours with fixed positive weights. On heterophilous graphs, where linked nodes tend to differ (e.g. some web-page and actor networks), that averaging blurs exactly the signal you need, and an MLP that ignores the edges can beat GCN. Learned neighbour weights (**Graph Attention Network (GAT)**) or keeping the self-feature separate from the neighbour sum (as in **GraphSAGE**) help.

> **Scaling past full batch:** The paper's model holds $\hat A$, $X$ and every hidden layer in memory and takes one gradient step per epoch. That fits Pubmed easily but not graphs with hundreds of millions of edges. Neighbour sampling (**GraphSAGE**), subgraph batching (Cluster-GCN) and precomputing $\hat A^KX$ (SGC) are the usual fixes.

**Strengths**

- 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.

**Limitations**

- 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)**).

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

- A. It is cheaper to compute
- B. The first-order operator has eigenvalues in [0, 2], so stacking layers can explode or vanish; the renormalised one has eigenvalues in (−1, 1]
- C. Without it the layer is not permutation equivariant
- D. It removes the need for self-loops

**Answer:** B. The first-order operator has eigenvalues in [0, 2], so stacking layers can explode or vanish; the renormalised one has eigenvalues in (−1, 1] — Both are sparse and both are permutation equivariant. The renormalisation trick folds the identity into the adjacency before normalising, which bounds the spectrum by 1. Repeated products then stay bounded. On the 5-node example the largest eigenvalue drops from 2 to 1.

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

- A. Only v
- B. v and its direct neighbours
- C. Every node within 2 hops of v
- D. All 2,708 nodes equally

**Answer:** C. Every node within 2 hops of v — Each layer mixes 1-hop neighbourhoods, so $Z=\hat A\,\sigma(\hat AXW^{(0)})W^{(1)}$ depends on $(\hat A^2)_{vj}$, which is non-zero exactly for nodes within 2 hops.

**Key points**

- Layer: $H'=\sigma(\tilde D^{-1/2}(A+I)\tilde D^{-1/2}HW)$; edge weight $1/\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.
- $\hat A^K$ is a low-pass filter: a few steps denoise, many steps over-smooth every node towards $\sqrt{\tilde d_i}$ times a shared vector.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
