Reverse engineering a distance metric from the output of a k-NN
Interesting question. If you supposed that the distance metric was some common one, of course you could just try all the common ones and see what is consistent with the nearest neighbors it returns. 

I can't think of a way to learn this reliably, because you don't have any info about the actual distances. Maybe treat all nearest-neighbor pairs as having 'small' distance and the rest 'large' and training a deep model that tries to learn to predict it across pairs of points. Whatever it comes up with as a metric would approximate it.