The International Conference for High Performance Computing, Networking, Storage and Analysis
Distributed Algorithms for Aligning Massive Networks.
Student: Arif Khan (Purdue University)
Supervisor: Alex Pothen (Purdue University)
Abstract: Given two graphs, the network alignment (NA) problem is to find the best one-to-one mapping between the vertices of one graph to those in the other by maximizing the number of overlapped edges. NA is an important problem with several applications in bioinformatics, computer vision and ontology matchings. It is an NP-hard problem, and solutions are heuristic and iterative in nature. Our algorithm is based on belief propagation and approximate weighted matching. Memory intensive requirements necessitate a distributed-memory implementation to solve large problems. A combination of sparse matrix operations and combinatorial algorithms makes network alignment a challenging problem. Our implementation is based on a special runtime system, Graph Multi-Threaded (GMT), designed to address irregular computation and memory accesses on distributed architectures. We demonstrate the utility of this approach by solving large problems that were previously not possible on shared-memory systems, and show strong scaling with 10x improvement on 64 nodes.