# SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 74 references that are in the map.
- First posted on arXiv 9 Oct 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [SpArch: Efficient Architecture for Sparse Matrix Multiplication](https://mlsanity.com/paper/2002.08947/) (2020)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [High-Quality Hypergraph Partitioning](https://mlsanity.com/paper/2106.08696/) (2021)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations](https://mlsanity.com/paper/1811.10722/) (2018)
- [GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis](https://mlsanity.com/paper/1911.04382/) (2019)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [Spectral Hypergraph Sparsifiers of Nearly Linear Size](https://mlsanity.com/paper/2106.02353/) (2021)
- [SF-GRASS: Solver-Free Graph Spectral Sparsification](https://mlsanity.com/paper/2008.07633/) (2020)
- [Towards Tight Bounds for Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/2011.06530/) (2020)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Similarity-Aware Spectral Sparsification by Edge Filtering](https://mlsanity.com/paper/1711.05135/) (2017)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)
- [Drawing Big Graphs using Spectral Sparsification](https://mlsanity.com/paper/1708.08659/) (2017)

## Abstract (arXiv)

State-of-the-art hypergraph partitioners utilize a multilevel paradigm to construct progressively coarser hypergraphs across multiple layers, guiding cut refinements at each level of the hierarchy. Traditionally, these partitioners employ heuristic methods for coarsening and do not consider the structural features of hypergraphs. In this work, we introduce a multilevel spectral framework, SHyPar, for partitioning large-scale hypergraphs by leveraging hyperedge effective resistances and flow-based community detection techniques. Inspired by the latest theoretical spectral clustering frameworks, such as HyperEF and HyperSF, SHyPar aims to decompose large hypergraphs into multiple subgraphs with few inter-partition hyperedges (cut size). A key component of SHyPar is a flow-based local clustering scheme for hypergraph coarsening, which incorporates a max-flow-based algorithm to produce clusters with substantially improved conductance. Additionally, SHyPar utilizes an effective resistance-based rating function for merging nodes that are strongly connected (coupled). Compared with existing state-of-the-art hypergraph partitioning methods, our extensive experimental results on real-world VLSI designs demonstrate that SHyPar can more effectively partition hypergraphs, achieving state-of-the-art solution quality.