# Expander Hierarchies for Normalized Cuts on Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 20 Jun 2024.

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

- [Adversarial Attack on Community Detection by Hiding Individuals](https://mlsanity.com/paper/2001.07933/) (2020)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization](https://mlsanity.com/paper/1812.08942/) (2018)
- [Expander Decomposition and Pruning: Faster, Stronger, and Simpler](https://mlsanity.com/paper/1812.08958/) (2018)
- [Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time](https://mlsanity.com/paper/1708.03962/) (2017)
- [Deterministic Mincut in Almost-Linear Time](https://mlsanity.com/paper/2106.05513/) (2021)
- [Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time](https://mlsanity.com/paper/1611.02864/) (2016)
- [Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2-ε)-Time](https://mlsanity.com/paper/1611.03745/) (2016)
- [The Expander Hierarchy and its Applications to Dynamic Graph Algorithms](https://mlsanity.com/paper/2005.02369/) (2020)
- [Maintaining Expander Decompositions via Sparse Cuts](https://mlsanity.com/paper/2204.02519/) (2022)
- [Dynamic Maintenance of Monotone Dynamic Programs and Applications](https://mlsanity.com/paper/2301.01744/) (2023)
- [A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization](https://mlsanity.com/paper/2311.15214/) (2023)

## Abstract (arXiv)

Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.