A similarity matrix is just a metric on a finite space. The standard metric on the space of all finite metric spaces is the [Gromov-Hausdorff metric][1].


  [1]: http://en.wikipedia.org/wiki/Gromov-Hausdorff_convergence#Gromov-Hausdorff_distance