Recently, the academic paper Approximating Single-Source Personalized PageRank with Absolute Error Guarantees by the team of Profs.Wei Zhewei, Profs.Wen Jirong and Yang Mingji from the Gaoling School of Artificial Intelligence, Renmin University of China (RUC), was accepted by the International Conference on Database Theory (ICDT) recommended by CCF.

This is the first time that faculty and students of RUC have published a paper in this international academic conference. ICDT is a well-known international conference focusing on theoretical research in data management, covering fundamental theoretical research in the areas of data management algorithms, data models and query languages, and data management systems.

Abstract:

Personalized PageRank (PPR) is a node proximity metric that has been widely studied and applied on graph data. For a pair of nodes s and t on a graph G=(V,E), the PPR value between them is defined as the probability that an α-decaying random walk(a random walk that terminates with probability α at each step) starting from s terminates at t. We have studied the classical single-source PPR query, i.e., to derive a PPR estimate from a given source node s to all nodes in the graph. Specifically, we aim to provide approximations with absolute error guarantees, which is to ensure that none of the absolute errors between the computed PPR estimates and the true values exceeds the error bound ε.

The existing results have been improved by the sublinear complexity. We have also studied the case when absolute error guarantees for degree normalization are required on an undirected graph, i.e., the absolute error between the PPR estimate and the true value for each node t is required to be no more than the error bound ε_d multiplied by the degree of the node t. Now we come up with an algorithm that provides such an error guarantee with high probability and whose expected complexity is asymptotically better than the previously known O(1/ε_d) complexity.