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

Jay Mardia; Kabir Aladin Verchand; Alexander S. Wein

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

Download PDF