New L1-Norm Relaxations and Optimizations for Graph Clustering
Feiping Nie, Hua Wang, Cheng Deng, Xinbo Gao, Xuelong Li, Heng Huang
AAAI - 2016
In recent data mining research, the graph clustering methods, such as normalized cut and ratio cut, have been well studied and applied to solve many unsupervised learning applications. The original graph clustering methods are NP-hard problems. Traditional approaches used spectral relaxation to solve the graph clustering problems. The main disadvantage of these approaches is that the obtained spectral solutions could severely deviate from the true solution. To solve this problem, in this paper, we propose a new relaxation mechanism for graph clustering methods. Instead of minimizing the squared distances of clustering results, we use the l1-norm distance. More important, considering the normalized consistency, we also use the l1-norm for the normalized terms in the new graph clustering relaxations. Due to the sparse result from the l1-norm minimization, the solutions of our new relaxed graph clustering methods get discrete values with many zeros, which are close to the ideal solutions. Our new objectives are difficult to be optimized, because the minimization problem involves the ratio of non-smooth terms. The existing sparse learning optimization algorithms cannot be applied to solve this problem. In this paper, we propose a new optimization algorithm to solve this difficult non-smooth ratio minimization problem. The extensive experiments have been performed on three two-way clustering and eight multi-way clustering benchmark data sets. All empirical results show that our new relaxation methods consistently enhance the normalized cut and ratio cut clustering results.
Links
- View publications from Hua Wang
- View publications presented in AAAI
- View publications in the project, Mining Materials Genome Data for Prediction and Guidance of Nanoparticle Synthesis
- View publications researching Graph Representations/Learning
- View publications researching Robust Learning Models
Cite this paper
MLA
Nie, Feiping, et al. "New l1-norm relaxations and optimizations for graph clustering." Thirtieth AAAI Conference on Artificial Intelligence. 2016.
BibTeX
@inproceedings{nie2016new,
title={New l1-norm relaxations and optimizations for graph clustering},
author={Nie, Feiping and Wang, Hua and Deng, Cheng and Gao, Xinbo and Li, Xuelong and Huang, Heng},
booktitle={Thirtieth AAAI Conference on Artificial Intelligence},
year={2016}
}