Nonlinear Eigenproblems in Data Analysis - Balanced Graph Cuts and the RatioDCA-Prox

Spectral clustering is one of the standard methods for graph-based clustering [1]. It is based on the spectral relaxation of the so called normalized cut, which is one of the most popular criteria for balanced graph cuts. While the spectral relaxation is known to be loose [2], tighter relaxations based on the graph p-Laplacian have been proposed in [3]. Exact relaxations for the Cheeger cut based on the nonlinear eigenproblem of the graph 1-Laplacian have been proposed in [4, 5]. In [6] the general balanced graph cut problem of an undirected, weighted graph (V,E) is considered.