I would like to measure the similarity between a pair of weighted tree graphs. According to this post, this can be done by regarding the trees as metric spaces and then applying the Gromov-Hausdorff distance.

Given two metric spaces, $(A, d_{A})$ and $(B, d_{B})$, the Gromov-Hausdorff distance is defined:

$$d_{GH}(A,B)=\inf\limits_{f:A\rightarrow M\\ g:B\rightarrow M}d_{H}(f(A), g(B))$$

where $f:A\rightarrow M$ and $g:B\rightarrow M$ are isometric embeddings of $A$ and $B$ into some metric space $M$, respectively. My question is: if the infimum is taken over all possible such embeddings, and there is an infinity of such embeddings, then how can one compute this distance?

Moreover, in this paper the authors took the approach described above to compare between brain networks and defined $f:A\rightarrow B$ and $g:B\rightarrow A$. That is, no common metric space $M$ is involved. What allows to discard M when using the Gromov-Hausdorff metrics?

Thanks a lot for your time.


I would direct you to Theorem 7.3.25 of the book "A Course in Metric Geometry" by Burago-Burago-Ivanov.

Roughly speaking, the Gromov-Hausdorff distance between two compact metric spaces can be computed by looking for the infimum of all $\epsilon>0$ such that there is a correspondence between $X$ and $Y$ that changes distances by an additive error of at most $\epsilon$. See the above reference for a more precise statement.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.