In the previous post I argued that social recommendation keeps underperforming the item-recommendation playbook for a structural reason, item interactions form a bipartite graph, social interactions form a unipartite one, and that difference pushes the viewer–candidate relevance matrix toward high effective rank. That is the kind of claim that sounds good in an essay and means nothing until you try to measure it. So before building anything on top of it, I want to take it apart: how would you actually check whether a recommendation problem is low-rank, how would you fool yourself doing it, and, once you have checked, how far does the answer get you?
The short version is that almost everything people do to “show their graph is low-rank” or “high-rank” is either meaningless or misleading, there is exactly one figure that settles it, and even settling it leaves you inside a frame that is too small for the problem. I will take those in order.
Why algebraic rank won’t help
The first thing to get out of the way is that the ordinary, algebraic rank of an interaction matrix tells you nothing here. People reach for it because it sounds rigorous, “the rank of \(R\)”, but a sparse binary matrix is, with overwhelming probability, close to full algebraic rank regardless of any structure it contains. A social graph with a billion nodes and a few hundred billion edges is “full rank” in the algebraic sense, and so is a randomly scrambled version of it with every community destroyed. If full algebraic rank is consistent with both “rich latent structure” and “pure noise,” it cannot distinguish them, and it is useless as a diagnostic.
What you want instead are measures that weight the singular values, because the whole question is how fast they fall off. There are a few, and they agree more than they disagree:
- Truncated-SVD reconstruction curve, for a target fraction \(x\), the smallest rank \(r\) such that the best rank-\(r\) approximation explains \(x\%\) of the matrix’s Frobenius mass. This is the one I would reach for first, for a reason I’ll come back to: it is literally the question the model is going to ask. Matrix factorization is a rank-\(r\) approximation, and this curve tells you, for every \(r\), how much signal survives.
- Stable rank, \(\|A\|_F^2 / \|A\|_2^2\), the ratio of total spectral mass to the top singular value. Bounded by algebraic rank, but robust to the long tail of tiny singular values that a sparse matrix always has.
- Effective rank, \(\exp(H(p))\), where \(p_i = \sigma_i / \sum_j \sigma_j\) and \(H\) is Shannon entropy; in plain terms, how spread out the spectrum is.[1]
- Spectral decay slope, fit \(\log \sigma_i \approx -\alpha \log i\); a steep \(\alpha\) is low-rank, a flat one is high-rank.
These are all reasonable. The reconstruction curve is the one that matters, because it is denominated in the same units as the thing you are about to do to the matrix.
The diagnostics that actually weight the spectrum:
| Measure | What it is | Caveat |
|---|---|---|
| Algebraic rank | number of nonzero singular values | useless, sparse 0-1 matrices are near-full-rank regardless of structure |
| Stable rank | |A|²_F / |A|²_2 | robust to the long tail of tiny singular values |
| Effective rank | exp(H(p)) over normalized σ | “how spread is the spectrum” |
| Truncated-SVD reconstruction | rank r to explain x% of the mass | the one that matters, it is exactly what MF loses |
| Spectral decay slope | fit log σ_i ≈ −α log i | steep α = low-rank |
The two traps
Here is where almost every “look, our graph is high-rank” plot I have seen goes wrong. There are two confounds, and either of them will manufacture a rank gap between an item matrix and a social matrix that has nothing to do with viewer-conditioning.
The first is sparsity. Item matrices and social matrices are rarely observed at the same density, an item catalog might have dozens of interactions per item, a social graph might have a handful per node, and sparsity alone inflates effective rank. A fair comparison has to hold density fixed, usually by subsampling the denser matrix down to the sparser one’s level, or by measuring on the observed-entry submatrix only. Without that, you are partly measuring how much data you have, not how it is shaped.
The second, and sneakier, is popularity. The top singular value of an interaction matrix is, to first order, just popularity, a few heavily-connected nodes and a few heavily-connected items dominate it. A matrix can look low-rank purely because its degree distribution is skewed, with no low-rank latent structure underneath at all. This is well known to the people who run these systems at scale; Meta’s RankGraph work does explicit popularity-bias correction before anything else, and it is not decoration.[2] The honest version of the measurement residualizes popularity out first, fit the rank-one model \(R \approx u d^\top\) of pure viewer and candidate popularity, subtract it, and measure the rank of what is left.
The claim from the previous post has to survive that residual. If you remove popularity and the social spectrum collapses to look like the item spectrum, then “high-rank” was never viewer-conditioning; it was just degree heterogeneity, and the thesis is dead. I have seen enough spectrum plots presented without this step that I no longer trust any of them on first reading.
The two things that will fake a rank gap between an item matrix and a social matrix:
| Confound | What it does | Fix |
|---|---|---|
| Sparsity | denser item vs sparser social inflates effective rank | compare at matched density (subsample the denser one) |
| Popularity | σ₁ is just degree skew; a matrix can look low-rank from popularity alone | residualize R ≈ ud^T first, measure the rank of the residual |
The figure that settles it
There is a cleaner test than reading spectra at all, and it is the one I would actually run. Stop looking at the matrix and look at the model.
Take a matrix-factorization model, or a sequence model, the choice does not matter much, and train it at increasing embedding dimension \(d\), say \(\{8, 16, 32, 64, 128, 256\}\), on both an item dataset and a social dataset, and plot a held-out metric (Recall@K, NDCG@K) against \(d\). The prediction is specific: the item curve saturates, it flattens once \(d\) is large enough to hold the low-rank structure, and more dimensions buy nothing. The social curve, on the same model, keeps climbing, or fails to saturate within any dimension you can afford.
This is the figure that settles it because it is denominated in the only currency that matters, model performance, and it ties the abstract rank claim to the concrete knob you actually turn. It is also, conveniently, a falsification test. If the social curve saturates just as early as the item curve, then for that dataset the problem was low-rank after all, the previous post’s framing does not apply, and no amount of spectral hand-waving rescues it. A claim that cannot be killed by its own experiment is not really a claim.
For completeness, the full set of things that would kill it: a low-rank model matching a viewer-conditioned one on social data; the social spectrum decaying as fast as the item spectrum after popularity residualization; and the metric-versus-\(d\) curve saturating equally fast in both domains. Treat those as the experimental program rather than as decoration. The claim is solid to the extent that none of them show up on real data, and the degree-500 production graphs most of this literature never touches are exactly where I would expect them not to.
But “high-rank” is still inside the matrix
Here is the part that took me longer to internalize than the rest of it put together. Even if you run all of the above and the answer comes back “yes, high-rank,” you are still standing inside a frame that is too small for the problem.
A matrix entry \(R_{vc}\) asserts something specific: that the relevance of \(c\) to \(v\) is a function of \(v\) and \(c\) alone, a bilinear form. Social relevance violates that routinely. Whether I want to connect to someone depends on who else connects us, which is a third party the matrix has no room for. It depends on the path between us, two hops versus three, a closed triangle versus an open one, which a single scalar entry collapses. It depends on the kind of edge (a follow is not a friendship is not a block) and on time and context, none of which a static 2D matrix can express without being unfolded into something larger.
The cleanest way to see how badly the matrix undersells the problem is the triangle. The single most predictive signal in friend suggestion is triadic closure, friends of friends, which is a specific third node whose identity matters. A bipartite graph cannot contain a triangle at all; it has no odd cycles. This is not a coincidence about why item recommendation and social recommendation differ. It is the reason. The dominant social signal lives in a motif that the item-recommendation topology is structurally forbidden from containing, which is also why hand-computed graph features keep beating dot-product embeddings on link-prediction benchmarks: Adamic-Adar, common-neighbor counts, and personalized PageRank are not functions of the pair, they are functions of the graph around the pair, and the graph around the pair is where the signal actually is.
There is a whole research line that takes “the matrix is not enough” seriously, tensor factorization, which models interactions as a \(d\)-mode object over (user, item, context, time) instead of a 2D matrix,[3] and hypergraph methods, where an edge can join more than two nodes at once. These are the honest endpoint. They are also expensive and do not scale kindly to billions of nodes, which is why almost nobody runs them in production and why “people you may know” systems still compute structural features by hand and hand them to the ranker.
Where the fix actually lives
So the landscape has three positions, and it is worth being clear about which one you are standing in.
At the bottom is global low-rank factorization, one shared embedding per node, a fixed dot product. This is item recommendation’s natural home, and it is sufficient there because the structure genuinely is low-rank.
At the top is the full higher-order object, tensors, hypergraphs, hand-computed graph features. This is where the signal actually lives, and it is the only frame that can express third-party dependence and triadic closure without cheating. It is also, at social-graph scale, more or less unaffordable as an end-to-end model.
In the middle is the move I want to defend, and I want to be careful about what it is and is not. If the same candidate has to be a different vector to each viewer, you can keep the candidate’s embedding viewer-independent in the part that is genuinely stable, its structural fingerprint, how it connects, and put the viewer-specific part into a small operator that re-projects that fingerprint per viewer. That operator does not escape the matrix; it is still bilinear in viewer and candidate, and it does not raise the rank ceiling either. Push the operator through the inner product and it lands on the viewer’s side rather than the candidate’s, which leaves one \(d\)-dimensional vector per viewer against one \(d\)-dimensional vector per candidate, so the matrix of scores still has rank at most \(d\), for any per-viewer rank \(r\) you pick. The third post derives that identity, and the same line that caps the rank is what makes the design cheap to serve. What the operator buys is not more rank but a better way of spending the \(d\) dimensions you already have: the viewer’s vector stops being a free row in a lookup table and becomes a function of the viewer’s own structure, which is where the cold-start, the generalization across viewers, and the storage that does not grow with the number of viewers all come from. Raising the ceiling is a different move, and it means giving up the single inner product, which puts you at the top of the landscape rather than the middle.
The landscape, three positions:
| Position | Rank model | Scale cost | Captures Axis B? |
|---|---|---|---|
| Global low-rank (MF) | one shared d | cheap | no |
| Per-viewer projection W_v | still one shared d (generated query) | cheap (query-side) | no, soft proximity only |
| Tensor / hypergraph / graph features | full higher-order | expensive | yes, the endpoint |
That is a modest claim and I want to keep it modest. Viewer-conditioned projection is not the endpoint, the endpoint is the higher-order structure, and anyone who tells you a clever embedding trick has replaced the need for graph features is selling something. It is a scalable middle floor: a way to get the viewer’s side of the bilinear frame from structure rather than from a lookup table, without paying for the full tensor, in the specific regime where you have a billion viewers and a relevance function that changes shape for each of them. Building that floor, and being honest about where it stops, is the next post.
Notes
[1] Effective rank as entropy of the singular-value spectrum goes back to Roy & Vetterli; the same quantity, under the name “stable rank” or “numerical rank,” appears all over the low-rank-adaptation literature, where it is used to ask how much useful direction an adapter matrix actually adds.
[2] Popularity-bias correction as a first-class step in billion-scale graph learning is laid out in Meta’s RankGraph line of work, which compresses hundreds-of-trillions of edges down to hundreds-of-billions partly by correcting for the degree skew before anything else. The residualization trick, fit and subtract a rank-one popularity model, is the single-node version of the same idea.
[3] The canonical reference for treating context as extra tensor modes is Karatzoglou et al., “Multiverse Recommendation” (RecSys 2010), which reports up to 30% improvement over non-contextual matrix factorization; the broader case that the user–item matrix is too small a frame is made in Shi, Hanjalic, “Collaborative Filtering beyond the User-Item Matrix” (ACM Computing Surveys, 2014).