Attributed Network Alignment: Problem Definitions and Fast Solutions
Attributed Network Alignment: Problem Definitions and Fast Solutions
复制标题
DOI：
10.1109/tkde.2018.2866440
复制
发表时间：
2019-09
影响因子：
8.9
通讯作者：
Si Zhang;Hanghang Tong
中科院分区：
文献类型：
--
作者：
Si Zhang;Hanghang Tong
网络很普遍，并且通常从许多高影响力领域的多个来源收集，这促进了许多需要跨多个网络连接的新兴应用程序的发展。网络对齐（即找到不同网络之间的节点对应关系）已成为许多应用的第一步，因此已经研究了数十年。尽管一些现有的工作可以使用属性信息作为对齐过程的一部分，但它们仍然具有一定的局限性。例如，一些现有的网络对齐方法可以使用节点属性相似性作为先验对齐信息的一部分，而大多数方法仅探索拓扑一致性，而没有底层网络属性之间的一致性。另一方面，传统的图匹配方法将节点和边属性（可能还有拓扑）编码到亲和力矩阵中，并将其表示为受约束的非凸二次最大化问题。然而，这些方法不能很好地扩展到大规模网络。在本文中，我们提出了一系列网络对齐算法（FINAL）来有效地对齐属性网络。关键思想是利用节点/边属性信息来指导（基于拓扑的）对齐过程。我们将此问题表述为凸二次优化问题，并开发有效且高效的算法来解决它。此外，我们推导出FINAL On-Query，这是FINAL的在线变体，可以跨网络为查询节点找到相似的节点。我们对真实网络进行了广泛的评估，以证实我们提出的方法的优越性。
Networks are prevalent and often collected from multiple sources in many high-impact domains, which facilitate many emerging applications that require the connections across multiple networks. Network alignment (i.e., to find the node correspondence between different networks) has become the very first step in many applications and thus has been studied in decades. Although some existing works can use the attribute information as part of the alignment process, they still have certain limitations. For example, some existing network alignment methods can use node attribute similarities as part of the prior alignment information, whereas most of them solely explore the topology consistency without the consistency among attributes of the underlying networks. On the other hand, traditional graph matching methods encode both the node and edge attributes (and possibly the topology) into an affinity matrix and formulate it as a constrained nonconvex quadratic maximization problem. However, these methods cannot scale well to the large-scale networks. In this paper, we propose a family of network alignment algorithms (FINAL) to efficiently align the attributed networks. The key idea is to leverage the node/edge attribute information to guide the (topology-based) alignment process. We formulate this problem as a convex quadratic optimization problem, and develop effective and efficient algorithms to solve it. Moreover, we derive FINAL On-Query, an online variant of FINAL that can find similar nodes for the query nodes across networks. We perform extensive evaluations on real networks to substantiate the superiority of our proposed approaches.