Source-linked AI summary
Computational Lower Bounds for Community Detection on Random Graphs
Bruce Hajek, Yihong Wu, Jiaming Xu
TL;DR
The paper asks when a small planted community in a random graph is statistically detectable and whether efficient procedures can attain that limit. Assuming the PC Hypothesis, the paper uses a randomized polynomial-time reduction from planted clique detection to planted dense subgraph detection. At α = 2/3, computational difficulty transitions: for α < 2/3 combinatorial procedures detect smaller communities than efficient ones, while for α > 2/3 total-edge counting achieves optimal detection in linear time.
Problem
The paper asks when a small planted community in a random graph is statistically detectable and whether efficient procedures can attain that limit.
Source: §1 · pp. 1–2Method
Assuming the PC Hypothesis, the paper uses a randomized polynomial-time reduction from planted clique detection to planted dense subgraph detection.
Source: §1.1 · p. 3, §1.2 · p. 5Results
At α = 2/3, computational difficulty transitions: for α < 2/3 combinatorial procedures detect smaller communities than efficient ones, while for α > 2/3 total-edge counting achieves optimal detection in linear time.
Source: §1.1 · p. 3Takeaways & Limitations
The lower bound implies no polynomial-time algorithm can approximate the planted dense subgraph or densest K-subgraph within any constant factor when α < β < 1/2 + α/4.
Source: §1.1 · p. 4The computational lower bounds are conditional on the PC Hypothesis holding for any positive constant γ.
Source: §1.1 · p. 3
Abstract
from arXiv · showhide
This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph $\mathcal{G}(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-\alpha}$, there exists a critical value of $\alpha = \frac{2}{3}$, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$-subgraph.
1 Introduction
The paper studies detecting a small, unusually dense community in a random graph and asks when statistical detectability can be achieved efficiently. Under planted-clique hardness, it derives a sparsity-dependent computational transition and implications for recovery and densest-subgraph approximation.
1 Introduction
- The planted dense subgraph problem asks whether a random graph contains a community with higher internal edge probability; this paper studies its computational limits when p = cq for constant c > 1.The planted community has a random, binomially distributed size with mean K.Source: §1 · pp. 1–2
1.1 Main Results
- At α = 2/3, computational difficulty changes: for α < 2/3 combinatorial methods detect smaller communities than efficient procedures, while for α > 2/3 total-edge counting achieves optimal detection in linear time.The regime diagram captures only leading polynomial terms; at β = α/4 + 1/2, more than simple edge counting may be needed.Source: §1.1 · pp. 3–4
- For α > 2, detection is impossible even when the planted subgraph spans the entire graph.The paper excludes this sparsity range from its interesting regime.Source: §1.1 · p. 3
- The detection lower bound implies average-case hardness of constant-factor approximation for the planted dense subgraph and densest K-subgraph when α < β < 1/2 + α/4.This complements the cited worst-case inapproximability result for DKS.Source: §1.1 · p. 4, §1.2 · p. 5
1.2 Connections to the Literature
- A randomized polynomial-time reduction maps planted-clique instances to PDS instances, with output distributions close to the target null and alternative distributions.The lower bounds assume the PC Hypothesis holds for any positive constant γ.Source: §1.1 · p. 3, §1.2 · pp. 4–5
2 Statistical Limits
The section characterizes the statistical detection boundary for planted dense subgraphs when p=cq, using lower and upper bounds. It shows when reliable detection is impossible and when linear or scan tests achieve vanishing error.
2 Statistical Limits
2.1 Lower Bound
- When q=O(1/K^4), no test can reliably detect the planted subgraph under the stated conditions.Proposition 1 gives the lower bound for p=cq with fixed c>1.Source: §2.1 · p. 6
2.2 Upper Bound
- Reliable detection is achieved above β*(α) by the linear or scan test; the linear test succeeds for β>1/2+α/4, while the scan test succeeds for β>α.The linear statistic counts all graph edges, while the scan statistic searches for a dense K-subgraph; the latter can be computationally intensive.Source: §2.2 · p. 7
- The linear test is computable in linear time, whereas computing the scan test requires enumerating all K-vertex subsets.The section leaves polynomial-time solvability in α<β<1/2+α/4 unresolved, referring to the next section for its computational lower bound.Source: §2.2 · p. 7
3 Computational Lower Bounds
Assuming planted-clique hardness, the section reduces planted clique detection to planted dense subgraph detection using a randomized graph transformation. The reduction yields computational lower bounds for PDS and locates a gap between its statistical and computational detection limits.
3 Computational Lower Bounds
- The reduction randomly assigns each output-graph vertex a parent in the input graph and generates inter-group edge counts through a conditional distribution.The construction uses additional randomness and selects specific edges uniformly after choosing each group-pair edge count.Source: §3 · p. 8
- The reduction matches the PDS null distribution exactly and approximates the alternative by matching planted-clique edge counts to the desired binomial distributions.The alternative matching requires controlling the total variation distance after averaging over the random partition.Source: §3 · p. 8
- A PDS test with Type-I+II error η induces a planted-clique test with Type-I+II error at most η+ξ under Proposition 3's conditions.This transfer is the formal connection that supports the computational lower bound.Source: §3 · pp. 8–9
- Theorem 1 establishes a computational lower bound for PDS by transferring hardness from planted clique detection under Hypothesis 1.The result applies to randomized polynomial-time tests under the theorem's parameter conditions.Source: §3 · pp. 7, 9
- The statistical limit is below the computational barrier exactly when α<2/3, so computational efficiency incurs a detection penalty in that regime.The paper relates this threshold to the noisy submatrix detection phenomenon reported in [30].Source: §3 · p. 9
4 Extensions and Open Problems
The extensions connect planted dense subgraph detection hardness to recovery and densest-K-subgraph approximation, then extend lower bounds to deterministic-size and bipartite settings. They also identify unresolved hardness questions and a limitation for the fixed-size reduction.
4.1 Recovering Planted Dense Subgraphs and DKS Problem
- Recovering the planted dense subgraph also yields a polynomial-time (1 + ε)-approximation to DKS for any ε > 0.This implication is stated for the asymptotic regime β > α and α < 1.Source: §4.1 · p. 10
- For α < β < β♯(α), planted dense subgraph recovery and constant-factor DKS approximation are hard; hardness in the blue regime remains open.In the simple regime β > 1/2, recovery and (1 + ε)-approximation of DKS are possible in polynomial time.Source: §4.1 · p. 10, Figure 2 · p. 10
4.2 PDS Problem with a Deterministic Size
- The fixed-size extension is limited by an unresolved equivalence: the random-size model concentrates near K, but the alternative distributions have not been shown to approximately match.The technical hurdle is controlling total variation between the partition-averaged edge-count distribution and the desired distribution.Source: §4.2 · p. 11
- For deterministic-size PDS, computational lower bounds hold for monotone tests in α < β < β♯(α), and recovery is computationally intractable there.The lower bound for tests does not cover arbitrary tests; proving it without monotonicity, or proving optimal polynomial-time tests are monotone, remains open.Source: §4.2 · p. 11
4.3 Bipartite PDS Problem
- Under the planted clique hypothesis, no efficient test solves bipartite PDS for α < β < β♯(α); the same limits apply to deterministic-size bipartite PDS.The reduction is from bipartite planted clique, and the paper states that its lower-bound proof is simpler than in the non-bipartite case.Source: §4.3 · pp. 11–12
A.1 Proof of Proposition 1
The proof bounds the distance between the null and alternative distributions by conditioning on the planted-set size and controlling the resulting conditional distance.
A.1 Proof of Proposition 1
- The proof conditions on planted-set size and uses a Chernoff bound to control the probability that the size exceeds 2K.The stated tail bound is exp(−K/8).Source: §A.1 · p. 14
- For a fixed size K′ ≤ 2K, the proof compares the conditional alternative distribution with the null using a chi-squared divergence bound.The displayed inequality relates total variation distance to log(χ² + 1), then bounds it by log(τ(Cc²)).Source: §A.1 · pp. 14–15
- Combining the conditional bound with the preceding size control yields inequality (2), with h defined as log composed with τ.Source: §A.1 · p. 15
A.2 Proof of Proposition 2
The proof analyzes the linear and scan test statistics under the null and alternative using concentration bounds.
A.2 Proof of Proposition 2
- Under the null, the proof begins by modeling the linear statistic Tlin with a binomial distribution and applying Bernstein’s inequality.Source: §A.2 · p. 15
- Under the alternative, a Chernoff bound controls the chance that the planted set has fewer than 0.9K vertices before bounding Tlin.The stated probability bound is exp(−K/200), followed by a multiplicative Chernoff bound conditional on planted-set size.Source: §A.2 · p. 15
- For the scan statistic, the proof bounds null probabilities with a union bound and Bernstein’s inequality, then analyzes the alternative with multiplicative Chernoff bounds.The alternative analysis conditions on planted-set size at least 0.9K.Source: §A.2 · p. 16
A.3 Proof of Proposition 3
The proof establishes the reduction’s distributional closeness by matching the null exactly and controlling the alternative through partition-wise comparisons.
A.3 Proof of Proposition 3
- Negative association of partition-block overlaps lets the proof control the joint alternative mismatch using bounds on the overlaps and individual block distances.The final proposition follows by combining the bounds on the component terms.Source: §A.3 · pp. 18, 19, 23
- The reduction’s null distributions match exactly: each block’s edge count has the same binomial law, yielding the Erdős–Rényi graph G(N, q).The proof establishes independence across blocks as part of this matching argument.Source: §A.3 · p. 20
- For the alternative, the planted set is a mixture indexed by a random set S, whose size is binomial with mean K; the proof conditions on S to bound the mismatch.It restricts attention to |S| ≤ 1.5K and controls oversized partition blocks with a Chernoff and union bound.Source: §A.3 · pp. 20–21
- The proof reduces block-distribution comparisons to edge-count comparisons, which are sufficient statistics, and applies a lemma to bound the total variation distance.Source: §A.3 · pp. 16, 22
A.4 Proof of Proposition 4
The reduction maps a planted-clique input to a graph distributed as G(N,q) under HC. It transfers the PDS test’s error bound to a test on the planted-clique instance.
A.4 Proof of Proposition 4
- Under HC, the reduction output eG is distributed as G(N,q).Here G′ is distributed according to either P0 or P1.Source: §A.4 · p. 23
- Under P0, the probability that φ(eG) outputs 1 equals the probability that φ(G′) outputs 1.Source: §A.4 · p. 23
- The transferred test’s Type-I plus Type-II error is at most η + ξ.Source: §A.4 · p. 23
A.5 Proof of Theorem 1
The proof assumes a polynomial-time PDS test with an error bound that contradicts Hypothesis 1 after applying the reduction from planted clique. The reduction’s additive error ξ vanishes in the limit.
A.5 Proof of Theorem 1
- The assumed PDS tests would yield a planted-clique test with Type-I plus Type-II error at most 1 − ε + ξ.The contradiction setup fixes α and β satisfying (7), chooses qℓ = ℓ^−(2+δ), and assumes the PDS tests exist for arbitrarily large ℓ.Source: §A.5 · p. 24
- Since qℓℓ² = ℓ^−δ, the proof shows that ξ → 0 as ℓ → ∞.Source: §A.5 · p. 24
- The resulting bound contradicts Hypothesis 1; sending γ ↓ 0 then gives (8) when Hypothesis 1 holds for any γ > 0.The reduction applies because kℓ ≥ ℓ^(1+δ) and the stated conditions hold for sufficiently large ℓ.Source: §A.5 · p. 24
B Computational Lower Bounds for Approximately Recovering a Planted Dense Subgraph with Deterministic Size
Theorem 2 reduces approximate recovery of a deterministic-size planted dense subgraph to detection in a planted dense subgraph model. It does so by running the recovery algorithm on a sequence of modified graphs and testing the outputs for unusually many internal edges.
B Computational Lower Bounds for Approximately Recovering a Planted Dense Subgraph with Deterministic Size
- PDSR targets a uniformly planted set of exactly K vertices and requires an output overlapping at least (1 − ε)K vertices, unlike PDS’s binomially distributed planted size.The stated hardness implication applies when Kq = Ω(log N).Source: B Computational Lower Bounds for… · p. 24
- A recovery algorithm with running time T_N yields a PDS test running in at most N² + NT_N + NK², with Type-I+II error at most η_N + e^−CK + 2Ne^−CK²q+K log N.Theorem 2 applies to recovery of PDSR(N,K,cq,q,ε) with success probability 1 − η_N and tests PDS(N,2K,cq,q).Source: B Computational Lower Bounds for… · p. 25
- The test randomly replaces each vertex in turn with a fresh vertex whose edges are independently sampled with probability q, then checks whether any recovery output has more than τ internal edges.The threshold is τ = q + (1 − ε)²(p − q)/2.Source: B Computational Lower Bounds for… · p. 25
C A Lemma on Hypergeometric Distributions
This appendix establishes a bound involving a hypergeometric random variable and proves it by splitting into parameter regimes and controlling expectations through decoupling and truncation.
C A Lemma on Hypergeometric Distributions
- Lemma 6 asserts a bound involving a function τ with τ(0+) = 1 for a hypergeometric random variable H.The passage identifies H as Hypergeometric(p,m,m), but the bound’s remaining expression is not available here.Source: C A Lemma on Hypergeometric… · p. 26
- The proof treats small p as trivial, then separates cases by m and focuses on an intermediate regime.Source: C A Lemma on Hypergeometric… · p. 26
- For the intermediate regime, the proof uses decoupling and truncates on T to bound expectations.It invokes a standard decoupling inequality and derives a tail bound involving τ′′(b), with 0 < b < 1/(16e).Source: C A Lemma on Hypergeometric… · pp. 26–28