Wasserstein-based Graph Alignment Article Swipe

View

Hermina Petric Maretić , Mireille El Gheche , Matthias Minder , Giovanni Chierchia , Pascal Frossard ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2003.06048

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 Topics

Line Graph

Computer Science

Algorithm

Theoretical Computer Science

Mathematics

Concepts

Voltage graph Graph Butterfly graph Null graph Line graph Computer science Strength of a graph Laplacian matrix Complement graph Algorithm Theoretical computer science Mathematics

Metadata

Type: preprint
Language: en
Landing Page: https://doi.org/10.48550/arxiv.2003.06048
OA Status: green
Cited By: 3
Related Works: 10
OpenAlex ID: https://openalex.org/W4287827140

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4287827140

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2003.06048

Digital Object Identifier
Title: Wasserstein-based Graph Alignment

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-03-12

Full publication date if available
Authors: Hermina Petric Maretić, Mireille El Gheche, Matthias Minder, Giovanni Chierchia, Pascal Frossard

List of authors in order
Landing page: https://doi.org/10.48550/arxiv.2003.06048

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://doi.org/10.48550/arxiv.2003.06048

Direct OA link when available
Concepts: Voltage graph, Graph, Butterfly graph, Null graph, Line graph, Computer science, Strength of a graph, Laplacian matrix, Complement graph, Algorithm, Theoretical computer science, Mathematics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 3

Total citation count in OpenAlex
Citations by year (recent): 2024: 1, 2022: 1, 2021: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4287827140
doi	https://doi.org/10.48550/arxiv.2003.06048
ids.doi	https://doi.org/10.48550/arxiv.2003.06048
ids.openalex	https://openalex.org/W4287827140
fwci
type	preprint
title	Wasserstein-based Graph Alignment
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11273
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9987000226974487
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Advanced Graph Neural Networks
topics[1].id	https://openalex.org/T10064
topics[1].field.id	https://openalex.org/fields/31
topics[1].field.display_name	Physics and Astronomy
topics[1].score	0.9965999722480774
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/3109
topics[1].subfield.display_name	Statistical and Nonlinear Physics
topics[1].display_name	Complex Network Analysis Techniques
topics[2].id	https://openalex.org/T10799
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9379000067710876
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1707
topics[2].subfield.display_name	Computer Vision and Pattern Recognition
topics[2].display_name	Data Visualization and Analytics
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C22149727
concepts[0].level	4
concepts[0].score	0.5417242050170898
concepts[0].wikidata	https://www.wikidata.org/wiki/Q7940747
concepts[0].display_name	Voltage graph
concepts[1].id	https://openalex.org/C132525143
concepts[1].level	2
concepts[1].score	0.5390578508377075
concepts[1].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[1].display_name	Graph
concepts[2].id	https://openalex.org/C18819970
concepts[2].level	5
concepts[2].score	0.5182176232337952
concepts[2].wikidata	https://www.wikidata.org/wiki/Q3035340
concepts[2].display_name	Butterfly graph
concepts[3].id	https://openalex.org/C17169500
concepts[3].level	5
concepts[3].score	0.5154250860214233
concepts[3].wikidata	https://www.wikidata.org/wiki/Q3033506
concepts[3].display_name	Null graph
concepts[4].id	https://openalex.org/C203776342
concepts[4].level	3
concepts[4].score	0.4964049458503723
concepts[4].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[4].display_name	Line graph
concepts[5].id	https://openalex.org/C41008148
concepts[5].level	0
concepts[5].score	0.4963987469673157
concepts[5].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[5].display_name	Computer science
concepts[6].id	https://openalex.org/C19332903
concepts[6].level	5
concepts[6].score	0.493144690990448
concepts[6].wikidata	https://www.wikidata.org/wiki/Q7623247
concepts[6].display_name	Strength of a graph
concepts[7].id	https://openalex.org/C115178988
concepts[7].level	3
concepts[7].score	0.46287137269973755
concepts[7].wikidata	https://www.wikidata.org/wiki/Q772067
concepts[7].display_name	Laplacian matrix
concepts[8].id	https://openalex.org/C168291704
concepts[8].level	5
concepts[8].score	0.4303275942802429
concepts[8].wikidata	https://www.wikidata.org/wiki/Q902252
concepts[8].display_name	Complement graph
concepts[9].id	https://openalex.org/C11413529
concepts[9].level	1
concepts[9].score	0.3608824610710144
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[9].display_name	Algorithm
concepts[10].id	https://openalex.org/C80444323
concepts[10].level	1
concepts[10].score	0.35518449544906616
concepts[10].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[10].display_name	Theoretical computer science
concepts[11].id	https://openalex.org/C33923547
concepts[11].level	0
concepts[11].score	0.33135104179382324
concepts[11].wikidata	https://www.wikidata.org/wiki/Q395
concepts[11].display_name	Mathematics
keywords[0].id	https://openalex.org/keywords/voltage-graph
keywords[0].score	0.5417242050170898
keywords[0].display_name	Voltage graph
keywords[1].id	https://openalex.org/keywords/graph
keywords[1].score	0.5390578508377075
keywords[1].display_name	Graph
keywords[2].id	https://openalex.org/keywords/butterfly-graph
keywords[2].score	0.5182176232337952
keywords[2].display_name	Butterfly graph
keywords[3].id	https://openalex.org/keywords/null-graph
keywords[3].score	0.5154250860214233
keywords[3].display_name	Null graph
keywords[4].id	https://openalex.org/keywords/line-graph
keywords[4].score	0.4964049458503723
keywords[4].display_name	Line graph
keywords[5].id	https://openalex.org/keywords/computer-science
keywords[5].score	0.4963987469673157
keywords[5].display_name	Computer science
keywords[6].id	https://openalex.org/keywords/strength-of-a-graph
keywords[6].score	0.493144690990448
keywords[6].display_name	Strength of a graph
keywords[7].id	https://openalex.org/keywords/laplacian-matrix
keywords[7].score	0.46287137269973755
keywords[7].display_name	Laplacian matrix
keywords[8].id	https://openalex.org/keywords/complement-graph
keywords[8].score	0.4303275942802429
keywords[8].display_name	Complement graph
keywords[9].id	https://openalex.org/keywords/algorithm
keywords[9].score	0.3608824610710144
keywords[9].display_name	Algorithm
keywords[10].id	https://openalex.org/keywords/theoretical-computer-science
keywords[10].score	0.35518449544906616
keywords[10].display_name	Theoretical computer science
keywords[11].id	https://openalex.org/keywords/mathematics
keywords[11].score	0.33135104179382324
keywords[11].display_name	Mathematics
language	en
locations[0].id	doi:10.48550/arxiv.2003.06048
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url
locations[0].version
locations[0].raw_type	article
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published
locations[0].raw_source_name
locations[0].landing_page_url	https://doi.org/10.48550/arxiv.2003.06048
indexed_in	datacite
authorships[0].author.id	https://openalex.org/A5065772016
authorships[0].author.orcid	https://orcid.org/0000-0001-7780-9244
authorships[0].author.display_name	Hermina Petric Maretić
authorships[0].author_position	first
authorships[0].raw_author_name	Maretic, Hermina Petric
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5103262517
authorships[1].author.orcid	https://orcid.org/0000-0003-2411-4064
authorships[1].author.display_name	Mireille El Gheche
authorships[1].author_position	middle
authorships[1].raw_author_name	Gheche, Mireille El
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5051729318
authorships[2].author.orcid
authorships[2].author.display_name	Matthias Minder
authorships[2].author_position	middle
authorships[2].raw_author_name	Minder, Matthias
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5057226360
authorships[3].author.orcid	https://orcid.org/0000-0001-5899-689X
authorships[3].author.display_name	Giovanni Chierchia
authorships[3].author_position	middle
authorships[3].raw_author_name	Chierchia, Giovanni
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5000947076
authorships[4].author.orcid	https://orcid.org/0000-0002-4010-714X
authorships[4].author.display_name	Pascal Frossard
authorships[4].author_position	last
authorships[4].raw_author_name	Frossard, Pascal
authorships[4].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.48550/arxiv.2003.06048
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Wasserstein-based Graph Alignment
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11273
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9987000226974487
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Advanced Graph Neural Networks
related_works	https://openalex.org/W2278094798, https://openalex.org/W2900680118, https://openalex.org/W2065459306, https://openalex.org/W2108781142, https://openalex.org/W2793949464, https://openalex.org/W2014355235, https://openalex.org/W3175246409, https://openalex.org/W2071056049, https://openalex.org/W3209476063, https://openalex.org/W2964146318
cited_by_count	3
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2022
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2021
counts_by_year[2].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.48550/arxiv.2003.06048
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url
best_oa_location.version
best_oa_location.raw_type	article
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://doi.org/10.48550/arxiv.2003.06048
primary_location.id	doi:10.48550/arxiv.2003.06048
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url
primary_location.version
primary_location.raw_type	article
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	https://doi.org/10.48550/arxiv.2003.06048
publication_date	2020-03-12
publication_year	2020
referenced_works_count	0
abstract_inverted_index.a	2, 31, 44, 71, 76, 100, 110
abstract_inverted_index.By	59
abstract_inverted_index.We	0, 115
abstract_inverted_index.at	42
abstract_inverted_index.by	22
abstract_inverted_index.in	46, 55, 63
abstract_inverted_index.is	91, 109
abstract_inverted_index.of	9, 84, 119, 147
abstract_inverted_index.on	13, 123
abstract_inverted_index.or	52
abstract_inverted_index.to	104, 136, 141
abstract_inverted_index.we	29, 68, 98, 130
abstract_inverted_index.The	87
abstract_inverted_index.and	75, 126, 129
abstract_inverted_index.for	5, 34, 145
abstract_inverted_index.new	32
abstract_inverted_index.one	51
abstract_inverted_index.our	64, 120, 133
abstract_inverted_index.the	14, 23, 35, 47, 56, 82, 107, 117, 142
abstract_inverted_index.use	99
abstract_inverted_index.aims	41
abstract_inverted_index.both	70
abstract_inverted_index.cast	30
abstract_inverted_index.each	146
abstract_inverted_index.more	53
abstract_inverted_index.node	45
abstract_inverted_index.plan	79
abstract_inverted_index.show	131
abstract_inverted_index.that	80, 106, 132
abstract_inverted_index.with	50, 93, 139
abstract_inverted_index.based	12
abstract_inverted_index.data.	86
abstract_inverted_index.graph	18, 25, 37, 49, 65, 73, 85, 124, 127
abstract_inverted_index.leads	135
abstract_inverted_index.nodes	54
abstract_inverted_index.novel	3, 101, 121
abstract_inverted_index.these	148
abstract_inverted_index.where	97
abstract_inverted_index.which	40
abstract_inverted_index.(soft)	112
abstract_inverted_index.ensure	105
abstract_inverted_index.graph.	58
abstract_inverted_index.graphs	8
abstract_inverted_index.larger	57
abstract_inverted_index.method	4, 134
abstract_inverted_index.models	81
abstract_inverted_index.signal	19, 77
abstract_inverted_index.sizes,	11
abstract_inverted_index.solved	92
abstract_inverted_index.tasks.	149
abstract_inverted_index.Dykstra	102
abstract_inverted_index.between	17
abstract_inverted_index.induced	21
abstract_inverted_index.matrix.	114
abstract_inverted_index.optimal	61
abstract_inverted_index.problem	90
abstract_inverted_index.propose	1
abstract_inverted_index.respect	140
abstract_inverted_index.smaller	48
abstract_inverted_index.descent,	96
abstract_inverted_index.distance	16
abstract_inverted_index.generate	69
abstract_inverted_index.gradient	95
abstract_inverted_index.matching	43
abstract_inverted_index.operator	103
abstract_inverted_index.problem,	39
abstract_inverted_index.solution	108
abstract_inverted_index.Laplacian	26
abstract_inverted_index.alignment	38, 89, 125
abstract_inverted_index.comparing	6
abstract_inverted_index.different	10
abstract_inverted_index.distance,	74
abstract_inverted_index.framework	122
abstract_inverted_index.matrices.	27
abstract_inverted_index.resulting	88
abstract_inverted_index.structure	83
abstract_inverted_index.transport	62
abstract_inverted_index.algorithms	144
abstract_inverted_index.assignment	113
abstract_inverted_index.comparison	66
abstract_inverted_index.framework,	67
abstract_inverted_index.respective	24
abstract_inverted_index.stochastic	94
abstract_inverted_index.Wasserstein	15
abstract_inverted_index.demonstrate	116
abstract_inverted_index.formulation	33
abstract_inverted_index.integrating	60
abstract_inverted_index.non-aligned	7
abstract_inverted_index.one-to-many	36, 111
abstract_inverted_index.performance	118
abstract_inverted_index.significant	137
abstract_inverted_index.improvements	138
abstract_inverted_index.Specifically,	28
abstract_inverted_index.distributions	20
abstract_inverted_index.transportation	78
abstract_inverted_index.classification,	128
abstract_inverted_index.state-of-the-art	143
abstract_inverted_index.structurally-meaningful	72
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
sustainable_development_goals[0].id	https://metadata.un.org/sdg/11
sustainable_development_goals[0].score	0.49000000953674316
sustainable_development_goals[0].display_name	Sustainable cities and communities
citation_normalized_percentile