Structure Preserving Embedding

by Blake Shaw and Tony Jebra

This paper proposes the concept structure preservaing embedding: given an algorithm to construct a graph \mathcal{G}, it would yield the same graph as the given affinity matrix A_0 with the computed Gram matrix K.

There are two kind of algorithms to construct the graph:

• kNN and \epsilon-ball; we can find linear constraints for K which ensure the nearby samples are nearer than other samples (the constrains are at most O(N^2)).
• Maximum weight subgraph, b-matching subgraph, maximum weight spanning tree. The number of constrains might be exponential in N.

The objective is \mathrm{tr}(K A), subject to \mathrm{tr}(K) \leq 1 and K \succeq 0. The authors prove that under these conditions, the Gram matrix has rank 1. The embedding is calculated with constraints with a common slack variable \xi, which allows possible violation of the constraints. Then the resulted embedding might has more dimensions.

For the first category of constraints, SDP can be directly applied while for the second category, we first use SDP without constraints and then add most violated constraints one-by-one, each time the model is updated with SDP until convergence is observed.

This technique is best regarded as a visualization technique (for graphs) though it could also be used in dimensionality reduction tasks for classification. The experiments show with SP contraints added to MUV and MVE, the classification rate improves.