Interview: Message Passing

Message: $\mathbf{m}_{ij} = \phi(\mathbf{h}_i, \mathbf{h}_j, \mathbf{e}_{ij})$. Aggregate: $\bar{\mathbf{m}}_i = \bigoplus_{j\in\mathcal{N}(i)} \mathbf{m}_{ij}$ (sum/mean/max). Update: $\mathbf{h}_i' = \gamma(\mathbf{h}_i, \bar{\mathbf{m}}_i)$. All GNNs are special cases of this framework.

$f(\mathbf{P}\mathbf{A}\mathbf{P}^T, \mathbf{P}\mathbf{X}) = \mathbf{P}f(\mathbf{A}, \mathbf{X})$. Reordering node IDs reorders outputs the same way. GNN layers must satisfy this - node identity should not depend on arbitrary indexing.

$g(\mathbf{P}\mathbf{A}\mathbf{P}^T, \mathbf{P}\mathbf{X}) = g(\mathbf{A}, \mathbf{X})$. Graph-level predictions must not change when nodes are relabeled. Achieved by symmetric readout (sum, mean, max over nodes).

Neighbors have no canonical order. Summing, averaging, or max-pooling over neighbors gives the same result regardless of neighbor ordering. LSTM aggregator over neighbors is common but technically order-dependent (random permutations used in practice).

A permutation-invariant function mapping all node embeddings $\{\mathbf{h}_i\}$ to a single graph embedding $\mathbf{h}_G$ for graph classification/regression. Examples: sum, mean, max, attention pooling, Jumping Knowledge.

$\mathbf{A}\mathbf{H}$ aggregates neighbor features in one step - each row $i$ sums (or averages) features of neighbors. GCN adds normalization and learnable $\mathbf{W}$: $\tilde{\mathbf{A}}\mathbf{H}\mathbf{W}$.

Disjoint union: concatenate all nodes and edges, offset edge indices, add a batch vector indicating graph membership per node. PyG DataLoader handles this automatically.

Injective means different multisets of neighbor features produce different outputs. Sum + universal MLP (GIN) is injective. Mean is not - different counts with same mean collapse.