Expander Hierarchies for Normalized Cuts on Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911619991207936 |
|---|---|
| author | Hanauer, Kathrin Henzinger, Monika Münk, Robin Räcke, Harald Vötsch, Maximilian |
| author_facet | Hanauer, Kathrin Henzinger, Monika Münk, Robin Räcke, Harald Vötsch, Maximilian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14111 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expander Hierarchies for Normalized Cuts on Graphs Hanauer, Kathrin Henzinger, Monika Münk, Robin Räcke, Harald Vötsch, Maximilian Data Structures and Algorithms Machine Learning 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. |
| title | Expander Hierarchies for Normalized Cuts on Graphs |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2406.14111 |