Asymmetric tree correlation testing for graph alignment
- Resource Type
- Conference
- Authors
- Maier, Jakob; Massoulie, Laurent
- Source
- 2023 IEEE Information Theory Workshop (ITW) Information Theory Workshop (ITW), 2023 IEEE. :503-508 Apr, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Signal Processing and Analysis
Correlation
Conferences
Testing
Information theory
graph alignment
sparse Erdős–Rényi graphs
tree correlation testing
- Language
- ISSN
- 2475-4218
We consider the partial graph alignment problem on two correlated sparse Erdős–Rényi graphs with differing edge or node densities. Exploiting that these graphs are locally tree-like, we come to consider a hypothesis testing problem on correlated Galton-Watson trees. To solve this problem, we give several equivalent conditions for the existence of likelihood-ratio tests with vanishing type-I-error and significant power. We then show that these same conditions enable the partial graph alignment algorithm MPAlign to succeed.This paper generalizes recent results from Ganassali L., Massoulié L. and Lelarge M. to the asymmetric edge and node density case. This extension allows for greater applicability of the results and resolves a special case of the subgraph isomorphism problem.