Attributed Network Alignment: Problem Definitions and Fast Solutions

Si Zhang, Hanghang Tong

Research output: Contribution to journalArticlepeer-review

Abstract

Networks are often collected from multiple sources in many high-impact domains, facilitating many emerging applications that require the connections across multiple networks. Network alignment 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.

Original languageEnglish (US)
JournalIEEE Transactions on Knowledge and Data Engineering
Volume31
Issue number9
DOIs
StatePublished - Sep 1 2019
Externally publishedYes

Keywords

  • Approximation algorithms
  • Feature extraction
  • Modeling
  • Network alignment
  • Network topology
  • Optimization
  • Symmetric matrices
  • Topology
  • 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