Statistical-computational gap in multiple Gaussian graph alignment

Abstract

We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massoulié (2025) to regimes where the number of observed graphs $p$ may also grow with the number of nodes $n$: when $p \leq O(n/\log(n))$, we recover the results from Vassaux and Massoulié (2025), and $p \geq Ω(n/\log(n))$ corresponds to a regime where the problem is as difficult as aligning one single graph with some unknown "signal" graph. Moreover, when $\log p = ω(\log n)$, the informational thresholds for partial and exact recovery no longer coincide, in contrast to the all-or-nothing phenomenon observed when $\log p=O(\log n)$. Then, we provide the first computational barrier in the low-degree framework for (multiple) Gaussian graph alignment. We prove that when the correlation $ρ$ is less than $1$, up to logarithmic terms, low degree non-trivial estimation fails. Our results suggest that the task of aligning $p$ graphs in polynomial time is as hard as the problem of aligning two graphs in polynomial time, up to logarithmic factors. These results characterize the existence of a statistical-computational gap and provide another example in which polynomial-time algorithms cannot handle complex combinatorial bi-dimensional structures.