{"id":"17e67b1d-6c39-4672-a6fa-38efb39a3313","arxiv_id":"2608.04909","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The minimax risk of any network experiment under arbitrary neighborhood interference is a function of the conflict graph of observable exposures, with rates bounded by the graph's independence number, critical degree, and spectral radius.","lead":"This paper works out the fundamental statistical limits of network experiments, where one person's treatment can affect their neighbors: the best possible estimation accuracy is controlled by a 'conflict graph' of potential outcomes that can never be observed together.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hölder bounds in Lemmas C.7 and C.9 are undefined at q=2, leaving the second-moment upper bound unproven as written.","rationale":"The reader's conditional verdict already flags the variance bounds C.7–C.9 as needing independent checking; my concern is a concrete instance of that. I do not find a flaw in the conflict-graph reduction or Proposition A.6 after close reading: the iterative construction in A.6 is consistent because any disagreement on common extended neighborhoods would create a conflict, and the injectivity assertion is not needed for the reductions. The informal Corollaries 1.1 and 1.2 drop a '+1' term, which is a real but readily fixable presentation error that the reader already captured. The most load-bearing unresolved issue is the missing q=2 case in the Hölder arguments of Theorem 4.1's proof. Since the reader's verdict is CONDITIONAL and this concern is a proof gap rather than a counterexample, the verdict should remain unchanged.","tokens_in":64765,"tokens_out":27393,"duration_ms":284478,"concrete_test":"Independently re-derive Lemma C.7 for q=2 without using the q/(q−2) Hölder step; compute the claimed bound ∑ x_i^2/p_i ≤ 2Ce^{1/C} λ(H) for a vector with ∥x∥_2=1 and p_i=1/(2λ(H)) on a star graph. If the proof cannot be completed, Theorem 4.1's q=2 claim is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.1, the upper-bound half of the central claim, rests on the variance estimates in Lemmas C.7–C.9. The proofs of these lemmas invoke Hölder's inequality with conjugate exponent q/(q−2), e.g., in Lemma C.7: ∑ x_i^2/p_i ≤ (∑ x_i^q)^{2/q} (∑ p_i^{-q/(q-2)})^{(q-2)/q}. For q=2, the exponent q/(q−2) is undefined and the inequality degenerates to ∑ x_i^2/p_i ≤ (∑ x_i^2) (max 1/p_i)^0, which is false when p_i are unequal. Since q=2 is the primary second-moment case and Theorem 4.1 is stated for all q≥2, the proof as written does not establish the upper bound for q=2. The same issue appears in Lemma C.9 and propagates to the bias-variance tradeoff Theorem 4.2, which inherits Theorem 4.1. A separate argument for q=2 (e.g., the spectral bound in Kandiros et al. 2024) would repair this, but it is not present.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops a design-based minimax theory for estimating contrastive causal effects under arbitrary neighborhood interference on a known network. The central object is a conflict graph whose vertices are the estimand-relevant exposures and whose edges join exposures that cannot be observed in a single intervention. The main structural result (Proposition 2.2) shows that the minimax risk depends on the network and effect only through this conflict graph, via a reduction to a minimax problem over maximal independent sets. The paper then derives lower bounds using Le Cam's method (in terms of large induced independent sets and a critical degree) and upper bounds using a generalized Conflict Graph Design and a bias-variance tradeoff governed by a regularized induced-subgraph objective. Applications to the direct treatment effect and the global average treatment effect yield bounds in terms of the original graph and its two-hop graph, respectively. Tightness results for d-regular and random d-regular graphs are given, and conjectures about computational hardness are discussed.","tokens_in":64881,"tokens_out":9916,"duration_ms":106107,"significance":"If the results hold, this is a substantial contribution to the design-based network experiment literature. It provides the first general lower bounds on the minimax risk for network experiments, offering a benchmark relative to which existing procedures can be evaluated. The conflict graph characterization is elegant and appears to be a genuine reduction, not a restatement of the conclusion; the appendix reductions are detailed and the framework-level arguments appear sound. The upper bounds improve on prior work for q>2, and the bias-variance tradeoff yields better rates under degree heterogeneity. The paper is technically careful, with explicit constants and structured appendix proofs. The main reservation is a gap in the proof of the upper bound at q=2, which is central but likely repairable.","major_comments":[{"comment":"The proofs of Lemmas C.7 and C.9 apply Hölder's inequality with conjugate exponent q/(q−2), which is undefined at q=2. The displayed inequality in Lemma C.7, ∑ x_i^2/p_i ≤ (∑ x_i^q)^{2/q} (∑ p_i^{-q/(q-2)})^{(q-2)/q}, degenerates at q=2 and is false when the p_i are unequal. Since Theorem 4.1 is stated for all q≥2 and the proof of the theorem does not supply a separate argument for q=2, the upper-bound half of the central claim is not established as written for q=2. This gap propagates to Theorem 4.2 and Proposition 4.3, which inherit Theorem 4.1. The paper should either add a self-contained q=2 argument (for instance, the spectral argument used in Kandiros et al., 2024) or explicitly restrict the formal proof to q>2 and note that the q=2 case follows from that cited result.","section":"Section C.1, Lemmas C.7 and C.9; Theorem 4.1"}],"minor_comments":[{"comment":"There are several typos: \"casual\" should be \"causal\" in the proof sketch of Theorem 3.2, \"constrastive\" should be \"contrastive\" in the proof of Proposition 2.2, and \"MMSE\" should be \"MSE\" in the proof of Proposition 4.3.","section":"Throughout, e.g., Section A.5 and Section C.3"},{"comment":"The proof sketch considers a simplified estimand written as a sum of the two potential outcomes rather than a contrast; this is helpful for intuition but should be labeled clearly as a non-contrastive surrogate, since the formal statement concerns contrastive effects.","section":"Section 3.2, proof sketch of Theorem 3.2"},{"comment":"The final sentence says the bound \"yields the lower bound in the statement,\" but the derivation establishes the upper bound on the minimax risk; this should be corrected.","section":"Appendix D.2, proof of Corollary D.2"}],"recommendation":"major_revision","confidential_remarks":"The only substantive issue is the q=2 gap in the upper-bound proof. Given that the q=2 rate was already established in Kandiros et al. (2024), the authors should be able to close the gap by importing that result explicitly or adding a short separate argument. I did not find other load-bearing errors; the conflict-graph reduction appears sound. The paper fits the scope of math.ST and is likely to have high impact in the network experiments community."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kandiros, Harshaw, and Sävje have written a serious paper. The core idea—that the minimax risk for a contrastive effect under arbitrary neighborhood interference depends on the network only through the conflict graph—is genuinely new and I believe it holds. I went through the reduction in Appendix A.5 and the chain of lemmas is sound; the equivalence to the maximal independent set problem is not a hand-wave. The lower bounds in Sections 3.2 and 3.3 are also new in this design-based setting, and the Le Cam machinery that adapts to the design is worth having on its own. The related work is fair, and the conjectures in Section 6 are honestly labeled as conjectures.\n\nThat said, there is a proof gap that matters. Theorem 4.1 is stated for all q ≥ 2, but Lemmas C.7 and C.9 use Hölder's inequality with exponent q/(q−2), which is undefined at q=2. The displayed bound for x^T T^(0) x fails for q=2 when the p_i are unequal. Since the q=2 case is exactly the one used in Corollaries 1.1 and 1.2 and in the informal Main Result, the upper bound for the second-moment problem is not established by the proof as written. This is fixable—the q=2 result is already in Kandiros et al. (2024), so the authors could cite that and handle q=2 separately—but it has to be fixed before publication.\n\nSmaller issue: the main-text Corollaries 1.1 and 1.2 write λ(G)/n and λ(G2)/n, but the appendix versions need (λ(G)+1)/n and (λ(G2)+1)/n. For an empty graph the main-text rate is 0, which is obviously wrong. Presentation bug, easy to fix.\n\nThe paper has no data or code, so reproducibility is about proof completeness. The lower-bound and reduction proofs are the strongest part. I did not check every inequality in Lemma B.4 or the finite-geometry construction in Proposition 5.2; those are intricate enough that a referee should ask for details.\n\nWho gets value: anyone working on design-based causal inference, network experiments, or minimax theory for inverse problems. It deserves a serious referee. My recommendation: send it out, but with an explicit request to (1) repair the q=2 upper-bound argument, and (2) align the main-text corollaries with the appendix.","headline":"A real minimax benchmark for network experiments with a clean conflict-graph reduction and new lower bounds, but the q=2 upper-bound proof is incomplete as written and the main-text corollaries drop a needed +1.","tokens_in":65536,"tokens_out":5003,"would_cite":true,"duration_ms":55813,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62C20","62K99","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"One graph determines the minimax risk of network experiments.","keywords":["network experiments","causal inference under interference","minimax risk","conflict graph","arbitrary neighborhood interference","design-based inference","treatment effect estimation"],"falsifier":"Compute the exact minimax risk by brute force on a small network, such as a five-vertex star with the direct treatment effect at $q=2$: the paper's bounds predict $\\Theta(1/n)$, so an exact value that is not between the stated lower and upper bounds would refute the characterization.","tokens_in":64432,"feed_emoji":"🕸️","tokens_out":10869,"duration_ms":116865,"temperature":0.7,"pith_summary":"This paper asks how accurately a network experiment can estimate a causal effect when the interference network is known in advance and the researcher may choose any design and any estimator. It establishes that under arbitrary neighborhood interference, the minimax mean-squared error depends on the network and the effect only through the conflict graph $H$, whose vertices are the estimand-relevant exposures and whose edges connect pairs of exposures that no treatment vector can reveal together. The main result bounds this risk as $\\max(1/|I(H)|,\\sqrt{d^*(H)}/n) \\lesssim R(G,\\tau,q) \\lesssim \\min_S Q(S,H)/n$, where $I(H)$ is the independence number, $d^*(H)$ is the critical degree, and $Q(S,H)$ is a regularized induced-subgraph objective. When specialized to the direct treatment effect and the global average treatment effect, the bounds become explicit rates in terms of the network and its two-hop graph, and for regular graphs both bounds are tight.","feed_headline":"One graph determines the minimax risk of network experiments","feed_subtitle":"It gives a benchmark that says which designs are near the fundamental limit.","key_machinery":"The central object is the conflict graph $H$, whose $2n$ vertices are the estimand-relevant potential outcomes and whose edges join two exposures that cannot be observed in the same treatment assignment. The engine of the reduction is the equivalence between treatment vectors and independent sets of $H$: every realized treatment reveals an independent set of exposures, and every maximal independent set is exactly realizable by some treatment vector. This turns the experimental design problem into a minimax problem over measures on maximal independent sets. The lower bounds adapt Le Cam's method with design-adaptive mixtures of potential outcome functions, and the upper bounds are achieved by the Conflict Graph Design, an importance-ordered rule for resolving exposure conflicts, refined by deleting a small set of conflicted vertices to trade bias against variance.","core_discovery":"The paper's central claim is that the fundamental statistical limit of a network experiment is a graph-theoretic quantity: for every contrastive estimand and moment restriction $q$, the minimax risk $R(G,\\tau,q)$ equals $f_q(H)$, where $H$ is the conflict graph and $f_q$ is defined through a minimax problem over probability distributions on maximal independent sets of $H$. The paper does not identify $f_q$ in closed form, but it proves two-sided bounds that capture the minimax rate: independent-set structure gives the global lower bound, the critical degree gives the local lower bound, and a generalized Conflict Graph Design with a bias-variance tradeoff gives the upper bound. For the direct treatment effect the conflict graph is essentially the original network, while for the global average treatment effect it is close to the two-hop network, which is why the former is provably easier to estimate.","pith_inferences":["If the conflict-graph characterization extends to other exposure-mapping models, the same recipe gives a plug-in diagnostic: build $H$, compute its independence number, critical degree, and spectral objective, and read off whether a proposed design is near the fundamental limit.","The conjectured NP-hardness of computing $f_q(H)$ implies that exact minimax benchmarking may be infeasible in general; a natural next step, suggested but not developed in the paper, is a computationally efficient minimax rate that restricts procedures to polynomial time.","The DTE-GATE gap suggests an interpolation: estimands whose conflict graphs sit between $G$ and $G^2$, such as $k$-hop spillover effects, should have minimax rates interpolating between the two rates on regular graphs.","The bias-variance deletion idea implies that on heavy-tailed networks, deliberately ignoring the most conflicted exposures can recover parametric rates despite high-degree hubs; this could be tested by simulating the design on observed degree distributions."],"forward_implications":["No design or estimator can achieve worst-case mean-squared error below $\\max(1/|I(H)|,\\sqrt{d^*(H)}/n)$, so any procedure reaching the upper bound is minimax rate-optimal on that network and effect.","For the direct treatment effect, the minimax rate is between $\\max(1/|I(G)|,\\sqrt{d_{\\mathrm{avg}}(G)}/n)$ and $\\lambda(G)/n$; for the global average treatment effect it is between $\\sqrt{d_{\\mathrm{avg}}(G^2)}/n$ and $\\lambda(G^2)/n$, so on random regular graphs the DTE is strictly easier than the GATE.","Stronger moment restrictions make the rate smaller, and on degree-heterogeneous conflict graphs the optimal procedure may delete a few central exposures: on a star at $q=2$, removing the center changes the rate from $n^{-1/2}$ to $n^{-1}$.","A polynomial-time approximation of the optimal deletion set achieves the upper bound up to a $\\log^{2-2/q} n$ factor, so the benchmark is computable in practice.","On a uniformly random $d$-regular graph, the minimax rate for the direct effect is $d/n$ up to logarithmic factors, giving an average-case benchmark for network experiments."],"supporting_citations":[{"why":"Introduces the conflict graph and Conflict Graph Design and proves the earlier $\\lambda(H)/n$ upper bound that this paper generalizes and complements with statistical lower bounds.","marker":"Kandiros et al. (2024)"},{"why":"Defines design-based exposure-mapping models, the framework within which arbitrary neighborhood interference is formalized.","marker":"Aronow and Samii (2017)"},{"why":"Provides the potential-outcome formulation for interference that contrastive estimands such as DTE and GATE build on.","marker":"Hudgens and Halloran (2008)"},{"why":"Supplies Le Cam's method, which the paper adapts to design-based settings to prove its lower bounds.","marker":"Yu (1997)"},{"why":"Provides the general design-based framework used to place the minimax definition in a wider setting.","marker":"Harshaw, Sävje, and Wang (2022)"},{"why":"Gives the independence-number bounds for random regular graphs used to characterize DTE risk on typical graphs.","marker":"Cooper et al. (2002)"},{"why":"Supplies generalized quadrangles, the graph family used to show the lower bound is tight.","marker":"Payne and Thas (2009)"}],"fun_headline_variants":["Conflict graph sets the minimax limit for network experiments","Network experiment limits tied to a single conflict graph","Minimax risk of network experiments is graph-defined","Conflict graph bounds the precision of network experiments"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire reduction rests on the assumption that outcomes depend on treatment only through each unit's exposure---the treatment pattern in its extended neighborhood---and that every maximal set of pairwise compatible exposures can be realized by some unconstrained treatment vector; if outcomes respond to more distant treatments, or if the design class forbids some treatment vectors, the conflict graph may not capture the minimax risk.","fun_headline_variants_meta":{"raw":{"variants":["Conflict graph sets the minimax limit for network experiments","Network experiment limits tied to a single conflict graph","Minimax risk of network experiments is graph-defined","Conflict graph bounds the precision of network experiments"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1463,"prompt_tokens":876,"completion_tokens":587,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":527}},"tokens_in":492,"tokens_out":587,"duration_ms":5854,"temperature":1.0,"reasoning_tokens":527,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:56:29.545447+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact minimax risk by brute force on a small network, such as a five-vertex star with the direct treatment effect at $q=2$: the paper's bounds predict $\\Theta(1/n)$, so an exact value that is not between the stated lower and upper bounds would refute the characterization.","supporting_citations":[],"review_version":1}