Fast Unsupervised Graph Embedding Based on Anchors

Abstract

Graph embedding is a widely used method for dimensionality reduction due to its computational effectiveness.The computational complexity of graph embedding method to construct traditional K-Nearest Neighbors (K-NN) graph is at least O(n2d), where n and d represents the sample size and dimensions respectively.The construction of K-NN graphs is very time-consuming since the computational complexity is proportional to the square of the number of samples in the case of a large amount of data, which will limit the application of graph embedding algorithms on large-scale data sets.To address this problem, a fast unsupervised graph embedding based on anchors (FUGE) method is proposed in this paper.FUGE first selects anchors (representative points) from the data, then constructs a similarity graph between the data and anchors, and finally performs graph embedding analysis.Since the number of anchors is much smaller than the number of data, the proposed method can effectively reduce the computational complexity of the process of graph construction.Different from using the kernel function to construct the similarity graph, FUGE directly learns the data point-anchor similarity graph by the neighbor information of the data, which further accelerates the process of graph construction.The overall computational complexity of FUGE is O(nd2+nmd), where m is the number of anchors.Extensive experiments on real-world benchmark data sets show the effectiveness and efficiency of the proposed method.

Keywords

• dimensionality reduction|graph embedding|anchors|<italic>k</italic>-means++|orthogonal constraint