Shamap: Shape-based Manifold Learning

Fenglei Fan, Hongming Shan, Ge WangarXiv 2018 · arXiv

Introduction

High-dimensional data, such as medical imagery, speech signals, or protein structures, often contains significant redundancy. While these datasets may possess thousands of dimensions, the underlying information typically resides on a much simpler, low-dimensional "manifold" embedded within that high-dimensional space. Traditional nonlinear dimensionality reduction (NLDR) tools, most notably Isomap, attempt to "unroll" this manifold by preserving geodesic distances between points.

However, distance-based metrics often fail to capture the intrinsic topological structure of complex data. If a dataset contains a spiral or curved structure, Isomap may successfully flatten it into a straight line, but in doing so, it discards the "shape"—the very geometric property that defines the data's identity. This paper introduces Shamap (Shape-based Manifold Learning), a technique that prioritizes accumulated angular changes over raw distance to better preserve these essential topological features.

Methodology

Shamap functions as an angularly oriented variant of Multidimensional Scaling (MDS). The algorithm proceeds through three primary stages:

  1. K-Nearest Neighbors (KNN): The algorithm constructs a neighborhood graph to identify local connectivity within the data cloud.
  2. Accumulated Angular Change: This is the core innovation. Rather than calculating the shortest distance between two distant points, Shamap identifies the shortest path and sums the incremental angular changes between neighboring vectors along that path. This captures the "tangential change" or the "flow" of the trajectory.
  3. Embedding Construction: The algorithm computes the cosine values of these cumulative angles to form a similarity matrix. It then performs an eigenvalue decomposition to project the data into a lower-dimensional space. A scaling factor based on vector norms relative to a reference point ensures that the relative scale of the high-dimensional points is maintained in the projection.

Key Insights: Shape vs. Distance

The fundamental advantage of Shamap is its sensitivity to how data turns and curves. Because angular increments are perpendicular to the tangential direction of a trajectory, they are uniquely suited to capture the geometric flow that distance-based metrics ignore.

The Protein Test

In experiments involving a synthetic 3D model of alpha-helices and beta-sheets, the limitations of Isomap became clear. Isomap flattened the 3D spiral into a 1D straight line. While mathematically accurate regarding distance preservation, the resulting visualization was useless for understanding the protein's structure. Shamap, by contrast, preserved the 2D spiral shape, providing a far more informative representation.

Comparison of Isomap and Shamap on a synthetic protein unfolding model.

Feature Representation and Orientation

Shamap also excels at capturing semantic features like rotation. In a "Digit Orientation" test using images of the digit "1," Isomap struggled to organize the data because it was distracted by pixel intensity changes. Shamap successfully organized the images based on their rotation angle, revealing a circular manifold structure that reflects the actual physical transformation of the data.

Visualization of digit '1' orientations using Isomap vs. Shamap.

Experimental Results and Stability

The researchers evaluated Shamap against standard benchmarks including MNIST, the ORL Face Database, and the CMUPIE dataset.

  • Clustering and Classification: Shamap consistently outperformed LLE, k-PCA, and Isomap. On the ORL dataset, Shamap achieved a classification accuracy (ACC) of 0.96 at $K=8$, significantly higher than LLE (0.52) and k-PCA (0.44).
  • Robustness to $K$: A common challenge in manifold learning is selecting the number of neighbors ($K$). Small $K$ values often lead to "broken" manifolds in Isomap. Shamap proved significantly more robust, maintaining high accuracy across a wide range of $K$ values (8 to 15) where Isomap’s performance was erratic.
  • Visualization Quality: Visualizations of the CMUPIE face dataset using Shamap resulted in much cleaner, more distinct clusters compared to competitors, which often suffered from overlapping classes.

Conclusion and Future Work

Shamap demonstrates that preserving the "shape" of a manifold is often more critical for data understanding than preserving raw distance. While the method shows great promise in computer vision and structural biology, future research will address its sensitivity to the choice of reference points and the computational complexity associated with eigenvalue decompositions on massive datasets. The authors aim to further refine the algorithm's topological invariability for even more complex real-world applications.

Summary updated

Abstract

For manifold learning, it is assumed that high-dimensional sample/data points are embedded on a low-dimensional manifold. Usually, distances among samples are computed to capture an underlying data structure. Here we propose a metric according to angular changes along a geodesic line, thereby reflecting the underlying shape-oriented information or a topological similarity between high- and low-dimensional representations of a data cloud. Our results demonstrate the feasibility and merits of the proposed dimensionality reduction scheme.
BibTeX
@misc{fan2018shamap,
  author = {Fenglei Fan and Hongming Shan and Ge Wang},
  title = {{Shamap: Shape-based Manifold Learning}},
  year = {2018},
  eprint = {1802.05386},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.05386},
}
Figure