Unsupervised Large Graph Embedding

By Feiping Nie, Wei Zhu, Xuelong Li. 2017

158 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Urban Studies

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Kevin Chen-Chuan Chang
2. Vincent Wenchen Zheng
3. Xiangyuan Lan
4. Pong Chi Yuen
5. Mang Ye
6. Zemin Liu
7. Junwei Han
8. Zhou Zhao

In Computer Vision and Pattern Recognition

1. Mang Ye
2. Xiangyuan Lan
3. Pong Chi Yuen
4. Junwei Han
5. Vincent Wenchen Zheng
6. Kevin Chen-Chuan Chang
7. Hongyun Cai
8. Tianji Pang

In Urban Studies

1. Pong Chi Yuen
2. Tianji Pang
3. Mang Ye
4. Xiangyuan Lan
5. Junwei Han
6. Feiping Nie

Citations in the corpus

• A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “Effective graph analytics can benefit a lot of applications, such as node classification [1], node clustering [2], node retrieval/recommendation [3], link prediction [4], etc.”
• Flexible Orthogonal Neighborhood Preserving Embedding (2017, methodology): “As for ULGE-K, we set its parameters as suggested in [Feiping Nie and Li, 2017].”
• Robust Anchor Embedding for Unsupervised Video Person re-IDentification in the Wild (2018, methodology): “A straightforward solution for label estimation is to design the graph Laplacian and conduct graph regularization as done in many anchor-graph based semi-supervised learning methods [25,31,37].”
• Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network (2018, background): “For example, in graph embedding, DeepWalk [27], LINE [32], node2vec [12], and many more [23, 25, 26] all try to learn an embedding vector for each node in the graph, which can preserve the graph structure.”
• Distance-Aware DAG Embedding for Proximity Search on Heterogeneous Graphs (2018, unknown): “Recent work uses graph embedding to do link prediction and proximity search; e.g., Deepwork (Perozzi, Al-Rfou, and Skiena 2014), LINE (Tang et al. 2015), node2vec (Grover and Leskovec 2016), and more (Zheng et al. 2016; Nie, Zhu, and Li 2017; Nikolentzos, Meladianos, and Vazirgiannis 2017).”