PACER: 从大规模干预数据中进行无环因果发现

# PACER：大规模干预性数据下无环因果发现
来源：https://arxiv.org/html/2605.15353
Sílvia Fàbregas SalazarSoyon ParkIvo Alexander BanArtyom GadetskyNikita DoikovMaria Brbić

###### 摘要

推断有向无环图（DAG）的结构是因果发现中的核心挑战。虽然干预性数据可以提高可辨识性，但现有方法仍受困于软无环约束，导致优化过程需处理无效的环状图、数值不稳定且可扩展性降低。我们提出 PACER（扰动驱动无环因果边恢复），这是一种可扩展的因果发现框架，通过设计保证了无环性。PACER 通过变量排列和边概率的联合模型定义了 DAG 上的分布，从而无需替代惩罚项即可直接对有效的因果结构进行优化。它支持对观测数据与干预性数据进行基于似然的处理，提供灵活的条件密度函数，并能整合结构先验知识。对于线性-高斯机制，我们推导出了干预对数似然的闭式表达式，从而获得了显著的计算优势。实验表明，在蛋白质信号转导和大规模遗传扰动基准上，PACER 达到或超越了最先进方法，可扩展至数千变量，并且相比基于惩罚的方法实现了高达两个数量级的加速。这些结果表明，通过原则性的搜索空间设计，可以从高维扰动数据中实现精确且可扩展的因果发现。

机器学习，ICML，因果发现，干预性数据

## 1 引言

从数据中推断有向无环图（DAG）的结构是因果发现的基本任务。虽然观测数据只能将因果图识别到马尔可夫等价类，但整合干预性数据可以通过解决原本无法区分的因果歧义，显著提高发现准确性（Hauser & Bühlmann, 2012）。这在基因组学等领域尤其重要，高通量扰动实验（如单细胞 Perturb-seq 筛选（Dixit 等, 2016））现已能够收集跨越数千变量的大规模实验干预数据。然而，随着这些系统维度的增加，结构学习的计算成本成为了主要瓶颈。

现代可微分因果发现试图通过将结构学习重新表述为连续优化问题，来探索有向无环图的超指数搜索空间。一种主要策略是利用基于矩阵的无环性表征，并通过增广拉格朗日惩罚来强制执行（Zheng 等, 2018; Brouillard 等, 2020; Lopez 等, 2022）。尽管这些框架相比传统的贪心或组合搜索更具可扩展性，但它们存在固有的结构和计算局限性。特别是，由于无环性仅作为软惩罚来执行，这些方法需要对缺乏良好定义联合似然的环状配置进行评估和优化。此外，随着节点数量的增加，标准无环性约束的计算复杂度常常导致数值不稳定（Nazaret 等, 2024）和不可接受的运行时间（Bello 等, 2022）。

在此，我们提出 PACER（扰动驱动无环因果边恢复），一个可扩展的因果发现框架，它利用观测数据和干预性数据直接在 DAG 空间中进行搜索。与在优化过程中放宽无环性的先前方法不同，PACER 通过构造保证了无环性。PACER 的主要特点包括：

- **通过设计保证无环性**。我们引入了一个 DAG 上的分布，用于同时对拓扑顺序进行建模并筛选因果边。这种公式化确保了优化过程中评估的每一个结构都是严格无环的，从而消除了对昂贵无环项的需求，并确保搜索在整个学习过程中始终停留在 DAG 空间内。
- **灵活的可微分因果发现**。PACER 提供了一个统一的基于似然的框架，联合利用了观测数据和干预性数据。该方法支持多种条件密度模型，包括神经参数化以及针对特定数据模态定制的分布。
- **精确的梯度计算**。我们在线性-高斯机制下推导出了干预对数似然目标的闭式表达式。该解析梯度使 PACER 能够扩展到数千变量，相比基于惩罚的可微分方法实现了高达两个数量级的加速。
- **归纳偏置与先验知识**。PACER 是一个灵活的框架，支持直接整合结构先验，例如节点中心性期望或在建模基因组调控网络时的转录因子结合约束。

我们在来自蛋白质信号转导网络和大规模遗传扰动基准的观测与干预数据上评估了 PACER。我们的结果表明，PACER 达到或超越了最先进因果发现方法的性能。关键的是，它能够在包含数千变量的网络中进行因果发现，相比基于惩罚的可微分方法，运行时间减少了高达两个数量级。PACER 是一个多功能的因果发现框架，能够高效且有效地从高维干预数据中重建因果图。

## 2 相关工作

因果发现传统上被框架化为对 DAG 指数空间的离散搜索。我们将 PACER 与基于排列的搜索、可微分无环松弛以及用于干预数据因果发现的框架进行对比，从而将其定位在现代因果发现领域。

##### 基于排列的因果发现。

一系列长期的工作利用了 DAG 与变量拓扑顺序之间的对应关系。一个突出的例子是最稀疏排列（SP）原理，它搜索能产生与数据一致的最稀疏 DAG 的排列（Raskutti & Uhler, 2018）。实际的方法在顺序上进行贪心或组合搜索（Singh & Moore, 2005; Silander & Myllymäki, 2006; Lam 等, 2022），或者先估计一个顺序再选择边，如 CAM（Bühlmann 等, 2014）。这些方法通过构造保证无环性，但依赖启发式的稀疏化或局部分解，并且返回单个图，从而限制了其表示结构变异的能力。此外，它们的计算成本随着变量数量超指数增长（最坏情况下为 \(O(n!)\)），限制了可扩展性。相比之下，PACER 采用基于 Plackett–Luce 参数化（Luce, 1959; Plackett, 1975; Gadetsky 等, 2020）的顺序概率表示，并联合学习边概率。这产生了 DAG 上的灵活分布，能够捕捉结构变异同时保持无环性。与经典排列搜索相比，PACER 以随机优化替代了精确枚举，从而获得了显著的可扩展性（二次复杂度而非阶乘复杂度）。

##### 可微分因果发现。

最近的进展将 DAG 学习重新表述为连续问题，这一转变主要由 NOTEARS（Zheng 等, 2018）推动。该方法引入了无环性的平滑表征，并扩展到非线性机制（Zheng 等, 2020）和神经参数化（Lachapelle 等, 2020; Bello 等, 2022）。然而，这些方法的可扩展性从根本上受到无环性约束及其梯度复杂度的阻碍，随着变量数量增加常导致数值不稳定（Nazaret 等, 2024）。此外，这些框架依赖增广拉格朗日惩罚，在训练过程中评估环状图，需要敏感的调整超参数和事后阈值化。相比之下，PACER 通过直接在排列空间中操作来避免替代正则化器，通过构造保证无环性，并且消除了事后阈值化的需要。

##### 通过三角邻接矩阵的排列对 DAG 进行建模。

越来越多的工作通过学习变量顺序上的分布来应对 DAG 发现的组合挑战。可微分方法如 DP-DAG（Charpentier 等, 2022）、BCD Nets（Cundy 等, 2021）、BCNP（Dhir 等, 2025）和 BayesDAG（Annadani 等, 2023）学习了顺序上的分布，但通常依赖 \(O(n^3)\) 算子，在高维设置中限制了可扩展性。此外，这些方法主要关注观测数据。相比之下，PACER 引入了计算效率更高的参数化，有效地扩展到数千变量，并且能够在一个基于似然的目标中处理干预数据。

##### 基于干预数据的因果发现。

干预数据提高了可辨识性，并已被纳入离散和可微分框架。传统方法将经典框架扩展到干预设置，包括基于评分的方法如 GIES（Hauser & Bühlmann, 2012）和 IGSP（Wang 等, 2017），它们利用不变性原理来定向边。然而，这些方法面临可扩展性挑战，并且由于依赖贪心启发式，容易陷入局部最优。更近期的可微分方法，例如 DCDI（Brouillard 等, 2020）、DCDFG（Lopez 等, 2022）和 ENCO（Lippe 等, 2022），使用神经似然联合建模观测和干预数据。然而，这些策略在优化过程中允许环状配置，可能导致定义不良的联合分布，并且需要事后剪枝以恢复有效的无环结构。PACER 则在训练过程中始终保持有效的 DAG 分解，从而能够在不使用辅助约束的情况下，高效地从干预数据中进行基于似然的学习。

## 3 背景

参见图注

**图 1：**框架概述。PACER 使用 Plackett-Luce 分布对变量的拓扑顺序进行建模。在生成的 DAG 中，权重较高的节点更有可能排在权重较低的节点之前。来自该分布的样本产生完全的 DAG，这些 DAG 再通过来自独立的、边特定的伯努利分布的样本进行筛选。这定义了我们在 DAG 上的伯努利-普莱克特-卢斯（Bernoulli-Plackett-Luce）分布。在训练时，我们采样多个候选图，并根据基于似然的目标函数对其进行评分。然后，我们使用 REINFORCE 梯度更新（Williams, 1992）来优化伯努利-普莱克特-卢斯模型的参数。

##### 基于干预数据的可微分因果发现。

DCDI（Brouillard 等, 2020）和 DCDFG（Lopez 等, 2022）优化一个基于干预似然的目标 \(S(\Theta, \Omega)\)，满足无环约束 \(\mathcal{C}(\mathbb{E}[M(\Theta)])\)：
\[
\max_{\Theta, \Omega} \quad S(\Theta, \Omega) \quad \text{使得} \quad \mathcal{C}(\mathbb{E}[M(\Theta)]) = 0,
\]
其中 \(\Theta\) 参数化邻接矩阵上的分布 \(M(\Theta)\)，\(\Omega\) 表示每个变量以其父变量为条件的条件分布参数。约束 \(\mathcal{C}(\cdot)=0\) 确保期望邻接矩阵对应一个无环图，使用基于谱半径或矩阵指数的可微惩罚函数（Zheng 等, 2018; Lopez 等, 2022）。评分 \(S(\Theta, \Omega)\) 定义为：
\[
\mathbb{E}_{M' \sim M(\Theta)} \left[ \sum_{r=1}^{R} \mathbb{E}_{X \sim P_{\text{data}}^{(r)}} \sum_{j \notin \mathcal{I}_r} \log p_{\Omega}^j (X_j | M'_j, X_{-j}) \right] - \lambda \| \mathbb{E}[M(\Theta)] \|_1.
\]
该评分反映了所有 \(r \in \{1, ..., R\}\) 干预机制下非干预变量 \(j \notin \mathcal{I}_r\) 的期望对数似然，并通过期望邻接矩阵上的 \(l_1\) 惩罚来鼓励稀疏网络。这里，\(P_{\text{data}}^{(r)}\) 表示在机制 \(r\) 下数据点 \(X\) 的分布，\(p_{\Omega}^j\) 表示变量 \(X_j\) 的条件密度模型，其父变量由采样的邻接矩阵 \(M'_j \sim M(\Theta)\) 指定。

##### 假设。

我们在以下假设下操作。首先，我们假设因果充分性，即系统中没有未观测的共同原因（潜在变量）。其次，我们考虑随机的完美干预，其中干预针对特定变量（或多个变量），通过修改其条件分布而不一定将其固定为常数值。第三，我们对变量的域没有全局限制：该框架功能上与似然函数的选择无关，可以通过选择合适的似然函数来适应离散、连续或混合数据。最后，我们假设潜在的因果结构是一个有向无环图（DAG）。重要的是，我们的方法返回来自干预马尔可夫等价类（Hauser & Bühlmann, 2012）中的一个成员，即输出应被视为一组合理结构中的元素，而非单个确定的图。

## 4 PACER

我们提出 PACER（扰动驱动无环因果边恢复），这是一种可扩展的因果发现方法，适用于具有数千变量的大规模干预数据（图 1）。PACER 的关键思想是将 DAG 结构