The problem of aligning ErdÅ's-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message-passing algorithm devised to solve the inference problem of partially recovering the hidden permutation, in the sparse regime with constant average degrees. We perform extensive numerical simulations to determine the range of parameters in which this algorithm achieves partial recovery. We also introduce a generalized ensemble of correlated random graphs with prescribed degree distributions, and extend the algorithm to this case.

Aligning random graphs with a sub-tree similarity message-passing algorithm / Piccioli G.; Semerjian G.; Sicuro G.; Zdeborova L.. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - ELETTRONICO. - 2022:6(2022), pp. 063401.1-063401.44. [10.1088/1742-5468/ac70d2]

Aligning random graphs with a sub-tree similarity message-passing algorithm

Sicuro G.;
2022

Abstract

The problem of aligning ErdÅ's-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message-passing algorithm devised to solve the inference problem of partially recovering the hidden permutation, in the sparse regime with constant average degrees. We perform extensive numerical simulations to determine the range of parameters in which this algorithm achieves partial recovery. We also introduce a generalized ensemble of correlated random graphs with prescribed degree distributions, and extend the algorithm to this case.
2022
Aligning random graphs with a sub-tree similarity message-passing algorithm / Piccioli G.; Semerjian G.; Sicuro G.; Zdeborova L.. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - ELETTRONICO. - 2022:6(2022), pp. 063401.1-063401.44. [10.1088/1742-5468/ac70d2]
Piccioli G.; Semerjian G.; Sicuro G.; Zdeborova L.
File in questo prodotto:
File Dimensione Formato  
2112.13079.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 1.41 MB
Formato Adobe PDF
1.41 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/958757
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact