New l1-Norm Relaxations and Optimizations for Graph Clustering

Authors

  • Feiping Nie University of Texas at Arlington
  • Hua Wang Colorado School of Mines
  • Cheng Deng Xidian University
  • Xinbo Gao Xidian University
  • Xuelong Li Chinese Academy of Sciences
  • Heng Huang University of Texas at Arlington

DOI:

https://doi.org/10.1609/aaai.v30i1.10278

Keywords:

Graph Clustering, l1-norm Normalized Cut

Abstract

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 nonsmooth 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.

Downloads

Published

2016-03-02

How to Cite

Nie, F., Wang, H., Deng, C., Gao, X., Li, X., & Huang, H. (2016). New l1-Norm Relaxations and Optimizations for Graph Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10278

Issue

Section

Technical Papers: Machine Learning Methods