“All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract)

Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2457-2459, 2025.

Abstract

This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdős–Rényi random graph $\mathcal{G}(n,\lambda/n)$. We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree $\lambda$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as $\lambda$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $\lambda < 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $\Theta(n)$ many small trees of size $\Theta(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $\Theta(\sqrt{n\log n})$ suffices.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-gaudio25a, title = {“All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract)}, author = {Gaudio, Julia and Sandon, Colin and Xu, Jiaming and Yang, Dana}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {2457--2459}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/gaudio25a/gaudio25a.pdf}, url = {https://proceedings.mlr.press/v291/gaudio25a.html}, abstract = {This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdős–Rényi random graph $\mathcal{G}(n,\lambda/n)$. We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree $\lambda$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as $\lambda$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $\lambda < 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $\Theta(n)$ many small trees of size $\Theta(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $\Theta(\sqrt{n\log n})$ suffices.} }
Endnote
%0 Conference Paper %T “All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract) %A Julia Gaudio %A Colin Sandon %A Jiaming Xu %A Dana Yang %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-gaudio25a %I PMLR %P 2457--2459 %U https://proceedings.mlr.press/v291/gaudio25a.html %V 291 %X This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdős–Rényi random graph $\mathcal{G}(n,\lambda/n)$. We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree $\lambda$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as $\lambda$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $\lambda < 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $\Theta(n)$ many small trees of size $\Theta(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $\Theta(\sqrt{n\log n})$ suffices.
APA
Gaudio, J., Sandon, C., Xu, J. & Yang, D.. (2025). “All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract). Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:2457-2459 Available from https://proceedings.mlr.press/v291/gaudio25a.html.

Related Material