Graph Neural Network: Theory, Practice, and Beyond

Learning Graphs

A graph $G = (V, E)$ with $n = \vert V \vert$ nodes is described by an adjacency matrix $\mathbf{A} \in \lbrace 0, 1 \rbrace^{n \times n}$ (or weighted $\mathbf{A} \in \mathbb{R}^{n \times n}$) and node features $\mathbf{X} \in \mathbb{R}^{n \times d}$. Define the degree matrix $\mathbf{D} = \text{diag} (\mathbf{A} \mathbf{1})$, the graph Laplacian $\mathbf{L} = \mathbf{D} - \mathbf{A}$, and its normalized version $\tilde{\mathbf{L}} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$.

The fundamental structural constraint is that node indexing is arbitrary: for any permutation matrix $\mathbf{P}$, the pair $(\mathbf{P} \mathbf{A} \mathbf{P}^T, \mathbf{P} \mathbf{X})$ represents the same graph. A graph-level function must therefore be permutation invariant:

while a node-level function must be permutation equivariant:

These two symmetry requirements play the same role for graphs as translation equivariance plays for CNNs, and essentially dictate the message-passing architecture below.

Embedding

An embedding is a map from a discrete object (node, edge, graph) to a vector space, such that structural similarity becomes geometric proximity.

Node Embedding

• Spectral methods (Laplacian eigenmaps) [Belkin et al. 2003]: embed nodes with the eigenvectors of the $k$ smallest nonzero eigenvalues of $\tilde{\mathbf{L}}$, minimizing $\sum_{(u,v) \in E} \vert\vert \mathbf{z}_u - \mathbf{z}_v \vert\vert^2$ subject to orthogonality.

• Random-walk methods: DeepWalk [Perozzi et al. 2014] and node2vec [Grover et al. 2016] run (biased) random walks and train a skip-gram objective, so that nodes co-occurring in walks obtain similar embeddings:

• GNN encoders: embeddings produced by message passing (see below), which unlike the shallow methods above are inductive — they generalize to unseen nodes/graphs because parameters are shared across nodes rather than stored per node.

Edge Embedding

Edge representations are usually built from the incident node embeddings: $\mathbf{z}{(u,v)} = \phi (\mathbf{z}_u, \mathbf{z}_v)$, where $\phi$ is symmetric for undirected graphs, e.g., Hadamard product $\mathbf{z}_u \odot \mathbf{z}_v$, average, or $\vert \mathbf{z}_u - \mathbf{z}_v \vert$ [Grover et al. 2016]. Some architectures maintain explicit edge features $\mathbf{e}{uv}$ updated alongside node features (e.g., MPNN [Gilmer et al. 2017]).

Graph Embedding

A graph-level representation is obtained by a permutation-invariant readout over node embeddings:

possibly hierarchically via differentiable pooling (DiffPool [Ying et al. 2018]). The classical alternative is graph kernels, notably the Weisfeiler-Lehman (WL) subtree kernel [Shervashidze et al. 2011], which iteratively hashes neighborhood labels — the same computation pattern that upper-bounds GNN expressiveness (see GIN below).

Classification

Node Classification

Semi-supervised setting: given labels on a subset $V_L \subseteq V$, predict the rest, with loss $\sum_{v \in V_L} \text{CE} (y_v, \text{softmax} (\mathbf{z}_v \mathbf{W}))$. The graph structure acts as a regularizer, implementing the homophily assumption that connected nodes tend to share labels. On heterophilic graphs this assumption fails and standard GNNs can underperform an MLP [Zhu et al. 2020].

Edge Classification

Link prediction: score a candidate edge by $s (u, v) = \sigma (\mathbf{z}u^T \mathbf{z}_v)$ (or an MLP on $\mathbf{z}{(u,v)}$), trained with negative sampling on non-edges. Used for knowledge-graph completion and recommendation.

Graph Classification

Predict a label per graph from $\mathbf{z}_G$ (molecule property prediction, protein function, etc.). Benchmarks: OGB [Hu et al. 2020].

Graph Neural Network (GNN)

The message-passing framework [Gilmer et al. 2017] unifies most architectures. At layer $k$:

where AGG is permutation invariant over the multiset of neighbors, which guarantees the equivariance of the whole network. Instances:

• GCN [Kipf et al. 2017]: symmetric-normalized mean aggregation,

• GraphSAGE [Hamilton et al. 2017]: sampled-neighborhood aggregation for scalability, $\mathbf{h}_v^{(k+1)} = \sigma (\mathbf{W} \cdot [\mathbf{h}_v^{(k)} \Vert \text{AGG} (\lbrace \mathbf{h}_u^{(k)} \rbrace)])$.

• GAT [Velickovic et al. 2018]: attention-weighted aggregation,

• GIN [Xu et al. 2019]: sum aggregation with MLP update, $\mathbf{h}v^{(k+1)} = \text{MLP} ((1 + \epsilon) \mathbf{h}_v^{(k)} + \sum{u \in \mathcal{N}(v)} \mathbf{h}_u^{(k)})$. GIN is as expressive as the 1-WL test, and no standard message-passing GNN is more expressive — e.g., they cannot distinguish certain non-isomorphic regular graphs.

Two practical pathologies: oversmoothing — stacking many layers drives all node representations to a common value, since each aggregation step is (roughly) one step of diffusion along the graph [Li et al. 2018, Oono et al. 2020]; and oversquashing — information from exponentially many distant nodes is compressed through bottleneck edges [Alon et al. 2021].

Interactive illustration: message passing and oversmoothing

Each node carries a scalar feature (color: blue = -1, red = +1), initialized by community. Click “One step” to apply one round of mean aggregation $\mathbf{h}v \leftarrow \frac{1}{\vert \mathcal{N}(v) \cup \lbrace v \rbrace \vert} \sum{u \in \mathcal{N}(v) \cup \lbrace v \rbrace} \mathbf{h}_u$. A few steps mix information along edges (useful); many steps wash all features to the global mean (oversmoothing).

Beyond Message Passing

Higher-order GNNs based on $k$-WL [Morris et al. 2019], subgraph-based models, and graph transformers with structural encodings [Rampasek et al. 2022] trade scalability for expressiveness. On the efficiency side, graph condensation compresses the training graph itself — gradient matching [Jin et al. 2022] and distribution matching [Liu et al. 2022] both transfer directly from the image setting; see the GNN section of my dataset condensation post.