Unsupervised Large Graph Embedding Based on Balanced and Hierarchical K-Means

Feiping Nie, Wei Zhu, Xuelong Li

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

There are many successful spectral based unsupervised dimensionality reduction methods, including Laplacian Eigenmap (LE), Locality Preserving Projection (LPP), Spectral Regression (SR), etc. We find that LPP and SR are equivalent if the symmetric similarity matrix is doubly stochastic, Positive Semi-Definite (PSD) and with rank pp, where pp is the reduced dimension. Since solving SR is believed faster than solving LPP based on some related literature, the discovery promotes us to seek to construct such specific similarity matrix to speed up LPP solving procedures. We then propose an unsupervised linear method called Unsupervised Large Graph Embedding (ULGE). ULGE starts with a similar idea as LPP but adopts an efficient approach to construct anchor-based similarity matrix and then performs spectral analysis on it. Moreover, since conventional anchor generation strategies suffer kinds of problems, we propose an efficient and effective anchor generation strategy, called Balanced KK-means based Hierarchical KK-means (BHKH). The computational complexity of ULGE can reduce to O(ndm)O(ndm), which is a significant improvement compared to conventional methods need O(n2d)O(n2d) at least, where nn, dd and mm are the number of samples, dimensions, and anchors, respectively. Extensive experiments on several publicly available datasets demonstrate the efficiency and effectiveness of the proposed method.

Original languageEnglish
Pages (from-to)2008-2019
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number4
DOIs
StatePublished - 1 Apr 2022

Keywords

  • Large graph embedding
  • anchor based graph
  • balanced K-means based hierarchical K-means
  • dimensionality reduction

Fingerprint

Dive into the research topics of 'Unsupervised Large Graph Embedding Based on Balanced and Hierarchical K-Means'. Together they form a unique fingerprint.

Cite this