Technical Summary: Detecting Weighted Hidden Cliques

Problem Statement

This paper investigates a generalization of the classical hidden clique (or planted clique) problem to graphs with real-valued edge weights. The problem is formulated as a binary hypothesis testing problem on a complete graph with $n$ vertices.

Let $X = (X_{ij})_{i,j \in [n]}$ denote the matrix of edge weights. The two hypotheses are:

• Null Hypothesis ($H_0$): The graph $G(n, P)$ is generated such that all edge weights are independent and identically distributed (i.i.d.) according to a probability distribution $P$.
• Alternative Hypothesis ($H_1$): The graph $G(n, k, P, Q)$ is generated by first choosing a subset of $k$ vertices uniformly at random. The edge weights between these $k$ vertices are drawn i.i.d. from a distribution $Q$, while all remaining edge weights are drawn i.i.d. from $P$.

The objective is to determine, based on the observed edge weights, whether the data was generated under $H_0$ or $H_1$. The authors analyze the statistical limits of detectability (when the risk of the optimal test vanishes) and the computational complexity of detection under two distinct scenarios regarding the availability of information about $P$ and $Q$.

Methodology and Scenarios

The paper analyzes the problem under two primary scenarios:

1. Complete Information

In this scenario, the distributions $P$ and $Q$ are fully known to the statistician. The analysis relies on information-theoretic divergences between $P$ and $Q$, specifically the Kullback-Leibler (KL) divergence ($D_{KL}(Q||P)$) and the $\chi^2$-divergence ($\chi^2(Q, P)$).

• Optimal Risk Analysis: The authors derive conditions on the size of the clique $k$ (denoted as $k_n$) required for the optimal likelihood ratio test to distinguish the hypotheses.
• Spectral Testing: To address computational efficiency, the authors propose a spectral test. This involves transforming the edge weight matrix $X$ into a matrix $Z$ using a function $\phi(x)$ based on the densities of $P$ and $Q$. The test statistic is the maximum eigenvalue of the centered matrix $Z - \mathbb{E}_0 Z$.

2. Partial Information

In this scenario, the full distributions $P$ and $Q$ are unknown.

• Non-Absolutely Continuous Case: When $Q$ is not absolutely continuous with respect to $P$ (i.e., there exists a set with positive $Q$-measure but zero $P$-measure), the authors propose a polynomial-time scan test. This test searches for an interval $I \subset \mathbb{R}$ and a subset of vertices $S$ such that all edges within $S$ have weights in $I$, while edges outside $S$ do not.
• Absolutely Continuous Case (Mean Difference): When $P$ and $Q$ are absolutely continuous but their means differ ($\mu_P \neq \mu_Q$) and they have bounded support, the authors propose a spectral test based on the maximum eigenvalue of the centered weight matrix $\|X - \mathbb{E}_0 X\|$. This test utilizes only the means and the support bounds, not the full densities.

Key Contributions and Results

Statistical Limits

• Non-Absolutely Continuous Distributions: If $Q$ is not absolutely continuous with respect to $P$, the hypotheses are distinguishable as long as $k \to \infty$. The optimal risk $R(T^*)$ converges to 0.
• Absolutely Continuous Distributions:
  • Lower Bound: If $k_n \to \infty$ (regardless of the rate), there exist distributions $P$ and $Q$ such that the hypotheses are distinguishable.
  • Upper Bound (Detectability): If $k_n \geq (2+\epsilon) \frac{\log n}{D_{KL}(Q||P)}$, the optimal risk converges to 0.
  • Indistinguishability: If $k_n \leq \lfloor 2 \log_\rho n - \dots \rfloor$ where $\rho = \chi^2(Q||P) + 1$, the optimal risk converges to 1, rendering the hypotheses indistinguishable.
• General Bound: For any $P \neq Q$, there exists a constant $c$ such that if $k \geq c \log n$, detection is possible. This establishes that the critical clique size is at most logarithmic in $n$.

Computational Results

• Spectral Algorithms: The paper provides computationally efficient (polynomial-time) spectral tests that can distinguish the hypotheses when $k = \Omega(\sqrt{n})$.
  • In the complete information scenario, the test uses the transformation $\phi(x)$ derived from the densities.
  • In the partial information scenario (bounded support, different means), the test uses the raw weight matrix centered by the null mean.
• Statistical-Computational Gap: The authors highlight a gap between the statistical limit ($k = \Omega(\log n)$) and the computational limit of their proposed spectral tests ($k = \Omega(\sqrt{n})$).

Specific Theorems

• Theorem 3.1 & 3.7: Establish that if $Q$ is not absolutely continuous w.r.t. $P$, detection is possible for any $k \to \infty$, even with unknown distributions.
• Theorem 3.4: Provides the precise statistical thresholds for detection in terms of $D_{KL}$ and $\chi^2$ divergences when distributions are known.
• Theorem 3.6 & 3.8: Define the performance bounds for the spectral tests in the complete and partial information settings, respectively, showing they succeed when $k \propto \sqrt{n}$.

Significance and Claims

The paper claims to extend the classical hidden clique problem (which corresponds to the case where $P$ is Bernoulli($p$) and $Q$ is Dirac at 1) to a general setting with real-valued edge weights. The significance of the work lies in:

1. Generalization: Moving beyond binary edge existence to continuous edge weights, which models more complex network data.
2. Characterization of Distinguishability: Providing rigorous statistical limits on the clique size $k$ required for detection, expressed through standard information divergence measures.
3. Handling Partial Information: Demonstrating that detection is feasible even when distributions are unknown, provided certain structural conditions (like non-absolute continuity or mean differences) are met.
4. Algorithmic Efficiency: Proposing polynomial-time spectral algorithms that achieve detection in the $k = \Omega(\sqrt{n})$ regime, contrasting with the $k = \Omega(\log n)$ statistical limit.

The authors explicitly note that while they provide upper and lower bounds for the detection threshold, a "sharp phase transition" (where the upper and lower bounds match exactly) is not guaranteed for all distribution pairs, unlike in the classical binary case. They identify the existence of a statistical-computational gap as a central feature of the problem, questioning whether this gap is inherent or can be closed for specific distribution pairs. The paper concludes by identifying the recovery of the planted clique (rather than just detection) and the thresholds for recovery under partial information as open directions for future work.