Polynomial-Delay Listing of Interventional Ancestral Graphs

Causal discovery from experiments rests on a simple bookkeeping device. Each experiment gets an extra node in the graph, an "intervention indicator" (an $F$-node) that points into the variables the experiment manipulated. Comparing an experimental dataset with an observational one then becomes an ordinary graph question: is the $F$-node d-separated from some variable? (d-separation is the path-blocking rule that reads conditional independences off a directed graph.) With hidden confounders, the learned object is a partial ancestral graph. It records some edge ends as arrows or tails and leaves others as circles, meaning "undetermined." The trouble is that the standard learner leaves circles that are in fact fixed across every graph consistent with the data. Zhou and Kocaoglu showed this gap is real. Their local rules close only part of it, and their complete method enumerates candidate graphs and times out at 100 nodes.

We propose to close this gap with an algorithm that lists every graph in the interventional equivalence class with polynomial delay, meaning polynomial time between consecutive outputs. As a byproduct it would give complete edge orientation in polynomial time. The key ingredient is an extension oracle. Given a partially oriented augmented graph, it answers in polynomial time whether at least one valid interventional ancestral graph completes the partial orientation. With such an oracle, an edge mark is compelled exactly when the oracle rejects every alternative mark. Listing then becomes a backtracking search that never enters a dead branch. The technical bet is that the special structure of known-target $F$-nodes keeps this oracle tractable. That structure is that an experiment's influence on a non-target variable must pass through its target. Under that bet, interventional constraints reduce to observational extension checks plus reachability queries, both of which are known to be polynomial.

What exists and where the gap sits

The representation comes from Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions.. It attaches $F$-nodes to known targets and projects the result to an interventional maximal ancestral graph ($\mathcal{I}$-MAG), a mixed graph that summarizes hidden confounding with bidirected edges. It characterizes equivalence through shared skeleton, unshielded colliders and discriminating paths, and it learns with $\mathcal{I}$-FCI. That paper supplies our semantics.

Towards Completeness in Causal Discovery from Soft Interventions with Known Targets motivates the work. It proves $\mathcal{I}$-FCI is incomplete. It adds three "transit node" rules, called FAST, which are fast but incomplete because compelledness depends on global inducing paths. It also gives LIST, which is complete but enumerates candidates and filters them with a realizability oracle, at super-exponential cost.

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules supplies the listing method. It achieves $O(m^3 d^4)$ delay for observational MAGs by fixing one vertex's orientation at a time (singleton background knowledge) and propagating locally complete rules. It has no notion of $F$-nodes or realizability.

ciflyr: Reachability-Based Primitives for Graphical Causal Inference supplies a second tool. It shows that custom path semantics over mixed graphs can be checked in linear time through programmable rule tables. We would use it to express the transit constraints. It does no structure learning.

Our proposal differs from LIST because it never generates a graph it will later reject. It differs from MAGLIST-POLY because the space being listed is the realizable interventional class, not the observational class over $V \cup F$.

Core Claim

Fix soft interventions with known targets and allow hidden confounding. Let $\mathcal{P}$ be the interventional partial ancestral graph learned under faithfulness, and let $K$ be a set of singleton orientation constraints. We conjecture that deciding whether some realizable $\mathcal{I}$-MAG is consistent with $(\mathcal{P}, K)$ takes polynomial time in the number of nodes and edges.

The intuition is as follows. An $\mathcal{I}$-MAG is a MAG over $V \cup F$ with two extra conditions. First, $F$-nodes have no parents and no edges among themselves. Second, any adjacency between $F_i$ and a non-target must be explained by an inducing path through the target. That second condition is a reachability statement with a fixed local grammar, so it can be written as a rule table.

If the conjecture holds, two results follow directly.

The first is a polynomial-delay lister. It performs a flashlight search over singleton orientations and prunes every branch the oracle rejects.

The second is a complete orienter. It makes at most two oracle calls per circle mark, roughly $O(m)$ calls in total. This settles the open problem stated in the Zhou–Kocaoglu paper.

If the conjecture fails, we aim to prove hardness of the extension problem. We would then give an algorithm whose running time is exponential only in a structural parameter, such as the number of targets whose transit constraints interact. Either outcome is informative.

Research Program

Phase 1: formalize realizability as a local-plus-reachability condition. We start from LIST's realizability oracle, treating it as a black box whose decisions we must reproduce. We prove a characterization of realizable $\mathcal{I}$-MAGs that has two parts. The first part consists of conditions checkable vertex by vertex. The second part consists of reachability conditions encoded as rule tables. We verify this characterization exhaustively against LIST on all small graphs.

Phase 2: lift MAGLIST-POLY's rules to the augmented setting. MAGLIST-POLY's rules R14–R16 assume that every MAG over the vertex set is admissible. We derive interventional analogues that also propagate transit constraints. We then prove they are locally complete for singleton constraints around one vertex, which is the property that gives polynomial delay in the observational case.

Phase 3: build the extension oracle and the two algorithms. We combine the Phase 2 rules with a final reachability check to obtain the extension oracle. On top of it we build the polynomial-delay lister and the complete orienter.

Phase 4: test empirically. We evaluate first with oracle d-separation and then with finite-sample tests.

The scope is deliberately limited to soft interventions with known targets. Mixed hard/soft interventions and unknown targets are natural follow-ons, but each changes the realizability condition. Claiming them now would dilute the result.

Baselines

The naive reference point is $\mathcal{I}$-FCI from Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions., run with the same conditional-independence tests and the same significance level as every other method. It defines how many circles remain if nothing is done beyond the established rules.

The strongest efficient competitor is FAST from Towards Completeness in Causal Discovery from Soft Interventions with Known Targets. It runs on the same learned partial graph, so any difference is due to orientation alone. That paper reports that FAST improved End-F1 and Structural Hamming Distance over $\mathcal{I}$-FCI on 5- and 100-node synthetic ADMGs, with "virtually no added runtime." No reported numeric End-F1 value was found on Lacuna for FAST or $\mathcal{I}$-FCI. To beat FAST, our method must resolve strictly more circles at 100 nodes. It must also keep runtime within a small constant factor of FAST's.

The strongest complete competitor is LIST, from the same paper. It is reported to achieve "the best orientation recovery in small-scale tests" but "timed out on the 100-node graphs"; no numeric End-F1 is reported on Lacuna. With oracle tests, our orienter must match LIST's output exactly on every small graph. It must also finish at sizes where LIST times out, under an identical wall-clock budget and identical hardware.

The ablation that isolates our key ingredient applies MAGLIST-POLY directly to the augmented partial graph and then filters each listed MAG for realizability, using LIST's oracle as the filter. This baseline has polynomial listing but no realizability-aware propagation. Comparing against it measures what the extension oracle buys. The comparison covers the rejection rate, the delay between consecutive realizable outputs, and the total time.

Why not just…?

Why not just run MAGLIST-POLY on the augmented graph and filter out unrealizable outputs? This is the most serious alternative, and it is exactly the ablation above. If the fraction of observationally valid MAGs over $V \cup F$ that are realizable stays bounded away from zero as graphs grow, then filter-after-listing is effectively polynomial delay already. In that case our oracle's contribution would be mainly the completeness proof. We will measure the rejection rate as a function of node count and number of interventions. Our expectation is that rejections grow with the number of $F$-nodes, since each adds transit constraints that observational listing ignores. If the data show otherwise, we will report that and reframe the work as a theoretical certificate.

Why not just keep FAST's local rules, since they may already capture most compelled marks? Zhou and Kocaoglu describe FAST's improvement at 100 nodes as "modest" and prove it is incomplete. They do not report how many compelled circles it misses. On small graphs where LIST finishes, we will count the circles that LIST orients and FAST leaves open. If that residual is near zero across graph densities and intervention counts, the practical case for our method weakens, and we will say so. The theoretical problem stands either way.

Why not just use a score-based interventional learner like IGSP? The permutation search in Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions assumes there are no hidden confounders, while our setting is defined by their presence. We will nonetheless run it on the confounded synthetic graphs to show how its errors look. The point is not to compete with it on its own assumptions.

Why not just add pruning and caching to LIST? Heuristic pruning of LIST leaves its worst-case cost unchanged. It also gives no guarantee between outputs, which matters when the class is listed in order to choose the next experiment. We will include a memoized LIST variant in the scaling plot. If that variant reaches 100 nodes, the remaining contribution is the delay guarantee and the polynomial orientation bound.

Proposed Experiments

Synthetic study. The synthetic study follows the soft-intervention ADMG protocol of the Zhou–Kocaoglu paper. It uses random mixed graphs with bidirected confounding edges at $n = 5$ and $n = 100$, plus intermediate sizes, with one to several known-target soft interventions.

The decisive correctness check uses oracle d-separation, which removes statistical error. On every graph where LIST terminates, our orienter's output must equal LIST's mark for mark. A single mismatch falsifies the completeness claim.

The scaling check measures three things against $n$ and the number of interventions. They are wall-clock time for full orientation, the maximum and mean delay between listed graphs, and the naive filter's rejection rate. Polynomial delay predicts flat or polynomially growing delay. The filter baseline, if our intuition holds, will show delay growing with the number of $F$-nodes.

Finite-sample study. A finite-sample variant repeats the comparison with standard conditional-independence tests. It reports End-F1 and Structural Hamming Distance against the true graph, to check that completeness gains survive test errors rather than amplify them.

Real data. On the Sachs protein-signaling data (7,466 cells, 11 variables, nine contexts), we report the number of compelled marks and the agreement with the literature reference graph, compared with $\mathcal{I}$-FCI, FAST and LIST. LIST is feasible at 11 variables, so this doubles as an exactness check on real data. For context, FASK reports adjacency precision 0.84 and recall 0.80 on this dataset in FASK with Interventional Knowledge Recovers Edges from the Sachs Model. We cite this only as a reference for skeleton quality, since our contribution concerns orientation.

Experiment selection. Finally, we repeat the experiment-selection analysis of MAGLIST-POLY in the interventional setting. That paper reports 98 causal marks identified with two interventions chosen using its observational lister, against 81 for random selection. We ask whether listing the realizable interventional class picks interventions that yield more marks than both random selection and observational listing. This is the downstream test of whether exact listing matters in practice.