GNNs for Recommender Systems

Slide 5 motivates the topic with the information explosion of the Internet era: 10K+ movies on Netflix, 12M products on Amazon (350M on Marketplace), 70M+ music tracks on Spotify, 10B+ videos on YouTube, 200B+ pins (images) on Pinterest. No user can browse this. Personalized recommendation, which means suggesting a small number of interesting items to each user, is what lets users find the content they care about.

Slide 6: a recommender system is naturally a bipartite graph.

• Two node types: users and items.
• Edges connect users and items only. An edge means a user–item interaction (click, purchase, review, …).
• Edges often carry a timestamp (when the interaction happened).

Slide 7 states the task. Given the past user–item interactions, predict the new items each user will interact with in the future. This is a link prediction problem: predict new user–item edges from the past edges (the figure shows a bipartite graph with dashed "?" edges from one user). Concretely, for \(u\in U\) and \(v\in V\) we need a real-valued score \(f(u,v)\).

Slide 8 raises a practical problem: we cannot evaluate \(f(u,v)\) for every user–item pair (millions of users times millions of items). The solution is a 2-stage process:

1. Candidate generation (cheap, fast). The user embedding is sent to a nearest-neighbour (NN) search engine over the embeddings of millions of items, which returns about 1000 candidate items. An example score here is \(f(u,v)=z_u\cdot z_v\).
2. Ranking (slow, accurate). Score and rank only the candidates with \(f(u,v)\) and return the top-10 items as recommendations.

The diagram on slide 8 shows exactly this pipeline: user embedding → NN engine → candidate items → scoring box → top-10.

Why the dot product is useful in stage 1: maximum inner-product search can be done approximately in sub-linear time with index structures, so the dot product is chosen for its speed as much as for its accuracy. This lecture focuses on how to learn good embeddings.

Slide 9: for each user we recommend \(K\) items. To be useful, \(K\) must be much smaller than the total number of items (up to billions); typically \(K\) is 10–100. The goal is to include as many positive items as possible in the top-\(K\) list, where positive items are the items the user will interact with in the future. The evaluation metric is Recall@K.

Slide 10 sets the notation for one user \(u\):

• \(P_u\): the set of positive items (future interactions).
• \(R_u\): the set of items recommended by the model. In top-\(K\) recommendation, \(|R_u|=K\).
• Items the user has already interacted with are excluded from \(R_u\).

Slide 11 defines the metric (the Venn diagram shows \(P_u\), \(R_u\) and their overlap):

\[ \text{Recall@}K(u)=\frac{|P_u\cap R_u|}{|P_u|}. \]

A higher value means more of the user's future items made it into the top \(K\). The final Recall@K is the average over all users.

Check yourself: a user will buy items \(\{a,b,c,d\}\) and you recommend \(\{a,x,c\}\) with \(K=3\). Recall@3 = 2/4 = 0.5. Why is recall, not precision, the natural choice here? show answer

Because \(K\) is fixed and small, while \(|P_u|\) varies; recall asks "how much of what the user wants did we catch?"

Slide 12, "Recommendations with LLMs?", compares two ways to build the embeddings in the same NN-engine pipeline:

• GNN: embed users and products with a GNN on the interaction graph.
• LLM: turn each product into text ("textify") and embed it with an LLM; the user embedding is the average of the embeddings of the purchased products.

The table is for H&M fashion recommendation:

• MAP@12: LLM 0.00190, GNN 0.02856 (about 15× better).
• Precision@12: LLM 0.00329, GNN 0.01023 (about 3×).
• Recall@12: LLM 0.00119, GNN 0.05234 (about 40×).
• F1@12: LLM 0.0071, GNN 0.01564 (about 2×).

The lesson: knowing what a product is (text) is much weaker than knowing who bought it together with what (graph). The link points to the article "Do Large Language Models make accurate personalized recommendations?".

Slide 14 fixes notation: \(U\) is the set of all users, \(V\) the set of all items, and \(E=\{(u,v)\mid u\in U, v\in V, u \text{ interacted with } v\}\) the set of observed interactions.

Slide 15: to get the top-\(K\) items we need a real-valued scalar score(u, v) for every user–item pair. The \(K\) items with the largest scores for user \(u\), excluding already-interacted items, are recommended. The figure shows user \(u\) with scores to items \(v_0,\dots,v_5\): \(\text{score}(u,v_0)=2.0\), \(v_1\): 3.0, \(v_2\): −2.3, \(v_3\): 4.0, \(v_4\): 0.7, and \(v_5\) is an already-interacted item (no score needed). For \(K=2\) the recommended items are the two highest, \(\{v_1,v_3\}\). The rule: rank by score, skip already-interacted items, take the top \(K\).

Slide 16 introduces embedding-based models:

• Each user \(u\in U\) has a \(D\)-dimensional embedding \(\mathbf u\in\mathbb R^D\).
• Each item \(v\in V\) has a \(D\)-dimensional embedding \(\mathbf v\in\mathbb R^D\).
• A parametrized function \(f_\theta(\cdot,\cdot):\mathbb R^D\times\mathbb R^D\to\mathbb R\) scores a pair: \(\text{score}(u,v)\equiv f_\theta(\mathbf u,\mathbf v)\).

Slide 17: so an embedding-based model has three kinds of parameters:

1. an encoder that produces user embeddings \(\{\mathbf u\}_{u\in U}\);
2. an encoder that produces item embeddings \(\{\mathbf v\}_{v\in V}\);
3. the score function \(f_\theta(\cdot,\cdot)\).

Training objective: optimise the parameters to achieve high Recall@K on seen (training) interactions, hoping that this gives high Recall@K on unseen (test) interactions. This is the usual generalisation bet of machine learning.

Slide 18: Recall@K is not differentiable (it depends on a sorted top-\(K\) list, which changes in jumps as the scores move). So we cannot use efficient gradient-based optimisation on it directly. Two surrogate loss functions are widely used instead:

• the binary loss;
• the Bayesian Personalized Ranking (BPR) loss.

A good surrogate must be differentiable and align well with the original objective.

Slide 19 defines the ingredients. Positive edges are the observed training interactions \(E\). Negative edges are all other user–item pairs:

\[ E_{\text{neg}}=\{(u,v)\mid (u,v)\notin E,\ u\in U,\ v\in V\}. \]

The sigmoid \(\sigma(x)=\frac{1}{1+\exp(-x)}\) maps a real score to a likelihood in \([0,1]\) (the small plot shows the S-shaped curve).

Slide 20, the binary loss: binary classification of positive vs negative edges using \(\sigma(f_\theta(\mathbf u,\mathbf v))\):

\[ -\frac{1}{|E|}\sum_{(u,v)\in E}\log\sigma\big(f_\theta(\mathbf u,\mathbf v)\big)\;-\;\frac{1}{|E_{\text{neg}}|}\sum_{(u,v)\in E_{\text{neg}}}\log\Big(1-\sigma\big(f_\theta(\mathbf u,\mathbf v)\big)\Big). \]

During training, both sums are approximated with mini-batches of positive and negative edges (\(E_{\text{neg}}\) is far too large to enumerate). The binary loss pushes scores of positive edges up and scores of negative edges down. This matches the recall metric in spirit: positive edges must be recalled.

Slide 21 states the issue: in the binary loss, the scores of ALL positive edges are pushed higher than those of ALL negative edges. This can penalise the model even when the training recall is already perfect.

Slide 22 gives the smallest example: two users \(u_0,u_1\), two items \(v_0,v_1\), metric Recall@1. The model's scores (figure):

• \((u_0,v_0)=1.0\), positive edge; \((u_0,v_1)=-1.0\), negative.
• \((u_1,v_0)=2.0\), negative; \((u_1,v_1)=4.0\), positive edge.

Training Recall@1 is 1.0: \(v_0\) is correctly recommended to \(u_0\) and \(v_1\) to \(u_1\). But the binary loss still penalises the model, because the negative edge \((u_1,v_0)\) (score 2.0) has a higher score than the positive edge \((u_0,v_0)\) (score 1.0). The binary loss wants a single global threshold separating all positives from all negatives; no such threshold exists here, even though each user's ranking is perfect.

Slide 23, key insight: the binary loss is non-personalized: it considers positive and negative edges across all users at once. The recall metric is personalized: it is defined per user. So the binary loss is overly stringent for the metric we care about.

Slide 24, lesson learned: the surrogate loss should be personalized. For each user, positive items should score higher than that user's negative items; we do not care about the order of scores across users. The figure redraws the example with "observed" and "unobserved" interactions. The BPR loss does exactly this.

Check yourself: compute the binary-loss term of the negative edge \((u_1,v_0)\): \(-\log(1-\sigma(2))\approx 2.13\). It is the largest term in the loss, and it concerns a comparison that never affects any user's top-1 list.

Slide 25: BPR is a personalized surrogate loss that aligns better with Recall@K. For each user \(u^*\in U\), define the rooted positive and negative edges:

\[ E(u^*)\equiv\{(u^*,v)\mid (u^*,v)\in E\},\qquad E_{\text{neg}}(u^*)\equiv\{(u^*,v)\mid (u^*,v)\in E_{\text{neg}}\}. \]

The figure shows one user \(u^*\) with a few positive (solid) and many negative (dashed) edges to items. A note on the slide: the word "Bayesian" is not essential. The original paper [Rendle et al. 2009] puts a Bayesian prior on the parameters, which acts as parameter regularisation; the lecture omits it.

Slide 26: for each user \(u^*\), we want the scores of rooted positive edges to be higher than those of rooted negative edges. The loss for one user is

\[ \text{Loss}(u^*)=\frac{1}{|E(u^*)|\cdot|E_{\text{neg}}(u^*)|}\sum_{(u^*,v_{\text{pos}})\in E(u^*)}\ \sum_{(u^*,v_{\text{neg}})\in E_{\text{neg}}(u^*)} -\log\sigma\Big(f_\theta(\mathbf u^*,\mathbf v_{\text{pos}})-f_\theta(\mathbf u^*,\mathbf v_{\text{neg}})\Big). \]

The difference inside \(\sigma\) is "encouraged to be positive", i.e. the positive edge score should exceed the negative edge score for the same user. The final BPR loss averages over users: \(\frac{1}{|U|}\sum_{u^*\in U}\text{Loss}(u^*)\). It can be approximated with a mini-batch.

Slide 27, mini-batch training:

1. Sample a subset of users \(U_{\text{mini}}\subset U\).
2. For each \(u^*\in U_{\text{mini}}\), sample one positive item \(v_{\text{pos}}\) and a set of sampled negative items \(V_{\text{neg}}=\{v_{\text{neg}}\}\).
3. Compute

\[ \frac{1}{|U_{\text{mini}}|}\sum_{u^*\in U_{\text{mini}}}\frac{1}{|V_{\text{neg}}|}\sum_{v_{\text{neg}}\in V_{\text{neg}}}-\log\sigma\Big(f_\theta(\mathbf u^*,\mathbf v_{\text{pos}})-f_\theta(\mathbf u^*,\mathbf v_{\text{neg}})\Big). \]

Intuition: \(-\log\sigma(x)\) is a smooth version of "penalise if \(x\lt 0\)". Each term is a small pairwise ranking problem inside one user's list. Back to the slide-22 example: for \(u_0\), \(-\log\sigma(1-(-1))=-\log\sigma(2)\approx0.13\); for \(u_1\), \(-\log\sigma(4-2)\approx0.13\). Both small, and the cross-user pair \((u_1,v_0)\) vs \((u_0,v_0)\) never appears.

Slide 28 summarises so far: Recall@K as the metric; embedding-based models with three kinds of parameters (user encoder, item encoder, score function); surrogate losses to reach high recall. Embedding-based models are state of the art in recommender systems. Why do they work so well?

Slide 29: the underlying idea is collaborative filtering. Recommend items to a user by collecting the preferences of many other similar users; similar users tend to prefer similar items. The figure: users \(u\) and \(u'\) share several items (they are "similar users"); an item that \(u'\) interacted with but \(u\) did not becomes a "likely edge" for \(u\). The key question is how to capture similarity between users and items.

Slide 30: embedding-based models capture this similarity automatically.

• Low-dimensional embeddings cannot simply memorize all user–item interaction data.
• So, to fit the data, the embeddings are forced to capture similarity between users and items.
• This lets the model predict unseen interactions well.

Think of the interaction matrix \(R\in\{0,1\}^{|U|\times|V|}\). A score \(\mathbf u^\top\mathbf v\) with \(D\)-dimensional vectors is a rank-\(D\) approximation of \(R\). Low rank is a compression; compression forces sharing; sharing is similarity.

Slide 31 lays out the rest of the lecture:

• (1) Neural Graph Collaborative Filtering (NGCF) [Wang et al. 2019] and (2) LightGCN [He et al. 2020]: improve conventional collaborative filtering (shallow encoders) by explicitly modelling graph structure with GNNs. They assume no user/item features.
• PinSAGE [Ying et al. 2018]: uses GNNs to produce high-quality embeddings that capture both rich node attributes (e.g., images) and graph structure.

Slide 33: conventional collaborative filtering uses shallow encoders.

• No user or item features.
• For every \(u\in U\) and \(v\in V\), a shallow learnable embedding \(\mathbf u,\mathbf v\in\mathbb R^D\) (one free vector per node, as in Lecture 3).
• Score function \(f_\theta(\mathbf u,\mathbf v)\equiv\mathbf z_u^\top\mathbf z_v\).

This is classic matrix factorization.

Slide 34, its limitations:

• The model itself does not explicitly capture graph structure. The graph appears only implicitly, through which pairs are positives in the training objective.
• Only first-order structure (the edges themselves) enters the objective. High-order structure, such as \(K\)-hop paths between two nodes, is not explicitly captured.

Slide 35: we want a model that (a) captures graph structure explicitly, not only through the loss, and (b) captures high-order structure beyond single edges. GNNs do both. Two models follow: NGCF [Wang et al. 2019] and LightGCN [He et al. 2020], a simplified and improved version of NGCF.

Check yourself: in matrix factorisation, two users who never share an item can still get similar embeddings. How? show answer

Through a chain: \(u_1\) shares items with \(u_2\), \(u_2\) shares items with \(u_3\). The loss sees only edges, so this multi-hop effect emerges slowly and indirectly through optimisation; a GNN builds it into the forward pass.

Slide 36: NGCF explicitly uses high-order graph structure when it produces user and item embeddings. Key idea: use a GNN to produce graph-aware embeddings. The three-panel figure: initial shallow embeddings on the bipartite graph → a GNN propagates embeddings along the edges → NGCF's graph-aware embeddings.

Slide 37, the framework. Given the user–item bipartite graph:

1. Prepare a shallow learnable embedding for each node.
2. Use a multi-layer GNN to propagate embeddings along the bipartite graph. This captures high-order structure.
3. The final embeddings are explicitly graph-aware.

Two kinds of parameters are learned jointly: the shallow user/item embeddings, and the GNN's parameters.

Slide 38, initial node embeddings: for every user \(u\), set \(\mathbf h_u^{(0)}\) to the user's shallow embedding; for every item \(v\), set \(\mathbf h_v^{(0)}\) to the item's shallow embedding. The learnable embeddings play the role of node features (there are no real features).

Slide 39, neighbor aggregation, done iteratively:

\[ \mathbf h_v^{(k+1)}=\text{COMBINE}\Big(\mathbf h_v^{(k)},\ \text{AGGR}\big(\{\mathbf h_u^{(k)}\}_{u\in N(v)}\big)\Big),\qquad \mathbf h_u^{(k+1)}=\text{COMBINE}\Big(\mathbf h_u^{(k)},\ \text{AGGR}\big(\{\mathbf h_v^{(k)}\}_{v\in N(u)}\big)\Big). \]

Items aggregate from their users and users from their items. Iterating captures high-order structure. Many architecture choices are possible; for example \(\text{AGGR}(\cdot)=\text{MEAN}(\cdot)\) and \(\text{COMBINE}(\mathbf x,\mathbf y)=\text{ReLU}(\text{Linear}(\text{Concat}(\mathbf x,\mathbf y)))\). The figure highlights the edges used to update one user (green) and one item (blue).

Slide 40: after \(K\) rounds we have the final embeddings \(\mathbf h_u^{(K)},\mathbf h_v^{(K)}\). Set \(\mathbf u\leftarrow\mathbf h_u^{(K)}\), \(\mathbf v\leftarrow\mathbf h_v^{(K)}\), and score with the inner product \(\text{score}(u,v)=\mathbf u^\top\mathbf v\). Training uses the BPR loss from before.

Slide 41, summary: conventional CF uses shallow embeddings that do not explicitly model graph structure, and its objective does not model high-order structure. NGCF propagates the shallow embeddings with a GNN, so the embeddings are explicitly aware of high-order structure.

Intuition: after 2 layers, a user's embedding contains the items it bought; after 3 layers it also contains the users who bought those items. That 3-hop path user → item → user → item is exactly the collaborative-filtering signal "people like you also bought".

Slide 43, motivation. NGCF learns shallow embeddings and GNN parameters. Observation: shallow embeddings are already very expressive. They are learned per node, and when \(N\) (number of nodes) \(\gg D\) (embedding dimension), almost all parameters are in them: shallow embeddings are \(O(ND)\), the GNN is \(O(D^2)\). So the GNN parameters may not matter much.

Slide 44: can we simplify NGCF's GNN, for example remove its learnable parameters? Yes, and as a bonus, the simplification improves performance. The plan: adjacency matrix of a bipartite graph → matrix form of GCN → remove the non-linearity (related: SGC for scalable GNNs [Wu et al. 2019]).

Slide 45, the matrices. With interaction matrix \(R\) (\(R_{uv}=1\) if user \(u\) interacts with item \(v\), else 0), the adjacency matrix of the undirected bipartite graph and the shallow embedding matrix are

\[ A=\begin{pmatrix}0 & R\\ R^\top & 0\end{pmatrix},\qquad E=\begin{pmatrix}E_U\\ E_V\end{pmatrix}\ \ (\text{user rows, then item rows}). \]

Slide 46, matrix form of GCN. Let \(D\) be the degree matrix of \(A\) and define the normalised adjacency (the diffusion matrix) \(\tilde A\equiv D^{-1/2}AD^{-1/2}\). Note: unlike the original GCN, the self-connection is omitted. With \(E^{(k)}\) the embedding matrix at layer \(k\) (each row is a node embedding), one GCN layer is

\[ E^{(k+1)}=\text{ReLU}\big(\tilde A E^{(k)}W^{(k)}\big), \]

where \(\tilde AE^{(k)}\) is neighbour aggregation and \(W^{(k)}\) is a learnable linear transformation.

Slide 47, simplify by removing ReLU (idea from SGC): \(E^{(k+1)}=\tilde AE^{(k)}W^{(k)}\). Unrolling,

\[ E^{(K)}=\tilde A E^{(K-1)}W^{(K-1)}=\tilde A\big(\tilde AE^{(K-2)}W^{(K-2)}\big)W^{(K-1)}=\cdots=\tilde A^K E\,W^{(0)}\cdots W^{(K-1)}, \]

with \(E^{(0)}=E\), the input embeddings.

Slide 48: so \(E^{(K)}=\tilde A^K E W\) with \(W\equiv W^{(0)}\cdots W^{(K-1)}\). The \(\tilde A^KE\) part is "diffusing node embeddings along the graph". The algorithm is just: apply \(E\leftarrow\tilde AE\) \(K\) times. Each multiplication spreads the current embeddings to one-hop neighbours. Note: \(\tilde A^K\) is dense and never materialised; we use repeated sparse matrix–matrix products instead.

Slide 49, multi-scale diffusion: \(\alpha_0E^{(0)}+\alpha_1E^{(1)}+\dots+\alpha_KE^{(K)}\) mixes embeddings diffused over different numbers of hops. The term \(\alpha_0E^{(0)}=\alpha_0\tilde A^0E^{(0)}\) acts as the self-connection that was dropped from \(\tilde A\). The \(\alpha_k\) are hyperparameters; LightGCN uses uniform weights \(\alpha_k=\frac{1}{K+1}\) for \(k=0,\dots,K\).

Why can \(W\) be dropped? \(E\) is itself a free learnable matrix, so \(EW\) is just another free matrix of the same shape: the product \(W\) adds no expressive power. LightGCN therefore keeps only \(E\).

Slides 50–53 show LightGCN as a picture of matrices.

1. Slide 50, given: the adjacency matrix \(A\) (blocks \(0,R;R^\top,0\)) and the initial learnable embedding matrix \(E\) (user rows on top, item rows below). Normalise \(A\) to \(\tilde A\), with self-loops omitted.
2. Slide 51, diffuse: for \(k=0,\dots,K-1\), \(E^{(k+1)}\leftarrow\tilde A\cdot E^{(k)}\), with \(E^{(0)}=E\). Because \(\tilde A\) has zero diagonal blocks, one step sends user embeddings to items and item embeddings to users.
3. Slide 52, average across scales: \(E_{\text{final}}\leftarrow\frac{1}{K+1}\big(E^{(0)}+E^{(1)}+\dots+E^{(K)}\big)\).
4. Slide 53, score: take user row \(\mathbf z_u\) and item row \(\mathbf z_v\) of \(E_{\text{final}}\) as the embeddings \(\mathbf u,\mathbf v\), and score with \(\mathbf z_u^\top\mathbf z_v\).

Slide 54, intuition. Why does simple diffusion work so well? Diffusion directly makes the embeddings of similar users (or items) similar. Similar users share many common neighbours (items), so after diffusion they are averages of largely the same vectors, and they are expected to have similar future preferences.

Slide 55, relation to GCN. GCN's aggregation is

\[ \mathbf h_v^{(k+1)}=\sum_{u\in N(v)}\frac{1}{\sqrt{d_u}\sqrt{d_v}}\,\mathbf h_u^{(k)}, \]

with \(d_u,d_v\) the node degrees and a self-loop added to the neighbourhood. LightGCN uses the same equation except: (1) no self-loop in the neighbourhood; (2) the final embedding is the average over all layers, \(\mathbf h_v=\frac{1}{K+1}\sum_{k=0}^{K}\mathbf h_v^{(k)}\).

Slide 56, LightGCN vs matrix factorisation (shallow encoders). Both learn a unique embedding per user and item. The difference is that LightGCN scores with the diffused embeddings. LightGCN performs better but costs more compute, because of the diffusion step: the final embedding of a node aggregates the embeddings of its multi-hop neighbours.

Slide 57, summary: LightGCN simplifies NGCF by removing the GNN's learnable parameters. All learnable parameters are in the shallow input embeddings. Diffusion uses only matrix–vector multiplication. And the simplification gives better empirical performance than NGCF.

Check yourself: with \(K=0\), what is LightGCN? show answer

Plain matrix factorisation. With \(K=1\), the user embedding is \(\frac12(\mathbf e_u+\sum_{v\in N(u)}\mathbf e_v/\sqrt{d_ud_v})\): the user's own vector blended with a degree-normalised sum of its items.

Why "simpler is better" here: with no real input features, the GNN weights and ReLUs in NGCF have nothing meaningful to transform, and they make optimisation harder. The useful part of the GNN was the propagation, not the learned transformation.

Slide 59, the use case: P2P (pin-to-pin) recommendation. The picture shows a fashion pin on the left and, after the arrow, a grid of related pins that should be recommended next to it.

Slide 60, PinSAGE pin embeddings:

• They unify visual, textual and graph information.
• PinSAGE was the largest industry deployment of a graph convolutional network.
• Huge adoption across Pinterest.
• It works for fresh content: an embedding is available a few seconds after a pin is created (inductive, unlike shallow embeddings).

Reference: "Graph Convolutional Neural Networks for Web-Scale Recommender Systems", Ying et al., 2018.

Slide 61, application at Pinterest. Goal: produce embeddings for nodes in a Pinterest graph with billions of objects. Key idea: borrow information from nearby nodes. Example: a bed rail pin may look like a garden fence (the two photos look alike: dark wrought-iron bars), but gates and beds are rarely adjacent in the graph. So the graph neighbourhood disambiguates what images alone confuse. Pin embeddings feed many tasks: recommendation, classification, ranking; services like "Related Pins", "Search", "Shopping", "Ads".

Slide 62, "Harnessing pins and boards": three pins on top (a jacket, a Hans Wegner chair, a plant photo) are connected by lines to the boards below that contain them ("mid century modern", "Men Style", "Plants", …). Users save pins to boards, and this pin–board membership is the graph.

Slide 63: the graph has tens of billions of nodes and edges. The figure shows the bipartite pins–boards graph and, on the right, the GNN computation graph for one pin: it aggregates from its boards, which aggregate from their pins. Doing this "further resolves" the embeddings across the Pinterest graph.

Slide 64: beyond the GNN model, PinSAGE introduces methods to scale GNN training to a billion-scale recommender:

• shared negative samples across users in a mini-batch;
• hard negative samples;
• curriculum learning;
• mini-batch training of GNNs on a large graph (covered in a later lecture).

Slide 65, the task: recommend related pins. Learn node embeddings \(z_i\) such that

\[ d(z_{\text{cake1}},z_{\text{cake2}})\lt d(z_{\text{cake1}},z_{\text{sweater}}). \]

The figure: from a cake source pin, another cake is a successful recommendation and a sweater is a bad one. On the right, two GNN computation trees produce \(z_1\) and \(z_2\), and the loss looks at their distance \(d(z_1,z_2)\).

Slide 66, training data: 1+B (over one billion) repin pairs from the Related Pins surface. They capture semantic relatedness. Goal: embed such pairs as "neighbours" (close). The example positive pairs \((Q,X)\) are pictures that belong together (two dog photos, two decorative items, and so on).

Slide 67 recalls BPR mini-batches: for each user \(u^*\in U_{\text{mini}}\), one positive item and a set of sampled negatives \(V_{\text{neg}}\). More negatives per user improve performance but are expensive:

• we must generate \(|U_{\text{mini}}|\cdot|V_{\text{neg}}|\) embeddings for negative nodes;
• we must run \(|U_{\text{mini}}|\cdot|V_{\text{neg}}|\) GNN computation graphs (the figure shows these trees), which is expensive.

Slide 68, key idea: share the same negative set \(V_{\text{neg}}\) across all users in the mini-batch. Then only \(|V_{\text{neg}}|\) negative embeddings are needed, a saving by a factor of \(|U_{\text{mini}}|\). Empirically, performance stays similar to the non-shared scheme.

Intuition: a random negative is "a random item"; it does not need to be specific to a user. Sharing them is like the in-batch negatives used in contrastive learning.

Slide 69, the challenge: industrial recommenders must make extremely fine-grained predictions. There are up to billions of items, and only 10–100 are recommended per user. Shared negatives are sampled at random from all items, so most of them are easy negatives: the model can tell them apart from positives without being fine-grained. We need hard negatives to force fine-grained distinctions.

Slide 70, the idea: use harder and harder negatives, including more hard negatives each epoch. The pictures: a source pin (a card with a leaf design), a positive (a similar leaf card), an easy negative (a photo of a rural house, obviously unrelated), and a hard negative (another greeting card, similar in style but not truly related).

Slide 71, curriculum learning: make the negatives gradually harder during training. At epoch \(n\), add \(n-1\) hard negative items. The number of hard negatives grows over training, and the model gradually learns finer-grained predictions. (Starting with hard negatives would make the problem too difficult early, when the embeddings are still random.)

Slide 72, how to find hard negatives. For each user node, hard negatives are item nodes that are close but not connected to the user in the graph. For user \(u\):

1. Run random walk with restart from \(u\) and record visit counts for other items/nodes.
2. Sort items in descending order of visit count.
3. Randomly sample items ranked high but not too high, e.g., ranks 2000th–5000th.

These items are close to the user, but not so close that they are likely true positives. Hard negatives are used in addition to the shared negatives.

Slide 73, another way to pick negatives. Positive pairs \((q,p)\) are given; various methods sample a negative \(n\) to form a triple \((q,p,n)\). Distance Weighted Sampling (Wu et al., 2017): sample negatives so that the query–negative distance distribution is approximately uniform on \([0.5,1.4]\). The left diagram: \((q,p)\) and the negatives in the batch go into a sampling block that outputs \((q,p,n)\). The right plot (from the Wu et al. paper) shows where different strategies sample along "distance between examples": hard negative mining concentrates at small distances, semi-hard mining around 0.5, uniform sampling at large distances (around 1.4–1.8), and distance-weighted sampling spreads across the whole range.

Slide 74, fine-grained object similarity. The query is a porcelain lace figurine. A visual-only model returns some figurines but also lamps and lampshades (similar colours and shapes). PinSAGE returns a row of porcelain figurines only: the graph tells it that people save these pins to the same boards.

Slide 75, compare against production. The query is a photo of a cat wearing a knitted lamb hat. The top row (the text extraction labels the systems Pixie, Pinterest's earlier random-walk recommender, and GraphSAGE) returns Shih Tzu posters, dog prints and a T-shirt: related words, wrong concept. The boxed row returns cats wearing knitted animal hats, which is what the user wants.

Slide 76, summary:

• PinSAGE uses GNNs to produce high-quality user/item embeddings that capture both rich node attributes and graph structure.
• It is trained effectively with sophisticated negative sampling strategies (shared, hard, curriculum).
• It is deployed at Pinterest, a billion-scale image recommendation service.

Contrast with LightGCN: LightGCN has no features and a free vector per node (transductive), so it cannot embed a brand-new pin. PinSAGE computes embeddings from features plus neighbourhood (inductive, GraphSAGE-style), which is why fresh pins get an embedding seconds after creation.