Technical Summary: PACER – Acyclic Causal Discovery from Large-Scale Interventional Data

Problem Statement

Inferring the structure of Directed Acyclic Graphs (DAGs) from data is a fundamental challenge in causal discovery. While observational data alone can only identify causal graphs up to Markov equivalence, the integration of interventional data significantly improves identifiability by resolving causal ambiguities. However, as the dimensionality of systems grows (e.g., in genomics with thousands of variables), existing methods face severe scalability bottlenecks.

Modern differentiable causal discovery approaches, such as NOTEARS and its variants (DCDI, DCDFG), recast structure learning as a continuous optimization problem. These methods typically enforce acyclicity via soft penalties (e.g., augmented Lagrangian penalties based on matrix exponentials or spectral radii). This approach suffers from three primary limitations:

1. Invalid Search Space: Optimization occurs over cyclic graphs that lack a well-defined joint likelihood, requiring expensive post-hoc pruning.
2. Numerical Instability: As the number of nodes increases, the computational complexity of acyclicity constraints leads to numerical instability and prohibitive runtimes.
3. Scalability: The reliance on surrogate penalties and the $O(n^3)$ or $O(n^4)$ complexity of constraint gradients limits these methods to small-to-moderate graph sizes, failing to scale to the thousands of variables found in modern high-throughput perturbation screens.

Methodology: PACER

The authors introduce PACER (Perturbation-driven Acyclic Causal Edge Recovery), a framework designed to guarantee acyclicity by construction rather than through penalty terms. PACER operates by defining a probability distribution directly over the space of DAGs, enabling optimization within the valid search space.

1. Bernoulli-Plackett-Luce Distribution

PACER models the DAG space using two components:

• Topological Orderings: It employs the Plackett-Luce distribution to model a distribution over permutations of variables. A permutation $\pi$ defines a valid topological ordering, ensuring that any edge $i \to j$ implies $\pi^{-1}_i < \pi^{-1}_j$.
• Edge Probabilities: It utilizes independent Bernoulli distributions to define a binary mask $B$ that prunes edges.
• Joint Model: The combination yields the Bernoulli-Plackett-Luce distribution, $p(\pi, B | \theta, P)$. An edge $a_{ij}$ exists if and only if the edge mask indicates $b_{ij}=1$ and the permutation places $i$ before $j$. This formulation ensures that every sampled graph is strictly acyclic by design.

2. Objective Function

PACER maximizes the expected log-likelihood of non-intervened variables across all intervention regimes. The objective function $S(\Theta, \Omega)$ is defined as:
$$S(\Theta, \Omega) = \mathbb{E}_{M' \sim M(\Theta)} [f(M', \Omega)] - \lambda \| \mathbb{E}[M(\Theta)] \|_1$$
where $f(M', \Omega)$ is the interventional log-likelihood, and the second term is an $\ell_1$ penalty to encourage sparsity. Crucially, no acyclicity constraint is required because the sampling distribution $M(\Theta)$ only generates DAGs.

3. Optimization Strategies

PACER offers two distinct pathways for optimization, depending on the assumed causal mechanism:

• General Case (REINFORCE): For arbitrary conditional densities (e.g., neural parameterizations), PACER uses the REINFORCE algorithm (Williams, 1992) with an average baseline to estimate gradients. This allows for flexible modeling of non-linear and non-Gaussian mechanisms.
• Linear-Gaussian Case (Analytic Solution): For linear-Gaussian mechanisms, the authors derive a closed-form expression for the expected interventional log-likelihood. This eliminates the need for Monte Carlo sampling entirely. The analytic gradient computation reduces the per-step complexity from $O(n^3)$ (typical of penalty-based methods) to $O(n^2)$, enabling scaling to thousands of variables.

4. Integration of Priors

The framework supports the direct integration of structural prior knowledge. The Plackett-Luce parameters ($\theta$) can be initialized based on expected node centralities, and Bernoulli probabilities ($P$) can be set to enforce or forbid specific edges (e.g., restricting regulation to transcription factors only).

Key Contributions

1. Acyclicity by Design: PACER is the first scalable framework to guarantee acyclicity by restricting the search space to DAGs via a probabilistic model of permutations and edge masks, eliminating the need for surrogate acyclicity penalties.
2. Scalability: By deriving an analytic expression for the expected log-likelihood under linear-Gaussian assumptions, PACER achieves computational complexity of $O(n^2)$, allowing it to scale to networks with thousands of variables where penalty-based methods fail.
3. Unified Framework: It provides a unified likelihood-based treatment for both observational and interventional data, supporting flexible conditional densities and structural priors.
4. Exact Gradient Computation: The derivation of closed-form gradients for linear-Gaussian mechanisms avoids the variance and instability associated with sampling-based estimators in high dimensions.

Experimental Results

The authors evaluated PACER on synthetic benchmarks and real-world datasets, including protein signaling networks and large-scale genetic perturbation data.

• Synthetic Scalability: On synthetic datasets with up to 50 variables, PACER maintained structural accuracy while other differentiable baselines (e.g., DCDI) became numerically unstable or exceeded time limits. PACER scaled to 1,000 variables with linear-Gaussian mechanisms, achieving runtimes two orders of magnitude faster than penalty-based approaches.
• Protein Signaling (Sachs et al., 2005): In both observational and interventional settings, PACER matched or exceeded state-of-the-art methods (e.g., GIES, CAM, NOTEARS) in Structural Hamming Distance (SHD), Structural Intervention Distance (SID), and F1 scores. It successfully recovered canonical signaling pathways (e.g., PKC→RAF→MEK→ERK).
• Large-Scale Genetic Perturbation (CausalBench & Perturb-CITE-seq):
  • On the CausalBench benchmark (RPE1 and K562 cell lines), PACER achieved top-tier Wasserstein distance scores while being over 300 times faster than competing differentiable methods (DCDFG, NOTEARS).
  • On the Perturb-CITE-seq dataset (~1,000 genes, 248 perturbations), PACER achieved the best interventional negative log-likelihood and mean absolute error, outperforming DCDFG by a factor of 300 in runtime.
• Robustness: PACER demonstrated robustness to hyperparameter variations (sparsity coefficient $\lambda$) and maintained performance under imperfect intervention scenarios (off-target effects and soft interventions).

Significance and Claims

The paper claims that PACER demonstrates that exact and scalable causal discovery from high-dimensional perturbation data is achievable through principled search space design.

By moving away from soft acyclicity constraints and directly modeling the distribution over DAGs, PACER overcomes the computational and numerical barriers that have limited differentiable causal discovery to small graphs. The authors position PACER as a practical solution for modern high-dimensional settings in systems biology and genomics, where understanding causal mechanisms from large-scale interventional data is critical but previously computationally prohibitive. The framework is presented as a tool for hypothesis generation that leverages domain knowledge and experimental validation, rather than a standalone decision-making system.