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.

Write the GCN propagation $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$ and explain the roles of $\tilde{A} = A + I$, the symmetric normalization, and $W^{(l)}$.

Spectral derivation: why is the full graph convolution infeasible ($O(n^2)$ eigen-decomposition, dense $U$)? How does the first-order Chebyshev approximation $g_\theta \approx \theta_0 I + \theta_1 \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ reduce step by step to the GCN formula?

Why symmetric normalization $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ instead of the random-walk normalization $\tilde{D}^{-1}\tilde{A}$? Differences in numerical stability and aggregation semantics (weighted average vs normalized sum).

Mechanism of oversmoothing: why do node representations converge as layers deepen (repeated low-pass filtering, dominant spectral components)? What are the mitigations?

Transductive vs inductive learning: why is classic GCN transductive? How does it generalize to unseen nodes/graphs at inference?