Graph Convolutional Networks (GCN)
You'll learn: How GCNs simplify spectral convolutions into an efficient, localized layer using a first-order approximation that scales linearly with edges.
The Big Idea
Remember Chebyshev polynomial approximations? GCNs take that concept one step further by using only the first-order term (K=1). This creates an incredibly simple, fast propagation rule that captures local neighborhood structure without expensive eigendecompositions.
The GCN layer boils down to:
- Add self-loops to the graph (so nodes consider their own features)
- Normalize by node degrees
- Aggregate neighbor features with a learned weight matrix
Why First-Order?
Higher-order Chebyshev filters capture multi-hop neighborhoods but add computational cost. GCNs discovered that stacking multiple first-order layers works better than one complex high-order layer—each layer looks one hop away, but depth creates multi-hop receptive fields naturally.
The elegant GCN propagation rule is:
H^(l+1) = σ(D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l))
Where:
à = A + I(adjacency matrix plus self-loops)D̃is the degree matrix ofÃH^(l)are node features at layer lW^(l)is the trainable weight matrix- σ is a nonlinearity (like ReLU)
The Efficiency Win
This symmetric normalization D̃^(-1/2) Ã D̃^(-1/2) ensures numerical stability and prevents feature magnitudes from exploding as you aggregate. The operation is localized (only touching direct neighbors) and O(|E|) complexity—linear in the number of edges.
Key Takeaway: GCNs achieve powerful graph convolutions through a beautifully simple first-order approximation, trading spectral complexity for stackable, efficient layers that learn hierarchical graph representations.