# A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 26 Nov 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Efficient Parameter-free Clustering Using First Neighbor Relations](https://mlsanity.com/paper/1902.11266/) (2019)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [Topology-Aware Graph Pooling Networks](https://mlsanity.com/paper/2010.09834/) (2020)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [Scalable Spectral Clustering Using Random Binning Features](https://mlsanity.com/paper/1805.11048/) (2018)
- [Spectral Clustering of Attributed Multi-relational Graphs](https://mlsanity.com/paper/2311.01840/) (2023)

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

- [Expander Hierarchies for Normalized Cuts on Graphs](https://mlsanity.com/paper/2406.14111/) (2024)

## Abstract (arXiv)

Normalized-Cut (N-Cut) is a famous model of spectral clustering. The traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via K-means or spectral rotation. However, this paradigm brings two vital problems: 1) two-stage methods solve a relaxed version of the original problem, so they cannot obtain good solutions for the original N-Cut problem; 2) solving the relaxed problem requires eigenvalue decomposition, which has O(n3) time complexity (n is the number of nodes). To address the problems, we propose a novel N-Cut solver designed based on the famous coordinate descent method. Since the vanilla coordinate descent method also has O(n3) time complexity, we design various accelerating strategies to reduce the time complexity to O(|E|) (|E| is the number of edges). To avoid reliance on random initialization which brings uncertainties to clustering, we propose an efficient initialization method that gives deterministic outputs. Extensive experiments on several benchmark datasets demonstrate that the proposed solver can obtain larger objective values of N-Cut, meanwhile achieving better clustering performance compared to traditional solvers.