Python图编辑距离接口差异及大图GED计算方法咨询

两个函数均为NetworkX库提供的图编辑距离（Graph Edit Distance, GED）计算接口，底层都基于A*搜索框架，但在计算内容、运行逻辑上有明确区别：

• graph_edit_distance()
  计算内容：返回两个图之间全局最优的精确最小编辑距离，即源图转换为目标图所需的节点增删、边增删、节点/边属性替换操作的最小代价总和，结果是确定值，不存在误差。
  计算逻辑：遍历全量可能的节点匹配空间，搜索过程中仅维护当前找到的最优代价作为剪枝上界，必须确认遍历完所有代价低于当前上界的匹配分支、拿到全局最小值后才会返回结果。该模式下搜索空间随节点数呈阶乘级增长，内存会因为存储大量待展开的搜索节点快速占用，节点数超过20时就很容易出现计算超时、内存溢出的问题。
• optimize_graph_edit_distance()
  计算内容：返回一个按编辑代价从小到大输出结果的生成器，不会直接给出最终精确值。迭代该生成器时，每一轮产出的都是当前搜索到的更优GED上界，直到迭代到最后一个值时，才和graph_edit_distance()返回的精确结果完全相等。
  计算逻辑：同样基于A*搜索，但优化了结果返回和剪枝逻辑：每找到一个比当前上界更小的可行编辑代价，就立刻通过生成器返回该值，同时用新的更小上界剪掉所有代价更高的搜索分支。使用者可以在拿到满足业务精度要求的近似值时直接终止迭代，不需要等全量搜索跑完，灵活性更高，相同搜索深度下内存占用比前者低30%~50%。

注：如果将optimize_graph_edit_distance()返回的生成器完整迭代到终止，最终得到的精确GED值和graph_edit_distance()的返回结果完全一致。

图编辑距离的精确求解本身是NP难问题，当图节点规模超过30时，全量A*搜索的时间、内存开销会达到不可用的程度，可根据业务对精度的要求选择以下方案：

• 启发式近似精确搜索
  不需要完全放弃A*搜索框架，通过剪枝、提前终止策略把开销降到可接受范围：
  • 直接使用optimize_graph_edit_distance()设置终止条件：比如连续2_{3轮迭代返回的上界差值小于预设阈值（比如总代价的1%），就直接终止迭代返回当前值，该结果和真实精确值的误差通常在5%以内，速度比全量搜索快1}2个数量级。
  • 给graph_edit_distance()传入基于二分图匹配的启发式代价函数做初始上界估算，替代默认的0初始上界，可以剪掉90%以上的无效搜索分支，百节点以内的带属性图通常能在几分钟内跑出精确结果。
• 结构特征近似计算
  百节点以上规模的图不需要走编辑路径匹配逻辑，可以通过结构特征映射快速计算近似距离：
  • 基于二分图匹配的近似GED算法：只做节点邻域结构的最优匹配，不回溯全量匹配路径，时间复杂度可以降到O(n³)，千节点以内的图计算时间可以控制在秒级，结果和真实GED的相关性通常能达到0.8以上。
  • 图嵌入近似：用Graph2Vec、FGSD等无监督图嵌入方法把全图映射为固定维度的低维向量，用向量间的距离近似GED，计算复杂度和节点数呈线性关系，可支持万级节点的大图距离计算，适合对精度要求不高、需要批量计算大量图对距离的场景。
• 图简化后精确计算
  如果业务要求必须得到精确GED值，可以先对大图做降维简化再计算：
  • 先做图结构压缩，把度为1的悬挂节点、结构完全同构的重复邻域子结构合并为超节点，通常能把图规模压缩到原有的1/3~1/2，再跑精确GED计算。
  • 按连通分量、节点属性分布把大图拆分为多个互不重叠的子图，分别计算子图对的编辑距离再加权求和，避免全图节点匹配的阶乘级复杂度。

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