Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

By Mikhail Belkin, Partha Niyogi. 2001

5,091 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning

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

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

Citations in the corpus

node2vec: Scalable Feature Learning for Networks (2016, methodology): “…on linear and non-linear dimensionality reduction techniques such as Principal Component Analysis, Multi-Dimensional Scaling and their extensions [3, 27, 30, 35] optimize an objective that transforms a representative data matrix of the network such that it maximizes the variance of the data…”
Spectral Networks and Locally Connected Networks on Graphs (2013, background): “This equivalence is given through the graph Laplacian, an operator which provides an harmonic analysis on the graphs [1].”
Predicting multicellular function through multi-layer tissue networks (2017, methodology): “The data matrix is projected to a low dimensional space using linear techniques based on SVD (Tang et al. , 2012), or non-linear techniques based on multi-dimensional scaling (Tenenbaum et al. , 2000; Belkin and Niyogi, 2001; Hou et al. , 2014).”
Deep Convolutional Networks on Graph-Structured Data (2015, methodology): “This distance is then used to build a Gaussian diffusion Kernel [1] In our experiments, we also consider the variant of self-tuning diffusion kernel [21] ω ( i, j ) = exp , where σ i is computed as the distance d ( i, i k ) corresponding to the k -th nearest neighbor i k of feature i .”
MixMatch: A Holistic Approach to Semi-Supervised Learning (2019, neutral): “, “transductive” models [14, 22, 21], graph-based methods [49, 4, 29], generative modeling [3, 27, 41, 9, 17, 23, 38, 34, 42], etc.”
UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, methodology): “Algorithms such as PCA [8], MDS [9], and Sammon mapping [20] fall into the former category while t-SNE [15] [26], Isomap [24], LargeVis [22], Laplacian eigenmaps [1] [2], diffusion maps [4], NeRV [28], and JSE [12] all fall into the latter category.”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Isomap (Tenenbaum et al., 2000), Local Linear Embedding (LLE) (Roweis and Saul, 2000), Hessian Local Linear Embedding (Donoho and Grimes, 2003), and Laplacian Eigenmaps (Belkin and Niyogi, 2001) all try to preserve exact local Euclidean distances from the original space when creating low-dimensional”
SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction (2017, methodology): “e-art deep learning approach to learn the representation of links. 2.2 Network Embedding There is a long history of work on network embedding. Earlier works such as IsoMap [24] and Laplacian Eigenmap [1] first construct the affinity graph of data using the feature vectors and then embed the affinity”
Compositional Fairness Constraints for Graph Embeddings (2019, methodology): “Traditional approaches to this problem include Laplacian eigenmaps (Belkin & Niyogi, 2002) and matrix factorization techniques (Ng et al., 2001), with recent years witnessing a surge in methods that rely on random-walk based objectives (Grover & Leskovec, 2016; Perozzi et al., 2014), deep…”
Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization (2020, methodology): “Carreira-Perpiñan (2010) pointed out that the attractive force used in Laplacian Eigenmaps is similar to that used in SNE.”
openTSNE: a modular Python library for t-SNE dimensionality reduction and embedding (2019, methodology): “However, when using initialization schemes based on PCA or Laplacian Eigenmaps (Belkin and Niyogi 2002), the clusters identified in the resulting embedding are typically grouped in a globally coherent manner.”
Visualizing Large-scale and High-dimensional Data (2016, methodology): “The non-linear methods such as Isomap [24], local linear embedding (LLE) [20], Laplacian Eigenmaps [2] are very eﬀective on laboratory data sets but do not perform really well on real-world high-dimensional data.”
Position-aware Graph Neural Networks (2019, background): “…et al., 2018b), with successful applications across domains such as social and information networks (Ying et al., 2018a), chemistry (You et al., 2018a), and biology (Zitnik & Leskovec, 2017). matrix-factorization approaches (Belkin & Niyogi, 2002), and random-walk approaches (Perozzi et al., 2014).”
Representation Learning on Graphs: Methods and Applications (2017, methodology): “Type Method Decoder Proximity measure Loss function (`) Laplacian Eigenmaps [4] ‖zi − zj‖(2)2 general DEC(zi, zj) · sG(vi, vj) Matrix Graph Factorization [1] zi zj Ai,j ‖DEC(zi, zj)− sG(vi, vj)‖(2)2 factorization GraRep [9] zi zj Ai,j ,A 2 i,j , .”
Graphite: Iterative Generative Modeling of Graphs (2018, methodology): “Popular ones include Laplacian Eigenmaps [2] and IsoMaps [36].”
FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling (2018, background): “A major category consists of factorization based algorithms that yield the embedding through matrix factorizations; see, e.g., Roweis & Saul (2000); Belkin & Niyogi (2001); Ahmed et al. (2013); Cao et al. (2015); Ou et al. (2016).”
PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks (2015, methodology): “Classical graph embedding algorithms such as MDS [9], IsoMap [28] and Laplacian eigenmap [1] are not applicable for embedding large-scale networks that contain millions of vertices and billions of edges.”
Pushing the Boundaries of Boundary Detection using Deep Learning (2015, background): “The solutions to this generalized eigenvector problem can be understood (Belkin & Niyogi, 2001) as euclidean embeddings of the inter-node distances - so nodes that have similar embeddings are likely to belong together and vice versa.”
Graph Embedding Techniques, Applications, and Performance: A Survey (2017, methodology): “Laplacian Eigenmaps [25] and Locally Linear Embedding”