深圳大学计算机与软件学院
College of Computer Science and Software Engineering, SZU

LABIN: Balanced Min Cut for Large-Scale Data

IEEE Transactions on Neural Networks and Learning Systems

 

Xiaojun Chen1    Renjie Chen2    Qingyao Wu2    Yixiang Fang3    Feiping Nie4    Joshua Zhexue Huang1

1Shenzhen University    2South China University of Technology    3University of Hong Kong    4Northwestern Polytechnical University

 

Abstract

Although many spectral clustering algorithms have been proposed during the past decades, they are not scalable to large-scale data due to their high computational complexities. In this paper, we propose a novel spectral clustering method for large-scale data, namely, large-scale balanced min cut (LABIN). A new model is proposed to extend the self-balanced min-cut (SBMC) model with the anchor-based strategy and a fast spectral rotation with linear time complexity is proposed to solve the new model. Extensive experimental results show the superior performance of our proposed method in comparison with the state-of-the-art methods including SBMC.

 

Fig. 1. Plots of three synthetic data sets. (a) Plot of D11. (b) Plot of D21.(c) Plot of D31.

 

Fig. 4. Average time cost of LSC, SNC, and LABIN versus the number of anchors m , average time cost of KASP versus the number of clusters m , and average time cost of Nyström versus the number of samples m on three data sets.

 

Fig. 8. Accuracy results versus s on three data sets. (a) PA25. (b) CA28. (c) MNIST.

 

Fig. 9. NMI results versus s on three data sets. (a) PA25. (b) CA28. (c) MNIST.

 

Acknowledgements

This work was supported in part by NSFC under Grant 61773268, Grant 61836005, and Grant 61876208, in part by the Shenzhen Research Foundation for Basic Research, China, under Grant JCYJ20180305124149387, in part by the National Engineering Laboratory for Big Data System Computing Technology, Guangdong Provincial Scientific and Technological funds 2017B090901008 and 2018B010108002, in part by Pearl River S&T Nova Program of Guangzhou under Grant 201806010081, and in part by the CCF-Tencent Open Research Fund RAGR20190103.

 

Bibtex

@article{chen2020labin,

author = { Xiaojun Chen and Renjie Chen and Qingyao Wu and Yixiang Fang and Feiping Nie and Joshua Zhexue Huang},

title = {LABIN: Balanced Min Cut for Large-Scale Data},

journal = {IEEE Transactions on Neural Networks and Learning Systems},

year={2020},

volume={31},

number={3},

pages={725--736},

doi={10.1109/TNNLS.2019.2909425 },

}

Downloads