The graph alignment problem: fundamental limits and efficient algorithms
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917644761825280 |
|---|---|
| author | Ganassali, Luca |
| author_facet | Ganassali, Luca |
| contents | This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The graph alignment problem: fundamental limits and efficient algorithms Ganassali, Luca Data Structures and Algorithms Machine Learning Probability This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail. |
| title | The graph alignment problem: fundamental limits and efficient algorithms |
| topic | Data Structures and Algorithms Machine Learning Probability |
| url | https://arxiv.org/abs/2404.12418 |