Message-Passing Algorithms for Sparse Network Alignment

• DOI: 10.1145/2435209.2435212
• Publication Date: 2013-03-19T13:34:23Z
• Authors: Mohsen Bayati; David F. Gleich; Amin Saberi; Ying Wang
• Keywords: 90C27; 0303 health sciences; 03 medical and health sciences; Optimization and Control (math.OC); FOS: Mathematics; Mathematics - Optimization and Control

Network alignment generalizes and unifies several approaches for forming a matching or between the vertices of two graphs. We study mathematical programming framework network problem sparse variation it where only small number matches graphs are possible. propose new message passing algorithm that allows us to compute, very efficiently, approximate solutions problems with graph sizes as large hundreds thousands vertices. also provide extensive simulations comparing our algorithms best solvers on synthetic problems, bioinformatics three ontology including multilingual known labeled alignment.