SimSky: An Accuracy-Aware Algorithm for Single-Source SimRank Search
Abstract
SimRank is a popular node-pair similarity search model based on graph topology. It has received sustained attention due to its wide range of applications in real-world scenarios. Considerable effort has been devoted to devising fast algorithms for SimRank computation through either iterative approaches or random walk based methods. In this paper, we propose an efficient accuracy-aware algorithm for computing single-source SimRank similarity. First, we devise an algorithm, ApproxDiag, to approximate the diagonal correction matrix. Next, we propose an efficient algorithm, named SimSky, which utilizes two Krylov subspaces for transforming high-dimensional single-source SimRank search into low-dimensional matrix-vector multiplications. Extensive experiments on various real datasets demonstrate the superior search quality of SimSky compared to other competitors.
Cite
Text
Yan and Yu. "SimSky: An Accuracy-Aware Algorithm for Single-Source SimRank Search." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023. doi:10.1007/978-3-031-43418-1_14Markdown
[Yan and Yu. "SimSky: An Accuracy-Aware Algorithm for Single-Source SimRank Search." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023.](https://mlanthology.org/ecmlpkdd/2023/yan2023ecmlpkdd-simsky/) doi:10.1007/978-3-031-43418-1_14BibTeX
@inproceedings{yan2023ecmlpkdd-simsky,
title = {{SimSky: An Accuracy-Aware Algorithm for Single-Source SimRank Search}},
author = {Yan, Liping and Yu, Weiren},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2023},
pages = {226-241},
doi = {10.1007/978-3-031-43418-1_14},
url = {https://mlanthology.org/ecmlpkdd/2023/yan2023ecmlpkdd-simsky/}
}