Multiscale Manifold Learning

Chang Wang, Sridhar MahadevanAAAI 2013 · OpenReview

Abstract

Many high-dimensional data sets that lie on a low-dimensional manifold exhibit nontrivial regularities at multiple scales. Most work in manifold learning ignores this multiscale structure. In this paper, we propose approaches to explore the deep structure of manifolds. The proposed approaches are based on the diffusion wavelets framework, data driven, and able to directly process directional neighborhood relationships without ad-hoc symmetrization. The proposed multiscale algorithms are evaluated using both synthetic and real-world data sets, and shown to outperform previous manifold learning methods.

Introduction

Traditional manifold learning techniques, such as Laplacian Eigenmaps or Locality Preserving Projections (LPP), typically produce a single "flat" representation of data. While effective for some tasks, these methods face two significant challenges. First, they are often "scale-blind," providing a global embedding that fails to capture hierarchical structures where local details (e.g., facial features) and global structures (e.g., head shape) coexist. Second, they frequently rely on ad-hoc symmetrization of neighborhood graphs, which can destroy critical information in datasets characterized by directed relationships, such as citation networks.

This paper introduces a multiscale framework using diffusion wavelets to build a hierarchy of embeddings. This approach captures both local and global structures while natively handling non-symmetric (directed) graphs, avoiding the pitfalls of traditional symmetrization.

The Diffusion Wavelet Framework

The core of the proposed method is the integration of Diffusion Wavelets (DWT) into manifold learning. Unlike standard spectral methods that utilize global eigenvectors, DWT employs dyadic powers of a diffusion operator ($T, T^2, T^4, \dots$) to construct a hierarchy of scaling functions.

Hierarchical construction of scaling functions using diffusion wavelets across multiple scales.

As illustrated in the framework above, the process involves repeated QR decompositions to compress the operator at each scale. This acts as a "tunable microscope": at fine scales (low $j$), the functions are sparse and capture local regularities; at coarse scales (high $j$), they represent broader global structures. Crucially, the authors prove that this framework can process non-symmetric matrices directly, allowing for the reconstruction of manifolds from directed k-nearest neighbor relationships.

Experimental Evaluation

The multiscale approach was evaluated across diverse datasets, ranging from synthetic manifolds to high-dimensional text data.

Synthetic and Citation Data

On a synthetic Punctured Sphere, the directed multiscale approach successfully reconstructed the manifold's shape, whereas standard methods failed due to the distortions introduced by symmetrization. Similarly, in classification tasks on the KDD Cup 2003 Citation Graph, the directed Multiscale LPP significantly outperformed Laplacian Eigenmaps by preserving the inherent directionality of citations.

Diffusion Faces vs. Eigenfaces

Using the Olivetti Faces dataset, the authors compared traditional "eigenfaces" with their "diffusion faces." While eigenfaces tend to be global and blurry, diffusion faces at finer scales are sparse and localized.

A sparse diffusion face capturing localized features like the eyes and nose area.

As seen in the example above, these localized bases provide a more intuitive decomposition of the data, focusing on specific features rather than global averages. This automatic discovery of intrinsic dimensionality allows users to select the appropriate "zoom level" for their specific analysis task, such as reducing 5,000 dimensions down to a specific level (e.g., 570) that optimizes classification accuracy.

Conclusion

By leveraging the diffusion wavelets framework, this work provides a robust method for multiscale manifold learning that respects the directed nature of real-world data. While the current implementation focuses on selecting the optimal single level for a task, future work may explore the simultaneous use of multiple levels for even richer data representations. Additionally, further optimization of the DWT process could enhance its scalability for massive datasets comprising millions of nodes.

Summary updated

Abstract

Many high-dimensional data sets that lie on a low-dimensional manifold exhibit nontrivial regularities at multiple scales. Most work in manifold learning ignores this multiscale structure. In this paper, we propose approaches to explore the deep structure of manifolds. The proposed approaches are based on the diffusion wavelets framework, data driven, and able to directly process directional neighborhood relationships without ad-hoc symmetrization. The proposed multiscale algorithms are evaluated using both synthetic and real-world data sets, and shown to outperform previous manifold learning methods.
BibTeX
@inproceedings{wang2013multiscale,
  author = {Chang Wang and Sridhar Mahadevan},
  title = {{Multiscale Manifold Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=Bk4JGlb_WH},
}
Figure