Co-Simrank is a useful Simrank-like measure
of similarity based on graph structure.
The existing method iteratively computes
each pair of Co-Simrank score from a dot
product of two Pagerank vectors, entailing
O(log(1/ǫ)n
3
) time to compute all pairs
of Co-Simranks in a graph with n nodes,
to attain a desired accuracy ǫ. In this study,
we devise a model, Co-Simmate, to speed
up the retrieval of all pairs of Co-Simranks
to O(log2
(log(1/ǫ))n
3
) time. Moreover,
we show the optimality of Co-Simmate
among other hop-(u
k
) variations, and integrate
it with a matrix decomposition based
method on singular graphs to attain higher
efficiency. The viable experiments verify
the superiority of Co-Simmate to others.