图同构问题的Weisfeiler-Lehman（WL）算法详解

题目描述
给定两个无向图 \(G_1 = (V_1, E_1)\) 和 \(G_2 = (V_2, E_2)\)，判断它们是否同构（即是否存在一个双射函数 \(f: V_1 \to V_2\)，使得任意两个顶点 \(u, v \in V_1\) 相邻当且仅当 \(f(u), f(v) \in V_2\) 相邻）。这是一个计算困难问题（尚无已知的多项式时间算法），Weisfeiler-Lehman（WL）算法是一种高效的图同构测试启发式方法，它通过迭代地“着色”顶点并比较颜色分布来判定同构可能性。虽然WL算法不能解决所有图同构问题（存在反例），但在实际中非常有效。

解题过程循序渐进讲解

第一步：理解核心思想——顶点着色迭代

WL算法的核心是：通过迭代地细化每个顶点的“颜色”（标签），使得颜色能编码顶点在图中的结构信息。如果两个图同构，那么它们的颜色分布（即每种颜色的顶点数量）在每一轮迭代中都必须相同；如果某轮颜色分布不同，则两图一定不同构。

关键概念：

• 初始颜色：每个顶点根据其度（相邻边数）赋予初始颜色（例如度相同的顶点颜色相同）。
• 颜色细化：每一轮中，每个顶点的颜色更新为其当前颜色加上邻居颜色的多重集的哈希编码。
• 收敛：当某一轮的颜色分布不再变化时停止。

第二步：算法步骤详解

设两个图 \(G_1, G_2\) 的顶点数相同（否则直接判定不同构）。

1. 初始化颜色

• 计算每个顶点的度（degree）。
• 将度相同的顶点赋予相同颜色（例如用整数编码颜色：度0→颜色0，度1→颜色1，等等）。
• 得到两个图的初始颜色向量 \(C_1^{(0)}, C_2^{(0)}\)（每个顶点一个颜色）。

示例：

图G1: 顶点A度2, B度2, C度1
图G2: 顶点X度2, Y度2, Z度1
初始颜色: 度2→颜色0, 度1→颜色1
颜色向量: G1: [A:0, B:0, C:1], G2: [X:0, Y:0, Z:1]

2. 迭代颜色细化

对于第 \(k\) 轮（从 \(k=1\) 开始）：

• 对每个顶点，收集其所有邻居在第 \(k-1\) 轮的颜色，构成一个多重集。
• 将“当前顶点颜色 + 邻居颜色多重集”拼接成一个字符串（或元组）。
• 用哈希函数（例如字典映射）将这个字符串映射为一个新的整数颜色，确保相同字符串得到相同颜色。
• 更新该顶点在第 \(k\) 轮的颜色。

注意：哈希映射是全局的，即两个图中相同的字符串必须映射到相同颜色。

3. 检查颜色分布

• 每轮迭代后，统计两个图中每种颜色的顶点数量（直方图）。
• 如果两个图的颜色分布不同，则算法终止并返回不同构。
• 如果分布相同，继续下一轮迭代。

4. 收敛判定

• 如果某轮迭代后，每个顶点的颜色都唯一（即所有顶点颜色均不同），或者颜色分布不再变化，则算法终止。
• 若算法终止时颜色分布始终相同，则返回可能同构（注意：WL算法可能给出假阳性，但实际中较少见）。

第三步：具体例子演示

考虑两个图：

图G1: 三角形（三个顶点两两相连）
图G2: 一个长度为3的路径（三个顶点线性连接）

初始颜色：

• G1所有顶点度均为2 → 颜色0。
• G2两端顶点度为1（颜色1），中间顶点度为2（颜色0）。
  颜色分布不同（G1: 三个颜色0；G2: 颜色0一个，颜色1两个）→ 直接判定不同构。

再考虑两个同构图例子（均为一个四边形）：

G1: A-B, B-C, C-D, D-A  （正方形）
G2: W-X, X-Y, Y-Z, Z-W  （另一个正方形）

初始颜色：所有顶点度均为2 → 颜色0。
第一轮迭代：

• G1顶点A：邻居B和D颜色均为0 → 邻居多重集{0,0} → 字符串“0|0,0” → 哈希为颜色1。
• 所有顶点同理，得到新颜色均为颜色1。
  颜色分布相同（四个颜色1）。
  第二轮迭代：
• 所有顶点邻居颜色均为1 → 邻居多重集{1,1} → 字符串“1|1,1” → 哈希为颜色2。
  颜色分布相同（四个颜色2）。
  迭代收敛（分布不再变化），返回可能同构。

第四步：算法复杂度与注意事项

• 时间复杂度：每轮迭代需遍历所有顶点和边，设顶点数 \(n\)、边数 \(m\)，则每轮 \(O(n+m)\)。迭代轮数通常很少（经验上小于10）。
• 空间复杂度：存储颜色映射和哈希表，\(O(n+m)\)。
• 局限性：
  1. WL算法不能区分所有非同构图（例如某些强正则图会误判）。
  2. 通常使用k维WL算法（k-WL）增强判别能力，但计算代价更高。
  3. 常用于图机器学习中的图核（Graph Kernel）设计。

第五步：实现伪代码

function WL_Isomorphism_Test(G1, G2):
    if |V1| ≠ |V2| or |E1| ≠ |E2|:
        return False
    # 初始颜色基于度
    color_map1 = assign_color_by_degree(G1)
    color_map2 = assign_color_by_degree(G2)
    if color_distribution(color_map1) ≠ color_distribution(color_map2):
        return False
    
    for iteration in 1 to MAX_ITERATIONS:
        # 构建字符串到新颜色的全局哈希映射
        hash_dict = {}
        new_color1 = refine_colors(G1, color_map1, hash_dict)
        new_color2 = refine_colors(G2, color_map2, hash_dict)
        # 比较颜色分布
        if color_distribution(new_color1) ≠ color_distribution(new_color2):
            return False
        if color_map1 == new_color1 and color_map2 == new_color2:
            break  # 收敛
        color_map1, color_map2 = new_color1, new_color2
    return True  # 可能同构

其中 refine_colors 函数执行颜色细化步骤，hash_dict 确保相同字符串得到相同新颜色。

总结
Weisfeiler-Lehman算法是一种基于迭代颜色细化的图同构启发式判定方法，它通过比较颜色分布来高效筛选非同构图。虽然不具完备性，但在实际应用中（如化学分子图比较、图神经网络）表现出强大的实用性。理解WL算法有助于掌握图结构编码的基本思想，并为学习更复杂的图同构算法（如k-WL、CFI图构造）打下基础。