Low-degree phase transitions for detecting a planted clique in sublinear time

Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3798-3822, 2024.

Abstract

We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $\Theta(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster—namely, sublinear time—algorithms in the high-signal regime when $k = \Theta(n^{1/2 + \delta})$, for some $\delta > 0$. To this end, we consider algorithms that non-adaptively query a subset $M$ of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of \emph{non-adaptive low-degree algorithms}: under the scaling $\lvert M \rvert = \Theta(n^{\gamma})$, the clique can be detected when $\gamma > 3(1/2 - \delta)$ but not when $\gamma < 3(1/2 - \delta)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-\delta)})$, cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound—based on bounding the conditional low-degree likelihood ratio—reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for \emph{every} non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-mardia24a, title = {Low-degree phase transitions for detecting a planted clique in sublinear time}, author = {Mardia, Jay and Verchand, Kabir Aladin and Wein, Alexander S.}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {3798--3822}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/mardia24a/mardia24a.pdf}, url = {https://proceedings.mlr.press/v247/mardia24a.html}, abstract = {We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $\Theta(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster—namely, sublinear time—algorithms in the high-signal regime when $k = \Theta(n^{1/2 + \delta})$, for some $\delta > 0$. To this end, we consider algorithms that non-adaptively query a subset $M$ of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of \emph{non-adaptive low-degree algorithms}: under the scaling $\lvert M \rvert = \Theta(n^{\gamma})$, the clique can be detected when $\gamma > 3(1/2 - \delta)$ but not when $\gamma < 3(1/2 - \delta)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-\delta)})$, cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound—based on bounding the conditional low-degree likelihood ratio—reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for \emph{every} non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective.} }
Endnote
%0 Conference Paper %T Low-degree phase transitions for detecting a planted clique in sublinear time %A Jay Mardia %A Kabir Aladin Verchand %A Alexander S. Wein %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-mardia24a %I PMLR %P 3798--3822 %U https://proceedings.mlr.press/v247/mardia24a.html %V 247 %X We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $\Theta(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster—namely, sublinear time—algorithms in the high-signal regime when $k = \Theta(n^{1/2 + \delta})$, for some $\delta > 0$. To this end, we consider algorithms that non-adaptively query a subset $M$ of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of \emph{non-adaptive low-degree algorithms}: under the scaling $\lvert M \rvert = \Theta(n^{\gamma})$, the clique can be detected when $\gamma > 3(1/2 - \delta)$ but not when $\gamma < 3(1/2 - \delta)$. As a result, the best known runtime for detecting a planted clique, $\widetilde{O}(n^{3(1/2-\delta)})$, cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound—based on bounding the conditional low-degree likelihood ratio—reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for \emph{every} non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective.
APA
Mardia, J., Verchand, K.A. & Wein, A.S.. (2024). Low-degree phase transitions for detecting a planted clique in sublinear time. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:3798-3822 Available from https://proceedings.mlr.press/v247/mardia24a.html.

Related Material