cuAlign: Scalable Network Alignment on GPU Accelerators

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. We say that edges (𝑖, 𝑗) ∈ 𝐴 and (𝑖′, 𝑗′) ∈ 𝐵 are overlapped if 𝑖 is mapped to 𝑖′ and 𝑗 is mapped to 𝑗′. 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. However, a combination of combinatorial and algebraic kernels within the network alignment algorithm poses significant hurdles for parallelization. Further, load imbalance and irregular DRAM traffic limit achievable performance on GPUs. 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. We provide a scalable implementation targeting modern GPU accelerators. Our novel approach identifies and exploits unique structural properties of the BP-based algorithm and employs code fusion to reduce data movement between different steps of the algorithm. Using a diverse set of inputs, 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.