2
$\begingroup$

I'm always wondering is there an universal (dis)similarity measure between two structures (let's say between two undirected simple graphs)? I mean, not "the measure with universal parameter that we can adapt to our needs", but rather "a measure without any parameters, magical, a measure that reads our mind(s)".

The normalized compression distance(NCD) seems to be a good candidate for such universal measure. But it have at least two problems:

  1. NCD is just an approximation of the information distance (ID). Although it should be noted that ID cannot be computed at all.

  2. NCD (and ID) compares not the objects themselves, but their representations – we must transform our objects to strings. And sometimes this transformation, $\text{Object} ↦ \text{String}$, can be very tricky, for example:

    Take two graphs $G_1$ and $G_2$. Of course, we can take their adjacency matrices: $A_1$ and $A_2$; and NCD will tell us how these matrices are similar. But isomorphic graphs can have very different adjacency matrices... Therefore, if we want to capture the graph isomorphism by NCD, we must use canonical labeling instead of adjacency matrices.

So, how can we develop an universal (dis)similarity measure between two structures? How can such a measure guess the most natural\universal isomorphism between them?

$\endgroup$
1
  • 1
    $\begingroup$ a universal distance measure will be uncomputable....(it seems also a somewhat philosophical issue: whether we really compare objects or their representations, because true representations themselves are nothing but objects isomorphic to the original objects....?) $\endgroup$
    – Suvrit
    Feb 3, 2014 at 0:20

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.