Given a graph G, a source node s and a target node t, the personalized PageRank (PPR) of t with respect to s is the probability that a random walk starting from s terminates at t, which reflects the importance of t with respect to s. Personalized PageRank has important applications in web search and social networks, e.g., in Twitter’s Who-To-Follow recommendation service. Similar to the global PageRank, PPR computation is immensely expensive, which usually requires hours on billion node graphs. However, unlike global PageRank, which requires only linear space to pre-store all PageRank scores, PPR has a score for each source-target pair, and requires quadratic space. This makes PPR resistant to indexing and poses challenges for PPR computations. Due to the high computational cost, most existing work focus on approximate PPR computation, which improves the query efficiency and provides rigorous guarantees on result quality. Nevertheless, even under approximation, the computational cost of approximate PPR is still immensely expensive. In this talk, I will present my recent work on efficient computation of approximate personalized PageRank. In particular, I will demonstrate our design of approximate query algorithms that can significantly reduce the computational cost of the queries, and illustrate how to design effective index structures to further improve the PPR query efficiency. Experimental results demonstrate that our proposed solutions improve over existing states-of-the-art by orders of magnitude without sacrificing the result quality.
Dr. Sibo Wang is currently a postdoctoral research fellow at DKE in University of Queensland, Australia. He obtained his PhD in 2016 from Nanyang Technological University, Singapore. His primary research interests lie in the area of database, particularly in the graph data management and data integration. Almost all of his research works are published in the most prestigious venues on data management like SIGMOD, PVLDB, and SIGKDD. He has been invited as the reviewer of DAPD 2017, TKDD 2015-2017, TKDE 2016-2017, SSTD 2015, DASFAA 2015, and external reviewer of SIGMOD 2015-2018, PVLDB 2015-2017, ICDE 2015-2017, SIGKDD 2015-2017.