TY - JOUR
T1 - AdaPush
T2 - An Adaptive Push Framework for Graph-Propagation Based Node Similarity Computation
AU - Yang, Yichun
AU - Li, Rong Hua
AU - Liao, Meihao
AU - Wang, Guoren
N1 - Publisher Copyright:
© 1989-2012 IEEE.
PY - 2026/7/1
Y1 - 2026/7/1
N2 - 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 π has a small L1-norm (e.g., personalized PageRank and heat kernel PageRank). However, we find that when π 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 ||π||1}, thus they are efficient even when ||π|| 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.
AB - 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 π has a small L1-norm (e.g., personalized PageRank and heat kernel PageRank). However, we find that when π 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 ||π||1}, thus they are efficient even when ||π|| 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.
KW - Graph propagation
KW - katz centrality
UR - https://www.scopus.com/pages/publications/105035415636
U2 - 10.1109/TKDE.2026.3681914
DO - 10.1109/TKDE.2026.3681914
M3 - Article
AN - SCOPUS:105035415636
SN - 1041-4347
VL - 38
SP - 4093
EP - 4106
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 7
ER -