Conferences >2009 Ninth IEEE International...

Algorithms for Large, Sparse Network Alignment Problems

Abstract:

We propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for this NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.

Published in: 2009 Ninth IEEE International Conference on Data Mining

Date of Conference: 06-09 December 2009

Date Added to IEEE Xplore: 28 December 2009

ISBN Information:

ISSN Information:

DOI: 10.1109/ICDM.2009.135

Conference Location: Miami Beach, FL, USA

I. Introduction

The focus of the network alignment problem is to find approximate isomorphisms, or alignments, between similar graphs. It is widely applied to problems in bioinformatics [1], [2], database schema matching [3], ontology matching [4], and computer vision [5], [6] (where it is also known as the weighted graph matching problem). Recent algorithms solve this problem approximately for graphs with around 10,000 vertices, however there are few comparisons among them. We propose a new algorithm based on belief propagation, survey and compare existing algorithms on real and synthetic data, and investigate a problem with over 200,000 vertices.

References is not available for this document.