Graph Conv Network

GCN (Graph Convolutional Network, Kipf & Welling 2017) propagates as $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$, where $\tilde{A} = A + I$ adds self-loops, $\tilde{D}$ is its degree matrix, $W^{(l)}$ is learnable, and $\sigma$ is an activation — essentially “degree-normalized weighted average of neighbor features + linear transform”. Spectral motivation: the graph convolution $x * g_\theta = U g_\theta(\Lambda) U^T x$ requires $O(n^2)$ eigen-decomposition; approximating $g_\theta(\Lambda) \approx \sum_{k=0}^{K} \theta_k T_k(\hat{\Lambda})$ with Chebyshev polynomials and truncating at first order ($K = 1$), sharing the two parameters ($\theta_0 = -\theta_1 = \theta$) and renormalizing ($\tilde{A} = A + I$) yields exactly the formula above — each node aggregates its 1-hop neighbors, and stacking $L$ layers expands the receptive field to $L$ hops. The cost is oversmoothing: after many layers node representations collapse toward the dominant eigenvectors and become indistinguishable (repeated low-pass filtering erases high-frequency information), so classic GCNs are typically 2–3 layers; mitigations include residual connections, JK-Net (jump connections with pooling), PairNorm, and layer normalization.

semi-supervised node classification (Cora/Citeseer/PubMed benchmarks), representation learning on citation and social networks; interview staples: writing the propagation formula, the first-order Chebyshev spectral derivation, normalization choices, and the oversmoothing mechanism.

naive graph convolution requires the $O(n^2)$ eigen-decomposition of a dense $U$ that is also non-transferable. The first-order Chebyshev truncation reduces the filter to a single sparse matrix multiplication $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ ($O(|E|)$), leaving only $W$ to learn like an ordinary DNN; symmetric normalization stabilizes numerics and enables generalization to unseen nodes, laying the “message passing” paradigm that GAT/GraphSAGE/GIN later follow.

Test Your Knowledge: Practice Questions for "Graph Conv Network"

Single choice pitfall questions with instant feedback and mistake tracking.