Pinterest PinSage / Pixie (Related Pins)

01 · CONTEXT

Recommending from a graph of pins and boards

At Pinterest, people organize pins into boards, which gather related pins by theme. PinSage and Pixie treat this environment as a bipartite graph of pins and boards.

At the reported scales, PinSage's graph has 3 billion nodes and 18 billion edges; Pixie's, already pruned, has 3 billion nodes and 17 billion edges.

Pixie traverses the graph with random walks to recommend on demand. PinSage learns pin embeddings with a graph convolutional network, a problem of ML system design. According to the PinSage paper, Pixie's method does not generate pin embeddings and was, at the time, the state of the art at Pinterest for certain tasks.

02 · PIXIE IN REAL TIME

Pixie: on-demand random walks

Pixie stems from a latency requirement: the paper defines real time as under 100 milliseconds per request. If the computation were too slow for the user to wait, recommendations for all users would have to be precomputed and materialized.

1. The Hadoop pipeline gathers the edges between boards and pins and sends the raw file to global storage.

2. The graph compiler downloads the file, prunes the graph, and writes it in binary format.

3. The Pixie server, which periodically checks for a new graph, loads the latest graph into memory.

4. The app sends the server the set of query pins, built from the pins the person interacted with.

5. The server simulates short walks from the query pins and counts the visits to each pin.

6. The most-visited pins go back to the app as recommendations.

The basis is simple: from the query pin, many short walks are simulated on the graph and the number of times each pin is visited is counted; the more visits, the more related it is to the query pin. The procedure's running time is constant and independent of graph size, since it is determined by the parameter N.

On top of that basis Pixie adds improvements: per-user bias in edge selection, different weights for each query pin, a preference for candidates linked to several query pins, and early stopping, which ends the walks when the set of top candidates becomes stable.

Because the walk visits pins and boards, both types of object can be recommended. To show new pins, Pixie recommends boards first and then serves the new pins saved in them.

03 · PIXIE AND THE IN-MEMORY GRAPH

The graph fits on one machine, by design

The graph comes from a Hadoop pipeline and a graph compiler, and this process runs once a day. The compiler runs on a single machine with RAM on the order of terabytes, prunes the graph, and writes it in binary format, which can be easily shared across machines. This flow is a data pipeline done in batch that feeds the online service.

Pruning removes high-entropy topic boards from the graph and discards edges of high-degree pins. According to the paper, it shrinks the graph and memory by six times and makes the recommendations 58% more relevant.

With this, the pruned graph of 3 billion nodes and 17 billion edges fits in about 120 GB of main memory. The random walk does not need to cross machines, and capacity grows by adding machines to the cluster. Each server restarts once a day to load the latest graph.

04 · PINSAGE AND GRAPH CONVOLUTION

PinSage: embeddings that combine graph and content

A graph convolutional network (GCN) learns to iteratively aggregate attribute information from each node's local neighborhood. GCNs take advantage of both the content and the structure of the graph, and pins have text and image attributes. The challenge the paper points out is scaling training and inference to graphs with billions of nodes and tens of billions of edges.

Instead of using all neighbors, PinSage simulates random walks from the node and defines the neighborhood as the nodes with the highest normalized visit counts. These counts become the weights of a weighted average in the aggregation, called importance pooling.

The parameters of the convolutional modules are shared across all nodes, and so the parameter complexity is independent of the input graph size.

1. The positive training pairs, of related pins, come from users' engagement history.

2. The adjacency list and the attribute matrix stay in CPU memory, from which the producer reads them.

3. The CPU-bound producer samples the nodes' neighborhoods; the CPU also handles negative sampling.

4. The ready minibatches go to the GPU, which does not need to communicate with the CPU during convolution.

5. The trained model is stored for the inference step, covered next.

Training adopts the producer-consumer pattern: a large-memory, CPU-bound producer samples the neighborhoods, and a GPU-bound TensorFlow model consumes the already-assembled computation graphs. The adjacency list and the attribute matrix stay in CPU memory.

For the model to separate similar items, each positive example gets hard negatives: items somewhat related to the query, but less than the positive item, randomly sampled from ranking positions 2000 to 5000. A training curriculum does not use them in the first epoch and adds them in later epochs.

05 · PINSAGE: INFERENCE AND SERVING

Precomputed embeddings, online search

Computing embeddings node by node with the naive algorithm leads to repeated computations. PinSage uses a MapReduce pipeline that runs model inference without repeated computations, and each node's latent vector is computed only once. It is another example of data pipeline done in batch.

1. With the model already trained, the MapReduce jobs read the graph and the pins' attributes.

2. The jobs project all pins into a latent space and join these representations to the boards where each pin appears.

3. The process repeats for the following layers, using the previous layer's representations as input.

4. The embeddings, each computed without repetition, are saved in the embedding store.

5. To recommend related pins, the app sends a query pin to the search service.

6. The service looks up in the store the embeddings closest to the query pin, with the help of locality-sensitive hashing.

The model is trained offline and the embeddings of all nodes are computed via MapReduce and saved in a store. Thus, efficient nearest-neighbor search makes it possible to serve recommendations online. The paper cites locality sensitive hashing as a way to get approximate KNN.

In offline evaluation, PinSage reached a 67% hit rate and 0.59 MRR. In A/B tests on the homefeed, the repin rate improved by 10% to 30% over the annotation-based and visual alternatives. Inference for 3 billion items finishes in under 24 hours.

06 · COMPARISON

Pixie and PinSage side by side