Message passing
Node h_v^(l+1) = UPDATE(h_v^l, AGGREGATE({h_u^l : u ∈ N(v)})). Layers compose.
Advertisement
Variants
GCN: mean aggregation + linear. GAT: attention over neighbors. GraphSAGE: sample + aggregate. GIN: sum + MLP (theoretically most powerful).
Advertisement
Depth issue
Deep GNNs suffer over-smoothing (node embeddings converge). Skip connections + normalization help.
Complexity
Per layer: O(E · d). L layers: O(L · E · d). Scales to millions of nodes with mini-batching.