Network Alignment by Propagating Reliable Similarities

Zirou Qiu, Clemson University
Ruslan Shaydulin, Clemson University
Xiaoyuan Liu, Clemson University
Yuri Alexeev, Argonne National Laboratory
Christopher S. Henry, Argonne National Laboratory
Ilya Safro, Clemson University


Networks model a variety of complex phenomena across different domains. In many applications, one of the central questions is how to align two or more networks to infer the similarities between nodes and discover potential correspondence. In this paper, we propose a network alignment algorithm that relies exclusively on the underlying graph structure. Under the guidance of rules which we defined, we compute the similarity between a pair of cross-network vertices iteratively based on their neighborhood. The resulting cross-network similarity matrix is then used to infer a permutation matrix which encodes the alignment. We improve the performance of a commonly used post-processing step (local search) by introducing a novel selection rule based on the levels of mismatching of vertices. Through extensive numerical experiments, we show that our alignment algorithm outperforms the state-of-the-art alignment methods in terms of alignment accuracy at the cost of an extra logarithmic factor.