In November 2023, one paper titled “Approximating Single-Source Personalized PageRank with Absolute Error Guarantees” was accepted byInternational Conference on Database Theory (ICDT).The authors of this paper are Prof. Zhewei Wei, Prof. Ji-Rong Wen, and doctoral student Mingji Yang, all from Renmin University of China. The upcoming ICDT conference is scheduled to be held from March 25 to March 28, 2024, in Paestum, Italy.

ICDT is an established and prestigious series of international conferences on research in the foundations and theory of data management. This is the first paper accepted by ICDT from Renmin University of China.

Paper Introduction

Paper Title: Approximating Single-Source Personalized PageRank with Absolute Error Guarantees

Authors: Zhewei Wei, Ji-Rong Wen, Mingji Yang

(Equal contribution, the authors areordered alphabetically by the first letter of their last names, following the convention of theoretical computer science)

Corresponding Author: Zhewei Wei

Paper Overview: Personalized PageRank (PPR) is an extensively studied and applied node proximity measure on graphs. For a pair of nodes s and t on a graph G='(V,E), the PPR value of t with respect to s is defined as the probability that an α-discounted random walk from s terminates at t, where the walk terminates with probability α at each step. We study the classic Single-Source PPR query, which asks for PPR approximations from a given source node s to all nodes in the graph. Specifically, we aim to provide approximations with absolute error guarantees, ensuring that each of the resultant PPR estimates differs from the true value by at most ε. We propose an algorithm that achieves this with high probability, which achieves the following expected running time on a graph with n nodes and m edges:

-soft-O(m^{1/2}/ε)for directed graphs, wheresoft-O is the big-O notation ignoring polylog(n)factors;

-soft-O(d_{max}^{1/2}/ε) for undirected graphs,where d_{max}is the maximum node degree of the graph;

-soft-O(n^{γ−1/2}/ε)for power-law graphs, whereγ∈(1/2,1) is the extent of the power law.

These sublinear bounds improve upon existing results. We also study the case when degree-normalized absolute error guarantees are desired on undirected graphs, requiring that the resultant PPR estimatesfor each node t differ from the true value by at most ε_d times the degree of node t. We give an algorithm that provides this error guarantee with high probability, achieving an expected complexity that improves over the previously known O(1/ε_d) complexity.

Paper Link: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.9

ArXiv Link: https://arxiv.org/abs/2401.01019