I suggest to look at the Gromov-Wasserstein distances (defined between two metric measure spaces). A great start is the paper "Gromov-Wasserstein distances and the metric approach to object matching" ( http://www.springerlink.com/content/d64702m3m1225613/) that also deals with some computational issues. As introduced in the paper, the approach does not incorporate weights on the edges yet (as far as I remember)...

I suggest to look at the Gromov-Wasserstein distances (defined between two metric measure spaces). A great start is the paper "Gromov-Wasserstein distances and the metric approach to object matching" ( https://link.springer.com/content/pdf/10.1007/s10208-011-9093-5.pdf) that also deals with some computational issues. As introduced in the paper, the approach does not incorporate weights on the edges yet (as far as I remember)...