PAPERS-07-004 · Paper — Graph Convolutional Networks (GCN)

The paper

The paper “Semi‑Supervised Classification with Graph Convolutional Networks” by Thomas Kipf and Max Welling (2016, ICLR) introduced a landmark method that made deep learning work on graph‑structured data, opening a whole new research area.

Before this paper

Before this work, convolutional networks were designed for regular grids like images, while graphs have no fixed geometry. Researchers struggled to adapt convolution to arbitrary graph structures, and existing spectral approaches were mathematically cumbersome and hard to scale. As a result, graph‑based learning remained limited and inefficient. Think of trying to apply a standard image filter to a tangled web of roads—without a consistent layout, the filter loses its meaning.

The key idea

The key insight was to define a simple, efficient graph convolution: each node updates its representation by aggregating the features of its immediate neighbors and then applying a learned linear transformation. By treating the neighborhood as a weighted average, the method captures the essence of local structure without expensive spectral decomposition, making the operation both intuitive and computationally light.

How it works

GCN starts with node feature vectors and the graph’s adjacency matrix. First, it adds self‑loops so each node also sees its own features. Then it normalizes the adjacency by the degree of each node, effectively averaging neighbor features. The normalized features are multiplied by a weight matrix that is learned during training. This operation forms one layer; stacking a few layers lets information propagate farther across the graph. For a two‑layer GCN, the receptive field of a node expands to include nodes up to two hops away, allowing the model to integrate information from a broader context. Finally, a softmax classifier predicts labels for the nodes of interest.

See it — convolution on a graph

flowchart LR
  A["Node + its<br/>neighbors"] --> B["Average neighbor<br/>features"]
  B --> C["Transform<br/>(weights)"]
  C --> D["New node<br/>representation"]

What they showed

Using only a handful of labeled nodes, GCN achieved strong results on standard citation‑network benchmarks such as Cora, Citeseer, and Pubmed, outperforming prior methods on these tasks.

What it changed

The paper made graph neural networks simple, practical, and scalable, turning GNNs into a mainstream tool. Its clear formulation sparked a wave of follow‑up research and many modern GNN architectures trace their roots back to this work. It demonstrated that deep learning could be effectively applied to non‑Euclidean data. Next: GraphSAGE.

The one-line takeaway

GCN showed that a single, well‑designed graph convolution layer can unlock powerful learning on arbitrary graphs.

Read it / meet it

Reading the original paper gives insight into the elegant derivation and experimental setup that started the GNN boom. Today, you’ll see its legacy in countless libraries and newer models that build directly on this simple graph convolution.