Network alignment is an important tool with extensive applications in comparative interactomics. Traditional approaches aim to simultaneously maximize the number of conserved edges and the underlying similarity of aligned entities. We propose a novel formulation of the network alignment problem that extends topological similarity to higher-order structures and provide a new objective function that maximizes the number of aligned substructures. This objective function corresponds to an integer programming problem, which is NP-hard. Consequently, we approximate this objective function as a surrogate function whose maximization results in a tensor eigenvalue problem. Based on this formulation, we present an algorithm called Triangular AlignMEnt (TAME), which attempts to maximize the number of aligned triangles across networks. We focus on alignment of triangles because of their enrichment in complex networks; however, our formulation and resulting algorithms can be applied to general motifs. Using a case study on the NAPABench dataset, we show that TAME is capable of producing alignments with up to 99% accuracy in terms of aligned nodes. We further evaluate our method by aligning yeast and human interactomes. Our results indicate that TAME outperforms the state-of-art alignment methods both in terms of biological and topological quality of the alignments.
@article{MoGlKoGr17,
author = {Shahin Mohammadi and David F. Gleich and Tamara G. Kolda and Ananth Grama},
title = {Triangular Alignment ({TAME}): {A} Tensor-based Approach for Higher-order Network Alignment},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
volume = {14},
number = {6},
pages = {1446-1458},
month = {December},
year = {2017},
doi = {10.1109/tcbb.2016.2595583},
eprint = {1510.06482},
}