A scalable clustering algorithm to approximate graph cuts
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916434150424576 |
|---|---|
| author | Suchan, Leo Li, Housen Munk, Axel |
| author_facet | Suchan, Leo Li, Housen Munk, Axel |
| contents | Due to their computational complexity, graph cuts for cluster detection and identification are used mostly in the form of convex relaxations. We propose to utilize the original graph cuts such as Ratio, Normalized or Cheeger Cut to detect clusters in weighted undirected graphs by restricting the graph cut minimization to $st$-MinCut partitions. Incorporating a vertex selection technique and restricting optimization to tightly connected clusters, we combine the efficient computability of $st$-MinCuts and the intrinsic properties of Gomory-Hu trees with the cut quality of the original graph cuts, leading to linear runtime in the number of vertices and quadratic in the number of edges. Already in simple scenarios, the resulting algorithm Xist is able to approximate graph cut values better empirically than spectral clustering or comparable algorithms, even for large network datasets. We showcase its applicability by segmenting images from cell biology and provide empirical studies of runtime and classification rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_09613 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A scalable clustering algorithm to approximate graph cuts Suchan, Leo Li, Housen Munk, Axel Data Structures and Algorithms Discrete Mathematics 68W25 (Primary), 68R10 (Secondary) Due to their computational complexity, graph cuts for cluster detection and identification are used mostly in the form of convex relaxations. We propose to utilize the original graph cuts such as Ratio, Normalized or Cheeger Cut to detect clusters in weighted undirected graphs by restricting the graph cut minimization to $st$-MinCut partitions. Incorporating a vertex selection technique and restricting optimization to tightly connected clusters, we combine the efficient computability of $st$-MinCuts and the intrinsic properties of Gomory-Hu trees with the cut quality of the original graph cuts, leading to linear runtime in the number of vertices and quadratic in the number of edges. Already in simple scenarios, the resulting algorithm Xist is able to approximate graph cut values better empirically than spectral clustering or comparable algorithms, even for large network datasets. We showcase its applicability by segmenting images from cell biology and provide empirical studies of runtime and classification rate. |
| title | A scalable clustering algorithm to approximate graph cuts |
| topic | Data Structures and Algorithms Discrete Mathematics 68W25 (Primary), 68R10 (Secondary) |
| url | https://arxiv.org/abs/2308.09613 |