{"id":"99387b6f-d2cf-4d8b-a0c4-ff386f51f9bf","arxiv_id":"2411.19885","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new planted ranked subgraph model in directed graphs is analyzed, with exact statistical and computational thresholds for detection and recovery in the log-density and extreme regimes.","lead":"This paper introduces a model of a hidden ranked community inside a directed graph and finds the exact signal strengths at which algorithms can detect or recover it, both statistically and in polynomial time. It produces a phase diagram with easy, hard-but-possible, and impossible regimes, and shows which simple algorithms such as ranking by wins and spectral methods are optimal.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the central phase diagram is well supported, with the acknowledged low-degree conjecture as the only conditional step.","rationale":"The reader's weakest assumption was the low-degree conjecture, and that is also the only point of conditionality in the paper. My stress-test focused on whether the proofs are internally sound and whether the claimed exponents are exactly supported. I verified the key calculations: the variance/expectation computations for the degree-2 detector, the χ2 upper bound and the moment-generating-function bounds (Propositions 4.2, 4.3), the Davis-Kahan spectral recovery analysis, and the low-degree advantage/correlation bounds. In each case the exponent bookkeeping matches the stated thresholds, including the handling of the sparse censoring p. The optional λ in the statistical recovery union bound is chosen as eΘ(max{k^{3/2}√p, k}), which legitimately absorbs the necessary log factors, and the final condition q ≫ log n/√(pk) yields β > 2α+γ as stated. The computational lower bounds are honestly presented as conditional on Conjecture 3.8, and this does not undermine the central claim provided the conjecture is accepted. No ad-hoc or circular reasoning was found. Therefore the reader's verdict of ACCEPT with moderate confidence stands unchanged.","tokens_in":63192,"tokens_out":22895,"duration_ms":208604,"concrete_test":"Independently recompute the low-degree advantage for degree 2 in the log-density setting by symbolically enumerating all even subgraphs in the bound of Proposition 3.12, verifying that the threshold β > 2/3α + 1/3γ + 1/2 emerges exactly; additionally run a numerical experiment at n=10^4 with α=0.2, γ=0.2 for β=0.6 and β=0.7 using the degree-2 detection statistic of Equation (11) to confirm the predicted transition from failure to success.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the core analyses and found no load-bearing defect. The statistical thresholds are supported by matching upper/lower bounds: the χ2-based lower bound for detection yields β < min{2α+γ, 2/3α+1/3γ+1/2} exactly matching the union-bound upper bound, and the KL-based recovery lower bound yields β < 2α+γ matching the MLE-type upper bound. The computational upper bounds are explicit polynomial-time algorithms (degree-2 polynomial, spectral method, ranking-by-wins), and the low-degree lower bounds are internally consistent, with the exponent algebra in the advantage/correlation sums checked across the β>1/2, β=1/2, β<1/2 cases. The only genuinely conditional element is the standard low-degree conjecture (Conjecture 3.8), explicitly flagged by the authors as informal; the detection lower bound uses degree D=O((log n)^{2−ε}) which is compatible with the conjecture's D≥(log n)^{1+ε} requirement. The 'less stringent assumptions' wording in Theorem 1.7 is slightly imprecise but the substantive claim is correct. No internal inconsistency or unproven nonstandard step was found.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the planted ranked subgraph (PRS) model for directed graphs, in which a hidden subset S of k vertices carries a latent permutation π and the observed directed edges within S are biased toward agreement with π, while all edge directions outside S are fair. The authors study both detection (testing the planted distribution against the null) and recovery (estimating S and π), in each case separating statistical from computational feasibility. In the log-density setting q=n^{-α}, k=n^β, p=n^{-γ}, they derive exact exponent thresholds: statistical detection is possible iff β>min{2α+γ, 2/3α+1/3γ+1/2}; statistical recovery iff β>2α+γ; computational detection iff β>2/3α+1/3γ+1/2; and computational recovery iff β>α+γ/2+1/2, with the computational lower bounds explicitly informal and resting on the low-degree conjecture. The paper also gives sharp results for two extreme cases: a full tournament weakly correlated with a global ranking (detection threshold q∼n^{-3/4}, recovery threshold q∼n^{-1/2}, with a spectral detection algorithm provably suboptimal), and a small planted ordered clique in a tournament (exact recovery for k≥c√n for any constant c).","tokens_in":63365,"tokens_out":48324,"duration_ms":423869,"significance":"If the phase diagram is correct, this is a substantial contribution to the theory of planted inference in directed graphs. The model is a natural directed analogue of planted dense subgraph, and the paper provides the first exact exponent-level characterization of statistical and computational thresholds for it, including explicit detection-recovery and statistical-computational gaps. The statistical upper and lower bounds are supported by matching χ²/KL and union-bound calculations, and the computational upper bounds are constructive polynomial-time algorithms (degree-2 polynomial, spectral method, ranking-by-wins). The computational lower bounds are conditional on the low-degree conjecture, but they are carefully and honestly labeled as informal, and the low-degree calculations themselves are internally consistent. The extreme-case results, particularly the spectral-vs-combinatorial gap for detection in tournaments, are interesting in their own right.","major_comments":[{"comment":"The proposition as stated is false and does not match its use. It claims the number of connected A⊆[n] choose 2 with 1∈V(A), |A|=d, and |V(A)|=d+1−h is at most (dn)^d(d/n)^d. But the proof immediately uses the bound (dn)^d(d/n)^h; for d=1 and h=0, the stated bound gives 1 while the actual number of such edge sets is n−1. Since this counting bound is a load-bearing step in the derivation of Corr≤D(P)²≤k²/n²·(...) that establishes Theorem 1.7's lower bound, the proof as written is not valid. Please correct the proposition statement (the intended bound appears to be (dn)^d(d/n)^h, as used) or revise the application accordingly, and make the dependence on the cited [SW22, Lemma 3.5] explicit.","section":"Section 4.3.2, Proposition 4.13 and following inequality"},{"comment":"The proof of the upper bound on OPT contains an incorrect stochastic domination statement. It says that for each fixed Bℓ, the distribution of Σ_{(x,y)∈Bℓ} Y_{x,y} is stochastically dominated by a sum of n/2^ℓ independent Rademacher variables. However |Bℓ| = n²/2^{ℓ+1}, so the number of summands is off by a factor of order n, which changes the tail scale and the resulting O(n^{3/2}) claim. This proof supports the upper bound in Proposition 5.1, which is used in Theorem 1.16. Please correct the number of summands (presumably |Bℓ| or an equivalent bound) and supply the omitted union-bound calculation, or state a precise adaptation of [dlV83].","section":"Section 5.1.4, Proposition 5.1 proof"}],"minor_comments":[{"comment":"There is a duplicated phrase: 'See, e.g., See, e.g., [KWB19, Lemma 1.13]'. Please fix.","section":"Section 5.1.1"},{"comment":"The remark says 'In the case of γ ≥ 1/4'; this should be 'q ≥ 1/4', since the surrounding discussion is about the tournament setting with the signal strength q, not the log-density exponent γ.","section":"Remark 1.17"},{"comment":"The tilde-o notation eO, eΘ, eΩ is used in Section 4.4.1 and elsewhere without being formally defined. Please add a sentence defining these as hiding poly-logarithmic factors.","section":"General notation"},{"comment":"The phrase 'under the less stringent assumptions that q=ω(√n/(k√p)), p=Ω(log n/n), and k=ω(1)' is misleading: in the log-density setting these assumptions are equivalent to β>α+γ/2+1/2, not weaker. The intended meaning is that the statement is more general because p, k, q need not be exact powers of n. Please rephrase.","section":"Theorem 1.7"},{"comment":"The abstract states that the paper establishes 'exact thresholds' for computational feasibility, but the computational lower bounds are conditional on the low-degree conjecture. Section 1.2 does qualify this, so please add a similar qualifier in the abstract to avoid overstating the status of the computational thresholds.","section":"Abstract and Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is strong and likely correct in its main conclusions, but the two proof issues identified above—especially the false Proposition 4.13, which is used in the core computational lower bound for recovery—require correction before the paper can be accepted. I do not see any reason to doubt the novelty or the general approach; the fixes appear localized."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a good paper, worth refereeing. The model—planted ranked subgraph in a directed graph—is genuinely new to me, and the authors do what a first paper on a model should do: they map out the log-density phase diagram for detection and recovery, with statistical thresholds backed by matching upper and lower bounds. The computational thresholds are conditional on the low-degree conjecture, and they say so clearly.\n\nThe strongest part is the statistical analysis. The chi-squared/TV calculations for detection and the KL/Neyman-Pearson arguments for recovery look complete. The low-degree advantage computations are intricate but appear correct; I checked the exponent algebra at the boundaries and it lines up. The two extreme cases are also well handled: the global ranking tournament gives sharp n^{-3/4} detection and n^{-1/2} recovery thresholds, and the ordered clique result (exact recovery for k = O(sqrt n)) extends the planted clique analogy naturally.\n\nThe main soft spot is not really a flaw: the computational hardness results depend on Conjecture 3.8 (low-degree conjecture). That is standard in this area, and the paper labels those theorems informal. The more minor issue is Theorem 1.7's 'less stringent assumptions' phrase—the stated conditions (p = Omega(log n/n), k = omega(1)) are not literally less stringent than the log-density setting, but the substantive claim is correct. Also, the paper is long and some appendix proofs are terse, but the structure is readable.\n\nI don't see a load-bearing defect. The model is interesting, the results are sharp, and the limitations are honestly disclosed. This deserves a serious referee. I'd cite it and would bring it to reading group.","headline":"A solid first paper on a new planted model; the statistical thresholds are rigorous, the computational ones are honest about relying on the low-degree conjecture.","tokens_in":63890,"tokens_out":2023,"would_cite":true,"duration_ms":21968,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper maps exactly when a hidden ranked community in a directed graph can be detected and recovered, statistically and in polynomial time.","keywords":["planted ranked subgraph","detection-recovery gap","statistical-computational gap","low-degree polynomial method","directed graph community detection","noisy ranking","random tournaments","planted ordered clique"],"falsifier":"A concrete falsifier would be any polynomial-time algorithm that achieves weak detection or weak recovery for some exponents with $\\beta < \\frac{2}{3}\\alpha + \\frac{1}{3}\\gamma + \\frac{1}{2}$; alternatively, one could numerically compute the low-degree advantage at degree $D = (\\log n)^{1+\\varepsilon}$ inside the claimed hard region and find it diverging, which would break the low-degree lower bound itself.","tokens_in":62989,"feed_emoji":"🎯","tokens_out":5890,"duration_ms":58075,"temperature":0.7,"pith_summary":"The paper studies a directed analogue of the planted dense subgraph problem: a hidden subset of $k$ vertices carries a latent ranking, and edges between those vertices favor the higher-ranked endpoint with probability $1/2 + q$, while all other pairwise directions are unbiased coin flips. Because the underlying undirected edge set is just a random graph with independent edges, the planted structure is visible only in the consistency of directions, not in edge density. In the log-density scaling $q = n^{-\\alpha}$, $k = n^{\\beta}$, $p = n^{-\\gamma}$, the paper claims exact exponent thresholds for statistical and computational detection and recovery, yielding a three-parameter phase diagram with both statistical-computational gaps and detection-recovery gaps. A sympathetic reader would take the central contribution to be a clean new model where the boundary between feasible and infeasible inference is known precisely, up to an explicit unproved conjecture about computational hardness.","feed_headline":"Exact thresholds found for hidden rankings in directed graphs","feed_subtitle":"Statistical and computational limits for detecting and recovering a planted rank-ordered subgraph turn out to be explicit exponent…","key_machinery":"Three mechanisms carry the argument. First, the degree-$2$ polynomial $f(Y) = \\sum_{i}\\sum_{j<k} Y_{ij}Y_{ik}$, essentially the sample variance of win counts, separates the planted from the null distribution when $k^3 p^2 q^2$ dominates the noise scale; thresholding it gives the computational detection upper bound. Second, the Hermitian matrix $iY$ has expectation whose top eigenvector encodes the planted set and ranking through a matrix $A_{\\ell}$ with eigenvalues $1/\\tan((2i-1)\\pi/(2\\ell))$, and a Davis-Kahan perturbation bound converts closeness of eigenvectors into approximate recovery of both the subset and the permutation. Third, the low-degree method computes the low-degree advantage and low-degree correlation as sums over edge subsets, bounded by counting even graphs, yielding the computational lower bounds that the paper labels as conditional on the low-degree conjecture. For tournaments, Ranking By Wins combined with read-$k$ tail bounds and Berry-Esseen estimates gives recovery and alignment guarantees.","core_discovery":"On the paper's own terms, the central discovery is that the planted ranked subgraph model has explicit, exact thresholds in the log-density regime. Strong detection is statistically possible if and only if $\\beta > \\min\\{2\\alpha + \\gamma,\\ \\frac{2}{3}\\alpha + \\frac{1}{3}\\gamma + \\frac{1}{2}\\}$, while strong detection by polynomial-time algorithms is possible if and only if $\\beta > \\frac{2}{3}\\alpha + \\frac{1}{3}\\gamma + \\frac{1}{2}$, with the lower bound informal and conditional on the low-degree conjecture. Strong recovery is statistically possible if and only if $\\beta > 2\\alpha + \\gamma$, and computationally possible if and only if $\\beta > \\alpha + \\frac{1}{2}\\gamma + \\frac{1}{2}$, again with the hardness part resting on the same conjecture. At the two extreme scalings the picture sharpens: a full tournament weakly correlated with a global ranking is strongly detectable when $q = \\omega(n^{-3/4})$ and weakly recoverable when $q = \\omega(n^{-1/2})$, and a planted ordered clique of size $k = \\Omega(\\sqrt{n})$ is exactly recoverable in polynomial time, with the constant in front of $\\sqrt{n}$ reducible to any positive constant.","pith_inferences":["Editorial extension: the same proof template of bounding low-degree advantage by counting even edge subsets should transfer to bipartite or multilayer versions of the model, with the exponent formulas changing according to the dimension of the planted structure.","Editorial extension: the spectral detection result suggests that in sparse directed models, eigenvalue-based statistics can be polynomially weaker than quadratic combinatorial statistics, a phenomenon that could be tested in other planted ranking and planted structure settings.","Editorial extension: the exponent predictions are directly testable at finite $n$ by Monte Carlo estimation of the low-degree advantage and comparison with the claimed threshold curves, independently of whether the low-degree conjecture is eventually resolved.","Editorial extension: the model provides a minimal setting where the detection-recovery gap and the statistical-computational gap coexist, so it could serve as a benchmark for transfer principles that predict computational hardness from low-degree calculations."],"forward_implications":["When $\\beta > \\frac{2}{3}\\alpha + \\frac{1}{3}\\gamma + \\frac{1}{2}$, a simple quadratic polynomial in the directed adjacency matrix detects the ranked community in polynomial time.","When $\\beta$ lies between $\\min\\{2\\alpha+\\gamma,\\ \\frac{2}{3}\\alpha+\\frac{1}{3}\\gamma+\\frac{1}{2}\\}$ and the computational threshold, detection is statistically possible but apparently computationally hard, exhibiting a statistical-computational gap.","Spectral recovery through the Hermitian matrix $iY$ succeeds down to $\\beta > \\alpha + \\frac{1}{2}\\gamma + \\frac{1}{2}$, matching the low-degree lower bound under the conjecture.","In a full tournament, Ranking By Wins is optimal up to constants: it strongly recovers the hidden ranking when $q = \\omega(n^{-1/2})$, weakly recovers when $q = \\Theta(n^{-1/2})$, and no estimator succeeds when $q = o(n^{-1/2})$.","A planted ordered clique of size $c\\sqrt{n}$ is exactly recoverable in polynomial time for every constant $c > 0$."],"supporting_citations":[{"why":"Supplies the conditioning and chi-squared divergence technique that the statistical detection lower bound adapts to the planted ranked subgraph model.","marker":"[HWX15]"},{"why":"Provides the low-degree minimum mean squared error framework used to prove the computational recovery lower bound.","marker":"[SW22]"},{"why":"States the low-degree conjecture that the computational lower bounds for detection and recovery explicitly rely on.","marker":"[Hop18]"},{"why":"Provides the eigenvector perturbation bound that converts the top eigenvector of $iY$ into a recovery algorithm.","marker":"[DK70]"},{"why":"Gives the finite-rank deformation analysis of Wigner matrices used to identify the spectral detection threshold at $c > \\pi/4$.","marker":"[CDMF09]"},{"why":"Supplies the planted clique algorithmic template, including the vertex-guessing enhancement, adapted here for exact recovery of the planted ordered clique.","marker":"[AKS98]"},{"why":"Provides read-$k$ tail bounds used to control fluctuations of the Ranking By Wins estimator and its alignment value.","marker":"[GLSS15]"},{"why":"Bounds the size of the largest acyclic subset in a random tournament, used to prove uniqueness of the planted ordered clique as the maximum acyclic subset.","marker":"[SS08]"}],"fun_headline_variants":["Exact thresholds for hidden rankings in digraphs","When can algorithms find hidden rankings in directed graphs?","Hidden ranked community: exact statistical and computational limits","Exact detectability thresholds for planted ranking in directed graphs","Spotting a hidden ranking in a directed graph: exact thresholds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The computational impossibility thresholds rest on the low-degree conjecture, an unproved claim that if low-degree polynomials cannot separate the two distributions, then no polynomial-time algorithm can. If that conjecture fails for this model, the claimed computationally hard regions could actually be easy, while the statistical thresholds would still stand.","fun_headline_variants_meta":{"raw":{"variants":["Exact thresholds for hidden rankings in digraphs","When can algorithms find hidden rankings in directed graphs?","Hidden ranked community: exact statistical and computational limits","Exact detectability thresholds for planted ranking in directed graphs","Spotting a hidden ranking in a directed graph: exact thresholds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001311,"raw_usage":{"total_tokens":5440,"prompt_tokens":1138,"completion_tokens":4302,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":754,"completion_tokens_details":{"reasoning_tokens":4235}},"tokens_in":754,"tokens_out":4302,"duration_ms":28660,"temperature":1.0,"reasoning_tokens":4235,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:06:56.826800+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete falsifier would be any polynomial-time algorithm that achieves weak detection or weak recovery for some exponents with $\\beta < \\frac{2}{3}\\alpha + \\frac{1}{3}\\gamma + \\frac{1}{2}$; alternatively, one could numerically compute the low-degree advantage at degree $D = (\\log n)^{1+\\varepsilon}$ inside the claimed hard region and find it diverging, which would break the low-degree lower bound itself.","supporting_citations":[],"review_version":1}