SimRank — 两个节点相似当且仅当它们的邻居相似

是什么

SimRank 是一套只看图的连接方式、就能算出”两个节点有多像”的算法。日常类比：判断两个人是不是同一类，不看他们本人长什么样，只看他们朋友圈是不是高度重合——朋友重合度高，就说这俩人很像。

核心一句话：两个节点相似，当且仅当它们的邻居也相似（递归定义）。

2002 年 Stanford 的 Glen Jeh 和 Jennifer Widom 在 KDD 发了这篇 9 页论文。和同实验室前辈 PageRank 是亲戚——PageRank 给单个节点打分，SimRank 给”节点对”打相似度。

为什么重要

不理解 SimRank，下面这些事都说不清：

推荐系统里”看了 A 也看了 B”的召回为什么不能只用余弦——文档没有内容向量时怎么办
引文网络里”这两篇论文研究方向接近”——它们没共同关键词，怎么判定
图嵌入（DeepWalk / node2vec）的”相似度”到底来自哪——很多目标函数本质是 SimRank 的近似
实体消歧（“张三”是不是同一个张三）— 看不到内容，看人际网络

PageRank 解决”哪个页面重要”，SimRank 解决”哪两个页面像”。这两个问题在图上同样基础。

核心要点

SimRank 的定义就一行公式，但理解需要拆三步：

基础情形：节点和自己的相似度永远是 1。s(a, a) = 1。
递归情形：两个不同节点 a, b 的相似度，等于”它们各自的入邻居两两相似度的平均”，再乘一个衰减因子 C（通常取 0.6-0.8）。

公式：s(a, b) = C / (|I(a)| × |I(b)|) × Σ s(Iᵢ(a), Iⱼ(b)) 其中 I(a) 是指向 a 的所有节点集合。
为什么要衰减 C：不衰减就会算出”所有相连节点都相似度 1”，公式失效。C 让”隔得越远的相似度越弱”，类似 PageRank 的阻尼系数。

直觉解释（论文里给的）：想象两个随机游走的人，从 a 和 b 同时出发，每一步沿入边反向走一步。他们俩在图上相遇的期望时间越短，a 和 b 就越相似。这个相遇时间的期望值，就是 SimRank。

为什么”反向走入边”？因为入边代表”被谁指向”，即谁认可我。两个人被同一群人认可，那他们在角色上就接近——这是论文整个直觉的根基。

收敛性保证：论文证明这个递归方程有唯一解，迭代 5-6 轮就基本稳定。可以从全 0 出发也可以从全 1 出发，最终收敛到同一组数。这点和 PageRank 的不动点迭代如出一辙。

实践案例

案例 1：两篇没有共同作者的论文为什么算”相似”

引文网络里：

Paper-A 被 P1, P2, P3 引用
Paper-B 被 P2, P3, P4 引用

A 和 B 没引用过对方，也没共同作者。但 SimRank 一算：它们的入邻居 {P1,P2,P3} 和 {P2,P3,P4} 重合度高（共有 P2, P3），所以 A 和 B 高度相似。

这就是 SimRank 的力量——纯结构信号，不需要任何内容。

案例 2：迭代怎么算（5 行 Python 直觉版）

def simrank(graph, C=0.8, K=5):
    nodes = list(graph)
    s = {(a,b): 1.0 if a==b else 0.0 for a in nodes for b in nodes}
    for _ in range(K):  # 通常 5-6 轮就收敛
        new = dict(s)
        for a in nodes:
            for b in nodes:
                if a == b: continue
                Ia, Ib = graph.in_neighbors(a), graph.in_neighbors(b)
                if not Ia or not Ib: continue
                new[(a,b)] = C/(len(Ia)*len(Ib)) * sum(s[(i,j)] for i in Ia for j in Ib)
        s = new
    return s

不动点迭代——每一轮都用上一轮的 s 算下一轮。论文证明它必然收敛，且收敛值唯一。

案例 3：推荐系统里的召回

电商场景，没有商品文本描述，只有”用户-商品”二部图：

用户 U1 买过 {A, B, C}
用户 U2 买过 {B, C, D}

SimRank 算出 A 和 D 有相似度（都被相似用户买过），就能做”买了 A 推荐 D”的召回。协同过滤的图论版。

很多工业推荐系统的”i2i 召回”（item-to-item）底层就是 SimRank 的变种。

案例 4：和 PageRank 算同一张图，结果完全互补

同一个网页超链图：

PageRank 输出：{页A: 0.3, 页B: 0.1, 页C: 0.05, ...}——每页一个标量
SimRank 输出：{(A,B): 0.7, (A,C): 0.2, (B,C): 0.6, ...}——每对一个标量

PageRank 告诉你”哪个页面最重要”（搜索结果排序），SimRank 告诉你”用户看了 A 还应该看哪个”（相关推荐）。Google 之后 20 年这两个信号一直并行用。

踩过的坑

暴力实现是 O(n²) 空间：n 个节点要存 n² 个相似度对。100 万节点 = 1 万亿对，单机存不下。论文之后十几年的工作都在做近似（采样、矩阵分解、Top-k 截断）。
冷启动节点相似度恒为 0：没入邻居的节点（孤立点 / 新加入），公式分母为 0。论文里直接定义为 0，工程上要单独处理新节点。
衰减 C 调不对效果差很多：C 太小（0.3）相似度衰减太快、几乎所有节点都接近 0；C 太大（0.95）远距离节点也被算成相似。多数实践取 0.6-0.8。
不能直接处理带权 / 带类型的边：原论文假设无权无类型图。SimRank++（2008）把权重塞进去，P-Rank（2009）把出边也算上。原版 SimRank 工业落地经常需要这些扩展。
“对称”看起来对、其实容易混：s(a,b) = s(b,a) 成立，但计算时不要只算上三角再镜像——迭代过程中两边数据要同步更新，不然收敛会出问题。

适用 vs 不适用场景

适用：

引文网络、社交网络、网页超链网络——纯结构相似度
推荐系统 i2i 召回——只有交互、没有内容时
实体消歧 / 链接预测——靠邻域结构判断
图嵌入预训练目标的设计灵感

不适用：

节点本身有丰富特征（文本 / 图像 / 数值）→ 用salton-vsm-1975 余弦或图神经网络更直接
超大图（千万级以上节点）→ 原版 O(n²) 跑不动，需要近似算法（SimRank*、 TopSim）
边带权重 / 类型 → 用 SimRank++ / P-Rank 扩展版
需要在线实时更新 → SimRank 是批量算法，节点新增要全量重算

历史小故事（可跳过）

2002 年：Glen Jeh 在 Stanford 跟着 Jennifer Widom 做博士，研究网页和引文网络。同实验室隔壁组（Page, Brin）2 年前刚把 PageRank 商业化成 Google。Jeh 想：PageRank 给每个节点一个标量分，那”节点对”的相似度有没有同样优雅的递归定义？
答案就是这篇 KDD 2002，9 页，公式只有一行，却引出之后 20 年几百篇近似算法、扩展、工业系统。
2014 年：Yu, McCann 等用矩阵形式重写 SimRank，证明它本质是一个 Sylvester 方程的解，给了快速近似算法的数学基础。
现在：图神经网络（GraphSAGE, GAT）的目标函数里能看到 SimRank 的影子——“邻居像我才像”是图学习最朴素的归纳偏置。

学到什么

递归定义在图上是个强武器——PageRank（重要性递归）、SimRank（相似度递归）、HITS（权威/枢纽递归）都是同一类思想
结构信号 vs 内容信号：当内容缺失或噪声大时，“谁连着谁”比”内容写了啥”更可靠
不动点迭代 + 衰减因子是图算法的常见套路：保证收敛 + 保证唯一解
理论简洁、工程复杂：一行公式，但 O(n²) 让 20 年的论文都在做近似

关联

pagerank-1998 —— 同 Stanford 同实验室；PageRank 排”节点重要性”，SimRank 排”节点对相似度”
salton-vsm-1975 —— 内容向量余弦相似度；SimRank 是它的”图结构版”补充
okapi-bm25-1994 —— 检索打分；和 SimRank 一起构成”内容 + 结构”双路召回的基础
akamai-2002 —— 同年代基础设施，SimRank 处理的网页图正是 Akamai 加速的对象