Attributed Network Alignment: Problem Definitions and Fast Solutions

Si Zhang, Hanghang Tong

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1680-1692
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume31
Issue number9
DOIs
StatePublished - Sep 2019

Keywords

  • Network alignment
  • alignment consistency
  • attributed networks
  • on-query alignment

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Attributed Network Alignment: Problem Definitions and Fast Solutions'. Together they form a unique fingerprint.

Cite this