Part I: Item recommendation is bipartite. Social recommendation isn’t.

There is, by now, a standard playbook for building a recommender, and most of it is well-trodden: embed the items, embed the users, score with a dot product (or some more complicated interaction architecture on top of those same shared embeddings, it doesn’t change anything that follows), then stack a sequence model on top to capture how taste drifts over time. It works remarkably well for products and ads. So it is natural to reach for the same machinery when the candidates stop being items and start being people, friend suggestions, follow recommendations, the “people you may know” rail.

And then it keeps underperforming, in ways that don’t quite match the usual suspects.

The two explanations you hear most are scale, a billion people is a harder candidate pool than a million products, and the cost of compressing people into semantic IDs or clusters. Both are real. I have spent a lot of time on the scale problem in particular, and it is genuinely brutal; on the graph I work with, the average node has around 500 neighbors, which is a different universe from the degree-5-to-10 citation graphs that most graph-learning papers experiment on. But neither scale nor compression is the root cause of why the playbook underperforms. You can solve both and still watch your embeddings underfit, and most teams do.

The root cause is structural, and almost nobody names it. Item recommendation operates on a bipartite graph. Social recommendation does not. Everything else, the high rank, the failure of sequence models, the strange durability of hand-crafted graph features, falls out of that one difference.

Two graphs that look alike

A user–item interaction graph is bipartite. Its nodes come in two disjoint sets, users and items, and edges only ever run between the sets: a user connects to an item, never to another user, and an item never connects to another item. This is so obvious that it is easy to miss what it buys you. The bipartite structure fixes every node’s role. A user is always the one doing the viewing; an item is always the one being viewed. There is no node that is sometimes a user and sometimes an item, so there is no ambiguity about which side of the dot product a node belongs on.

A social graph is unipartite. There is one set of nodes, people, and edges run within it. The same person who is the viewer in one edge is the candidate in another. Roles are not a property of the node; they are a property of the edge.

Item recommendation is bipartite. Social recommendation isn’t.

This is not a notational quibble. It is the reason a single static embedding per person is the wrong object.

The contrast, compactly, and why the topology is doing the work:

Item rec — bipartite            Social rec — unipartite

  u1 ---- i1                      p1 ---- p2
  |       |                       |       |
  u2 ---- i2                      p3 ---- p4

  two node types                 one node type
  roles fixed by side            roles fixed per edge

The same person is a different person to everyone

In item recommendation, giving each item one vector is a reasonable thing to do, because an item has a relatively stable meaning: a phone is a phone to everyone, up to small differences in how much any given person wants one. The item’s “attractiveness” is approximately a global property, and a user’s “taste” is approximately a global property, and the score is the inner product of the two. This clean separation, one factor per side, is exactly what matrix factorization assumes, and it works because the topology hands it to you for free: the two sides are literally different types.

In a social graph there is only one type. A person has, simultaneously, a taste (whom they tend to reach out to) and an attractiveness (who tends to reach out to them), and there is no partition to keep them apart.[1] Worse, the attractiveness is itself viewer-dependent. To one person I am an old college classmate; to another a former manager; to a third a competitor. These are not small perturbations of a single ground-truth vector. They are close to orthogonal roles, and any single embedding has to average over all of them.

This is the thing that breaks the playbook. The candidate embedding, which in item recommendation is a noun, a stable description of what the item is, has to become a verb in social recommendation: a function of who is looking.

The same person is a different person to everyone.

You can feel the problem without any math. But it has a precise mathematical statement, and the statement is what tells you which fixes will work and which are wishful thinking.

Why the low-rank trick stops working

Matrix factorization, shared embeddings, and attention-based sequence models all share one assumption: the interaction structure is low-rank. Concretely, if you write the user–item interaction matrix as \(R\) and look at its singular values, they drop off fast, so a rank-\(d\) approximation \(R \approx UV^\top\) with small \(d\) captures most of the signal. That is why a 64- or 128-dimensional embedding is enough for a catalog of millions of items, and it is the whole reason any of this is computable.

“Low-rank” is not magic; it means something specific. It means the preference for any one item can be reconstructed, approximately, as a linear combination of preferences for a small basis of other items. That holds for items because items have discoverable latent dimensions, genre, price, brand, that many users agree on. The basis is small and shared.

Social relevance does not have a small shared basis. The relevance of candidate \(c\) to viewer \(v\) depends on the subgraph between them, which mutual friends they share, what communities they overlap in, how the connection would close a triangle, and that subgraph is a different function for every viewer. Stack the viewer–candidate relevance across all viewers and you do not get a matrix whose singular values drop off fast. You get one whose spectrum is comparatively flat. In the language people use for this, the effective rank is high.[2]

Exactly how high, and how to measure it without being fooled by sparsity or by popularity skew, is a question worth its own treatment, and I will come back to it. For now the point is structural: viewer-conditioning pushes the relevance matrix toward high rank as a matter of construction, not noise.

Here is the practical consequence, and it is the one I keep coming back to. If you train a model at increasing embedding dimension \(d\), on an item dataset the held-out metric saturates quickly, you have captured the low-rank structure and more dimensions buy you nothing. On a social dataset, with the same model, the curve keeps climbing, or fails to saturate within any budget you can afford. The signal is there; it just does not fit in a low-rank box.

And why piling on attention doesn’t help

The natural reaction to “low rank isn’t enough” is “then use a bigger model, a sequence model, a transformer.” This is the move the field has made for item recommendation, and it is a good move there. But it does not escape the rank problem in social recommendation, because sequence models bake low rank in at two separate places, and neither is lifted by adding layers.

First, the embeddings. Giving every item one vector in a shared \(d\)-dimensional space is itself the assertion that the item–item similarity structure lives in \(d\) dimensions, that the similarity matrix has rank at most \(d\). Sharing an embedding across all viewers is only harmless when an item’s meaning is viewer-independent, which is exactly the low-rank regime.

Second, and more sharply, attention itself is a low-rank operator. In a single attention head the \(n \times n\) score matrix is \(QK^\top\), where \(Q\) and \(K\) are projected down to the head dimension \(d_h\). So

no matter how deep or wide the model gets.[3] Stacking layers does not raise this ceiling; only the head dimension does, and even then only to \(d_h\). Multi-head attention is several rank-\(d_h\) operators in parallel, not one high-rank operator.

So a sequence model is, mechanically, a rank-\(d_h\) projector applied to the relationship structure. In item recommendation that is fine: the true structure fits in \(d_h\) dimensions, the projector is lossless, and the model recovers it, which is exactly why sequence-model architectures win there. In social recommendation the true structure needs rank well above \(d_h\), the spectrum is flat enough that each captured component explains little, and the projector returns almost nothing transferable. More layers and more parameters cannot fix a rank ceiling; they can only carry you closer to a ceiling you were already under.

This is also, I suspect, why the generative-recommendation literature keeps reporting instability when it tries to map heterogeneous social signals into a single shared vector space. The model is trying to express high-rank structure through a low-rank bottleneck, and the optimizer has nowhere good to put the residual.

But isn’t item recommendation also “beyond bilinear”?

There is a reasonable objection to all of this, and I want to put it directly, because it is the one I get most often. Item recommendation is also beyond bilinear, that, after all, is the whole reason the field moved from plain matrix factorization to sequence models. Matrix factorization is bilinear and insufficient; HSTU adds capacity beyond it. So “beyond bilinear” does not actually separate social from item. Maybe the real difference is just scale and degree.

The objection is half right, and I do not want to talk past it. HSTU is genuinely beyond static matrix factorization: it makes the user state a function of their interaction sequence, which a fixed user vector cannot express. That is real capacity, on a real axis.

The mistake is in thinking “beyond bilinear” is one axis. It is two, and they are orthogonal.

The first axis is temporal and sequential: whether a user’s state is a fixed vector or a function of the sequence of things they have done. Matrix factorization is at zero on this axis; sequence models are at one. This is the axis HSTU lives on, and it is the axis item recommendation was actually limited by, so the gain was large and real.

The second axis is higher-order and relational: whether the relevance of a pair depends only on the two endpoints, or on the graph structure between them, the mutual friends, the paths, the triangles. On this axis, attention scores a candidate against a history through inner products over shared low-rank embeddings, which is a rank-\(d_h\) bilinear operator. It learns soft, anonymous co-occurrence (this candidate tends to appear with these history items); it does not learn that a specific third person mediates this particular pair. Sequence models are at zero on this axis too. They are beyond bilinear on the first axis and still bilinear on the second.

Social recommendation is beyond bilinear on the second axis, and that is the one that matters for it. The dominant signal in friend suggestion is triadic closure, friends of friends, which is a specific third party whose identity matters. A bipartite graph cannot contain a triangle at all, which is why item recommendation’s “beyond bilinear” is necessarily confined to the temporal axis and a sequence model is sufficient there; a unipartite graph is made of triangles, which is why social recommendation forces the relational axis and a sequence model is not.

There is an empirical tell that the two axes are different. The big wins in item recommendation came from the matrix-factorization-to-sequence-model transition, the temporal axis. The big wins in social recommendation did not come from sequence models; they came from hand-crafted graph features, things like Adamic-Adar and personalized PageRank and common-neighbor counts, which attack the relational axis directly. Production “people you may know” systems still compute these features by hand and feed them into the ranker. If “beyond bilinear” were a single axis, the sequence models would have made those features redundant by now. They have not, because the structural signal is not something attention discovers; it is something you have to compute and hand it.

What this changes

If the problem is structural, unipartite topology, high effective rank, a relational axis that attention cannot reach, then the fixes that get tried most often are the wrong ones. A bigger embedding table does not help; the signal does not fit in a larger low-rank box, it fits in a differently-shaped one. More attention layers do not help; they sit under the same rank ceiling. A fancier walk-based graph tokenizer does not help, at least not at social-graph degrees, when I ran 12-hop node2vec-style walks on the degree-500 graph, they came back as near-straight chains, because on a node with 500 neighbors the probability that a walk ever turns back is \((499/500)^{12} \approx 97.6\%\), and 97 or 98 of every 100 sampled structures were the same trivial path.

What does help, I think, is taking the viewer-dependence seriously as a first-class object rather than something to be averaged away. If the same candidate has to be a different vector to each viewer, then the candidate embedding should be viewer-independent only in the part that is genuinely stable, its structural fingerprint, the pattern of how it connects, and the viewer-specific part should live in an operator that re-projects that fingerprint for each viewer. Done at the scale of a billion people, the engineering question becomes how to materialize a per-viewer operator without storing a matrix per viewer, and the answer turns out to look a lot like the low-rank residual trick from model adaptation, relocated from “adapt a model cheaply” to “make a candidate viewer-aware cheaply.”

That is a story for another post. The point of this one is narrower, and I think more useful: before arguing about which model to use, it is worth noticing that item recommendation and social recommendation are not the same problem wearing different clothes. They are different problems that happen to share a vocabulary, and the vocabulary, embeddings, attention, sequence models, is borrowed from the one where it works. No amount of borrowed machinery fixes a problem whose structure you have not named. Naming the structure is most of the work.

Notes

[1] The taste/attractiveness split for people-to-people recommendation goes back to symmetric collaborative-filtering work from around 2010, which pointed out that the standard active-user / passive-item assumption of collaborative filtering does not hold when the “items” are also users.

[2] Effective rank is usually measured as something like the entropy of the normalized singular-value spectrum, or the stable rank \(\|R\|_F^2 / \|R\|_2^2\), rather than the algebraic rank, a sparse binary matrix is trivially near full algebraic rank regardless of structure, so the algebraic rank tells you nothing useful here.

[3] This is Theorem 1 of Bhojanapalli et al., “Low-Rank Bottleneck in Multi-Head Attention Models” (ICML 2020): the head size places a hard low-rank bottleneck on what an attention unit can express, and it is not lifted by depth or width.