{"id":"6e9e9841-0dcb-4aef-a10a-7c2cd6de69df","arxiv_id":"2502.06232","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"TGES extends greedy equivalence search with tiered background knowledge and is proven sound and complete in the large sample limit, while improving finite-sample recall over temporal PC.","lead":"This paper introduces TGES, a score-based causal discovery algorithm that uses tiered, typically temporal, background knowledge to orient edges in a causal graph from observational data. It proves that in the large-sample limit TGES recovers the correct restricted equivalence class of DAGs, and its simulations show better recall than the temporal PC algorithm.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"TGES's scoring step is underspecified: Algorithms 4–6 compute local score differences from parent sets of a tiered MPDAG, whose parent sets are not defined without a DAG extension; Theorem 3 may not cover a literal implementation.","rationale":"The reader's weakest assumption identifies the same point, and I agree it is the most load-bearing issue. The theorem is the central claim; it is proved for an abstract greedy search over restricted equivalence classes, but the paper's algorithms are the operational definition of TGES. The gap between the two is not cosmetic: scoring a partially directed graph requires committing to a DAG extension, and Kτ-score equivalence does not imply invariance of local score differences across extensions. If the invariance fails, a literal implementation can make different greedy moves than the proof analyzes, so the sound-and-completeness guarantee is not automatically inherited. The proof itself (Lemma 4) is detailed and largely coherent, and the empirical results are supportive, so this is not a rejection; it is a condition: specify the DAG-extension rule (or prove the local score differences are invariant) and correct Algorithm 1's orientation rule. The additional issues noted by the reader are less central: the Lemma 5 inequality can be read as applying Definition 10(ii) with the fewer-edged graph as G', and the tuning of α and λ affects the strength of empirical comparisons rather than the asymptotic theorem. Hence the verdict should remain conditional.","tokens_in":27271,"tokens_out":24987,"duration_ms":221809,"concrete_test":"Run a computational invariance check on small Gaussian examples (e.g., d=6, three tiers, n=10000, 500 random DAGs). For each tiered MPDAG encountered during TGES, score all candidate edge additions using two different DAG extensions: one obtained by orienting undirected in-tier edges in a fixed topological order, the other in the reverse order. Record the chosen move and the final tiered MPDAG. If any run selects a different move or terminates at a different graph, the pseudocode is under-specified and Theorem 3 does not apply to a literal implementation. A negative result (identical choices) would indicate a hidden invariance that the paper should still state and prove.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 guarantees that TGES returns a sound and complete estimate of the restricted Markov equivalence class. The proof (Lemmas 4–6) works with DAGs in a restricted class E^Kτ and with scores S(G, D, Kτ) defined on DAGs. But Algorithms 4, 5, and 6 (Appendix A.2) compute each candidate move as ∆s = s(Xi, Pa^W_i ∪ Y, Kτ) − s(Xi, Pa^W_i, Kτ), where W is a tiered MPDAG. A tiered MPDAG is partially directed, so its 'parent set' Pa^W_i is not uniquely defined. If an implementation takes only directed parents, it scores an object that is not a DAG and does not equal the score of any DAG in the class. If it chooses an arbitrary DAG extension, the local score differences are extension-dependent: Kτ-score equivalence fixes total scores of restricted classes, not local parent-set contributions, and two extensions of the same MPDAG can produce different ∆s for the same proposed edge. The paper never states which DAG representative is used or proves invariance. Consequently, the greedy decisions a literal implementation makes need not be the restricted-class decisions analyzed in the proof of Lemma 4, and the almost-sure guarantee of Theorem 3 is not established for the algorithm as written. A related internal inconsistency is that Algorithm 1's line 4 replaces an undirected edge {A—B} with {A→B} when {A→B} is in F, i.e. when that direction is forbidden by Kτ; taken literally, this already fails to produce a graph encoding Kτ in stage (ii).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops Temporal Greedy Equivalence Search (TGES), a score-based causal discovery algorithm that incorporates tiered background knowledge (e.g., temporal ordering) into greedy equivalence search. The authors define tiered background knowledge Kτ, restricted Markov equivalence classes, and a Temporal Bayesian Information Criterion (TBIC) with properties of Kτ-consistency, Kτ-score equivalence, and decomposability. They prove that TGES always returns a tiered MPDAG and, in the large-sample limit, a sound and complete estimate of the restricted Markov equivalence class of the true DAG. They also propose a simpler post-hoc method (STGES), present simulations comparing TGES with GES, STGES, and TPC, and apply TGES to life-course health data.","tokens_in":27489,"tokens_out":9678,"duration_ms":82856,"significance":"If the issues identified below are addressed, the paper would be a useful contribution to causal discovery with background knowledge. It provides a score-based alternative to the constraint-based temporal PC algorithm, with explicit asymptotic guarantees for restricted equivalence classes. The definitions of Kτ-consistency and the extension of GES to tiered background knowledge are natural and could be reusable by other authors. The simulation study, based on 10,000 generated DAGs, suggests practical gains in recall and overall structural Hamming distance relative to TPC, and the code is stated to be available as supplementary material. However, the current manuscript has load-bearing problems: the algorithmic pseudocode is not well-defined for partially directed graphs, one of the key subroutines contains an orientation error, and some proof steps invoke greedy search without constructing the required neighboring class.","major_comments":[{"comment":"The scoring steps in Algorithms 4–6 compute local score differences using parent sets Pa^W_i of the current tiered MPDAG W. A tiered MPDAG is partially directed, so the parent set of a node is not uniquely defined across DAGs in the restricted equivalence class. The theoretical analysis in Appendix B.6 works with DAGs G ∈ E^Kτ and scores S(G, D, Kτ), but the pseudocode scores objects that are not DAGs or relies on an unspecified choice of DAG extension. The paper neither states which DAG representative is used nor proves that the local score differences are invariant across extensions. Consequently, the greedy decisions made by an implementation that follows the pseudocode literally need not coincide with the restricted-class decisions analyzed in Lemma 4, and Theorem 3 is not established for the algorithm as written. The authors should specify how a DAG extension is selected and maintained (e.g., by keeping a current DAG in the class alongside the tiered MPDAG) and prove that the scoring comparisons are well-defined.","section":"Appendix A.2, Algorithms 4–6; Section 5.2"},{"comment":"Algorithm 1 (Restrict PDAG according to Kτ) contains an orientation error: line 4 replaces an undirected edge {A—B} with {A→B} when {A→B} ∈ F. Since F contains exactly the edges with τ(A) > τ(B), the forbidden direction is A→B, so the undirected edge should be oriented as B→A. As written, Algorithm 1 returns a PDAG that contradicts Kτ. This subroutine is used in Stage (ii) of TGES and in STGES, so Lemma 3, which asserts that each TGES step results in a tiered MPDAG, relies on a procedure that, taken literally, fails to produce a graph in agreement with Kτ. This is likely a typo, but it must be corrected and the downstream effects checked.","section":"Section 4, Algorithm 1"},{"comment":"The proofs of Lemma 2 and Lemma 5 derive contradictions by comparing the current equivalence class with the true DAG G* and then invoking greediness. For example, in Lemma 2, the argument states that if the resulting class E′ is not in agreement with Kτ, then all DAGs in E′ contradict Kτ, so by Kτ-consistency (iii) S(G*,D,Kτ) > S(G′,D,Kτ), and 'since GES is greedy' this is a contradiction. However, G* is not necessarily a neighboring equivalence class of E′, and the greedy algorithm only moves to neighboring classes with higher scores. A valid proof must construct a specific neighboring class with a higher score, as is done for the unconstrained case in Chickering [2003]. The same issue appears in the backward-phase proof of Lemma 5 when it asserts that the score 'has decreased' without identifying the neighboring class. This gap affects Lemma 1 and the proof of Theorem 3. (On a related point, the reader's concern that Definition 10(ii) implies the opposite inequality in Lemma 5 does not land: with G′ in Definition 10(ii) assigned to the fewer-edge graph tilde G* and G assigned to G′, the inequality S(tilde G*) > S(G′) is exactly what Definition 10(ii) yields. The remaining problem is the missing neighbor construction, not the inequality direction.)","section":"Appendix B.5, Lemma 2; Appendix B.6.2, Lemma 5"}],"minor_comments":[{"comment":"The codomain of τ is written as {1,...,T}^d; it should be {1,...,T}.","section":"Definition 1"},{"comment":"The statement of Theorem 2 says STGES results in a CPDAG and estimates the Markov equivalence class, but the proof concludes a tiered MPDAG and the restricted Markov equivalence class. Since a non-empty Kτ generally produces orientations beyond the CPDAG, the stated theorem is false as written. The proof indicates the intended correct statement, which should be reflected in the theorem statement.","section":"Theorem 2 and Appendix B.3"},{"comment":"The tuning of λ so that TGEStuned has exactly the same number of edges as the expert DAG uses the gold standard to select a hyperparameter. This makes the reported confusion matrices and p-values partly a product of fitting to the reference graph. The authors should clearly state that this is an illustrative calibration and not an unbiased evaluation of TGES.","section":"Section 7"},{"comment":"The abstract says the tiered MPDAG 'contains the true DAG' in the large sample limit, while Theorem 3 more precisely states that the tiered MPDAG is a sound and complete estimate of the restricted Markov equivalence class of the true DAG. The looser wording may mislead readers about the identifiability of individual DAGs.","section":"Abstract and Section 5.2"},{"comment":"The instruction 'W ← CPDAG of W' is ambiguous when W is a tiered MPDAG rather than a DAG. The authors should specify whether the CPDAG is computed from a DAG extension of W and how that extension is chosen.","section":"Algorithms 4–6, line 7"},{"comment":"The sentence 'we know that Kτ /∈ PaG_Y' appears to contain a typo and should read 'we know that K /∈ PaG_Y'.","section":"Appendix B.6.1, Case D.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a statistics or machine learning journal. The main novelty is modest (a direct extension of GES to tiered background knowledge), but the formalization of restricted equivalence classes and the simulation study are useful. The most important fix is the specification of how scores are computed when the current graph is a tiered MPDAG; the authors may also want to consult how similar issues are handled in Hauser and Bühlmann's score-based algorithms for interventional classes. The code is mentioned as supplementary material but was not accessible in the manuscript text; I could not verify the reproducibility claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"TGES is a genuine contribution: a score-based temporal extension of GES that incorporates tiered background knowledge, with a plausible asymptotic guarantee and a large simulation study. It should go to peer review, but the pseudocode needs to be cleaned up before the algorithm as written can be said to satisfy the theorem.\n\nNew and well done: TGES and its Temporal BIC (which sends any graph contradicting the tier ordering to −∞) are not in the earlier work by Bang & Didelez or Witte. The proof appendix adapts Chickering’s machinery to restricted Markov equivalence classes, and the theoretical derivation builds on external results rather than circling. The simulation study is substantial—10,000 DAGs—and shows TGES with a more balanced precision-recall trade-off than TPC, which matches the known GES-vs-PC pattern. The authors are also honest about limitations: Gaussian misspecification on the binary Metropolit data, the manual tuning of TPC and of the λ penalty, and the open question of general background knowledge are all acknowledged in Section 8.\n\nOne reader concern does not stand up. The alleged inequality error in Lemma 5 is not an error. Kτ-consistency (ii) gives a higher score to the graph with fewer edges; the proof uses that exactly, comparing the pre-addition graph against the final graph. So that part is fine.\n\nThe real problems are elsewhere. First, Algorithms 4–6 compute local score differences using parent sets of the current tiered MPDAG. A tiered MPDAG is only partially directed, so parent sets are not defined without choosing a DAG extension. The paper never states which extension is used or why the local differences are invariant. A literal implementation could make greedy moves that are not the ones analyzed in Lemma 4. This is fixable by specifying a representative or proving invariance, but as it stands there is a gap between the proof and the pseudocode. Second, Algorithm 1 looks like it has a sign error: when {A→B} is in the forbidden set F, the text says to replace {A—B} with {A→B}, which would orient the edge in the forbidden direction. The intended line must be {B→A}. This is an easy correction, but it is a concrete error.\n\nThe empirical comparisons are weakened by tuning: TGEStuned’s λ is chosen to match the expert graph’s edge count, and TPC’s α is chosen after seeing the metrics. The authors acknowledge this, so I read it as a moderate limitation rather than a deceptive one.\n\nWho this is for: anyone doing score-based causal discovery with temporal or tiered structure, and applied researchers in life-course epidemiology who want an alternative to TPC. I would cite it and would bring it to a causal-inference reading group. It deserves a serious referee; the requested revisions should be about clarity and correctness of the pseudocode, not about reworking the core theory.","headline":"TGES is a genuinely new temporal extension of GES with a solid proof appendix; the main fixable problem is that the pseudocode leaves the DAG representative underlying the scoring step unspecified.","tokens_in":28166,"tokens_out":6809,"would_cite":true,"duration_ms":56319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62D20","62H05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A temporal extension of score-based causal discovery, TGES, is proven to always return a tiered MPDAG and to recover the true restricted equivalence class in the large-sample limit.","keywords":["causal discovery","score-based learning","temporal background knowledge","tiered MPDAG","Greedy Equivalence Search","Temporal Bayesian Information Criterion","Markov equivalence class","observational data"],"falsifier":"On simulated Gaussian data from a known DAG with clear tiers, implement TGES exactly as in Algorithms 4–6 without adding any DAG-extension rule, and check whether the returned tiered MPDAG converges to the true restricted equivalence class as the sample size grows; if the output depends on the arbitrary representative used to read parent sets, or systematically misses the true class in the limit, the claimed guarantee fails for the published pseudocode.","tokens_in":26926,"feed_emoji":"🕒","tokens_out":7122,"duration_ms":56955,"temperature":0.7,"pith_summary":"This paper develops Temporal Greedy Equivalence Search (TGES), a score-based causal discovery algorithm that exploits temporal information encoded as tiers over variables: causes cannot point backward in time. The central claim is that TGES always terminates in a tiered maximally oriented partially directed acyclic graph (tiered MPDAG), and that in the large-sample limit this output is almost surely sound and complete, representing exactly the restricted Markov equivalence class containing the true data-generating DAG. The authors introduce the Temporal Bayesian Information Criterion (TBIC), a scoring criterion with the consistency, decomposability, and score-equivalence properties needed for the proof. The practical motivation is that temporal knowledge improves both orientation and adjacency recovery; simulations show TGES achieves better recall with comparable precision than the temporal PC algorithm, and a real-world example on life-course health data demonstrates its use.","feed_headline":"TGES provably recovers the true causal class when time is tiered","feed_subtitle":"Uses temporal tiers to orient edges, always returns a tiered MPDAG, and recovers the truth in the limit.","key_machinery":"The machinery is the tiered MPDAG together with the TBIC score and a three-stage greedy step. Tiered background knowledge Kτ forbids directed edges from later to earlier tiers; restricting a CPDAG by Kτ and applying Meek's rule 1 yields a tiered MPDAG, a partially directed graph representing a restricted Markov equivalence class. Each TGES step scores neighboring CPDAGs with TBIC, orients all undirected cross-tier edges according to the tier ordering, then closes under Meek's rule 1. TBIC is decomposable, Kτ-score equivalent, and Kτ-locally consistent, so local score differences can be computed from parent sets of the current graph; these properties are what let the classical GES proof be carried over to the restricted setting.","core_discovery":"The paper's central result, Theorem 3, is that TGES using a score that is Kτ-score equivalent, decomposable, Kτ-consistent, and Kτ-locally consistent produces a tiered MPDAG, and as n → ∞ this tiered MPDAG is almost surely a sound and complete estimate of the restricted Markov equivalence class of the true data-generating DAG. Equivalent statements are proved for each phase: the forward phase adds edges until every graph in the class is an independence supergraph of the truth, the backward phase removes edges until class equality is reached, and the turning phase provably makes no harmful changes once the class is correct. The paper also proves that TBIC, which is BIC with a −∞ penalty for any graph contradicting the tier ordering, satisfies all required properties for Gaussian data.","pith_inferences":["If the asymptotic guarantee holds, temporal tiers shrink the restricted equivalence class, which should make subsequent procedures such as causal-effect bound estimation tighter; the paper notes the class is smaller but does not quantify this gain.","The proof's reliance on reading parent sets from a partially directed graph leaves open a choice of DAG extension; different implementations of that choice may change finite-sample behavior even if the limit is unaffected.","The tier constraint affects only orientations, yet simulations show adjacency recovery improves as well; a possible explanation is that correct orientations prevent score-based searches from chasing wrong conditional-independence patterns, a mechanism worth testing directly.","Extending TGES to non-Gaussian or mixed data should be possible by using the paper's recipe with a suitable consistent score, which would make temporal score-based discovery applicable to the broader data types common in epidemiology."],"forward_implications":["TGES always returns a tiered MPDAG, so the output represents a well-defined class of DAGs and supports downstream causal-inference machinery for MPDAGs.","In the large-sample limit, the algorithm recovers the restricted Markov equivalence class of the true DAG almost surely, matching GES's guarantee while exploiting temporal constraints.","Any consistent, decomposable, finite score criterion can be turned into a temporal one by assigning −∞ to graphs contradicting Kτ, so the result extends beyond Gaussian BIC to other score families.","Finite-sample simulations indicate TGES has considerably better recall of adjacencies than the temporal PC algorithm with comparable precision, giving a more balanced precision-recall trade-off.","On a life-course health dataset, TGES finds significantly more correct adjacencies than random guessing, with direction agreement on most of the shared edges."],"supporting_citations":[{"why":"Supplies the GES algorithm and the lemmas and theorems on score equivalence, decomposability, consistency, and sound-and-complete structure learning that TGES adapts.","marker":"Chickering [2003]"},{"why":"Provides the four orientation rules used to close a restricted PDAG into a maximally oriented graph, including the rule that TGES applies after tier restriction.","marker":"Meek [1995]"},{"why":"Defines tiered background knowledge and establishes that applying Meek's rule 1 after tier restriction yields a tiered MPDAG.","marker":"Bang and Didelez [2023]"},{"why":"Formalizes MPDAGs and gives the Algorithm 1 restriction step that turns a CPDAG into a PDAG respecting Kτ.","marker":"Perkovic et al. [2017]"},{"why":"Supplies the BIC score on which TBIC is built, giving the consistent, decomposable base score.","marker":"Schwarz [1978]"},{"why":"Provides the life-course health dataset, the expert consensus DAG, and the TPC comparison used in the real-data application.","marker":"Petersen et al. [2023a]"}],"fun_headline_variants":["TGES provably nails the true causal class using tiered time","Tiered time boosts causal discovery: TGES provably recovers truth","TGES: tiered background knowledge guarantees correct DAG class","Score-based causal discovery with time tiers: TGES provably wins","TGES uses temporal tiers to provably recover the causal graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the greedy score differences are computed from parent sets that are well-defined for the current partially directed graph, but Algorithms 4–6 do not specify how a DAG representative of the tiered MPDAG is chosen for scoring, and different choices could change the greedy path.","fun_headline_variants_meta":{"raw":{"variants":["TGES provably nails the true causal class using tiered time","Tiered time boosts causal discovery: TGES provably recovers truth","TGES: tiered background knowledge guarantees correct DAG class","Score-based causal discovery with time tiers: TGES provably wins","TGES uses temporal tiers to provably recover the causal graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000624,"raw_usage":{"total_tokens":2851,"prompt_tokens":869,"completion_tokens":1982,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":1905}},"tokens_in":485,"tokens_out":1982,"duration_ms":11277,"temperature":1.0,"reasoning_tokens":1905,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T16:18:09.974480+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On simulated Gaussian data from a known DAG with clear tiers, implement TGES exactly as in Algorithms 4–6 without adding any DAG-extension rule, and check whether the returned tiered MPDAG converges to the true restricted equivalence class as the sample size grows; if the output depends on the arbitrary representative used to read parent sets, or systematically misses the true class in the limit, the claimed guarantee fails for the published pseudocode.","supporting_citations":[{"cited_title":"Causal inference and causal explanation with background knowledge","cited_arxiv_id":null,"evidence_quote":"Provides the four orientation rules used to close a restricted PDAG into a maximally oriented graph, including the rule that TGES applies after tier restriction."},{"cited_title":"Interpreting and using cpdags with background knowledge","cited_arxiv_id":null,"evidence_quote":"Formalizes MPDAGs and gives the Algorithm 1 restriction step that turns a CPDAG into a PDAG respecting Kτ."}],"review_version":1}