Keeping Causal Orderings Diverse in Mixed-Type Structure Search

Many real datasets mix measurement types. A clinical record holds blood pressure (continuous), a diagnosis (yes/no) and a genotype (one of several categories). Learning which variables cause which from such data means searching an enormous space of candidate causal graphs for the one that best explains the data. Most practical searches are greedy: they add, remove or flip one edge at a time. Greedy search can stop early at a graph that no single move improves, even though a better graph exists elsewhere. Optimization researchers call this premature convergence.

We argue that mixed data makes this failure worse in a specific way. When a continuous and a categorical variable are linked, the two possible edge directions are scored with different model families: a shift model for "category causes number" and a classifier for "number causes category". Early in the search, the direction chosen for such an edge often reflects which model family happens to fit the finite sample better, not which direction is causal. Later moves then build on that choice and lock it in.

We propose a population search over causal orderings, meaning rankings of variables from causes to effects. The population is kept deliberately diverse, and diversity is measured specifically on how members order continuous–categorical pairs. Each candidate is scored with an existing fast mixed-type score. The method is built around a diagnostic that asks a simple question first: when current methods fail, is it because the search missed the true graph, or because the score prefers a wrong one?

Core Claim

Our claim is that on mixed-type data with more than about twenty variables, a large share of structural errors made by greedy score-based search are search failures, not score failures. For a search failure, the true graph's score beats the returned graph's score under the method's own score. We further claim that most of these failures concentrate on edges between continuous and categorical variables.

If this holds, the remedy is not a better score but a search that refuses to commit early on those type-crossing orientations. The search we propose borrows two ideas from the diversity literature. The first is selection on a two-objective trade-off between quality and dissimilarity from the rest of the population, as in MEoH, which selects LLM-generated heuristics by performance and by code-structure dissimilarity. The second is a split into fast-moving and slow-moving subpopulations with one-way overwriting, as in MF-PBT. We apply both in the space of variable orderings, with a dissimilarity measure tailored to mixed types.

The closest prior work handles local optima in other ways. LiM explicitly notes that continuous optimization of mixed linear models gets trapped. It repairs this with a local edge-reversal sweep restricted to the skeleton found first, so a skeleton error cannot be undone, and it handles only binary discrete variables. TCCD couples tree search with gradient updates to escape local optima, but it targets event sequences rather than independent mixed observations, and it keeps no population. MERIT gives identifiability for mixed additive-noise models with multi-category variables. Its greedy leaf-peeling cannot revisit an early ordering mistake and is limited to roughly 10–20 variables. CV-LR makes a kernel score for mixed data cost linear in sample size, but its authors note that it inherits Greedy Equivalence Search (GES, a greedy add-then-delete edge search) and its local optima as the number of variables grows. Our proposal reuses CV-LR's score and MERIT's model class unchanged and replaces only the search.

Research Program

The first component is the diagnostic. For each method and each dataset with a known graph, we compute two quantities. One is the method's score of the graph it returned. The other is the score of the true graph, given the same parent-fitting procedure, under the same scoring function. Each error then falls into one of two classes. In a search failure, the truth scores higher and the search did not reach it. In a score failure, the returned graph genuinely scores higher. We further split errors by edge type: continuous–continuous, categorical–categorical, and continuous–categorical. No paper in our file reports this decomposition for mixed data. It is useful whether or not our search succeeds, because it tells the field where effort should go.

The second component is the search itself. Each member of a population of $N$ orderings is turned into a graph by choosing each variable's parents from among the variables ranked before it. Parent choice uses cached local CV-LR scores, so the acyclicity constraint is satisfied automatically and costly local scores are reused. A second scoring option fits MERIT-style models, with additive noise for continuous children and an argmax-over-noisy-scores model for $K$-level categorical children. Orderings change through three moves: swapping two neighbours, moving a single variable, and moving a categorical variable together with its current children as a block.

A fast subpopulation hill-climbs on score alone. A steady subpopulation is selected on the Pareto front, meaning members not beaten on both objectives at once, of score and distance to the other steady members. The distance between orderings $\pi$ and $\pi'$ is

$$ D(\pi,\pi') = \sum_{(i,j)\in S} w_{ij}\,\mathbf{1}\big[\pi \text{ and } \pi' \text{ order } i,j \text{ differently}\big]. $$

Here $S$ is the set of variable pairs adjacent in any current population member's graph, and $w_{ij}$ equals $\lambda > 1$ for continuous–categorical pairs and 1 otherwise. Restricting the sum to adjacent pairs means diversity is not spent on orderings that differ only between unrelated variables. Migration runs in one direction, following MF-PBT. A steady member may overwrite a fast member that has stalled. A fast member may enter the steady pool only if it is not beaten on both objectives. This prevents one lucky greedy climber from cloning itself through the population, which is the collapse that MF-PBT documents for standard population-based training.

The third component is cost accounting. Every method is charged in local-score evaluations, counting each cached evaluation once, and in wall-clock time. This keeps comparisons against restarts and plain GES honest.

Baselines

The naive reference points are the empty graph and a random graph of matched density. These matter because causalAssembly reports that PC, DirectLiNGAM, NOTEARS and others did no better than these references in Structural Hamming Distance (SHD, the number of edge additions, deletions and flips needed to reach the true graph) on realistic production data. Any gain must clear these first.

The strongest existing method is CV-LR's kernel score with GES. On the discretized SACHS protein network it reports F1 = 0.94, against DAGMA at 0.42 and NOTEARS at 0.19 (CV-LR). We run it with the authors' setting of about 100 low-rank pivots, the number they report suffices, on identical data, using the same cached score our search uses. Because SACHS has only 11 nodes and 0.94 is near ceiling, we do not expect to beat it there. Matching it within noise counts as parity. Beating it means lower SHD and SID at 30–100 variables under an equal budget of score evaluations. SID, the Structural Intervention Distance, counts how many interventional predictions the learned graph gets wrong.

For the identifiable mixed-model setting, the strongest competitor is MERIT, run with its own independence tests at the sizes it supports. Its paper reports outperforming HCM and the Generalized Score at $p \in \{3,5,10\}$, but our file contains no numeric table entries, so no reported result was found on Lacuna for MERIT's SHD values. We therefore rerun it ourselves.

LiM is run on the binary-only linear subsets it supports. On bivariate and real pairs we also include Crack, which picks the direction with the shorter compressed description of the data and reports 88.2% accuracy on 17 mixed real datasets.

The ablations that isolate our key ingredient are three. In one, the population keeps both subpopulations but sets $\lambda = 1$, so diversity is not type-aware. In another, the population keeps the same moves but uses no diversity objective, so only score drives selection. In the third, the population uses diversity measured as plain adjacency Hamming distance rather than ordering disagreement.

Why not just…?

Why not just run GES or ordering hill-climbing with random restarts at the same budget? This is the real threat. MF-PBT's own results show random search (IQM 17,713 on Humanoid) beating greedy population-based training (16,171), even though structured diversity did better still (23,793) (MF-PBT). We run randomized-order GES and restarted ordering hill-climbing with exactly matched score-evaluation budgets. If restarts match our search, we will report that and recommend restarts, since the diagnostic still stands as the contribution. Our prediction is that restarts help most on single-type edges and least on continuous–categorical orientations, which independent restarts keep rediscovering the same wrong way. Per-edge-type error rates will settle this.

Why not just improve the score instead of the search? If the diagnostic shows that most errors are score failures, then search is the wrong target and our method should give no gain. In that case we would redirect toward better mixed-type scores or independence tests, the direction Raghu et al. supports by finding that test choice dominates search choice. Notably, their finding was for constraint-based methods at modest size. Whether it holds for score-based search at larger sizes is exactly what the diagnostic measures.

Why not just discretize or one-hot encode and use standard tools? Our file already argues against this. Continuous relaxations collapse on discretized SACHS (NOTEARS 0.19, DAGMA 0.42 versus 0.94 for a native mixed score, CV-LR). One-hot encoding biases mixed conditional mutual information toward zero (MS0-∞). We include an all-discretized GES baseline to confirm this on our larger graphs.

Proposed Experiments

Synthetic data comes from MERIT-style mixed additive-noise generators on Erdős–Rényi and scale-free graphs (random graphs with uniform versus hub-dominated degree distributions). We use $p \in \{10, 20, 50, 100\}$, categorical fractions from 10% to 50%, $K \in \{2, 3, 5\}$ categories, and $n$ from 500 to 5000. A matched linear-logistic family supports comparison with LiM. Semi-real data comes from SACHS and CHILD, and from causalAssembly with a chosen subset of its 98 continuous variables thresholded into categories at physically meaningful cut points. Real pairs come from User Knowledge, where MERIT recovers 4 of 5 known links, Boston Housing, and Crack's 17 datasets. Metrics are SHD, SID, F1, ordering accuracy, and per-edge-type orientation error, all at matched score-evaluation budgets.

The decisive checks are three. First, the search-versus-score decomposition for GES with CV-LR at $p \ge 50$ must show a substantial fraction of search failures concentrated on continuous–categorical edges. If it does not, the premise fails. Second, our search must reduce search failures relative to restarts at an equal budget, and the $\lambda = 1$ ablation must lose most of that reduction. This would show that type-aware diversity, not merely having a population, is responsible. Third, on the unimodal-like case of all-continuous data, our search should not be worse than GES. This tests the cost that DPSO reports for diversity forces on single-basin landscapes, where repulsion lowers precision.