  Distance measures between graphs are important primitives for a variety of
learning tasks. In this work, we describe an unsupervised, optimal transport
based approach to define a distance between graphs. Our idea is to derive
representations of graphs as Gaussian mixture models, fitted to distributions
of sampled node embeddings over the same space. The Wasserstein distance
between these Gaussian mixture distributions then yields an interpretable and
easily computable distance measure, which can further be tailored for the
comparison at hand by choosing appropriate embeddings. We propose two
embeddings for this framework and show that under certain assumptions about the
shape of the resulting Gaussian mixture components, further computational
improvements of this Wasserstein distance can be achieved. An empirical
validation of our findings on synthetic data and real-world Functional Brain
Connectivity networks shows promising performance compared to existing
embedding methods.
