* External authors




Wasserstein-based Graph Alignment

Hermina Petric Maretic*

Mireille El Gheche

Giovanni Chierchia*

Pascal Frossard*

* External authors

Transactions on Signal and Information Processing over Networks



We propose a novel method for comparing non-aligned graphs of different sizes, based on the Wasserstein distance between graph signal distributions induced by the respective graph Laplacian matrices. Specifically, we cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. By integrating optimal transport in our graph comparison framework, we generate both a structurally-meaningful graph distance, and a signal transportation plan that models the structure of graph data. The resulting alignment problem is solved with stochastic gradient descent, where we use a novel Dykstra operator to ensure that the solution is a one-to-many (soft) assignment matrix. We demonstrate the performance of our novel framework on graph alignment and graph classification, and we show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.

Related Publications

Distributed Graph Learning with Smooth Priors

ICASSP, 2022
Isabela Cunha Maia Nobre*, Mireille El Gheche, Pascal Frossard*

Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that lives on the graph node…

fGOT: Graph Distances based on Filters and Optimal Transport

AAAI, 2022
Hermina Petric Maretic*, Mireille El Gheche, Giovanni Chierchia*, Pascal Frossard*

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance. It is an opt…


Shape the Future of AI with Sony AI

We want to hear from those of you who have a strong desire
to shape the future of AI.