  We introduce the tree distance, a new distance measure on graphs. The tree
distance can be computed in polynomial time with standard methods from convex
optimization. It is based on the notion of fractional isomorphism, a
characterization based on a natural system of linear equations whose integer
solutions correspond to graph isomorphism. By results of Tinhofer (1986, 1991)
and Dvo\v{r}\'ak (2010), two graphs G and H are fractionally isomorphic if and
only if, for every tree T, the number of homomorphisms from T to G equals the
corresponding number from T to H, which means that the tree distance of G and H
is zero. Our main result is that this correspondence between the equivalence
relations "fractional isomorphism" and "equal tree homomorphism densities" can
be extended to a correspondence between the associated distance measures. Our
result is inspired by a similar result due to Lov\'asz and Szegedy (2006) and
Borgs, Chayes, Lov\'asz, S\'os, and Vesztergombi (2008) that connects the cut
distance of graphs to their homomorphism densities (over all graphs), which is
a fundamental theorem in the theory of graph limits. We also introduce the path
distance of graphs and take the corresponding result of Dell, Grohe, and Rattan
(2018) for exact path homomorphism counts to an approximate level. Our results
answer an open question of Grohe (2020).
  We establish our main results by generalizing our definitions to graphons as
this allows us to apply techniques from functional analysis. We prove the
fairly general statement that, for every "reasonably" defined graphon
pseudometric, an exact correspondence to homomorphism densities can be turned
into an approximate one. We also provide an example of a distance measure that
violates this reasonableness condition. This incidentally answers an open
question of Greb\'ik and Rocha (2021).
