Learning a causal graph when some causes are unmeasured is much harder than learning one when every cause is observed. The best exact solvers for the latent-variable case stall at a few dozen variables. Maximal ancestral graph structure learning via exact search reaches 12 variables in 10 hours, and Integer Programming for Causal Structure Learning in the Presence of Latent Variables reaches about 18 variables only after capping how large a confounded group may be. The fully observed case is far more tractable. Parameterized Complexity Results for Exact Bayesian Network Structure Learning shows that exact directed acyclic graph (DAG) learning runs in linear time when the candidate skeleton is tree-like and has bounded degree. This note proposes to charge the extra difficulty of latent variables only to the part of the graph that is actually confounded. The optimal fully observed DAG serves as the guaranteed baseline, since every DAG is a legal latent-variable model and its score is therefore a lower bound. The solver's exponential cost should then depend only on how far the answer strays from that baseline.
Concretely, we will design an exact algorithm whose cost is the known DAG cost times a factor that depends only on $\mu$, the number of variables touched by latent confounding. We will also prove conditional lower bounds showing why this factor is needed. The lower-bound claim is that if confounding is left unbounded, the extra cost of tracking which variables share hidden causes grows quadratically in the exponent with skeleton width. Bounding $\mu$ removes that quadratic term. The result would be the first tractability-and-hardness map for score-based learning of graphs with latent confounders, together with a solver that tests the map on standard networks.
Core Claim
Some terms first. A latent confounder is drawn as a bidirected edge $A \leftrightarrow B$. Variables linked by chains of bidirected edges form a district, also called a c-component, which is a group that shares hidden causes. Chen et al. and Rantanen et al. both prove that the Gaussian Bayesian Information Criterion (BIC) score splits additively over districts. A single variable with no bidirected edges is a trivial district and scores exactly as in a DAG.
Let $G_S$ be a superstructure, meaning an undirected graph that bounds which edges may appear. Let $w$ be its treewidth, $\Delta$ its maximum degree, and $\delta_f$ the maximum number of candidate parent sets per variable. Define the confounded mass $\mu$ as the number of variables lying in non-trivial districts. We conjecture, and aim to prove, that the best acyclic directed mixed graph (ADMG) can be found in time
$$ T(n, w, \Delta, \mu) = \delta_f^{O(w)} \cdot 2^{O(\mu^2)} \cdot n^{O(1)} . $$
The first factor is the Ordyniak–Szeider DAG cost. The $2^{O(\mu^2)}$ factor has a specific source. Inside each separator of the tree decomposition, the dynamic program must remember two things about the confounded variables only: how they are grouped into districts, and which of them are ancestors of which. The ancestor relation is needed to rule out "almost directed cycles" $A \to \cdots \to B \leftrightarrow A$. At most $\mu$ such variables exist, so the state carries at most $\mu^2$ bits.
The matching lower-bound claim is that, with $\mu$ unrestricted, no algorithm runs in $2^{o(w^2)} \cdot n^{O(1)}$ time even at bounded degree, unless the Exponential Time Hypothesis (ETH, the conjecture that 3-SAT needs $2^{\Omega(n)}$ time) fails. At $\mu = 0$ the problem reduces to DAG learning, and all known results hold unchanged. This framing is the above-guarantee idea of Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees, which measures departure from a structural baseline. Here the baseline is the causally sufficient optimum, and the departure is the confounding.
Research Program
The theory has three pieces.
The first is the upper bound. We extend the Ordyniak–Szeider tree-decomposition dynamic program so that each separator also records three things: a partition of its confounded vertices into partial districts, an ancestral relation among them, and the partial district score. We score districts with the c-component BIC decomposition of Chen et al. and Rantanen et al. That decomposition is the method we reuse. What is new is keeping district bookkeeping confined to the $\mu$ confounded vertices. We will also treat the maximal ancestral graph (MAG) variant. Rantanen et al. note that removing a single edge can create an inducing path over arbitrary distances, which is a genuinely non-local effect. We will check whether that effect stays confined to confounded vertices or leaks into the rest of the graph.
The second is the lower bounds. Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover shows that non-local properties can push treewidth dependence far above single-exponential by packing much information into small separators. We will adapt its encoding style, starting from a linear-size SAT reduction as in Tight Running Time Lower Bounds for Vertex Deletion Problems. The goal is to force the solver to distinguish $2^{\Theta(w^2)}$ district and ancestor configurations across a width-$w$ separator. Two results constrain the design:
- Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis shows that bounding the moralized graph is W[1]-hard. W[1]-hardness is the standard evidence that no runtime of the form $f(k)\cdot n^{O(1)}$ exists. So $\mu$ must bound variables in districts, not moral edges.
- The same paper, together with Ordyniak–Szeider, shows NP-hardness at bounded degree alone. So $\mu$ cannot be tractable without $w$.
We will state the resulting dichotomy precisely, including hardness for $\mu$ alone.
The third is the solver. Stage one computes the DAG optimum on a superstructure. Following the undirected independence graph construction in A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables, we build that superstructure from Markov blankets. Stage two runs the $\mu$-bounded dynamic program, increasing $\mu$ until one more confounded variable no longer improves BIC by more than its penalty. The DAG score also supplies a pruning rule. Any candidate district whose BIC gain over its best DAG restriction cannot cover its extra parameters is discarded before search. This is an above-guarantee analogue of AGIP's pruning rules.
Baselines
The naive reference point is the DAG optimum itself. It is our stage one, run alone, and it reports how much BIC is lost by ignoring confounding. If our method rarely beats it on data generated with latent variables, the whole question is moot.
The strongest exact competitor is AGIP, the integer program of Integer Programming for Causal Structure Learning in the Presence of Latent Variables. It enumerates candidate districts up to a size cap and enforces acyclicity with cluster and bicluster cutting planes. Its reported result is that it improved BIC over the greedy M3HC algorithm in 53 of 60 random instances of up to 20 variables. Its bow-free extension, Integer Programming Based Methods and Heuristics for Causal Graph Learning, reports a skeleton F-score of 0.972 against 0.891 for ABIC and 0.918 for GBAP on 10-node graphs. The same paper reports that GBAP did not finish on Barley within 24 hours.
The exact MAG search of Rantanen et al., a dynamic program with branch-and-bound over districts, is the second exact baseline. Its reported ceiling is 12 variables within 10 hours on marginalized ecoli70 and magic-niab. All exact methods will get the same superstructure, the same Gaussian BIC, the same machine, and a common wall-clock limit. AGIP will be tuned over its district cap using a budget equal to our search over $\mu$.
The approximate baselines are M3HC, GFCI, and DiCoLa+FCI. They represent what practitioners run.
Two ablations isolate our key ingredient. The first gives AGIP our DAG warm start and our pruning rule but keeps its global district enumeration. The second runs our dynamic program with the $\mu$ bound removed, so it tracks full district and ancestor state over each separator. Beating the baselines means certified-optimal BIC on instances where AGIP and exact MAG search time out, together with equal or lower Structural Hamming Distance (SHD, the count of edge insertions, deletions and reorientations separating the learned graph from the truth) against the known graph.
Why not just…?
Why not just cap district size in AGIP? A size cap limits each district, but AGIP still enumerates candidate districts over all $p$ variables, and that enumeration is the ceiling of about 18 variables. Our parameter bounds total confounded mass and localizes it through tree decompositions, so cost should grow linearly in $n$ at fixed $w$ and $\mu$. This alternative is a real threat on small, densely confounded instances. The warm-started AGIP ablation settles the matter: if it matches us on Barley and Andes subgraphs, the decomposition adds nothing.
Why not just let the integer program's LP relaxation do the work? Branch-and-bound already exploits small integrality gaps, as Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics explains for vertex cover. We will measure AGIP's root LP gap on every instance. If the gap alone predicts AGIP's runtime as well as $(w, \mu)$ predicts ours, we will report that the LP gap is the better explanatory parameter.
Why not just use DiCoLa or FCI with separators? These methods give no score guarantee. By DiCoLa's own account, they revert to the base algorithm on dense graphs. Chen et al. also note that constraint-based search compounds single test errors. We compare against DiCoLa+FCI on SHD. Our claim concerns certified BIC optimality, and DiCoLa cannot supply that at any speed.
Proposed Experiments
The synthetic study uses linear Gaussian ADMGs on Erdős–Rényi and scale-free skeletons with 30 to 200 variables, following the setups of DiCoLa and DCILP. We vary superstructure treewidth and planted confounded mass independently.
The decisive check has two parts. At fixed $w$, runtime should grow like $2^{O(\mu^2)}$ and stay flat in $n$. At fixed $\mu$, the $\mu$-unbounded ablation should grow markedly faster in $w$ than our solver. If our solver's runtime tracks $w^2$ even when $\mu$ is small, the upper-bound analysis is wrong.
The real-network study marginalizes hidden nodes out of MILDEW, BARLEY, ANDES, ecoli70 and magic-niab. It reports certified optimality, BIC relative to the DAG baseline, SHD, and time. It checks whether real networks have small $\mu$ at their optimum. On LINK we report whether a certified solution is reached at all, since DiCoLa reports only that decomposition let otherwise timed-out algorithms finish. On the 33-gene Arabidopsis data we check whether the recovered districts respect the MEP/MVA block structure that DiCoLa+FCI recovered.
The theoretical deliverable is either a proof of the ETH bound ruling out $2^{o(w^2)}$ or an explicit faster dynamic program that refutes it. Either outcome answers the question.
References
- Maximal ancestral graph structure learning via exact search
- Integer Programming for Causal Structure Learning in the Presence of Latent Variables
- Parameterized Complexity Results for Exact Bayesian Network Structure Learning
- Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
- Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover
- Tight Running Time Lower Bounds for Vertex Deletion Problems
- Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
- A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables
- Integer Programming Based Methods and Heuristics for Causal Graph Learning
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics