• 人工智能
• 机器学习
• 深度学习
• 图计算

【免费下载链接】dgl

Python package built to ease deep learning on graph, on top of existing DL frameworks.

项目地址： https://gitcode.com/gh_mirrors/dg/dgl

点击查看 免费下载

本指南围绕 DGL 官方仓库 examples/pytorch/graph_matching 目录下的图匹配工具展开，系统讲解如何在两张 DGLGraph 之间计算图编辑距离（Graph Edit Distance, GED），涵盖 astar、beam、bipartite、hausdorff 四种算法的适用场景、graph_edit_distance 函数的完整参数语义、成本函数设计方法，以及从源码层面剖析搜索树、线性指派（LAP）与豪斯多夫匹配的底层实现。读完本文，你将能够独立安装依赖、调用该工具计算任意两张 DGL 图的结构相似度，并理解四种算法在精确性与效率之间的取舍。

什么是图编辑距离

图编辑距离（GED）是衡量两张图结构相似程度的经典度量，可以视为字符串编辑距离在图上的一般化推广：字符串编辑距离衡量把一个字符串变成另一个字符串所需的最小"插入/删除/替换字符"次数，而 GED 衡量把一张图变成另一张图所需的最小"节点/边的插入、删除、替换（substitution）"代价之和。

在 DGL 的这套实现中，输入是两张 DGLGraph（记为 G1 与 G2），输出是一个三元组：编辑距离数值、节点映射（node_mapping）与边映射（edge_mapping）。映射结果可以直接用于解释"G1 中哪个节点对应 G2 中的哪个节点、哪些边被删除、哪些边被插入"，这在分子结构比对、化合物相似度检索、图数据库近似查询等场景中非常实用。

目录结构与快速上手

本工具位于仓库的 examples/pytorch/graph_matching 目录，仅由三个文件组成：

文件	作用
README.md	使用说明、API 文档与参考文献
ged.py	核心实现，提供 graph_edit_distance 函数与全部内部算法
examples.py	可运行的示例脚本，演示默认成本与自定义成本两种用法

快速运行示例：

# 在 examples/pytorch/graph_matching 目录下
pip install lapjv
python examples.py

示例脚本基于两张仅相差一条边的链式图（G1 有 7 个节点 6 条边，G2 有 6 个节点 5 条边），依次输出四种算法的计算结果（详见后文"运行示例与输出解读"）。

依赖说明

唯一必需的第三方依赖是 lapjv（LAPJV 求解器），它负责求解线性指派问题（Linear Assignment Problem, LAP）。官方注释（见 ged.py）特别指出选择 lapjv 的原因是可扩展性好（scalability），并提及如果不便安装，也可以改用 SciPy 自带的匈牙利算法 scipy.optimize.linear_sum_assignment 作为替代。注意：本工具实现里默认直接 from lapjv import lapjv，若替换为 SciPy 求解器需要自行改写调用处。

四种算法一览与选择建议

graph_edit_distance 通过 algorithm 参数指定算法，四种算法在"精确性"与"计算开销"之间分布如下：

算法	精确性	核心思想	参考文献（对应 README 中的编号）
astar	精确（exact）	A* 图搜索 + Riesen & Bunke 提出的二分启发式	[1] Riesen, Fankhauser, Bunke, "Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic", MLG 2007
beam	近似（approximate）	A* 搜索 + 对 open list 大小设置阈值上限	[2] Neuhaus, Riesen, Bunke, "Fast suboptimal algorithms for the computation of graph edit distance", SPR/SSPR 2006
bipartite	近似（approximate，默认）	节点上的线性指派（LAP），使用 Jonker-Volgenant（JV）算法	[3] Fankhauser, Riesen, Bunke, "Speeding up graph edit distance computation through fast bipartite matching", GbRPR 2011
hausdorff	近似（approximate）	基于豪斯多夫匹配（Hausdorff matching）的估计	[4] Fischer et al., "A Hausdorff heuristic for efficient computation of graph edit distance", SPR/SSPR 2014

从源码 graph_edit_distance 的分支逻辑（ged.py）可以确认：

• astar 与 beam 共用 a_star_search 搜索流程，差异仅在 max_beam_size：beam 模式下搜索树 open list 只保留代价最小的前 k 个节点，从而牺牲精确性换取速度；
• bipartite 走 contextual_cost_matrix_construction 构造带上下文信息的成本矩阵，再用 lapjv 求解整体指派；
• hausdorff 走 hausdorff_matching，只返回一个距离数值。

选择建议：追求精确结果且图规模较小，用 astar；图规模中等且允许有界误差，用 beam 并调节 max_beam_size；大规模图需要快速近似，用默认的 bipartite；只需一个快速下界估计、不需要具体映射时，用 hausdorff。

graph_edit_distance API 详解

完整的函数签名与 docstring 见 ged.py，与 README 保持一致：

graph_edit_distance(
    G1, G2,
    node_substitution_cost=None,
    edge_substitution_cost=None,
    G1_node_deletion_cost=None,
    G2_node_insertion_cost=None,
    G1_edge_deletion_cost=None,
    G2_edge_insertion_cost=None,
    algorithm='bipartite',
    max_beam_size=100,
)

参数语义

参数	类型与形状	语义	默认值
G1, G2	DGLGraph	待比较的两张图	必填
node_substitution_cost	2D numpy 数组，形状 (num_G1_nodes, num_G2_nodes)	[i, j] 表示用 G2 的节点 j 替换 G1 的节点 i 的代价	None 时全 0
edge_substitution_cost	2D numpy 数组，形状 (num_G1_edges, num_G2_edges)	[i, j] 表示用 G2 的边 j 替换 G1 的边 i 的代价	None 时全 0
G1_node_deletion_cost	1D numpy 数组，长度 num_G1_nodes	[i] 表示删除 G1 节点 i 的代价	None 时全 1
G1_edge_deletion_cost	1D numpy 数组，长度 num_G1_edges	[i] 表示删除 G1 边 i 的代价	None 时全 1
G2_node_insertion_cost	1D numpy 数组，长度 num_G2_nodes	[i] 表示插入 G2 节点 i 的代价	None 时全 1
G2_edge_insertion_cost	1D numpy 数组，长度 num_G2_edges	[i] 表示插入 G2 边 i 的代价	None 时全 1
algorithm	string	取值 'astar'、'beam'、'bipartite'、'hausdorff'	'bipartite'
max_beam_size	int	仅 beam 算法有效：open list 中保留的最大搜索树节点数	100

需要特别留意源码中的一个细节：graph_edit_distance 入口处，只要 algorithm != "beam" 就会把 max_beam_size 强制置为 -1（见 ged.py），随后 a_star_search 中以 max_beam_size > 0 作为是否裁剪 open list 的条件（ged.py）。这意味着：只有 beam 算法会受 max_beam_size 约束，astar 的 open list 无上限，理论上能保证找到精确解。

返回值

返回三元组 (edit_distance, node_mapping, edge_mapping)：

• edit_distance：计算得到的编辑距离（float）。
• node_mapping：大小为 2 的元组，分别对应 G1、G2 的节点映射。例如 node_mapping[0][i] 表示 G1 节点 i 映射到的 G2 节点编号，None 表示该节点被删除；node_mapping[1][j] 同理，None 表示 G2 节点 j 是插入的。
• edge_mapping：与 node_mapping 结构完全一致的边映射。
• 对于 hausdorff 算法，node_mapping 与 edge_mapping 均返回 None，因为该近似方法不产生唯一的编辑路径（这也是 README 与 ged.py docstring 中明确说明的行为）。

源码中映射通过 get_sorted_mapping（ged.py）转换为按原始节点/边 ID 对齐的定长列表，方便直接按下标索引查询。

成本函数的设计与默认值

成本函数是 GED 的灵魂：同一对图在不同成本设定下会得到不同的距离与最优映射。工具的默认策略是替换免费、插入/删除代价为 1——即 validate_cost_functions（ged.py）中实现的逻辑：任何传入为 None 的成本数组都被初始化如下，并对用户传入数组做形状断言：

• 节点/边替换成本 → 全 0 矩阵，形状分别为 (num_G1_nodes, num_G2_nodes) 与 (num_G1_edges, num_G2_edges)；
• 节点/边删除与插入成本 → 全 1 向量。

因此，若直接调用 graph_edit_distance(G1, G2)，得到的是"仅统计必须删除或插入多少节点/边"的距离，两张同构图距离为 0。

当需要引入语义相似度（例如节点带有标签或特征）时，应自行构造成本矩阵。examples.py 给出了完整的自定义示例（examples.py），核心做法是：

# 节点替换：节点 ID 相同时代价为 0，否则为 1
node_substitution_cost = np.empty((G1.num_nodes(), G2.num_nodes()))
node_substitution_cost.fill(1.0)
for i in range(G1.num_nodes()):
    for j in range(G2.num_nodes()):
        node_substitution_cost[i, j] = 0.0

# 节点插入/删除代价为 1
G1_node_deletion_cost = np.ones(G1.num_nodes())
G2_node_insertion_cost = np.ones(G2.num_nodes())

# 边替换代价为 0；边插入/删除代价为 0.5
edge_substitution_cost = np.zeros((G1.num_edges(), G2.num_edges()))
G1_edge_deletion_cost = np.full(G1.num_edges(), 0.5)
G2_edge_insertion_cost = np.full(G2.num_edges(), 0.5)

该例最终用 algorithm='astar' 求得距离 0.5：由于节点替换免费、边替换免费，两张图唯一的差异是 G2 比 G1 少一条边，删除该边代价 0.5，因此精确距离为 0.5。

运行示例与输出解读

在 examples.py 中，两张图定义为：

src1 = [0, 1, 2, 3, 4, 5]
dst1 = [1, 2, 3, 4, 5, 6]      # G1：0-1-2-3-4-5-6 链
src2 = [0, 1, 3, 4, 5]
dst2 = [1, 2, 4, 5, 6]         # G2：0-1-2 与 3-4-5-6 两段链（比 G1 少一条边）
G1 = dgl.DGLGraph((src1, dst1))
G2 = dgl.DGLGraph((src2, dst2))

四种算法的输出与注释（源自 examples.py）如下：

调用	输出	解读
graph_edit_distance(G1, G1, algorithm='astar')	0.0	图与自身比较，精确距离为 0
graph_edit_distance(G1, G2, algorithm='astar')	1.0	默认成本下需删除 1 条边
自定义成本 + algorithm='astar'	0.5	边删除成本降为 0.5
graph_edit_distance(G1, G2, algorithm='beam', max_beam_size=2)	3.0	近似结果 ≥ 精确距离（默认成本 1，此处 3.0）
graph_edit_distance(G1, G2, algorithm='bipartite')	9.0	近似结果 ≥ 精确距离；注释提示中间 LAP 存在多个解，结果可能因环境而异
graph_edit_distance(G1, G2, algorithm='hausdorff')	0.0	近似结果 ≤ 精确距离

README 与示例注释（examples.py）总结了三条经验法则：

• astar 给出精确下界之上的真值；beam 与 bipartite 是上界近似（结果 ≥ 精确距离）；
• hausdorff 是下界近似（结果 ≤ 精确距离），适合快速筛选；
• bipartite 的中间 LAP 存在多解，同一输入在不同环境下可能得到不同数值，属正常现象。

源码级原理剖析

1. 成本矩阵的构造（LAP 视角）

construct_cost_functions（ged.py）把"节点替换 + 删除 + 插入"统一编码进一个 (n1+n2) × (n1+n2) 的方阵：左上块是节点替换成本，右上对角块是 G1 节点删除成本，左下对角块是 G2 节点插入成本，其余位置填充 cost_upper_bound（所有成本之和 + 1）以强制禁止非法指派。边矩阵同理，形状为 (m1+m2) × (m1+m2)。这样，图编辑问题被约化为标准线性指派问题，可直接交给 LAP 求解器。

2. A*/Beam 搜索树（精确与近似的分水岭）

a_star_search（ged.py）维护一个以堆实现的 open list，搜索树节点由 search_tree_node 类（ged.py）表示。每个搜索树节点记录：已匹配代价 matched_cost、未来代价的近似估计 future_approximate_cost、已匹配的节点/边、以及未处理的节点/边集合。搜索从"G1 节点 0 与 G2 每个节点替换或删除"开始，每次从堆顶弹出总代价最小的节点展开。当待处理节点归零时即返回当前代价，这保证了 astar 的精确性。

启发式质量的关键在于 future_approximate_cost 的计算：对尚未匹配的节点集合与边集合分别调用 lapjv 求一次线性指派（或纯删除/纯插入时直接求和），得到一个乐观的剩余代价估计。这种"二分启发式"正是参考文献 [1] 提出的方法。

beam 只是在此流程上加了裁剪：当 open list 超过 max_beam_size 时，用 nsmallest 只保留代价最小的 k 个节点并重新堆化（ged.py）。这一处小小的约束就把指数级搜索空间压缩为有界搜索，代价是可能错过全局最优。

3. Bipartite：带边上下文信息的整体指派

contextual_cost_matrix_construction（ged.py）比基础的 LAP 更进一步：在为每对节点 (i, j) 计算替换成本时，会把与 i、j 相关联的边（自环、入边、出边）的替换/删除/插入成本也通过一次局部 lapjv 折算进 cost_matrix[i, j]，即"节点替换成本 = 节点自身代价 + 关联边结构的最优编辑代价"。最后对整个 (n1+n2) × (n1+n2) 矩阵再求解一次 lapjv（ged.py），得到节点指派，再由 edit_cost_from_node_matching（ged.py）按节点映射逐对结算边编辑代价，汇总出最终距离与映射。这就是参考文献 [3] 的二分匹配加速思路。

4. Hausdorff：免映射的下界估计

hausdorff_matching（ged.py）不构造唯一映射，而是逐节点对计算"替换优于删除/插入"的节省量：对每个节点对的关联边，用 min 操作找出替换成本低于删除/插入成本的节省，再以 argpartition 求部分和得到边编辑下界，最终取"节点数差产生的必然删除/插入下界"与"逐节点最优替换成本之和"两者的较大值作为豪斯多夫距离。该值总是精确 GED 的下界，计算复杂度低，非常适合海量图对的粗筛。

5. 对 DGL 图 API 的依赖

工具全程通过标准 DGL 图查询接口访问拓扑结构，例如 G.in_edges([node_id], "all")、G.out_edges([node_id], "all")、G.edge_ids(u, v, return_array=True)、G.has_edge_between(i, i) 等（见 ged.py 的 get_edges_to_match 与 ged.py 的边分类逻辑）。这些方法定义在 python/dgl/heterograph.py 中：in_edges（python/dgl/heterograph.py#L3344）、out_edges（python/dgl/heterograph.py#L3430）、edge_ids（python/dgl/heterograph.py#L3147）、num_nodes（python/dgl/heterograph.py#L2493）与 num_edges（python/dgl/heterograph.py#L2685）。边编辑成本按 eid 索引，而 in_edges(..., "eid") 恰好返回入边 ID 数组，二者无缝衔接；自环通过 has_edge_between 加 edge_ids(..., return_array=True) 单独提取，并在 np.setdiff1d 中从出入边集合中剔除，确保每条边只被计入一次。

使用注意事项

• 图必须为同构图（homogeneous）：成本矩阵按节点/边 ID 直接索引，多类型异构图需要自行拆分为单类型图后再比较。
• 成本矩阵形状必须精确匹配：validate_cost_functions 会断言所有数组形状，例如节点替换矩阵必须是 (G1.num_nodes(), G2.num_nodes())，否则直接抛出 AssertionError。
• max_beam_size 仅对 beam 生效：其他算法下该参数被强制置为 -1，不会裁剪 open list。
• 结果可复现性：bipartite 的中间 LAP 存在多解，不同环境（LAPJV 版本、numpy 版本）下结果可能不同；astar 是精确算法，结果确定。
• 复杂度预期：astar 在最坏情况下为指数级，beam 的开销由 max_beam_size 控制，bipartite 与 hausdorff 以多项式级指派/排序为主，适合较大图。
• hausdorff 不返回映射：若下游任务需要编辑路径（如可视化差异），应改用其他三种算法。

延伸阅读

• 完整 API 文档与参考文献：examples/pytorch/graph_matching/README.md
• 核心实现（约 1300 行）：examples/pytorch/graph_matching/ged.py
• 可直接运行的示例脚本：examples/pytorch/graph_matching/examples.py
• 底层依赖的 DGL 图查询接口：python/dgl/heterograph.py

如需深入算法细节，可查阅 README 引用的四篇文献：Riesen & Bunke 的二分启发式（[1]）、Neuhaus 等的快速次优算法（[2]）、Fankhauser 等的快速二分匹配（[3]）以及 Fischer 等的豪斯多夫启发式（[4]），它们分别对应 astar、beam、bipartite 与 hausdorff 四种实现的算法出处。

• 人工智能
• 机器学习
• 深度学习
• 图计算

【免费下载链接】dgl

Python package built to ease deep learning on graph, on top of existing DL frameworks.

项目地址： https://gitcode.com/gh_mirrors/dg/dgl

点击查看 免费下载