Graph Neural Networks: From Message Passing to PinSage

Images are grids. Text is sequences. Recommendation systems are graphs — users, items, and interactions forming a web of relationships that no grid or sequence model can capture. Graph Neural Networks process this structure directly. PinSage took the core idea to 3 billion nodes and 18 billion edges at Pinterest. This is how message passing works and why it scales.

Convolutional networks work because images are regular grids: every pixel has the same number of neighbours in the same spatial arrangement. The same filter, applied uniformly, extracts the same pattern at every position. This regularity is the precondition for convolution.

Real-world data is often not a grid. A social network has users with varying numbers of friends. A knowledge graph has entities with different numbers of relationships. A recommendation system has users connected to items they interacted with, items connected to users who bought them. The structure is irregular, and the structure carries information. Graph Neural Networks learn by passing messages along edges — aggregating information from neighbours, iteratively, to produce embeddings that encode both node features and graph topology.

The message passing framework

A GNN operates in rounds. In each round, every node collects representations from its neighbours, aggregates them (by summing, averaging, or learned combination), and uses the result to update its own representation. After k rounds, a node's representation encodes information from all nodes within k hops.

Formally, for node v at round t: h_v^(t+1) = UPDATE(h_v^(t), AGGREGATE({ h_u^(t) : u in N(v) })). The choice of AGGREGATE and UPDATE defines the GNN variant. Mean aggregation plus a linear transform plus ReLU is Graph Convolutional Network (GCN). Max aggregation with a learned aggregator is GraphSAGE. Attention-weighted aggregation is Graph Attention Network (GAT).

Graph Convolutional Network: the spectral view

GCN (Kipf & Welling, 2017) derives from spectral graph theory. The core operation is: H^(l+1) = σ(D^(-1/2) A_hat D^(-1/2) H^(l) W^(l)), where A_hat is the adjacency matrix plus self-loops, D is the degree matrix, H is the node feature matrix, and W is the learned weight. The degree normalisation ensures that high-degree nodes do not dominate — without it, a node with 1000 neighbours aggregates 1000 raw vectors; after normalisation it aggregates their mean.

The limitation: GCN requires the full graph adjacency matrix in memory. For a million-node graph, the adjacency matrix alone is terabytes. GCN does not scale directly.

GraphSAGE: mini-batch training by neighbourhood sampling

GraphSAGE (Hamilton et al., 2017) solves scalability with a simple idea: instead of aggregating over all neighbours, sample a fixed-size subset. For a node with 500 neighbours, sample 25. The aggregation runs on those 25. This makes mini-batch training possible. To compute the embedding of a node, you need its sampled neighbourhood at hop 1, and for each of those their sampled neighbourhood at hop 2. The full computation tree for a k-hop embedding has at most S^k nodes where S is the sample size — independently computable for each training example.

GraphSAGE also introduced the inductive setting: the aggregation function is learned on a training graph and applied to unseen nodes at inference time. This is a requirement for any production recommendation system where new users and items arrive daily.

PinSage: GraphSAGE at Pinterest scale

Pinterest deployed GraphSAGE as PinSage (Ying et al., 2018) on a graph of 3 billion pins, 18 billion edges (user–pin interactions), and 2 billion users. Three problems had to be solved that do not arise at research scale.

Random walk-based neighbourhood sampling. Instead of uniform random sampling, PinSage used random walks to define importance-weighted neighbourhoods. The importance of node u to node v is the visiting frequency of random walks starting at v that land on u. High-importance neighbours contribute more to the aggregation. This produces more informative embeddings than uniform sampling, especially for high-degree nodes where most connections are weak.

On-the-fly feature computation. Pinterest pins have rich visual and text features — image embeddings from a CNN, text embeddings from title and description. Storing full feature matrices for 3B nodes is infeasible. PinSage computed node features on the fly during mini-batch construction, caching only recently used embeddings.

Curriculum training with hard negatives. Easy negatives — items completely unrelated to the query — give the model almost no signal once it has learned the basics. PinSage used curriculum learning: start with random negatives, then gradually increase difficulty by selecting items the model currently ranks highly but the user did not interact with. Hard negatives force fine-grained distinction rather than coarse separation.

The result: 150% lift in engagement on downstream recommendation tasks compared to the prior collaborative filtering baseline, at a graph scale no prior GNN method had approached.

Why graph structure matters for recommendations

A user-item interaction graph encodes collaborative filtering signal directly. Items that many users co-interact with should have similar embeddings; users with similar interaction patterns should be embedded nearby. GNNs learn this from topology, without hand-engineering similarity metrics.

Beyond first-order connections, graph structure encodes higher-order relationships. If user A interacts with items X and Y, and user B interacts with items Y and Z, then X and Z are second-order related — they share a user neighbourhood. A 2-hop GNN embeds this relationship. Factorisation methods cannot represent it without explicit feature engineering.

Try on Colab: implement a 2-layer GCN in PyTorch Geometric on the Cora citation dataset (2708 nodes, 5429 edges, 7 classes). Measure test accuracy at 1 hop vs 2 hops vs 3 hops — watch it peak then degrade (over-smoothing). Then swap the mean aggregator for a max aggregator. The difference in accuracy is small on Cora but the exercise makes aggregation choices concrete and reproducible.