Approximate anchor-based similarity graph and its applications for large-scale data

Although spectral-based methods have become very popular in pattern recognition and data mining, they run into bottlenecks when dealing with large-scale data. This is mainly because the high computational cost of constructing the similarity graph. Recently, the anchor-based graph construction methods have been proposed, where the main time cost is composed of anchor generation and distance calculation. In this paper, we propose a unified framework to further speed up the construction of anchor-based graphs from two aspects. First, we propose a classifier-based hierarchical balanced binary K-means algorithm named C-BKHK to accelerate the process of generating anchors. Then, an efficient approximate nearest anchor search method called AKNN is designed based on C-BKHK for graph construction. By combining the anchor generating method C-BKHK with AKNN for graph construction, we propose a general framework named Approximate Anchor-based Similarity Graph Construction (A2SGC), which improves the speed of graph construction about two times at least. Further, we apply A2SGC to various learning tasks to validate its effectiveness, including spectral clustering and semi-supervised learning. Experimental results on several benchmark datasets demonstrate the superiority of our framework with respect to the running time and performance.