如何在Networkx中使用不同k阶Weisfeiler-Lehman算法判断图同构

你遇到的是1阶Weisfeiler-Lehman（WL）算法的局限性——它只能区分大部分非同构图，但对某些特殊结构（比如你构造的g1和g2）会失效，因为这两个图的1阶WL特征（节点标签+直接邻居标签的聚合）完全一致，导致哈希值相同。高阶WL算法（比如2阶、k阶）通过考虑更复杂的邻域结构（如节点对、k元组的邻域），可以区分这类图。

以2阶WL为例，核心是把节点对（无序）作为基本单元，迭代更新它们的标签：

1. 初始化标签：对每个无序节点对(u, v)（u ≤ v），用两个节点的度数组合作为初始标签；
2. 迭代更新标签：对每个节点对，收集其所有“邻域节点对”的标签（比如对于(u, v)，收集所有与u相邻的节点w组成的(w, v)，以及与v相邻的节点w组成的(u, w)的当前标签），将这些标签排序后哈希得到新标签；
3. 收敛判断：重复更新直到标签不再变化，或达到指定迭代次数；
4. 生成图哈希：将所有节点对的最终标签组成多集合，对该集合哈希得到整个图的哈希值。

下面是基于NetworkX的2阶WL哈希实现，可直接区分你的g1和g2：

import networkx as nx
import hashlib
from collections import defaultdict

def weisfeiler_lehman_k_graph_hash(G, k=2, iterations=3):
    # 初始化无序节点对的标签
    labels = defaultdict(str)
    nodes = sorted(G.nodes())
    
    # 初始标签用节点度数的组合生成
    for i in range(len(nodes)):
        for j in range(i, len(nodes)):
            u, v = nodes[i], nodes[j]
            initial_label = f"{G.degree(u)},{G.degree(v)}"
            labels[(u, v)] = initial_label
    
    for _ in range(iterations):
        new_labels = defaultdict(str)
        for (u, v) in labels:
            neighbor_pairs = []
            # 收集u的邻居与v组成的节点对标签
            for w in G.neighbors(u):
                pair = tuple(sorted((w, v)))
                neighbor_pairs.append(labels[pair])
            # 收集v的邻居与u组成的节点对标签
            for w in G.neighbors(v):
                pair = tuple(sorted((u, w)))
                neighbor_pairs.append(labels[pair])
            
            # 排序后拼接并哈希生成新标签
            neighbor_pairs.sort()
            combined = ",".join(neighbor_pairs)
            new_hash = hashlib.md5(combined.encode()).hexdigest()[:8]
            new_labels[(u, v)] = new_hash
        labels = new_labels
    
    # 基于所有节点对的最终标签生成图哈希
    sorted_labels = sorted(labels.values())
    graph_hash = hashlib.md5(",".join(sorted_labels).encode()).hexdigest()
    return graph_hash

# 测试你的图
g1 = nx.Graph()
g1.add_edges_from([(1, 2), (1, 4), (2, 4), (2, 5), (3, 5), (3, 6), (5, 6)])
g2 = nx.Graph()
g2.add_edges_from([(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6)])

# 生成2阶WL哈希
g1_hash_2 = weisfeiler_lehman_k_graph_hash(g1, k=2)
g2_hash_2 = weisfeiler_lehman_k_graph_hash(g2, k=2)

print(g1_hash_2 == g2_hash_2)  # 输出False，正确区分非同构图
print(nx.is_isomorphic(g1, g2))  # 输出False，验证结果

• k的选择：k越大，WL算法的区分能力越强，但计算复杂度也越高。对于大多数常见非同构图，2阶或3阶WL足够区分；
• 初始标签自定义：如果图节点有自定义属性，可以替换初始标签的生成逻辑（比如用节点的属性值代替度数）；
• NetworkX局限：目前NetworkX确实没有内置的高阶WL哈希函数，需要手动实现。

内容的提问来源于stack exchange，提问作者jAdex