Generalized Unsupervised Manifold Alignment

Zhen Cui, Hong Chang, Shiguang Shan, Xilin Chen

Introduction

In machine learning, we often deal with datasets that describe the same underlying phenomenon but exist in different "spaces"—such as a person’s face captured from two different camera angles, or the same document written in two different languages. Manifold alignment is the process of projecting these disparate datasets into a mutual embedding space where they can be directly compared.

The major hurdle has been that most effective alignment methods are supervised or semi-supervised, requiring "anchor points" (known pairs of corresponding samples) to learn the transformation. Unsupervised methods exist, but they traditionally face a combinatorial explosion problem: trying to find the best matching between $N$ points in one set and $M$ points in another often requires checking an astronomical number of permutations, making them computationally impractical for real-world use.

Generalized Unsupervised Manifold Alignment (GUMA) is a novel framework that aligns two different but related datasets without requiring any pre-existing labels or known correspondences. By jointly optimizing for point-to-point matching and a shared embedding space, GUMA achieves state-of-the-art performance in tasks like cross-domain image matching and protein structure alignment while remaining computationally efficient.

Methods

GUMA formulates unsupervised alignment as an explicit integer optimization problem. The core of the method is a three-part objective function:

  1. Geometry Matching ($E_s$): Ensures that the global topological structures of the two manifolds are similar by comparing the full adjacency matrices of both datasets.
  2. Feature Matching ($E_f$): Penalizes the distance between corresponding points once they are projected into the mutual embedding space.
  3. Geometry Preserving ($E_p$): Ensures that if two points were neighbors in their original space, they remain neighbors in the new shared space (using Graph Laplacians).

To solve this without checking every possible permutation, the authors use an alternating optimization strategy. They fix the projections to find the best matching matrix, then fix the matching to find the best projections. To handle the "NP-hard" nature of matching, they employ a relaxed version of the Frank-Wolfe algorithm combined with the Kuhn-Munkres (KM) algorithm. This turns a discrete search into a continuous optimization problem that converges efficiently.

Datasets

The authors evaluated GUMA across several diverse domains:

  • Multi-PIE: A massive face database used to align images across different poses and expressions.
  • PDB-1G7O: A bioinformatics dataset consisting of protein sequences (Glutaredoxin) to test structural manifold matching.
  • YouTube Faces: 3,425 video clips used for unsupervised face verification.
  • Domain Adaptation Benchmark: A collection of four datasets (Amazon, DSLR, Webcam, and Caltech-256) commonly used to test how well a model trained on one domain performs on another.

Key Insights and Ideas

  • Synergy is Key: Manifold structure and sample features are complementary. Using either one alone for alignment yields mediocre results, but combining them improves accuracy by more than 15% in face-matching tasks.
  • Global over Local: Unlike previous methods that only looked at local neighborhoods (which can shift during alignment), GUMA looks at the global adjacency matrix. This makes the alignment much more robust to noise and partial overlaps.
  • Efficiency through Relaxation: By relaxing the 0-1 integer constraint during the optimization steps, the authors bypassed the $K!$ computational cost that plagued earlier unsupervised attempts, making unsupervised alignment viable for datasets with hundreds or thousands of points.

Key Results

GUMA demonstrates strong empirical performance across both visual and structural alignment tasks.

Face matching accuracy comparison
  • Face Matching: As seen above, GUMA significantly outperformed previous unsupervised methods (Wang’s and Pei’s). In pose matching, it achieved nearly 90% accuracy, whereas previous methods hovered between 20% and 40%.
  • Protein Structure Alignment: When aligning 3D protein structures (PDB-1G7O), GUMA provides a noticeably tighter and more accurate structural match compared to baseline methods.
3D protein structure alignment comparison
  • Video Verification: On the YouTube Faces dataset, GUMA improved face verification accuracy from 61.8% (unaligned) to 65.7% in a purely unsupervised setting.
  • Domain Adaptation: GUMA achieved the best results in 9 out of 12 cross-domain scenarios, outperforming state-of-the-art methods like Geodesic Flow Kernel (GFK) and Subspace Alignment (SA). Its average accuracy of 44.98% beat the next best method (43.68%).

Limitations and Future Work

While GUMA is a significant step forward, the authors note a few areas for growth:

  • Linear Constraints: The current model primarily uses explicit linear projections. While they mention kernel tricks for non-linearity, a fully integrated deep learning approach could potentially capture even more complex manifold deformations.
  • Computational Scaling: Although much faster than previous methods, the KM algorithm used for matching still has a cubic complexity ($O(n^3)$). For extremely large-scale applications, further approximations or hierarchical matching might be necessary.
  • Integer Constraint Relaxation: Further generalizing GUMA by relaxing the strict integer constraints even more could open up new applications in soft-matching and probabilistic alignment.

Summary updated

Abstract

In this paper, we propose a generalized Unsupervised Manifold Alignment (GUMA) method to build the connections between different but correlated datasets without any known correspondences. Based on the assumption that datasets of the same theme usually have similar manifold structures, GUMA is formulated into an explicit integer optimization problem considering the structure matching and preserving criteria, as well as the feature comparability of the corresponding points in the mutual embedding space. The main benefits of this model include: (1) simultaneous discovery and alignment of manifold structures; (2) fully unsupervised matching without any pre-specified correspondences; (3) efficient iterative alignment without computations in all permutation cases. Experimental results on dataset matching and real-world applications demonstrate the effectiveness and the practicability of our manifold alignment method.
BibTeX
@inproceedings{cui2014generalized,
  author = {Zhen Cui and Hong Chang and Shiguang Shan and Xilin Chen},
  title = {{Generalized Unsupervised Manifold Alignment}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure