Classic Architectures
Write the GCN layer equation and explain each part.
$\mathbf{H}^{(l+1)} = \sigma(\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\mathbf{H}^{(l)}\mathbf{W}^{(l)})$ where $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$. Normalized adjacency averages neighbor features fairly. $\mathbf{W}^{(l)}$ is a learnable linear transform. $\sigma$ is activation. It is a first-order spectral approximation (ChebNet with $K=1$).
How does GraphSAGE differ from GCN?
GraphSAGE explicitly concatenates the node's own embedding with an aggregated neighborhood embedding, then passes through an MLP. It supports multiple aggregators (mean, max, LSTM) and neighbor sampling for scalability. It is designed for inductive learning on large graphs.
How does GAT attention work on graphs?
Compute attention scores $e_{ij} = \text{LeakyReLU}(\vec{a}^T[\mathbf{W}\mathbf{h}_i \| \mathbf{W}\mathbf{h}_j])$, normalize with softmax over neighbors to get $\alpha_{ij}$, then update $\mathbf{h}_i' = \sigma(\sum_j \alpha_{ij}\mathbf{W}\mathbf{h}_j)$. Different neighbors get different weights - unlike GCN's fixed normalization.
Why is GIN more expressive than GCN?
GIN uses sum aggregation followed by an injective MLP: $\mathbf{h}_i' = \text{MLP}((1+\epsilon)\mathbf{h}_i + \sum_{j\in\mathcal{N}(i)}\mathbf{h}_j)$. Sum preserves multiset structure (mean loses count info). Xu et al. proved this matches the power of the 1-Weisfeiler-Lehman test - the upper bound for standard MPNNs.
What is the 1-WL test and why does it matter?
The 1-Weisfeiler-Lehman test iteratively refines node labels by hashing (own label + sorted neighbor labels). It distinguishes many but not all non-isomorphic graphs. Standard MPNNs are at most as powerful as 1-WL. GIN achieves this bound; GCN does not.
When would you pick GAT over GCN?
When neighbors have varying importance (heterogeneous neighbor types, attention helps), or when GCN's fixed averaging loses signal. Cost: more parameters and compute. On simple homophilous citation graphs, GCN may match GAT with less tuning.
What is MPNN and how does it handle edge features?
MPNN (Gilmer 2017) defines message $\mathbf{m}_{ij} = \mathbf{M}(\mathbf{h}_i, \mathbf{h}_j, \mathbf{e}_{ij})$, aggregate messages, then update $\mathbf{h}_i' = \mathbf{U}(\mathbf{h}_i, \sum_j \mathbf{m}_{ij})$. Edge features $\mathbf{e}_{ij}$ (bond type, distance) are built into the message - critical for molecules.
Why add self-loops in GCN?
Without self-loops, a node's new embedding is only a function of neighbors - it loses its own identity. Adding $\mathbf{I}$ to $\mathbf{A}$ lets each node include its own features in the aggregation, stabilizing training.
Compare mean vs sum aggregation.
Sum: preserves neighborhood size information; injective with MLP (GIN). Mean: size-invariant; can fail to distinguish neighborhoods with same mean but different counts. Max: captures strongest neighbor signal; good for some heterophily settings.
What is the receptive field of an $L$-layer GNN?
The $L$-hop neighborhood - all nodes within $L$ edges. A 2-layer GCN on node $i$ uses features from $i$ and its 2-hop neighbors. Deeper layers = wider context but also more oversmoothing risk.