Timezone: »
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.
Author Information
Hermina Petric Maretic (EPFL)
Mireille El Gheche (EPFL)
Giovanni Chierchia (ESIEE Paris)
Pascal Frossard (EPFL)
More from the Same Authors
-
2021 : Predicting future myocardial infarction from angiographies with deep learning »
Dorina Thanou · Emmanuel Abbe · Pascal Frossard -
2021 Poster: What can linearized neural networks actually say about generalization? »
Guillermo Ortiz-Jimenez · Seyed-Mohsen Moosavi-Dezfooli · Pascal Frossard -
2020 Poster: Building powerful and equivariant graph neural networks with structural message-passing »
ClĂ©ment Vignac · Andreas Loukas · Pascal Frossard -
2020 Poster: Neural Anisotropy Directions »
Guillermo Ortiz-Jimenez · Apostolos Modas · Seyed-Mohsen Moosavi · Pascal Frossard -
2020 Poster: Hold me tight! Influence of discriminative features on deep network boundaries »
Guillermo Ortiz-Jimenez · Apostolos Modas · Seyed-Mohsen Moosavi · Pascal Frossard -
2019 Poster: Ultrametric Fitting by Gradient Descent »
Giovanni Chierchia · Benjamin Perret -
2016 Poster: Robustness of classifiers: from adversarial to random noise »
Alhussein Fawzi · Seyed-Mohsen Moosavi-Dezfooli · Pascal Frossard