# More Recent Advances in (Hyper)Graph Partitioning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 235 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 30 of 48)

- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [High-Quality Hypergraph Partitioning](https://mlsanity.com/paper/2106.08696/) (2021)
- [k-way Hypergraph Partitioning via n-Level Recursive Bisection](https://mlsanity.com/paper/1511.03137/) (2015)
- [Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner](https://mlsanity.com/paper/1707.06665/) (2017)
- [ADWISE: Adaptive Window-based Streaming Edge Partitioning for High-Speed Graph Processing](https://mlsanity.com/paper/1712.08367/) (2017)
- [Scalable Edge Partitioning](https://mlsanity.com/paper/1808.06411/) (2018)
- [Spinner: Scalable Graph Partitioning in the Cloud](https://mlsanity.com/paper/1404.3861/) (2014)
- [Graph Bisection with Pareto-Optimization](https://mlsanity.com/paper/1504.03812/) (2015)
- [Memetic Multilevel Hypergraph Partitioning](https://mlsanity.com/paper/1710.01968/) (2017)
- [Window-based Streaming Graph Partitioning Algorithm](https://mlsanity.com/paper/1902.01543/) (2019)
- [Parallel Graph Partitioning for Complex Networks](https://mlsanity.com/paper/1404.4797/) (2014)
- [Distributed Balanced Partitioning via Linear Embedding](https://mlsanity.com/paper/1512.02727/) (2015)
- [Partitioning Trillion-edge Graphs in Minutes](https://mlsanity.com/paper/1610.07220/) (2016)
- [High-Quality Shared-Memory Graph Partitioning](https://mlsanity.com/paper/1710.08231/) (2017)
- [Network Flow-Based Refinement for Multilevel Hypergraph Partitioning](https://mlsanity.com/paper/1802.03587/) (2018)
- [Advanced Flow-Based Multilevel Hypergraph Partitioning](https://mlsanity.com/paper/2003.12110/) (2020)
- [Prioritized Restreaming Algorithms for Balanced Graph Partitioning](https://mlsanity.com/paper/2007.03131/) (2020)
- [Deep Multilevel Graph Partitioning](https://mlsanity.com/paper/2105.02022/) (2021)
- [Tree-based Coarsening and Partitioning of Complex Networks](https://mlsanity.com/paper/1402.2782/) (2014)
- [Partitioning Complex Networks via Size-constrained Clustering](https://mlsanity.com/paper/1402.3281/) (2014)
- [Algorithms for Mapping Parallel Processes onto Grid and Torus Architectures](https://mlsanity.com/paper/1411.0921/) (2014)
- [Graph Partitioning for Independent Sets](https://mlsanity.com/paper/1502.01687/) (2015)
- [Better Process Mapping and Sparse Quadratic Assignment](https://mlsanity.com/paper/1702.04164/) (2017)
- [ILP-based Local Search for Graph Partitioning](https://mlsanity.com/paper/1802.07144/) (2018)
- [Balanced k-means for Parallel Geometric Partitioning](https://mlsanity.com/paper/1805.01208/) (2018)
- [Multilevel Acyclic Hypergraph Partitioning](https://mlsanity.com/paper/2002.02962/) (2020)
- [Scalable Shared-Memory Hypergraph Partitioning](https://mlsanity.com/paper/2010.10272/) (2020)
- [BiPart: A Parallel and Deterministic Multilevel Hypergraph Partitioner](https://mlsanity.com/paper/2012.13618/) (2020)
- [Multilevel Hypergraph Partitioning with Vertex Weights Revisited](https://mlsanity.com/paper/2102.01378/) (2021)
- [Buffered Streaming Graph Partitioning](https://mlsanity.com/paper/2102.09384/) (2021)

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

- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Inverse analysis of granular flows using differentiable graph neural network simulator](https://mlsanity.com/paper/2401.13695/) (2024)
- [A Comprehensive Survey on Graph Summarization with Graph Neural Networks](https://mlsanity.com/paper/2302.06114/) (2023)
- [An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2308.15602/) (2023)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Sparsity-Aware Communication for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2504.04673/) (2025)
- [A Hybrid Chimp Optimization Algorithm and Generalized Normal Distribution Algorithm with Opposition-Based Learning Strategy for Solving Data Clustering Problems](https://mlsanity.com/paper/2302.08623/) (2023)
- [Hypergraph clustering using Ricci curvature: an edge transport perspective](https://mlsanity.com/paper/2412.15695/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2604.01000/) (2026)
- [Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment](https://mlsanity.com/paper/2608.29635/) (2026)
- [Cost Characterization of Vertically Partitioned Federated Knowledge Graphs](https://mlsanity.com/paper/2609.13664/) (2026)

## Abstract (arXiv)

In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the last decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic. In particular, the survey extends the previous survey by also covering hypergraph partitioning and streaming algorithms, and has an additional focus on parallel algorithms.