Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913482000039936 |
|---|---|
| author | Gu, Jinhao García-Fernández, Ángel F. Firth, Robert E. Svensson, Lennart |
| author_facet | Gu, Jinhao García-Fernández, Ángel F. Firth, Robert E. Svensson, Lennart |
| contents | This paper proposes a metric to measure the dissimilarity between graphs that may have a different number of nodes. The proposed metric extends the generalised optimal subpattern assignment (GOSPA) metric, which is a metric for sets, to graphs. The proposed graph GOSPA metric includes costs associated with node attribute errors for properly assigned nodes, missed and false nodes and edge mismatches between graphs. The computation of this metric is based on finding the optimal assignments between nodes in the two graphs, with the possibility of leaving some of the nodes unassigned. We also propose a lower bound for the metric, which is also a metric for graphs and is computable in polynomial time using linear programming. The metric is first derived for undirected unweighted graphs and it is then extended to directed and weighted graphs. The properties of the metric are demonstrated via simulated and empirical datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07596 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes Gu, Jinhao García-Fernández, Ángel F. Firth, Robert E. Svensson, Lennart Social and Information Networks Machine Learning Signal Processing This paper proposes a metric to measure the dissimilarity between graphs that may have a different number of nodes. The proposed metric extends the generalised optimal subpattern assignment (GOSPA) metric, which is a metric for sets, to graphs. The proposed graph GOSPA metric includes costs associated with node attribute errors for properly assigned nodes, missed and false nodes and edge mismatches between graphs. The computation of this metric is based on finding the optimal assignments between nodes in the two graphs, with the possibility of leaving some of the nodes unassigned. We also propose a lower bound for the metric, which is also a metric for graphs and is computable in polynomial time using linear programming. The metric is first derived for undirected unweighted graphs and it is then extended to directed and weighted graphs. The properties of the metric are demonstrated via simulated and empirical datasets. |
| title | Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes |
| topic | Social and Information Networks Machine Learning Signal Processing |
| url | https://arxiv.org/abs/2311.07596 |