AdaPush: An Adaptive Push Framework for Graph-Propagation Based Node Similarity Computation

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 -