Message-Passing Algorithms for Sparse Network Alignment

摘要: 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.