# HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 17 Aug 2021.

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

- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Faster Graph Embeddings via Coarsening](https://mlsanity.com/paper/2007.02817/) (2020)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [Flow-Based Local Graph Clustering with Better Seed Set Inclusion](https://mlsanity.com/paper/1811.12280/) (2018)

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

- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [T2T-LA: A Topology-to-Topology LLM Agent for Graph Learning with Neither Feature Access nor Task Knowledge](https://mlsanity.com/paper/2512.08964/) (2025)
- [Anchor-guided Hypergraph Condensation with Dual-level Discrimination](https://mlsanity.com/paper/2605.10001/) (2026)

## Abstract (arXiv)

Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To address the ever-increasing computational challenges, graph coarsening can be potentially applied for preprocessing a given hypergraph by aggressively aggregating its vertices (nodes). However, state-of-the-art hypergraph partitioning (clustering) methods that incorporate heuristic graph coarsening techniques are not optimized for preserving the structural (global) properties of hypergraphs. In this work, we propose an efficient spectral hypergraph coarsening scheme (HyperSF) for well preserving the original spectral (structural) properties of hypergraphs. Our approach leverages a recent strongly-local max-flow-based clustering algorithm for detecting the sets of hypergraph vertices that minimize ratio cut. To further improve the algorithm efficiency, we propose a divide-and-conquer scheme by leveraging spectral clustering of the bipartite graphs corresponding to the original hypergraphs. Our experimental results for a variety of hypergraphs extracted from real-world VLSI design benchmarks show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering as well as runtime efficiency when compared with existing state-of-the-art algorithms.