GOT: An Optimal Transport framework for Graph comparison

Abstract

We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an explicit expression of the Wasserstein distance between graph signal distributions in terms of the graph Laplacian matrices. This leads to a structurally meaningful measure for comparing graphs, which is able to take into account the global structure of graphs, while most other measures merely observe local changes independently. Our measure is then used for formulating a new graph alignment problem, whose objective is to estimate the permutation that minimizes the distance between two graphs. We further propose an efficient stochastic algorithm based on Bayesian exploration to accommodate for the non-convexity of the graph alignment problem. We finally demonstrate the performance of our novel framework on different tasks like graph alignment, graph classification and graph signal prediction, and we show that our method leads to significant improvement with respect to the-state-of-art algorithms.

arXiv comment33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada

References in corpus (10)

• Emergence of scaling in random networks
• On the Convergence of Adam and Beyond
• Learning graphs from data: A signal representation perspective
• NetLSD: Hearing the Shape of a Graph
• Implicit Reparameterization Gradients
• Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance
• Learning Permutations with Sinkhorn Policy Gradient
• Spectral distances on graphs
• DS++: A flexible, scalable and provably tight relaxation for matching problems
• Variational Adaptive-Newton Method for Explorative Learning

Cited by in corpus (12)

• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space
• COPT: Coordinated Optimal Transport for Graph Sketching
• Wasserstein Embedding for Graph Learning
• DiffPaSS -- High-performance differentiable pairing of protein sequences using soft scores
• Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
• A Wasserstein Graph Distance Based on Distributions of Probabilistic Node Embeddings
• Optimal transport distances for directed, weighted graphs: a case study with cell-cell communication networks
• Online Graph Dictionary Learning
• State-Driven Dynamic Graphon Model
• Graph embedding using multi-layer adjacent point merging model