# Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner

arXiv: https://arxiv.org/abs/1707.06665 · HTML: https://mlsanity.com/paper/1707.06665/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2017.

## Built on by (most cited first, 7 of 7)

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Scalable Hypergraph Embedding System](https://mlsanity.com/paper/2103.09660/) (2021)
- [Community and hyperedge inference in multiple hypergraphs](https://mlsanity.com/paper/2505.04967/) (2025)
- [Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs](https://mlsanity.com/paper/2505.20972/) (2025)
- [A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient](https://mlsanity.com/paper/2509.22294/) (2025)
- [From Representation to Clusters: A Contrastive Learning Approach for Attributed Hypergraph Clustering](https://mlsanity.com/paper/2603.09370/) (2026)

## Abstract (arXiv)

We design and implement a distributed algorithm for balanced k-way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and (k-1)-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 100 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.