A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models

Hang Du, Shuyang Gong, Jiaming Xu
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1559-1563, 2025.

Abstract

We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al. (2023) show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al. (2024) make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. (2018) is order-optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-du25a, title = {A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models}, author = {Du, Hang and Gong, Shuyang and Xu, Jiaming}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {1559--1563}, 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/du25a/du25a.pdf}, url = {https://proceedings.mlr.press/v291/du25a.html}, abstract = {We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al. (2023) show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al. (2024) make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. (2018) is order-optimal.} }
Endnote
%0 Conference Paper %T A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models %A Hang Du %A Shuyang Gong %A Jiaming Xu %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-du25a %I PMLR %P 1559--1563 %U https://proceedings.mlr.press/v291/du25a.html %V 291 %X We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al. (2023) show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-\Omega(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al. (2024) make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al. (2018) is order-optimal.
APA
Du, H., Gong, S. & Xu, J.. (2025). A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:1559-1563 Available from https://proceedings.mlr.press/v291/du25a.html.

Related Material