TALK.md - Semi-Supervised Classification with Graph Convolutional Networks

Verifiable Press / Blog Coverage

  1. ICLR 2017 (Oral presentation) - GCN was presented at the International Conference on Learning Representations 2017 and received outstanding reviews. The paper is available at OpenReview: https://openreview.net/forum?id=SJU4ayYgl

  2. Thomas Kipf Blog Post - The author wrote a widely-read companion blog post “Graph Convolutional Networks” (https://tkipf.github.io/graph-convolutional-networks/) that explains the spectral motivation in accessible terms and includes the Karate Club embedding visualization. This blog post is one of the most-cited GNN explainers in the community.

  3. Stanford CS224W: Machine Learning with Graphs - Jure Leskovec course covers GCN as a foundational graph neural network architecture, with detailed lecture notes on the spectral derivation and the simplified propagation rule. The GCN layer is taught as the starting point for all message-passing GNNs. (https://web.stanford.edu/class/cs224w/)

  4. Geometric Deep Learning (Bronstein et al., 2017) - Positions GCN as the graph-domain analogue of convolutional neural networks, providing a unified mathematical framework (symmetry groups, filters, pooling) that encompasses CNNs on grids, GCNs on graphs, and spherical CNNs.

  5. PyTorch Geometric Documentation - The GCNConv layer in PyG is a direct implementation of the Kipf and Welling propagation rule, and is one of the most-used GNN layers in practice. The documentation explicitly references this paper. (https://pytorch-geometric.readthedocs.io/)

Interview Q&A

Q1: What was the key simplification that made GCN practical?

Thomas Kipf: The spectral approach to graph convolutions existed before us - Bruna et al. (2014) defined filters in the Fourier domain using the eigendecomposition of the graph Laplacian, and Defferrard et al. (2016) used Chebyshev polynomials to approximate those filters efficiently. But both approaches were still relatively complex. Our contribution was noticing that if you reduce the Chebyshev expansion to just first order - keeping only the immediate neighborhood - you get a propagation rule that is a simple matrix multiplication with the normalized adjacency matrix. No eigendecomposition, no polynomial coefficients. Just A_norm @ H @ W. That simplification turned out to be not just faster but also empirically better on the benchmarks we tested, which was a pleasant surprise.

Q2: Why does the two-layer GCN work so well with so few labels?

Max Welling: The graph structure provides an incredibly strong inductive bias. In citation networks, if two papers cite each other, they are likely in the same research area - that is homophily. The GCN exploits this by propagating features along edges: even if only a few nodes are labeled, the labels diffuse through the graph via the normalized adjacency matrix. Two layers give a 2-hop receptive field, which is enough to reach a labeled node from most unlabeled nodes in a well-connected graph. The key is that the propagation and the feature transformation are learned jointly - the model learns weights that make the propagation useful for classification, not just smoothing.

Q3: What are the limitations of the first-order approximation?

Thomas Kipf: The main limitation is the narrow receptive field. Each layer only reaches immediate neighbors, so you need many layers to capture long-range dependencies - but deep GCNs suffer from over-smoothing, where all node representations converge to the same vector. This was identified in follow-up work by Li et al. (2018) and others. The Chebyshev approach with K>1 can capture multi-hop structure in a single layer, which partially addresses this. Another limitation is that the normalization is fixed - it does not adapt to the task. Graph Attention Networks (Velickovic et al., 2018) addressed this by replacing fixed normalization with learned attention weights.

Q4: How does GCN relate to message-passing neural networks (MPNNs)?

Max Welling: GCN is a special case of the message-passing framework that Gilmer et al. (2017) formalized. In MPNN terms, the message function is a linear projection of the neighbor features, the aggregation is a normalized sum, and the update function is a nonlinearity. The general MPNN framework subsumes GCN, GraphSAGE, GAT, GIN, and many others - they all differ in how they compute and aggregate messages. The contribution of our paper was showing that the simplest possible message function (identity + linear + sum) is already surprisingly powerful when combined with the right normalization.

Q5: What advice would you give to someone implementing a GCN from scratch?

Thomas Kipf: Start with the propagation rule - it is literally one line of NumPy: H_new = relu(A_norm @ H @ W). The entire graph part of a GCN is that matrix multiply with A_norm. Everything else is standard neural network machinery. The most common mistake I see is forgetting the self-loops (A_tilde = A + I) - without self-loops, a node features get completely overwritten by its neighbors at each layer, which destroys the node identity. Also, the symmetric normalization (D_tilde^-1/2) matters more than people expect - using the row-normalized adjacency instead changes the results noticeably, especially on graphs with skewed degree distributions.

Common Misconceptions

  1. “GCN is a convolutional neural network for graphs.” - While the name borrows from CNNs, the convolution in GCN is defined in the spectral domain (graph Fourier transform), not the spatial domain. The first-order approximation makes it look like a spatial neighborhood aggregation, but the derivation comes from spectral graph theory. The connection to spatial convolution is a consequence, not the starting point.

  2. “More GCN layers always help.” - The opposite is true: deep GCNs (more than 3-4 layers) typically perform worse due to over-smoothing. Each layer averages a node representation with its neighbors, so after many layers, all representations converge. This is fundamentally different from CNNs where depth is almost always beneficial. Most GCN applications use 2-3 layers.

  3. “GCN requires node features.” - While the paper uses bag-of-words features for citation networks, GCN works with any input feature matrix, including the identity matrix (one-hot node IDs). When no features are available, using the identity matrix as input lets the GCN learn node-specific representations purely from structure, similar to DeepWalk-style embeddings but with end-to-end supervised training.

  4. “The normalized adjacency is just a preprocessing step.” - The normalization D_tilde^-1/2 * A_tilde * D_tilde^-1/2 is the core of the model. Without it, high-degree nodes would dominate aggregation, and training would be unstable. The symmetric normalization ensures that the propagation is a contraction (spectral norm <= 1), which is what makes the model trainable and what connects it back to the spectral theory.

Real Citations

  • Kipf, T.N. and Welling, M. (2017). “Semi-Supervised Classification with Graph Convolutional Networks.” ICLR 2017. arXiv:1609.02907. 40,000+ Google Scholar citations.

  • Key predecessors:
    • Bruna, J. et al. (2014). “Spectral Networks and Locally Connected Networks on Graphs.” ICLR 2014. (Original spectral graph convolution)
    • Defferrard, M. et al. (2016). “Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.” NIPS 2016. (Chebyshev polynomial approximation)
    • Hammond, D.K. et al. (2011). “Wavelets on Graphs via Spectral Graph Theory.” Applied and Computational Harmonic Analysis. (Chebyshev filters foundation)
  • Key follow-ups:
    • Hamilton, W. et al. (2017). “Inductive Representation Learning on Large Graphs (GraphSAGE).” NeurIPS 2017. (Inductive neighborhood sampling)
    • Velickovic, P. et al. (2018). “Graph Attention Networks (GAT).” ICLR 2018. (Learned attention replacing fixed normalization)
    • Xu, K. et al. (2019). “How Powerful are Graph Neural Networks? (GIN).” ICLR 2019. (Theoretical expressiveness analysis)
    • Gilmer, J. et al. (2017). “Neural Message Passing for Quantum Chemistry.” ICML 2017. (MPNN framework formalizing GCN)
  • Other notable:
    • Li, Q. et al. (2018). “Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning.” AAAI 2018. (Over-smoothing analysis)
    • Wu, F. et al. (2019). “Simplifying Graph Convolutional Networks (SGC).” ICML 2019. (Shows linear GCN is competitive)
    • Kipf, T.N. and Welling, M. (2016). “Variational Graph Auto-Encoders.” Bayesian DL Workshop, NIPS 2016. (Unsupervised extension via VAE)