

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

## 2.1 Similarity Graphs

To gain more insight into the underlying structure of a collection of comparisons C, we can represent C as a directed graph over X
2. Each vertex in the graph corresponds to a pair (i, j) ∈ X 2, and an edge from (i, j) to (**k, ℓ**) corresponds to a similarity measurement (**i, j, k, ℓ**) (see Figure 2).

Interpreting C as a graph will allow us to infer properties of *global* (graphical) structure of C. In particular, two facts become immediately apparent:
1. If C contains cycles, then there exists no embedding which can satisfy C. 2. If C is acyclic, any embedding that satisfies the transitive reduction C
min also satisfies C.

The first fact implies that no algorithm can produce an embedding which satisfies all measurements if the graph is cyclic. In fact, the converse of this statement is also true: if C is acyclic, then an embedding exists in which all similarity measurements are preserved (see Appendix A). If C is cyclic, however, by analyzing the graph, it is possible to identify an "unlearnable" subset of C which must be violated by any embedding.

Similarly, the second fact exploits the transitive nature of distance comparisons. In the example depicted in Figure 2, any g that satisfies (**j, k, j, ℓ**) and (**j, ℓ, i, k**) must also satisfy (**j, k, i, k**). In effect, the constraint (**j, k, i, k**) is redundant, and may also be safely omitted from C.

These two observations allude to two desirable properties in C for embedding methods: *transitivity* and *anti-symmetry*. Together with irreflexivity, these fit the defining characteristics of a partial order. Due to subjectivity and inter-labeler disagreement, however, most collections of relative comparisons will not define a partial order. Some graph processing, presented next, based on an approximate maximum acyclic subgraph algorithm, can reduce them to a partial order.

## 2.2 Graph Simplification

Because a set of similarity measurements C containing cycles cannot be embedded in any Euclidean space, C is inherently inconsistent. Cycles in C therefore constitute a form of *label noise*. As noted by Angelova (2004), label noise can have adverse effects on both model complexity and generalization. This problem can be mitigated by detecting and pruning noisy (confusing) examples, and training on a reduced, but certifiably "clean" set (Angelova et al., 2005; Vezhnevets and Barinova, 2007).

Unlike most settings, where the noise process affects each label independently - *e.g.*, random classification noise (Angluin and Laird, 1988) - the graphical structure of interrelated relative comparisons can be exploited to detect and prune inconsistent measurements. By eliminating similarity measurements which cannot be realized by any embedding, the optimization procedure can be carried out more efficiently and reliably on a reduced constraint set.