Statistical-computational gap in multiple Gaussian graph alignment
arXiv:2512.00610v1 Announce Type: new
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’e (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’e (2025), and $p geq Omega(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 = omega(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 $rho$ 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.
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’e (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’e (2025), and $p geq Omega(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 = omega(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 $rho$ 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.
Bertrand Even, Luca Ganassali
Go to original source