Sig-SR: SimRank search over singular graphs

Weiren Yu, Julie A. McCann

Research output: Chapter in Book/Published conference outputConference publication


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, 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(2+Kr2)) time for K iterations. In contrast, the only known matrix-based algorithm that supports singular graphs [1] needs O(r4n2) time. The experimental results on real and synthetic datasets demonstrate the superiority of InvSR on singular graphs against its baselines.
Original languageEnglish
Title of host publicationSIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval
Place of PublicationNew York, NY (US)
Number of pages4
ISBN (Print)978-1-4503-2257-7
Publication statusPublished - 3 Jul 2014
Event37th international ACM SIGIR conference on Research & Development in Information Retrieval - Gold Coast, Queensland, Australia
Duration: 6 Jul 201411 Jul 2014


Conference37th international ACM SIGIR conference on Research & Development in Information Retrieval
Abbreviated titleSIGIR 2014
CityGold Coast, Queensland

Cite this