High-dimensional data rarely fills its embedding space uniformly. Instead, it often concentrates on a lower-dimensional, highly non-linear surface known as a manifold.
Traditional linear methods like Principal Component Analysis (PCA) analyze global variance, attempting to find orthogonal axes that maximize the spread across an entire dataset. However, if a manifold is highly curved—such as the complex variations of human faces under different lighting conditions or the continuous spectrum of a star—global Euclidean distances become deceptive. Two points that are far apart along the winding surface of a manifold might appear close due to a straight-line global shortcut.
The core insight of neighborhood-preserving methods is a fundamental property of smooth manifolds: locally, everything looks flat. Just as the Earth appears flat from a human perspective on the ground, any curved manifold behaves like a linear Euclidean space if you zoom in closely enough. Rather than measuring global distances, we can capture the true geometry of a complex manifold by characterizing how each data point relates to its immediate neighbors.
Characterizing Geometry through Local Reconstruction
How do we mathematically capture this local flatness? The classic approach, pioneered by Locally Linear Embedding (LLE), breaks the problem into two distinct steps: characterizing the local geometry, and then mapping it to a lower-dimensional space.
As explained by John Aldo Lee et al. in Locally Linear Embedding versus Isotop, we assume that each data point and its nearest neighbors lie on or near a locally linear patch of the manifold. We can represent each point as a weighted linear combination of its $k$-nearest neighbors. By computing a set of reconstruction weights $W_{ij}$ that minimize the squared reconstruction error, we capture the local patch's structure.
Crucially, these weights are invariant to global rotations, translations, and scalings. Once these weights are fixed, the next step is to find a low-dimensional configuration of points that preserves these exact same reconstruction weights. This is achieved by solving a global eigenvalue problem, yielding a low-dimensional embedding where the local geometric relationships remain intact.
This principle of local linear reconstruction is highly versatile. For instance, Chunyan Liang et al. utilize this mechanism in Factor Analysis of Neighborhood-Preserving Embedding for Speaker Verification to preserve speech manifolds, outperforming traditional global variance methods. Similarly, Buyue Qian et al. extend this concept to semi-supervised multi-label classification in Semi-Supervised Dimension Reduction for Multi-Label Classification, showing that local linear reconstruction can simultaneously capture geometric relationships across both feature and label spaces.
Linear Projections and Graph Laplacians
While standard LLE provides a non-parametric mapping for a fixed set of training points, it does not naturally define a continuous transformation function for unseen data. To address this, Locality Preserving Projections (LPP) reformulates the problem as a linear subspace learning method.
As introduced by Xiaofei He et al. in Learning a Locality Preserving Subspace for Visual Recognition, LPP constructs an explicit adjacency graph where edges connect neighboring data points. Instead of computing reconstruction weights, it solves a generalized eigenvalue problem based on the graph Laplacian. The objective is to find a linear transformation matrix that minimizes the distance between neighboring points in the projected low-dimensional space. By preserving these local relationships, the resulting "Laplacianfaces" prove significantly more robust to real-world variations in lighting and facial expressions than global methods like PCA.
The graph-based formulation allows the core mechanism to scale to higher-order data structures and non-Euclidean spaces:
- Tensor Spaces: Xiaofei He et al. developed Tensor Subspace Analysis, which avoids flattening images into vectors—a process that destroys spatial layouts—by constructing adjacency graphs directly over tensor representations.
- Non-Euclidean Manifolds: To handle data that naturally resides on curved mathematical surfaces, Boyue Wang et al. proposed Grassmann Locality Preserving Projections in Locality Preserving Projections for Grassmann manifold, optimizing projections that preserve the intrinsic geometric relationships of points on non-Euclidean manifolds.
- Probabilistic Neighborhoods: Alternatively, instead of linear projections, local neighborhoods can be preserved probabilistically. James Cook et al. demonstrate in Visualizing Similarity Data with a Mixture of Maps. that converting pairwise distances into conditional probabilities and minimizing Kullback-Leibler divergence prioritizes local neighborhood structures over global distances, preventing crowding artifacts during visualization.
Aligning and Imputing Latent Spaces
The intuition of local neighborhood preservation extends far beyond traditional dimensionality reduction; it serves as a powerful constraint for aligning disparate latent spaces or imputing missing information.
Consider the challenge of combining multiple pre-trained word embedding spaces (like Word2vec and GloVe) into a single unified representation. Kohei Hayashi et al. address this in Think Globally, Embed Locally - Locally Linear Meta-embedding of Words by enforcing that a target word's reconstruction weights must be shared across all source spaces. By finding a low-dimensional space that respects this local semantic consensus, they build highly accurate meta-embeddings without requiring a complex global transformation.
Similarly, the local neighborhood structure can be used to rescue unreliable or rare word embeddings. Shibo Yao et al. introduce Latent Semantic Imputation in Enhancing Domain Word Embedding via Latent Semantic Imputation, solving a non-negative least squares problem with simplex constraints to represent rare entities as linear combinations of well-mapped neighbors. This allows structural information from an external affinity space to flow seamlessly into the semantic embedding space.
In text retrieval, Deepak P 0001 et al. demonstrate in Latent Space Embedding for Retrieval in Question-Answer Archives that preserving the local neighborhood structures of both question and answer spaces bridges the lexical gap far more effectively than global topic models. To refine modern deep sentence representations, Changrong Min et al. apply locality-preserving embeddings to SBERT outputs in Locality Preserving Sentence Encoding, "unfolding" the complex geometric manifold of language to improve semantic similarity tasks without any additional fine-tuning.
Widespread Applications across Domains
Because the assumption of local linearity is so fundamental, neighborhood preservation techniques have found success across an extraordinary variety of scientific and engineering domains:
- Physical Sciences: In astronomy, Scott F. Daniel et al. show in CLASSIFICATION OF STELLAR SPECTRA WITH LOCAL LINEAR EMBEDDING that LLE can map complex stellar spectra onto a continuous, low-dimensional "stellar locus" that correlates directly with physical properties like temperature, providing a more intuitive classification than PCA.
- Bioinformatics: For predicting drug side effects, Wen Zhang 0008 et al. leverage linear neighborhood similarity in A unified frame of predicting side effects of drugs by using linear neighborhood similarity to represent a drug candidate as a combination of its neighbors, creating a robust similarity metric for high-dimensional feature spaces. In protein analysis, Xinke Zhan et al. apply LPP in Predicting Protein–Protein Interactions Based on Ensemble Learning-Based Model from Protein Sequence to compress evolutionary profiles while ensuring similar biological sequences remain close.
- Generative Models: To navigate the latent spaces of Generative Adversarial Networks (GANs) for satellite imagery, Georgia Kourmouli et al. use LPP in Locality-preserving Directions for Interpreting the Latent Space of Satellite Image GANs to discover semantic trajectories (like urbanization) that avoid the visual artifacts typically introduced by global variance methods.
- Signal Processing and Retrieval: In Outlier Detection in Energy Disaggregation Using Subspace Learning and Gaussian Mixture Model, Xiuming Tang et al. combine LPP with Gaussian Mixture Models to isolate sensor errors in complex household energy data. Furthermore, Hualei Shen et al. develop a multi-view variant of LLE in Multiview Locally Linear Embedding for Effective Medical Image Retrieval to weight and align distinct visual features like texture and shape, bypassing the curse of dimensionality in medical image retrieval.
Key Foundational Work
Locally Linear Embedding versus Isotop (2003) — contributed 1 concept elements to this direction.
Learning a Locality Preserving Subspace for Visual Recognition (2003) — contributed 1 concept elements to this direction.
Locality preserving indexing for document representation (2004) — contributed 1 concept elements to this direction.