Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing
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_ | 1866917336760451072 |
|---|---|
| author | Maier, Jakob Massoulié, Laurent |
| author_facet | Maier, Jakob Massoulié, Laurent |
| contents | Graph alignment - identifying node correspondences between two graphs - is a fundamental problem with applications in network analysis, biology, and privacy research. While substantial progress has been made in aligning correlated Erdős-Rényi graphs under symmetric settings, real-world networks often exhibit asymmetry in both node numbers and edge densities. In this work, we introduce a novel framework for asymmetric correlated Erdős-Rényi graphs, generalizing existing models to account for these asymmetries. We conduct a rigorous theoretical analysis of graph alignment in the sparse regime, where local neighborhoods exhibit tree-like structures. Our approach leverages tree correlation testing as the central tool in our polynomial-time algorithm, MPAlign, which achieves one-sided partial alignment under certain conditions.
A key contribution of our work is characterizing these conditions under which asymmetric tree correlation testing is feasible: If two correlated graphs $G$ and $G'$ have average degrees $λs$ and $λs'$ respectively, where $λ$ is their common density and $s,s'$ are marginal correlation parameters, their tree neighborhoods can be aligned if $ss' > α$, where $α$ denotes Otter's constant and $λ$ is supposed large enough. The feasibility of this tree comparison problem undergoes a sharp phase transition since $ss' \leq α$ implies its impossibility. These new results on tree correlation testing allow us to solve a class of random subgraph isomorphism problems, resolving an open problem in the field. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02299 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing Maier, Jakob Massoulié, Laurent Information Theory Data Structures and Algorithms Graph alignment - identifying node correspondences between two graphs - is a fundamental problem with applications in network analysis, biology, and privacy research. While substantial progress has been made in aligning correlated Erdős-Rényi graphs under symmetric settings, real-world networks often exhibit asymmetry in both node numbers and edge densities. In this work, we introduce a novel framework for asymmetric correlated Erdős-Rényi graphs, generalizing existing models to account for these asymmetries. We conduct a rigorous theoretical analysis of graph alignment in the sparse regime, where local neighborhoods exhibit tree-like structures. Our approach leverages tree correlation testing as the central tool in our polynomial-time algorithm, MPAlign, which achieves one-sided partial alignment under certain conditions. A key contribution of our work is characterizing these conditions under which asymmetric tree correlation testing is feasible: If two correlated graphs $G$ and $G'$ have average degrees $λs$ and $λs'$ respectively, where $λ$ is their common density and $s,s'$ are marginal correlation parameters, their tree neighborhoods can be aligned if $ss' > α$, where $α$ denotes Otter's constant and $λ$ is supposed large enough. The feasibility of this tree comparison problem undergoes a sharp phase transition since $ss' \leq α$ implies its impossibility. These new results on tree correlation testing allow us to solve a class of random subgraph isomorphism problems, resolving an open problem in the field. |
| title | Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.02299 |