相似性与同构：两个图/节点有多像？

前几篇文章中，我们学会了探索一张图的内部结构——BFS/DFS（Art. 1）让我们系统地遍历图，连通性（Art. 2）让我们知道图是否完整，最短路径（Art. 6）和中心性（Art. 7）帮我们度量节点的距离和重要性，社区发现（Art. 8）帮我们找到节点的群组结构。但有一个关键问题一直没触及：两个节点有多像？两张图有多像？两张图是否本质上是同一张图？

这些问题在实际应用中无处不在。推荐系统需要判断哪些用户”相似”来做协同过滤；知识图谱需要预测缺失的边（链接预测），核心是评估两个实体的相似度；药物发现需要比较分子图的结构相似性；化学信息学需要判断两个分子是否是同一种物质（图同构）。

本文的核心问题：怎么量化两个节点之间、两张图之间的相似性？怎么判断两张图的结构是否完全相同？

算法范式：穷举搜索（VF2）、消息传递（WL test）、回溯+剪枝（VF2）、迭代逼近（SimRank）

核心思路：从局部邻域到全局结构

我们将问题按粒度分为三个层次：

节点相似性：给定同一张图中的两个节点 $u$ 和 $v$ ，它们有多像？核心思路——如果两个节点的邻居”长得像”，那它们自己也像。这可以是直接比较邻域重叠（Common Neighbors、Jaccard），也可以递归地定义（SimRank）。
图相似性：给定两张不同的图 $G_1$ 和 $G_2$ ，它们有多像？核心思路——把图映射到一个特征空间，在特征空间中用内积度量相似性（Graph Kernel）。
图同构：给定 $G_1$ 和 $G_2$ ，它们的结构是否完全相同？核心思路——逐步细化节点标签，如果标签分布一致则”可能同构”（WL test）；如果需要精确判定，则回溯搜索所有可能的节点映射（VF2）。

这三个层次形成一个递进关系：节点相似性是图相似性的基础（很多图核基于节点/子结构的比较），而图同构是图相似性的极端情况（相似度 = 1，结构完全一致）。

Section A: 节点相似性——两个节点有多像？

给定图 $G = (V, E)$ 中的两个节点 $u$ 和 $v$ ，我们想量化它们的”相似程度”。最直觉的出发点是：看它们的邻域有多少重叠。

基于邻域的指标

回忆 $N(u)$ 表示节点 $u$ 的邻居集合（在 Art. 1 中定义）。

Common Neighbors（共同邻居数）：

$\text{CN}(u, v) = |N(u) \cap N(v)|$

最简单的度量——两个节点共享的邻居越多，越相似。在上面的例子中， $u$ 和 $v$ 共享邻居 $c$ 和 $d$ ，所以 $\text{CN}(u, v) = 2$ 。

优点：计算简单， $O(\deg(u) + \deg(v))$ 。缺点：不归一化——度高的节点天然有更多共同邻居。

Jaccard Index（Jaccard 相似系数）：

$J(u, v) = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}$

用交集除以并集，归一化到 $[0, 1]$ 。在上例中， $N(u) = \{a, b, c, d\}$ ， $N(v) = \{c, d, e\}$ ，所以 $J(u, v) = 2/5 = 0.4$ 。

Adamic-Adar Index：

$\text{AA}(u, v) = \sum_{w \in N(u) \cap N(v)} \frac{1}{\log \deg(w)}$

核心洞察：不是所有共同邻居都同样有价值。一个度很高的共同邻居（比如 hub 节点）提供的信息量比度低的共同邻居少——如果一个人和每个人都是朋友，那”我们都认识他”这个事实不太说明我们俩相似。Adamic-Adar 用 $1/\log \deg(w)$ 给每个共同邻居加权，度越高权重越低。

这三个指标的计算都只依赖节点的一阶邻域，时间复杂度为 $O(\deg(u) + \deg(v))$ （用排序/哈希求交集）。

基于随机游走的指标：SimRank

邻域指标只看一跳范围，但有时相似性需要考虑更广的结构上下文。SimRank（Jeh & Widom, 2002）提出了一个递归定义：

被相似节点指向的节点也相似。

形式化定义（对于有向图）：

$s(u, v) = \begin{cases} 1 & \text{if } u = v \\ \frac{C}{|I(u)| \cdot |I(v)|} \sum_{x \in I(u)} \sum_{y \in I(v)} s(x, y) & \text{otherwise} \end{cases}$

逐项拆解：

$I(u)$ 是指向 $u$ 的入邻居集合（in-neighbors）
$C \in (0, 1)$ 是衰减系数（通常取 0.6-0.8），保证远距离的贡献递减
双重求和遍历 $u$ 和 $v$ 的所有入邻居对 $(x, y)$
直觉：如果 $u$ 的”上游” $x$ 和 $v$ 的”上游” $y$ 很相似，那 $u$ 和 $v$ 也应该相似

计算方法：迭代到收敛。初始化 $s^{(0)}(u, u) = 1$ ， $s^{(0)}(u, v) = 0$ （ $u \neq v$ ），然后反复应用上述递推公式，直到变化量小于阈值。

复杂度：朴素实现每次迭代 $O(n^2 \cdot d^2)$ （ $d$ 是平均度），需要约 $O(n^2)$ 空间存储所有节点对的相似度。对于大图（ $n > 10^5$ ），这是不可承受的——后续有各种近似算法（如 Monte Carlo SimRank）。

应用：链接预测

节点相似性最重要的应用之一是链接预测（Link Prediction）：给定当前的图，预测未来可能出现的新边。

场景举例：

社交网络：预测两个用户未来可能成为好友（Facebook 的”你可能认识的人”）
知识图谱补全：知识图谱中已知”A 是 B 的作者”、“B 属于领域 C”，预测缺失的关系（如”A 研究领域 C”）
生物网络：预测蛋白质之间的未知交互

做法：对所有尚未连接的节点对 $(u, v)$ 计算相似度分数，按分数排名，分数越高越可能存在边。实验表明（Liben-Nowell & Kleinberg, 2007），即使是最简单的 Common Neighbors 在社交网络链接预测上也表现不错，Adamic-Adar 通常更优。

Section B: 图相似性——两张图有多像？

节点相似性关注的是同一张图内部的比较。当我们需要比较两张不同的图时，问题变得更难——两张图的节点集不同、大小可能不同，没有自然的”对齐”方式。

Graph Kernel：把图映射到特征空间

核心思路：如果我们能把每张图映射为一个固定维度的特征向量 $\phi(G)$ ，那么图之间的相似性就可以用向量内积来度量。

一个 Graph Kernel $K(G_1, G_2)$ 定义了两张图之间的相似度，等价于某个特征空间中的内积：

$K(G_1, G_2) = \langle \phi(G_1), \phi(G_2) \rangle$

关键问题是： $\phi$ 应该是什么？不同的 Graph Kernel 给出不同的答案。

WL Subtree Kernel

Weisfeiler-Leman (WL) subtree kernel（Shervashidze et al., 2011）是最有影响力的 Graph Kernel 之一。它的特征映射 $\phi(G)$ 基于 WL test 的颜色细化过程（下一节详述）。

核心步骤：

对图 $G$ 运行 $h$ 轮 WL 颜色细化，得到每个节点在每轮的颜色标签
$\phi(G)$ = 所有轮中所有颜色标签的频率直方图（concatenation）
两张图的 kernel 值 = 两个直方图的内积

直觉：WL 颜色细化的每一轮捕获的是节点的” $k$ -跳邻域子树结构”。两张图如果在各级邻域子树结构的分布上相似，它们的 kernel 值就高。

时间复杂度： $O(h \cdot m)$ （ $h$ 是迭代轮数， $m$ 是边数），线性于图的大小——非常高效。

Random Walk Kernel

Random Walk Kernel 的思路不同：在两张图的乘积图（product graph）上做随机游走，用同步随机游走的匹配概率作为相似度。

$K_{RW}(G_1, G_2) = \sum_{k=0}^{\infty} \mu_k \cdot q_k^\top p_k$

其中 $\mu_k$ 是第 $k$ 步的权重（通常几何衰减）， $q_k$ 和 $p_k$ 分别涉及两张图上的游走概率。

直觉：如果两张图结构相似，在它们上同步做随机游走时，很容易找到”匹配”的游走路径。

复杂度： $O(n_1^3 \cdot n_2^3)$ （朴素实现），计算量大，仅适用于小图。

与 GNN 的关系

WL test 不仅是一个图核方法——它与图神经网络（GNN）有深刻联系：

定理（Xu et al., 2019；Morris et al., 2019）：消息传递 GNN（如 GCN、GraphSAGE、GIN）的表达力不超过 1-WL test。也就是说，如果 1-WL test 无法区分两张图，那么没有任何消息传递 GNN 能区分它们。

这个结论为 GNN 的设计提供了理论指导：

GIN（Graph Isomorphism Network）被设计为与 1-WL test 等价的 GNN，达到了消息传递框架的表达力上界
要突破 1-WL 的限制，需要引入高阶 WL test 对应的架构（如 k-GNN）

这个联系将在 Art. 18：图嵌入与 GNN 中详细展开。

Section C: 图同构——两张图结构是否完全相同？

前面讨论的是”多像”（连续度量），现在转向一个离散问题：两张图的结构是否完全相同？

问题定义

图同构（Graph Isomorphism）：给定两个图 $G_1 = (V_1, E_1)$ 和 $G_2 = (V_2, E_2)$ ，是否存在一个双射（bijection） $f: V_1 \to V_2$ ，使得对所有 $u, v \in V_1$ ：

$(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$

换句话说，存在一种节点的重新标号方式，使得两张图的边集完全一致。

直觉上，同构意味着”如果你把节点名字擦掉，两张图画出来长得一样”。但难点在于：你不知道该怎么对齐节点——有 $n!$ 种可能的映射方式，暴力枚举不可行。

必要条件：快速排除

在尝试精确判定之前，有一些必要条件可以快速排除不可能的情况：

节点数和边数相同： $|V_1| = |V_2|$ 且 $|E_1| = |E_2|$
度序列相同：将两张图所有节点的度排序后，序列一致
各阶连通分量数相同

这些检查都是多项式时间的，但不充分——满足这些条件的两张图仍可能不同构。我们需要更强的检测手段。

WL Test：多项式时间的颜色细化

Weisfeiler-Leman (WL) test（又称 color refinement，1968）是最经典的图同构必要条件检测。它的核心思想是一个消息传递过程：

算法步骤：

初始化：给所有节点赋予相同的初始颜色（标签） $c_0(v) = 0$
迭代细化：在第 $k$ 轮，每个节点 $v$ 的新颜色由自身旧颜色和邻居颜色的多重集（multiset）决定：

$c_{k+1}(v) = \text{HASH}\big(c_k(v), \{\!\{ c_k(u) : u \in N(v) \}\!\}\big)$

逐项拆解：

$c_k(v)$ 是节点 $v$ 在第 $k$ 轮的颜色
$\{\!\{ \cdot \}\!\}$ 表示多重集（multiset），保留重复元素
$N(v)$ 是 $v$ 的邻居集合
HASH 是一个将（旧颜色, 邻居颜色多重集）映射为新颜色的注入函数（injective function）
直觉：如果两个节点的”自身标签 + 邻居标签分布”不同，它们就获得不同的新颜色

终止：当两轮之间的颜色分配不再变化时停止（最多 $n$ 轮，因为每轮只会增加不同颜色的数量，上界为 $n$ ）
判定：比较 $G_1$ 和 $G_2$ 的颜色直方图（每种颜色出现多少次）。如果直方图不同，一定不同构；如果直方图相同，可能同构（但不能确定）。

这就是为什么 WL test 是”必要不充分”的：它能排除非同构对，但不能证明同构。

WL Test 走查

下面的交互组件展示了 WL test 在两张 5 节点图上的完整迭代过程。逐步点击，观察颜色如何细化以及两张图的颜色直方图是否保持一致。

迭代 0 / 3

初始化：所有节点标签相同（颜色 0）。

走查要点：

第 0 轮：所有节点颜色相同（初始化）
第 1 轮：度不同的节点获得不同颜色——这一轮本质上是按度数分类
第 2 轮：邻居的颜色组合不同的节点进一步分化
如果所有轮的颜色直方图都一致，WL test 说”可能同构”

WL Test 与 BFS/DFS 的联系

WL test 的颜色细化过程与 Art. 1 中 DFS 的时间戳概念有一个有趣的联系：两者都是通过聚合邻域信息来区分节点。DFS 时间戳通过”何时发现、何时结束”给每个节点一个独特标识；WL test 通过”邻居颜色的多重集”给每个节点一个独特标识。区别在于：DFS 时间戳依赖遍历顺序（同一张图不同遍历可能得到不同时间戳），而 WL 颜色是顺序无关的——它是一个确定性的图不变量。

WL Test 的局限

1-WL test 并非万能。存在一些非同构图对，1-WL 无法区分它们——最经典的例子是正则图（regular graph，所有节点度数相同）。例如，两个不同的 3-正则图（每个节点恰好 3 条边）可能产生完全相同的 WL 颜色序列。

为了增强区分能力，可以使用** $k$ -WL test**（ $k \geq 2$ ），它操作的是 $k$ -元组而非单个节点。 $k$ 越大，区分能力越强，但复杂度也从 $O(n)$ 增长到 $O(n^k)$ 。

VF2 算法：精确的回溯搜索

当 WL test 说”可能同构”时，我们需要一个精确算法来确认。VF2（Cordella et al., 2004）是实践中最常用的精确图同构判定算法。

核心思想：通过回溯搜索，逐步构建从 $G_1$ 到 $G_2$ 的节点映射 $f$ 。每一步选择一个 $G_1$ 中未映射的节点 $u$ ，尝试将其映射到 $G_2$ 中某个兼容的节点 $v$ ，然后检查这个部分映射是否一致（映射的节点之间的边关系是否保持）。

VF2 的关键优化——可行性剪枝规则：

不是盲目尝试所有映射。VF2 维护了一组可行性规则（feasibility rules），在每一步检查：

一致性规则（ $R_{consist}$ ）：如果 $u$ 映射到 $v$ ，那么 $u$ 在已映射子图中的邻居必须恰好映射到 $v$ 在已映射子图中的邻居
前瞻规则（ $R_{look-ahead}$ ）：检查未映射节点的度约束——如果 $u$ 有 3 个已映射邻居但 $v$ 只有 2 个，这个映射不可能成功
新增对规则（ $R_{new}$ ）：限制可能的候选对数量

这些规则大幅减少了搜索空间——实践中 VF2 在多数图上远快于最坏情况。

复杂度：

最坏情况： $O(n! \cdot n)$ （穷举所有排列）
实际表现：对于大多数实际图，可行性规则的剪枝使得运行时间远低于最坏情况
空间： $O(n)$ （只存储当前的部分映射）

复杂度之谜：图同构在哪里？

图同构问题（Graph Isomorphism, GI）在计算复杂度理论中占据着一个独一无二的位置。

已知事实：

GI $\in$ NP：给出一个映射 $f$ ，验证它是否是同构可以在多项式时间完成
GI 不太可能是 NP-complete：如果 GI 是 NP-complete，则多项式层次（polynomial hierarchy）将坍缩到第二层（Boppana, Hastad & Zachos, 1987），这被认为极不可能
GI 不知道是否属于 P：没有已知的多项式时间算法

Babai 的突破（2015/2016）：László Babai 证明 GI 可以在准多项式时间（quasipolynomial time）内解决：

$O\big(e^{(\log n)^c}\big)$

其中 $c$ 是常数。这个复杂度介于多项式时间 $O(n^k)$ 和指数时间 $O(2^n)$ 之间——比任何多项式都慢，但比指数快得多。这是 GI 问题 30 多年来最大的理论突破。

实践意义：尽管理论上 GI 的精确复杂度未定，实践中 VF2 等算法对大多数实际图表现良好。真正困难的实例（如高度正则的图）在实际应用中很少出现。

应用场景

化学信息学中的分子比较

分子可以自然地建模为图——原子是节点，化学键是边。两个分子是否是同一种物质，本质上就是图同构问题。药物发现中比较候选分子的结构相似性，则需要 Graph Kernel。

具体例子：PubChem 数据库中有超过 1.1 亿个化合物。搜索”与某分子结构相似的所有化合物”本质上就是 Graph Kernel 排序问题。WL subtree kernel 在分子分类任务上的表现通常优于传统的分子指纹方法（Morgan fingerprint）。

社交网络中的链接预测与推荐

Facebook 的”你可能认识的人”功能：对每对非好友用户计算 Common Neighbors/Adamic-Adar 指标，按分数排名推荐。Facebook 在 2012 年的论文中报告，Adamic-Adar 在其网络上的链接预测 AUC 达到 0.92。

知识图谱补全

知识图谱（如 Wikidata、Freebase）中存在大量缺失的关系。SimRank 等基于全局结构的相似度可以用于实体对齐（entity alignment）——当同一个实体在不同图谱中有不同的标识符时，基于结构相似性找出它们对应的节点。

复杂度对比表

方法	时间复杂度	空间复杂度	适用场景
Common Neighbors	$O(\deg(u) + \deg(v))$	$O(1)$	节点对相似性，链接预测
Jaccard Index	$O(\deg(u) + \deg(v))$	$O(1)$	归一化的节点相似性
Adamic-Adar	$O(\deg(u) + \deg(v))$	$O(1)$	加权链接预测（通常最优）
SimRank（朴素）	$O(Kn^2d^2)$ （ $K$ 轮迭代）	$O(n^2)$	全局节点相似性（小图）
WL Subtree Kernel	$O(hm)$ （ $h$ 轮 WL）	$O(n)$	图分类（高效）
Random Walk Kernel	$O(n_1^3 n_2^3)$ （朴素）	$O(n_1 n_2)$	图比较（小图）
WL Test	$O(n \cdot m)$ （最多 $n$ 轮）	$O(n)$	同构快速筛选（必要不充分）
VF2	$O(n! \cdot n)$ 最坏	$O(n)$	精确同构判定

🔁 迭代机器视角 — 1-WL (Color Refinement)EQ: 方程 / 不动点

Graph	原图
State[v]	颜色标签 color(v)
SELECT	全集（同步迭代）
COMBINE	聚合邻居颜色 → hash 生成新颜色
重入	到不动点（颜色稳定）
TERMINATE	颜色分布不再变化
求解方法	FI

1-WL 的 COMBINE 与 GNN message passing 的区分能力等价（Xu et al., 2019）

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — VF2 (Subgraph Isomorphism)CST: 约束满足

Graph	搜索树（隐式）
State[v]	部分匹配映射
SELECT	LIFO（DFS 回溯）
COMBINE	尝试匹配一对节点 → 检查一致性
重入	可回退
TERMINATE	完成匹配或穷尽
求解方法	B&P

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文覆盖了图比较问题的三个层次：

节点相似性（Common Neighbors、Jaccard、Adamic-Adar、SimRank）：从邻域重叠到递归结构匹配，核心应用是链接预测
图相似性（WL Subtree Kernel、Random Walk Kernel）：把图映射到特征空间用内积度量，核心应用是图分类
图同构（WL test + VF2）：WL test 是多项式时间的必要不充分检测，VF2 是回溯搜索精确判定；GI 问题的复杂度介于 P 和 NP-complete 之间，是计算复杂度理论中的”奇特”问题
WL test 是连接传统图算法与现代 GNN 的桥梁：消息传递 GNN 的表达力上界就是 1-WL test（详见 Art. 18）

我们正处于路径 Part 2”量”的末段——在度量了距离（Art. 6）、重要性（Art. 7）、社区（Art. 8）之后，现在又掌握了相似性和同构的度量工具。下一篇 Art. 10：团与稠密子图将转向另一类”量”的问题——找出图中最密集的局部结构。

实现指引

算法	库	函数/方法
Common Neighbors	NetworkX	`nx.common_neighbors(G, u, v)`
Jaccard Index	NetworkX	`nx.jaccard_coefficient(G, ebunch)`
Adamic-Adar	NetworkX	`nx.adamic_adar_index(G, ebunch)`
SimRank	NetworkX	`nx.simrank_similarity(G)`
图同构判定	NetworkX	`nx.is_isomorphic(G1, G2)` (基于 VF2)
子图同构	NetworkX	`nx.algorithms.isomorphism.GraphMatcher(G1, G2)`
WL Subtree Kernel	GraKeL	`grakel.WeisfeilerLehman(n_iter=5)`
Random Walk Kernel	GraKeL	`grakel.RandomWalk()`
图同构 (GNN)	PyG	`torch_geometric.nn.WLConv` (WL-inspired layer)