Triangular Alignment (TAME): A Tensor-based Approach for Higher-order Network Alignment

Abstract

Network alignment is an important tool with extensive applications in comparative interactomics. Traditional approaches to alignment of biomolecular networks aim to maximize edge conservation (as a measure of topological similarity), as well as prior information on the underlying similarity of aligned entities (e.g., known similarity of nodes). 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 not scalable to real-world networks. 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 different classes of biological networks -- however, our formulation and resulting algorithms can be applied to general motifs. Using a case study on the synthetic 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.

Keywords:

Network alignment, SS_HOPM, Tensor, Z-eigenpair, optimization


Supplementary Materials

  1. Yeast and Human PPI networks PDF
  2. Sequence similarity of gene transcripts between yeast and human PDF