Studio di algoritmi message-passing per il problema dell'allineamento dei grafi

The graph alignment problem is an optimization problem that aims at recovering a permutation between the vertices of two graphs in such a way that their edges result to be maximally aligned. In its most general definition this belongs to the class of NP-hard computational problems, however there are some circumstances in which a solution is possible. Those have been studied in recent literature and in some cases polynomial-time algorithms have been proposed for them. In the present work we analyze the alignment of correlated Erdős-Rényi random graphs in the sparse regime, that is when the average degree is finite λ=O(1) while the size of the graphs is diverging n→∞. In this setting it has been proven that it is possible only a partial recovery of the permutation between the vertices’ sets, that is only a finite fraction of vertices can be correctly matched. In order to achieve this we started from the algorithm proposed by [1], which approaches the problem exploiting the local convergence of Erdős-Rényi graphs to trees and recovering the permutation thanks to subtree-similarity. Simulations performed with such algorithm showed that it works pretty well for the partial recovery task, however it suffers from a very high computational cost when increasing λ and thus limits the study of the problem to only small average degree values. For this reason, in the present work we have studied a variant of that algorithm to overcome this limitation. The idea for it has been opened up by a rewriting of the problem presented by [2], which suggested the possibility to introduce an approximation in the algorithm. Hence, we wrote the analytical form of this new version and implemented the respective code, we checked the coherence of the new algorithm’s results with the older ones and we performed several simulations with it. This led to a computational cost way cheaper at the expense of only a slight loss of performances, thus we have been able to explore the region at higher λ that was not previously accessible in reasonable computational time. 1. Piccioli G, Semerjian G, Sicuro G, Zdeborová L. Aligning random graphs with a sub-tree similarity message-passing algorithm. J Stat Mech. 2022 Jun 1;2022(6):063401. 2. Ganassali L, Massoulié L, Semerjian G. Statistical limits of correlation detection in trees [Internet]. arXiv; 2022 [cited 2023 Jun 20]. Available from: http://arxiv.org/abs/2209.13723