Abstract
Several challenging problem in clustering, partitioning and imaging have traditionally been solved using the spectral technique. These problems include the normalized cut problem, the graph expander ratio problem, the Cheeger constant problem and the conductance problem. These problems share several common features: all seek a bipartition of a set of elements; the problems are formulated as a form of ratio cut equivalent to a quadratic ratio, referred to as the Rayleigh ratio. The Rayleigh ratio optimization is defined on discrete variables and a single sum constraint which we call the balance or orthogonality constraint. The spectral method for these problems is tantamount to solving a relaxation of the Rayleigh problem omitting the discreteness constraints. On the other hand, the relaxation of the orthogonality constraint yields optimization problems that are interesting in their own right. It is shown that a new, combinatorial, algorithm solves these latter discrete problems in strongly polynomial time in O(mn\log{n^2/m}) for a graph on n nodes and m edges. The implemented algorithm, using HPF (Hochbaum's Pseudo-Flow) as subroutine, is efficient enough to solve these bi-partitioning problems on millions of elements and more than 300 million edges within a couple of minutes. It is also shown, via an experimental study, that the results of the combinatorial algorithm proposed often improve dramatically on the quality of the results of the spectral method as measured by the proximity to the optimum of the respective NP-hard problems.