KDD2024 - Expander Hierarchies for Normalized Cuts on Graphs

Robin Münk
Expander decompositions have recently lead to important new results in the study of classical theoretical graph problems. Although fast algorithms for their construction exist, their implementations have so far not been feasible in practice. We introduce the first practically efficient algorithm for computing expander decompositions and -hierarchies and use it in XCut, our new solver for the normalized cut problem. Our extensive simulations on large real-world networks show that XCut produces cuts of superior quality compared to state-of-the-art solvers by a large margin on a variety of graph classes, like social network, infrastructure, e-mail and web-graphs while remaining competitive in running time.