Personalized PageRank to a Target Node, Revisited

Abstract

Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node $s$ and a target node $t$, the PPR value $\pi (s,t)$ represents the probability that a random walk from $s$ terminates at $t$, and thus indicates the bidirectional importance between $s$ and $t$. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node $s$ and every node $t\in V$. However, the single-source query only reflects the importance of each node $t$ with respect to $s$. In this paper, we consider the {\em single-target PPR query}, which measures the opposite direction of importance for PPR. Given a target node $t$, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node $t$. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets.

ACM SIGKDD 2020

References in corpus (8)

• Semi-Supervised Classification with Graph Convolutional Networks
• Link Prediction in Complex Networks: A Survey
• Representation Learning on Graphs with Jumping Knowledge Networks
• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Fast Distributed PageRank Computation
• PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs
• ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs
• Efficient SimRank Computation via Linearization

Cited by in corpus (11)

• Efficient Algorithms for Personalized PageRank Computation: A Survey
• Approximate Graph Propagation
• Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders
• Efficient and Effective Similarity Search over Bipartite Graphs
• Edge-based Local Push for Personalized PageRank
• Effective and Efficient PageRank-based Positioning for Graph Visualization
• BSAL: A Framework of Bi-component Structure and Attribute Learning for Link Prediction
• LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Revisiting Local Computation of PageRank: Simple and Optimal
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal