Recommendation Systems Built on Graph Embeddings

Collaborative filtering and graph-based recommendation start from identical data: who interacted with what. The difference is how far the signal is allowed to travel. Matrix factorisation looks at direct interactions; a graph model propagates along paths, and the length of the longest useful path is essentially the whole design decision.

The same matrix, drawn as a graph

A user-item interaction matrix with a 1 wherever a user touched an item is exactly the adjacency structure of a bipartite graph: users on one side, items on the other, an edge per interaction. Nothing has been added by redrawing it. What changes is which operations look natural.

Classical matrix factorisation learns a vector per user and per item so that their dot product reconstructs the observed entries. Every user vector is fitted from that user’s own row. Neighbourhood collaborative filtering is a little further along — it scores an item by what similar users did, which is implicitly a path of length three — but the similarity is precomputed and fixed. A graph model makes the propagation explicit and learnable, and lets it run for as many hops as you configure.

Every signal lives on an odd-length path

Three users, four items:

u1 - i1      u2 - i2      u3 - i3
u1 - i2      u2 - i3      u3 - i4

degrees:  u1=2  u2=2  u3=2
          i1=1  i2=2  i3=2  i4=1

Recommend to u1. Walk outward and count what is reachable at each hop:

from u1
  1 hop  (items):  i1, i2                    — already interacted
  2 hops (users):  u2         via i2         — a "similar user"
  3 hops (items):  i3         via i2 → u2    — the recommendation
  4 hops (users):  u3         via i3 → u3
  5 hops (items):  i4         via i3 → u3

paths from u1 to i3 of length 3:  u1 → i2 → u2 → i3    (exactly one)
paths from u1 to i4 of length 3:  none — shortest is 5

Because the graph is bipartite, a walk starting at a user is on a user at every even step and on an item at every odd step. There is no such thing as an even-length user-to-item path. Every candidate item is therefore reached at 3, 5, 7 hops, and each additional pair of hops admits a new and weaker tier of evidence: i3 arrives at 3 hops on strong evidence, i4 at 5 hops on evidence routed through two intermediaries.

That is also the precise reason common-neighbour scores are useless here, as noted on link prediction — u1 and i3 can never share a neighbour. And it is why two propagation layers is the usual minimum in a graph recommender and why going past three or four stops helping: the fifth hop is reachable from most of the graph, so it adds popularity rather than personalisation.

LightGCN: what it removes

LightGCN (He et al., SIGIR 2020) is worth studying because its contribution is subtractive. Standard graph convolution applies a learned weight matrix and a nonlinearity at every layer. LightGCN removes both, keeping only neighbourhood aggregation with symmetric normalisation:

e_u^(k+1) = Σ            1 / sqrt( |N(u)| · |N(i)| )  ·  e_i^(k)
            i ∈ N(u)

e_i^(k+1) = Σ            1 / sqrt( |N(i)| · |N(u)| )  ·  e_u^(k)
            u ∈ N(i)

final embedding = weighted sum over layers, alpha_k = 1/(K+1)

Compute one coefficient from the graph above. For the edge u1–i2: |N(u1)| = 2 and |N(i2)| = 2, so the coefficient is 1/sqrt(4) = 0.500. For the edge u1–i1: |N(u1)| = 2, |N(i1)| = 1, so 1/sqrt(2) = 0.707. The rarely-touched item contributes more to u1’s embedding than the popular one, which is the symmetric normalisation doing its job — a hub is downweighted from both ends.

The argument for removing the transformation and the nonlinearity is that in a pure collaborative-filtering setting the node inputs are one-hot identity vectors with no features to transform. There is nothing for a weight matrix to learn from except the embedding table it already has, so it adds parameters and training difficulty without adding capacity. The layer-combination weights matter more than the layer depth: summing the outputs of all layers rather than taking the last one is what keeps the shallow, sharper signal from being averaged away.

What the model is actually trained against

The propagation rule gets all the attention and the loss function decides more. Interaction data is implicit: you observe that u1 touched i1 and i2, and you observe nothing about i3 and i4. Absence is not a negative — it is overwhelmingly just non-exposure. Training a regression to predict 1 on observed edges and 0 on the rest teaches the model that everything the user has not yet seen is unwanted, which is both false and self-fulfilling.

The standard answer is to train on relative preference instead. Bayesian personalised ranking, from Rendle et al. (UAI 2009), samples a triple of one user, one observed item and one unobserved item and only asks that the observed one score higher:

for each (u, i observed, j sampled unobserved)

  loss = − ln sigmoid( score(u,i) − score(u,j) )   + regularisation

nothing here claims j is disliked — only that i is preferred to j

Two properties follow that matter in practice. The loss is a function of the difference of two scores, so it optimises an ordering rather than a value, which is what a recommender is judged on. And the sampled negative j is drawn per step, so a single user with ten interactions contributes ten triples per epoch rather than one row against a catalogue of a million. How j is sampled is a real design decision: uniform sampling picks obscure items that are trivially easy to rank below the positive and give little gradient, while popularity-weighted sampling picks harder negatives and pushes the model to distinguish items the user genuinely saw and skipped.

Sampling neighbourhoods at production scale

Full-graph propagation assumes the whole adjacency structure fits somewhere you can multiply against. PinSage (Ying et al., KDD 2018) describes the alternative used on a web-scale bipartite graph: instead of aggregating over all neighbours, run short random walks from the target node and define its neighbourhood as the top-T nodes by visit count, weighting each neighbour’s contribution by its visit frequency.

Two things come out of that at once. The neighbourhood is a fixed size, so every training example is the same shape and batches are efficient. And the neighbourhood is importance-ranked rather than arbitrary, so a node with a hundred thousand neighbours contributes the hundred that a walk from it actually keeps landing on, rather than a uniform sample dominated by noise. The general treatment of that trade-off is on graph sampling strategies for training.

Popularity, cold start and leaky evaluation

• Propagation amplifies popularity. High-degree items sit on more paths and accumulate more signal at every hop. Symmetric normalisation dampens this but does not remove it, and the exponent on the degree term is worth treating as a tunable: pushing it toward 1 flattens the popularity bias and usually costs some accuracy on the head of the catalogue.
• A new item has no edges. It is unreachable at any hop count, so it can never be recommended, so it never gets edges. The only escape is information from outside the interaction graph — content features, category, text or image embeddings — which is where an inductive, feature-consuming architecture earns its complexity over a pure embedding table.
• Random splits leak the future. Holding out a random 10% of interactions leaves later interactions from the same user in training, and the model can use tomorrow to predict yesterday. Reported numbers from random splits are systematically optimistic; split by time.
• Offline gains do not survive contact with a feedback loop. The interaction graph you train on was generated by the recommender you are replacing, so it records what was shown, not what was wanted. This is the reason serious deployments run online tests and treat offline ranking metrics as a filter, not a verdict.