A NEW CONTINUOUS OPTIMIZATION MODEL FOR SPECTRAL CLUSTERING
Liu Xin1,2, Michael Ng3, Zhang Rui1,2, Zhang Zaikun4
1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;
2. University of Chinese Academy of Sciences, Beijing 100190, China;
3. Hong Kong Baptist University, China;
4. Hong Kong Polytechnic University, China
Clustering and graph partition play an important role in big data analysis. These problems are often formulated as combinatorial optimization models. Consequently, to solve them efficiently is difficult. In this paper, we propose a novel continuous optimization model, and a block coordinate decent method to solve it. Numerical experiments show that the new approach has great potential in dealing with clustering and graph partition problems. We also give preliminary analysis on the relationship between our model and the original combinatorial optimization model.
. A NEW CONTINUOUS OPTIMIZATION MODEL FOR SPECTRAL CLUSTERING[J]. Mathematica Numerica Sinica, 2018, 40(4): 354-366.
Chung F. Spectral Graph Theory. Number 92 in Regional Conferences in Mathematics. American Mathematical Society, Providence, 1997.
Donath W E and Hoffman A J. Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices[J]. IBM Technical Disclosure Bulletin, 1972, 15(3):938-944.
Donath W E and A. J. Hoffman A J. Lower bounds for the partitioning of graphs[J]. IBM Journal of Research and Development, 1973, 17(5):420-425.
Hagen L and Kahng A B. New spectral methods for ratio cut partition and clustering[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992, 11(9):1074- 1085.
Lütkepohl H. Handbook of matrices. John Wiley & Sons, New York, 1996.
Mohar B. The Laplacian spectrum of graphs. In Y. Alavi, G. Chartrand, O. R. Oellermann, and J. Schwenk, A, editors, Graph Theory, Combinatorics, and Applications:Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, volume 2, pages 871-898. Wiley, New York, 1991.
Mohar B. Some applications of Laplace eigenvalues of graphs. In G. Hahn and G. Sabidussi, editors, Graph Symmetry:Algebraic Methods and Applications, volume 497 of Nato Science Series C, pages 225-275. Springer Netherlands, Dordrecht, 1997.
Ng A Y, Jordan M I, and Weiss Y. On spectral clustering:Analysis and an algorithm. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 849-856. MIT Press, 2002.
Shi J and Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.
von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4):395-416.
von Luxburg U, Bousquet O, and Belkin M. On the convergence of spectral clustering on random samples:the normalized case. In International Conference on Computational Learning Theory, pages 457-471. Springer, 2004.