Model Reduction for Edge-Weighted Personalized PageRank

Seminar | February 21 | 4-5 p.m. | 306 Soda Hall

 David Bindel, Assistant Professor, Cornell University, Department of Computer Science

 Electrical Engineering and Computer Sciences (EECS)


In physical simulations, model reduction methods are often used to approximate the output of an expensive simulation by a much smaller and less expensive surrogate function. These methods are articularly appropriate in tasks such as control, optimization, and uncertainty quantification, where it is necessary to repeatedly evaluate the system behavior under varying inputs and parameter settings. In this talk, I describe work on adapting model reduction to a standard kernel for many data mining computations: fast computation of PageRank for graphs in which the edge weights depend on parameters. For an example learning-to-rank application, our approach is nearly five orders of magnitude faster than the standard approach. This speed improvement enables interactive computation of a class of ranking results that previously could only be computed offline. While our approach draws on ideas common in model reduction for large physical simulations, the cost and accuracy tradeoffs for the edge-weighted PageRank problem are different, as we will describe.

This is joint work with Wenlei Xie, Johannes Gehrke, and Al Demers.


David S. Bindel is an assistant professor of computer science at Cornell University. Before joining Cornell, he was a Courant Instructor of mathematics at NYU. He works broadly in scientific computing, with a particular focus on numerical linear algebra applied to a variety of problems from computer science and electrical engineering. He received B.S. degrees in mathematics and computer science from the University of Maryland and a Ph.D. in computer science from UC Berkeley. He is the recipient of the Householder Prize, the SIAG/LA prize, and a Sloan fellowship.