你可能认识的人：难的不是猜得准，是先把十亿人砍到一万个

一句话

这一章把「好友推荐」翻译成图上的链接预测（link prediction）：给定当下的社交图，预测哪两个还没连上的点会在未来连上。你以为难点是模型选型，其实难点在它前面一步——十亿用户两两配对是 10¹⁸ 量级，任何模型都没资格给它们打分。这一章真正的骨架是：先用二跳邻居把候选压到 10⁴，再谈特征，最后才谈模型。

Glossary · 术语表

坐标

ML 系统设计面试 Part II「十道真题」的最后一道，也是全书唯一一道输入是一整张图、而不是一批彼此独立的样本的题。它上承 Ch9 相似房源（从共现关系学嵌入）与 Ch10 信息流（候选 + 排序的漏斗结构），把这两条线合到图上。对应现实里的 LinkedIn「你可能认识的人」、Facebook 的同名功能、X 的 Who to Follow。

这章要解决什么

先把规模摆出来。十亿量级的用户，人均好友数在几百这个量级。把所有用户两两配对是 n(n−1)/2 ≈ 5×1017 对；就算一对只花 1 微秒，也要一万多年。「给每一对打分」这个框架从一开始就是错的，这是本章和前十章最大的结构差别：前面几章的候选池是天然有界的（一个人的信息流、一个视频库），这一章的候选池是用户数的平方。

另一头的压力来自产品：社交产品普遍把「新用户在 N 天内建立 K 条关系」当激活的核心指标。注册完看到一片空白基本就流失了——而新用户恰恰是图上完全没有位置的那批人。

所以这一章要同时解决两件事：怎么把候选集从 10¹⁸ 砍到能算的量级，以及在这个砍完的集合里怎么排序。前者决定了系统能不能跑，后者决定了效果好不好。

核心内容，讲透

一、先把问题写对：时间切片打标签

最容易犯的错是用当前的图去预测当前的图——你要预测 u 和 v 会不会成为好友，却在算特征时用了「u 和 v 之间已经有边」这个事实，那是标签泄漏（label leakage），离线指标会漂亮得离谱，上线一片死寂。

正确做法是时间切片：取 t 时刻的图快照算特征，把 t 到 t+Δ（比如两周到一个月）之间新增的边当正样本。负样本从「t 时刻还没连上的二跳候选」里采——不能从全体用户里随机采：随机两个人几乎必然不认识，模型学会「默认说不认识」就能拿 0.99 的 AUC，却学不到任何有用的区分力。负样本必须和正样本来自同一个候选池，这叫 hard negative。

二、候选生成：二跳邻居，10¹⁸ → 10⁴

依据是三元闭包：现实中的新好友，绝大多数是通过已有好友认识的。所以只取二跳邻居当候选。规模估算很直观——度为 d 的用户，二跳邻居的量级是 d²（去重后更小）：d ≈ 300 时是 10⁴–10⁵，相比 10¹⁸ 砍掉了十几个数量级。

代价必须写清楚：凡是和你没有任何共同好友的人，永远进不了候选。刚搬到新城市、刚换行业、刚注册的用户全在这个盲区里。所以二跳邻居只能当主候选源，旁边必须并联几路「非图」候选：同学校同专业且年份重叠、同公司同期在职、通讯录/邮箱导入、同城同群组。这几路的作用不是提升精度，而是给图上还没有位置的人一个入口。

三、把「共同好友」做对：Adamic-Adar 与边权

朴素的排序信号就是共同好友个数，谁多推谁。它好用得惊人，但有个致命缺陷：hub 节点——那些手握五千好友的招聘、网红、销售账号。他们让无数互不相干的人凭空拥有「1 个共同好友」，信号被稀释成噪声。

修正办法是 Adamic-Adar：AA(u,v) = Σ 1/log(deg(w))，其中 w 跑遍所有共同好友，deg(w) 是这个中间人自己的好友数。白话就是：每个中间人按他自己朋友数的对数取倒数打折，朋友越多的中间人，那一票越不值钱。

要诚实的一点是：这个折扣是对数级的，不是线性的——5000 好友的 hub 贡献 0.12，30 好友的贡献 0.29，只差 2.4 倍，hub 被削弱但没被抹掉。工业界往往还要额外加一条硬规则：度超过某个阈值的节点直接不进二跳展开，否则光是它的邻居表就能把候选集撑爆。

再往上一层是边权：好友关系不是 0/1——有互动的边远强于加完就再没说过话的边。把共同好友按两侧边强度加权，收益通常大于换一个更复杂的模型。

四、三代模型：规则 → 有监督分类 → 图神经网络

第一代，纯规则：直接按 AA 分数排序。零训练成本、完全可解释、新用户一有边就能用。它是任何 PYMK 系统的正确起点，也是所有后续模型必须打败的基线——很多团队的第一版 A/B 就输给了它。

第二代，pointwise 有监督分类：把候选对 (u,v) 当一条样本，喂三族特征——图特征（共同好友数、AA、最短路、两人各自的度）、属性特征（同校同司且年份重叠、同城、年龄相近、语言）、交互特征（是否访问过对方主页、停留多久、是否被同一个人同时提及）——用逻辑回归或梯度提升树输出 P(会连边)。这是工业界最长寿的方案：好调、好解释、能上线。它的天花板在于图结构只能以人工特征的形式进入模型，二跳以外的结构信息全丢了。

第三代，图神经网络，也是原书推荐的终点。机制用白话讲：每个人先把自己的属性写成一张卡片；第一轮，每个人把卡片发给所有好友，各自把收到的一叠卡片揉成一张新卡片；第二轮再传一次——此时你手上这张卡片已经同时编码了你自己、你的朋友、以及你朋友的朋友是什么样的人。这张卡片就是节点嵌入 z。预测就一步：P(u,v) = σ(z_u · z_v)，两个向量做点积再压成概率。

GNN 的代价同样具体：全图放不进显存，训练要做邻居采样（每层只随机取若干个邻居）；推理要把全量嵌入预先算好缓存，图一变嵌入就旧了；hub 节点的邻居采样天然有偏；而且出了问题几乎没法像 GBDT 那样看特征重要度定位。它赢的是那部分「没有共同好友、但朋友圈整体形状相似」的信号——这部分恰恰是二代模型的盲区。

五、离线预计算 + 在线取：PYMK 不是实时打分

关键观察：社交图变化极慢——一个活跃用户一天新增的边大概 0 到几条。所以整条链路都能搬到离线：批任务定期为每人展开二跳、算特征、打分、截断 Top-K，写进 KV 存储；线上只做一次 get 加过滤（已好友 / 已忽略 / 已屏蔽），几十毫秒返回。模型多重都不影响线上延迟——这是本章最省事、也最容易被面试者漏掉的一步。

例外只有一个：刚注册、刚导入通讯录、刚加了第一批好友的用户，必须立刻看到结果。这类用户走触发式增量重算——图上他那一小块子图很小，单独算一次并不贵。

关键权衡与选型

第一张表回答「候选从哪来」。注意最后一列——没有任何一路能独当一面，二跳邻居覆盖率最高却恰好盖不住最需要推荐的新用户。

第二张表是模型选型：三代方案不是替代关系，成熟系统通常是「规则兜底 + 监督主力 + GNN 补盲区」并存。

还有一个不在模型里的权衡，面试里最能拉开差距：目标该定成「会不会认识」还是「会不会发出邀请且被接受」。后者才是产品要的，而且是双边事件——推得准但对方不接受，换来的是邀请疲劳：被打扰方开始忽略全部邀请，大盘接受率一起下滑。所以线上目标通常取「发出 × 被接受」，还要看两周后这条边是否仍有互动。

为什么重要 / 落到真实系统

面试里说「用 GNN 做链接预测」是零分答案。得分点是四句话：先谈候选集再谈模型（10¹⁸ 打不动）、标签必须时间切片（否则泄漏）、负样本必须从候选池里采（否则 AUC 虚高）、整条链路默认离线预计算（图变得慢）。架构评审里同理：真正的成本不在模型推理，在每天那次全量二跳展开。

易错点与争议

• 标签泄漏：用当前图算特征、又用当前图里已存在的边当标签。离线 AUC 会高到 0.99，上线归零。必须时间切片。
• 负样本采错：从全体用户随机采负样本，等于让模型做「这两个人是不是随机的两个陌生人」这道送分题。负样本要和正样本同源——从二跳候选里采。
• 只数共同好友不看 hub：不做度归一化，排前面的会是一堆「和某个五千好友的招聘号有共同好友」的陌生人。
• 用离线 AUC 判优：真正的指标是邀请发送率 × 接受率，且要看留存——推得准但没人发出邀请，等于没做。
• 反馈闭环：PYMK 造出来的边会变成下一轮的训练数据和二跳结构，hub 越连越大，富者愈富。这需要在候选阶段主动做度惩罚与多样性约束，模型自己纠不过来。
• 隐私争议：PYMK 最真实的风险，也是原书讨论最轻的地方。图知道两个人有关系，却不知道这段关系为什么不该被第三方看见——通讯录导入与共同好友都可能把用户刻意分隔的两个身份接通。这是产品边界问题不是精度问题，只能靠候选源准入与用户可控的屏蔽来兜，没有模型解。
• 时代局限：原书以 GNN 收尾，没展开实时图那条线（GraphJet 式的滑动窗口索引），也没细讲嵌入检索与二跳候选如何并存、嵌入过期后按什么节奏重算。

要点