Graph Neural Networks: An Introduction

A graph is a pair $G = (V, E)$ with node features $X \in \mathbb{R}^{|V| \times d}$, one feature row per node, and edges $E$ encoding pairwise relationships, often stored as an adjacency matrix $A \in \{0,1\}^{|V|\times|V|}$. Unlike image pixels, graph nodes have no canonical ordering and no fixed number of neighbors — node 5 might have 2 neighbors, node 6 might have 200. Any layer we design must therefore be (a) applicable regardless of neighborhood size, and (b) invariant to the arbitrary order in which we list a node's neighbors — this is the permutation-invariance requirement, and it rules out simply concatenating neighbor features or treating the adjacency row like an image patch. The Graph Convolutional Network (GCN) layer, introduced by Kipf and Welling, satisfies both requirements with a strikingly simple update. Let $\hat{A} = A + I$ (adding self-loops so a node includes itself in its own aggregation) and let $\hat{D}$ be the diagonal degree matrix of $\hat{A}$, i.e. $\hat{D}_{ii} = \sum_j \hat{A}_{ij}$. The layer computes

with $H^{(0)} = X$. Here $W^{(l)}$ is a learned weight matrix (shared across all nodes — this weight-sharing is the direct analogue of a convolution filter's shared weights across spatial positions), and $\sigma$ is a nonlinearity such as ReLU. The matrix $\tilde{A} = \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}$ is the symmetric-normalized adjacency; row $i$ of $\tilde{A}H^{(l)}$ is precisely a degree-normalized average of node $i$'s own and neighbors' features. So the GCN layer can be read two equivalent ways: as a first-order Chebyshev approximation to spectral graph convolution (its original derivation), or — more usefully for intuition — as "average your neighbors' features, then apply a shared linear transform and a nonlinearity." This "aggregate, then transform" pattern is the instance, for GCNs, of the general message-passing template covered as a prerequisite concept: each node collects messages from neighbors, aggregates them with a permutation-invariant function (here, weighted sum/average), and updates its own state. GCN's specific contribution is the choice of aggregator — a fixed, symmetric, degree-normalized average, derivable from spectral theory — as opposed to, say, an attention-weighted sum (Graph Attention Networks) or a learned max-aggregator followed by a sampled-neighbor MLP (GraphSAGE). Understanding GCN as one point in this larger design space is essential: it is simple and effective, but its aggregator has no learnable per-edge weighting, which matters for later diagnosing when it underperforms.

Setup. We are given $X \in \mathbb{R}^{|V|\times d_0}$ (node features) and adjacency $A$. We choose a number of layers $L$ and per-layer output dimensions $d_1, \dots, d_L$. For a node classification task, we typically want $L$ small (2–3) since the label of a node depends mostly on its local neighborhood; for whole-graph tasks we may go deeper and add a final pooling/readout layer.

Step 1 — Preprocessing. Compute $\hat{A} = A + I$, then $\hat{D}_{ii} = \sum_j \hat A_{ij}$, then the normalized propagation matrix $\tilde A = \hat D^{-1/2}\hat A \hat D^{-1/2}$. Because $A$ is sparse in essentially every real graph (a social network user does not know all other users), $\hat A$ and $\tilde A$ are stored in sparse format (e.g. coordinate list / CSR), with $O(|E|)$ nonzero entries — this sparsity is what makes the whole pipeline scale.

Step 2 — Layer-wise propagation. For layer $l = 0, \dots, L-1$: compute $Z^{(l)} = \tilde{A}\, H^{(l)}$ (neighborhood aggregation, a sparse matrix–dense matrix product), then $H^{(l+1)} = \sigma(Z^{(l)} W^{(l)} + b^{(l)})$ (feature transform). Dropout and/or batch/layer normalization are commonly inserted between layers to control over-smoothing and overfitting.

Step 3 — Task head.

• Node classification/regression: apply a final linear layer to each row of $H^{(L)}$, i.e. $\hat y_v = \text{softmax}(H^{(L)}_v W_{\text{out}})$, and train with per-node cross-entropy (often only on a labeled subset of nodes — semi-supervised node classification, GCN's flagship setting).
• Link prediction: score an edge $(u,v)$ with a function of $H^{(L)}_u, H^{(L)}_v$ (e.g. dot product or an MLP on the concatenation).
• Graph classification/regression: pool all node embeddings into one graph-level vector, $h_G = \text{READOUT}(\{H^{(L)}_v : v \in V\})$, where READOUT is permutation-invariant (mean, sum, max, or a learned attention pooling), then feed $h_G$ to a classifier.

```

# ---- GCN forward pass (single graph, node classification) ----

# Inputs:

# X : |V| x d0 node feature matrix

# A : |V| x |V| sparse adjacency matrix (0/1)

# W[0..L-1] : learned weight matrices, W[l] has shape d_l x d_{l+1}

# b[0..L-1] : learned bias vectors

# Output:

# Y_hat : |V| x num_classes predicted class distributions function PRECOMPUTE_PROPAGATION(A): A_hat = A + IDENTITY(|V|) # add self-loops D_hat = DIAGONAL(ROW_SUM(A_hat)) # degree matrix of A_hat D_inv_sqrt = DIAGONAL(1 / sqrt(diag(D_hat))) A_tilde = D_inv_sqrt @ A_hat @ D_inv_sqrt # symmetric normalization return A_tilde # sparse, O(|E|) nonzeros function GCN_FORWARD(X, A_tilde, W, b, L, activation=RELU): H = X for l in 0 .. L-1: Z = SPARSE_DENSE_MATMUL(A_tilde, H) # aggregate neighbor features H = Z @ W[l] + b[l] # linear transform if l < L - 1: H = activation(H) # nonlinearity on hidden layers H = DROPOUT(H, p) # regularization Y_hat = SOFTMAX(H, axis=1) # final layer: class distribution return Y_hat function TRAIN(X, A, labels, train_mask, epochs, lr): A_tilde = PRECOMPUTE_PROPAGATION(A) # done once, reused every epoch initialize W, b for epoch in 1 .. epochs: Y_hat = GCN_FORWARD(X, A_tilde, W, b, L) loss = CROSS_ENTROPY(Y_hat[train_mask], labels[train_mask]) grads = BACKPROP(loss, W, b) # standard backprop through

# sparse-dense matmuls W, b = SGD_UPDATE(W, b, grads, lr) return W, b

# ---- Graph-level task: add a readout after the last GCN layer ---- function GRAPH_READOUT(H_final, pool="mean"): if pool == "mean": return MEAN(H_final, axis=0) # |V| x d -> d if pool == "sum": return SUM(H_final, axis=0) if pool == "max": return MAX(H_final, axis=0) ``` Every step above is permutation-invariant in the nodes: relabeling node indices permutes rows of $X$, $H$, and $A$ consistently, and the matrix product $\tilde A H W$ commutes with that permutation. This is precisely why the architecture needs no canonical node ordering, unlike a CNN's implicit pixel grid ordering.

Time complexity. Precomputing $\tilde A$ costs $O(|E|)$: we touch each edge (plus $|V|$ self-loops) a constant number of times to build $\hat A$ and compute degrees. Each layer's forward pass does a sparse–dense matrix product $\tilde A H^{(l)}$, costing $O(|E|\, d_l)$ (one multiply–add per nonzero entry of $\tilde A$, times the feature dimension), followed by a dense–dense product $Z W^{(l)}$ costing $O(|V|\, d_l\, d_{l+1})$. Summed over $L$ layers, total forward cost is

taking $d = \max_l d_l$ as a representative width. Backpropagation has the same asymptotic cost as the forward pass (each matmul's gradient is another matmul of the same shape family). Because real graphs satisfy $|E| = O(|V|)$ (social networks, citation graphs, molecules — all sparse, bounded average degree), this is linear in the number of nodes and edges, not quadratic. This is the essential efficiency argument for using the graph's sparsity structure directly, rather than materializing a dense $|V| \times |V|$ matrix, which would force an unavoidable $O(|V|^2 d)$ cost.

Space complexity. Storing $\tilde A$ sparsely costs $O(|E|)$. Storing all layers' activations for backprop costs $O(L\, |V|\, d)$. Weight matrices cost $O(L d^2)$, independent of graph size — an important property, since it means the same trained GCN can be applied to graphs of different sizes at inference time (this is the graph analogue of a CNN filter's size being independent of image resolution).

Correctness / why the aggregator is principled. The spectral derivation justifies why $\tilde A$ specifically, rather than an arbitrary weighted average, is the right choice. Define the graph Laplacian $L = I - \hat D^{-1/2}\hat A \hat D^{-1/2}$, a symmetric positive semi-definite matrix whose eigendecomposition $L = U\Lambda U^\top$ gives the graph Fourier basis $U$. A spectral graph convolution filters a signal $x$ by $g_\theta(L)x = U g_\theta(\Lambda) U^\top x$ for some learnable spectral filter $g_\theta$. This is $O(|V|^2)$ or worse (eigendecomposition is $O(|V|^3)$) if computed directly — computationally infeasible for large graphs. Approximating $g_\theta(\Lambda)$ by a degree-$K$ Chebyshev polynomial in $\Lambda$ turns $g_\theta(L)x$ into a sum of $K$ local sparse matrix–vector products (Chebyshev / ChebNet), avoiding the eigendecomposition entirely. GCN takes $K=1$ (a first-order truncation) and further ties parameters across the two resulting terms, collapsing the whole filter to a single application of $\tilde A$ — this is exactly the propagation rule above. So the GCN layer is not an ad hoc averaging trick; it is the cheapest nontrivial term of a principled spectral filter, made tractable by never actually diagonalizing $L$.

Why self-loops and normalization matter. Without the $+I$ self-loop term, a node's own previous-layer features would be discarded at each update, which empirically and theoretically degrades performance (a node's own information is usually the single most predictive signal). Without the symmetric $\hat D^{-1/2}(\cdot)\hat D^{-1/2}$ normalization (versus, say, simple row-normalization $\hat D^{-1}\hat A$), high-degree "hub" nodes would dominate feature magnitudes; the symmetric normalization keeps $\tilde A$ symmetric, which preserves the connection to the (symmetric) graph Laplacian used in the spectral derivation, and empirically stabilizes training.

Tradeoff — over-smoothing. Repeated multiplication by $\tilde A$ is a form of Laplacian smoothing: as $L \to \infty$, $\tilde A^L H^{(0)}$ converges (subject to connectivity conditions) toward a distribution proportional to node degree, regardless of the original node features — every node's representation collapses toward the same vector. This is why GCNs are typically shallow (2–4 layers): depth buys larger receptive field but linearly trades off against representational collapse, an intrinsic and well-documented limitation, not a training bug.

Consider a tiny 4-node graph — a "triangle plus pendant" — with edges $\{(1,2), (2,3), (1,3), (3,4)\}$, i.e. nodes 1, 2, 3 form a triangle and node 4 hangs off node 3. Suppose 1-dimensional node features (say, a single scalar "activity score"):

Step 1: build $\hat A = A + I$.

Step 2: degrees of $\hat A$ (row sums): $\hat D = \text{diag}(3, 3, 4, 2)$.

Step 3: normalized propagation matrix $\tilde A = \hat D^{-1/2}\hat A \hat D^{-1/2}$. Using $\hat D^{-1/2} = \text{diag}(1/\sqrt3, 1/\sqrt3, 1/2, 1/\sqrt2)$:

Step 4: one layer of propagation, no transform yet (i.e. compute $Z = \tilde A X$, taking $W = I$, $\sigma = \text{identity}$ for clarity):

So $Z \approx [1.00,\ 1.00,\ 2.28,\ 2.00]^\top$. Notice the effect: node 3 (the bridge/hub, degree 4 including self-loop) absorbs a blended signal from the triangle and the pendant, becoming an intermediate value between them; nodes 1 and 2 converge toward the same value since they are symmetric in the graph (same neighbors); node 4's value shrinks from 4.0 toward 2.0 because it is pulled toward its only neighbor, node 3's original value of 0. This one-layer averaging is exactly the "smoothing along edges" behavior that, iterated too many times, causes over-smoothing — here after one layer it is a feature (local context injected), and this is the phenomenon to watch as $L$ grows.

Step 5: apply learned $W^{(0)}\in\mathbb{R}^{1\times2}$, bias, and ReLU to get $H^{(1)} \in \mathbb{R}^{4\times2}$, then repeat for a second layer to reach 2-hop context, then a final linear + softmax layer for node classification (e.g., "is this node an anomaly?").

The path to GCNs runs through spectral graph theory, then convolutional networks, then their fusion. Bruna, Zaremba, Szlam, and LeCun (2014) first proposed convolutions on graphs via the graph Laplacian's eigenbasis — theoretically elegant, but computationally expensive due to the required eigendecomposition. Defferrard, Bresson, and Vandergheynst (2016) introduced ChebNet, replacing the exact spectral filter with a truncated Chebyshev polynomial expansion, making the operation local and $O(|E|)$-scalable — this is the direct ancestor of the GCN layer. Thomas Kipf and Max Welling (2017) simplified ChebNet to first order, producing the now-canonical GCN propagation rule and demonstrating strong results on semi-supervised node classification with remarkably few labeled nodes, catalyzing the modern GNN research explosion. In parallel, the message-passing perspective was crystallized by Gilmer et al. (2017) with the Message Passing Neural Network (MPNN) framework for molecular property prediction, unifying GCN, GraphSAGE (Hamilton, Ying, Leskovec, 2017), and Graph Attention Networks (Veličković et al., 2018) as instances of a common aggregate-then-update template.

GCN-style layers and their message-passing generalizations underpin production systems across many domains. Recommendation engines (e.g., large-scale systems inspired by PinSAGE, built on GraphSAGE) use GNNs over user–item interaction graphs to generate embeddings for candidate retrieval and ranking. Drug discovery and computational chemistry pipelines represent molecules as graphs of atoms and bonds, applying GNNs to predict properties like solubility, toxicity, and binding affinity — a use case central to Gilmer et al.'s original MPNN framing and to later systems like AlphaFold's use of graph-structured representations for protein modeling. Fraud and anomaly detection systems in finance model transactions as graphs (accounts as nodes, transfers as edges) and use GNNs to flag suspicious subgraphs via node/edge classification. Knowledge-graph completion and question-answering systems use GNN-style propagation to reason over entities and relations for link prediction. Traffic forecasting systems model road networks as graphs and use spatio-temporal GNNs (GCN layers combined with recurrent or temporal-convolution components) to predict congestion. In all these cases, the underlying justification is the same: whenever the natural relational structure of data is graph-shaped rather than grid- or sequence-shaped, message-passing/GCN-style layers provide the principled way to share learned representations across variably-connected entities, building directly on Message Passing on Graphs as the general computational template.

Ask the tutor: How would you modify the GCN propagation rule to make it inductive, so it generalizes to entirely new, unseen graphs at test time?