Semi-Supervised Classification with Graph Convolutional Networks

Chapter 1: From Spectral to Spatial

GCN's derivation starts from spectral graph theory — but the key contribution is showing that the resulting model has a simple spatial interpretation. We'll trace the path from spectral convolutions to the final layer equation.

The Spectral Starting Point

In signal processing, filtering a signal s in the frequency domain is equivalent to multiplying by a filter g in frequency space. For graphs, the analog is: a graph convolution filters a graph signal x (one feature per node) using the graph Laplacian's eigenvectors.

The normalized graph Laplacian is L = I − D^−½AD^−½, where A is the adjacency matrix and D is the degree matrix. Its eigendecomposition is L = U Λ U^T, where U is a matrix of eigenvectors (the "graph Fourier basis") and Λ is diagonal (the eigenvalues = "frequencies").

A graph convolution with filter g is:

where g(Λ) = diag(g(λ₀), ..., g(λ_n−1)) applies the filter to each eigenvalue. This is exact but hopelessly expensive: O(N²) per convolution just for the U^Tx projection — and computing U itself is O(N³).

Chebyshev Polynomial Approximation

Hammond et al. (2011) showed you can approximate g(Λ) as a truncated polynomial in Λ:

where Λ̃ = 2Λ/λ_max − I (rescaled to [−1,1]) and T_k are Chebyshev polynomials. The key insight: A^k applied to a graph signal gives the k-hop neighborhood contribution. So the resulting filter uses only k-hop neighbors — no eigenvector decomposition needed. Cost: O(K|E|) per layer.

Kipf & Welling's Key Simplification

Kipf & Welling take K = 1: only first-order Chebyshev polynomials. This is the first-order approximation. For K=1, the filter becomes:

Two parameters: θ₀ (how much to weight the node itself) and θ₁ (how much to weight the mean of neighbors). They then make another simplification: set θ = θ₀ = −θ₁. This gives a single-parameter filter:

Note that I + D^−½AD^−½ has eigenvalues in [0, 2]. This is numerically problematic — repeated applications can cause exploding or vanishing values. Enter the renormalization trick (Chapter 3).

Chapter 2: The GCN Layer

After the spectral derivation and renormalization trick (Chapter 3), the final GCN propagation rule for a multi-feature, multi-layer network is:

Where every symbol earns its place:

What One Layer Does — Step by Step

Let's trace the computation for a tiny example: 4 nodes, 2 input features, 2 output features. Node features: H⁽⁰⁾ ∈ R^4×2. Weight matrix: W⁽⁰⁾ ∈ R^2×2.

Step 1: Multiply H^(l) W^(l). This is a standard linear transformation of each node's features. Shape: [4,2] × [2,2] = [4,2]. Every node's features are rotated/scaled in the same way. No graph structure yet — this is just a linear layer.

Step 2: Left-multiply by D̃^−½ÃD̃^−½. This is where the graph structure enters. For each node i, this operation computes a weighted average of the TRANSFORMED features of all neighbors (including i itself via the self-loop). The weights are 1/√(d_i·d_j) for each neighbor j. Shape stays [4,2].

Step 3: Apply σ (ReLU). Element-wise nonlinearity. Result: H⁽¹⁾ ∈ R^4×2.

python
# Complete GCN layer: exact implementation of the paper's equation
# H^(l+1) = sigma( D̃^(-½) Ã D̃^(-½) H^(l) W^(l) )
import torch
import torch.nn as nn
import torch.nn.functional as F

def precompute_adj_norm(A):
    """Pre-compute D̃^(-½) Ã D̃^(-½). Call once, cache result."""
    N = A.shape[0]
    A_tilde = A + torch.eye(N)                      # Ã = A + I
    D_tilde = A_tilde.sum(dim=1)                  # D̃ diagonal
    D_inv_sqrt = torch.diag(D_tilde.pow(-0.5))    # D̃^(-½)
    return D_inv_sqrt @ A_tilde @ D_inv_sqrt        # [N, N]

class GCNLayer(nn.Module):
    def __init__(self, in_feats, out_feats):
        super().__init__()
        self.W = nn.Linear(in_feats, out_feats, bias=False)
        # No bias needed: the normalized adj already acts like centering

    def forward(self, H, A_norm):
        # H: [N, in_feats]   A_norm: [N, N] (pre-computed, cached)
        step1 = self.W(H)        # [N, out_feats] — linear transform first
        step2 = A_norm @ step1   # [N, out_feats] — neighborhood aggregation
        return F.relu(step2)     # element-wise ReLU

# Two-layer GCN (the paper's model for Cora):
# Input dim: 1433 (bag-of-words) → hidden: 16 → output: 7 (classes)
# Softmax at output, not ReLU
class TwoLayerGCN(nn.Module):
    def __init__(self, in_feats=1433, hidden=16, num_classes=7):
        super().__init__()
        self.layer1 = GCNLayer(in_feats, hidden)
        self.layer2 = nn.Linear(hidden, num_classes, bias=False)

    def forward(self, X, A_norm):
        H = self.layer1(X, A_norm)              # [N, 16]
        logits = A_norm @ self.layer2(H)        # [N, 7] — aggregation at last layer too
        return F.log_softmax(logits, dim=-1)    # [N, 7]

Chapter 3: The Renormalization Trick

After the K=1 simplification from Chapter 1, the filter was: θ(I + D^−½AD^−½)x. The matrix (I + D^−½AD^−½) has eigenvalues in [0, 2]. This is the problem: when you stack multiple layers (multiply by this matrix multiple times), eigenvalues larger than 1 explode and eigenvalues near 0 vanish. Training becomes unstable.

The Fix: Add Self-Loops, Re-Normalize

Instead of starting from (I + D^−½AD^−½), which causes instability, Kipf & Welling propose the renormalization trick:

The key difference: instead of adding I to the NORMALIZED adjacency (I + D^−½AD^−½), you add I to the RAW adjacency FIRST (à = A + I), THEN normalize (D̃^−½Ã D̃^−½). This keeps all eigenvalues in [0, 1], preventing both explosion and vanishing.

Why Does This Help Numerically?

The normalized adjacency D̃^−½Ã D̃^−½ is a stochastic matrix — each row sums to at most 1 (it's row-stochastic under the symmetric normalization). Its spectral radius is at most 1. Multiplying by it repeatedly (stacking GCN layers) will not cause the signal to explode. Values can only stay the same or decrease.

Worked Example: Renormalization on a Small Graph

Triangle graph: 3 nodes (A, B, C), all connected. Adjacency matrix:

Degree matrix: D = diag(2, 2, 2). Without renormalization: I + D^−½AD^−½ = I + (1/2)·ones_minus_identity = eigenvalue max = 1 + 1 = 2. Repeated application explodes.

With renormalization: à = A + I = [[1,1,1],[1,1,1],[1,1,1]]. D̃ = diag(3,3,3). D̃^−½Ã D̃^−½ = (1/3)·[[1,1,1],[1,1,1],[1,1,1]]. Each node gets 1/3 of each node's features (including its own). Eigenvalues: {1, 0, 0}. Maximum eigenvalue = 1. Stable.

Chapter 4: Multi-Layer GCN

The paper uses a two-layer GCN for Cora, Citeseer, and Pubmed. Two layers because: (1) one layer only captures 1-hop neighbors, (2) more than 2 layers for citation graphs empirically hurts performance (over-smoothing begins).

The Two-Layer Model

Let  = D̃^−½Ã D̃^−½ (pre-computed, cached). The full two-layer GCN is:

Every piece of this equation is important:

• X W⁽⁰⁾: Linear transform of raw features. [N, 1433] × [1433, 16] = [N, 16]. Reduces from 1433-dim bag-of-words to 16-dim hidden.
• Â · (X W⁽⁰⁾): Aggregation over the 1-hop neighborhood. Each node's hidden representation becomes the weighted mean of its neighbors' representations.
• ReLU(...): Element-wise nonlinearity. Without this, two linear layers collapse to one linear layer (useless depth).
• W⁽¹⁾: [16, 7] weight matrix. Maps from 16-dim hidden to 7-dim class logits.
• Second  · (...): Second round of neighborhood aggregation. Now each node has seen its 2-hop neighborhood.
• softmax(...): Row-wise softmax to get class probabilities. Applied at the final layer only.

Parameter Count

For Cora (1433 input features, 16 hidden, 7 classes): W⁽⁰⁾ has 1433 × 16 = 22,928 parameters. W⁽¹⁾ has 16 × 7 = 112 parameters. Total: 23,040 parameters. This is tiny — fewer than most fully connected networks on tabular data. The graph structure does the heavy lifting; the learned parameters are compact.

Dropout for Regularization

With only 140 labeled nodes, overfitting is a severe risk. The paper uses dropout on both X (before the first layer) and H⁽¹⁾ (between layers) with a rate of 0.5. L2 regularization (λ = 5×10⁻⁴) is also applied to W⁽⁰⁾ and W⁽¹⁾. Together, these allow training to convergence without overfitting the 140 labels.

python
# Full two-layer GCN — the paper's actual model for Cora
import torch
import torch.nn as nn
import torch.nn.functional as F

class GCN(nn.Module):
    def __init__(self, nfeat=1433, nhid=16, nclass=7, dropout=0.5):
        super().__init__()
        self.W0 = nn.Linear(nfeat, nhid, bias=False)   # [1433, 16]
        self.W1 = nn.Linear(nhid, nclass, bias=False)   # [16, 7]
        self.dropout = dropout

    def forward(self, X, A_hat):
        # A_hat = D̃^(-½) Ã D̃^(-½), pre-computed [N, N]
        X = F.dropout(X, self.dropout, training=self.training)
        H = F.relu(A_hat @ self.W0(X))        # [N, 16] — first layer
        H = F.dropout(H, self.dropout, training=self.training)
        Z = A_hat @ self.W1(H)                # [N, 7] — second layer (no ReLU)
        return F.log_softmax(Z, dim=-1)       # [N, 7] log-probabilities

# Training with L2 regularization on weights
model = GCN()
optimizer = torch.optim.Adam(
    model.parameters(), lr=0.01, weight_decay=5e-4
)

# Loss: cross-entropy only on labeled nodes
def train(model, X, A_hat, labels, train_mask):
    model.train()
    optimizer.zero_grad()
    out = model(X, A_hat)
    loss = F.nll_loss(out[train_mask], labels[train_mask])  # only labeled!
    loss.backward()
    optimizer.step()
    return loss.item()

Chapter 5: Semi-Supervised Training

The word "semi-supervised" in the title is doing real work. Let's be precise about what it means here and why it enables learning from 140 labels.

The Loss Function

Cross-entropy, computed only over the labeled nodes:

Where V_L is the set of labeled nodes (140 for Cora), Y ∈ R^N×F is the label indicator matrix (one-hot), and Z is the GCN's output (softmax probabilities). The sum runs over ONLY the 140 labeled rows of Z. Unlabeled nodes (2,568 of them) contribute NO loss term.

This seems strange: how can 2,568 unlabeled nodes possibly be useful if they never contribute to the loss?

The Mechanism: Indirect Supervision

Even though unlabeled nodes don't appear in the loss, they DO appear in the forward pass. The GCN's message passing means:

1. Labeled node A's embedding is computed from A's features + A's neighbors' features. Some neighbors of A are unlabeled nodes B, C, D.
2. When the loss backpropagates through A's embedding, it implicitly sends gradients to W⁽⁰⁾ and W⁽¹⁾ that encode "what features predict A's label."
3. The SAME weights W⁽⁰⁾, W⁽¹⁾ are applied when computing the embedding of unlabeled node E (which might share features with A).
4. At inference time, E's embedding is computed using weights trained on A and other labeled nodes — so E benefits from the label signal even though it was never in the loss.

Training Details

The model is trained for up to 200 epochs with early stopping based on validation loss (500 validation nodes). Adam optimizer, learning rate 0.01, L2 regularization 5×10⁻⁴ on weights, dropout 0.5 on inputs and hidden layer. All training runs in a single forward pass through the ENTIRE graph — no mini-batches, since the full graph fits in memory.

Chapter 6: Results

The paper evaluates on three citation network benchmarks. The results were striking: a simple 2-layer GCN with 23,040 parameters outperforms complex graph-based methods that use hand-crafted features, spectral methods, and graph regularization.

Benchmark Datasets

Classification Accuracy (Test Set)

GCN improves over the second-best method (Planetoid) by 5.8% on Cora, 5.6% on Citeseer, and 1.8% on Pubmed. These are large margins — especially given that GCN uses far fewer parameters and is simpler to train.

Why GCN Wins

The key advantage over DeepWalk: GCN uses node features (1,433-dim bag-of-words on Cora), while DeepWalk ignores them entirely. The features are highly informative for topic classification — a paper about "reinforcement learning" likely contains the word "reward." DeepWalk must infer class from graph structure alone.

The key advantage over Planetoid (which also uses features): GCN's end-to-end training optimizes the features and graph structure jointly, while Planetoid uses them in separate stages. Joint optimization is almost always better.

Chapter 7: Why It Works

GCN achieves high accuracy with 140 labels. The question is: why? What is the model actually doing, and what prior assumptions make it work?

Connection to Label Propagation

Label propagation (LP) is a classic semi-supervised method: assume connected nodes likely have the same label, then iteratively propagate known labels to unknown nodes. The GCN is a learnable version of this. The propagation rule  = D̃^−½Ã D̃^−½ is exactly the "influence matrix" used in LP. What GCN adds: a learned feature transformation W that tells the model WHAT features to look for when propagating.

The Homophily Assumption

GCN implicitly assumes homophily: connected nodes tend to belong to the same class. In citation networks, this is true — papers cite papers in their field. If you cite a reinforcement learning paper, you're probably also an RL paper.

When does this fail? In social networks, "haters" might connect to people they hate (heterophily). A GCN applied naively would try to make their embeddings similar, which is wrong. This is a genuine limitation — not a flaw in the math, but a mismatch between the model's implicit assumption and the data's actual structure.

What the Embeddings Learn

The paper shows a 2D t-SNE visualization of the GCN embeddings on Cora. The 7 classes are cleanly separated in the embedding space, with only 140 labels used for training. The model has correctly placed unlabeled papers in the same cluster as labeled papers on the same topic — purely from the combination of citation structure and word content.

One way to think about it: the GCN computes a "smoothed" version of each node's features, where the smoothing operator is the graph structure. A paper's embedding is not just its own bag-of-words, but a weighted average of the bag-of-words of all papers it cites and is cited by. This average is a much better representation of the paper's field than its raw word content, because it captures community membership.

Chapter 8: Limitations

GCN's success sparked years of follow-up work precisely because its limitations were clear and well-defined. Understanding them tells you when to use GCN and when to reach for something else.

1. Over-Smoothing with Depth

As established in Chapter 4, adding more GCN layers causes all node embeddings to converge to the same vector. After K layers, each node's embedding is the weighted average of its K-hop neighborhood. For most real graphs, the K-hop neighborhood covers nearly all nodes when K ≥ 5. All embeddings become identical — useless for classification.

Consequence: GCN is limited to shallow networks (2-3 layers). This is in stark contrast to CNNs on images, which benefit from 50+ layers. Deep GNNs require specialized techniques (skip connections, JK-networks, DropEdge).

2. Fixed Graph — Transductive Setting

The normalized adjacency  is pre-computed from the FULL graph structure. If a new node arrives,  must be recomputed. The model cannot efficiently embed a new node without re-running the forward pass with the updated graph.

Consequence: GCN as described is transductive — it cannot generalize to unseen nodes. GraphSAGE (Hamilton et al., 2017) fixes this by sampling a fixed-size neighborhood at each layer, allowing truly inductive inference.

3. Mean Aggregation Loses Information

D̃^−½Ã D̃^−½ computes a MEAN of neighbor features. Two different neighborhood distributions can have the same mean. A node with neighbors [1, 3] and a node with neighbors [2, 2] would produce identical aggregate signals if the mean is the same value.

Consequence: GCN cannot distinguish some structurally different neighborhoods — it fails on certain graph structure tasks. GIN (Graph Isomorphism Network, Xu et al., 2019) showed that SUM aggregation is more expressive than mean, achieving maximal expressivity (as powerful as the 1-Weisfeiler-Lehman graph isomorphism test).

4. Fixed Edge Weights

In GCN, the aggregation weights 1/√(d_i·d_j) are determined by the graph structure alone. They don't adapt based on the CONTENT of the nodes. An edge between two very similar nodes should perhaps carry more weight than an edge between very different nodes.

Consequence: Graph Attention Networks (GAT, Veličković et al., 2018) replace fixed structural weights with learned content-based attention weights — an important step forward for heterogeneous graphs.

5. Homophily Requirement

GCN's message passing assumes connected nodes are similar. On heterophilic graphs (nodes connect to dissimilar nodes), GCN can perform WORSE than an MLP that ignores graph structure entirely.

Chapter 9: Connections

GCN is the first node in a graph of ideas. Understanding where it sits helps you navigate the broader GNN literature.

The Paper

Kipf, T.N. & Welling, M. (2017). "Semi-Supervised Classification with Graph Convolutional Networks." ICLR 2017. arXiv:1609.02907. Over 20,000 citations as of 2024 — one of the most cited papers in all of machine learning.

Papers That GCN Builds On

• Spectral Graph Theory (Chung, 1997): Defines the graph Laplacian, its eigenvectors, and spectral graph signal processing — the theoretical foundation for the derivation in Chapter 1.
• Bruna et al. (2014): "Spectral Networks" — first paper to propose learning on graphs using spectral convolutions. GCN is a practical, scalable simplification of this idea.
• Hammond et al. (2011): Proposed the Chebyshev polynomial approximation to spectral convolutions. GCN uses K=1 of their framework.
• Defferrard et al. (ChebNet, 2016): The direct predecessor — used K=3 Chebyshev. GCN simplifies to K=1 and adds the renormalization trick.

Papers That Build on GCN

• GraphSAGE (Hamilton et al., 2017): Inductive version. Samples fixed-size neighborhoods instead of using the full  matrix, enabling mini-batch training and generalization to unseen nodes.
• GAT (Veličković et al., 2018): Replaces fixed structural weights with learned attention weights, adapting the aggregation to node content. GAT = GCN + attention.
• GIN (Xu et al., 2019): Proves that SUM aggregation is strictly more expressive than MEAN aggregation. GIN = GCN + SUM + theoretically optimal.
• MPNN (Gilmer et al., 2017): Unified framework for all message-passing GNNs. Shows GCN, GraphSAGE, and GAT are all special cases of the same abstract architecture.
• Sign (Rossi et al., 2020): Pre-computes multiple powers of  and concatenates them — a scalable generalization of multi-layer GCN without the over-smoothing issue.

Related Gleams

Start with CS224W Lecture 1 for graph basics. Then Lecture 2 for shallow embeddings (DeepWalk). Then Lecture 3 for the GNN framework this paper instantiates. The CS224W series continues with GraphSAGE and GAT.

"The simplicity of the GCN model is perhaps its most striking feature. A two-layer model with a first-order spectral approximation, a renormalization trick, and 23,040 parameters beats methods with far more complexity. This is the signal that the idea is fundamentally right."
— Paraphrase of the CS224W interpretation

arXiv:1609.02907 →    Original Code (tkipf/gcn) →