Massively Parallel Single-Source SimRanks in O(log N) Rounds

Siqiang Luo, Zulun Zhu, Lixiang Li, Wenqian Dong, Jiahui Qu

Abstract

SimRank is a fundamental measure for node similarity in graphs, but its recursive definition poses significant computational challenges for large-scale datasets. In the Massively Parallel Computation (MPC) model, existing algorithms suffer from a "round complexity barrier," requiring $\Omega(\log n)$ rounds. This paper presents the first distributed algorithm to break this barrier, achieving $O(\log^2 \log n)$ rounds for single-source SimRank. By leveraging parallel random walk generation and a novel distributed meeting detection mechanism, the proposed method maintains high accuracy and sub-linear space complexity per machine.

Introduction

In graph analysis, SimRank is based on the intuition that two nodes are similar if they are referenced by similar nodes. While powerful for recommendation engines and link prediction, calculating SimRank for a source node against every other node in a graph of $n$ nodes is incredibly expensive. To handle modern web-scale graphs, researchers use the Massive Parallel Computation (MPC) model. However, existing distributed SimRank algorithms face a "round complexity barrier," typically requiring at least $\Omega(\log n)$ communication rounds to converge. This paper addresses whether approximate SimRank can be computed in "sub-logarithmic" rounds while keeping the memory footprint of each machine sub-linear.

Methodology

The authors move away from the traditional iterative approach and instead leverage the relationship between SimRank and random walks. SimRank can be estimated by the probability that two random walks starting from different nodes will eventually "meet." The paper introduces three key innovations:

  1. Parallel Random Walk Generation: Using a Weighted Random Walk technique (WRME), the algorithm generates thousands of independent walks in $O(\log^2 \log n + \log^2 l)$ rounds, bypassing the sequential bottleneck.
  2. Geometric Length Regularization: Walks are generated with lengths following a geometric distribution to match the SimRank decay factor ($\sqrt{c}$), ensuring error remains negligible.
  3. Distributed Meeting Detection: To find if two walks "met" without moving all data to one machine, the authors decompose walks into tuples and use a distributed sorting procedure. This allows machines to efficiently link walks from the source node $u$ to walks from any other node $v$ in constant rounds.
Figure 1: Distributed meeting detection via tuple decomposition and matching.

Theoretical Results and Comparison

The algorithm achieves a round complexity of $O(\log^2 \log n)$. For a graph with a billion nodes, this reduces the rounds from approximately 30 to 5. As shown in the comparison table below, the proposed method is the first to achieve sub-logarithmic rounds while maintaining provable accuracy and sub-linear space per machine.

Figure 2: Comparison of the proposed algorithm against existing distributed SimRank methods.

The algorithm is guaranteed to produce SimRank values with at most $\epsilon$ absolute error for any $\epsilon > 3/n$, making the approximation robust for real-world use. Each machine only needs $O(n^\alpha)$ space, and the total space across the cluster is nearly linear, $O(\tilde{m} + n)$.

Conclusion

This work breaks the long-standing round complexity barrier for distributed SimRank computation. By treating walk generation as a parallel sampling problem, the authors provide a theoretically superior framework for large-scale graph analysis. Future work may focus on optimizing constant factors for practical implementations on systems like Apache Flink.

Summary updated

BibTeX
@inproceedings{luo2024massively,
  author = {Siqiang Luo and Zulun Zhu and Lixiang Li and Wenqian Dong and Jiahui Qu},
  title = {{Massively Parallel Single-Source SimRanks in O(log N) Rounds}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=PDcsBXTrHC},
}
Figure