# Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 45 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 13 of 13)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Optimal Transport Graph Neural Networks](https://mlsanity.com/paper/2006.04804/) (2020)
- [k-way Hypergraph Partitioning via n-Level Recursive Bisection](https://mlsanity.com/paper/1511.03137/) (2015)
- [Memetic Multilevel Hypergraph Partitioning](https://mlsanity.com/paper/1710.01968/) (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)
- [Partitioning Complex Networks via Size-constrained Clustering](https://mlsanity.com/paper/1402.3281/) (2014)
- [Multilevel Hypergraph Partitioning with Vertex Weights Revisited](https://mlsanity.com/paper/2102.01378/) (2021)
- [Longest Processing Time rule for identical parallel machines revisited](https://mlsanity.com/paper/1801.05489/) (2018)

## Abstract (arXiv)

We propose a balanced coarsening scheme for multilevel hypergraph partitioning. In addition, an initial partitioning algorithm is designed to improve the quality of k-way hypergraph partitioning. By assigning vertex weights through the LPT algorithm, we generate a prior hypergraph under a relaxed balance constraint. With the prior hypergraph, we have defined the Wasserstein discrepancy to coordinate the optimal transport of coarsening process. And the optimal transport matrix is solved by Sinkhorn algorithm. Our coarsening scheme fully takes into account the minimization of connectivity metric (objective function). For the initial partitioning stage, we define a normalized cut function induced by Fiedler vector, which is theoretically proved to be a concave function. Thereby, a three-point algorithm is designed to find the best cut under the balance constraint.