* External authors




Distributed Graph Learning with Smooth Priors

Isabela Cunha Maia Nobre*

Mireille El Gheche

Pascal Frossard*

* External authors




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 nodes. However, there are settings where data cannot be collected easily or only with a non-negligible communication cost. In such cases, distributed processing appears as a natural solution, where the data stays mostly local and all processing is performed among neighbours nodes on the communication graph. We propose here a novel distributed graph learning algorithm, which permits to infer a graph from signal observations on the nodes under the assumption that the data is smooth on the target graph. We solve a distributed optimization problem with local projection constraints to infer a valid graph while limiting the communication costs. Our results show that the distributed approach has a lower communication cost than a centralised algorithm without compromising the accuracy in the inferred graph. It also scales better in communication costs with the increase of the network size, especially for sparse networks.

Related Publications

Wasserstein-based Graph Alignment

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

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…

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.