Focused SANA: Speeding Up Network Alignment

Authors

  • Ilia Leybovich Ben Gurion University of the Negev
  • Rami Puzis Ben Gurion University of the Negev
  • Roni Stern Ben Gurion University of the Negev
  • Maor Reuben Ben Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v9i1.18466

Abstract

Network Alignment (NA) is a generalization of the graph isomorphism problem for non-isomorphic graphs, where the goal is to find a node mapping as close as possible to isomorphism. Recent successful NA algorithms follow a search-based approach, such as simulated annealing. We propose to speed up search-based NA algorithms by pruning the search-space based on heuristic rules derived from the topological features of the aligned nodes. We define several desirable properties of such pruning rules, analyze them theoretically, and propose a pruning rule based on nodes' degrees. Experimental results show that using the proposed rule yields significant speedup and higher alignment quality compared to the state of the art. In addition, we redefine common NA objective functions in terms of established statistical analysis metrics, opening a wide range of possible objective functions.

Downloads

Published

2021-09-01