ML p(r)ior | On the Structure and Efficient Computation of IsoRank Node Similarities

On the Structure and Efficient Computation of IsoRank Node Similarities

2016-02-01
1602.00668 | q-bio.MN
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.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-01-23

Digital presence in the world of online social media entails significant privacy risks. In this work… show more
PDF

Highlights - Most important sentences from the article

2018-05-03
1805.01209 | cs.SI

A typical way in which network data is recorded is to measure all the interactions among a specified… show more
PDF

Highlights - Most important sentences from the article

2018-08-16

Graph similarity search is among the most important graph-based applications, e.g. finding the chemi… show more
PDF

Highlights - Most important sentences from the article

2018-11-27

Node embedding is the task of extracting informative and descriptive features over the nodes of a gr… show more
PDF

Highlights - Most important sentences from the article

2018-04-25

We derive and analyse a new iterative algorithm for detecting network core--periphery structure. Usi… show more
PDF

Highlights - Most important sentences from the article

2019-01-10
1901.03425 | cs.SI

Studying networks to predict the emerging interactions is a common research problem for both fields … show more
PDF

Highlights - Most important sentences from the article

2018-04-26
1804.10029 | q-bio.MN

Protein-protein interaction (PPI) network alignment is a canonical operation to transfer biological … show more
PDF

Highlights - Most important sentences from the article

2019-03-22

Measures of node centrality that describe the importance of a node within a network are crucial for … show more
PDF

Highlights - Most important sentences from the article

2019-05-15
1905.06457 | cs.SI

Comparative graph and network analysis play an important role in both systems biology and pattern re… show more
PDF

Highlights - Most important sentences from the article

2019-04-09

Mining community structures from the complex network is an important problem across a variety of fie… show more
PDF

Highlights - Most important sentences from the article

2018-10-23
1810.10866 | cs.LG

We introduce GSimCNN (Graph Similarity Computation via Convolutional Neural Networks) for predicting… show more
PDF

Highlights - Most important sentences from the article

2018-10-31

Community detection is, at its core, an attempt to attach an interpretable function to an otherwise … show more
PDF

Highlights - Most important sentences from the article

2019-02-28
1902.11105 | quant-ph

Large scale complex systems, such as social networks, electrical power grid, database structure, con… show more
PDF

Highlights - Most important sentences from the article

2019-03-14

We design fast deterministic algorithms for distance computation in the congested clique model. Our … show more
PDF

Highlights - Most important sentences from the article

2018-09-21

Multiple network alignment is the problem of identifying similar and related regions in a given set … show more
PDF

Highlights - Most important sentences from the article

2018-09-02

In this paper, we consider the problem of approximately aligning/matching two graphs. Given two grap… show more
PDF

Highlights - Most important sentences from the article