The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911809818066944 |
|---|---|
| author | Fishkind, Donniell E. Parker, Felix Sawczuk, Hamilton Meng, Lingyao Bridgeford, Eric Athreya, Avanti Priebe, Carey E. Lyzinski, Vince |
| author_facet | Fishkind, Donniell E. Parker, Felix Sawczuk, Hamilton Meng, Lingyao Bridgeford, Eric Athreya, Avanti Priebe, Carey E. Lyzinski, Vince |
| contents | The alignment strength of a graph matching is a quantity that gives the practitioner a measure of the correlation of the two graphs, and it can also give the practitioner a sense for whether the graph matching algorithm found the true matching. Unfortunately, when a graph matching algorithm fails to find the truth because of weak signal, there may be "phantom alignment strength" from meaningless matchings that, by random noise, have fewer disagreements than average (sometimes substantially fewer); this alignment strength may give the misleading appearance of significance. A practitioner needs to know what level of alignment strength may be phantom alignment strength and what level indicates that the graph matching algorithm obtained the true matching and is a meaningful measure of the graph correlation. The {\it Phantom Alignment Strength Conjecture} introduced here provides a principled and practical means to approach this issue. We provide empirical evidence for the conjecture, and explore its consequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_00624 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match Fishkind, Donniell E. Parker, Felix Sawczuk, Hamilton Meng, Lingyao Bridgeford, Eric Athreya, Avanti Priebe, Carey E. Lyzinski, Vince Optimization and Control The alignment strength of a graph matching is a quantity that gives the practitioner a measure of the correlation of the two graphs, and it can also give the practitioner a sense for whether the graph matching algorithm found the true matching. Unfortunately, when a graph matching algorithm fails to find the truth because of weak signal, there may be "phantom alignment strength" from meaningless matchings that, by random noise, have fewer disagreements than average (sometimes substantially fewer); this alignment strength may give the misleading appearance of significance. A practitioner needs to know what level of alignment strength may be phantom alignment strength and what level indicates that the graph matching algorithm obtained the true matching and is a meaningful measure of the graph correlation. The {\it Phantom Alignment Strength Conjecture} introduced here provides a principled and practical means to approach this issue. We provide empirical evidence for the conjecture, and explore its consequences. |
| title | The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2103.00624 |