Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem, the proposed algorithms strictly improve the best known feasible region for exact alignment by polynomial-time algorithms.
翻译:图形对齐旨在找到两个相关图表之间的顶点对应物, 这项任务经常在图形采矿应用中出现, 如社交网络分析。 属性图形对齐是图形对齐的变方, 其中利用公开可得的侧信息或属性来帮助图形对齐。 有关属性图形对齐的现有研究侧重于理论性能, 没有计算限制, 或者高效算法的经验性能。 这促使我们用理论性能保障来调查高效算法。 在本文中, 我们提议了两种多元时算法, 以极有可能的方式完全恢复顶点对应物。 与信息理论性限值相比, 提议的算法的可行区域是接近最佳的。 在对种子图形对齐问题进行专门研究时, 拟议的算法严格改进已知的最佳可行区域, 以便通过多元时算法精确对齐。</s>