怎么判断两张图“长得像”？Weisfeiler-Lehman(WL)核
本帖最后由 yinda_peng 于 2026-7-20 13:13 编辑给你两张社交网络图，A图里张三认识李四和王五，B图里赵六认识孙七和周八。如果只看“谁连着谁”（边），你能告诉我这两张图的结构相似吗？这在数学上叫“图同构测试”。对于电脑来说，这不是个简单活，因为把节点顺序随便换一换，邻接矩阵就全变了。总不能把所有的排列组合都试一遍吧。
我们人是怎么看的？我们不会去看矩阵，我们看的是“朋友圈”。
[*]看局部角色：你先看每个节点在局部是什么“角色”。比如，节点A是个“交际花”（1跳朋友多），节点B是个“桥梁”（朋友之间互相不认识，但联系着两个大团体）。
[*]放大范围确认：为了确认角色，你还会看看“朋友的朋友”（2跳），确保没看走眼。比如这个“交际花”的朋友们之间是不是也互相认识？（如果认识，说明是个小团伙；如果不认识，说明是个纯粹的广播站）。
[*]统计角色分布：你把图上所有节点的这些“局部角色”都提取出来，整理成一张“角色清单”（也就是我们后面提到的标签直方图）。
[*]对比清单：你拿着图A的“角色清单”和图B的“角色清单”去对比。
[*]如果清单里的角色类型和数量完全一致，那这两张图的结构肯定是一样的（同构）。
[*]如果清单里有不同的“角色”，或者某个角色的数量对不上，那这两张图的结构肯定不一样！
WL核的核心思想就是：把这种“朋友圈分层”的办法，变成电脑能懂的语言。
电脑怎么看邻居呢？这里引入一个词：多重集（Multiset）：“没有顺序但允许元素重复”。
[*]普通集合 {程序员, 产品经理}
[*]多重集 {{程序员, 程序员, 产品经理}}
为什么要强调重复？ 因为一个节点有2个程序员朋友，和它有1个程序员朋友，在图结构里是完全不同的概念！顺序不重要（邻接点的顺序不重要），但数量绝对重要（度）！
假设我们有两张图要比较，WL算法是这样迭代的：
[*]第1步（开局）：首先，为每个节点分配一个初始标签。在多数图中，该标签即为节点的度。
[*]第2步（迭代刷新——这是核心）：接着，通过哈希化节点邻域内当前所有标签构成的多重集，迭代地为每个节点赋予新的标签。双花括号表示多重集，而 HASH 函数将每个唯一的多重集映射为一个全新的唯一标签。
[*]第3步（重复）：把第2步重复K次。
# 输入：
# graph: 你要分析的图（包含节点和边）
# initial_labels: 每个节点的初始标签（如果没有，就把节点的“度”当作初始标签）
# K: 迭代次数（即要看几层“朋友圈”）
def Weisfeiler_Lehman(graph, initial_labels, K):
# 1. 初始化：给每个节点起个“名字”（标签）
current_labels = initial_labels
# 2. 创建一个“历史记录本”，用来保存每一轮迭代后，全图所有节点的标签
# 这个记录本最后会用来判断两个图是否相似
history = []
# 3. 开始迭代查看“朋友圈”
for iteration in range(K):
# ----- 核心步骤 A：收集邻居的信息（构建多重集）-----
# 创建一个空字典，用来存“每个节点看到的邻居标签列表”
neighbor_multisets = {}
for node in graph.nodes:
# 遍历当前节点的所有邻居，把它们的【当前名字】装进一个列表
# 注意：这里用的是列表（List），而不是集合（Set）！
# 如果两个邻居标签一样，列表里就出现两次，这就构成了【多重集】
neighbor_names = []
for neighbor in node.neighbors:
neighbor_names.append(current_labels)
# 把这个列表存起来（这就是该节点看到的“多重集”）
neighbor_multisets = neighbor_names
# ----- 核心步骤 B：给自己改标签（哈希）-----
# 创建一个新字典，用来存“下一轮迭代时节点的标签”
new_labels = {}
# 这里需要一个“神奇的字典”（在编程里叫 Hash Map）
# 它的作用：把“我当前的标签 + 邻居多重集” 映射成一个新的标签
hash_map = {}
next_id = 0
for node in graph.nodes:
# 把“自己现在的名字”和“邻居多重集”拼在一起，组成一个长的特征串
# 注意：一定要把“自己”放在第一位！因为可能出现邻居一样的情况
feature_tuple = (current_labels, neighbor_multisets)
# 如果这个特征串以前没见过，就给它发一个没用过的标签
if feature_tuple not in hash_map:
hash_map = next_id
next_id = next_id + 1
# 给节点换上新的标签
new_labels = hash_map
# ----- 核心步骤 C：记录这一刻的全图状态 -----
# 把这一轮所有节点的【新标签】都复制一份，保存到历史记录里
# （注意：是复制，不是引用，防止后面被改掉）
history.append( copy_of(new_labels) )
# 更新，进入下一轮迭代
current_labels = new_labels
# 4. 大功告成！返回整本“历史记录”
return history
第1次迭代后，标签代表“我和我的邻居”。
第2次迭代后，标签代表“我、我的邻居、以及我邻居的邻居”（即2跳范围内的结构）。
第K次迭代后，标签代表了一棵以该节点为根的K层高度的树。
解释：
通过哈希函数计算出来的。在伪代码里，我们有一个 hash_map（哈希字典），它的作用是把一长串复杂的信息压缩成一个int整数(如果我们用度做标签)。
我们看一下这个“复杂信息”长什么样：feature_tuple = (自己上一轮的名字, [所有邻居上一轮的名字列表])
重点来了：因为这个 feature_tuple 里包含了“邻居的名字”，而邻居的名字又是上一轮迭代时生成的，而上一轮迭代的名字又包含了上上一轮邻居的信息……这就形成了“套娃”结构！
一开始，根据每个节点的度生成初始标签，然后开始迭代。
第1轮生成的新标签（比如数字5），它的 feature_tuple 里包含了【1跳邻居的标签】比如(5, )。
第2轮生成的新标签（比如数字38，即把(5, )哈希编号成38），它的 feature_tuple 里包含了【第1轮生成的那些旧标签】，而那些旧标签本身又指向了【1跳邻居】。所以数字38背后对应的 feature_tuple 实际上展开后包含【2跳邻居的信息】。
为什么说标签“代表”了一棵树？因为在哈希表里，我们存着这个对应关系：数字38对应着长字符串 (5, )
而数字5它又对应着更早的长字符串。所以虽然标签表面上只是一个孤零零的数字38，但只要你拿着这个数字去哈希表里查，你可以一直展开，最终展开成一棵以该节点为根，向下延伸K层的树状结构图。
迭代完了，怎么比较两张图呢？
K次迭代后每个节点均获得一个标签 ，用以概括其K跳邻域的结构。随后，可基于这些标签计算直方图或其他汇总统计量，作为图的特征表示。换言之，WL核通过衡量两个图最终所得标签集合之间的差异来计算，把图里所有节点在所有轮次中的标签都拿出来，统计每个标签出现过多少次（形成一个直方图）。
[*]如果两个直方图长得完全不同：这两张图的结构肯定不一样。
[*]如果两个直方图长得基本一样：这两张图极大概率是同构的（结构一致）。
页:
[1]