Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
cuAlign: Scalable Network Alignment on GPU Accelerators
DescriptionGiven 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.
Event Type
Workshop
TimeSunday, 12 November 20234:30pm - 5pm MST
Location702
Algorithms
Applications
Architecture and Networks
W