Breaking Bad: Component-Wise Parent Deletion
A novel, simple, yet powerful operator for score-based causal discovery, which is theoretically sound and compatible with existing score-based methods.
Breaking Bad: Component-Wise Parent Deletion for Score-Based Causal Discovery Accepted at UAI 2026 · joint work with LG AI Research
Abstract
Directed acyclic graphs (DAGs) are widely used to represent complex causal relationships in real-world systems. The goal of causal discovery is to learn the underlying DAG from data generated by these systems. While Greedy Equivalence Search (GES) is a well-established score-based algorithm for causal discovery, the GES family often suffers from scalability and sample complexity issues due to its large search space and susceptibility to local optima.
In this paper, we introduce parent deletion, a novel, simple, yet powerful operator for score-based causal discovery. This operator is theoretically sound and effectively alleviates these limitations. Moreover, its simplicity enables seamless compatibility with existing score-based methods, and extensive experiments demonstrate consistent improvements across a wide range of settings.
Motivating experiment
GES often fails to recover the true MEC in finite-sample regimes: sampling variability induces numerous local optima across the search space. Once the algorithm is trapped in a local optimum with a dense structure, score evaluation itself becomes unreliable — large parent sets leave insufficient data for accurate estimation.
Existing mitigations — prioritizing deletion operators (XGES-0) or restricting insertions (LGES) — do not remove the bias. This motivates a metaheuristic that explicitly promotes sparser structures so the search can escape dense local optima.
Contributions
- We investigate the expansion of the neighborhood of local search to reach better solutions, applying heuristic perturbations to the current local optimum — namely, parent deletion.
- This simple perturbation operator enables faster escape from local optima with low computational overhead, leading to notable speedups and substantial performance gains, without sacrificing theoretical guarantees.
- We formally define the parent deletion operator, starting with a single-node deletion, and extend it to a component-wise formulation with complete validity conditions.
Method
Under a decomposable scoring criterion, local scores depend only on the node and its parent set, with their finite-sample variability governed by the parent size. The parent sizes in a CPDAG provide tight lower bounds on the parent sizes across all DAGs in an equivalence class. Consequently, any strictly larger parent size than that in the true DAG implies that the corresponding Markov equivalence class cannot contain the true underlying DAG.
Parent deletion operator
Definition (Parent deletion). Given a CPDAG Pc, let X be a node in Pc with at least one parent, and let H be a subset of the neighbors of X. The operator DeletePa(X, H) modifies Pc by (i) deleting all edges from the parents of X to X, and (ii) orienting each undirected edge between X and H as X → H for every H ∈ H.
This operation creates new v-structures mediated by H. Note that, similar to Insert and Delete, the graph resulting immediately after parent deletion is not necessarily a CPDAG.
Proposition (Validity of parent deletion). The operator DeletePa(X, H) is valid for Pc if and only if Ne(X) \ H is a clique.
At first glance, DeletePa(X, H) appears computationally attractive, since its validity condition depends solely on the local structure around the target node X, rather than on the individual parent nodes whose incident edges are removed. As a consequence, checking its validity incurs the same computational cost as verifying a single-edge deletion, despite removing multiple parent edges simultaneously.
Collateral parental growth. However, this seemingly efficient approach masks a fundamental limitation: the effects of DeletePa(X, H) are not confined to the target node. While it efficiently reduces the parent size of a target variable, it may increase the parent sizes of other nodes as a side effect — nodes in H acquire additional parents by participating in newly induced v-structures. This follows from the fact that if X — Y is an undirected edge in a CPDAG, then X and Y have the same parent set.
Parent deletion over undirected components
To overcome the collateral parental growth induced by single-node parent deletions, we extend parent deletion to operate at the level of nodes connected by undirected edges. An undirected component is defined as a maximal connected component of the graph obtained by removing all directed edges. By construction, all nodes within the same undirected component share the same parent set in the corresponding CPDAG. This property motivates the introduction of a component-wise parent deletion operator: DeletePa(U) removes all directed edges from the parents of every node in U.
One might surmise that such a deletion would require iteratively checking the validity condition for every node in the component. Somewhat surprisingly, this is unnecessary; component-wise parent deletion is always valid and incurs no additional validity-checking cost.
Theorem. DeletePa(U) is valid for any CPDAG Pc.
Applying DeletePa(U) reduces the parent set of each node in U to the empty set, while leaving the local scores of all other nodes unchanged. This yields a simple closed-form expression for the resulting score improvement.
While deleting an entire component’s parents may seem like overkill, it is not necessarily so, since score-based methods often favor insertion over deletion and subsequent search steps can recover useful edges incrementally. Thus, deleting first and then reconstructing meaningful edges can be more practical than identifying and removing unnecessary edges one by one.
Perturbation strategy
The perturbation plugs into existing score-based search algorithms as an iterated local search step. Variants are named after the perturbation they use:
| Method | Perturbation |
|---|---|
| -D | Single-edge deletion |
| -DP | Component-wise parent deletion |
| DP+ | Scheduling: component-wise → node-wise → edge-wise |
Experiments
Setup. Baselines are GES, OPS, XGES, LGES and BOSS; for each search algorithm we compare perturbation strategies. Metrics: SHD (↓), F1 (↑), AID (↓) and runtime (↓). Benchmarks are Erdős–Rényi and scale-free synthetic graphs, plus the biological networks ARTH150, ECOLI70, MAGIC-IRRI and MAGIC-NIAB.
Dense graphs. Performance deteriorates as the expected degree ρ increases. Notably, the degradation in F1 is primarily driven by a sharp decline in precision, indicating that denser graphs are more prone to over-insertion errors. In this regime, the DP and DP+ variants improve performance across all baselines. Moreover, these advantages become more pronounced as ρ increases, suggesting that the proposed perturbation strategies enable the search to escape local optima even in dense graphs. The relatively smaller improvement observed for BOSS is due to the fact that BOSS is less affected by parent-size overestimation.
Performance under varying sample sizes. For GES and GES-D, F1 scores do not increase monotonically and may even decrease, whereas the DP and DP+ variants exhibit steadily improving F1 scores as the sample size increases. Interestingly, when n ≤ 10³, GES-D outperforms GES-DP. We hypothesize that component-wise parent deletion may be too strong in landscapes where local optima are closely spaced. Overall, GES-DP+ outperforms all others across all sample sizes.
High-dimensional condition performance. As the number of nodes d varies from 10 to 500, GES-DP and GES-DP+ outperform both GES and GES-D.
Runtime analysis. GES has the lowest runtime, as it does not incorporate the ILS procedure. GES-DP runs faster than GES-D, as expected, since (i) it avoids iterating over a potentially exponential number of candidates, and (ii) its perturbation loop scales with the number of undirected components rather than edges, i.e., O(d) versus O(d²). Although GES-DP+ incurs additional overhead due to its three-phase design, it has runtime comparable to GES-D.
Grid configurations performance. All variants are evaluated across a total of 81 grid configurations, varying d ∈ {50, 100, 200}, ρ ∈ {2, 3, 5}, n ∈ {10³, 10⁴, 10⁵} and λ ∈ {1, 2, 4}. The DP+ variants consistently outperform other methods. Moreover, this performance gap becomes more pronounced in relatively dense regimes (i.e., ρ = 5). The DP variants consistently outperform all non-ILS methods.
Resources
- Code — LGAI-Research/breaking-bad
- Paper link — to be added once UAI 2026 proceedings are published