Graph neural networks for recommendation

A recommender is not a table that happens to have a graph hiding inside it — it is a graph. The user–item interaction matrix is literally a bipartite graph, and classical collaborative filtering is just the shallowest, 1-hop reading of it. GNNs are what you get when you stop pretending otherwise and let signal flow across the edges you already have.

The recommender was a graph all along

Take the user–item interaction matrix R — rows are users, columns are items, an entry is "this user clicked / watched / bought this item." Rotate your eyes: that matrix is the adjacency matrix of a bipartite graph. Users on one side, items on the other, an edge wherever an interaction happened. Nothing was added; the matrix and the graph are the same object in two notations.

Once you see the graph, the classical methods reveal themselves as special cases. Matrix factorization learns a vector e_u per user and e_i per item so that e_u · e_i reconstructs the edge — but it only ever looks at the direct edge between u and i. It is a 1-hop, transductive model: it knows who you clicked, and nothing about who the people who clicked the same things clicked next.

That is the starvation problem. A sparse interaction matrix gives a flat model almost no direct edges per node — long-tail items have a handful of clicks, new users have one. The signal a 1-hop model needs simply is not in its receptive field. A GNN widens that receptive field by propagating embeddings over multi-hop neighborhoods, so a node's representation is built from its neighbors, its neighbors' neighbors, and so on. That multi-hop reach is precisely the signal collaborative filtering throws away.

Message passing — the one primitive that runs everything

Every GNN, under the branding, is the same loop: each node builds a new representation by aggregating messages from its neighbors, then updating itself with that aggregate. Repeat K times and information has flowed K hops. The general layer equation:

h_v^(k) = UPDATE( h_v^(k−1), AGG( { h_u^(k−1) : u ∈ N(v) } ) )

Read it slowly. h_v^(k) is node v's embedding after k layers. N(v) is its neighbors. AGG is a permutation-invariant pool (mean, sum, max, or attention) — it must not care about neighbor ordering, because a set of neighbors has none. UPDATE combines the old self-embedding with the pooled neighbor message (a concatenation through a weight matrix, a gated sum, or — as we will see — nothing at all).

The depth k is the hop count, and the receptive field grows combinatorially with it: layer 1 sees direct neighbors, layer 2 sees neighbors-of-neighbors, and on a bipartite graph that alternation is what lets a user embedding absorb information from other users who share its items:

That u → i → u' → i' path is the entire intuition of collaborative filtering, made explicit as graph propagation. A 1-hop model can never traverse it; a 3-hop GNN bakes it directly into the embedding.

GraphSAGE — sample, aggregate, and stay inductive

The first thing that breaks at scale: you cannot aggregate over a node's entire neighborhood when a popular item has ten million neighbors. GraphSAGE's answer is to sample a fixed-size neighbor set at each hop (say 25 at hop 1, 10 at hop 2) and aggregate over the sample. The layer, concretely with a mean aggregator:

h_v^(k) = σ( W · CONCAT( h_v^(k−1), mean_{u ∈ S(v)} h_u^(k−1) ) )

where S(v) is a fixed-size sample of N(v). The aggregator can be mean, an LSTM (order-sensitive, so neighbors are shuffled), or max/mean pool (each neighbor passed through a small MLP, then pooled). The deeper point is in the word inductive.

Matrix factorization is transductive: it learns one fixed embedding per node ID. A node that did not exist at training time has no row in the embedding table — you must retrain to give it one. GraphSAGE instead learns the aggregator weights W, not the per-node vectors. To embed a brand-new node you feed its features and its sampled neighbors through the learned aggregators — no retraining, no new parameters. That is the bridge straight to 15 · Cold start: an inductive GNN can embed an item the instant it is uploaded, as long as it has features and at least a few edges.

PinSage — GraphSAGE at three billion nodes

PinSage is GraphSAGE taken to Pinterest production: a graph of pins and boards with roughly 3 billion nodes and 18 billion edges. At that scale even sampling a fixed neighbor count uniformly is wrong, because uniform sampling on a power-law graph mostly returns noise. Three engineering moves make it work:

• Random-walk neighborhoods. Instead of "the neighbors," define a node's neighborhood as the nodes most frequently visited by short random walks starting at it. This captures the important neighbors — strongly connected, multi-path — rather than a uniform sample, and it gives a principled, bounded set on a graph where degree varies by orders of magnitude.
• Importance pooling. Weight each neighbor in the aggregation by its random-walk visit count (an L1-normalized importance score), so the pool is a weighted mean. A neighbor reached by many walks contributes more than one reached by a fluke — attention learned from graph structure, essentially for free.
• MapReduce / producer-consumer serving. Embeddings for all 3B nodes are computed offline in a single giant batched pass that avoids recomputing shared neighborhoods, then stored. Online, you do an ANN lookup — never a live multi-hop traversal.

And the training detail interviewers love: curriculum with hard negatives. Easy negatives (a random pin) teach the model almost nothing once it is competent. PinSage starts with random negatives, then progressively mixes in hard negatives — items that are somewhat related to the query (high PageRank-ish proximity but not the true positive) — so the model is forced to learn fine distinctions. Increase negative difficulty by epoch; that is the curriculum.

LightGCN — the radical subtraction

Here is the result that surprises people. GNNs imported a lot of deep-learning machinery — feature transformation matrices W, nonlinearities σ, self-connections. LightGCN's authors ablated all of it for the collaborative filtering setting and found that the feature transform and the nonlinearity actively hurt. In pure CF the only input is a one-hot node ID — there are no rich node features for a W to transform — so the transform just adds parameters that overfit, and the nonlinearity discards useful linear structure.

So LightGCN keeps only neighborhood aggregation, and makes it purely linear. The propagation rule, symmetrically normalized:

e_u^(k+1) = Σ_{i ∈ N(u)} ( 1 / √( |N(u)| · |N(i)| ) ) · e_i^(k)

No W, no σ, no self-loop inside the layer — just a normalized sum of neighbor embeddings. The 1/√(|N(u)||N(i)|) term is the standard symmetric normalization: it down-weights edges to high-degree (popular) nodes so a hub does not drown out the signal. Items aggregate from users by the mirror-image rule.

Then the second idea: instead of using only the last layer, the final embedding is a weighted sum of every layer's output, including layer 0:

e_u = Σ_k=0..K α_k · e_u^(k) (typically α_k = 1/(K+1))

This layer combination is what tames over-smoothing (next section): keeping e_u⁽⁰⁾ in the mix preserves the node's own identity, while the deeper layers add high-order signal. The recommendation score is the same old dot product e_u · e_i — so at serving, LightGCN is a two-tower / embedding model, and everything you know from 03 · Embeddings & ANN applies directly. The GNN is only how the embeddings were trained.

Why GNNs beat plain CF — and where they break

The win is high-order connectivity. A 1-hop model scores a cold node from almost nothing — one edge, maybe none. A multi-hop GNN lets that node borrow signal from its multi-hop neighbors: a long-tail item with three clicks inherits structure from the users who made those clicks and the other items those users engaged with. The sparser the node, the more it gains, because the multi-hop reach is doing the work the missing direct edges cannot. This is the same cold-start logic as lesson 15, expressed structurally instead of through content.

The failure mode is over-smoothing, and it is the flip side of the same mechanism. Each aggregation hop mixes a node's representation with its neighbors'. Do it too many times and every node's embedding converges toward the same average — the graph's stationary distribution. After enough hops you cannot tell two nodes apart, and the embeddings become useless for ranking.

as K → ∞ : h_v^(K) → c · (degree-weighted global mean) ∀ v (everything collapses to one point)

This is why GNN depth is capped low in practice — typically 2 to 4 hops. Past that, over-smoothing erases more identity than the extra hops add. LightGCN's layer-combination (keeping e⁽⁰⁾) and residual/jumping-knowledge connections are the standard defenses, but the blunt truth is: depth is a hyperparameter you tune down, not up. A GNN is not a CNN; more layers is not more capacity, it is more blur.

Interactive · how far does a cold node's evidence reach?

A tiny bipartite graph: users u1…u4, items i1…i4. We focus on cold user u3, who has touched only one item. Slide the hop count and watch how many nodes enter u3's receptive field — its "evidence set" — and how the embedding behaves. At 0 hops u3 is just its own (near-empty) ID. A couple of hops pull in collaborative signal. Crank it too high and the over-smoothing readout fires: every node's embedding has converged to the same blur.

When is a GNN actually worth it?

GNNs are not free — they add a graph-construction step, a sampling pipeline, an offline embedding job, and a refresh cadence to your stack. The honest answer to "should we build one?":

The principle in one sentence: a GNN is worth it exactly when the edges encode information the node features alone do not, and you can afford to amortize the graph computation offline. If a two-tower model with good content features already captures the signal, the GNN buys you complexity, not accuracy. The interviewer is testing whether you reach for the heavy tool reflexively or because the structure demands it.

Interview prompts you should be ready for