I-CoSim: Efficient Dynamic CoSimRank Retrieval on Evolving Networks
Xiaoyu Xu, Weiren Yu · 2024
CoSimRank, a favorable measure for assessing node similarity based on graphs, faces computational challenges on real evolving graphs. The best-of-breed algorithm, D-CoSim, for incremental CoSimRank search evaluates similarity changes by summing dot products between two vectors. These vectors are iteratively generated from scratch in the original high-dimensional space, leading to significant costs. In this paper, we propose I-CoSim, a novel efficient dynamic CoSimRank algorithm for evolving graphs. I-CoSim resorts to two low-dimensional Krylov subspaces and maximally reuses previously computed similarities in the original graph, which substantially expedites CoSimRank search on evolving graphs. We also theoretically provide an error bound on the I-CoSim estimation with guaranteed accuracy. Experimental results on real datasets show that I-CoSim is up to 28 times faster than the best-known competitor, with only a slight compromise in accuracy.