图同构问题的 Weisfeiler-Lehman (WL) 算法
字数 3887 2025-12-23 02:33:34

好的，我们已经讲过了很多图论算法。根据你的要求，我将随机挑选一个图同构问题的 Weisfeiler-Lehman (WL) 算法来详细讲解。这个算法虽然不保证完全正确（即存在“非同构但WL测试无法区分”的图对，即WL测试的“失效案例”），但它是一个非常强大、高效且实用的图同构近似判别和节点特征提取工具，在图神经网络等领域有广泛应用。

图同构问题的 Weisfeiler-Lehman (WL) 算法

题目描述：
给定两个无向图 G 和 H，判断它们是否可能是同构的。图同构意味着存在一个双射（一一对应）函数，将图 G 的顶点映射到图 H 的顶点，使得在 G 中相邻的顶点在 H 中的像也相邻，反之亦然。这是一个著名的、尚未被证明是P或NP完全的问题。Weisfeiler-Lehman (WL) 算法提供了一种迭代的、基于节点邻域“颜色”（标签）聚合与哈希的测试方法。如果两个图在这个测试中表现不同（即产生的颜色多重集不同），那么它们一定不同构；如果表现相同，则它们很可能（但不一定）同构。

核心思想：
算法为图中的每个节点分配一个初始“颜色”（通常基于节点的度），然后迭代地“精炼”这个颜色。在每一轮迭代中，一个节点的新颜色由其当前颜色和它所有邻居的当前颜色多重集共同决定。经过多轮迭代后，如果两个图产生的节点颜色多重集在任何一轮都不相同，则它们非同构。

解题过程：

我们将分步讲解经典的 1-维 Weisfeiler-Lehman (1-WL) 算法，也称为“颜色精炼”算法。

第1步：初始化颜色

我们首先为两个图的每个节点分配一个初始颜色（标签）。最自然、最常用的初始化方式是基于节点的度。因为同构的图中，度相同的节点才有可能相互对应。

  1. 对于图 G 和 H，分别计算每个节点的度（与该节点相连的边的数量）。
  2. 将度相同的节点分配相同的颜色标签。例如，我们可以直接用度的数值作为初始颜色标签 C^0(v)。
    • 度数为 1 的节点颜色为 “1”。
    • 度数为 2 的节点颜色为 “2”，以此类推。

例子：
假设图G有三个节点：v1(度3), v2(度2), v3(度2)。
图H有三个节点：u1(度3), u2(度2), u3(度2)。
初始颜色：
G: C^0(v1)=“3”, C^0(v2)=“2”, C^0(v3)=“2”
H: C^0(u1)=“3”, C^0(u2)=“2”, C^0(u3)=“2”

此时，两个图的颜色多重集都是 {“3”, “2”, “2”}，相同。

第2步：迭代颜色精炼

这是算法的核心。我们将进行 k 轮迭代（k 通常直到颜色稳定或达到预设值）。在第 t 轮：
对于图 G（对图 H 进行完全相同的过程）中的每个节点 v：

  1. 收集邻域颜色：收集节点 v 的所有邻居节点在第 t-1 轮的颜色，构成一个多重集 M_t(v)。例如，M_t(v) = { C^{t-1}(u) | u 是 v 的邻居 }。注意是多重集，邻居颜色可以重复。
  2. 生成新标签：将节点 v 自身当前的颜色 C^{t-1}(v) 和它的邻居颜色多重集 M_t(v) 组合成一个新的、唯一的字符串（或哈希值）。这个组合方式必须保证：如果两个节点在这一步的输入（自身颜色，邻居颜色多重集）完全相同，那么它们产生的新字符串也完全相同。
    常见的做法是：新标签字符串 = C^{t-1}(v) + “,” + 排序后的(M_t(v))
    例如，v自身颜色是“A”，邻居颜色多重集是 {“B”, “B”, “C”}，排序后得到列表 [“B”, “B”, “C”]，那么新标签字符串就是 “A,B,B,C”。
  3. 压缩标签（哈希）：第2步产生的新标签字符串可能非常长且不便于比较。我们用一个哈希函数将其映射为一个简短的新颜色标签 C^t(v)。这个哈希函数需要为不同的输入字符串生成不同的哈希值。在实际算法中，我们通常维护一个全局字典（哈希表）：
    • 当我们首次遇到一个新字符串 “A,B,B,C” 时，我们给它分配一个新的、递增的简短颜色ID，比如 “5”。
    • 之后再遇到相同的字符串 “A,B,B,C”，我们就直接从字典中查到它的颜色ID “5”。

例子（接上文）：
进行第一轮迭代 (t=1)。

  • 对于图G的节点 v1：C^0(v1)=“3”。假设它的邻居是 v2 和 v3，那么 M_1(v1) = {“2”, “2”}。排序后得到 [“2”, “2”]。组合字符串：“3,2,2”。假设哈希后得到新颜色 “7”。所以 C^1(v1)=“7”。

  • 对于图G的节点 v2：C^0(v2)=“2”。假设它的邻居是 v1 和 v3，那么 M_1(v2) = {“3”, “2”}。排序 [“2”, “3”]。组合字符串：“2,2,3”。哈希后得到新颜色 “8”。C^1(v2)=“8”。

  • 对于图G的节点 v3：C^0(v3)=“2”。邻居假设是 v1 和 v2，那么 M_1(v3) = {“3”, “2”}（和v2相同）。组合字符串：“2,2,3”。哈希后得到新颜色 “8”（和v2相同）。C^1(v3)=“8”。
    图G第一轮后的颜色：{“7”, “8”, “8”}。

  • 对图H进行完全相同的操作。由于我们假设G和H在这个例子中结构相同，节点u1, u2, u3的邻居关系和初始颜色与v1, v2, v3一一对应，因此它们生成的组合字符串也一一对应。

    • u1 生成 “3,2,2” -> 哈希为 “7”。
    • u2 生成 “2,2,3” -> 哈希为 “8”。
    • u3 生成 “2,2,3” -> 哈希为 “8”。
      图H第一轮后的颜色：{“7”, “8”, “8”}。

两个图的颜色多重集仍然相同。

第3步：检查与终止

在每一轮迭代后，我们需要比较两个图当前的节点颜色多重集。

  1. 比较：计算图G所有节点的颜色 C^t(v) 构成的多重集，和图H的多重集进行比较。
  2. 判断：
    • 如果不同：算法立即终止，并断定 图G和图H不同构。因为如果它们同构，那么每一轮精炼出的颜色模式必须完全相同。
    • 如果相同：则继续下一轮迭代 (t+1)。
  3. 终止条件（当多重集相同时）：
    • 条件A：颜色稳定。即从第 t 轮到第 t+1 轮，两个图各自的颜色分配方案都没有任何变化（每个节点的颜色都不再改变）。此时算法终止，我们无法区分这两个图，称它们为 “WL-等价”或“k-等价”。对于WL-等价的图，算法返回“可能是同构的”（但请注意，存在著名的非同构但WL-等价的图，如某些正则图）。
    • 条件B：达到预设的最大迭代轮数 K。在实际应用中，为了控制计算成本，我们可能会设置一个最大迭代次数。达到后即终止，并返回“在K轮内无法区分，可能是同构的”。

例子（继续）：
在我们的例子中，第一轮后颜色多重集相同。我们进入第二轮 (t=2)。
用同样的方法，基于 C^1 的颜色计算 C^2。

  • v1(C^1=“7”)的邻居是 v2(“8”), v3(“8”)。组合 “7,8,8” -> 假设哈希为 “12”。
  • v2(C^1=“8”)的邻居是 v1(“7”), v3(“8”)。组合 “8,7,8” -> 假设哈希为 “13”。
  • v3(C^1=“8”)的邻居是 v1(“7”), v2(“8”)。组合 “8,7,8” -> 哈希为 “13”。
    图G第二轮颜色：{“12”, “13”, “13”}。
    图H也会得到完全相同的 {“12”, “13”, “13”}。

假设在第三轮(t=3)时，每个节点的颜色组合字符串与第二轮完全相同，因此哈希后的新颜色也不变。此时颜色达到稳定。算法终止，判定G和H是WL-等价的，因此可能是同构的。

第4步：算法输出与意义

  • 输出“不同构”：这是确定的结论，100%正确。
  • 输出“可能是同构”：这是一个概率性/启发式的结论。对于绝大多数随机图或非高度对称的图，WL测试非常可靠。但对于一些精心构造的强正则图、凯莱图等，WL测试会失效（即两个非同构的图被判定为WL-等价）。

算法复杂度：
假设图有 n 个节点，m 条边，迭代 K 轮。

  • 每轮迭代需要遍历所有节点和它们的邻居，时间复杂度为 O(K * (n + m))。
  • 哈希和字典查找操作通常是 O(1) 的。
    因此，WL算法是一个非常高效的图同构判别启发式算法。

总结一下关键步骤：

  1. 初始化：基于节点度分配初始颜色。
  2. 迭代精炼（核心）：
    a. 对每个节点，收集自身颜色和邻居颜色多重集。
    b. 将这两部分组合成一个新字符串。
    c. 哈希压缩该字符串，得到节点的新颜色。
  3. 检查比较：每轮结束后，对比两个图的节点颜色多重集。
  4. 终止与判定：若多重集不同，则“不同构”；若达到稳定或最大轮数时多重集仍相同，则“可能是同构”。

这个算法不仅用于同构测试，其“颜色”可以视为节点的特征，因此它也是现代图神经网络（GNN）中消息传递和聚合机制的奠基性理论之一。

好的，我们已经讲过了很多图论算法。根据你的要求，我将随机挑选一个 图同构问题的 Weisfeiler-Lehman (WL) 算法 来详细讲解。这个算法虽然不保证完全正确（即存在“非同构但WL测试无法区分”的图对，即WL测试的“失效案例”），但它是一个非常强大、高效且实用的图同构近似判别和节点特征提取工具，在图神经网络等领域有广泛应用。 图同构问题的 Weisfeiler-Lehman (WL) 算法 题目描述： 给定两个无向图 G 和 H ，判断它们是否可能是同构的。图同构意味着存在一个双射（一一对应）函数，将图 G 的顶点映射到图 H 的顶点，使得在 G 中相邻的顶点在 H 中的像也相邻，反之亦然。这是一个著名的、尚未被证明是P或NP完全的问题。Weisfeiler-Lehman (WL) 算法提供了一种迭代的、基于节点邻域“颜色”（标签）聚合与哈希的测试方法。如果两个图在这个测试中表现不同（即产生的颜色多重集不同），那么它们一定不同构；如果表现相同，则它们很可能（但不一定）同构。 核心思想： 算法为图中的每个节点分配一个初始“颜色”（通常基于节点的度），然后迭代地“精炼”这个颜色。在每一轮迭代中，一个节点的新颜色由其当前颜色和它所有邻居的当前颜色 多重集 共同决定。经过多轮迭代后，如果两个图产生的节点颜色 多重集 在任何一轮都不相同，则它们非同构。 解题过程： 我们将分步讲解经典的 1-维 Weisfeiler-Lehman (1-WL) 算法 ，也称为“颜色精炼”算法。 第1步：初始化颜色 我们首先为两个图的每个节点分配一个初始颜色（标签）。最自然、最常用的初始化方式是 基于节点的度 。因为同构的图中，度相同的节点才有可能相互对应。 对于图 G 和 H ，分别计算每个节点的度（与该节点相连的边的数量）。 将度相同的节点分配相同的颜色标签。例如，我们可以直接用度的数值作为初始颜色标签 C^0(v) 。 度数为 1 的节点颜色为 “1”。 度数为 2 的节点颜色为 “2”，以此类推。 例子： 假设图G有三个节点：v1(度3), v2(度2), v3(度2)。 图H有三个节点：u1(度3), u2(度2), u3(度2)。 初始颜色： G: C^0(v1)=“3” , C^0(v2)=“2” , C^0(v3)=“2” H: C^0(u1)=“3” , C^0(u2)=“2” , C^0(u3)=“2” 此时，两个图的颜色多重集都是 {“3”, “2”, “2”}，相同。 第2步：迭代颜色精炼 这是算法的核心。我们将进行 k 轮迭代（ k 通常直到颜色稳定或达到预设值）。在第 t 轮： 对于图 G （对图 H 进行完全相同的过程）中的每个节点 v ： 收集邻域颜色 ：收集节点 v 的所有邻居节点在第 t-1 轮的颜色，构成一个 多重集 M_t(v) 。例如， M_t(v) = { C^{t-1}(u) | u 是 v 的邻居 } 。注意是 多重集 ，邻居颜色可以重复。 生成新标签 ：将节点 v 自身当前的颜色 C^{t-1}(v) 和它的 邻居颜色多重集 M_t(v) 组合成一个新的、唯一的字符串（或哈希值）。这个组合方式必须保证： 如果两个节点在这一步的输入（自身颜色，邻居颜色多重集）完全相同，那么它们产生的新字符串也完全相同 。 常见的做法是： 新标签字符串 = C^{t-1}(v) + “,” + 排序后的(M_t(v)) 例如， v 自身颜色是“A”，邻居颜色多重集是 {“B”, “B”, “C”}，排序后得到列表 [“B”, “B”, “C”] ，那么新标签字符串就是 “A,B,B,C” 。 压缩标签（哈希） ：第2步产生的新标签字符串可能非常长且不便于比较。我们用一个哈希函数将其映射为一个简短的新颜色标签 C^t(v) 。这个哈希函数需要为 不同的输入字符串生成不同的哈希值 。在实际算法中，我们通常维护一个全局字典（哈希表）： 当我们首次遇到一个新字符串 “A,B,B,C” 时，我们给它分配一个新的、递增的简短颜色ID，比如 “5” 。 之后再遇到相同的字符串 “A,B,B,C” ，我们就直接从字典中查到它的颜色ID “5” 。 例子（接上文）： 进行第一轮迭代 ( t=1 )。 对于图G的节点 v1 ： C^0(v1)=“3” 。假设它的邻居是 v2 和 v3 ，那么 M_1(v1) = {“2”, “2”} 。排序后得到 [“2”, “2”] 。组合字符串： “3,2,2” 。假设哈希后得到新颜色 “7” 。所以 C^1(v1)=“7” 。 对于图G的节点 v2 ： C^0(v2)=“2” 。假设它的邻居是 v1 和 v3 ，那么 M_1(v2) = {“3”, “2”} 。排序 [“2”, “3”] 。组合字符串： “2,2,3” 。哈希后得到新颜色 “8” 。 C^1(v2)=“8” 。 对于图G的节点 v3 ： C^0(v3)=“2” 。邻居假设是 v1 和 v2 ，那么 M_1(v3) = {“3”, “2”} （和v2相同）。组合字符串： “2,2,3” 。哈希后得到新颜色 “8” （和v2相同）。 C^1(v3)=“8” 。 图G第一轮后的颜色： {“7”, “8”, “8”} 。 对图H进行完全相同的操作。由于我们假设G和H在这个例子中结构相同，节点u1, u2, u3的邻居关系和初始颜色与v1, v2, v3一一对应，因此它们生成的组合字符串也一一对应。 u1 生成 “3,2,2” -> 哈希为 “7” 。 u2 生成 “2,2,3” -> 哈希为 “8” 。 u3 生成 “2,2,3” -> 哈希为 “8” 。 图H第一轮后的颜色： {“7”, “8”, “8”} 。 两个图的颜色多重集仍然相同。 第3步：检查与终止 在每一轮迭代后，我们需要比较两个图当前的节点颜色多重集。 比较 ：计算图G所有节点的颜色 C^t(v) 构成的多重集，和图H的多重集进行比较。 判断 ： 如果不同 ：算法立即终止，并断定 图G和图H不同构 。因为如果它们同构，那么每一轮精炼出的颜色模式必须完全相同。 如果相同 ：则继续下一轮迭代 ( t+1 )。 终止条件 （当多重集相同时）： 条件A ：颜色稳定。即从第 t 轮到第 t+1 轮，两个图各自的颜色分配方案都没有任何变化（每个节点的颜色都不再改变）。此时算法终止，我们无法区分这两个图，称它们为 “WL-等价”或“k-等价” 。对于WL-等价的图，算法返回“ 可能是同构的 ”（但请注意，存在著名的非同构但WL-等价的图，如某些正则图）。 条件B ：达到预设的最大迭代轮数 K 。在实际应用中，为了控制计算成本，我们可能会设置一个最大迭代次数。达到后即终止，并返回“在K轮内无法区分，可能是同构的”。 例子（继续）： 在我们的例子中，第一轮后颜色多重集相同。我们进入第二轮 ( t=2 )。 用同样的方法，基于 C^1 的颜色计算 C^2 。 v1 ( C^1=“7” )的邻居是 v2(“8”) , v3(“8”) 。组合 “7,8,8” -> 假设哈希为 “12” 。 v2 ( C^1=“8” )的邻居是 v1(“7”) , v3(“8”) 。组合 “8,7,8” -> 假设哈希为 “13” 。 v3 ( C^1=“8” )的邻居是 v1(“7”) , v2(“8”) 。组合 “8,7,8” -> 哈希为 “13” 。 图G第二轮颜色： {“12”, “13”, “13”} 。 图H也会得到完全相同的 {“12”, “13”, “13”} 。 假设在第三轮( t=3 )时，每个节点的颜色组合字符串与第二轮完全相同，因此哈希后的新颜色也不变。此时颜色达到稳定。算法终止，判定G和H是WL-等价的，因此 可能是同构的 。 第4步：算法输出与意义 输出“不同构” ：这是确定的结论，100%正确。 输出“可能是同构” ：这是一个概率性/启发式的结论。对于绝大多数随机图或非高度对称的图，WL测试非常可靠。但对于一些精心构造的强正则图、凯莱图等，WL测试会失效（即两个非同构的图被判定为WL-等价）。 算法复杂度： 假设图有 n 个节点， m 条边，迭代 K 轮。 每轮迭代需要遍历所有节点和它们的邻居，时间复杂度为 O(K * (n + m)) 。 哈希和字典查找操作通常是 O(1) 的。 因此，WL算法是一个 非常高效 的图同构判别启发式算法。 总结一下关键步骤： 初始化 ：基于节点度分配初始颜色。 迭代精炼 （核心）： a. 对每个节点，收集自身颜色和邻居颜色多重集。 b. 将这两部分组合成一个新字符串。 c. 哈希压缩该字符串，得到节点的新颜色。 检查比较 ：每轮结束后，对比两个图的节点颜色多重集。 终止与判定 ：若多重集不同，则“不同构”；若达到稳定或最大轮数时多重集仍相同，则“可能是同构”。 这个算法不仅用于同构测试，其“颜色”可以视为节点的特征，因此它也是现代图神经网络（GNN）中消息传递和聚合机制的奠基性理论之一。