Ideally, when eliminating edges from the graph, we would like to retain as much information as possible. Unfortunately, this is equivalent to the *maximum acyclic subgraph* problem, which is NP-Complete (Garey and Johnson, 1979). A 1/2-approximate solution can be achieved by a simple greedy algorithm (Algorithm 1) (Berger and Shor, 1990). Algorithm 1 Approximate maximum acyclic subgraph Input: Directed graph G = (**V, E**)
Output: Acyclic graph G′
E′ ← ∅
for each (**u, v**) ∈ E in random order do if E′ ∪ {(**u, v**)} is acyclic **then**
E′ ← E′ ∪ {(**u, v**)}
end if end for G′ ← (**V, E**′)
Once a consistent subset of similarity measurements has been produced, it can be simplified further by pruning redundancies. In the graph view of similarity measurements, redundancies can be easily removed by computing the transitive reduction of the graph (Aho et al., 1972).

By filtering the constraint set for consistency, we ensure that embedding algorithms are not learning from spurious information. Additionally, pruning the constraint set by transitive reduction focuses embedding algorithms on the most important core set of constraints while reducing overhead due to redundant information.

## 3. Partial Order Embedding

Now that we have developed a language for expressing similarity between items, we are ready to formulate the embedding problem. In this section, we develop an algorithm that learns a representation of data consistent with a collection of relative similarity measurements, and allows to map unseen data into the learned similarity space after learning. In order to accomplish this, we will assume a feature representation for X . By parameterizing the embedding function g in terms of the feature representation, we will be able to apply g to any point in the feature space, thereby generalizing to data outside of the training set.

## 3.1 Linear Projection

To start, we assume that the data originally lies in some Euclidean space, *i.e.*, X ⊂ R
D. There are of course many ways to define an embedding function g : R
D → R
d. Here, we will restrict attention to embeddings parameterized by a linear projection matrix M, so that for a vector x ∈ R
D,
g(x)
.= Mx.

Collecting the vector representations of the training set as columns of a matrix X ∈ R
D×n, the inner product matrix of the embedded points can be characterized as

$$A=X^{\mathsf{T}}M^{\mathsf{T}}M X.$$
A = XTMTMX. (2)
7