A Wasserstein Graph Distance Based on Distributions of Probabilistic Node Embeddings

IEEE International Conference on Acoustics Speech and Signal Processing

Abstract

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 find- ings on synthetic data and real-world Functional Brain Connectivity networks shows promising performance compared to existing em- bedding methods.

Authors 6

1. Michael Scholkemper Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Computer Science,Germany

   Department of Computer Science, RWTH Aachen University, Germany

2. Damin Kühn Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Computer Science,Germany

   Department of Computer Science, RWTH Aachen University, Germany

3. Gerion Nabbefeld Aachen Department of Biology

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Biology,Germany

   Department of Biology, RWTH Aachen University, Germany

4. Simon Musall Aachen Department of Biology

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Biology,Germany

   Department of Biology, RWTH Aachen University, Germany

5. Björn M. Kampa Aachen Department of Biology

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Biology,Germany

   Department of Biology, RWTH Aachen University, Germany

6. Michael T. Schaub Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Department of Computer Science,Germany

   Department of Computer Science, RWTH Aachen University, Germany