Sig-SR: SimRank search over singular graphs

Weiren Yu, Julie A. McCann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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)
PublisherACM
Pages859-862
Number of pages4
ISBN (Print)978-1-4503-2257-7
DOIs
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

Conference

Conference37th international ACM SIGIR conference on Research & Development in Information Retrieval
Abbreviated titleSIGIR 2014
CountryAustralia
CityGold Coast, Queensland
Period6/07/1411/07/14

Cite this

Yu, W., & McCann, J. A. (2014). Sig-SR: SimRank search over singular graphs. In SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval (pp. 859-862). ACM. https://doi.org/10.1145/2600428.2609459