  Given a graph $G$ with $n$ nodes and two nodes $u,v\in G$, the {\em
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
$\epsilon$, the state-of-the-art approximate algorithm for computing all
pairwise CoSimRanks requires $O(n^3\log_2(\ln(\frac{1}{\epsilon})))$ time,
which is prohibitively expensive even though $\epsilon$ is large. In this
paper, we propose \rsim, a fast randomized algorithm for computing all pairwise
CoSimRank values. The basic idea of \rsim is to approximate the $n\times n$
matrix multiplications in CoSimRank computation via random projection.
Theoretically, \rsim runs in
$O(\frac{n^2\ln(n)}{\epsilon^2}\ln(\frac{1}{\epsilon}))$ time and meanwhile
ensures an absolute error of at most $\epsilon$ in each CoSimRank value in $G$
with a high probability. Extensive experiments using six real graphs
demonstrate that \rsim is more than orders of magnitude faster than the state
of the art. In particular, on a million-edge Twitter graph, \rsim answers the
$\epsilon$-approximate ($\epsilon=0.1$) all pairwise CoSimRank query within 4
hours, using a single commodity server, while existing solutions fail to
terminate within a day.
