Fast Approximate All Pairwise CoSimRanks via Random Projection

Given a graph G with n nodes, and two nodes u, v∈ G, the CoSimRank value s(u, v) quantifies the similarity between u and v based on graph topology. Compared to SimRank, CoSimRank is shown to be more accurate and effective in many real-world applications including synonym expansion, lexicon extraction, and entity relatedness in knowledge graphs. The computation of all pairwise CoSimRanks in G is highly expensive and challenging. Existing solutions all focus on devising approximate algorithms for the computation of all pairwise CoSimRanks. To attain a desired absolute accuracy guarantee ϵ, the state-of-the-art approximate algorithm for computing all pairwise CoSimRanks requires O(n³log₂(ln(1/ϵ))) time, which is prohibitively expensive even ϵ is large. In this paper, we propose RPCS, a fast randomized algorithm for computing all pairwise CoSimRank values. The basic idea of RPCS is to approximate the n× n matrix multiplications in CoSimRank computation via random projection. Theoretically, RPCS runs in O(n²ln(n)/ϵ²ln(1/ϵ)) time and meanwhile ensures an absolute error of at most ϵ in each CoSimRank value in G with a high probability. Extensive experiments using six real graphs demonstrate that RPCS is more than up to orders of magnitude faster than the state of the art. In particular, on a million-edge Twitter graph, RPCS answers the ϵ -approximate (ϵ= 0.1 ) all pairwise CoSimRank query within 4 h, using a single commodity server, while existing solutions fail to terminate within a day.