Graph alignment, which aims at identifying corresponding entities across multiple networks, has been widely applied in various domains. As the graphs to be aligned are usually constructed from different sources, the inconsistency issues of structures and features between two graphs are ubiquitous in real-world applications. Most existing methods follow the ``embed-then-cross-compare'' paradigm, which computes node embeddings in each graph and then processes node correspondences based on cross-graph embedding comparison. However, we find these methods are unstable and sub-optimal when structure or feature inconsistency appears. To this end, we propose SLOTAlign, an unsupervised graph alignment framework that jointly performs Structure Learning and Optimal Transport Alignment. We convert graph alignment to an optimal transport problem between two intra-graph matrices without the requirement of cross-graph comparison. We further incorporate multi-view structure learning to enhance graph representation power and reduce the effect of structure and feature inconsistency inherited across graphs. Moreover, an alternating scheme based algorithm has been developed to address the joint optimization problem in SLOTAlign, and the provable convergence result is also established. Finally, we conduct extensive experiments on six unsupervised graph alignment datasets and the DBP15K knowledge graph (KG) alignment benchmark dataset. The proposed SLOTAlign shows superior performance and strongest robustness over seven unsupervised graph alignment methods and five specialized KG alignment methods.
翻译:图形对齐旨在确定多个网络的对应实体,在不同的领域广泛应用。由于要对齐的图表通常是从不同来源构建的,因此两个图形的结构和特征的不一致问题在现实世界应用中普遍存在。大多数现有方法都遵循“嵌入-正交叉比较”的范式,该范式计算每个图形中的节点嵌入,然后根据交叉嵌入比较处理对等程序。然而,我们发现这些方法不稳定,而且当结构或特征出现不一致时,也是次最佳的。为此,我们建议建立一个不易监督的图形对齐框架,共同进行结构学习和优化优化。我们把图形对齐转换成两个内部矩阵之间的最佳运输问题,而无需交叉对比比较。我们进一步纳入多视图结构学习,以加强图形表达能力,减少结构与特征不一致性的影响。此外,我们开发了一种基于更强烈的算法,以解决SLOTAlign结构中的联合优化问题,以及可配置的高级趋同性图表结果。最后,我们对SLOBG 的拟议数据对齐性做了广泛的测试。