Compare between similar and dissimilar couples of instances
You can compute a similarity score between each couple of instances (diff in features) and then you can check if the distribution of the difference for each group (similar and dissimilar) is significantly different using the Kolmogorov-Smirnov test.