计算难的图问题一直以来都是学术界的研究热点之一，由于传统算法的计算复杂度过高，在实际应用中往往会受到诸多限制。北京大学教授、智源青年科学家邹磊团队提出了一种新颖的被称作 Noah（Neural-optimized A* algorithm的缩写）的方法，它结合了图神经网络和传统的 A* 搜索算法，以更有效和更智能的方式计算近似最小图编辑距离（mGED）。这种结合主要体现在两个方面：第一，通过提出的图路径网络（GPN）学习 A* 算法中的估计函数h(·)。预训练的 mGED 和其对应的编辑路径也被纳入模型训练，从而帮助 A* 搜索算法优化搜索方向。第二，学习了一个可变大小的 beam size，可以帮助 A* 算法减少搜索空间大小并满足应用对计算准确度的需求。该方法不同于以往使用端到端的神经网络来替换图相似度计算问题的思路，而是聚焦在如何使用图神经网络来自动学习搜索算法中的估计函数，替换传统算法中由人来定义的启发式策略；从而提升整体算法的准确度、效率和可扩展性；同时又能保证计算结果的可解释性。实验结果验证了所提方法能处理的图大小比 SODA（State-of-the-art）算法提高了一个数量级，并且计算效率和准确度有了明显提升。
图左. 传统基于A*搜索的最小图编辑距离算法 图右. 提出的融合图神经网络和A*搜索的算法框架Noah（图片来源：学者提供）
