IEEE Transactions on Signal and Information Processing over Networks, volume 8, pages 353-363
Wasserstein-Based Graph Alignment
Hermina Petric Maretic
1
,
Mireille El Gheche
2
,
Matthias Minder
1
,
Giovanni Chierchia
3
,
Pascal Frossard
1
2
Sony AI, Sony Europe B.V., Schlieren, Switzerland
|
3
Université Gustave Eiffel, LIGM (UMR 8049), ESIEE Paris, Noisy-le-Grand, CNRS, France
|
Publication type: Journal Article
Publication date: 2022-04-26
Q1
Q2
SJR: 1.320
CiteScore: 5.8
Impact factor: 3
ISSN: 2373776X, 23737778
Information Systems
Computer Networks and Communications
Signal Processing
Abstract
A novel method for comparing non-aligned graphs of various sizes is proposed, based on the Wasserstein distance between graph signal distributions induced by the respective graph Laplacian matrices. Specifically, a new formulation for the one-to-many graph alignment problem is casted, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. By incorporating optimal transport into our graph comparison framework, a structurally-meaningful graph distance, and a signal transportation plan that models the structure of graph data are generated. The resulting alignment problem is solved with stochastic gradient descent, where a novel Dykstra operator is used to ensure that the solution is a one-to-many (soft) assignment matrix. The performance of our novel framework is demonstrated on graph alignment, graph classification and graph signal transportation. Our method is shown to lead to significant improvements with respect to the state-of-the-art algorithms on each ofthese tasks.
Found
Found
Top-30
Journals
|
1
|
|
|
IEEE Transactions on Signal and Information Processing over Networks
1 publication, 33.33%
|
|
|
Journal of the Royal Statistical Society. Series B: Statistical Methodology
1 publication, 33.33%
|
|
|
1
|
Publishers
|
1
|
|
|
Institute of Electrical and Electronics Engineers (IEEE)
1 publication, 33.33%
|
|
|
Oxford University Press
1 publication, 33.33%
|
|
|
Cold Spring Harbor Laboratory
1 publication, 33.33%
|
|
|
1
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Maretic H. P. et al. Wasserstein-Based Graph Alignment // IEEE Transactions on Signal and Information Processing over Networks. 2022. Vol. 8. pp. 353-363.
GOST all authors (up to 50)
Copy
Maretic H. P., Gheche M. E., Minder M., Chierchia G., Frossard P. Wasserstein-Based Graph Alignment // IEEE Transactions on Signal and Information Processing over Networks. 2022. Vol. 8. pp. 353-363.
Cite this
RIS
Copy
TY - JOUR
DO - 10.1109/tsipn.2022.3169632
UR - https://doi.org/10.1109/tsipn.2022.3169632
TI - Wasserstein-Based Graph Alignment
T2 - IEEE Transactions on Signal and Information Processing over Networks
AU - Maretic, Hermina Petric
AU - Gheche, Mireille El
AU - Minder, Matthias
AU - Chierchia, Giovanni
AU - Frossard, Pascal
PY - 2022
DA - 2022/04/26
PB - Institute of Electrical and Electronics Engineers (IEEE)
SP - 353-363
VL - 8
SN - 2373-776X
SN - 2373-7778
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2022_Maretic,
author = {Hermina Petric Maretic and Mireille El Gheche and Matthias Minder and Giovanni Chierchia and Pascal Frossard},
title = {Wasserstein-Based Graph Alignment},
journal = {IEEE Transactions on Signal and Information Processing over Networks},
year = {2022},
volume = {8},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
month = {apr},
url = {https://doi.org/10.1109/tsipn.2022.3169632},
pages = {353--363},
doi = {10.1109/tsipn.2022.3169632}
}