Introduction
The Hidden Clique Problem is a foundational challenge in computational graph theory and statistics. In its standard formulation, a clique of size $k$ is "planted" within an Erdős-Rényi random graph $G(N, 1/2)$, where each edge exists independently with probability 0.5. The objective is to recover the vertices of this hidden clique. While information theory suggests that the clique is unique and identifiable for $k \ge 2 \log_2 N$, a significant "computational gap" has persisted for decades. Efficient algorithms, primarily those based on spectral methods, have historically required a clique size of at least $\sqrt{N}$ to succeed.
This paper presents a breakthrough by introducing a nearly linear-time algorithm capable of recovering cliques as small as $\sqrt{N/e} \approx 0.606\sqrt{N}$. By utilizing a message-passing framework based on Belief Propagation (BP), the authors push past the long-standing spectral barrier, offering both a theoretical advancement and a computationally efficient solution.
The Spectral Barrier and the Hidden Clique Problem
The difficulty of the Hidden Clique Problem lies in the "noise" generated by the random background graph. In $G(N, 1/2)$, the largest naturally occurring clique is approximately $2 \log_2 N$. When a planted clique is larger than this, it becomes the unique maximum clique. However, finding it is not trivial.
Spectral methods typically examine the eigenvalues and eigenvectors of the graph's adjacency matrix. When $k \ge \sqrt{N}$, the planted clique creates a "spike" in the spectrum—a principal eigenvector that aligns significantly with the clique's indicator vector. Below this $\sqrt{N}$ threshold, the signal from the clique is swallowed by the bulk of the eigenvalues of the random graph, causing standard spectral tools to fail.
Methodology: Linearized Belief Propagation
To overcome the limitations of global spectral analysis, the authors employ a local message-passing approach. The algorithm consists of three primary stages:
1. Message Passing
The core of the algorithm is an iterative process where vertices exchange "messages" regarding their likelihood of belonging to the hidden clique. Unlike standard BP, which can be difficult to analyze rigorously in dense graphs, the authors utilize a Linearized Belief Propagation scheme. In each iteration, messages are updated based on the sum of incoming signals from neighbors, processed through a specific polynomial function.
2. State Evolution
The authors use State Evolution to track the distribution of these messages as the number of vertices $N$ grows. This technique allows them to prove that the "signal-to-noise ratio" of the messages improves over iterations, provided the clique size exceeds the new threshold. The constant $1/e$ emerges naturally from the convergence properties of this recursive process; it marks the point where the clique's signal is strong enough to prevent the message distribution from collapsing into uninformative noise.
3. The Cleaning Phase
Message passing identifies a "candidate" set of vertices. To refine this into the exact clique, the authors apply a two-step cleaning procedure:
- Power Method: They compute the principal eigenvector of the subgraph induced by the candidate set.
- Thresholding: A final threshold is applied to the eigenvector components to isolate the $k$ vertices of the clique.
Key Results and Theoretical Insights
The primary contribution is the proof that this algorithm succeeds with high probability for clique sizes $|C_N| \ge (1 + \epsilon)\sqrt{N/e}$.
Breaking the $\sqrt{N}$ Barrier
By moving from global eigenvectors to iterative local updates, the algorithm effectively "filters" the background noise. The non-linear (or linearized polynomial) nature of the message updates rewards vertices with high local connectivity more effectively than linear spectral methods.
Computational Efficiency
The algorithm runs in $O(N^2 \log N)$ time. In the context of dense graphs where the number of edges is $O(N^2)$, this is nearly linear. This represents a significant improvement over high-order Semidefinite Programming (SDP) or Sum-of-Squares (SoS) hierarchies, which, while theoretically powerful, often require $O(N^3)$ or higher complexity, making them impractical for large-scale graphs.
Generalization to Sparse Graphs
The research also extends to sparse, locally tree-like regular graphs of degree $\Delta + 1$. The authors establish a sharp transition for "local" algorithms (those restricted to a $t$-step neighborhood): success is possible if the clique size is above $N/\sqrt{e\Delta}$ and impossible below it.
Conclusion and Future Directions
The reduction of the computational threshold from $\sqrt{N}$ to $\sqrt{N/e}$ is a significant step in understanding the Hidden Clique Problem. It demonstrates that the "spectral barrier" is not an absolute limit for efficient algorithms.
However, a substantial gap remains between $\sqrt{N/e}$ and the information-theoretic limit of $2 \log N$. Whether any polynomial-time algorithm can reach the logarithmic limit remains one of the most prominent open questions in theoretical computer science. Future work may explore whether more complex non-linear message-passing functions or different algorithmic paradigms can further close this gap.
Summary updated