DeepMatching: A structural seed identification framework for social network alignment

Chenxu Wang, Zhiyuan Zhao, Yang Wang, Dong Qin, Xiapu Luo, Tao Qin

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)


Network alignment aims at finding a bijective mapping between nodes of two networks. Due to its wide application in various fields (e.g., Computer Vision, Data Management, Bioinformatics, and Privacy Protection), researchers have proposed many network alignment algorithms, most of which rely on a set of pre-mapped seeds. However, it is challenging to identify an initial credible set of seeds solely with structural information. In this paper, by exploiting the observation that a true mapping leads to a large portion of consistent edges among the mapped nodes, we formally define the credibility of a mapping as its deviation from a random one. This enables us to measure the credibility of an initial set of seeds. We also present DeepMatching which is a seed identification framework for social network alignment. First, we represent the nodes of the two mapping networks with their structural feature vectors by employing graph embedding techniques. Second, we obtain an initial mapping of the nodes based on the obtained vectors by leveraging point set registration methods. Third, we develop a heuristic algorithm to extract a credible set of seed from the initial mapping. Finally, we utilize the extracted seed set as input of an efficient propagation-based algorithm for large scale network alignment. We conduct extensive experiments to evaluate the performance of DeepMatching, and the results clearly demonstrate its effectiveness and the efficiency.

Original languageEnglish
Title of host publicationProceedings - 2018 IEEE 38th International Conference on Distributed Computing Systems, ICDCS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages11
ISBN (Electronic)9781538668719
Publication statusPublished - 19 Jul 2018
Event38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018 - Vienna, Austria
Duration: 2 Jul 20185 Jul 2018

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Conference38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018


  • Edge Consistency
  • Mapping Credibility
  • Network Alignment
  • Seed Identification

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this