怎么判断两张图“长得像”？Weisfeiler-Lehman(WL)核

yinda_peng

给你两张社交网络图，A图里张三认识李四和王五，B图里赵六认识孙七和周八。如果只看“谁连着谁”（边），你能告诉我这两张图的结构相似吗？这在数学上叫“图同构测试”。对于电脑来说，这不是个简单活，因为把节点顺序随便换一换，邻接矩阵就全变了。总不能把所有的排列组合都试一遍吧。



我们人是怎么看的？我们不会去看矩阵，我们看的是“朋友圈”。

• 看局部角色：你先看每个节点在局部是什么“角色”。比如，节点A是个“交际花”（1跳朋友多），节点B是个“桥梁”（朋友之间互相不认识，但联系着两个大团体）。
• 放大范围确认：为了确认角色，你还会看看“朋友的朋友”（2跳），确保没看走眼。比如这个“交际花”的朋友们之间是不是也互相认识？（如果认识，说明是个小团伙；如果不认识，说明是个纯粹的广播站）。
• 统计角色分布：你把图上所有节点的这些“局部角色”都提取出来，整理成一张“角色清单”（也就是我们后面提到的标签直方图）。
• 对比清单：你拿着图A的“角色清单”和图B的“角色清单”去对比。
  

• 如果清单里的角色类型和数量完全一致，那这两张图的结构肯定是一样的（同构）。
• 如果清单里有不同的“角色”，或者某个角色的数量对不上，那这两张图的结构肯定不一样！
  

WL核的核心思想就是：把这种“朋友圈分层”的办法，变成电脑能懂的语言。

电脑怎么看邻居呢？这里引入一个词：多重集（Multiset）：“没有顺序但允许元素重复”。

• 普通集合 {程序员, 产品经理}
• 多重集 {{程序员, 程序员, 产品经理}}
  

为什么要强调重复？ 因为一个节点有2个程序员朋友，和它有1个程序员朋友，在图结构里是完全不同的概念！顺序不重要（邻接点的顺序不重要），但数量绝对重要（度）！

假设我们有两张图要比较，WL算法是这样迭代的：

• 第1步（开局）：首先，为每个节点分配一个初始标签。在多数图中，该标签即为节点的度。
• 第2步（迭代刷新——这是核心）：接着，通过哈希化节点邻域内当前所有标签构成的多重集，迭代地为每个节点赋予新的标签。 双花括号表示多重集，而 HASH 函数将每个唯一的多重集映射为一个全新的唯一标签。
  

• 第3步（重复）：把第2步重复K次。
  

1. 
   
2. # 输入：
   
3. #   graph: 你要分析的图（包含节点和边）
   
4. #   initial_labels: 每个节点的初始标签（如果没有，就把节点的“度”当作初始标签）
   
5. #   K: 迭代次数（即要看几层“朋友圈”）
   
6. 
   
7. def Weisfeiler_Lehman(graph, initial_labels, K):
   
8.    
   
9.     # 1. 初始化：给每个节点起个“名字”（标签）
   
10.     current_labels = initial_labels  
    
11.    
    
12.     # 2. 创建一个“历史记录本”，用来保存每一轮迭代后，全图所有节点的标签
    
13.     #    这个记录本最后会用来判断两个图是否相似
    
14.     history = []
    
15.    
    
16.     # 3. 开始迭代查看“朋友圈”
    
17.     for iteration in range(K):
    
18.         
    
19.         # ----- 核心步骤 A：收集邻居的信息（构建多重集）-----
    
20.         # 创建一个空字典，用来存“每个节点看到的邻居标签列表”
    
21.         neighbor_multisets = {}
    
22.         
    
23.         for node in graph.nodes:
    
24.             
    
25.             # 遍历当前节点的所有邻居，把它们的【当前名字】装进一个列表
    
26.             # 注意：这里用的是列表（List），而不是集合（Set）！
    
27.             # 如果两个邻居标签一样，列表里就出现两次，这就构成了【多重集】
    
28.             neighbor_names = []
    
29.             for neighbor in node.neighbors:
    
30.                 neighbor_names.append(current_labels[neighbor])
    
31.             
    
32.             # 把这个列表存起来（这就是该节点看到的“多重集”）
    
33.             neighbor_multisets[node] = neighbor_names
    
34.         
    
35.         # ----- 核心步骤 B：给自己改标签（哈希）-----
    
36.         # 创建一个新字典，用来存“下一轮迭代时节点的标签”
    
37.         new_labels = {}
    
38.         
    
39.         # 这里需要一个“神奇的字典”（在编程里叫 Hash Map）
    
40.         # 它的作用：把“我当前的标签 + 邻居多重集” 映射成一个新的标签
    
41.         hash_map = {}
    
42.         next_id = 0
    
43.         
    
44.         for node in graph.nodes:
    
45.             # 把“自己现在的名字”和“邻居多重集”拼在一起，组成一个长的特征串
    
46.             # 注意：一定要把“自己”放在第一位！因为可能出现邻居一样的情况
    
47.             feature_tuple = (current_labels[node], neighbor_multisets[node])
    
48.             
    
49.             # 如果这个特征串以前没见过，就给它发一个没用过的标签
    
50.             if feature_tuple not in hash_map:
    
51.                 hash_map[feature_tuple] = next_id
    
52.                 next_id = next_id + 1
    
53.             
    
54.             # 给节点换上新的标签
    
55.             new_labels[node] = hash_map[feature_tuple]
    
56.         
    
57.         # ----- 核心步骤 C：记录这一刻的全图状态 -----
    
58.         # 把这一轮所有节点的【新标签】都复制一份，保存到历史记录里
    
59.         # （注意：是复制，不是引用，防止后面被改掉）
    
60.         history.append( copy_of(new_labels) )
    
61.         
    
62.         # 更新，进入下一轮迭代
    
63.         current_labels = new_labels
    
64.    
    
65.     # 4. 大功告成！返回整本“历史记录”
    
66.     return history
    

复制代码

第1次迭代后，标签代表“我和我的邻居”。
第2次迭代后，标签代表“我、我的邻居、以及我邻居的邻居”（即2跳范围内的结构）。
第K次迭代后，标签代表了一棵以该节点为根的K层高度的树。
解释：
通过哈希函数计算出来的。在伪代码里，我们有一个 hash_map（哈希字典），它的作用是把一长串复杂的信息压缩成一个int整数(如果我们用度做标签)。
我们看一下这个“复杂信息”长什么样：feature_tuple = (自己上一轮的名字, [所有邻居上一轮的名字列表])
重点来了：因为这个 feature_tuple 里包含了“邻居的名字”，而邻居的名字又是上一轮迭代时生成的，而上一轮迭代的名字又包含了上上一轮邻居的信息……这就形成了“套娃”结构！
一开始，根据每个节点的度生成初始标签，然后开始迭代。
第1轮生成的新标签（比如数字5），它的 feature_tuple 里包含了【1跳邻居的标签】比如(5, [1, 2, 4])。
第2轮生成的新标签（比如数字38，即把(5, [1, 2, 4])哈希编号成38），它的 feature_tuple 里包含了【第1轮生成的那些旧标签】，而那些旧标签本身又指向了【1跳邻居】。所以数字38背后对应的 feature_tuple 实际上展开后包含【2跳邻居的信息】。
为什么说标签“代表”了一棵树？因为在哈希表里，我们存着这个对应关系：数字38对应着长字符串 (5, [1, 2, 4])
而数字5它又对应着更早的长字符串。所以虽然标签表面上只是一个孤零零的数字38，但只要你拿着这个数字去哈希表里查，你可以一直展开，最终展开成一棵以该节点为根，向下延伸K层的树状结构图。

迭代完了，怎么比较两张图呢？
K次迭代后每个节点均获得一个标签 ，用以概括其K跳邻域的结构。随后，可基于这些标签计算直方图或其他汇总统计量，作为图的特征表示。换言之，WL核通过衡量两个图最终所得标签集合之间的差异来计算，把图里所有节点在所有轮次中的标签都拿出来，统计每个标签出现过多少次（形成一个直方图）。

• 如果两个直方图长得完全不同：这两张图的结构肯定不一样。
• 如果两个直方图长得基本一样：这两张图极大概率是同构的（结构一致）。