Visualizing pairwise similarity via semidefinite programming

Amir Globerson, Sam T. RoweisAISTATS 2007 · OpenReview

Abstract

We introduce a novel learning algorithm for binary pairwise similarity measurements on a set of objects. The algorithm delivers an embedding of the objects into a vector representation space that captures the intrinsic geometric structure of the data.

Introduction

In many domains, such as bioinformatics or social network analysis, researchers lack precise numerical distances between objects. Instead, they may only have access to sparse binary labels: whether two objects are "similar" or "dissimilar." Traditional visualization techniques like Multidimensional Scaling (MDS) or manifold learning methods (e.g., Isomap) typically require real-valued distance matrices or local neighborhood information, making them unsuitable for purely binary constraints.

This paper addresses the challenge of creating a vector-space embedding when the only available input is a set of binary constraints: "Object A is like B, but not like C." The authors present Pairwise Semidefinite Embedding (PSDE), a method that turns these simple labels into meaningful low-dimensional visualizations by framing the problem as a convex semidefinite program (SDP).

Methodology

PSDE works by "unfolding" the data—maximizing the spread of the embedding while respecting the relative proximity dictated by the labels.

Geometric Constraints

For every object $i$, the algorithm identifies a radius $b_i$. It requires that all objects labeled "similar" to $i$ fall within this radius in the embedding space, while all objects labeled "dissimilar" fall outside. This relative ranking ensures that similar points are closer to each other than dissimilar ones without requiring absolute distance measurements.

Geometric constraints in PSDE: similar points ($s_{ij}=+1$) are pulled within a radius $b_i$, while dissimilar points ($s_{ik}=-1$) are pushed outside.

Optimization via Semidefinite Programming

To avoid the trivial solution of collapsing all points to a single location, the algorithm maximizes the variance of the embedding. By representing the embedding through a Gram matrix (a matrix of dot products) and relaxing rank constraints, the authors transform the non-convex distance problem into a convex SDP. This ensures a global optimum, avoiding the local minima issues common in other manifold learning techniques.

The authors also introduce KPSDE, a kernelized version that allows for a functional mapping. This enables the model to handle out-of-sample data, placing new, unseen points into the learned visualization space correctly.

Experiments and Results

The algorithm was tested on both synthetic structures and real-world image datasets to demonstrate its ability to recover topological shapes from connectivity data alone.

Manifold Recovery

The most significant result was achieved on the NORB Dataset, which contains images of toy airplanes at various azimuths and elevations. Using only binary similarity labels, the algorithm successfully recovered the underlying "camera manifold."

Recovery of the NORB airplane manifold. The algorithm reconstructs a 3D cylinder representing azimuth and elevation from binary similarity labels.

As shown in the visualization, the data was unfolded into a nearly perfect cylinder, capturing the circular nature of the azimuth and the linear nature of the elevation. In out-of-sample tests using KPSDE, the model correctly placed unseen images on this 3D manifold, capturing 94% of the variance in the top three dimensions. Even though the algorithm is allowed to use many dimensions, the resulting Gram matrices typically had a very low "effective rank," confirming that the unfolding objective successfully finds low-dimensional representations.

Discussion and Conclusion

A key insight of this work is that maximizing variance subject to similarity constraints naturally favors low-dimensional solutions. The relative ranking of points provides sufficient information to reconstruct complex 3D geometries.

However, the approach faces computational challenges. Standard SDP solvers scale poorly ($O(n^2)$ constraints), making it difficult to process very large datasets. Future work may involve more formal constraint pruning methods or extending the model to handle ordered similarities (e.g., "A is more like B than C") to capture even richer structural information.

Summary updated

Abstract

We introduce a novel learning algorithm for binary pairwise similarity measurements on a set of objects. The algorithm delivers an embedding of the objects into a vector representation space that s...
BibTeX
@inproceedings{globerson2007visualizing,
  author = {Amir Globerson and Sam T. Roweis},
  title = {{Visualizing pairwise similarity via semidefinite programming}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=CJC6nIFZlwp},
}
Figure