Graph-based recommendations

The big idea

The user-item matrix is also a graph. Every user and every item is a node, and every click, save or purchase is an edge between them. On a site where people save items to collections (boards, playlists, wishlists), the collections are nodes too. Matrix factorization looks at one edge at a time. A graph view can also follow paths: this item was saved to a board, that board holds these other items, which were saved to other boards, and so on.

You already use this idea about people: you can tell a lot about someone from the company they keep, and more from their friends' friends. Graph methods describe an item by its neighbourhood. That helps most when the item's own features are weak (a photo with no caption) and when the graph knows something the features cannot, such as the fact that thousands of people put this lamp and that rug in the same collection.

There are two families. Random-walk methodsRecommending by simulating short random walks over the interaction graph from a query node and ranking other nodes by how often the walks visit them. score items by how often short walks from the query reach them. Graph neural networksA neural network whose layers update each node's vector by combining it with an aggregate of its neighbours' vectors, so stacked layers mix in information from several hops away. GNN for short. (GNNs) learn an embedding for every node by mixing in its neighbours' features. Sampling neighbourhoods with random walks is what makes GNNs feasible on graphs with billions of nodes.

How it works

Step 1: Walks over the graph

Counting visits over many short walks gives every item a score relative to the query. In the limit of infinitely many walks, the normalized counts approach the personalized PageRankA PageRank variant where the random surfer keeps jumping back to one start node, so scores measure how close every node is to that node in the graph. scores of the query node, as the PinSage paper notes. Random walks are simple, need no training, and handle any graph. Their limits: an item with few edges gets a noisy score, a brand-new item with no edges gets none, and the result is a list of scores, not a vector you can store in an index.

Step 2: A graph neural network layer

A GNN layer gives each node a new vector built from its own vector and its neighbours'. The layer used in PinSage, the Pinterest system in the case study below, does four things for a node $u$ with neighbours $N(u)$:

1. Pass each neighbour's vector $h_v$ through a small dense layer.
2. Pool them into one neighbourhood vector $n_u$ (a mean, or a weighted mean).
3. Concatenate $n_u$ with $u$'s own vector and pass it through another dense layer: $h_u^{\prime }=\text{ReLU}(W[h_u;n_u]+b)$.
4. Normalize $h_u^{\prime }$ to unit length, which the paper reports makes training more stable and nearest-neighbour search more efficient.

Stack two layers and each node sees its neighbours' neighbours. The key property is that the weights are shared by every node. The model's size does not grow with the graph, and it is inductiveAble to produce outputs for nodes that were not in the training graph, because the model is a function of features and neighbourhoods rather than a lookup table of per-node vectors.: a pin added this morning gets an embedding as soon as it has features and a few edges. Contrast this with methods such as DeepWalk and node2vec, which learn a free vector per node: the PinSage authors rule them out because their parameter count grows linearly with the graph and they cannot use node features.

Training works like the two-tower models of Two-tower retrieval and embedding-based retrieval . Take pairs of items that users engaged with one after the other as positives, sample negatives, and train the embeddings so a positive pair's dot product beats the negatives' by a margin. Serving is the same too: compute every item's embedding offline and look up nearest neighbours.

Step 3: Sampling makes it scale

The textbook graph convolution multiplies by the whole graph's adjacency matrix, which is impossible for billions of nodes, and a popular item's full two-hop neighbourhood can be millions of nodes. GraphSAGE (Hamilton, Ying and Leskovec, 2017) introduced sampling a fixed number of neighbours per node. PinSage went further and used random walks to choose the neighbours:

• Importance-based neighbourhoods. Run short random walks from $u$ and keep the $T$ nodes with the highest normalized visit counts. That fixes the memory per node, and skips nodes that are adjacent but barely related.
• Importance pooling. Use those visit counts as the weights of the weighted mean in step 2. The paper reports a 46 percent gain in offline metrics from this alone.
• Computation graphs on the fly. For each minibatch, CPU workers sample the neighbourhoods and gather features, and the GPUs only see the small subgraph they need.

Going deeper

Code: walks, plain pooling and importance pooling

import numpy as np

# A pin-board style bipartite graph: 2,000 items in 20 topics, 600 boards of 15 items each,
# 12 from the board's topic and 3 at random. Item features are only a weak hint of the topic.
rng = np.random.default_rng(0)
I, B, K, F = 2000, 600, 20, 16
topic = rng.integers(0, K, I)
x = 0.35 * rng.normal(0, 1, (K, F))[topic] + rng.normal(0, 1, (I, F))
boards = [np.r_[rng.choice(np.flatnonzero(topic == t), 12, replace=False), rng.choice(I, 3, replace=False)]
          for t in rng.integers(0, K, B)]
item_boards = [[] for _ in range(I)]
for b, items in enumerate(boards):
    for i in items: item_boards[i].append(b)

def walk_counts(q, n_walks=100, hops=3):                      # item -> board -> item, n_walks times
    counts = np.zeros(I)
    for _ in range(n_walks):
        i = q
        for _ in range(hops):
            if not item_boards[i]: break
            bd = item_boards[i][rng.integers(len(item_boards[i]))]
            i = boards[bd][rng.integers(15)]
            counts[i] += 1
    counts[q] = 0
    return counts / max(counts.sum(), 1)                     # L1-normalized visit counts

unit = lambda v: v / np.linalg.norm(v, axis=-1, keepdims=True)
Wc = np.array([walk_counts(i) for i in range(I)])            # visit counts from every item
T = 50                                                        # neighbours kept per item
mean_nb, imp_nb = np.zeros_like(x), np.zeros_like(x)
for i in range(I):
    if Wc[i].sum() == 0: continue                             # no board: features only
    mean_nb[i] = x[Wc[i] > 0].mean(0)                         # plain mean of every item a walk reached
    top = np.argsort(-Wc[i])[:T]                              # importance pooling: top T, weighted
    imp_nb[i] = Wc[i, top] @ x[top] / Wc[i, top].sum()
layer = lambda nb: unit(np.c_[unit(x), nb / (np.linalg.norm(nb, axis=1, keepdims=True) + 1e-9)])  # concat, normalize

queries = rng.choice(I, 300, replace=False)
def precision(S):                                             # share of the top 10 in the query's topic
    return np.mean([np.mean(topic[[j for j in np.argsort(-S[q]) if j != q][:10]] == topic[q]) for q in queries])
print(f"edges {sum(map(len, boards))}, items on no board {sum(not b for b in item_boards)}")
print(f"content features only        precision@10 {precision(unit(x) @ unit(x).T):.3f}")
print(f"random-walk visit counts     precision@10 {precision(Wc):.3f}")
for name, nb in [("graph layer, mean of all", mean_nb), ("graph layer, importance", imp_nb)]:
    e = layer(nb)
    print(f"{name:28s} precision@10 {precision(e @ e.T):.3f}")
queries = np.array([i for i in range(I) if len(item_boards[i]) == 1])   # items saved to a single board
print(f"{len(queries)} items on one board: walks {precision(Wc):.3f}, importance layer {precision(e @ e.T):.3f}")

edges 9000, items on no board 21
content features only        precision@10 0.135
random-walk visit counts     precision@10 0.743
graph layer, mean of all     precision@10 0.712
graph layer, importance      precision@10 0.809
99 items on one board: walks 0.600, importance layer 0.660

2,000 items in 20 topics and 600 boards of 15 items, 12 from the board's topic and 3 at random: 9,000 edges. Item features are mostly noise with a weak topic signal. From every item the code runs 100 three-hop walks, then builds one untrained graph layer: the item's own features concatenated with a pooled neighbour vector, normalized. Quality is precision@10: the share of an item's 10 nearest items that are in its topic (random guessing gives 0.05).

• Features alone reach only 0.135.
• Random-walk visit counts reach 0.743: the graph knows far more than the features.
• A plain mean over every item the walks reached gives 0.712. Many of those items were visited once, through the random off-topic saves, and they dilute the mean.
• Importance pooling over the top 50 by visit count, weighted by the counts, reaches 0.809, better than either source alone.
• For the 99 items saved to only one board, walks give 0.600 and the importance layer 0.660: when the graph is thin, the item's own features help.

This layer has no trained weights at all. A real GNN learns the dense layers, which lets it decide how much to trust features against neighbours.

Hard negatives from the graph

Random negatives are too easy when the catalogue has billions of items. PinSage takes hard negatives from the graph itself: items ranked 2,000 to 5,000 by personalized PageRank from the query, related but not as related as the positive. Training on them from the start doubled the epochs needed to converge, so it uses a curriculum: no hard negatives in the first epoch, then one more per item in each later epoch. The paper reports a 12 percent gain from the curriculum.

Trade-offs

Common mistakes

• Pooling over every neighbour of a popular node. Hubs blow up memory and drown the signal; sample a fixed number, ideally by importance.
• Evaluating on edges that were also in the graph used to build neighbourhoods, so the model "finds" the answer through the test edge itself.
• Learning a free embedding per node and calling it a GNN: it cannot embed new items and grows with the graph.
• Stacking many layers. Each layer averages over a wider area, so with too many, nodes' vectors start to look alike and the cost of each neighbourhood grows fast. PinSage used two.
• Training only on random negatives, so the model separates kitchens from cars but not good kitchens from merely related ones.

In the wild

Check yourself

Recap