acceptodds
Under review as a conference paper at ICLR 2027

Optimal Correction Sets for Provable Redress of Contestable Causal Discovery

Abstract

Constraint-based causal discovery relies on conditional-independence (CI) tests that may conflict in finite samples, leaving no causal graph that satisfies them all. Causal Assumption-based Argumentation (ABA) makes these tests explicit as defeasible commitments, and offers correspondence guarantees with a subset of them, but its existing repair procedure releases facts heuristically and offers no formal response to a user's contestation of a release. We argue that contestable causal discovery requires an inspectable repair object, a justification for it, and a predictable revision procedure for such contestations. We therefore formulate CI-fact repair as a minimum-cost correction problem and implement it in Answer Set Programming (ASP). Building on Causal ABA, we provide a compact and efficient ASP encoding of causal consistency, with soundness and completeness guarantees, and a two-way projection correspondence between optimal stable models and minimum-cost correction sets. These results establish fidelity to retained facts, subset-minimality and cost optimality of the repair, conflict-based justifications for released facts, and formally guaranteed redress under user contestations. An empirical evaluation supports the formal account: OptABA-PC retains more correct CI statements, reduces ambiguity in the compatible output causal graphs, while keeping competitive reconstruction performance on common benchmarks with limited number of nodes.

Primary area:
causal reasoning
Keywords:
Hybrid Causal Discovery, Argumentation, Answer Set Programming, Optimal Repair, Contestability, Explainability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_G4vDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper casts conflicting finite-sample CI evidence as minimum-cost correction-set optimization. It proves projection correspondence between optimal stable models and optimal correction sets, graph fidelity to retained facts, and hard-retention/release-cost contestability properties. A Bayes-ball encoding replaces explicit active-path enumeration.

Critical strengths
  1. Inspectable repair objects and logical guarantees are valuable beyond returning a graph alone. Optimal-model projections, conflict certificates, and contestability margins form a coherent audit interface, instantiated by exact small-graph forced-retention evaluations
  2. The controlled ABA-PC comparison and encoding ablation are reasonable. Repair methods share CI traces, weights, and Bayes-ball encoding, while Table 4 isolates the encoding change and shows substantial eight-node speedups.
Critical weaknesses

1.It is unclear which theoretical guarantees are new relative to existing weighted constraint optimization methods. The contribution is clearer in how repairs are exposed and computed. 2.Differences in inputs and weights complicate some baseline comparisons. The small graphs and incomplete solver runs also limit the evidence for reliability and scalability.

Questions for authors
  1. Please clarify: With identical CI facts, strictly positive weights, and DAG space, do the authors agree with the optimal-cost and violation-set/correction-set equivalence above? If not, please give a counterexample. If so, which guarantee cannot be obtained from the previous weighted encoding with explicit violation-set output and a forced-retention re-solve?
  2. Please add additional comparison: On the existing exactly solvable small-graph subset, can both encodings use identical facts and weights, comparing optimal projections, retention-contestation outputs, and runtime to isolate encoding/interface gains?
  3. Please clarify: Can proven-optimal and incumbent subsets be reported separately, with complete set counts and generating-MEC coverage on fully enumerable cases? Please avoid interpreting full-trace failure on infeasible inputs as comparative weakness.
2 comments

Thank you for the constructive questions.

W1/Q1: equivalence and guarantees. The common response addresses your correspondence and novelty query by relating weighted violations to releases and transferring our Thm. 2 to ASPCR's DAG encoding through the keep/fail construction. Our two-way projection, private conflicts and hard/graded revision guarantees make the abstract's contestability claim explicit: an expert can inspect, challenge and revise CI commitments with predictable consequences. Under the common response's assumptions, their CI-only objective is an instance of our general framework. Objective atoms can also encode weighted structural commitments, retaining conflict explanations and revision guarantees for feasible protections.

W2/Q2: matched comparison. Results Table R1 compares timings on our partial PC/MPC trace; the repair/contestation block compares projections and revisions on that evidence. This controls evidence acquisition, which differs between our partial-trace and ASPCR's native full-test pipelines. An additional link to Tables 12–13 is that matched ASPCR retains exactly the same facts as OptABA on all 400 original inputs, so their fact-count/PP/RR/F1F_1 rows coincide.

W2/Q3: optima, incumbents and complete graph sets. Results Table R2 separates cost attainment from proof by budget. We also audited the original 400 saved outputs through additional rebuttal solves. We now certify the minimum cost for 397, including 29 of the original 32 timeouts. Three remain valid repairs without a minimum-cost certificate. Below are group means of the original fact scores (Table 13). Correct kept % and False kept % use Table 12's per-run counts, divided by all recorded tests in that run before averaging.

Original solveCost proved in auditnnFact PPFact RRFact F1F_1Correct kept %False kept %
All397/400400.908.960.93284.257.88
FinishedYes368.910.962.93384.807.74
TimeoutYes29.897.953.92478.769.00
TimeoutNo3.835.859.84670.3113.76

The next table combines original solve status, rebuttal cost certification, and compatibility with the generating MEC. The last two columns count repairs whose retained CI facts all agree with the generating DAG; by Cor. 1, exactly then its MEC remains among the compatible models. This checks inclusion, not unique recovery.

DatasetFinished/timeoutProved cost /50Opt true MEC /50ABA true MEC /50
Cancer50/05059
Earthquake50/0504646
Survey50/05003
ER550/0502322
SF550/0503530
Asia48/25000
ER831/194888
SF839/1149210

Table 18's graph counts are those found before the enumeration limit, even when the repair is proved optimal. For ten Survey and ten ER5 inputs, we fixed the CI statements retained by each method under the baseline settings (N=5,000N=5{,}000, α=.01\alpha=.01, original weights), then enumerated every DAG satisfying those statements. This completely enumerates the graph family of one selected repair per method per input, rather than all optimal repairs. The table gives medians over ten inputs per dataset; all enumerations finished and all twenty OptABA repairs are proved optimal.

DatasetMethodMedian DAGsMedian MECsTrue MEC /10
SurveyOptABA1.51.00
ABA952.0458.50
ER5OptABA6.01.54
ABA8.52.05

We will add the certification audit to App. G.3 and complete-family results to App. G.4, clarifying Table 18's budgeted counts. These are the same baseline inputs used in YbLS Q4: that table measures average reconstruction accuracy, while this one reports set size and whether the exact generating MEC is included. On Survey both exclude the true MEC, despite OptABA's much smaller set; a small set alone does not establish truth.

W2/Q3: full-trace failure (Tables 5/18). We agree that an infeasible full CI trace cannot be satisfied by any DAG. Table 18 tests every native outcome for ASPCR/MPC, but only retained outcomes for ABA/OptABA. We will make that distinction explicit and remove the inference that positive full-trace disagreement means ASPCR provides no consistent repair. The matched experiment instead checks each output against its retained evidence. Table 7's 8/88 MPC failures on feasible traces remain a different, avoidable enforcement gap.

We are happy to provide any additional clarification.

Reviewer_G4vDOpenReview ↗

Reply

I appreciate the replies. But the theoretical advance and the evidence for scalability still remain unclear to me. So I will maintain my score.

Reviewer_BVwLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper addresses a common problem in constraint-based causal discovery, that with finite samples, the conditional-independence tests can contradict each other, so that no causal graph satisfies all of them. Building on Causal ABA, the authors cast the repair of these conflicts as a minimum-cost correction problem. The cheapest set of test outcomes is released, with costs derived from the tests’ p-values, and the problem is formulated for exact ASP optimization. They prove that optimal solutions correspond to minimum-cost correction sets, give a Bayes-ball encoding of d-separation, justify each released fact by a conflict it takes part in, and show that a user who contests a release, by forcing a fact to be kept or raising its cost, gets a predictable revised answer. On benchmarks with at most eight variables, the method keeps more correct test outcomes and returns fewer compatible graphs than the original heuristic, ABA-PC, but its graph reconstruction is generally weaker than that of standard baselines such as MPC and FGS.

Critical strengths
  • The problem is well motivated, Finite-sample CI tests often contradict each other for various reasons, including noise in measurements and, in most constraint-based methods, an inability to resolve these contradictions. Making the repair a calculated approach with justification is a worthwhile goal.

  • Clean and correct formulations and developments, and all the theorems, lemmas, and propositions are correct, to the best of my knowledge.

  • The method can guarantee consistency among solutions returned.

  • Interesting engineering contribution to causal ABA by replacing pass enumeration with Bayes-ball encoding making the original framework substantially faster.

Critical weaknesses
  • My main concern is that of the novelty. The core optimization is not new. The method seems to be a variation of CI-violation objective of Hyttinen et al. (2014) restricted to DAGs with the same facts and weights. Hyttinen et al. (2017) already compute such sets by core-guided hitting sets. So the claims in App. G.3 that ASPCR has “no counterpart of Prop. S.1” and offers “no consistent repair” are incorrect.

  • Borboudakis & Tsamardinos (2016) already encode Bayes-Ball in ASP for semi-Markov models with selection, a larger class than DAGs; the paper cites them only for greedy constraint selection. Hyttinen et al. (2014) also avoid path enumeration, and the classical linear-time d-separation algorithms (Geiger, Verma & Pearl, 1990) are not cited.

  • The theoretical results are correct but largely standard. Lemma 1, Theorem 1 and Prop. 1 restate known facts about soft-constraint optimisation and MUS/MCS hitting-set duality. The contestability properties (Properties 1–2, Prop. 2, Prop. S.1) are elementary monotonicity facts about a minimum when one cost rises or one constraint is added.

  • Example 3 is incorrect. ABA-PC’s nine retained facts are satisfied by four Markov-equivalent DAGs (an undirected path E–I–O–R), not “one compatible DAG with one correct edge”. This contradicts the paper’s own Corollary 1 and App. G.1, and makes the comparison in Example 6 misleading.

  • Several citations are inaccurate:


    • Reiter (1987) and Liffiton & Sakallah (2008) are cited for “diagnosis of ASP programs”, though neither concerns ASP.
    • Gebser et al. (2011) is the wrong reference for clingo.
    • Hung et al. (1997) does not support the claim about p-values near α.
    • Hyttinen et al. (2014) do not return PAGs.
    • Russo et al. used Fisher-Z at α = 0.05, not G² at α = 0.01 as the paper states for “the Causal ABA setting”.
    • Rapberger et al. (2024) is not the standard ABA–ASP correspondence result and does not cover the disjunctive rule in Listing 2.
Questions for authors

With the same CI facts and weights, how does your objective differ from the DAG-restricted objective of Hyttinen et al. (2014)?


Borboudakis & Tsamardinos (2016) already encode Bayes-Ball in ASP for semi-Markov models with selection, and Hyttinen et al. (2014) use a d-connection encoding that avoids path enumeration. What is new in your Bayes-ball encoding relative to these works?

2 comments

Thank you for the careful technical review.

W1/W3/Q1: native ASP construction and general explanations. Hyttinen et al. (2017) reuse the 2014 causal encoding in MaxSAT, adding domain-specific cores, incremental extraction, dynamic clause activation and bounds-based hardening to speed up SAT/IP solving. Our opt\mathsf{opt} operator compiles repair into native ASP: each optimal Causal ABA stable model yields an MCS and a compatible DAG. Their Thm. 1 validates seven core patterns; our Thm. 1/Prop. 1 apply to arbitrary finite ASP programs and objective atoms. Generic MUS extraction can recover present pattern instances, when minimal, and other conflicts. We deliberately expose release-specific witnesses and repair/graph projections for expert inspection.

Because the 2017 method reuses the 2014 consistency encoding, the transfer in the common response covers both. Under its DAG and positive-weight assumptions, our framework gives the guarantees of our Thm. 2 for that encoding: minimum-cost MCSes, corresponding graphs satisfying retained facts, a private MUS for each release, and realisation of every optimal MCS. Hard retention and cost revision transfer too. This makes their encoding usable in our expert-guided revision framework, including for partial PC/MPC evidence. We will correct App. G.3's exclusivity claims and clarify Sect. 5.2/App. E and Sect. 2.

W2/Q2: Bayes-ball. Our contribution here is the implementation improving Causal ABA. We will credit ETIO's existing ASP Bayes-ball encoding (Borboudakis & Tsamardinos, 2016), Hyttinen et al. (2014)'s avoidance of path enumeration, and Geiger, Verma & Pearl (1990). Our DAG module uses two arrival states and contracts ETIO's observed-descendant traversal through ancestor-of-observation closure: for X→C←YX\to C\leftarrow Y, C→DC\to D, conditioning on DD opens CC via that closure. We will add a line-by-line rule comparison in App. B.2. Table 4 (App. G.2) holds the repair policy fixed: mean runtime is .38 of the old path-enumerating core on Survey and .03–.05 at eight nodes.

W4: Examples 3/6, Cor. 1 and App. G.1. Thank you for identifying the error: Example 3 admits all four DAGs in the E−I−O−RE-I-O-R MEC. Cor. 1 characterises the DAGs satisfying retained facts; it does not assert uniqueness. All four satisfy ABA-PC's nine facts, so the corrected example does not contradict it. App. G.1's example is unaffected: the repair and its costs do not depend on that mistaken count. In Example 6 the optimisation reduces the compatible DAGs from four to one, hence reduces orientation uncertainty; it does not correct an orientation compelled by ABA-PC. We will amend Examples 3 and 6 accordingly.

W5: ABA–ASP correspondence. We will add Bondarenko et al. (1997) and Caminada & Schulz (2017) for the classical flat ABA/normal-LP correspondence, retaining Rapberger et al. (2024) for its non-flat/negated-head generalisation. Thank you for identifying Listing 2's disjunction: it is outside Rapberger's result. We can replace line 1 by normal rules. For each node pair X<YX<Y, write a=arrow(X,Y), b=arrow(Y,X) and n=no_edge(X,Y), a fresh atom for no edge. The first two atoms denote the two orientations:

a :- not b, not n. b :- not a, not n. n :- not a, not b.

Their stable choices are a\\{a\\}, b\\{b\\}, n\\{n\\}. We will add this lemma to App. B.1: for Listings 1–4, replacement preserves stable-model projections on the original atoms, selected facts and costs. Each pair has the same three choices; the fresh no_edge atoms occur nowhere else, and the remaining closures/constraints accept the same graphs. Thus both generators represent every DAG, as required by Russo et al.'s Prop. 3.3. With the unchanged CI constraints, Lemma 2 ensures each represented graph satisfies the enforced facts; conversely every DAG satisfying them extends to a model. This is Cor. 1's two-way CI–DAG fidelity. We will use this normalisation in Apps. C/E and clarify the citation's scope.

W5: citation/settings corrections. We will replace “diagnosis of ASP programs” with “diagnosis of logic-based systems” for Reiter (1987) and Liffiton & Sakallah (2008). The Gebser et al. (2011) citation will point to Potassco: The Potsdam Answer Set Solving Collection (doi:10.3233/AIC-2011-0491). Hyttinen et al.'s output will be described as causal graphs, including cycles, rather than PAGs. We will remove Hung et al. (1997), retain Casella & Berger (2002), and add Gelman & Stern (2006) and Boos & Stefanski (2011) for the revised wording “decisions near α\alpha can be unstable” and its reproducibility implications. As you note, “Following Russo et al.” at the start of Sect. 6 can suggest identical settings. We will qualify that opening and App. G.2's “Causal ABA setting”: we reuse the benchmark design, but use G2G^2/α=.01\alpha=.01 rather than Russo et al.'s Fisher-Z/α=.05\alpha=.05.

We are happy to provide any additional clarification.

Thank you for the detailed response and additional experiments. The common response and your response to my review settled my main question. With identical facts and positive weights and DAG constraints, the optimal repairs and graph coincide with the DAG-restricted objective of Hyttinen et al. (2014). The corrections to Examples 3 and 6, plus the citations and graphs generator edits resolve my soundness concerns. However, this confirms that the optimization and its guarantees are not specific to the proposed method. The remaining contributions seem modest for ICLR, so I will keep my score.

Reviewer_YbLSOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper develops OptABA-PC, an answer-set programming approach to repairing inconsistent conditional-independence test outcomes in causal discovery. It minimizes the positive weighted cost of released facts and returns compatible causal graphs together with explicit correction sets. The formal results establish the correspondence between optimal stable models and optimal correction sets, explanations through minimal inconsistent subsets, and the response to increasing a fact's release cost or requiring its retention. A Bayes-ball encoding replaces active-path enumeration. Experiments on eight small network settings compare optimal and heuristic repair, graph reconstruction, encoding efficiency, and forced-fact sensitivity. The main empirical contribution is better repair under a declared objective and a more explicit contestation interface; graph-estimation accuracy remains mixed against external baselines.

Critical strengths
  1. Precise and inspectable repair guarantees. The paper defines the retained evidence, released facts, compatible graphs, and contestation operations explicitly. The optimality correspondence is correctly stated under projection rather than as a bijection. Positive release costs justify subset minimality, and the private inconsistency witnesses explain why each released fact conflicts with the retained set. The scope of single-fact enforcement is clearly identifiable.
  2. Strong controls for the principal implementation changes. OptABA-PC and ABA-PC repair the same recorded tests with the same weights. The matched encoding ablation in Table 4 isolates the Bayes-ball change while retaining the heuristic repair policy, producing identical retained-fact and model counts on completed pairs and large runtime reductions at eight nodes. The broader comparison uses 50 matched seeds per dataset and reports uncertainty and multiplicity-adjusted paired tests. The appendices also acknowledge cases where more correct facts are retained alongside more false ones.
Critical weaknesses
  1. The novelty relative to weighted graph-disagreement optimization needs a sharper account. Appendix G.3 describes ASPCR-DAG as minimizing the weighted cost of facts contradicted by a graph and successfully performs 4,330 hardening probes. For the same admissible DAG family, facts, and positive weights, a graph's contradicted facts define a feasible correction set, suggesting a close optimization relationship to the proposed objective. The explicit repair object, explanation machinery, and user-facing redress semantics are useful contributions. However, different traces and weights in the reported ASPCR comparison prevent isolating the contribution of those choices, and the claim that hardening is not redress needs a more precise semantic justification.
  2. The computational evidence remains limited to very small graphs. Primary experiments use five to eight nodes, and 32 of 400 OptABA-PC solves reach the time limit without proved optimality. The returned incumbents remain valid repairs, but the optimality-based guarantees do not automatically apply to them. Compatible graph sets are also enumerated under a separate budget, so their reported sizes and average reconstruction scores characterize saved outputs rather than necessarily complete sets. Scaling curves and explicit optimality/enumeration status would clarify where the method is usable.
  3. Repair optimality does not resolve statistical reliability of the retained evidence. The paper acknowledges that weights encode preferences rather than calibrated probabilities. On Survey, correct retained facts increase from 24.8 to 29.7, but false retained facts increase from 2.4 to 13.4 and Fact F1 falls from 0.789 to 0.742 (Tables 9 and 12). Thus a smaller compatible set can accompany a less accurate evidence set. Evaluation at a single sample size and test threshold leaves sensitivity to the weight mapping and CI-test reliability insufficiently characterized.
Questions for authors
  1. Under matched facts, positive weights, and admissible DAGs, what is the exact equivalence or difference between OptABA-PC and weighted graph-disagreement minimization? Which redress guarantees require the additional representation?
  2. Can the ASPCR comparison include a matched-input objective, while retaining the native-input comparison as a separate end-to-end result?
  3. Can you report scaling beyond eight nodes, optimality gaps for timeout incumbents, and enumeration completeness or budget sensitivity for the graph-set statistics?
  4. How do retained-fact precision, recall, and graph recovery vary with sample size, CI threshold, and release-weight mapping, particularly on Survey?
  5. What happens when several facts are protected simultaneously, or background graph constraints are added? Please distinguish infeasible requests from the stated totality result for one valid fact.
1 comment

Thank you for the constructive review.

W1/Q1: equivalence and redress. The common response relates the objectives and transfers Thm. 2 to ASPCR, clarifying correspondence, novelty and the link between contestability, inspectable repairs and guaranteed revision. App. G.3 uses hardening to probe sensitivity; redress treats enforcement as commitment revision. With matched facts, weights and DAG constraints, hardening used for revision implements hard-retention redress.

W1/Q2: matched inputs. Table 3 lists the original settings; Table 18 reports native-pipeline outcomes. Results Table R1 fixes the CI trace, weights, DAG space and timing scope to compare the encodings.

W2/Q3: scaling, gaps and enumeration. Results Table R1 extends scaling to 100 ER/SF10 inputs (600 s) and 25 Sachs11 samples (1800 s); R2 separates cost attainment from proof across ten-node budgets. OptABA attains 46/50 certified ten-node costs (mean gap .97%, max 17.24%); 50 optima remain unknown. Sachs: 8/25 attained, mean gap 87.97%, max 297.95%. Both attain all 147 known costs among 150 eight-node inputs by 300 s. Table 18's enumeration cap can leave compatible graphs uncounted; complete counts are in G4vD Q3 and below.

W3/Q4: cost, α\alpha and sample-size sensitivity. We report seven settings on ten simulated datasets each from Survey and ER5. Original uses N=5,000N=5{,}000, α=.01\alpha=.01. Every OptABA repair is proved optimal; we enumerated every compatible DAG/MEC for each method's selected repair. We will add it to App. G.4.

Unit sets release costs to one (ABA keeps its original ordering). ETIO costs uses posterior-confidence weights derived from MPR (Maximum Posterior Ratio), introduced by Triantafillou & Tsamardinos (2015, Sect. 4.3) and used by ETIO, while keeping the original G2G^2 decisions. ABA uses the transformed confidence ordering. Changing α\alpha or NN changes the CI outcomes/queries.

Fact PP is the fraction of retained tests agreeing with the generating DAG; Fact RR is the fraction of correct recorded tests retained. Entries are mean ±\pm sample SD across ten datasets. Graph F1F_1 averages reconstruction scores over compatible MECs, then datasets.

DatasetMethodSettingFact PPFact RRGraph F1F_1
SurveyOptABAOriginal.720±.075.720\pm.075.878±.066.878\pm.066.468±.145.468\pm.145
Unit.667±.098.667\pm.098.825±.120.825\pm.120.275±.204.275\pm.204
ETIO costs.697±.139.697\pm.139.833±.145.833\pm.145.425±.177.425\pm.177
α=.05\alpha=.05.769±.093.769\pm.093.893±.044.893\pm.044.510±.202.510\pm.202
α=.10\alpha=.10.771±.076.771\pm.076.875±.050.875\pm.050.525±.140.525\pm.140
N=1,000N=1{,}000.329±.130\mathbf{.329\pm.130}.945±.095.945\pm.095.171±.168\mathbf{.171\pm.168}
N=10,000N=10{,}000.748±.033.748\pm.033.850±.039.850\pm.039.591±.154.591\pm.154
ABAOriginal.907±.061.907\pm.061.700±.109.700\pm.109.380±.188.380\pm.188
Unit.907±.061.907\pm.061.700±.109.700\pm.109.380±.188.380\pm.188
ETIO costs.872±.178.872\pm.178.733±.156.733\pm.156.313±.215.313\pm.215
α=.05\alpha=.05.943±.033\mathbf{.943\pm.033}.715±.092.715\pm.092.402±.194.402\pm.194
α=.10\alpha=.10.946±.037.946\pm.037.688±.079.688\pm.079.374±.159.374\pm.159
N=1,000N=1{,}000.416±.218\mathbf{.416\pm.218}.892±.157.892\pm.157.212±.191.212\pm.191
N=10,000N=10{,}000.949±.031.949\pm.031.773±.034.773\pm.034.355±.185.355\pm.185
ER5OptABAOriginal.942±.072.942\pm.072.982±.031.982\pm.031.465±.371.465\pm.371
Unit.931±.089.931\pm.089.973±.053.973\pm.053.478±.426.478\pm.426
ETIO costs.928±.089.928\pm.089.970±.055.970\pm.055.421±.400.421\pm.400
α=.05\alpha=.05.932±.080.932\pm.080.980±.027.980\pm.027.507±.371.507\pm.371
α=.10\alpha=.10.918±.085.918\pm.085.982±.019.982\pm.019.579±.297.579\pm.297
N=1,000N=1{,}000.867±.114.867\pm.114.977±.035.977\pm.035.525±.268.525\pm.268
N=10,000N=10{,}000.959±.055.959\pm.055.985±.023.985\pm.023.584±.370.584\pm.370
ABAOriginal.961±.072.961\pm.072.970±.036.970\pm.036.551±.389.551\pm.389
Unit.961±.072.961\pm.072.970±.036.970\pm.036.551±.389.551\pm.389
ETIO costs.961±.072.961\pm.072.962±.046.962\pm.046.551±.389.551\pm.389
α=.05\alpha=.05.940±.081.940\pm.081.955±.049.955\pm.049.508±.353.508\pm.353
α=.10\alpha=.10.930±.087.930\pm.087.947±.059.947\pm.059.488±.362.488\pm.362
N=1,000N=1{,}000.883±.113.883\pm.113.903±.152.903\pm.152.450±.359.450\pm.359
N=10,000N=10{,}000.971±.036.971\pm.036.973±.040.973\pm.040.561±.346.561\pm.346

Bold marks changes from the same method’s Original (paired two-sided Wilcoxon; BH over the original tested family per dataset/method/metric, q<.05q<.05). On Survey, N=1,000N=1{,}000 reduces fact precision for both methods and graph F1F_1 for OptABA; α=.05\alpha=.05 increases ABA fact precision. No other tested changes reach q<.05q<.05. Graph F1F_1 measures partial reconstruction.

Q5 — protections/background knowledge. Joint protections can conflict, e.g. opposite CI outcomes or X⊥YX\perp Y together with X→YX\to Y. A MUS identifies the minimal conflicting data/expert commitments for revision (Prop. 1). If feasible, optimisation returns the cheapest repair satisfying protections and background knowledge. Prop. 2/App. F guarantees totality for one valid fact over unrestricted DAGs; arbitrary joint requests may be infeasible. That said, our formulation also naturally supports structural commitments carrying release costs which is an interesting future direction.

We are happy to provide any additional clarification.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Common response: objective correspondence, novelty and redress

We thank all reviewers for the constructive feedback. We address relation to prior work here (YbLS Q1; BVwL W1/Q1; G4vD Q1); the results comment covers matched comparisons and scalability.

Novelty: native ASP construction for inspectable repair. We deliberately expose CI commitments as objective atoms. Our opt\mathsf{opt} operator compiles minimum-cost repair into ASP: an optimal Causal ABA model jointly represents an MCS and a compatible DAG. Thm. 1 gives the general, two-way, cost-preserving ASP–MCS correspondence for finite programs; Thm. 2 instantiates it for Causal ABA. Objective atoms can represent structural commitments, e.g. preferred arrows, with release costs optimised alongside CI costs. Crucially, our release-specific MUSes, margins and hard/graded revision support inspectable repair, justification and predictable expert revision. Bayes-ball separately improves Causal ABA.

Partial PC evidence. Native ASPCR (Hyttinen et al., 2014) and Dseptor (Hyttinen et al., 2017) use all testable CI statements in their experiments. OptABA-PC repairs PC/MPC's partial trace, leaving unqueried statements unspecified. Both prior encodings accept partial evidence; our matched experiment fixes the same input, weights and DAG class. Our partial-input pipeline performs better overall in the native comparison; full-trace ASPCR exceeded one hour above six variables (App. G.2).

Objectives and their correspondence. Fix statements KK, positive weights wkw_k and the same nonempty DAG class G\mathcal G, including background restrictions. Let V(G)=k∈K:G violates kV(G)=\\{k\in K:G\text{ violates }k\\}. Hyttinen et al. (2014), Eq. (1), minimises LH(G)=∑k∈V(G)wkL_H(G)=\sum_{k\in V(G)}w_k, charging each violated statement once even if several paths derive its fail atom. We minimise C(R)=∑k∈RwkC(R)=\sum_{k\in R}w_k subject to G⊨K∖RG\models K\setminus R. Since V(G)⊆RV(G)\subseteq R for feasible pairs, and (G,V(G))(G,V(G)) is feasible,

min⁡G∈G, R⊆K: G⊨K∖RC(R)=min⁡G∈GLH(G).\min_{G\in\mathcal G,\,R\subseteq K:\,G\models K\setminus R} C(R)=\min_{G\in\mathcal G} L_H(G).

Positive weights force R=V(G)R=V(G) at every optimum, so optimal repair/graph projections coincide. In [w_k@1,k], kk distinguishes equal-weight statements; all priorities are 1, with no secondary tie ordering. Selected ties can differ.

Beyond fixed core patterns. Hyttinen et al. (2017) use SAT/IP on the 2014 encoding and prove seven minimal core patterns (Thm. 1). Our generic MUS extraction can recover these instances when minimal, and other conflicts, without hand-coded patterns. Their implicit hitting-set solver also extracts general cores. We compile repair natively into ASP and expose repair/graph projections and release-specific explanations for expert revision.

Which guarantees transfer? Hyttinen et al. (2014), Thm. 1 proves dd-connection preservation under conditioning/marginalisation, analogous in role to our Bayes-ball correctness (Lem. 2) and CI–DAG fidelity (Cor. 1). Their Thm. 2 gives graph-level weighted optimality, corresponding to our Thm. 2(1)–(2).

Our representation can be extended to ASPCR by adding retention atoms over its DAG-restricted encoding HH, removing its original weak constraints. For statement kk with failure atom FkF_k, adding :- keep(k), F_k. defines PHP_H and OH=keep(k):k∈KO_H=\\{\mathrm{keep}(k):k\in K\\}. Applying opt(PH,OH,W)\mathsf{opt}(P_H,O_H,W) with the same weights gives R(M)=k:Fk∈MR(M)=\\{k:F_k\in M\\} at positive-weight optima.

Our Thm. 1 yields optimal MCSes and realises each through an optimal model. Correct CI enforcement (their dd-connection construction and fail rules) ensures retained facts hold in the graph. Prop. 1 supplies a private MUS UkU_k with Uk∩R=kU_k\cap R=\\{k\\} for each release. Their full graph class allows cycles/latent confounders and zero weights; our transfer uses DAGs and positive costs. With these modifications, ASPCR's encoding supports our explanation/revision/repair framework.

From interpretation to informed revision. Our repair and revision guarantees support the abstract's contestability claim: an expert can inspect a repair, challenge releases and propose statements to enforce. If proposed statements conflict with retained facts or each other, a MUS exposes a minimal incompatible subset, helping the expert decide which commitments to revise. Inconsistent protections must first be relaxed.

For a contested release ff, the margin μ(f)=ckeep(f)−crelease(f)\mu(f)=c_{\rm keep}(f)-c_{\rm release}(f) is the extra minimum repair cost of retaining rather than releasing it. Under fixed evidence and a common cost scale, margins compare individual challenges: smaller values indicate less costly revisions. Increasing ff's release penalty by more than μ(f)\mu(f) forces retention (Prop. S.1). The expert can combine margins with MUS explanations to choose feasible commitments and revised release costs; exact optimisation finds minimum-cost MCSes and corresponding graphs satisfying the retained facts (Thms. 1–2/Prop. 2).

We will expand Sect. 5.2, with the derivation in App. E and joint-protection examples in App. F.

AuthorsOpenReview ↗

Additional results: matched comparison, scalability and contestability

Here we report the results of the requests for a matched-input comparison (YbLS Q2; G4vD Q2), scalability beyond eight nodes and budget dependence (YbLS Q3), and repair/contestation and graph-family checks (YbLS Q1–2/Q5; G4vD Q2–3). Sensitivity is reported in YbLS Q4; original-run certification and complete graph counts are in G4vD Q3.

Table 3 documents the original settings: OptABA-PC uses a partial PC-derived trace, while native ASPCR uses the full test collection. Table 18 reports runtimes and output counts for those pipelines, with different timing scopes. Our comparison below instead fixes the same partial trace, weights, DAG constraints and timing scope for both encodings to isolate encoding costs and correspondence.

Matched comparison and scalability across graph sizes (YbLS Q2–3; G4vD Q2). Table R1 extends the controlled comparison from the original 400 inputs to 50 ER10, 50 SF10 and 25 discrete bnlearn Sachs samples (11 nodes).

Table R1. Proof coverage and paired time to proof, 5–11 nodes. Both methods receive identical partial PC/MPC CI traces, weights and DAG constraints, using N=5,000N=5{,}000, G2G^2 and α=.01\alpha=.01. Each solve uses four threads on four physical cores; timing covers prepared-program parsing, grounding and solving. “Proved” counts minimum-cost proofs within the limit. Time ratio is median paired OptABA/ASPCR time to proof among jointly proved pairs; nn is their count. Ratios above 1 favour ASPCR. CI testing, input preparation and graph enumeration are outside this timing.

DatasetInputsLimit (s)OptABA provedASPCR provedTime ratio (nn)
Cancer (5)506050501.33 (50)
Earthquak (5)506050501.19 (50)
Survey (6)506050505.04 (50)
ER5506050501.24 (50)
SF5506050501.20 (50)
Asia (8)50300485012.34 (48)
ER85030031487.40 (31)
SF85030038488.66 (38)
ER105060012237.72 (12)
SF1050600162712.80 (16)
Sachs (11)25180012518.87 (1)

Scalability as the time budget increases (YbLS Q3; G4vD Q3's distinction between incumbents and proofs). Table R2 answers how additional time changes incumbent quality and certification.

Table R2. Progressive-budget scalability on 100 ten-node inputs. Checkpoints from the same uninterrupted ten-node (ER and SF) solves. Proof counts use all 100 inputs; “at min” and gaps use the same 50 inputs with certified optimum costs. Gaps are mean (maximum) percentage excess; the other 50 optimum costs remain unknown.

SecondsOptABA proofs /100ASPCR proofs /100OptABA at min /50ASPCR at min /50OptABA gap %ASPCR gap %
151230214031.88 (141.07)4.74 (53.65)
601936304915.82 (132.58)0.17 (8.39)
300264539505.31 (51.37)0
600285046500.97 (17.24)0

The extra budget improves OptABA's known-cost attainment from 21/50 at 15 s to 46/50 at 600 s, while proof coverage grows from 12/100 to 28/100. ASPCR attains all 50 known costs by 300 s and proves 50/100 cases by 600 s. This separates improvement in incumbent quality from completion of the optimisation proof; gaps cannot be calculated for the 50 unknown optima.

Efficiency and future directions. ASPCR's shorter paired proof times and higher proof coverage on matched partial traces motivate using its consistency encoding within our repair framework. The common response's construction would combine this encoding with explicit MCS/graph outputs, MUS explanations and hard/graded revision under the stated assumptions. We will investigate this integration and its explanation/revision overhead, alongside weighted structural commitments.

Repair and contestation checks (YbLS Q1–2/Q5; G4vD Q2–3). To test the formal correspondence and single-fact revision guarantees, we forced every released fact to be retained on all 250 five/six-node inputs. Both encodings agree on all 853 optimal revised costs and contestability margins (Definition 4). For one release in up to five inconsistent inputs per benchmark (23 targets), both return valid private MUSes: minimal conflicts containing the challenged release and otherwise retained facts. These test single-fact redress; joint-protection feasibility is addressed in YbLS Q5.

To address graph-family/projection questions, we enumerated all optimal repairs and compatible DAGs on five seeds each from the five/six-node datasets (25 inputs): outputs match, with one optimal repair each. A constructed four-node case with three equal-cost corrections also confirms agreement across tied repairs and DAGs, including the graded-contestation tie and strict-retention cases. Larger selected-repair enumeration counts and their completeness are in G4vD Q3.

Using the extra page, Sect. 6 will summarise matched/scaling results; App. G.4 will give full tables/profiles, and App. G.3 the repair/contestation audits.

AuthorsOpenReview ↗

Updated Manuscript

Dear reviewers,

Thank you again for your careful and constructive reviews.

To make the proposed changes easier to review, we have uploaded an updated manuscript, with additions and revisions highlighted in blue. The main changes are:

  • Clearer positioning relative to prior weighted causal optimisation and Bayes-ball encodings, including the generality of our repair and contestability framework (§2; §5.1; §5.2, lines: 415-425).
  • Further explanation of expert revision, joint protection and contestation margins (§5.2, lines: 426-431; Appendix F.1) alongside corrections to the worked example’s MEC description (Examples 3 and 6, in §3.3 and §5.1), alongside
  • Additional matched-input comparisons with ASPCR-DAG, including ten-node ER/SF graphs and the eleven-node Sachs network, with runtime and time-budget analyses (§6; Appendix G.4, lines: 2430-2442; Tables 2, 22 and 23).
  • Sensitivity analyses for release costs, significance thresholds and sample size, and complete enumeration of compatible graph families (Appendix G.4, lines: 2443-2470; Tables 24 and 25). We also distinguish proven optima from timeout incumbents and report subsequent certification of saved repairs (Appendix G.3, lines: 1881-1885; Tables 10 and 11).
  • Corrections and clarifications to references (§3.2, §3.4 and §5.1) and experimental-protocol attribution (§6, lines: 467-468; Appendix G.2, lines: 1501-1506) as well as an explicit normalisation of the graph generator to clarify the ABA–ASP correspondence, and a formal account of transferring our framework to other faithful CI encodings (§3.2; Appendices B.1 and E.1).

We would greatly appreciate your feedback on these changes and any questions or concerns that remain.

AuthorsOpenReview ↗

Response to BVwL and G4vD

Thank you, BVwL and G4vD. We appreciate BVwL's confirmation that the soundness concerns are resolved. Our objective is to enable experts to reason about causality from and with finite data. We started from Causal ABA because it was envisaged as a transparent framework for integrating data and expert knowledge, exposing conflicts for inspection and revision. This matters in high-stakes decisions, where people need to understand and question the reasoning, approve decisions and take responsibility for them.

Our contribution enables interactive use of exact causal methods with formal guarantees. We formalise weighted optimal correction sets in ASP and their cost-preserving, two-way correspondence with optimal stable models (§4). Experts can inspect retained and released commitments, obtain minimal conflict explanations, protect a fact when feasible, and determine exact cost thresholds for retaining it in every optimum (§5.2).

We were pleased to find that Hyttinen et al.'s encoding optimises faster on matched inputs: the encoding is a means to our goal, and our framework can use it too. The guarantees transfer to that encoding (Appendix E.1), demonstrating the generality of our construction. Both encodings also return the same optimum costs on all 853 matched hard-retention challenges (Appendix G.3).

Computational improvements make this approach usable. We accelerate Causal ABA's consistency computation (Table 5). In our experiments, applying our partial-input and weighting protocol to ASPCR extends its tested range from six to eleven variables (Table 2). The complete OptABA-PC procedure also achieves significantly higher reconstruction perfomance than native ASPCR on all five shared benchmarks (Table 14).

We will sharpen the introduction and contribution statement around this objective. Thank you again for helping us clarify the message and establish the generality of our framework.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.