A causal graph that allows for hidden common causes uses two kinds of arrows. Ordinary arrows mean "X causes Y." Two-headed arrows mean "X and Y share a cause we did not measure." Learning such a graph from data is a search over a huge discrete space. The current leading approach turns that search into smooth gradient descent and, on hard instances, often settles on a wrong graph. This note proposes treating the problem as one that linkage-learning evolutionary algorithms were built for. These algorithms discover which decision variables must be changed together and swap those groups as whole blocks. Here, the variables that must change together are edges inside the same hidden-confounder cluster.
The structural fact that makes this work is old and exact. Tian and Pearl showed that a graph with hidden confounders splits into "districts." A district (also called a c-component) is a set of variables linked by chains of two-headed arrows, and the likelihood factorizes over districts (A General Identification Condition for Causal Effects). A proposed edit to the graph therefore changes the score of only the districts it touches. That is the "partial evaluation" trick behind gray-box evolutionary optimization, which updates only the parts of an objective that depend on the changed variables. It is also a ready-made blueprint for which edges belong together. We propose a Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) whose genome is an acyclic directed mixed graph (ADMG), whose block structure is read from the current districts, and whose fitness is recomputed one district at a time.
Core Claim
The claim is narrow and testable. For linear Gaussian models with hidden confounding, the main reason Differentiable Causal Discovery Under Unmeasured Confounding fails is search, not statistics. That paper learns ADMGs by relaxing a Bayesian information criterion (BIC) into a smooth score it calls ABIC and fitting it with residual iterative conditional fitting (RICF). On graphs built to exhibit Verma constraints, which are equality constraints that ordinary independence tests cannot see, it recovers the true equivalence class only about 39% of the time at n=1000.
We claim that a discrete optimizer will find graphs with strictly better exact BIC, and correspondingly higher recovery, at matched compute. The optimizer swaps district-shaped blocks of edges and accepts each swap only if the score does not get worse. Because the genome is discrete, it can also represent "bows," pairs joined by both a direct and a confounding edge. Neural ADMG learning must exclude bows to stay identifiable (Causal Reasoning in the Presence of Latent Confounders via Neural ADMG Learning). Arid graphs, the class that captures Verma constraints, can contain bows. A search that can enter bowed arid graphs and then check membership in the class exactly is a real capability difference, not just a speedup.
The closest existing work, Learning Discretized Bayesian Networks with GOMEA, already uses GOMEA to learn graph structure. It learns ordinary directed acyclic graphs, assumes no hidden confounders, and builds its blocks from population statistics. We differ on all three points: a mixed-graph genome, blocks derived from districts, and exact per-district partial evaluation. Nothing in that paper addresses two-headed arrows.
Research Program
The genome assigns each unordered variable pair one of six states: none, i→j, j→i, i↔j, and the two bowed states, a direct edge plus ↔. Edits that create a directed cycle, or that leave the arid class when aridity is required, are rejected immediately. Optimal mixing already rolls back any change that does not help, so rejecting infeasible edits fits the algorithm naturally. Aridity is checked with the Greenery characterization implemented in the Ananke package released with the ABIC work.
Fitness is exact BIC. The Gaussian likelihood is fitted with RICF, which itself works district by district, plus an edge-count penalty. A cache maps each district's variable set and parent set to its fitted log-likelihood. An edit to a directed edge into variable v refits only v's district. An edit to a two-headed edge refits the one or two districts it merges or splits. Population members share the cache, so recurring building blocks cost nothing to rescore.
The block structure that optimal mixing iterates over, which GOMEA calls the family of subsets, is built in three variants. The first is the univariate variant, in which every pair is its own block. The second is the standard linkage tree learned from mutual information between gene values across the population, as in Parameterless Gene-Pool Optimal Mixing Evolutionary Algorithms. The third is the proposed district-aware variant. For each district in the current elite solutions, it forms the block of all pairs inside that district and its parents, then nests these blocks hierarchically by how often districts co-occur across the population. This variant resembles the overlapping clique blocks of Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEA. The difference is that its blocks come from causal structure rather than from quadratic-cost pairwise fitness probing, which avoids the O(L²) probing overhead that paper incurs. Population size is handled by the interleaved multistart scheme, implemented on the gomea library from A Joint Python/C++ Library for Efficient yet Accessible Black-Box and Gray-Box Optimization with GOMEA. As a result, there are no tuning knobs to favor our method.
The analytical part is a "score gap" diagnostic run before any method comparison. For each instance where ABIC fails, we compute the exact BIC of the true graph and of ABIC's output. If ABIC's output usually scores at least as well as the truth, the failure is statistical: BIC itself does not identify the truth at that sample size, and no optimizer can help. In that case, the project's claim is falsified early, and we report it. Only if the truth usually scores better is search the bottleneck, which is the condition that justifies the rest of the work.
Baselines
The naive reference point is a greedy hill-climber over the same six-state genome. It uses the same district-cached exact BIC, with random restarts, and makes single-pair edits only. It gets the identical evaluation budget, counted in district refits, and identical wall-clock. This baseline isolates whether anything beyond cheap local scoring matters. Beating it means a statistically significant increase in the share of instances where the correct equivalence class is found, across seeds, at equal refit counts.
The strongest existing method is ABIC from Differentiable Causal Discovery Under Unmeasured Confounding, run through its released Ananke implementation. It reports about 39% recovery of the true equivalence class at n=1000 on Verma-constraint ADMGs with 10 and 15 variables. On Sachs protein data it reports skeleton precision of 0.77 and identifies the Erk–PKA association as confounded. It is the right competitor because it uses the same model class, the same likelihood, and the same arid constraint. Any gain we show is therefore due to the search procedure. We regenerate its synthetic protocol, give ABIC multiple random restarts until its wall-clock matches ours, and score every method's output with the same exact BIC. Beating ABIC means higher equivalence-class recovery than its best-of-restarts result at matched wall-clock, together with better final BIC on the same instances. Matching its 0.77 Sachs precision while finding a better-scoring graph would count as parity, not a win.
greedyBAP is included as the classical discrete score-based method; the ABIC paper reports outperforming it but the file gives no number. FCI is included as the constraint-based reference. Its bidirected-edge F1 of 0.75 on the Fork-Collider benchmark, against 0.99 for N-ADMG, comes from Causal Reasoning in the Presence of Latent Confounders via Neural ADMG Learning. That benchmark is nonlinear, so it serves as context only.
The key ablation compares the three block structures at an otherwise identical setting. A second ablation turns partial evaluation off by refitting the whole graph after every edit, which measures how much of the gain is pure throughput.
Why not just…?
Why not just run ABIC with many random restarts? This is the most serious threat. If ABIC's local optima are shallow and varied, restarts alone may close the gap. The matched-wall-clock restart protocol above settles the question directly. We will also plot recovery against the number of restarts. If ABIC with restarts plateaus below our method's recovery while its best BIC stays worse, the failure is structural rather than a matter of budget. If ABIC with restarts matches us, we will say so, and the contribution shrinks to bow-capable search.
Why not just use greedy search with district caching? Partial evaluation might be the whole story, in which case the evolutionary machinery is decoration. The greedy baseline and the univariate-block ablation test exactly this. The evidence that blocks should help is indirect. In optimization, GOMEA outperforms non-linkage methods on block-structured problems such as the sum of rotated ellipsoid blocks (Exploiting linkage information in real-valued optimization with the real-valued gene-pool optimal mixing evolutionary algorithm). Moving a whole district at once is what lets a search escape graphs where every single-edge edit lowers the score. We expect the advantage to grow with district size, and we will measure it as a function of district size.
Why not just use the generic linkage tree that GOMEA already learns? It might rediscover district structure from population statistics on its own. If the mutual-information tree matches the district-aware variant, the causal derivation of blocks is unnecessary and the result simplifies to "GOMEA works on ADMGs." That would still be new relative to Learning Discretized Bayesian Networks with GOMEA, but less interesting. We will report it either way.
Proposed Experiments
The first step is the score-gap diagnostic on regenerated linear Gaussian Verma-constraint ADMGs with 10 and 15 variables at n=1000. This stage can stop the project.
If search is shown to be the bottleneck, the main comparison follows on the same generator. It extends to 30 and 50 variables, where non-convexity should hurt ABIC more, and covers sample sizes from 500 to 5000. Instances are generated with and without bows, and with and without hidden confounders that act on more than two variables. Pairwise-only confounding is the restriction that continuous methods inherit. Metrics are the fraction of instances recovering the true equivalence class, skeleton precision and recall, bidirected-edge F1, the final exact BIC relative to the truth, and the number of district refits.
On Sachs, we compare learned graphs and their BIC with ABIC's reported precision of 0.77. We also check whether the Erk–PKA confounded edge appears, and whether the bow-capable search proposes any bow that ABIC's arid but differently searched output does not.
The decisive results are two. First, on the instances where ABIC fails, our method must find a graph that scores better and lies in the correct class, at matched compute. Second, the district-aware blocks must beat both the univariate blocks and greedy search by a margin that grows with district size. If either result fails, the corresponding part of the claim is withdrawn.
References
- A General Identification Condition for Causal Effects
- Differentiable Causal Discovery Under Unmeasured Confounding
- Causal Reasoning in the Presence of Latent Confounders via Neural ADMG Learning
- Learning Discretized Bayesian Networks with GOMEA
- Parameterless Gene-Pool Optimal Mixing Evolutionary Algorithms
- Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEA
- A Joint Python/C++ Library for Efficient yet Accessible Black-Box and Gray-Box Optimization with GOMEA
- Exploiting linkage information in real-valued optimization with the real-valued gene-pool optimal mixing evolutionary algorithm