# On the Structure and Efficient Computation of IsoRank Node Similarities

arXiv: https://arxiv.org/abs/1602.00668 · HTML: https://mlsanity.com/paper/1602.00668/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2016.

## Built on by (most cited first, 3 of 3)

- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)

## Abstract (arXiv)

The alignment of protein-protein interaction (PPI) networks has many applications, such as the detection of conserved biological network motifs, the prediction of protein interactions, and the reconstruction of phylogenetic trees [1, 2, 3]. IsoRank is one of the first global network alignment algorithms [4, 5, 6], where the goal is to match all (or most) of the nodes of two PPI networks. The IsoRank algorithm first computes a pairwise node similarity metric, and then generates a matching between the two node sets based on this metric. The metric is a convex combination of a structural similarity score (with weight  α ) and an extraneous amino-acid sequence similarity score for two proteins (with weight  1 - α ). In this short paper, we make two contributions. First, we show that when IsoRank similarity depends only on network structure (α = 1), the similarity of two nodes is only a function of their degrees. In other words, IsoRank similarity is invariant to any network rewiring that does not affect the node degrees. This result suggests a reason for the poor performance of IsoRank in structure-only ( α = 1 ) alignment. Second, using ideas from [7, 8], we develop an approximation algorithm that outperforms IsoRank (including recent versions with better scaling, e.g., [9]) by several orders of magnitude in time and memory complexity, despite only a negligible loss in precision.