
## Appendix C. Relationship To Auc

In this appendix, we formalize the connection between partial orders over distances and query-byexample ranking. Recall that Algorithm 2 minimizes the loss 1/|C|PC
ξ**ijkℓ**, where each ξ**ijkℓ** ≥ 0 is a slack variable associated with a margin constraint

$$d(i,j)+1\leq d(k,\ell)+\xi_{i j k\ell}.$$

As noted by Schultz and Joachims (2004), the fraction of relative comparisons satisfied by an embedding g is closely related to the area under the receiver operating characteristic curve (AUC).

To make this connection precise, consider the following information retrieval problem. For each point xi ∈ X , we are given a partition of **X \ {**i}:

$$\begin{array}{l}{{\mathcal{X}_{i}^{+}=\{x_{j}\;:\;x_{j}\in\mathcal{X}\;\mathrm{relevant~for}\;x_{i}\},\;\mathrm{and}}}\\ {{\mathcal{X}_{i}^{-}=\{x_{k}\;:\;x_{k}\in\mathcal{X}\;\mathrm{ irrelevant~for}\;x_{i}\}.}}\end{array}$$

If we embed each xi ∈ X into a Euclidean space, we can then rank the rest of the data **X \ {**xi} by increasing distance from xi. Truncating this ranked list at the top τ elements (*i.e.*, closest τ points to xi) will return a certain fraction of relevant points (true positives), and irrelevant points (false positives). Averaging over all values of τ defines the familiar AUC score, which can be compactly expressed as:

$$\mathrm{AUC}(x_{i}|g)={\frac{1}{|\mathcal{X}_{i}^{+}|\cdot|\mathcal{X}_{i}^{-}|}}\sum_{(x_{j},x_{k})\in\mathcal{X}_{i}^{+}\times\mathcal{X}_{i}^{-}}\mathbf{1}\left[\|g(x_{i})-g(x_{j})\|<\|g(x_{i})-g(x_{k})\|\right].$$

Intuitively, AUC can be interpreted as an average over all pairs (xj , xk) ∈ X +
i × X −
iof the number of times a xi was mapped closer to a relevant point xj than an irrelevant point xk. This in turn can be conveniently expressed by a set of relative comparisons for each xi ∈ X :

$$\forall(x_{j},x_{k})\in{\mathcal{X}}_{i}^{+}\times{\mathcal{X}}_{i}^{-}\;:\;(i,j,i,k).$$

An embedding which satisfies a complete set of constraints of this form will receive an AUC score of 1, since every relevant point must be closer to xithan every irrelevant point.

Now, returning to the more general setting, we do not assume binary relevance scores or complete observations of relevance for all pairs of points. However, we can define the generalized AUC score (GAUC) as simply the average number of correctly ordered pairs (equivalently, satisfied constraints) given a set of relative comparisons:

$$\text{GAUC}(g)=\frac{1}{|\mathcal{C}|}\sum_{(i,j,k,\ell)\in\mathcal{C}}\mathds{1}\left[\|g(x_{i})-g(x_{j})\|<\|g(x_{k})-g(x_{\ell})\|\right].\tag{18}$$

Like AUC, GAUC is bounded between 0 and 1, and the two scores coincide exactly in the previously described ranking problem. A corresponding loss function can be defined by reversing the order of the inequality, *i.e.*,

$$L_{\mathrm{GAUC}}(g)=\frac{1}{|C|}\sum_{(i,j,k,\ell)\in C}\mathds{1}\left[\|g(x_{i})-g(x_{j})\|\geq\|g(x_{k})-g(x_{\ell})\|\right].$$
