很多团队把 motif 当成又一个特征。跑一个图作业，拿到一堆三角形，像「共同好友数」那样挂到排序器上。这个做法把整个问题藏起来了。一条三角形从流水线里出来，是三个整数 node id，神经网络的排序器吃不了三个整数 id。从这三个整数到一个真正能给「人对人」打分的模型，中间隔着一层，而这层不是格式问题。真正的问题就住在这里，也就是我前面几篇一直在讲的那个：人不是 item，所以一个人的表示必须取决于谁在看。
三角形不是 embedding。
这篇是前面三篇的工程篇。前面我论证社交推荐之所以套不上 item 推荐那套，是因为「查看者-候选」矩阵是高秩的、是 viewer-conditioned 的，老实的修法是给一个 per-viewer 的投影 W_v，作用在一个结构指纹 E_c 上。这篇讲的是，在这套理论碰到线上系统之前，有两个不起眼的问题必须先解决，而它们都比理论本身更有意思。
这是两个问题，大家经常混成一个。第一，图有十亿节点、有度 500 的大 V，三角形到底怎么算出来。第二，三角形算出来之后，ranker 要的是向量，一个三角形怎么变成向量，「喂给排序器」这件事排序器并不支持。我按顺序讲，然后说明第二个问题恰好就是前面那几篇里 per-viewer 投影的具体落地。
把三角形从一张放不进单机的图里算出来
输入是边表，每一行是一条 follow。任务是找出每一个三角形（每一组互相连接的三个人），交给下游。朴素的算法是：对每个点，看它每一对邻居，查这对邻居之间有没有边。度 500 的点，单点就要 C(500, 2) ≈ 12.5 万次检查，图里只要有几个这种 hub，时间几乎全花在它们身上。更糟的是每个三角形会被数 6 次。
标准的修法是 degree ordering，年纪比在读这篇文章的大多数人都大。把所有点按度排序（度相同按 id），每条边重新定向，从低度端点指向高度端点。图就变成了一个有向无环图，因为每条边都严格指向「序更高」的点。然后只在每个三角形的最低度顶点上做枚举：对一个点 v，看它出边邻居的两两组合，查这对之间是不是边。每个三角形只被找到一次（全序有唯一最小元），工作量从大约 O(m·Δ)（Δ 是最大度）掉到幂律图上的 O(m^1.5)。这就是 NodeIterator++，界是 Suri 和 Vassilvitskii 给的。hub 永远不是 pivot，只有度小的点做枚举，它们便宜。把朴素算法打爆的星图，现在几乎不干活，因为中心是度最高的点，永远轮不到它当 pivot。
到这里都是单机。分布式那个坑是我自己踩的，值得讲清楚，因为大部分文章里没写。
Spark 上的自然做法是把定向后的边 hash 分区，在每个分区内做枚举。你会听到一个说法：「vertex-cut，复制因子降到 2」。这个说法讲的是存储，不是三角形的局部性，两者的区别很要紧。一个三角形 {v, u, w}（v 是最低度的，是 pivot），三条定向边是 v→u、v→w、u→w。如果你按 source hash 每条边，v→u 和 v→w 都落到拥有 v 的那个分区（因为它们的 source 都是 v），很好。但闭合边 u→w 的 source 是 u，落到拥有 u 的分区，几乎必然是另一台机器。pivot 的分区有两条腿，能看到 u 和 w 都是 v 的邻居，但确认不了 u 和 w 之间有边，因为那条边在别处。这个三角形对唯一有权发现它的分区来说是不可见的。
这不是换个好 hash 能修的。任何按单端点的 hash 都会把某些三角形拆到不同分区，因为三角形是个闭合结构，三条边互相 reinforcing。修法是放弃「worker 能在本地闭合三角形」这个幻想。让 worker 只做便宜、本地的部分：枚举开放的 wedge (v, u, w)，即 u 和 w 都是 v 出边邻居的那些。然后用一次 Spark join 闭合，把每个 wedge 按 (u, w) 去边表里匹配。两条腿是本地的，因为 degree ordering 让 pivot 成为两条腿的 source，而 hash-by-source 把它们放到了一起。那一条闭合边交给 join。三条边算清楚了：两条本地，一条 join。
worker 很小，又是热路径，所以做成 native sidecar，Spark 通过 stdio 把列数据喂进来。剥到只剩骨架：
// 一个分区的定向边，按 src hash。outAdj[v] 正好就是 N+(v)。
std::vector<Wedge> worker_emit_wedges(
const std::vector<int64_t>& srcs, const std::vector<int64_t>& dsts,
const std::vector<int32_t>& dst_degree, const std::vector<int64_t>& view_ids)
{
std::unordered_map<int64_t, std::unordered_map<int64_t, NbrInfo>> outAdj;
for (size_t i = 0; i < srcs.size(); ++i)
outAdj[srcs[i]][dsts[i]].views.insert(view_ids[i]);
std::vector<Wedge> out;
for (const auto& [v, nbrMap] : outAdj) {
std::vector<std::pair<int64_t, NbrInfo>> nbrs(nbrMap.begin(), nbrMap.end());
for (size_t i = 0; i < nbrs.size(); ++i)
for (size_t j = i + 1; j < nbrs.size(); ++j) { // 每对只一次
// 把 {u,w} 规范成边表的 (低度, 高度) 方向
int64_t u, w;
if (nbrs[i].second.degree != nbrs[j].second.degree
? nbrs[i].second.degree < nbrs[j].second.degree
: nbrs[i].first < nbrs[j].first) {
u = nbrs[i].first; w = nbrs[j].first;
} else { u = nbrs[j].first; w = nbrs[i].first; }
out.push_back({u, w, v, /*两条腿的 view*/});
}
}
return out;
}
闭合就一次 join，不需要任何图基础设施：
-- wedges(v, u, w) 来自 worker；oriented 是度序 DAG
SELECT wed.v, wed.u, wed.w
FROM wedges wed
JOIN oriented e ON e.src = wed.u AND e.dst = wed.w; -- 唯一的那次 join
这个版本能扛十亿节点。大家会去摸的另一条路是：在图上跑 node2vec 或者某种 random-walk tokenizer，让 Transformer 自己把 motif 学出来。这条路在同样的图上死掉，原因不是审美，是算术。在度 500 的点上，一次无偏游走回到上一个点的概率是 1/500；走 12 跳一次都不回头的概率是 (499/500)^12 ≈ 97.6%。采 100 条 walk，97 条是同一条直链 [0,1,2,...,11]，tokenizer 当年发明出来要找的菱形子结构基本不会出现。我跑过，就是这样。tokenizer 那些论文验证用的是分子图（平均度 3）和引用图（平均度 7），那种图上你走一步就撞上一个三角形；社交图上三角形是有的，但游走会从它们旁边滑过去。
所以枚举这一段不是你耍深度学习的地方。这一段是你要尊重度分布、付 O(m^1.5) 而不是 O(m·Δ)，并接受闭合边值一次 join。
一个三角形变成了什么
现在是更难、更有意思的问题。流水线给你 (v, u, w)，ranker 要的是向量。问题是怎么转换，而那些显然的答案都是错的。
显然的答案是给每个 node 一个学出来的 embedding，完事。这是 item 推荐那套隐含的路，也是这条路失败的原因，原因正是这一系列前面讲的：每人一个静态向量，表示不了「同一个候选在不同查看者眼里是不同的人」这件事。三角形正好是暴露这一点的结构。三角形说「这三个人构成一个闭合的小团体」，而这个团体是哪个团体、对其中两个人该不该连起来意味着什么，取决于第三个人是谁、取决于谁在问。
转换分两层，很容易混。
第一层，把一个三角形里 3 个 node 的 embedding 融合成一个三角形 embedding。第二层，把一个点参与的所有三角形，融合成这个点的指纹。大家听到「在 motif 上做 DeepSets」，会以为 DeepSets 是在第一层、在融那 3 个 node。不是。第一层就是对 3 个 node embedding 取个 mean（无向三角形的三个顶点是可互换的，对称融合才是正解，在 3 个元素上玩花的收益很小）。DeepSets 在第二层，把一个点的多个三角形融成一个指纹 E_c。
E_c 是候选的结构指纹。它编码这个候选在多少个三角形里、是哪种三角形，这也是一个人身上唯一稳定的信号（人没有 item 那种内容语义，人的语义就是它的拓扑）。E_c 是名词，是静态的，它对查看者一无所知。
查看者从算子那里进来。查看者有自己的指纹 f_v，由完全相同的两层流水线、跑在查看者的三角形上得到。一个小超网络读 f_v，吐出一个低秩残差 (U_v, V_v)。per-viewer 的算子是 W_v = I + U_v V_v^T，打分是 ⟨a_v, W_v E_c⟩，其中 a_v 是从 f_v 导出的查询向量。候选指纹是名词，从查看者指纹生成的算子是动词。查看者的三角形从来不直接碰候选，它们塑造的是那个去重投影候选的算子。
为什么是 I + U_v V_v^T 而不是一个完整的 d×d 矩阵，因为完整矩阵在十亿规模上是不可能的。d = 128、十亿查看者，一个 per-viewer 矩阵是 64 TB。低秩残差每个查看者只存 2dr 个数，d = 128、r = 8 的时候是 2 KB，这和 LoRA 在微调大模型里能 work 是同一个道理。能上线的关键是那个 serving 技巧。你不想对每个候选都把 W_v 乘上去，那就废了候选表存在的意义（双塔检索）。所以把算子挪到查看者这边：
score(v,c) = ⟨ a_v , W_v E_c ⟩
= ⟨ a_v + V_v (U_v^T a_v) , E_c ⟩
= ⟨ z_v , E_c ⟩
z_v 每个查看者花 O(dr) 就算出来，候选表 E_c 保持静态，serving 就退化成拿 z_v 对着候选表做一次标准的最近邻查找。算子是真的、是作用在候选上的，但在 serving 的时候候选完全不需要知道它存在。
整个 ranker 的代码很短，训练和 serving 跑同一个 forward：
class MotifProjectionRanker(nn.Module):
def __init__(self, n_nodes, d, r, use_motif=True, pooling="deepsets"):
super().__init__()
self.proj = ViewerProjection(d, r)
if use_motif:
self.tri_enc = TriangleEncoder(n_nodes, d_id, d_motif) # 第一层: mean
self.fp = MotifFingerprint(d_motif, d, pooling) # 第二层: 聚合
else:
self.id_table = nn.Embedding(n_nodes, d) # baseline: 不用 motif
def forward(self, ftab, viewer_ids, cand_ids):
f_v = ftab[viewer_ids] # 查看者指纹
E_c = ftab[cand_ids] # 静态候选表
z_v = self.proj.query_vec(f_v) # z_v = a_v + V_v(U_v^T a_v), O(dr)
return (z_v * E_c).sum(-1) # <z_v, E_c> = <a_v, W_v E_c>
这个构造函数里藏了一个消融，值得停一下讲，因为它最干净地说出了投影到底值多少。把 r 设成 0，W_v 就退化成单位阵，打分变成 ⟨a_v, E_c⟩，也就是朴素的矩阵分解。把 use_motif 关掉，E_c 就变成一个裸的、学出来的 id 表，里面没有任何三角形结构。这两个开关张成一个小网格，孤立投影贡献的那个格子，是不用 motif、r > 0 的那个：一个学出来的 id 表，只通过 W_v 对查看者敏感，没有任何图编码。如果这个格子能涨指标，那涨出来的部分就是投影的，不是别的。然后把 motif 开回来，量一量结构指纹在上面再加多少。这才是能告诉你「这套东西到底值不值」的实验，而大多数「我们加了图特征」的论文跑不了这个实验，因为它们根本没造过没有图特征的那个版本。
我预期什么，不预期什么
第二层的聚合有三个档：sum、deepsets、attention，构成一条表达力的阶梯：线性聚合，加一个逐元素非线性，再加元素间交互。我预期 attention 比 deepsets 略好，deepsets 比 sum 略好，而且好得不多，因为每个三角形的 embedding 已经够丰富，在丰富的元素之上玩更花的聚合，边际通常不大。更大的杠杆是查看者算子的秩 r，以及到底要不要开 motif。
有一个升级我不觉得会来自聚合，但它才是第一层真正要紧的东西，而且它不是 attention。第一层丢掉的是角色信息：在一个三角形里，degree ordering 让一个点当 pivot（度最低）、一个当中间、一个当最高，朴素的 mean 不记录谁是谁。在 3 个可互换的元素上做 attention 找不回这个。能找回来的是把 degree ordering 的角色作为显式的 role embedding 灌进去，让三角形编码器知道「这个候选是这个三角形的 hub」和「这个候选是这个三角形的叶子」是两件不同的事。这才是第一层有意义的改进，它现在还在 to-do 上，不在聚合那条轴里。
我想老实说一下 headroom 到底在哪，因为写这种文章的诱惑是吹过头。枚举不是排序上的改进，它是你为了拥有结构特征而付的代价，替代方案（random-walk tokenizer）在我跑的那种图上不 work。结构指纹和 per-viewer 投影才是任何指标涨幅住的地方，而这个涨幅有一个上限：友谊的形成里到底有多少是被局部拓扑驱动的，而不是被活动和时机驱动的，三角形看不到后两者。三元闭合是好友推荐里最强的单一信号，所以这个上限是宽裕的，但它是个上限。造消融网格的意义，是把这个上限量出来，而不是断言它。
这个东西的形状
更深的那条主张是前面几篇里的，这里不重新推导。人不是 item。item 有稳定的内容语义，所以一个 item 一个 embedding 是合理的对象，用户-item 矩阵是低秩的。人没有稳定的内容语义，人的语义是它的图，而相关的图对每个查看者都不一样，所以一人一个 embedding 是错的对象，「查看者-候选」矩阵是高秩的。per-viewer 算子 W_v 的活，是让候选变成查看者的函数，又不给每个查看者存一个完整矩阵；结构指纹 E_c 的活，是给这个算子一个老实的、编码的是边而不是兴趣的东西去作用。
这篇补的是前面几篇略过去的那部分。指纹得有个来处，这个来处是一条流水线：它靠 degree ordering 在大规模上枚举三角形、并接受一次 join，然后再经两层融合成一个向量。理论说你需要 E_c 和 W_v。这篇讲的是 E_c 是拿什么做的，以及让 W_v 能上线的工程。一个三角形是三个整数。剩下的活，是把这三个整数变成一个知道是谁在问的排序器。
注释
[1] 三角形枚举里的 degree ordering 和「每条边 O(m^1/2)」（总共 O(m^3/2)）的工作量界，可以追溯到 Schank 和 Wagner 的实验研究，在 MapReduce 场景下被 Suri 和 Vassilvitskii 的《Counting Triangles and the Curse of the Last Reducer》（WWW 2011）讲得很干净。「最低度的点负责」就是他们的 NodeIterator++。
[2] 把低秩残差 I + U V^T 当 per-viewer 算子，是 LoRA（Hu 等，2021）的搬用；恒等式 ⟨a_v, (I+UV^T)E_c⟩ = ⟨a_v + V(U^T a_v), E_c⟩ 是它能作为双塔查找上线的关键。同样的残差形式在推荐里以 per-user 投影出现过（McAuley 等，CIKM 2015；RecLoRA，2024），不过它们都没有论证这一系列在讲的结构必要性那个版本。
[3] (499/500)^12 ≈ 97.6% 是在度 500 的点上、12 跳无偏游走一次都不回到上一个点的概率。退化成直链，是 random-walk motif tokenizer（G2PM 那一类）从分子图和引用图迁移到社交图上、不做重度有偏采样就 work 不了的原因；就算做了，游走也在和度分布较劲，而不是在把它读出来。