Share Email Print

Proceedings Paper

Projected power iteration for network alignment
Author(s): Efe Onaran; Soledad Villar
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The network alignment problem asks for the best correspondence between two given graphs, so that the largest possible number of edges are matched. This problem appears in many scientific problems (like the study of protein-protein interactions) and it is very closely related to the quadratic assignment problem which has graph isomorphism, traveling salesman and minimum bisection problems as particular cases. The graph matching problem is NP-hard in general. However, under some restrictive models for the graphs, algorithms can approximate the alignment efficiently. In that spirit the recent work by Feizi and collaborators introduce EigenAlign, a fast spectral method with convergence guarantees for Erdős-Renyí graphs. In this work we propose the algorithm Projected Power Alignment, which is a projected power iteration version of EigenAlign. We numerically show it improves the recovery rates of EigenAlign and we describe the theory that may be used to provide performance guarantees for Projected Power Alignment.

Paper Details

Date Published: 24 August 2017
PDF: 8 pages
Proc. SPIE 10394, Wavelets and Sparsity XVII, 103941C (24 August 2017); doi: 10.1117/12.2275366
Show Author Affiliations
Efe Onaran, New York Univ. (United States)
Soledad Villar, New York Univ. (United States)

Published in SPIE Proceedings Vol. 10394:
Wavelets and Sparsity XVII
Yue M. Lu; Dimitri Van De Ville; Manos Papadakis, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?