图同构问题（Weisfeiler-Lehman算法） 问题描述 图同构问题（Graph Isomorphism）是判断两个无向图是否在顶点重标号意义下具有完全相同的结构。形式化地说，给定两个图 \( G_ 1 = (V_ 1, E_ 1) \) 和 \( G_ 2 = (V_ 2, E_ 2) \)，需要判断是否存在一个双射 \( f: V_ 1 \to V_ 2 \)，使得对任意顶点对 \( (u, v) \in V_ 1 \)，边 \( (u, v) \in E_ 1 \) 当且仅当边 \( (f(u), f(v)) \in E_ 2 \)。该问题在计算复杂性理论中属于NP问题，但尚未被证明是NP完全问题。Weisfeiler-Lehman（WL）算法是一种高效的图同构判定启发式方法，尤其适用于多数实际场景。 解题过程详解 1. 算法核心思想 WL算法通过迭代地 细化顶点标签 来区分图的局部结构。每一轮迭代中，算法会聚合每个顶点及其邻居的当前标签信息，生成新的复合标签。若两个图在迭代过程中产生不同的标签多重集，则可判定它们不同构；若标签稳定后多重集一致，则两图可能同构（但需注意存在特例）。 2. 算法步骤 设输入图为 \( G_ 1, G_ 2 \)，顶点集分别为 \( V_ 1, V_ 2 \)。 步骤1：初始化标签 为每个顶点分配初始标签。通常使用顶点的度作为初始标签（若顶点度相同则标签相同）。 例如： 度数为1的顶点标签为 \( L_ 0(v) = 1 \) 度数为2的顶点标签为 \( L_ 0(v) = 2 \) 若所有顶点度数相同，则所有顶点初始标签相同。 步骤2：迭代标签细化 对第 \( k \) 轮迭代（\( k \geq 1 \)）： 对每个顶点 \( v \)，收集其邻居的当前标签集合 \( \{ L_ {k-1}(u) \mid u \in N(v) \} \)，其中 \( N(v) \) 是 \( v \) 的邻居集合。 对邻居标签集合进行排序，得到有序列表 \( S_ v \)。 生成新标签 \( L_ k(v) = \text{Hash}(L_ {k-1}(v), S_ v) \)，其中 Hash 函数将复合信息映射为唯一的新标签（例如使用字符串拼接后哈希）。 步骤3：检查标签收敛 每轮迭代后，比较两个图的标签多重集（即每个标签的出现次数）。 若两图的多重集不同，立即终止并返回“不同构”。 若多重集相同且标签不再变化（即 \( L_ k = L_ {k-1} \)），终止迭代并进入步骤4。 步骤4：判定结果 若迭代收敛时两图标签多重集一致，则输出“可能同构”。 注意 ：WL算法对某些特殊图（如强正则图）可能失效，此时需结合其他方法验证。 3. 实例演示 考虑两个图 \( G_ 1 \) 和 \( G_ 2 \)： \( G_ 1 \)：三角形（3个顶点，3条边） \( G_ 2 \)：三顶点路径（2条边） 初始标签 ： \( G_ 1 \) 所有顶点度为2 → 标签均为 \( L_ 0 = 2 \)。 \( G_ 2 \) 两端顶点度为1 → 标签 \( L_ 0 = 1 \)，中间顶点度为2 → 标签 \( L_ 0 = 2 \)。 第一轮迭代 ： \( G_ 1 \) 中每个顶点的邻居标签集合均为 \( \{2, 2\} \)，新标签 \( L_ 1 = \text{Hash}(2, [ 2,2 ]) \) 全部相同。 \( G_ 2 \) 中： 端顶点邻居标签为 \( \{2\} \) → \( L_ 1 = \text{Hash}(1, [ 2 ]) \) 中间顶点邻居标签为 \( \{1, 1\} \) → \( L_ 1 = \text{Hash}(2, [ 1,1 ]) \) 比较多重集：\( G_ 1 \) 为 \( \{3 \times \text{Hash}(2,[ 2,2])\} \)，\( G_ 2 \) 包含三种不同标签 → 多重集不同，判定“不同构”。 4. 算法特性与局限性 时间复杂度 ：每轮迭代需遍历所有边，标签哈希和排序开销为 \( O(|E| \log d_ {\text{max}}) \)，其中 \( d_ {\text{max}} \) 为最大度。 表达能力 ：一维WL算法等价于图神经网络中的GIN模型，能区分大多数常见图，但无法区分所有非同构图（如某些强正则图）。 改进版本 ：k-维WL算法通过考虑k元顶点组提升判别能力，但计算成本较高。 通过WL算法，我们可在多项式时间内对多数实际图结构完成同构判定，为图数据库、化学分子比对等应用提供基础工具。