Improved MinMax Cut Graph Clustering with Nonnegative Relaxation

View Researcher II's Other Codes

Disclaimer: “The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).”

Please contact us in case of a broken link from here

Authors Feiping Nie, Chris Ding, Dijun Luo, Heng Huang
Journal/Conference Name The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)
Paper Category
Paper Abstract In graph clustering methods, MinMax Cut tends to provide more balanced clusters as compared to Ratio Cut and Normalized Cut. The traditional approach used spectral relaxation to solve the graph cut problem. The main disadvantage of this approach is that the obtained spectral solution has mixed signs, which could severely deviate from the true solution and have to resort to other clustering methods, such as K-means, to obtain final clusters. In this paper, we propose to apply additional nonnegative constraint into MinMax Cut graph clustering and introduce novel algorithms to optimize the new objective. With the explicit nonnegative constraint, our solutions are very close to the ideal class indicator matrix and can directly assign clusters to data points. We present efficient algorithms to solve the new problem with the nonnegative constraint rigorously. Experimental results show that our new algorithm always converges and significantly outperforms the traditional spectral relaxation approach on ratio cut and normalized cut.
Date of publication 2010
Code Programming Language MATLAB

Copyright Researcher II 2021