In this talk, I will describe work on model reduction for 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.