上一篇里我论证过：社交推荐之所以在物品推荐的那套打法上持续表现不佳，有一个结构性的原因，物品交互构成的是二分图，社交交互构成的是单分图，而这个差异会把"查看者–候选"的相关性矩阵推向高有效秩。这类论断在文章里听起来很漂亮，可一旦你想去量它，它就什么都不是了。所以在往上盖任何东西之前，我想先把它拆开：到底该怎么去检验一个推荐问题是低秩的？在这个过程中你会怎么把自己骗了？以及，一旦检验完了，这个答案能把你带多远？
简短说：人们为了"证明自己的图是低秩/高秩"而做的几乎所有事情,要么没意义,要么误导人;真正能一锤定音的图只有一张;而即便定完了音,你仍然站在一个对这个问题来说太小了的框架里。我按顺序讲。
代数秩帮不上忙
首先得把一件事赶走：交互矩阵普通的代数秩，在这里什么也告诉你不了。人们去抓它,是因为它听起来很严谨–"\(R\) 的秩"–但一个稀疏的 0-1 矩阵,无论它含有什么结构,都以压倒性的概率接近满代数秩。一个十亿节点、几千亿边的社交图,按代数秩是"满秩"的,把它打乱、把所有社群结构都毁掉之后,它还是"满秩"。如果满代数秩同时和"丰富的潜在结构"以及"纯噪声"都相容,那它就区分不了这二者,作为诊断工具它毫无用处。
你要的是那些给奇异值加权的度量,因为整个问题就是它们掉得有多快。有几个，彼此一致远大于分歧：
- 截断 SVD 重建曲线，给定一个目标比例 \(x\)，能解释矩阵 \(x\%\) 的 Frobenius 范数能量的最小秩 \(r\)。这是我会第一个去抓的，原因待会讲：它问的，恰好就是模型接下来要问的那个问题。矩阵分解本身就是一个秩-\(r\) 近似，这条曲线告诉你，对每一个 \(r\)，有多少信号能活下来。
- 稳定秩，\(\|A\|_F^2 / \|A\|_2^2\)，总谱能量与最大奇异值之比。受代数秩约束，但对稀疏矩阵总有的那一长串微小奇异值很稳健。
- 有效秩，\(\exp(H(p))\)，其中 \(p_i = \sigma_i / \sum_j \sigma_j\)，\(H\) 是香农熵；大白话就是谱有多摊开。[1]
- 谱衰减斜率，拟合 \(\log \sigma_i \approx -\alpha \log i\)；\(\alpha\) 陡就是低秩，平就是高秩。
这些都合理。重建曲线才是要紧的那一条，因为它用的单位，和你接下来要对这个矩阵做的事是同一个。
那些真正给谱加权的度量：
| 度量 | 是什么 | 注意 |
|---|---|---|
| 代数秩 | 非零奇异值个数 | 没用，稀疏的 0-1 矩阵无论结构如何都接近满秩 |
| 稳定秩 | |A|²_F / |A|²_2 | 对尾部那一长串微小奇异值很稳健 |
| 有效秩 | 归一化 σ 上的 exp(H(p)) | “谱有多摊开” |
| 截断 SVD 重建 | 能解释 x% 质量的秩 r | 唯一要紧的，就是 MF 损失多少 |
| 谱衰减斜率 | 拟合 log σ_i ≈ −α log i | α 陡 = 低秩 |
两个陷阱
我见过的几乎所有“看，我们的图是高秩的”这类图，都错在这里。有两个混淆因素,随便哪一个都能在物品矩阵和社交矩阵之间凭空造出一个秩差,而它和"以查看者为条件"毫无关系。
第一个是稀疏性。物品矩阵和社交矩阵很少在同一个密度下被观测，一个物品目录里每件物品可能有几十次交互，一张社交图里每个节点可能只有寥寥几次，而单是稀疏性就会抬高有效秩。公平的比较必须把密度固定住，通常是把更密的那个矩阵下采样到更稀疏的那个的密度，或者只在已观测条目子矩阵上度量。不这么做，你量到的一部分是"你有多少数据"，而不是"数据长成什么样"。
第二个更隐蔽，是流行度。一个交互矩阵的最大奇异值，一阶近似地说，就是流行度，少数几个高度连接的节点、少数几件高度连接的物品把它整个主导了。一个矩阵可以纯粹因为度数分布偏斜而显得低秩，底下根本没有任何低秩潜在结构。在大规模跑这些系统的人对此心知肚明；Meta 的 RankGraph 工作在做任何事之前都会先做显式的流行度偏差校正，那不是装饰。[2] 诚实的量法是先把流行度残差化掉，拟合一个纯查看者与候选流行度的秩一模型 \(R \approx u d^\top\)，减掉它，再量剩下部分的秩。
上一篇的那个论断，必须挺过这一道残差。如果你把流行度拿掉之后，社交谱就塌得和物品谱一样了，那"高秩"从来就不是以查看者为条件，而只是度数的异质性，论断就死了。我见过太多没做这一步就摆出来的谱图，以至于我现在对任何一张，第一遍都不再信了。
两个会在物品矩阵和社交矩阵之间伪造秩差的东西：
| 混淆因素 | 它干了什么 | 修复 |
|---|---|---|
| 稀疏性 | 更密的物品 vs 更稀的社交，抬高有效秩 | 在匹配密度下比较（下采样更密的那个） |
| 流行度 | σ₁ 就是度数偏斜；光靠流行度就能让矩阵显得低秩 | 先残差化 R ≈ ud^T，再量残差的秩 |
一锤定音的那张图
有一个比读谱更干净的检验，而且是我真会去跑的那个。别再看矩阵了，看模型。
拿一个矩阵分解模型，或者一个序列模型，选哪个差别不大，在物品数据集和社交数据集上、分别用越来越大的嵌入维度 \(d\)（比如 \(\{8, 16, 32, 64, 128, 256\}\)）去训练，把一个留出集指标（Recall@K、NDCG@K）对 \(d\) 画出来。预测很具体：物品那条曲线会饱和，一旦 \(d\) 大到装得下低秩结构它就平了，再加维度没用；而社交那条曲线，用同一个模型，会一直往上爬，或者在你买得起的任何维度内都不饱和。
这张图之所以一锤定音，是因为它用的是唯一要紧的那种货币，模型表现，并且它把抽象的秩论断绑到了你真去拧的那个旋钮上。顺带，它还是一个证伪检验。如果社交曲线和物品曲线饱和得一样早，那么对这个数据集，问题本来就是低秩的，上一篇的框架不适用，再多的谱上花拳绣腿也救不回来。一个论断如果连自己的实验都证伪不了它，那它其实就不算个论断。
为完整起见，能把这件事判死的全部情况列一下：一个低秩模型在社交数据上追平了一个以查看者为条件的模型；做过流行度残差化之后，社交谱衰减得和物品谱一样快；以及指标对 \(d\) 的曲线在两个领域里饱和得一样快。把它们当成实验纲领，而不是装饰。这个论断成不成立，取决于这些情况在真实数据上是否一个都不出现；而那份文献几乎从不碰的、度数 500 的生产图，恰恰是我预期它们不会出现的地方。
但"高秩"仍然在矩阵之内
这一节，我花在消化上的时间比其余所有加起来都长。即便你把上面那些全跑了一遍、答案是"对，高秩"，你仍然站在一个对这个问题来说太小的框架里。
一个矩阵条目 \(R_{vc}\) 断言了一件具体的事：\(c\) 对 \(v\) 的相关性，只是 \(v\) 和 \(c\) 的函数，一个双线性形式。社交相关性却经常违反它。我想不想去连一个人，取决于还有谁把我们连在一起，而那是矩阵里放不下的第三方。它取决于我们之间的路径，两跳还是三跳、闭合的还是敞开的三角，而一个标量条目把这些全压扁了。它取决于边的类型（关注不是友谊，友谊不是拉黑），还取决于时间和上下文，而这一切，一张静态的二维矩阵不展开成更大的东西就表达不了。
要看清矩阵把这个问题描述得有多糟,最干净的角度是三角。好友推荐里最强的信号是三元闭合–朋友的朋友–这是某个具体的、身份至关重要的第三方。一张二分图根本容不下一个三角,它没有奇环。这不是“物品推荐和社交推荐为什么不同”的一个巧合，这就是原因本身。最强的社交信号活在一个物品推荐拓扑在结构上被禁止拥有的 motif 里,这也正是为什么手工算出来的图特征,在链路预测基准上一直打败点积嵌入:Adamic-Adar、共同邻居数、个性化 PageRank,都不是这对节点的函数,而是这对节点周围那张图的函数,而信号真正住的地方,就是这对节点周围那张图。
有一条完整的研究脉络是认真对待"矩阵不够用"的，张量分解，把交互建模成 \((用户, 物品, 上下文, 时间)\) 上的一个 \(d\)-模张量、而不是二维矩阵，[3] 还有超图方法，其中一条边可以一次连接两个以上的节点。这些才是诚实的终点。它们也都很贵，对十亿节点并不友好，所以几乎没人在生产里跑它们，“你可能认识的人"系统至今仍在手工算结构特征、喂给排序器。
真正的解法在哪一层
所以这片地形上有三个位置，值得说清楚你站在哪一个。
最底下是全局低秩分解，每个节点一个共享嵌入、一个固定的点积。这是物品推荐天然的归宿，在那里它够用，因为结构确实是低秩的。
最顶上是完整的高阶对象，张量、超图、手工算的图特征。信号真正住的地方，也是唯一一个能不耍花招地表达"第三方依赖"和"三元闭合"的框架。而在社交图的规模上，它作为一个端到端模型，差不多是负担不起的。
中间，是我想为之辩护的那一步，而我想小心地说清楚它是什么、不是什么。如果同一个候选必须对每个查看者是不同的向量，你可以让候选嵌入只在它真正稳定的部分保持与查看者无关，它的结构指纹、它连接的方式，而把那个依赖查看者的部分，放进一个小算子里，为每个查看者重新投影这个指纹。这个算子并没有逃出矩阵，它在查看者和候选之间仍然是双线性的，而且它也并没有把秩天花板抬高。把这个算子穿过内积推过去，它落在查看者那一侧、而不是候选那一侧，剩下的仍然是每个查看者一个 \(d\) 维向量、对每个候选一个 \(d\) 维向量，所以分数矩阵的秩仍然至多是 \(d\)，无论你把逐查看者的秩 \(r\) 取成多少。第三篇会把这个恒等式推出来，而那条给秩封顶的式子，恰恰就是让这套设计上线时便宜的那一条。这个算子买到的不是更多的秩，而是把你本来就有的那 \(d\) 个维度花得更好：查看者的向量不再是查找表里自由的一行，而变成了查看者自身结构的一个函数，冷启动、跨查看者的泛化、以及不随查看者数量增长的存储，全都是从这里来的。真要把天花板抬起来是另一回事，那意味着放弃单个内积，而那已经把你放到了这片地形的顶层、不是中间层。
这片地形，三个位置：
| 位置 | 秩模型 | 规模代价 | 抓得到 B 轴？ |
|---|---|---|---|
| 全局低秩（MF） | 一个共享 d | 便宜 | 否 |
| 逐查看者投影 W_v | 仍是一个共享 d（查询向量由生成得来） | 便宜（查询侧） | 否，只有软邻近 |
| 张量/超图/图特征 | 完整高阶 | 贵 | 是，终点 |
这是个克制的论断，我也想让它保持克制。以查看者为条件的投影不是终点，终点是高阶结构，而任何告诉你"一个聪明的嵌入技巧就能替代图特征"的人，都是在推销东西。它是一块可扩展的中间楼层：一种在"你有十亿个查看者、而相关性函数对每个查看者都换一个形状"这个特定场景下、不必付完整张量的代价、把双线性框架里查看者那一侧从结构生成出来、而不是从查找表里取出来的办法。把这块楼层搭起来，并诚实地说明它止于何处，是下一篇的事。
注释
[1] 把有效秩定义为奇异值谱的熵，可追溯到 Roy & Vetterli；同一个量在低秩适配文献里以"稳定秩"或"数值秩"的名字到处出现，用来问一个适配矩阵究竟加了多少有用方向。
[2] 在十亿规模图学习里把"流行度偏差校正"作为头等公民的一步，见 Meta 的 RankGraph 系列工作：它把几十万亿条边压到几千亿，部分靠的就是在任何事之前先校正度数偏斜。残差化这个技巧，拟合并减去一个秩一的流行度模型，是同一思想在单节点上的版本。
[3] 把上下文当成额外张量模来处理的经典参考是 Karatzoglou 等人的 “Multiverse Recommendation”（RecSys 2010），它报告称相对非上下文矩阵分解有最高 30% 的提升；“用户–物品矩阵这个框太小"这个更全面的论点，见 Shi、Hanjalic 的 “Collaborative Filtering beyond the User-Item Matrix”（ACM Computing Surveys, 2014）。