Searching for Hidden Cancelling Paths in Bayesian Causal Discovery

Causal discovery methods learn a graph of cause-and-effect arrows from data. They rely on a simple rule: if two variables look statistically unrelated, there is probably no causal link between them. That rule fails when two causal routes cancel. Suppose X raises Y directly but lowers Y through a mediator Z, and the two effects are about the same size. Then X and Y look unrelated even though X causes Y twice over. Bayesian discovery methods keep a probability distribution over possible graphs instead of picking one. Most of them still treat each edge's presence as its own independent coin flip, and that cannot express the actual uncertainty here. The real choice is between two joint answers: "the direct edge exists, the mediator path runs X→Z→Y, and their strengths offset", or "none of that, and Z is a common effect of X and Y". These two answers differ in several edges and in edge directions at once.

This note proposes a posterior approximation that represents exactly this kind of coupled alternative. The approximation is a small mixture of graph hypotheses. Some components are seeded by a "cancellation move": a local rewrite that turns a sparse graph explaining an apparent independence into a denser graph whose paths cancel. The rewrite fits the dense graph's weights so it reproduces the same local covariance, so the two hypotheses start out equally good at explaining the data. The core claim is that much of the failure of neural and Bayesian discovery under near-cancellation is an inference failure, not only a scoring failure. The approximate posterior never finds the dense, cancelling mode, even when the exact posterior gives it real mass. Couplings that link edges, edge directions and weight signs are the right tool to recover that mass. The claim is testable. On small graphs the exact posterior can be enumerated, which lets us split the error into "the score is wrong" and "the approximation missed what the score says".

Where the two directions meet, and what is open

Three lines of work frame the problem. Since Faithfulness Fails benchmarks DCDI, SDCD, DiBS and BayesDAG on data with a controlled faithfulness margin λ. The margin is the smallest partial correlation along any active path, so small λ means near-cancellation. Across methods, performance tracks λ closely (correlation −0.93 between λ and the data needed to solve a graph). Growing the sample from 800 to 80,000 helps only marginally. The best method, DCDI, still has an expected structural Hamming distance of 45.9 on 30-node, degree-2 random graphs. These results motivate the proposal. The authors read them as a wall built into likelihood scoring, but they do not separate the score's error from the error of each method's posterior approximation. Geometry of the faithfulness assumption supports taking the problem seriously. It shows that near-unfaithful parameters are not rare once a finite-sample margin is required, reaching nearly 90% of parameter volume for a sparse 10-node graph at λ = 0.01.

The second line supplies the method. BayesDAG samples a node ordering through continuous node potentials with gradient-based MCMC. Given that ordering, it fits an edge-belief matrix with a factorized Bernoulli variational distribution, and the authors name edge dependence as an open problem. Expressiveness of Parametrized Distributions over DAGs shows that single-ordering distributions are overconfident: total variation 0.34 on a 3-node equivalence class. A 2-component mixture cuts the edge-coupling error by nearly 100×. Generative flow networks such as GFlowNet-DAG and JSP-GFN can in principle represent any joint distribution, but are reported to train about 250× slower than order-based models. The expressiveness paper fits its mixtures to known target distributions, which is a faithful setting. So two questions remain open. Do mixtures find the cancelling mode when they must learn it from a likelihood that weakly favours the sparse wrong graph? And does the way components are placed matter more than how many there are?

The third line constrains the evaluation. Causal Effect Identification in Uncertain Causal Networks searches for the most plausible subgraph in which a target causal effect can be computed from observational data, a property called identifiability. It assumes independent edge probabilities. Under cancellation those probabilities are biased toward the sparse graph, and the edges themselves are correlated. We use this setting as a downstream check, not as the core contribution.

Core Claim

Take near-cancellation in a linear Gaussian model with a direct edge X→Y and a mediated path X→Z→Y. The observed marginal covariance of X and Y is approximately

$$\beta_{XY} + \beta_{XZ}\beta_{ZY} \approx 0,$$

where each $\beta$ is a structural edge coefficient. A sparse graph that has no X–Y edge and treats Z as a common effect of X and Y fits nearly as well, and a sparsity penalty prefers it. At finite margin λ the exact posterior still gives the dense graph a share of mass that shrinks with the sample size and λ. A factorized edge posterior conditioned on one sampled ordering cannot move there. Getting there requires changing the ordering, adding an edge and flipping the sign relationship between weights, all together. The gradient-based ordering sampler has no reason to make that jump, because intermediate states fit worse.

We claim that a mixture of order-plus-edge components, where some components come from explicit cancellation moves, recovers that mass at small extra cost. We further claim that the gain comes from where components are placed, not from how many there are.

Research Program

We build three things.

The cancellation move. Given a component's current graph G, we scan small node sets S of three or four nodes. We look for sets where G implies an independence that the data supports only weakly: the test statistic sits close to its threshold, or the partial correlation is below a small multiple of the estimated noise level. For each such set we propose a component that keeps G outside S. Inside S it uses a different local ordering, chosen so that the implied independence would arise from cancellation rather than from a missing edge. The local subgraph is made dense, and its weights are fit by regression in the new ordering. The regression reproduces the empirical local covariance, so the proposed component starts at almost the same likelihood as G. The prior penalty and any remaining likelihood gap then decide its weight. This is a deterministic, likelihood-preserving jump between graphs that make different independence claims, which is the jump gradient samplers do not make.

The posterior family. The approximation is a mixture

$$q(G,\theta)=\sum_{k=1}^{K}\pi_k\, q_k(G,\theta),$$

where $\pi_k$ are mixture weights. Each $q_k$ is a BayesDAG-style component, with node potentials for the ordering and edge beliefs plus functional parameters $\theta$ given that ordering. Edges are coupled across components but can stay factorized inside each one, which keeps BayesDAG's scaling. Components are spawned by cancellation moves, trained with BayesDAG's existing objective, and pruned when their weight collapses. K stays between 2 and 10, the range where the expressiveness paper found mixtures sufficient.

The error decomposition. On 5-node graphs we enumerate every DAG and compute the exact posterior under the same linear Gaussian likelihood and prior. We then split the total error into two parts. Score error is the distance between the exact posterior and the true graph. Model error is the distance between the approximation and the exact posterior. Both are reported as functions of λ. This shows how much of the "performance wall" any posterior approximation can remove at all.

For the nonlinear benchmarks the move uses a linear local fit only to place the component. Training then proceeds under the nonlinear model. We report separately whether the move helps outside the linear Gaussian regime.

Baselines

The do-nothing reference is BayesDAG as published, with one ordering chain and factorized edge beliefs, run with the authors' settings. It is also the strongest existing Bayesian method on the scale we target. It reports an expected structural Hamming distance of about 296 on 100-variable random graphs, against about 362 for the next baseline, BCD (BayesDAG). Our method changes only the posterior family, so any difference comes from the coupling.

The strongest point-estimate competitor under unfaithfulness is DCDI. It holds the best reported result in the controlled-λ protocol, an expected structural Hamming distance of 45.9 on 30-node, degree-2 random graphs (Since Faithfulness Fails). DiBS is reported best on 5–10 node graphs in the same study and is included there. We rerun DCDI and DiBS on our regenerated data instead of copying numbers, because our λ grid is finer.

The most important baseline is the generic mixture of Expressiveness of Parametrized Distributions over DAGs. It uses the same number of components K, the same component type, and the same training steps and wall-clock budget. Its components are initialized randomly or by independent restarts instead of by cancellation moves. This ablation isolates our key ingredient. No reported result was found on Lacuna for mixtures under controlled unfaithfulness; the only reported numbers are the faithful-setting 0.34 total variation and the roughly 100× coupling-error reduction.

We also run GFlowNet-DAG or JSP-GFN where they fit the compute budget, mainly on small graphs, matching training time instead of iteration count.

All methods share the data draws, the prior's sparsity strength, which is tuned once on faithful validation graphs and then frozen, and the same hyperparameter search budget. Beating the field means two things. On data with λ below the median, our method must reduce expected structural Hamming distance and model error compared with the generic mixture at equal K and compute. On faithful data, it must not raise expected structural Hamming distance by more than seed-to-seed variation.

Why not just…?

Why not just collect more data? Since Faithfulness Fails already scaled samples 100-fold with marginal gains. Geometry of the faithfulness assumption gives a reason: the region of near-unfaithful parameters stays large at any realistic margin. We still sweep sample size in the 5-node exact study. That sweep shows whether model error, which our method targets, shrinks with data on its own. If it does, the case for our method weakens to a small-sample argument, and we will say so.

Why not just use a generic mixture with more components? This is the real threat. The expressiveness results show mixtures can represent the coupling. Our hypothesis is that, when learned from a likelihood that slightly prefers the sparse graph, all components drift into that sparse basin. The equal-K, equal-compute ablation settles the question directly. If randomly initialized mixtures recover the cancelling mode equally often, the contribution reduces to applying known mixtures to a new regime, and we would report that as the finding.

Why not just lower the sparsity penalty or temper the posterior? Weakening the penalty adds mass to dense graphs everywhere, not only where paths cancel. It should therefore raise false edges on faithful parts of the graph. We sweep the penalty and a posterior temperature for BayesDAG. We then compare the best trade-off curve between recall of cancelling edges and false-positive rate against our method's single operating point. If tempering matches us on that curve, the move adds nothing.

Why not just use non-Gaussian noise or interventions? Methods based on independent component analysis (Causal Discovery in Linear Latent Variable Models Subject to Measurement Error, Learning Linear Non-Gaussian Causal Models) break cancellation through higher-order statistics. They assume linear mechanisms and non-Gaussian noise, and our benchmarks use Gaussian and nonlinear data. Interventions break the symmetry, as UT-IGSP shows (Permutation-Based Causal Structure Learning), but our target is the observational case. On Sachs we run UT-IGSP with the interventional data as an upper reference, not as a competitor.

Proposed Experiments

The first experiment is the 5-node exact study. We generate random graphs with expected degree 1 and plant cancelling triangles with margins λ on a grid from 0.3 down to 0.01. The protocol follows Since Faithfulness Fails, with samples of 800, 8,000 and 80,000. We report score error and model error separately, using maximum mean discrepancy to the exact posterior and total variation, along with exact versus approximate posterior mass on the true graph.

The second experiment scales up to random graphs with 10 and 30 nodes (degree 2), plus bipartite and scale-free graphs. Metrics are expected structural Hamming distance, the posterior marginal on edges that truly cancel, and false-positive rates on non-cancelling pairs, all stratified by λ. The third experiment runs on 100-node random graphs to check that we keep BayesDAG's scaling and its reported expected structural Hamming distance of about 296 on faithful data. The fourth uses Sachs and SynTReN. There, ground-truth margins are unknown, so we report held-out negative log-likelihood, agreement with the accepted Sachs network, and the number of distinct components that survive pruning.

As a downstream check, we take an interventional query on the planted graphs, such as the effect of setting Z on Y, which differs between the cancelling and sparse modes. We report the error and calibration of its posterior distribution. We also solve the most-plausible-identifiable-subgraph problem from Causal Effect Identification in Uncertain Causal Networks once with independent marginals and once per mixture component. Then we record how often the independent version returns a subgraph that no component supports.

The decisive outcomes are fixed in advance. The idea succeeds if, at small λ, model error makes up a substantial part of total error in the exact study, and if cancellation-seeded mixtures cut that part markedly more than random-seeded mixtures of the same size, while staying neutral on faithful data. It fails if score error dominates everywhere. In that case, no posterior approximation can recover the true graph from observational data alone, which would sharpen the "performance wall" finding into a statement about the score itself. It also fails if the generic mixture or tempered BayesDAG matches our method at equal compute.