Unsupervised Large Graph Embedding

Authors

  • Feiping Nie Northwestern Polytechnical University
  • Wei Zhu Northwestern Polytechnical University
  • Xuelong Li Chinese Academy of Sciences

DOI:

https://doi.org/10.1609/aaai.v31i1.10814

Keywords:

Spectral based dimensionality reduction, Equivalence between LPP and SR, Large graph embedding, Anchor-based graph

Abstract

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.

Downloads

Published

2017-02-13

How to Cite

Nie, F., Zhu, W., & Li, X. (2017). Unsupervised Large Graph Embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10814