Classification by Cheeger Constant Regularization

This paper develops a classification algorithm in the framework of spectral graph theory where the underlying manifold of a high dimensional data set is described by a graph. The classification on the data is performed on the graph. The classifier optimizes an objective functional that combines prior information with the Cheeger constant. We interpret this approach as a regularized version of the Cheeger constant based classifier that we introduced recently. Our derivation shows that Cheeger regularization removes noise like a Laplacian based classifier but preserves better sharp boundaries needed for class separation. Experimental results show good performance of our proposed approach for classification applications.