This Iowa State Department Seminar is an online seminar only
Title: A Structural Result for Personalized PageRank and its Algorithmic Consequence
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.
Joint work with Daniel Vial, University of Texas, Austin and University of Illinois at Urbana-Champaign.
Bio: Vijay Subramanian received the Ph.D. degree in electrical engineering from the University of Illinois at Urbana-Champaign, Champaign, IL, USA, in 1999. He worked at Motorola Inc., at the Hamilton Institute, Maynooth, Ireland, for many years, and also in the EECS Department, Northwestern University, Evanston, IL, USA. In Fall 2014, he started in his current position as an Associate Professor with the EECS Department at the University of Michigan, Ann Arbor. For the academic year 2022-2023, he’s visiting UIUC hosted graciously by CSL and also the ECE department. His research interests are in stochastic analysis, random graphs, multi-agent systems, and game theory (mechanism and information design) with applications to social, economic and technological networks.
Please click this URL to start or join. https://iastate.zoom.us/j/96810972944?pwd=SVVLWlY2cVdZYXhxWWg4ZHF1cVdSZz09
Or, go to https://iastate.zoom.us/join and enter meeting ID: 968 1097 2944 and password: 334840
Join from dial-in phone line:
Dial: +1 309 205 3325 or +1 312 626 6799
Meeting ID: 968 1097 2944
Participant ID: Shown after joining the meeting
International numbers available: https://iastate.zoom.us/u/aqUgrVklM