Fast parallel algorithms for graph similarity and matching

• Global graph alignment on supercomputer-class clusters.
• Experimentally we demonstrate the scalability of our algorithm.
• Alignment of networks of sizes two orders of magnitude larger than currently possible.
• Serial NSD description heavily revised; introduction condensed or otherwise updated.
• New section comparing our method to a recent multithreaded approach.

This paper addresses the problem of global graph alignment on supercomputer-class clusters. We define the alignment of two graphs, as a mapping of each vertex in the first graph to a unique vertex in the second graph so as to optimize a given similarity-based cost function.1 Using a state of the art serial algorithm for the computation of vertex similarity scores called Network Similarity Decomposition (NSD), we derive corresponding parallel formulations. Coupling this parallel similarity algorithm with a parallel auction-based bipartite matching technique, we obtain a highly efficient and scalable graph matching pipeline. We validate the performance of our integrated approach on a large parallel platform and on diverse graph instances (including Protein Interaction, Wikipedia and Web networks). Experimental results demonstrate that our algorithms scale to large machine configurations (thousands of cores) and problem instances, enabling the alignment of networks of sizes two orders of magnitude larger than reported in the current literature.