因果发现算法现代综述

1. 引言

因果发现（Causal Discovery）旨在从观测数据中自动推断变量之间的因果关系，是因果推断领域的核心问题之一。与传统相关性分析不同，因果发现试图回答”什么导致什么”而非”什么与什么相关”的问题。¹

1.1 问题定义

给定一组变量 $X_1,X_2,...,X_n$ 的观测数据集，因果发现问题要求学习一个有向无环图（DAG） $\mathcal{G}$，使得：

• 节点集 $V=\{X_1,...,X_n\}$
• 边 $X_i\to X_j$ 表示 $X_i$ 是 $X_j$ 的直接原因
• 图满足马尔可夫条件和忠诚性假设

1.2 基本假设

假设	描述
马尔可夫性	给定父节点，节点条件独立于其非后代
faithfulness	所有条件独立性都源于图结构
Causal Sufficiency	不存在未观测的共同原因
无混杂假设	可识别直接因果效应

---

2. 约束方法（Constraint-based Methods）

约束方法通过统计独立性检验来发现因果结构，核心思想是利用条件独立性关系推断因果方向。²

2.1 PC算法

PC算法（Spirtes et al., 2000）是最经典的约束方法：

算法流程：
1. 从完全图开始
2. 迭代删除边：
   - 对每对变量 (X, Y)
   - 对每个大小为k的分离集 S
   - 若 X ⊥ Y | S，则删除边 X—Y
3. 定向剩余边（使用v-结构、方向传播规则）

核心性质：

• 在Causal Sufficiency假设下，输出忠实于数据的等价类（CPDAG）
• 时间复杂度：$O(n^{k+2})$，其中 $k$ 是最大分离集大小

2.2 FCI算法

FCI算法（Fast Causal Inference）处理存在未观测混杂变量的情况：

• 输出部分有向无环图（PAG）
• 允许存在不可判定的边方向
• 时间复杂度更高，但假设更弱

2.3 GES算法

GES算法（Greedy Equivalence Search，Chickering 2002）：

• 分数搜索：使用贝叶斯信息准则（BIC）或MDL
• 贪婪搜索：从空图开始，逐步添加、删除、反转边
• 局部最优保证：在某些正则条件下

# GES伪代码
def GES(data):
    forward_step()  # 添加边直到局部最优
    backward_step()  # 删除边直到局部最优
    return equivalence_class

2.4 LiNGAM方法

LiNGAM（Linear Non-Gaussian Acyclic Model，Shimizu et al., 2006）³：

核心假设：

• 线性关系：$X_i={\sum }_j{b}_j{X}_j+e_i$
• 非高斯噪声：$e_i$ 非高斯分布
• 无环性：DAG结构

可识别性：在非高斯假设下，因果方向可唯一确定（高斯情况下不可区分）

数学推导：
设数据矩阵 $X$ 满足 $X=BX+E$，其中 $B$ 是严格下三角矩阵。

若 $E$ 的列独立且非高斯，则 $B$ 可从 $X$ 唯一识别。

---

3. 分数方法（Score-based Methods）

分数方法将因果发现形式化为优化问题，通过最大化某个评分函数来选择最优结构。⁴

3.1 结构方程模型

结构方程模型（SEM）：
$X_i=f_i(P{A}_i,e_i)$

其中 $P{A}_i$ 是 $X_i$ 的父节点，$e_i$ 是独立噪声。

线性SEM：
$X=BX+E$

其中 $B_{ij}\ne 0$ 当且仅当存在边 $X_j\to X_i$。

3.2 评分函数

评分函数	公式	特点
BIC	$\text{BIC}(\mathcal{G}) = \log p(D	\hat{\theta}{\mathcal{G}}) - \frac{d{\mathcal{G}}}{2}\log n$
MDL	$\text{MDL}(\mathcal{G}) = -\log p(D	\mathcal{G})$
贝叶斯评分	$\log p(D	\mathcal{G}) + \log p(\mathcal{G})$

3.3 优化方法

贪婪搜索（GES/Grow-Shrink）：

• 空间复杂度高，$O(2^{n^2})$
• 适合中等规模问题（$n<50$）

动态规划：

• 精确求解，但指数复杂度
• 适合树结构或链结构

整数规划：

• 使用MIP求解器
• 可处理中等规模问题

---

4. 可微分学习方法

可微分学习将组合DAG约束放松为连续优化问题，利用神经网络进行端到端学习。⁵

4.1 NOTEARS算法

NOTEARS（Non-combinatorial Optimization via Trace Exponential and Augmented lagRangian for Structure learning，Yu et al., 2019）⁶：

核心思想：将DAG约束转化为矩阵迹函数

$h(B)=\text{tr}(e^{B\circ B})-n=0$

其中 $B$ 是加权邻接矩阵，$\circ$ 表示Hadamard积。

优化问题：
${\min }_B\frac{1}{2}\Vert X-XB{\Vert }_F^2+\frac{\lambda }{2}\Vert B{\Vert }_F^2\text{s.t.}h(B)=0$

算法流程：

def NOTEARS(X, lambda_reg):
    B = initialize_zeros(n, n)
    while not converged:
        B = B - lr * gradient
        # Augmented Lagrangian update
        h = trace_exp(B) - n
        B = projection_to_dag(B)  # if needed
    return B

4.2 NOTEARS变体

变体	改进
NOTEARS-MLP	使用MLP建模非线性关系
NOTEARS-Linear	线性假设，计算高效
GraN-DAG	基于神经网络，可处理非线性
DAG-GNN	图神经网络架构

4.3 DAG约束的松弛形式

$h(B)=0$ 的多种松弛形式：

1. 矩阵指数松弛：
   $h(B)=\text{tr}(e^{B\circ B})-n$

2. 幂级数松弛：
   $h(B)={\sum }_{k=1}^n\frac{\text{tr}(B^k)}{n}$

3. 子模松弛：
   $h(B)=\Vert B{\Vert }_{\ast }-\Vert B{\Vert }_{\text{diag}}$

4.4 NOTIME算法（2025）

NOTIME（AISTATS 2025）⁷：

核心创新：

• 首个在LiNGAM模型下具有可证明可识别性保证的可微分DAG学习算法
• 基于联合独立性度量构建
• 对数据归一化不敏感

名称含义：
Non-combinatorial Optimization of Trace exponential and Independence MEasures

---

5. 时序因果发现

时序因果发现处理时间序列数据，目标是发现变量之间的时滞因果关系。⁸

5.1 Granger因果性

Granger因果性（Granger, 1969）：

$X$ Granger-cause $Y$ 当且仅当使用 $(X,Y)$ 的历史预测 $Y$ 比仅用 $Y$ 的历史预测更准确。

数学定义：
$P(Y_{t+1}|Y_t,Y_{t-1},...)<P(Y_{t+1}|Y_t,Y_{t-1},...,X_t,X_{t-1},...)$

局限：

• 只能发现滞后因果关系
• 不能处理同期因果关系
• 需要因果充分性假设

5.2 PCMCI算法

PCMCI（Peter-Clark Moments Conditional Independence，Runge et al., 2019）⁹：

算法流程：

1. 条件独立性筛选（PC阶段）
   - 移除与目标变量条件独立的父节点
   
2. Moment Conditional Independence (MCI)
   - 利用时间序列特性进行更精确的因果检验
   
3. 因果时间延迟估计

优势：

• 可处理高维时序数据
• 计算效率高
• 适用于大规模变量集

5.3 TiMINo算法

TiMINo（Peter et al., 2018）：

• 基于信息论的时序因果发现方法
• 利用状态向量表示时间依赖关系
• 理论保证：在渐近情况下可正确识别因果结构

5.4 深度学习时序因果发现

CausalFormer（2024）

CausalFormer（arXiv:2406.16708）¹⁰：

• 因果感知Transformer + 分解式因果检测器
• 多核因果卷积：沿时间维度聚合输入时间序列
• 回归相关性传播：利用整个深度学习模型识别因果关系

TS-CausalNN（2024）

TS-CausalNN（arXiv:2404.01466）：

• 同时发现同期和滞后因果关系
• 并行自定义因果层卷积块：自然处理非平稳性
• 无环性约束：使用增广拉格朗日方法

STIC（2024）

STIC（Short-Term Invariance using Convolutional Neural Networks，arXiv:2408.08023）：

• 利用短时时间和机制不变性
• 两种因果卷积核：
  • 短时时间不变性卷积核
  • 短时机制不变性卷积核

---

6. 因果发现的评估基准

6.1 基准测试数据集

基准	描述	规模
Sachs	蛋白质信号网络	11节点
Tuebingen	因果发现基准集	多种规模
Semi-Continuous	半连续数据	中等规模
OCDB	开放因果发现基准	大规模

6.2 评估指标

指标	公式/描述
SHD（Structural Hamming Distance）	与真实CPDAG的边差异数
F1-Score	边恢复的精确率和召回率
MCC（Matthews相关系数）	平衡考虑真阳/真阴/假阳/假阴
IoU（Intersection over Union）	边集合的Jaccard相似度

$SHD(\hat{\mathcal{G}},\mathcal{G})=|E_{\hat{\mathcal{G}}}\Delta E_{\mathcal{G}}|$

6.3 CausalRivers基准（ICLR 2025）

CausalRivers是最大规模的时序因果发现野外评估数据集：

• 覆盖范围：德国东部（666节点）、巴伐利亚（494节点）
• 时间跨度：2019-2023年，15分钟分辨率
• 特点：包含真实分布偏移场景（如洪水事件）

---

7. 方法对比与选择指南

7.1 方法分类总结

因果发现方法
├── 约束方法
│   ├── PC算法（经典）
│   ├── FCI算法（允许未观测混杂）
│   └── GES算法（分数搜索）
├── 分数方法
│   ├── BIC/MDL评分
│   └── 贝叶斯评分
├── 可微分方法
│   ├── NOTEARS系列
│   ├── GraN-DAG
│   └── NOTIME（2025）
└── 时序方法
    ├── Granger因果性
    ├── PCMCI
    ├── CausalFormer
    └── TS-CausalNN

7.2 场景选择指南

场景	推荐方法
小规模数据（n<20）	PC算法、GES算法
中等规模（20<n<100）	NOTEARS、GraN-DAG
大规模数据（n>100）	CauScale（2026）、DAG-GNN
需要理论保证	LiNGAM、NOTIME
时序数据	PCMCI、CausalFormer
存在未观测混杂	FCI算法
非线性关系	GraN-DAG、神经网络方法

7.3 各方法优缺点

方法	优点	缺点
PC	理论基础扎实、无参数假设	输出等价类、计算量大
GES	有最优性保证	可能陷入局部最优
NOTEARS	可微分、端到端	不保证DAG约束、缺乏可识别性
LiNGAM	因果方向可识别	仅线性假设
神经网络方法	可处理非线性	缺乏理论保证

---

8. 最新进展与未来方向

8.1 2024-2026年重要进展

方法	年份	突破
CauScale	2026	1000节点规模、推理速度提升13000倍
NOTIME	2025	首个LiNGAM下可证明可识别性的可微分方法
Score Matching	2025	支持隐变量的得分函数方法
CausalRivers	2025	最大规模时序基准

8.2 开放问题

1. 可识别性理论：什么条件下可以从观测数据唯一识别因果结构？
2. 大规模高效算法：如何处理百万节点级别的因果图？
3. 分布外泛化：在分布偏移下如何保证因果发现的鲁棒性？
4. 隐变量处理：如何有效发现存在隐变量的因果结构？
5. 因果表示学习：如何利用深度学习表示学习因果结构？

8.3 未来研究方向

• 神经符号因果发现：结合神经网络表达力和符号推理的可解释性
• 因果基础模型：类似语言模型的基础模型用于因果发现
• 因果强化学习：利用因果结构指导探索
• 多模态因果发现：跨模态数据的因果关系发现

---

9. 代码实现

9.1 使用CausalDiscovery库

import numpy as np
from causalnex.structure.pytorch import DAGRegressor
from sklearn.preprocessing import StandardScaler
 
# 数据准备
X = StandardScaler().fit_transform(data)
 
# 使用NOTEARS方法
dag_model = DAGRegressor(
    method='notears',
    beta=0.5,  # L2正则化
    tabu_edges=100  # 防止过拟合
)
dag_model.fit(X)
 
# 获取邻接矩阵
adjacency_matrix = dag_model.state['adjacency'].numpy()

9.2 PC算法实现

from causallearn.search.ConstraintBased.PC import pc
from causallearn.utils.cit import fisherz
 
# PC算法
data = np.array(dataset)
cg = pc(data, alpha=0.05, indep_test=fisherz)
 
# 获取图结构
G = cg.G
adj_matrix = G.graph  # adjacency matrix

9.3 时序因果发现

from tigramite import data_processing as dp
from tigramite.pcmci import PCMCI
from tigramite.independence_tests import ParCorr
 
# 数据准备
 dataframe = dp.DataFrame(data, 
                          var_names=var_names,
                          time_axis=0)
 
# PCMCI
pcmci = PCMCI(dataframe=dataframe, 
              cond_ind_test=ParCorr())
 
# 运行
results = pcmci.run_pcmci(tau_max=5, 
                           pc_alpha=0.05)

---

10. 参考文献

---

相关主题

• 因果表示学习理论
• 因果反事实推理
• LLM因果推理能力评估
• 概率图模型综述

Footnotes

1. Spirtes, P., Glymour, C., & Scheines, R. (2000). Causation, Prediction, and Search. MIT Press. ↩

2. Spirtes, P., & Zhang, K. (2016). Causal discovery and inference: Concepts and recent methodological advances. Applied Informatics. ↩

3. Shimizu, S., Hoyer, P. O., Kerminen, A. J., & Jordan, M. I. (2006). A linear non-Gaussian acyclic model for causal discovery. JMLR. ↩

4. Chickering, D. M. (2002). Optimal structure identification with greedy search. JMLR. ↩

5. Zheng, X., Aragam, B., Ravikumar, P., & Xing, E. P. (2018). DAGs with NO TEARS: Continuous optimization for structure learning. NeurIPS. ↩

6. Yu, K., Liu, L., & Suzuki, A. (2019). Revisiting NOTEARS: A boosting perspective. ICLR. ↩

7. Berrévoets et al. (2025). NOTIME: Identifiable DAG Learning with Trace Exponential and Independence Measures. AISTATS 2025. ↩

8. Runge, J. (2018). Causal network reconstruction from time series. Springer. ↩

9. Runge, J., et al. (2019). Inferring causation from time series with PCMCI. Nature Communications. ↩

10. CausalFormer Authors. (2024). CausalFormer: Transformer-based Temporal Causal Discovery. arXiv:2406.16708. ↩