The feasibility of multi-graph alignment: a Bayesian approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911705704955904 |
|---|---|
| author | Vassaux, Louis Massoulié, Laurent |
| author_facet | Vassaux, Louis Massoulié, Laurent |
| contents | We establish thresholds for the feasibility of random multi-graph alignment in two models. In the Gaussian model, we demonstrate an "all-or-nothing" phenomenon: above a critical threshold, exact alignment is achievable with high probability, while below it, even partial alignment is statistically impossible. In the sparse Erdős-Rényi model, we rigorously identify a threshold below which no meaningful partial alignment is possible and conjecture that above this threshold, partial alignment can be achieved. To prove these results, we develop a general Bayesian estimation framework over metric spaces, which provides insight into a broader class of high-dimensional statistical problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_17142 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The feasibility of multi-graph alignment: a Bayesian approach Vassaux, Louis Massoulié, Laurent Statistics Theory Probability Machine Learning We establish thresholds for the feasibility of random multi-graph alignment in two models. In the Gaussian model, we demonstrate an "all-or-nothing" phenomenon: above a critical threshold, exact alignment is achievable with high probability, while below it, even partial alignment is statistically impossible. In the sparse Erdős-Rényi model, we rigorously identify a threshold below which no meaningful partial alignment is possible and conjecture that above this threshold, partial alignment can be achieved. To prove these results, we develop a general Bayesian estimation framework over metric spaces, which provides insight into a broader class of high-dimensional statistical problems. |
| title | The feasibility of multi-graph alignment: a Bayesian approach |
| topic | Statistics Theory Probability Machine Learning |
| url | https://arxiv.org/abs/2502.17142 |