Gromov-Hausdorff distance between weighted tree graphs

Question

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.

Answer 1

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.