Fast incremental SimRank on link-evolving graphs

Weiren Yu, Xuemin Lin, Wenjie Zhang

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

Abstract

SimRank is an arresting measure of node-pair similarity based on hyperlinks. It iteratively follows the concept that 2 nodes are similar if they are referenced by similar nodes. Real graphs are often large, and links constantly evolve with small changes over time. This paper considers fast incremental computations of SimRank on link-evolving graphs. The prior approach [12] to this issue factorizes the graph via a singular value decomposition (SVD) first, and then incrementally maintains this factorization for link updates at the expense of exactness. Consequently, all node-pair similarities are estimated in O(r4n2) time on a graph of n nodes, where r is the target rank of the low-rank approximation, which is not negligibly small in practice. In this paper, we propose a novel fast incremental paradigm. (1) We characterize the SimRank update matrix ΔS, in response to every link update, via a rank-one Sylvester matrix equation. By virtue of this, we devise a fast incremental algorithm computing similarities of n2 node-pairs in O(Kn2) time for K iterations. (2) We also propose an effective pruning technique capturing the “affected areas” of ΔS to skip unnecessary computations, without loss of exactness. This can further accelerate the incremental SimRank computation to O(K(nd+|AFF|)) time, where d is the average in-degree of the old graph, and |AFF| (≤ n2) is the size of “affected areas” in ΔS, and in practice, |AFF| ≪ n2. Our empirical evaluations verify that our algorithm (a) outperforms the best known link-update algorithm [12], and (b) runs much faster than its batch counterpart when link updates are small.
Original languageEnglish
Title of host publication30th IEEE International Conference on Data Engineering (IEEE ICDE '14)
PublisherIEEE
Pages304-315
Number of pages12
ISBN (Electronic)978-1-4799-2555-1
DOIs
Publication statusPublished - 19 May 2014
Event2014 IEEE 30th International Conference on Data Engineering - Chicago, United States
Duration: 31 Mar 20144 Apr 2014

Publication series

Name2014 IEEE 30th International Conference on Data Engineering
PublisherIEEE
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Conference

Conference2014 IEEE 30th International Conference on Data Engineering
Abbreviated titleICDE 2014
CountryUnited States
CityChicago
Period31/03/144/04/14

Bibliographical note

This paper has received CiSRA Best Research Paper Award in 2014.

© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Fingerprint Dive into the research topics of 'Fast incremental SimRank on link-evolving graphs'. Together they form a unique fingerprint.

  • Cite this

    Yu, W., Lin, X., & Zhang, W. (2014). Fast incremental SimRank on link-evolving graphs. In 30th IEEE International Conference on Data Engineering (IEEE ICDE '14) (pp. 304-315). (2014 IEEE 30th International Conference on Data Engineering). IEEE. https://doi.org/10.1109/ICDE.2014.6816660