Anti-differentiating approximation algorithms:A case study with min-cuts, spectral, and flow
David F. Gleich, Michael W. Mahoney · 2014
We formalize and illustrate the general concept of algorithmic anti-differentiation: given an algorith-mic procedure, e.g., an approximation algorithm for which worst-case approximation guarantees are available or a heuristic that has been engi-neered to be practically-useful but for which a pre-cise theoretical understanding is lacking, an algo-rithmic anti-derivative is a precise statement of an optimization problem that is exactly solved by that procedure. We explore this concept with a case study of approximation algorithms for finding locally-biased partitions in data graphs, demon-strating connections between min-cut objectives, a personalized version of the popular PageRank vector, and the highly effective “push ” procedure for computing an approximation to personalized PageRank. We show, for example, that this lat-ter algorithm solves (exactly, but implicitly) an `1-regularized `2-regression problem, a fact that helps to explain its excellent performance in prac-tice. We expect that, when available, these im-plicit optimization problems will be critical for rationalizing and predicting the performance of many approximation algorithms on realistic data. 1.