The Graph Convolutional Network of Kipf and Welling (2017) is the most widely used graph neural network layer and the standard baseline for node classification. Each layer replaces every node's features with a degree-normalized average of its own and its neighbors' features, followed by a shared linear transform and a nonlinearity. The rule is compact — H' = σ(Â H W) — but it is grounded in spectral graph theory, which explains both why it works and its main failure mode, over-smoothing.
Read the product right to left. H W applies the same linear map to every node's feature vector — the shared "kernel". Multiplying by the normalized adjacency  then replaces each row with a weighted sum over the node's neighborhood. A nonlinearity follows. Because  is sparse, the layer costs time linear in the number of edges, and computing HW first (when d' < d) keeps the sparse product cheap.
Two modifications to raw A make the layer work. First, self-loops: à = A + I, otherwise a node's new representation would ignore its own features. Second, normalization: multiplying by raw A sums neighbors, so high-degree nodes get large activations and repeated layers explode or vanish. GCN uses symmetric normalization  = D̃−1/2 à D̃−1/2, where D̃ is the degree matrix of Ã; edge (u, v) receives weight 1/√(d̃u d̃v). Its eigenvalues lie in (−1, 1], so repeated application is numerically stable. The row-normalized alternative D̃−1à is an exact neighbor mean (GraphSAGE-mean style).
On a grid, convolution is multiplication in the Fourier domain. Graphs have an analogous transform: the eigenvectors U of the normalized graph Laplacian L = I − D−1/2 A D−1/2 act as frequencies, with small eigenvalues corresponding to signals that vary smoothly across edges. A spectral graph convolution filters a signal x as U gθ(Λ) UT x. That is exact but expensive (eigendecomposition is O(N3)) and not localized.
ChebNet (Defferrard et al., 2016) approximated the filter with a K-th order Chebyshev polynomial of L, which is K-hop localized and needs no eigendecomposition. Kipf and Welling took K = 1, approximated the largest eigenvalue as 2, tied the two remaining parameters into one, and applied the "renormalization trick" (adding self-loops before normalizing) to obtain Â. So a GCN layer is a first-order low-pass filter on the graph followed by a learned feature map: it smooths node features along edges. That is exactly what helps when connected nodes share labels (homophily) and exactly what causes over-smoothing when applied too many times.
The original paper's model is just two layers, with 16 hidden units, dropout 0.5, L2 weight decay 5e-4 on the first layer, and Adam at learning rate 0.01. Trained on a few labeled nodes per class of a citation graph, it substantially outperformed earlier label-propagation and embedding methods, which is why the setup became the standard benchmark (Cora, Citeseer, PubMed). Its success with tiny label sets comes from the graph: unlabeled nodes participate in message passing, so the loss on labeled nodes shapes the whole embedding space.
Writing the layer directly with a sparse matrix shows there is nothing hidden. In practice use torch_geometric.nn.GCNConv (see the GNN page) or DGL's GraphConv.
import torch
import torch.nn as nn
import torch.nn.functional as F
def normalized_adjacency(edge_index, num_nodes):
"""Return sparse A_hat = D^-1/2 (A + I) D^-1/2 from an undirected edge list."""
loops = torch.arange(num_nodes).repeat(2, 1)
ei = torch.cat([edge_index, edge_index.flip(0), loops], dim=1) # both directions + self-loops
ei = torch.unique(ei, dim=1)
deg = torch.zeros(num_nodes).scatter_add_(0, ei[0], torch.ones(ei.size(1)))
w = deg[ei[0]].rsqrt() * deg[ei[1]].rsqrt()
return torch.sparse_coo_tensor(ei, w, (num_nodes, num_nodes)).coalesce()
class GCNLayer(nn.Module):
def __init__(self, d_in, d_out):
super().__init__()
self.lin = nn.Linear(d_in, d_out, bias=False)
self.bias = nn.Parameter(torch.zeros(d_out))
nn.init.xavier_uniform_(self.lin.weight)
def forward(self, x, a_hat):
return torch.sparse.mm(a_hat, self.lin(x)) + self.bias # A_hat (X W) + b
class GCN(nn.Module):
def __init__(self, d_in, d_hid, n_cls, p=0.5):
super().__init__()
self.l1, self.l2, self.p = GCNLayer(d_in, d_hid), GCNLayer(d_hid, n_cls), p
def forward(self, x, a_hat):
x = F.dropout(x, self.p, self.training)
x = F.relu(self.l1(x, a_hat))
x = F.dropout(x, self.p, self.training)
return self.l2(x, a_hat) # logits
# Toy graph: two communities joined by one edge
edges = torch.tensor([[0, 0, 1, 2, 3, 4, 4, 5, 2],
[1, 2, 2, 3, 4, 5, 6, 6, 4]])
N = 7
a_hat = normalized_adjacency(edges, N)
x = torch.eye(N) # featureless: one-hot node ids
y = torch.tensor([0, 0, 0, 0, 1, 1, 1])
train = torch.tensor([True, False, False, False, False, False, True]) # one label per class
model = GCN(N, 8, 2)
opt = torch.optim.Adam(model.parameters(), lr=0.05, weight_decay=5e-4)
for _ in range(200):
model.train(); opt.zero_grad()
F.cross_entropy(model(x, a_hat)[train], y[train]).backward(); opt.step()
model.eval()
print(model(x, a_hat).argmax(1).tolist()) # labels spread to unlabeled nodesApplying  repeatedly is a random-walk-like diffusion: in the limit, the features of every node in a connected component converge to a vector determined only by degree, erasing the differences the classifier needs (Li et al., 2018). Two layers usually give the best results with plain GCN; accuracy typically degrades as layers are added. Remedies include residual connections, initial-residual and identity mapping (GCNII), jumping-knowledge networks, DropEdge, and decoupling propagation from transformation (APPNP and SGC propagate with a fixed filter, so they can reach far without stacking learned layers).
softmax(ÂK X W). It precomputes ÂKX once and is often close to GCN accuracy at a fraction of the cost.Take the path graph 1 – 2 – 3. Adding self-loops gives degrees d̃ = (2, 3, 2), and the symmetric normalization sets each entry of  to 1 / √(d̃i d̃j) for connected pairs:
| Â | node 1 | node 2 | node 3 |
|---|---|---|---|
| node 1 | 1/2 = 0.50 | 1/√6 ≈ 0.41 | 0 |
| node 2 | 0.41 | 1/3 ≈ 0.33 | 0.41 |
| node 3 | 0 | 0.41 | 0.50 |
Give node 1 a scalar feature of 1 and the others 0, and set W = 1 with no nonlinearity, so we see propagation alone. One layer gives Âx ≈ (0.50, 0.41, 0): the signal reaches node 2 but not node 3. A second layer gives Â2x ≈ (0.42, 0.34, 0.17): now node 3 has received information two hops away, and the values are becoming more alike. Keep multiplying and the vector approaches one proportional to √d̃, independent of where the signal started. That is over-smoothing in miniature, and it is why two or three layers are typical. Notice also that the middle node, with the higher degree, gives each neighbor a smaller share (0.41 rather than 0.50): symmetric normalization stops high-degree nodes from dominating.
The GCN layers produce one embedding per node; what you put on top decides the task. Node classification applies a softmax to each embedding and computes the loss only on labeled nodes, which is the semi-supervised setting of the original paper. Link prediction scores a pair of embeddings, commonly with a dot product or a small MLP, and trains against sampled non-edges as negatives; held-out edges must be removed from the graph used for message passing, or the model can see the answer. Graph classification pools all node embeddings of a graph (mean, sum or attention pooling) into one vector and classifies it; molecules and proteins are the standard examples, though for this task sum-based layers such as GIN are often more expressive than GCN.
Evaluation needs the same care as any ML project, plus graph-specific traps. Random node splits on citation graphs are easier than time-based or community-based splits, which better match deployment where new nodes arrive later. Always compare against an MLP on the node features alone and against simple label propagation; if the GCN does not beat both, the graph structure is not helping. Report means and standard deviations over several seeds and splits, because small benchmarks such as Cora have few labeled nodes and high variance.