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.

Publication DOI: https://doi.org/10.1145/2600428.2609459
Divisions: College of Engineering & Physical Sciences
Event Title: 37th international ACM SIGIR conference on Research & Development in Information Retrieval
Event Type: Other
Event Dates: 2014-07-06 - 2014-07-11
ISBN: 978-1-4503-2257-7
Last Modified: 08 Jan 2024 09:52
Date Deposited: 24 Jan 2017 14:40
Full Text Link:
Related URLs: https://dl.acm. ... 2600428.2609459 (Publisher URL)
PURE Output Type: Conference contribution
Published Date: 2014-07-03
Authors: Yu, Weiren (ORCID Profile 0000-0002-1082-9475)
McCann, Julie A.

Download

[img]

Version: Accepted Version


Export / Share Citation


Statistics

Additional statistics for this record