Semi-Supervised Classification with Graph Convolutional Networks

Images have a regular grid; text has a linear sequence. Standard convolutions exploit that regularity: slide a fixed-size filter across a grid or sequence. But a social network, a molecule, or a citation graph has no fixed grid — each node may have 1 neighbor or 1,000, and there is no natural left-to-right order.

Before GCN, two families of approaches existed:

• Feature engineering + classifier. Hand-design graph statistics (degree, centrality, PageRank), ignore the raw node features, and feed them to an SVM. This throws away the rich information sitting on each node.

• Spectral methods. Decompose the graph Laplacian to define a Fourier transform on the graph, then convolve in the frequency domain. Mathematically elegant, but eigendecomposition costs $O(n^3)$ and the filters are graph-specific — train on one graph, and the learned filters cannot transfer to another.

Kipf and Welling asked: can we take the insight from spectral theory — that convolution on a graph is multiplication in the eigenspace of the Laplacian — but simplify it until we get a spatial rule that scales?

The journey from full spectral convolution to GCN's propagation rule has three steps. Each step trades mathematical generality for computational speed, until we arrive at a rule so simple it can be written in one line of code.

Step 1 — Spectral convolution on graphs. Given a graph with $N$ nodes and adjacency matrix $A$, define the normalized graph Laplacian $L = I_N - D^{-1/2}AD^{-1/2}$ where $D$ is the degree matrix. Its eigendecomposition $L = U\Lambda U^T$ defines a Fourier basis on the graph. A spectral filter $g_\theta$ convolves a signal $x$ by multiplying in the frequency domain: $g_\theta \star x = U \, g_\theta(\Lambda) \, U^T x$. This is exact but costs $O(N^2)$ per multiplication and requires computing all eigenvectors.

Step 2 — Chebyshev approximation. Defferrard et al. (ChebNet) approximated $g_\theta(\Lambda)$ with a $K$th-order Chebyshev polynomial, making the filter $K$-hop localized and reducing cost to $O(K \cdot |\mathcal{E}|)$ — linear in edges. But $K$ is a hyperparameter and the polynomial coefficients must be learned.

Step 3 — First-order + renormalization (GCN). Kipf and Welling set $K{=}1$, producing a filter that looks at each node and its immediate neighbors only. They then apply a renormalization trick: add self-loops ($\tilde{A} = A + I_N$) and symmetrically normalize ($\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$). The result is a single, clean propagation rule per layer.

For semi-supervised node classification, Kipf and Welling stack exactly two GCN layers. The first layer takes raw node features $X \in \mathbb{R}^{N \times C}$ (e.g. a bag-of-words vector for each paper), transforms them to a hidden dimension $H$, and applies ReLU. The second layer maps the hidden representation to class logits and applies softmax.

Think of it as a two-step conversation: in the first round, each node collects its neighbors' features and builds a richer understanding of its local neighborhood. In the second round, it collects those enriched representations from neighbors — now carrying 2-hop information — and makes its classification decision.

The loss is computed only on the labeled nodes, but the gradient flows through the entire graph because every node's representation depends on its neighbors, labeled or not. This is the essence of semi-supervised learning on graphs: the structure itself propagates supervision signal.

To build intuition, consider a citation network: each paper is a node, each citation is an edge, and each paper's features are its bag-of-words vector. Suppose we label just 20 papers per category (out of thousands).

Layer 1. Every paper averages its own word vector with those of papers it cites or is cited by. A machine-learning paper surrounded by NLP papers absorbs NLP vocabulary into its representation. The weight matrix $W^{(0)}$ learns which combinations of neighbor features are informative — compressing, say, 1433 words into 16 hidden dimensions.

Layer 2. Now each paper averages the already-enriched representations of its neighbors. A paper two hops away from a labeled "deep learning" paper now carries some of that label's influence in its representation. The weight matrix $W^{(1)}$ maps 16 hidden dimensions to the number of classes, and softmax produces a probability distribution.

The labeled nodes anchor the gradient signal. Because the computation graph connects every node to its neighborhood, the gradient from each labeled node ripples outward through 2-hop paths, gently nudging the representations of unlabeled nodes toward the correct classes.

The key insight is that a GCN does not treat labeled and unlabeled nodes differently during the forward pass — all nodes participate in every propagation step. The asymmetry enters only at the loss: gradients originate from labeled nodes but backpropagate through the shared graph structure to update every weight matrix.

On the Cora dataset (2,708 papers, 7 classes), using only 20 labeled nodes per class (140 total, about 5%), the two-layer GCN achieved 81.5% accuracy. Compare this to label propagation (68.0%), DeepWalk (67.2%), or Planetoid (75.7%). The GCN's ability to jointly learn from features and structure is what makes it so effective with minimal labels.

Why does this work? Consider two nodes connected by an edge but with different initial features. If they share a label, the GCN learns weight matrices that produce similar hidden representations for both, despite their different inputs. The graph structure acts as a regularizer: connected nodes should have similar representations, which is precisely the smoothness assumption underlying semi-supervised learning on graphs.

In image CNNs, depth is power — VGG, ResNet, and modern architectures go 100+ layers deep. So why does GCN peak at 2–3 layers?

The answer is over-smoothing. Each GCN layer averages a node's representation with its neighbors'. After $K$ layers, each node's representation is influenced by all nodes within $K$ hops. For small-world graphs (like citation networks), 6–7 hops already reach most of the graph. The result: after too many layers, every node's representation converges to the same value — all information about the node's own identity is washed out.

Imagine stirring paint colors together. One stir blends neighboring colors nicely. Two stirs create a beautiful gradient. But 10 stirs? You get a uniform brown. That is over-smoothing.

Kipf and Welling found that 2–3 layers achieve optimal performance on their benchmarks. This is not a limitation of graph networks in general — later work (GATv2, JKNet, GCNII) introduced residual connections and identity mappings to enable deeper graph networks — but it is a fundamental property of vanilla GCN that practitioners must respect.

Kipf and Welling evaluated on three citation network datasets — Cora, Citeseer, and Pubmed — and the NELL knowledge graph. In each, only a handful of labels per class were used for training.

On Cora (2,708 nodes, 5,429 edges, 7 classes): GCN achieved 81.5% accuracy with just 140 labeled nodes. The closest competitor, Planetoid, scored 75.7%.

On Citeseer (3,327 nodes, 4,732 edges, 6 classes): GCN reached 70.3%, beating Planetoid's 64.7%.

On Pubmed (19,717 nodes, 44,338 edges, 3 classes): GCN scored 79.0%, surpassing Planetoid's 77.2%.

The GCN also scaled linearly: training time grew proportionally to edge count, not node count squared. On random graphs with up to 1 million edges, wall-clock time remained feasible on a single GPU.

GCN proved that a principled simplification of spectral theory could yield a practical, scalable architecture. This single insight triggered an avalanche of graph neural network research.

GCN's most lasting contribution is not a number on a leaderboard — it is the proof that graphs are a first-class data type for deep learning. Before this paper, graph methods were niche and expensive. After it, graph neural networks became a standard tool in the ML toolkit, as natural as convolutions for images or attention for sequences.