带空间距离考量的图连通分量图编辑距离算法问询

问题背景 #

现有两个规模相同、节点一致但边集不同的非连通图，需对比图1的连通分量a与图2的连通分量b。要求同时满足：计算将a转换为b结构的图编辑距离，同时考量二者的空间距离，确保转换后结构一致且位置重合。示例中需为a添加2条边，并将其向右移动4步、向下移动1步。

已知可行方法 #

• 质心位置对齐：计算连通分量所有节点坐标的质心（x坐标均值、y坐标均值），通过质心间的欧几里得距离衡量整体空间偏移。这种方法能反映连通分量的整体位置，避免单个节点的偶然性误差。
• 点集匹配算法：把连通分量的节点看作点集，用迭代最近点（ICP）算法做匹配，找到最优平移（若允许可包含旋转、缩放）变换，使两个点集的整体匹配误差最小。适合节点对应关系明确的场景，能给出全局最优的位置变换参数。
• 联合代价优化模型：扩展图编辑距离的代价函数，将结构编辑代价（增删边的成本）与位置变换代价（如平移距离、节点对齐误差）加权合并，形成联合优化目标，通过动态规划或启发式搜索求解最优转换方案。

对你初步思路的点评 #

你提出的“选取最靠下且最靠左的对应节点计算欧几里得距离”属于锚点匹配法，优点是计算简单直观，适合网格图这类有明确锚点特征的场景。但存在两个局限：

• 若连通分量中有多个节点同时满足“最靠下最靠左”（坐标相同），会出现锚点选取歧义；
• 单个锚点的位置误差会直接影响整体位置评估的准确性，鲁棒性不如质心或ICP方法。

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