A Multithreaded Algorithm for Network Alignment Via Approximate Matching

Abstract

Network alignment is an optimization problem to find the best one-to-one map between the vertices of a pair of graphs that overlaps in as many edges as possible. It is a relaxation of the graph isomorphism problem and is closely related to the subgraph isomorphism problem. The best current approaches are entirely heuristic, and are iterative in nature. They generate real-valued heuristic approximations that must be rounded to find integer solutions. This rounding requires solving a bipartite maximum weight matching problem at each step in order to avoid missing high quality solutions. We investigate substituting a parallel, half-approximation for maximum weight matching instead of an exact computation. Our experiments show that the resulting difference in solution quality is negligible. We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor Intel Xeon E7-8870 system (from 10 minutes to 36 seconds).