A simple inverse power method for balanced graph cut

The existing inverse power ($\mathbf{I}\mathbf{P}$) method for solving the balanced graph cut lacks local convergence and its inner subproblem requires a nonsmooth convex solver. To address these issues, we develop a simple inverse power ($\mathbf{S}\mathbf{I}\mathbf{P}$) method using a novel equivalent continuous formulation of the balanced graph cut, and its inner subproblem allows an explicit analytic solution, which is the biggest advantage over $\mathbf{I}\mathbf{P}$ and constitutes the main reason why we call it $simple$. By fully exploiting the closed-form of the inner subproblem solution, we design a boundary-detected subgradient selection with which $\mathbf{S}\mathbf{I}\mathbf{P}$ is proved to be locally converged. We show that $\mathbf{S}\mathbf{I}\mathbf{P}$ is also applicable to a new ternary valued $\theta$-balanced cut which reduces to the balanced cut when $\theta =1$. When $\mathbf{S}\mathbf{I}\mathbf{P}$ reaches its local optimum, we seamlessly transfer to solve the $\theta$-balanced cut within exactly the same iteration algorithm framework and thus obtain $\mathbf{S}\mathbf{I}\mathbf{P}$-$\mathbf{p}\mathbf{e}\mathbf{r}\mathbf{t}\mathbf{u}\mathbf{r}\mathbf{b}$ – an efficient local breakout improvement of $\mathbf{S}\mathbf{I}\mathbf{P}$, which transforms some partitioned" vertices back to the un-partitioned" ones through the adjustable $\theta$. Numerical experiments on G-set for Cheeger cut and Sparsest cut demonstrate that $\mathbf{S}\mathbf{I}\mathbf{P}$ is significantly faster than $\mathbf{I}\mathbf{P}$ while maintaining approximate solutions of comparable quality, and $\mathbf{S}\mathbf{I}\mathbf{P}$-$\mathbf{p}\mathbf{e}\mathbf{r}\mathbf{t}\mathbf{u}\mathbf{r}\mathbf{b}$ outperforms $\mathtt{G}\mathtt{u}\mathtt{r}\mathtt{o}\mathtt{b}\mathtt{i}$ in terms of both computational cost and solution quality.