Fast Approximate All Pairwise CoSimRanks via Random Projection

Renchi Yang*, Xiaokui Xiao

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

Abstract

Given a graph G with n nodes, and two nodes u, v∈ G, the CoSimRank value s(u, v) quantifies the similarity between u and v based on graph topology. Compared to SimRank, CoSimRank is shown to be more accurate and effective in many real-world applications including synonym expansion, lexicon extraction, and entity relatedness in knowledge graphs. The computation of all pairwise CoSimRanks in G is highly expensive and challenging. Existing solutions all focus on devising approximate algorithms for the computation of all pairwise CoSimRanks. To attain a desired absolute accuracy guarantee ϵ, the state-of-the-art approximate algorithm for computing all pairwise CoSimRanks requires O(n3log2(ln(1/ϵ))) time, which is prohibitively expensive even ϵ is large. In this paper, we propose RPCS, a fast randomized algorithm for computing all pairwise CoSimRank values. The basic idea of RPCS is to approximate the n× n matrix multiplications in CoSimRank computation via random projection. Theoretically, RPCS runs in O(n2ln(n)/ϵ2ln(1/ϵ)) time and meanwhile ensures an absolute error of at most ϵ in each CoSimRank value in G with a high probability. Extensive experiments using six real graphs demonstrate that RPCS is more than up to orders of magnitude faster than the state of the art. In particular, on a million-edge Twitter graph, RPCS answers the ϵ -approximate (ϵ= 0.1 ) all pairwise CoSimRank query within 4 h, using a single commodity server, while existing solutions fail to terminate within a day.

Original languageEnglish
Title of host publicationWeb Information Systems Engineering – WISE 2021
Subtitle of host publication22nd International Conference on Web Information Systems Engineering, WISE 2021, Melbourne, VIC, Australia, October 26–29, 2021, Proceedings, Part I
EditorsWenjie Zhang, Lei Zou, Zakaria Maamar, Lu Chen
PublisherSpringer Cham
Pages438-452
Number of pages15
Edition1st
ISBN (Electronic)9783030908881
ISBN (Print)9783030908874
DOIs
Publication statusPublished - 2 Dec 2021
Event22nd International Conference on Web Information Systems Engineering, WISE 2021 - Melbourne, Australia
Duration: 26 Oct 202129 Oct 2021
https://link.springer.com/book/10.1007/978-3-030-90888-1

Publication series

NameLecture Notes in Computer Science
Volume13080
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameInformation Systems and Applications, incl. Internet/Web, and HCI
NameWISE: International Conference on Web Information Systems Engineering

Conference

Conference22nd International Conference on Web Information Systems Engineering, WISE 2021
Country/TerritoryAustralia
CityMelbourne
Period26/10/2129/10/21
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Approximate algorithm
  • CoSimRank
  • Random projection

Fingerprint

Dive into the research topics of 'Fast Approximate All Pairwise CoSimRanks via Random Projection'. Together they form a unique fingerprint.

Cite this