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
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). New York, NY (US): ACM.
Yu, Weiren ; McCann, Julie A. / Sig-SR: SimRank search over singular graphs. SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. New York, NY (US) : ACM, 2014. pp. 859-862
@inproceedings{b776c4d6437a406492ed10c7b2c1ecae,
title = "Sig-SR: SimRank search over singular graphs",
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.",
author = "Weiren Yu and McCann, {Julie A.}",
year = "2014",
month = "7",
day = "3",
language = "English",
pages = "859--862",
booktitle = "SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval",
publisher = "ACM",
address = "United States",

}

Yu, W & McCann, JA 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. ACM, New York, NY (US), pp. 859-862, 37th international ACM SIGIR conference on Research & Development in Information Retrieval, Gold Coast, Queensland, Australia, 6/07/14.

Sig-SR: SimRank search over singular graphs. / Yu, Weiren; McCann, Julie A.

SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. New York, NY (US) : ACM, 2014. p. 859-862.

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

TY - GEN

T1 - Sig-SR: SimRank search over singular graphs

AU - Yu, Weiren

AU - McCann, Julie A.

PY - 2014/7/3

Y1 - 2014/7/3

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 859

EP - 862

BT - SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

PB - ACM

CY - New York, NY (US)

ER -

Yu W, McCann JA. Sig-SR: SimRank search over singular graphs. In SIGIR '14 Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval. New York, NY (US): ACM. 2014. p. 859-862