The Machine Learning Center at Georgia Tech invites you to a seminar by Vijay Subramanian from the University of Michigan.

TITLE

A Structural Result for Personalized PageRank and its Algorithmic Consequences

ABSTRACT

Many systems, such as the Internet, social networks, and the power grid, can be represented as graphs. When analyzing graphs, it is often useful to compute scores describing the relative importance or distance between nodes. One example is Personalized PageRank (PPR), which assigns to each node v a vector whose i-th entry describes the importance of the i-th node from the perspective of v. PPR has proven useful in many applications, such as recommending who users should follow on social networks (if this i-th entry is large, v may be interested in following the i-th user). Unfortunately, computing n PPR vectors exactly for a graph of n nodes has complexity O(n^3), which is infeasible for many graphs of interest.

In this work, we devise a scheme to estimate all n PPR vectors with bounded l1 error and complexity O(n^c), where c< 2 depends on the degrees of the graph at hand, the desired error tolerance, and a parameter that defines PPR. This improves upon existing methods, the best of which have complexity O(n^2 log n) in our setting. Our complexity guarantee holds with high probability, for certain choices of the PPR parameter, and for a certain class of random graphs (roughly speaking, the sparse directed configuration model with heavy-tailed in-degrees); our accuracy guarantee holds with probability 1 and for arbitrary graphs and PPR parameters. The complexity result arises as a consequence of our main (structural) result, which shows that the dimensionality of the set of PPR vectors scales sublinearly in n with high probability, for the same class of random graphs and for a notion of dimensionality similar to matrix rank. It is this coupling of the PPR vectors for the nodes on a common underlying graph that allows for estimating them faster. Hence, at a high level, our scheme is analogous to (but distinct from) low-rank matrix approximation. We also note that our scheme is similar to one that was proposed in Jeh and Widom (2003) but lacked accuracy and complexity guarantees, so another contribution of our paper is to address this gap in the literature.

This is joint work with Daniel Vial, Univ. of Michigan.

BIO

Vijay Subramanian is an Associate Professor in the EECS Department at the University of Michigan. His main research interests are in stochastic modeling, communications, information theory, and applied mathematics. A large portion of his past work has been on probabilistic analysis of communication networks, especially the analysis of scheduling and routing algorithms. In the past, he has also done some work with applications in immunology and coding of stochastic processes. His current research interests are on random graphs, game-theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.