为可解释且健壮的无监督图对齐过程，采用信息最大化的最优运输算法

《Knowledge-Based Systems》：Information-maximized optimal transport for interpretable and robust unsupervised graph alignment

　　

Jiayu Zhang|Chunyu Liu|Zeshu Tian|Hongli Zhang

哈尔滨工业大学网络空间科学学院，哈尔滨，150001，中国黑龙江省

摘要

无监督图对齐旨在在无法访问真实映射的情况下，识别两个图之间的语义对应节点。这项技术在社交网络整合和知识图谱对齐等应用中起着至关重要的作用。然而，大多数现有方法依赖于成熟的最优传输范式，这些范式容易受到异常结构和局部噪声的影响。此外，对齐过程的可解释性往往被忽视，限制了这些模型在现实世界场景中的透明度和可靠性。为了解决这些挑战，我们提出了IMOTAlign，这是一种新的无监督框架，它在提供具有竞争力的对齐准确性的同时，还具备可解释性和鲁棒性。在该框架中，我们通过引入互信息最大化机制来扩展最优传输范式，从而形成一个信息最大化最优传输范式，该机制鼓励传输计划关注图之间的语义连贯性和结构弹性对应关系。此外，我们还提出了一种对齐感知图解释器，它在传输过程中运作，以揭示支持对齐决策的结构模式，并提高模型的透明度。在多个基准测试上的广泛实验表明，IMOTAlign实现了最先进的对齐性能，同时展现了强大的鲁棒性和清晰的可解释性。

引言

图对齐旨在识别两个图之间的语义等价节点，从而实现跨网络的对应关系，尽管拓扑或节点特征可能存在差异[1]。它是图结构数据分析的基石，支持诸如社交网络去匿名化、跨平台用户画像、知识图谱融合和生物网络整合等应用[2]、[3]、[4]。由于其在各种领域的广泛应用以及在连接不同图数据方面的基础性作用，图对齐吸引了学术界和工业界的越来越多的关注。

早期的图对齐方法遵循了监督范式[5]、[6]、[7]，利用已知的锚点链接通过优化嵌入相似性或学习跨图变换来学习节点对应关系。虽然在使用高质量锚点时有效，但由于隐私限制、数据稀疏性和平台异构性，其在现实世界环境中的应用受到限制。这导致了对无监督对齐的兴趣日益增加，无监督对齐可以在没有真实映射的情况下推断节点对应关系。无监督方法通常包括：（1）通过随机漫步、图神经网络（GNN）或几何嵌入生成节点表示；（2）通过相似性度量或最优传输来推断对齐[8]。这种范式的转变使无监督图对齐成为解决现实世界中对齐挑战的一种有前景且实用的方法。

尽管无监督图对齐在多个方向上取得了进展，但关键的限制阻碍了其在现实世界中的应用。首先，大多数方法严重依赖于成熟的最优传输（OT）[9]、[10]来推断节点对应关系，假设结构得以保持并且映射全局一致。尽管在理论上是合理的，但这些假设在实践中常常失败，因为结构噪声（包括噪声连接、无关节点和对抗性扰动）可能会破坏OT假设的全局结构一致性，如图1所示。例如，在跨平台社交网络中，不活跃或噪声较大的用户可能会产生误导性的拓扑结构，导致错误的匹配。如果没有自适应机制，静态OT计划仍然容易受到这些偏差的影响，从而限制了鲁棒性。其次，大多数现有方法缺乏可解释性，难以深入了解对齐决策。在生物网络等敏感领域，未解释的蛋白质或基因对齐可能会破坏下游的预测或实验。这些挑战突显了需要一个更强大且可解释的框架，以处理现实世界的不确定性并提供可信的对齐解释。

为了解决上述挑战，我们提出了IMOTAlign，这是一种用于图对齐的新无监督框架。基于最优传输范式，IMOTAlign整合了结构意识和语义指导，以共同提高对齐的鲁棒性和可解释性。为了减轻依赖成熟传输计划但在结构不一致性下表现不佳的现有方法的限制，我们在传输过程中引入了跨图互信息最大化机制。通过最大化匹配节点之间的互信息，这种机制不同于传统的基于平滑的正则化方法，它的目的不仅仅是稳定优化和平滑传输计划，而是保持图之间的共享结构和语义规则性，从而引导传输过程朝着更全局一致的对应关系发展，并提高其对结构异常（如噪声连接和孤立簇）的抵抗力。为了进一步提高可解释性，我们设计了一种与对齐流程紧密耦合的对齐感知图解释器。它经过训练，能够识别驱动对齐决策的关键子结构和关系模式。通过量化结构层面的贡献并生成强调显著性的解释，该模型帮助用户理解为什么节点对被匹配，从而提高信任度和透明度。因此，IMOTAlign提供了一个平衡准确性、鲁棒性和可解释性的统一解决方案，推动了在复杂和噪声环境中图对齐的发展。此外，我们框架中探索的优化驱动和熵感知的目标设计与机器学习领域最近的methodological进展[11]、[12]、[13]相一致，进一步强调了在复杂学习环境中结构化目标工程的基本相关性。本工作的主要贡献总结如下：

• •
  我们提出了一种新的无监督图对齐框架IMOTAlign，它在提供对结构噪声的鲁棒性的同时，实现了具有竞争力的对齐准确性，并具有透明的可解释性。
• •
  我们提出了一种信息最大化最优传输（IMOT）范式用于图对齐，在传输过程中加入了互信息最大化机制，以提高语义连贯性和结构鲁棒性。
• •
  我们提出了一种专为对齐任务设计的对齐感知图解释器，将其集成到模型中，以量化结构层面的贡献并生成可解释的对齐决策。
• •
  在多个基准测试上的广泛实验表明，我们的方法在准确性和鲁棒性方面始终优于现有方法，实现了最先进的性能。

章节片段

监督图对齐方法

监督方法利用标记的锚点链接来训练模型，学习跨网络的节点表示和对齐映射。DeepLink [14] 结合了网络采样和深度神经网络以及双重学习，自动提取特征并提高链接性能，其迭代细化机制有助于稳定学习到的嵌入空间。为了集成异构信号，NAME [15] 采用了一种多视图嵌入方案，晚期融合结构、属性等

提出的框架

如图2所示，IMOTAlign是一种无监督图对齐框架，通过三个紧密协调的组件来提高鲁棒性和可解释性。具体来说，对齐感知图解释器首先通过识别与对齐相关的子结构并抑制误导性的连接来细化输入图结构。基于细化的结构以及节点特征，自适应多视图结构融合模块然后构建多个互补的

实验

在本节中，我们全面评估了所提出的IMOTAlign框架在对齐性能、鲁棒性和可解释性方面的表现。我们旨在解决以下关键研究问题：

• •
  (Q1) IMOTAlign能否在无监督图对齐任务中实现最先进的性能？
• •
  (Q2) IMOTAlign中的各个组件是否对最终的对齐性能有积极贡献？
• •
  (Q3) 与现有方法相比，IMOTAlign是否对结构和特征级别的扰动更加鲁棒？

结论

在这项工作中，我们提出了IMOTAlign，这是一种无监督图对齐框架，它同时提高了鲁棒性和可解释性。为此，我们将信息最大化机制集成到最优传输范式中，使IMOTAlign能够在抑制结构扰动的影响的同时保持全局结构一致性。此外，还结合了对齐感知解释器，揭示了对对齐过程最有影响力的子结构。

CRediT作者贡献声明

Jiayu Zhang：撰写——原始草稿、验证、软件、方法论、数据策划。Chunyu Liu：可视化。Zeshu Tian：可视化。Hongli Zhang：撰写——审稿与编辑、监督、资金获取。

利益冲突声明

作者声明他们没有已知的会影响到本文报告工作的竞争性财务利益或个人关系。