{"id":"aa4b68e3-914b-4e6f-9ad5-0d532b83bd6a","arxiv_id":"2502.07857","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SNAP repeatedly removes variables that cannot be ancestors of the targets, so targeted causal effects can be learned from a much smaller causal graph.","lead":"SNAP is a new algorithm that learns only the part of a causal network needed to estimate effects between a few chosen variables, pruning away unrelated variables as it goes. It can run alone or speed up existing causal discovery tools, and tests show large reductions in computation time and statistical tests without hurting effect estimates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SNAP(1) soundness proof applies Lemma B.3 with mismatched conditioning statements; the k=1 case of Theorem 3.1 is therefore not established as written.","rationale":"The reader identified Lemma B.3/B.4 as the most fragile step; I agree and sharpen it to a concrete variable-substitution mismatch in the proof of Lemma B.4. Reading in good faith, the high-level ideas are plausible: the possibly ancestral set argument in Lemma 3.1 is sound, SNAP(∞) uses RFCI for i≥2 and has a more secure proof, and the code plus extensive experiments are real supporting evidence. I did not find a counterexample to Lemma B.3 itself by inspection, so I am not claiming the theorem is false. But the written proof of the k=1 case does not follow from the stated lemma, and the k=1 case is exactly what justifies SNAP(1) prefiltering and Corollary 3.1 for the most used variant. This is an internal correctness risk, not a dispute about consensus, and it warrants a condition on acceptance: the authors should either prove the intended implication directly, correct the lemma invocation, or add a formal verification. The reader's CONDITIONAL verdict remains appropriate, so no verdict change is needed.","tokens_in":52799,"tokens_out":19414,"duration_ms":182378,"concrete_test":"Run an exhaustive d-separation check over all DAGs on n≤6 nodes (enumerating with networkx and an oracle d-separation routine) for Lemma B.3 and for the specific implication used in Lemma B.4: if X̸⊥Z, X⊥W|{V}, and X⊥Z|{W}, does X⊥Z|{V}? If a counterexample exists, instantiate it as a SNAP(1) run with T containing Z and verify whether a true possible ancestor is pruned. If the implication holds in all enumerated DAGs, the proof gap is expositional and Theorem 3.1 remains credible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that SNAP prunes only definite non-ancestors of the targets. For k=1, Theorem 3.1 depends on Lemma B.4, which needs the two RFCI dependencies X⊥⊥Z|sepset(X,Y) and Z⊥⊥Y|sepset(X,Y). When sepset(X,Y)={W} and W is not adjacent to X, the proof invokes Lemma B.3 as: 'if X̸⊥⊥Z, X⊥⊥W|{V} and X⊥⊥Z|{W}, then X⊥⊥Z|{V}'. Lemma B.3 as stated has antecedents X̸⊥Y, X⊥Y|Z, Z⊥Y|W and conclusion X⊥Y|W. Substituting (X,Y,Z,W) := (X,Z,W,V) requires W⊥Z|V as the third antecedent, not X⊥W|V. The displayed implication is therefore not an instance of Lemma B.3. The same mismatch recurs in the finite-chain argument of Lemma B.4. If the intended implication is false, SNAP(1) can orient an unshielded triple as a v-structure even though the center is a true possible ancestor of a target, and line 15 can then prune a node that belongs to PossAn(T), contradicting Theorem 3.1 for k=1. Since SNAP(1) is a recommended prefilter and the experiments rely heavily on low-order SNAP variants, this gap is load-bearing. SNAP(∞) for i≥2 uses RFCI orientation and may be unaffected, but the prefiltering corollary for k=1 is not backed by the supplied proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses targeted causal effect estimation with an unknown graph: rather than learning a full CPDAG over all variables, it proposes to learn only a subgraph over a possibly ancestral superset of the possible ancestors of a small target set T. The central claim is that definite non-ancestors of T are unnecessary both for identifying causal relations among targets and for finding valid and efficient adjustment sets. The proposed SNAP(k) algorithm interleaves a PC-style skeleton search with orientation of v-structures and iterative pruning of nodes that have no possibly directed path to T; SNAP(∞) adds Meek rule completion and is claimed to return exactly the induced CPDAG over PossAn(T). The paper gives oracle soundness/completeness theorems (Theorems 3.1 and 3.2), a worst-case complexity analysis, and extensive experiments on synthetic data and two real benchmark networks.","tokens_in":53051,"tokens_out":8050,"duration_ms":76093,"significance":"If the oracle claims are correct, the paper makes a useful step: it formalizes a targeted discovery task and shows that only possible ancestors of the target set need to be retained, building on known ancestral-set preservation results of Lauritzen and Guo et al. The paper is strong on framing, has extensive experiments with several CI test families, reports both computational and effect-estimation metrics, and releases code. No fitted constants or circularity in the main theorems was found. However, the k=1 soundness proof contains a concrete gap in the appendix, and Theorem 3.2 and the prefiltering Corollary 3.1 rely on that k=1 case. Because SNAP(1) and SNAP(∞) are central to the paper's practical claims, this gap is load-bearing and prevents accepting the paper in its current form.","major_comments":[{"comment":"The proof of the k=1 case applies Lemma B.3 with a substitution that does not fit the lemma's statement. Lemma B.3 states: if X and Y are d-connected given the empty set, X⊥d Y | Z, and Z⊥d Y | W, then X⊥d Y | W. In Lemma B.4, to conclude X⊥d Z | {V}, the proof requires the third antecedent to be W⊥d Z | {V}. Instead, the displayed implication uses X⊥d W | {V}. Thus the claimed derivation is not an instance of Lemma B.3, and the same mismatch recurs in the 'two successive applications' argument later in the same proof. As written, the k=1 case of Theorem 3.1 is not established, and since Theorem 3.2 and Corollary 3.1 depend on Theorem 3.1, the central soundness claim that SNAP(1) prunes only definite non-ancestors is not backed by the supplied proof.","section":"Appendix B, Lemma B.4"},{"comment":"The repeated-application argument in Lemma B.4 is an inductive chain over non-adjacent nodes, but each step invokes the same unmatched form of Lemma B.3. Even if the intended implication 'X⊥d Z|{W}, X⊥d W|{V}, X not⊥d Z implies X⊥d Z|{V}' were true, it is not proved in the paper; the proof as written is therefore incomplete for every iteration in the chain, not just the first step. The authors should either state and prove the correct auxiliary lemma, or modify the algorithm so that the RFCI dependency checks are also used at iteration k=1.","section":"Appendix B, Lemma B.4 and Theorem 3.1"},{"comment":"The paper itself reports that, in finite samples, missing edges in SNAP(∞)'s output arise not from type II CI-test errors but from pruning the wrong nodes. This is an honest limitation statement, but it should be weighed explicitly against the abstract's unqualified claim that pruning is done without compromising estimation quality. The oracle theorems are not contradicted by this finite-sample behavior, but the main text should state that the 'prunes only definite non-ancestors' guarantee holds only with oracle CI tests, and that finite-sample SNAP can remove true possible ancestors, with the experimental support for the no-compromise claim resting on intervention distance rather than structural fidelity.","section":"Appendix D.9"}],"minor_comments":[{"comment":"The theorem says a set is possibly ancestral, 'i.e., PossAn_G(\\hat V_i) ⊆ \\hat V_{i+1}'. The displayed condition is stronger than the definition of \\hat V_{i+1} being possibly ancestral, which should be PossAn_G(\\hat V_{i+1}) ⊆ \\hat V_{i+1}. The proof establishes the stronger statement, but the wording is imprecise.","section":"Theorem 3.1"},{"comment":"The conclusion refers to 'SNAP(1), a stand-alone sound and complete discovery algorithm', while the rest of the paper defines SNAP(∞) as the sound and complete stand-alone algorithm. This appears to be a typo and should be corrected.","section":"Section 3.2 / Section 6"},{"comment":"In the proof of Corollary 3.1, the sentence 'from the application of Theorem 3.1, that shows that a possibly ancestral set...' should presumably refer to Lemma 3.1, not Theorem 3.1.","section":"Appendix B.3"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful idea and extensive experiments, and the mismatch in Lemma B.3/B.4 looks repairable rather than fatal. If the authors can supply a correct proof of the k=1 orientation step, or adjust the algorithm to use RFCI-style checks at k=1 while preserving the claimed complexity, I would be willing to accept a revised version. The finite-sample pruning caveat in App. D.9 should also be reflected in the main text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nSNAP is worth a serious look: it makes targeted causal effect estimation scale to larger graphs by pruning definite non-ancestors, and it ships code, oracle proofs, and extensive experiments. The claim that possible ancestors of the targets are all you need for both structure and adjustment sets is the right kind of claim, and the reduction to an induced CPDAG on a possibly ancestral set is cleanly imported from Lauritzen and Guo et al. The SNAP(∞) variant, with RFCI orientation and Meek completion, is plausibly sound and complete over the possible ancestors, and the empirical gains in CI tests and runtime are consistent across synthetic and real data.\n\nThe soft spot is real and load-bearing. Theorem 3.1 for k=1 rests on Lemma B.4, which invokes Lemma B.3 with mismatched conditions. Lemma B.3 says: if X and Y are marginally dependent, X⊥Y|Z, and Z⊥Y|W, then X⊥Y|W. In the k=1 proof, after sepset(X,Y)={W}, the text invokes Lemma B.3 as: if X̸⊥⊥Z, X⊥⊥W|{V} and X⊥⊥Z|{W}, then X⊥⊥Z|{V}. Substituting the lemma's variables, the third antecedent would need to be W⊥Z|{V}, not X⊥W|{V}. The displayed implication is not an instance of the lemma. The finite-chain argument repeats the same mismatch. So as written, the k=1 case of Theorem 3.1 is not established. Since SNAP(1) is recommended as a prefilter and the experiments lean on low-order SNAP variants, this is not a cosmetic issue. SNAP(∞) for i≥2 uses RFCI's explicit dependency checks and likely survives, but the prefiltering corollary for k=1 needs a corrected proof or a restricted statement.\n\nOther issues are minor by comparison: the conclusion calls SNAP(1) a stand-alone sound-and-complete algorithm when that is SNAP(∞); App. D.9 admits finite-sample SNAP prunes some true possible ancestors, and the signed intervention-distance plots contradict the absolute-value definition in App. C.3. The authors should reconcile those before publication.\n\nBottom line: this is a useful paper with a real proof gap. I would send it to referees, ask for the k=1 lemma to be fixed or the k=1 claims downgraded, and let the method stand on SNAP(0) prefiltering plus SNAP(∞).","headline":"Useful targeted causal discovery method, but the k=1 soundness proof has a concrete lemma-application gap that needs fixing before the prefiltering claims are credible.","tokens_in":53631,"tokens_out":4081,"would_cite":true,"duration_ms":39205,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62D20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The full causal graph is unnecessary for targeted effect estimation: a sequential pruning algorithm that keeps only possible ancestors of the targets recovers exactly the relevant CPDAG.","keywords":["targeted causal effect estimation","causal discovery","possible ancestors","non-ancestor pruning","conditional independence tests","CPDAG","adjustment sets","causal sufficiency"],"falsifier":"Enumerate all labeled DAGs on four nodes and check Lemma B.3 directly: any quadruple $(W, X, Y, Z)$ in which $X$ and $Y$ are d-connected given the empty set, $X \\perp\\!\\!\\!\\perp_d Y \\mid Z$ and $Z \\perp\\!\\!\\!\\perp_d Y \\mid W$ both hold, but $X \\perp\\!\\!\\!\\perp_d Y \\mid W$ fails, is a counterexample that collapses the order-1 soundness proof. A complementary end-to-end check is to run SNAP(1) with oracle d-separation tests over all DAGs up to six nodes and all possible target sets, recording the first graph in which a true possible ancestor of a target is pruned.","tokens_in":52538,"feed_emoji":"✂️","tokens_out":14284,"duration_ms":109293,"temperature":0.7,"pith_summary":"The paper takes on targeted causal effect estimation with an unknown graph: the user names a small set of target variables and wants the interventional effects between them, without learning the full causal graph over all variables. Its central claim is that only the possible ancestors of the targets — variables that could lie on a causal path into a target in some graph consistent with the data — are needed for this task, both to orient the causal relations among targets and to form statistically efficient adjustment sets. The paper proves that a possibly ancestral superset of these variables supports exactly the same restricted CPDAG and the same adjustment sets as the full graph, and it contributes SNAP, an algorithm that alternates low-order conditional-independence search with v-structure orientation and prunes definite non-ancestors at every step. In experiments with oracle and finite-sample tests, SNAP cuts the number of independence tests and the computation time by large factors while keeping causal effect estimates comparable to global discovery.","feed_headline":"Causal estimates need possible ancestors, not the full graph","feed_subtitle":"SNAP prunes irrelevant variables, cutting independence tests and runtime while preserving adjustment sets.","key_machinery":"The central object is the set of possible ancestors of the targets. In a CPDAG $G$, a node $X$ is a possible ancestor of $Y$ when a possibly directed path connects them — a path made of undirected edges and edges pointing toward $Y$ — which is equivalent to $X$ being an ancestor of $Y$ in at least one DAG of the Markov equivalence class. The load-bearing identity is Lemma 3.1: a possibly ancestral set $V^*$ that contains $\\mathrm{PossAn}(T)$ induces the same CPDAG as the full graph restricted to $V^*$, so discovery can be confined to $V^*$ without losing any informative adjustment set. The algorithm's mechanism is a loop that runs a PC-style skeleton search with conditioning sets of size $i$, orients v-structures (using PC rules for $i \\in \\{0,1\\}$ and RFCI-style rules with extra dependency checks for $i \\geq 2$, because low-order tests can create conflicting v-structures even when the underlying edge is real), and then removes every node with no possibly directed path to a target. The safety of the cheap PC-style orientation at order 1 rests on a d-separation lemma about treks (Lemma B.3), applied repeatedly.","core_discovery":"The paper establishes that definite non-ancestors of the targets are unnecessary for learning causal relations among the targets and for identifying efficient adjustment sets. Theorem 3.1 states that, given oracle conditional independence tests, every iteration of SNAP(k) retains all possible ancestors of the targets and leaves a possibly ancestral set, one that contains all of its own possible ancestors. Lemma 3.1 then guarantees that any possibly ancestral set containing the targets' possible ancestors yields the same canonical, parental, ancestor, and asymptotically optimal adjustment sets as the full CPDAG. Theorem 3.2 completes the picture: SNAP(∞), the standalone variant, returns exactly $\\hat{G} = G|_{\\mathrm{PossAn}(T)}$, the induced subgraph of the full CPDAG over the possible ancestors of the target set, and is sound and complete over that subgraph. The upshot is that recovering the complete CPDAG over all variables is not required for targeted causal effect estimation; the relevant subgraph suffices, and pruning can happen during discovery rather than after it.","pith_inferences":["My inference: the 'possible ancestors are all you need' principle should carry over to causally insufficient settings, where the analogous object is the set of nodes possibly ancestral to the targets in a partial ancestral graph; the paper names this as future work, and nothing in Lemma 3.1 depends essentially on causal sufficiency.","My inference: SNAP's prefiltering is agnostic to the downstream method, so it should combine equally well with score-based discovery, where the reduced variable set also shrinks the search space over DAGs.","My inference: the paper's own finite-sample diagnostics (App. D.9) find more missing than extra edges and attribute them to pruning the wrong nodes, which suggests that a confidence-aware pruning rule — keeping nodes whose possible-ancestor status is borderline — could close the gap between the oracle soundness guarantee and finite-sample behaviour; the paper does not pursue this.","My inference: Lemma B.3 is a purely discrete statement about d-separation, so exhaustive enumeration over all four-node DAGs would certify or refute it outright, a check that costs almost nothing and would settle the most fragile step of the proof."],"forward_implications":["Stopping SNAP(k) at any order and running a sound-and-complete discovery algorithm on the survivors returns the induced subgraph of the full CPDAG restricted to those variables, so all informative adjustment sets for the target effects are preserved (Corollary 3.1).","Even SNAP(0), which prunes purely on marginal-independence information, already cuts independence tests and runtime by large factors as a prefilter in the reported experiments, and it consistently improved PC, MARVEL, and MB-by-MB* across settings.","SNAP(∞) as a standalone method recovers exactly the induced CPDAG over $\\mathrm{PossAn}(T)$, and its worst-case complexity of $O(|V|^{d_{\\max}+2} + |V|^4)$ matches PC's $O(|V|^{d_{\\max}+2})$ for graphs with maximum degree at least 2.","SNAP's cost is nearly constant as the number of targets grows, because all targets are handled jointly, whereas local methods that process targets one at a time degrade substantially with more targets.","Because SNAP concentrates its independence tests at low orders, it avoids high-order conditional-independence tests, which are statistically weaker for kernel-based and $\\chi^2$ tests."],"supporting_citations":[{"why":"Supplies the variable-elimination result (their Lemma D.1) that non-ancestors of the outcome are uninformative, which Lemma 3.1 extends from ancestral sets to possibly ancestral sets.","marker":"Guo et al. [2023]"},{"why":"Provides the RFCI algorithm (Algorithm 4) whose extra dependency checks keep v-structure orientation sound when only low-order CI tests are available.","marker":"[Colombo et al., 2012]"},{"why":"Establishes that conflicting v-structures produced by low-order CI tests imply non-adjacency in the true CPDAG, motivating the orientation and pruning strategy.","marker":"[Wienöbst and Liskiewicz, 2020]"},{"why":"Defines the PC algorithm whose skeleton search, orientation routine, and worst-case complexity SNAP adapts.","marker":"[Spirtes et al., 2000]"},{"why":"Defines the canonical adjustment set in Markov equivalence classes, the object the paper uses to argue possible ancestors suffice for valid adjustment.","marker":"[Perković et al., 2018]"},{"why":"Defines the asymptotically optimal adjustment set as the parents of nodes on possibly directed paths, a subset of the possible ancestors of the outcome.","marker":"[Henckel et al., 2022]"},{"why":"Supplies Proposition 3.22 on ancestral sets and induced subgraphs, used in the proof of Lemma 3.1.","marker":"[Lauritzen, 1996]"}],"fun_headline_variants":["SNAP prunes non-ancestors, keeps the essential graph","Targeted causal effects: SNAP finds only the necessary subgraph","SNAP: prune non-ancestors to get causal estimates faster","Skip irrelevant variables: SNAP keeps adjustment sets intact","Don't learn the whole graph: SNAP prunes for targeted effects"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The soundness guarantee assumes oracle conditional-independence tests, and within that idealization the fragile step is Lemma B.3, a d-separation implication about treks that lets SNAP orient v-structures cheaply at order 1; if that implication fails in any configuration, a true possible ancestor of the targets could be mislabeled as a definite non-ancestor and pruned.","fun_headline_variants_meta":{"raw":{"variants":["SNAP prunes non-ancestors, keeps the essential graph","Targeted causal effects: SNAP finds only the necessary subgraph","SNAP: prune non-ancestors to get causal estimates faster","Skip irrelevant variables: SNAP keeps adjustment sets intact","Don't learn the whole graph: SNAP prunes for targeted effects"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001292,"raw_usage":{"total_tokens":5274,"prompt_tokens":943,"completion_tokens":4331,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":4240}},"tokens_in":559,"tokens_out":4331,"duration_ms":27641,"temperature":1.0,"reasoning_tokens":4240,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:56:10.106978+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all labeled DAGs on four nodes and check Lemma B.3 directly: any quadruple $(W, X, Y, Z)$ in which $X$ and $Y$ are d-connected given the empty set, $X \\perp\\!\\!\\!\\perp_d Y \\mid Z$ and $Z \\perp\\!\\!\\!\\perp_d Y \\mid W$ both hold, but $X \\perp\\!\\!\\!\\perp_d Y \\mid W$ fails, is a counterexample that collapses the order-1 soundness proof. A complementary end-to-end check is to run SNAP(1) with oracle d-separation tests over all DAGs up to six nodes and all possible target sets, recording the first graph in which a true possible ancestor of a target is pruned.","supporting_citations":[{"cited_title":"Variable elimination, graph reduction and the efficient g-formula","cited_arxiv_id":null,"evidence_quote":"Supplies the variable-elimination result (their Lemma D.1) that non-ancestors of the outcome are uninformative, which Lemma 3.1 extends from ancestral sets to possibly ancestral sets."},{"cited_title":"Recovering causal structures from low-order conditional independencies","cited_arxiv_id":null,"evidence_quote":"Establishes that conflicting v-structures produced by low-order CI tests imply non-adjacency in the true CPDAG, motivating the orientation and pruning strategy."},{"cited_title":"Graphical criteria for efficient total effect estimation via adjustment in causal linear models","cited_arxiv_id":null,"evidence_quote":"Defines the asymptotically optimal adjustment set as the parents of nodes on possibly directed paths, a subset of the possible ancestors of the outcome."},{"cited_title":"Graphical models, volume 17","cited_arxiv_id":null,"evidence_quote":"Supplies Proposition 3.22 on ancestral sets and induced subgraphs, used in the proof of Lemma 3.1."}],"review_version":1}