{"ID":2835260,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.00610","arxiv_id":"2512.00610","title":"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.","short_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/\\lo...","url_abs":"https://arxiv.org/abs/2512.00610","url_pdf":"https://arxiv.org/pdf/2512.00610v1","authors":"[\"Bertrand Even\",\"Luca Ganassali\"]","published":"2025-11-29T19:52:12Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.ST\"]","methods":"[]","has_code":false}