SimRank is an attractive structural-context measure of similarity
between two objects in a graph. It recursively follows
the intuition that “two objects are similar if they are referenced
by similar objects”. The best known matrix-based
method [1] for calculating SimRank, however, implies an
assumption that the graph is non-singular, i.e., its adjacency
matrix is invertible. In reality, non-singular graphs are very
rare; such an assumption in [1] is too restrictive in practice.
In this paper, we provide a treatment of [1], by supporting
similarity assessment on non-invertible adjacency matrices.
Assume that a singular graph G has n nodes, with r (< n)
being the rank of its adjacency matrix. (1) We show that
SimRank matrix S on G has an elegant structure: S can be
represented as a rank r matrix plus a scaled identity matrix.
(2) By virtue of this, an efficient algorithm over singular
graphs, Sig-SR, is proposed for calculating all-pairs SimRank
in O(r(n
2 + Kr2
)) time for K iterations. In contrast, the
only known matrix-based algorithm that supports singular
graphs [2] needs O(r
4n
2
) time. The experimental results on
real and synthetic datasets demonstrate the superiority of
Sig-SR on singular graphs against its baselines.