Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment

无监督图对齐是指仅利用图结构和节点特征，找到一对属性图之间的一对一节点对应关系。现有工作中，一类方法首先计算节点表示，然后匹配具有相似嵌入的节点，这种方法直观但缺乏针对无监督图对齐的明确目标。另一类方法通过Gromov-Wasserstein（GW）学习将问题简化为最优传输（OT），并具有明确定义的目标，但在传输成本的设计方面还有很大的改进空间。本文提出了一种原则性的方法，结合了它们的优点，受模型表达能力的理论分析的启发。我们注意到在区分匹配和未匹配节点对时判别能力的局限性，通过特征变换改进了GW学习的成本设计，从而实现了跨维度的特征交互。此外，我们提出了一种简单而有效的基于嵌入的启发式算法，受Weisfeiler-Lehman测试的启发，并将其先验知识添加到OT中，以处理非欧几里得数据。此外，我们是第一个通过将问题简化为最大权重匹配来保证一对一匹配约束的算法设计。算法设计通过堆叠（一种集成学习策略）有效地结合了我们的OT和基于嵌入的预测。我们提出了一个名为\texttt{CombAlign}的模型框架，将所有上述模块集成在一起，逐步完善节点对齐。通过大量实验证明，与现有最先进方法相比，我们的模型在对齐精度方面有显着提高，并验证了所提出模块的有效性。

本文旨在解决无监督图对齐问题，即通过图结构和节点特征找到一一对应的节点。文章提出一种基于Gromov-Wasserstein（GW）学习和特征变换的方法，旨在提高匹配准确性。

文章提出的方法结合了现有方法的优点，通过特征变换提高GW学习的成本设计，同时利用基于嵌入的启发式方法来增强非欧几里德数据的表达能力，并通过最大权匹配来保证一对一匹配约束。

本文提出的方法在多个数据集上进行了广泛的实验，证明了其在对齐准确性方面的显著改进。此外，文章还提供了开源代码，并呼吁对该领域进行更深入的研究。

与本文相关的研究包括基于图嵌入的图匹配方法和基于最优传输的图匹配方法。其中，文章提到了Graph2Vec、DeepWalk、Node2Vec、MAGNA、GAlign等相关研究。