Unsupervised Large Graph Embedding
Unsupervised Large Graph Embedding
复制标题
DOI：
10.1609/aaai.v31i1.10814
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
F. Nie;Wei Zhu;Xuelong Li
中科院分区：
文献类型：
--
作者：
F. Nie;Wei Zhu;Xuelong Li
基于谱的无监督降维方法有很多，包括Laplacian Eigenmap（LE）、Locality Preserving Projection（LPP）、Spectral Regression（SR）等。LPP和SR是两种不同的基于线性谱的方法，但是，我们发现LPP和SR是等价的，如果对称相似矩阵是双随机的、半正定的且秩为p，其中p是缩减的维数。这一发现促使我们寻找低秩双随机相似矩阵，并在此基础上提出了一种无监督的线性降维方法，称为无监督大图嵌入（ULGE）。ULGE的思想与LPP相似，它采用一种高效的方法构造相似性矩阵，然后高效地进行谱分析，计算复杂度可以降低到O（ndm），这比传统的基于谱的方法至少需要O（n^2d）的计算复杂度有了显著的提高，其中n，d和m分别是样本数，维数和锚点数。在多个公开数据集上的实验表明了该方法的有效性。
There are many successful spectral based unsupervised dimensionality reduction methods, including Laplacian Eigenmap (LE), Locality Preserving Projection (LPP), Spectral Regression (SR), etc. LPP and SR are two different linear spectral based methods, however, we discover that LPP and SR are equivalent, if the symmetric similarity matrix is doubly stochastic, Positive Semi-Definite (PSD) and with rank p, where p is the reduced dimension. The discovery promotes us to seek low-rank and doubly stochastic similarity matrix, we then propose an unsupervised linear dimensionality reduction method, called Unsupervised Large Graph Embedding (ULGE). ULGE starts with similar idea as LPP, it adopts an efficient approach to construct similarity matrix and then performs spectral analysis efficiently, the computational complexity can reduce to O(ndm), which is a significant improvement compared to conventional spectral based methods which need O(n^2d) at least, where n, d and m are the number of samples, dimensions and anchors, respectively. Extensive experiments on several public available data sets demonstrate the efficiency and effectiveness of the proposed method.