Spectral Recovery of a Planted Triangle-Dense Subgraph

Sam van der Poel, Cheng Mao, Benjamin McKenna
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6410-6457, 2026.

Abstract

Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erdős–Rényi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-van-der-poel26a, title = {Spectral Recovery of a Planted Triangle-Dense Subgraph}, author = {{van der Poel}, Sam and Mao, Cheng and McKenna, Benjamin}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6410--6457}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/van-der-poel26a/van-der-poel26a.pdf}, url = {https://proceedings.mlr.press/v336/van-der-poel26a.html}, abstract = {Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erdős–Rényi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$.} }
Endnote
%0 Conference Paper %T Spectral Recovery of a Planted Triangle-Dense Subgraph %A Sam van der Poel %A Cheng Mao %A Benjamin McKenna %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-van-der-poel26a %I PMLR %P 6410--6457 %U https://proceedings.mlr.press/v336/van-der-poel26a.html %V 336 %X Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erdős–Rényi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$.
APA
van der Poel, S., Mao, C. & McKenna, B.. (2026). Spectral Recovery of a Planted Triangle-Dense Subgraph. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6410-6457 Available from https://proceedings.mlr.press/v336/van-der-poel26a.html.

Related Material