The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Workshop: IA^3 2023 - 13th Workshop on Irregular Applications: Architectures & Algorithms
Authors: Lizhi Xiang (University of Utah), Arif Khan (Meta), S. M. Ferdous (Pacific Northwest National Laboratory (PNNL)), SR Aravind (Meta), and Mahantesh Halappanavar (Pacific Northwest National Laboratory (PNNL))
Abstract: Given two graphs, the objective of network alignment is to find a one-to-one mapping of vertices in one graph to vertices in the other, such that the number of overlaps is maximized. Network alignment is an important optimization problem with several applications in bioinformatics, computer vision and ontology matching. Since it is an NP-hard problem, efficient heuristics and scalable implementations are necessary. In this work, we introduce a novel framework (cuAlign) that combines intra-network proximity using node (vertex) embedding, sparsification for computational efficiency, and belief propagation (BP) and approximate weighted matching for alignment. We demonstrate qualitative improvements up to 22% over state-of-the-art approaches and provide a scalable implementation targeting modern GPU accelerators. We demonstrate up to 19× speedup for belief propagation, 3× speedup for approximate weighted matching, and 15× total, relative to a state-of-the-art multi-threaded implementation. We believe that our work will enable algorithmic improvements and applications of network alignment.