  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 $ \alpha $) and an extraneous amino-acid sequence
similarity score for two proteins (with weight $ 1 - \alpha $). In this short
paper, we make two contributions. First, we show that when IsoRank similarity
depends only on network structure ($\alpha = 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
($ \alpha = 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.
