Asymmetric tree correlation testing for graph alignment

Jakob Maier (1, 2, 3) , Laurent Massoulié (1, 2, 3, 4)

1 DI-ENS - Département d'informatique - ENS Paris
2 DYOGENE - Dynamics of Geometric Networks
3 PSL - Université Paris Sciences et Lettres
4 MSR - INRIA - Microsoft Research - Inria Joint Centre

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.

Mots clés: Graph alignment; Sparse Erdős-Rényi graphs; Tree correlation testing

Domaines: Théorie de l'information et codage [math.IT]; Probabilités [math.PR]; Machine Learning [stat.ML]

Jakob Maier, Laurent Massoulié. Asymmetric tree correlation testing for graph alignment. 2023 IEEE Information Theory Workshop (ITW), Apr 2024, Saint-Malo, France. pp.503-508, ⟨10.1109/ITW55543.2023.10161653⟩. ⟨hal-04435165⟩