使用NetworkX查找图列表中的同构对并排除自同构的实现方法

核心优化逻辑：避免两两图做同构校验的O(n²)复杂度开销，采用正则哈希分组思路，先为每个图生成同构唯一标识，再按标识分组提取配对，性能比两两校验高1~2个数量级。

实现步骤 #

• 步骤1：图结构归一化表示：用Weisfeiler-Lehman（WL）哈希作为同构类的唯一标识，所有属于同一同构类的图会生成完全相同的哈希值。对准确率要求极高的场景，可在分组后补充精确同构校验避免哈希碰撞。
• 步骤2：按哈希值对图分组，每个分组内的所有图两两互为同构。
• 步骤3：从每个分组中生成无序对，仅保留索引i<j的配对，天然剔除自配对（i=j的情况）和重复逆序对（如(G3,G0)）。如果需要额外剔除结构完全相同的重复图配对，可在分组前先对边列表排序去重。

代码示例 #

import networkx as nx
from itertools import combinations

# 输入边列表集合
G_list = [[(0,1), (0,2)], [(0,3), (1,3)], [(0,3), (1,3)], [(0,3), (1,3), (2,3)]]

# 同构类分组
iso_groups = {}
for idx, edges in enumerate(G_list):
    g = nx.Graph(edges)
    # 生成WL哈希，可调整迭代次数提高哈希区分度
    iso_key = nx.weisfeiler_lehman_graph_hash(g, iterations=3)
    iso_groups.setdefault(iso_key, []).append(idx)

# 生成符合要求的同构对，可根据需要存储图对象或者索引标识
G_iso = []
for group in iso_groups.values():
    if len(group) < 2:
        continue
    # 生成所有不重复的两两组合
    for a, b in combinations(group, 2):
        # 若需剔除结构完全相同的配对，可增加判断：if G_list[a] != G_list[b] 再加入结果
        G_iso.append((f"G{a}", f"G{b}"))

print(G_iso)

补充说明 #

如果你的场景图规模很小、总数量少于100，也可以直接用nx.is_isomorphic(g1, g2)做两两校验，规模较大时必须用哈希分组方案降低开销。

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