Grigory Yaroslavtsev (Indiana University, Bloomington)
Badger Rampage: Multi-dimensional Balanced Partitioning of
Facebook-scale Graphs

I will describe Badger Rampage, a simple general framework for
designing practical algorithms for d-dimensional balanced partitioning
of graphs with several billions of vertices and up to 10^12
edges. Badger Rampage is based on applying noisy projected gradient
descent to a non-convex relaxation of the problem. For an
appropriately chosen relaxation, the gradient descent step can be
implemented simply as local averaging of the neighboring values. The
technical core of our work is optimizing the computationally expensive
projection step for which we give an algorithm with complexity O(|V|
log^d |V|) for d <= 2. Experiments on Apache Giraph using subsets of
the Facebook graph show comparable or superior performance against
existing literature on one-dimensional graph partitioning with the
added benefits of simplicity and generalizability to the
multi-dimensional case. Analysis of convergence properties of Badger
Rampage is left as an open problem.

Joint work with Dmitrii Avdiukhin (Indiana University) and Sergey
Pupyrev (Facebook).