Graph Neural Networks: Theory & Variants

Spectral Graph Theory Background

For a graph G = (V, E) with adjacency matrix A and degree matrix D, the normalized graph Laplacian is L = I − D^−½AD^−½. Its eigenvalues λ ∈ [0, 2] encode graph connectivity; small eigenvalues correspond to smooth (low-frequency) signals on the graph.

Key Architectures

• GCN (Kipf & Welling, 2017): H^(l+1) = σ(ÃH^(l)W^(l)) where à is the normalized adjacency with self-loops. A first-order spectral approximation.
• GAT (Veličković et al., 2018): Replaces fixed aggregation weights with learned attention coefficients α_ij, allowing neighbors to contribute differently.
• GraphSAGE (Hamilton et al., 2017): Samples a fixed-size neighborhood and aggregates via mean, LSTM, or pooling — enabling inductive learning on unseen nodes.

Over-smoothing

As depth increases, node representations converge to the same vector, losing discriminative power. This is related to repeated application of the graph diffusion operator: features converge to the dominant eigenvector of L. Solutions include residual connections, normalization layers, and PDE-inspired designs.

PDE-Inspired GNNs

Interpreting GNN layers as discretizations of PDEs on graphs opens new architectural possibilities. First-order hyperbolic PDEs (advection) preserve feature sharpness, contrasting with the diffusion behavior of standard GCNs. This connection motivates the PDE-based GNN work in my research.