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.

Highlights - Most important sentences from the article

Related Articles

2018-01-23
1801.07386 | cs.SI

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

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

Highlights - Most important sentences from the article

2018-08-16
1808.05689 | cs.LG

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

Highlights - Most important sentences from the article

2018-11-27
1811.10797 | cs.LG

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

Highlights - Most important sentences from the article

2018-04-25
1804.09820 | cs.SI

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

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

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

Highlights - Most important sentences from the article

2019-03-22
1903.09689 | cs.SY

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

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

Highlights - Most important sentences from the article

2019-04-09
1904.04583 | cs.SI

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

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

Highlights - Most important sentences from the article

2018-10-31
1811.12162 | cs.SI

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

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

Highlights - Most important sentences from the article

2019-03-14
1903.05956 | cs.DC

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

Highlights - Most important sentences from the article

2018-09-21
1809.08198 | cs.SI

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

Highlights - Most important sentences from the article

2018-09-02
1809.00320 | cs.SI

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

Highlights - Most important sentences from the article