NetworkX中两个multiDiGraph同构验证失败问题排查求助

1. 核对节点结构特征的一致性 #

同构图的节点必须具备一一对应的结构特征，可通过以下代码提取并对比：

def get_node_features(G):
    features = {}
    for node in G.nodes():
        features[node] = (
            G.in_degree(node),    # 入度
            G.out_degree(node),   # 出度
            len(G.in_edges(node, keys=True)),  # 入多重边数量
            len(G.out_edges(node, keys=True))  # 出多重边数量
        )
    return features

# 提取两个图的节点特征
feat1 = get_node_features(G1)
feat2 = get_node_features(G2)

# 统计特征出现频次，判断是否一致
from collections import Counter
print("G1节点特征频次:", Counter(feat1.values()))
print("G2节点特征频次:", Counter(feat2.values()))

若频次结果不同，说明节点的核心结构特征不匹配，直接导致图不同构。

2. 对比边的分布与属性差异 #

总边数相同不代表边的分布、多重性或属性一致，可通过生成边签名来对比：

def get_edge_signatures(G, node_features):
    sigs = []
    for u, v, key, attr in G.edges(data=True, keys=True):
        # 用节点特征替代原编号，生成统一的边签名
        sig = (node_features[u], node_features[v], attr)
        sigs.append(sig)
    return sorted(sigs)

# 生成并对比排序后的边签名
sigs1 = get_edge_signatures(G1, feat1)
sigs2 = get_edge_signatures(G2, feat2)

if sigs1 != sigs2:
    diff_g1 = [s for s in sigs1 if s not in sigs2]
    diff_g2 = [s for s in sigs2 if s not in sigs1]
    print("G1独有的边特征:", diff_g1[:5])
    print("G2独有的边特征:", diff_g2[:5])

签名列表不一致时，说明边的连接关系或属性存在差异。

3. 手动生成候选节点映射验证 #

若特征统计一致但自动验证失败，可基于特征匹配生成候选映射，手动验证：

from collections import defaultdict

def build_candidate_mapping(feat1, feat2):
    group1 = defaultdict(list)
    for node, feat in feat1.items():
        group1[feat].append(node)
    group2 = defaultdict(list)
    for node, feat in feat2.items():
        group2[feat].append(node)
    
    mapping = {}
    for feat in group1:
        if len(group1[feat]) != len(group2[feat]):
            return None
        # 按特征组配对节点（组内节点数少时可尝试全排列）
        for n1, n2 in zip(group1[feat], group2[feat]):
            mapping[n1] = n2
    return mapping

# 生成映射并验证
candidate_map = build_candidate_mapping(feat1, feat2)
if candidate_map:
    print("候选映射验证结果:", nx.is_isomorphic(G1, G2, edge_match=lambda e1,e2: e1==e2, node_mapping=candidate_map))

若候选映射验证通过，说明自动检测算法未找到正确映射；若不通过，特征组内节点仍存在结构差异。

4. 显式指定边属性匹配规则 #

如果图的边带有自定义属性（如weight、label），默认的nx.is_isomorphic会忽略属性，需显式指定匹配规则：

# 验证时强制匹配所有边属性
is_iso_with_attr = nx.is_isomorphic(G1, G2, edge_match=lambda e1, e2: e1 == e2)
print("考虑边属性的同构验证结果:", is_iso_with_attr)

若之前未指定该参数，可能因边属性不同导致验证失败。

5. 可视化局部子图对比 #

若以上方法仍无法定位，可提取特征相同的节点子图，可视化对比结构：

import matplotlib.pyplot as plt

# 选取任意一组特征对应的节点
target_feat = next(iter(feat1.values()))
nodes_g1 = [n for n, f in feat1.items() if f == target_feat]
nodes_g2 = [n for n, f in feat2.items() if f == target_feat]

subg1 = G1.subgraph(nodes_g1)
subg2 = G2.subgraph(nodes_g2)

plt.figure(figsize=(12,5))
plt.subplot(121)
nx.draw(subg1, with_labels=True)
plt.title("G1子图")
plt.subplot(122)
nx.draw(subg2, with_labels=True)
plt.title("G2子图")
plt.show()

通过可视化可直观观察子图的连接结构是否一致。

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