.png){kind=icon}
.png){kind=icon}
Return
AdaPush: An Adaptive Push Framework for Graph-Propagation Based Node Similarity Computation
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2026.3681914.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Computing graph-propagation based node similarities is a fundamental operator in many graph mining and graph learning tasks. The state-of-the-art approach to compute the graph-propagation based similarity is based on a push-style iterative framework. The push framework is very efficient when the resulting node similarity vector $\bm {\pi }$ has a small $L1$-norm (e.g., personalized PageRank and heat kernel PageRank). However, we find that when $\bm {\pi }$ has a large $L1$-norm (e.g., Katz scores and exponential communicability), such a framework is inefficient. To overcome this issue, we propose a novel framework, called AdaPush, which is more efficient and flexible than the state-of-the-art (SOTA) framework. Based on the AdaPushframework, we develop two new algorithms with two different carefully-designed randomized acceleration techniques, respectively. We prove that both of our new algorithms can achieve a relative-error guarantee. Additionally, a striking feature of our algorithms is that their time complexity is insensitive to $\Vert \pi \Vert _{1}$, thus they are efficient even when $\Vert \pi \Vert _{1}$ is large. Extensive experiments on 5 large real-life datasets demonstrate that our algorithms substantially outperform the SOTA algorithms for computing Katz score and exponential communicability in terms of both running time and estimation accuracy.
Keywords:
Graph propagation
katz centrality
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W