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.

通过引入第一个实际有效的算法来计算扩展者分解及其层级，我们在大量的实验中展示了我们基于扩展者的算法在解决归一化割图聚类问题上相对于当前最先进的解决方案在解决质量上大大优于各种图类，如引用、电子邮件、社交网络或网络图，并且在运行时间上仍然具有竞争力。