  Efficient computation of node proximity queries such as transition
probabilities, Personalized PageRank, and Katz are of fundamental importance in
various graph mining and learning tasks. In particular, several recent works
leverage fast node proximity computation to improve the scalability of Graph
Neural Networks (GNN). However, prior studies on proximity computation and GNN
feature propagation are on a case-by-case basis, with each paper focusing on a
particular proximity measure.
  In this paper, we propose Approximate Graph Propagation (AGP), a unified
randomized algorithm that computes various proximity queries and GNN feature
propagation, including transition probabilities, Personalized PageRank, heat
kernel PageRank, Katz, SGC, GDC, and APPNP. Our algorithm provides a
theoretical bounded error guarantee and runs in almost optimal time complexity.
We conduct an extensive experimental study to demonstrate AGP's effectiveness
in two concrete applications: local clustering with heat kernel PageRank and
node classification with GNNs. Most notably, we present an empirical study on a
billion-edge graph Papers100M, the largest publicly available GNN dataset so
far. The results show that AGP can significantly improve various existing GNN
models' scalability without sacrificing prediction accuracy.
