# Best way to evaluate ranking when one only has pairwise distances?

Let's say I have a strict ranked set of samples.

I only have a similarity measure $$s$$. I want to evaluate how good this similarity measure is at ranking the examples.

One approach would be to use a simplified version of d-ranking with only 3 points at a time instead of 4.

For example, I sample instance A, B, and C. Without loss of generality, A < B < C in my ranking. If s(A, B) > s(A, C) and s(B, C) > s(A, C), then the accuracy is one on this triplet. And I repeat.

Is there a better way to evaluate how good a similarity measure is, against a ranked set of samples?

One alternative would be to find the instances with the furthest distance, then use Dijkstra's algorithm to find the minimum shortest path, and then compute a spearman over that ranking. I don't love this because it assumes that the distance measure is additive. Alternately, I could greedily create edges between the nearest points, but enforce I create a path, i.e. no node has more that 2 edges. I still don't love this because it seems to do fewer evaluations than the original triplet-accuracy d-ranking method I propose.

Another alternative that I am leaning towards is this:

• Pick the lowest rank item in the set. Order all the instances by distance from lowest. Compute spearman.
• As before, but with the highest rank item in the set. Compute spearman.

Slightly more fancy:

• For every point:
• The difficulty is to know whether other points are above or below it. So pick the orientation based upon the other point's distance from min and max points.
• Do spearman as before but over all the points.