We design and implement a distributed algorithm for balanced @math -way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and ( @math )-cut metric, by optimizing a novel objective called probabilistic fanout. This choice allows a simple local search heuristic to achieve comparable solution quality to the best existing hypergraph partitioners. Our algorithm is arbitrarily scalable due to a careful design that controls computational complexity, space complexity, and communication. In practice, we commonly process hypergraphs with billions of vertices and hyperedges in a few hours. We explain how the algorithm's scalability, both in terms of hypergraph size and bucket count, is limited only by the number of machines available. We perform an extensive comparison to existing distributed hypergraph partitioners and find that our approach is able to optimize hypergraphs roughly @math times bigger on the same set of machines. We call the resulting tool Social Hash Partitioner (SHP), and accompanying this paper, we open-source the most scalable version based on recursive bisection.
We stress that being of high theoretical importance, the above approximation algorithms are too slow to be used for large graphs, as they require solving linear programs. Hence, most of the existing methods for graph and hypergraph partitioning are heuristics based on a simple local search optimization @cite_3 . We follow the same direction and utilize a heuristic that can be implemented in an efficient way. It is unlikely that one can provide strong theoretical guarantees on a local search algorithm or improve existing bounds: Since fanout minimization is a generalization of minimum bisection, it would imply a breakthrough result.
@cite_3
2949888389
We survey recent trends in practical algorithms for balanced graph partitioning together with applications and future research directions.