Efficient Personalized PageRank Estimation for Many Sources and Many Targets

Personalized PageRank (PPR) is a measure of the importance of a node in a graph from the perspective of another node (we call these nodes the target and the source, respectively). PPR has been used in many applications, such as offering a Twitter user (the source) personalized recommendations of who to follow (targets deemed important by PPR). Computing PPR at scale is infeasible for networks like Twitter, so many estimation algorithms have been proposed. Here we explore two methods for estimating PPR of many source/target pairs. The bulk of the talk will be on extending the state-of-the-art PPR estimator for a single source/target pair to the cases of many sources and/or many targets by eliminating repeated computations that may occur when using existing algorithms separately for each source or each target. Time permitting, we will discuss our second method that considers computation of PPR vectors from all unknown nodes when the PPR for a set of nodes, called the known set, are given. This will provide theoretical backing for a commonly used heuristic algorithm. Note that if the known set is small, then the computation of all the PPR vectors becomes an easier task. At a high level, both approaches can be viewed as dimensionality reduction methods in which quantities used to compute PPR are shared among sources and/or targets by exploiting certain graph characteristics. Moving forward, we aim to develop a deeper understanding of how PPR vectors — a high-dimensional set of objects — are related. This may in turn help us understand how information is organized in modern networks.

This is joint work with Daniel Vial a Ph.D. candidate in ECE at the University of Michigan.

I am an Associate Professor in the EECS department at the University of Michigan. After graduating I worked in the research arm of the Networks Business Sector of Motorola in Arlington Heights, Illinois, USA until May 2006. In May 2006 I returned to an academic setting. I started with a move to the Hamilton Institute of the National University of Ireland, Maynooth as a Research Fellow. In the summer of 2010 I was a visiting researcher at LIDS MIT. From November 2010 to October 2011, I was a Senior Research Associate in the EECS Department at Northwestern University. From November 2011 until August 2014 I was a Research Assistant Professor in the EECS Department at Northwestern University.