Efficient Ensemble Conditional Independence Test Framework for Causal Discovery

会议: ICLR 2026
arXiv: 2509.21021
代码: 无
领域: 因果推理
关键词: conditional independence test, causal discovery, ensemble method, stable distribution, p-value combination

一句话总结

提出 E-CIT（集成条件独立性检验）框架，通过将数据分割为子集后独立执行检验并基于稳定分布的 p 值聚合方法合并结果，将任意条件独立性检验的计算复杂度降至关于样本量线性，同时在重尾噪声和真实数据等复杂场景下保持甚至提升检验功效。

研究背景与动机

领域现状: 基于约束的因果发现（如 PC 算法）依赖大量条件独立性检验 (CIT) 来确定因果图结构。KCIT（基于核的 CIT）是最流行的方法之一，但关于样本量具有 \(O(n^3)\) 的时间复杂度。

现有痛点: - CIT 本身的高计算复杂度是因果发现的核心瓶颈（而非检验次数） - 现有加速方法（RCIT、FastKCIT）专门针对 KCIT 优化，不是通用框架 - Shah & Peters (2018) 证明没有单一 CIT 在所有条件依赖结构下都有效——因此通用加速框架比改进单一方法更有价值

核心矛盾: 需要大样本保证检验功效，但 CIT 的高复杂度使大样本下计算不可行

本文目标: 设计一个通用的、即插即用的框架，可以应用于任意 CIT 方法以降低计算开销，同时保持统计功效

切入角度: 借鉴集成学习思想——将数据分割为固定大小的子集，独立检验后聚合 p 值。关键创新在聚合方法：利用稳定分布的封闭性质设计一致性有保证的 p 值合并方法

核心 idea: 分而治之 + 稳定分布 p 值聚合 = 任意 CIT 的线性复杂度加速框架

方法详解

整体框架

E-CIT 的三步流水线（Figure 1）： 1. 分割 (Divide): 将 \(n\) 个样本均匀分为 \(K\) 个子集，每个子集大小 \(n_k\)（固定），\(K = n / n_k\) 2. 独立检验 (Test): 对每个子集独立运行基础 CIT，得到 \(K\) 个 p 值 \(\{p_1, \ldots, p_K\}\) 3. 聚合 (Aggregate): 使用基于稳定分布的方法将 \(K\) 个 p 值合并为最终 p 值

当 \(n_k\) 固定时，基础 CIT 的总复杂度为 \(K \times O(f(n_k)) = O(n)\)，与原始 \(O(f(n))\) 相比实现了线性化。

关键设计

1. 基于稳定分布的 p 值聚合 (Definition 2):

   • 功能：将 \(K\) 个子检验的 p 值合并为一个保证统计性质的最终 p 值
   • 核心思路：利用稳定分布的封闭性——若 \(X_j \sim \mathbf{S}(\alpha, \beta, \gamma, \delta)\) 独立同分布，则 \(\frac{1}{K}\sum X_j \sim \mathbf{S}(\alpha, \beta, K^{1/\alpha - 1}\gamma, \delta)\)。检验统计量为： \(T_e = \frac{1}{K} \sum_{k=1}^K F_S^{-1}(p_k)\) 最终 p 值 \(p_e = F_{S'}(T_e)\)，其中 \(S' = \mathbf{S}(\alpha, \beta, K^{1/\alpha-1}\gamma, \delta)\)
   • 设计动机：参数 \(\alpha\) 控制尾部厚度，\(\alpha = 2\) 退化为 Stouffer 方法（正态），\(\alpha = 1\) 为 Cauchy——通过调节 \(\alpha\) 可适配不同 CIT 和数据特性

2. 理论保证 (Theorem 1 & 2):

   • 功能：证明集成检验的有效性、可容许性、无偏性和一致性
   • 核心思路：
     • 有效性: 零假设下 \(p_e\) 均匀分布于 \([0,1]\)（精确 p 值时）
     • 一致性 (Theorem 2): 当 \(K \to \infty\) 时功效趋于 1，条件仅要求：① 子检验期望 p 值 \(\le \alpha_e\)；② p 值密度在 \([0, 1/2]\) 上不低于镜像值；③ 稳定分布参数 \(\alpha \ge 1, \beta = \delta = 0\)
   • 设计动机：一致性条件不对数据生成过程做假设，仅要求子检验合理有效——这使得 E-CIT 即使在基础 CIT 自身缺乏一致性保证的复杂场景中也能提供一致性

3. 灵活性设计:

   • 功能：通过 \(\alpha\) 参数控制 p 值聚合的灵活度
   • 核心思路：根据 Neyman-Pearson 引理，最优合并统计量应是 \(-\sum \log f_1(p_k)\) 的单调变换。不同 CIT 在不同依赖结构下的备择假设 p 值分布不同，\(\alpha\) 允许自适应调节
   • 设计动机：传统方法（Fisher、Stouffer）对应固定的 \(\alpha\) 值，不够灵活；E-CIT 通过 \(\alpha\) 提供简洁的一维调控

损失函数 / 训练策略

• 非监督学习方法，无需训练步骤
• 实践推荐：\(n_k = 400\)（基于经验），\(\alpha \in \{1.75, 2.0\}\)，\(\beta = \delta = 0\)，\(\gamma = 1\)

实验关键数据

主实验

数据生成：后非线性模型，\(Z\) 服从正态或 Laplace 分布，噪声分别为 Student-t、Cauchy、Laplace

计算效率对比 (Figure 2, KCIT 加速):

方法	时间复杂度	n=2000 运行时间	Type I Error	检验功效
KCIT (原始)	\(O(n^3)\)	~100s	~0.05	基线
RCIT	\(O(n)\)	~0.1s	~0.05	略低于 KCIT
FastKCIT	\(O(n \log n)\)	~1s	~0.05	接近 KCIT
E-KCIT	\(O(n)\)	~0.1s	~0.05	接近或优于 KCIT（重尾时更好）

跨方法通用性 (Table 2, n=1200, Normal Z, t-noise df=2):

方法	Orig. Power	Ensemble Power (α=1.75)
RCIT	0.548	0.623
LPCIT	0.422	0.447
CMIknn	0.982	0.988
FisherZ	0.510	0.561
CCIT	0.904 (Type I=0.454!)	0.816 (Type I=0.286↓)

消融实验

真实数据 Flow-Cytometry (Table 3):

方法	Orig. F1	Ensemble F1
KCIT	0.624	0.695
RCIT	0.665	0.687
LPCIT	0.691	0.741
CMIknn	0.779	0.756
FisherZ	0.737	0.767

关键发现

1. 显著加速: E-KCIT 将 KCIT 的 \(O(n^3)\) 降至 \(O(n)\)，运行时间与 RCIT 相当
2. 功效不降反升: 在重尾噪声（Student-t df=2、Cauchy）下，E-KCIT 功效优于 KCIT 和 RCIT——子集上估计更稳定
3. 通用性: 对 6 种不同 CIT 方法（KCIT、RCIT、LPCIT、CMIknn、CCIT、FisherZ）均有效
4. 真实数据优势: 在 Flow-Cytometry 数据上，对大多数方法提升 F1-score 2-5 个百分点
5. CCIT 的意外发现: E-CIT 显著降低了 CCIT 过高的 Type I error（从 0.45+ 降至 0.28-0.34），牺牲少量功效换取了更好的校准
6. 因果发现应用 (Figure 3): 在非线性 + 加性噪声因果图上，E-KCIT 在 F1 和 SHD 上均优于 KCIT 和 RCIT

亮点与洞察

1. 通用框架而非特定方法: 是加速器而非新 CIT——可即插即用到任意现有方法中
2. 理论一致性条件极其宽松: 不对数据/模型做假设，只要求子检验"合理有效"
3. 稳定分布的巧妙应用: 利用稳定分布的封闭性实现精确的 p 值聚合，\(\alpha\) 参数提供灵活调控
4. 实际启示: 在复杂场景（重尾、真实数据）下，集成反而能提升功效——因为小样本估计更稳定，聚合后取长补短

局限与展望

1. 理论假设子检验 p 值独立同分布——数据中可能存在相关性（如时序数据或分布漂移）
2. \(\alpha\) 参数的最优选择是 context-dependent 的，当前仅给出经验推荐 \(\{1.75, 2.0\}\)
3. 子集大小 \(n_k\) 需要足够大以保证子检验有效——对极高维条件集 \(Z\) 可能仍面临维度灾难
4. CMIknn 这类本身已很强的方法受益较小，说明框架更适合加速中等功效的方法
5. 未来方向：处理相关 p 值、针对特定 CIT 优化 \(\alpha\)、自适应子集大小选择

相关工作与启发

• RCIT (Strobl et al., 2019): 用随机傅里叶特征加速 KCIT——但仅适用于 KCIT，E-CIT 是通用框架
• FastKCIT (Schacht & Huang, 2025): 用 GMM 分割数据——思路类似但专为 KCIT 设计
• Cauchy 合并方法 (Liu & Xie, 2020): 用 Cauchy 分布合并 p 值用于 WGS 检验——E-CIT 推广到一般稳定分布并面向 CIT 场景
• 启发: 分而治之 + 聚合是解决大规模统计检验的通用范式，有望推广到其他高计算开销的检验问题

评分

• 新颖性: ⭐⭐⭐⭐ 将稳定分布的封闭性创造性地应用于 CIT 的 p 值聚合，框架思想清晰实用；但"分割-聚合"本身不算全新
• 实验充分度: ⭐⭐⭐⭐⭐ 合成数据 + 真实数据 + 因果发现应用，6 种 CIT 方法 × 多种噪声分布 × 多种样本量，消融充分
• 写作质量: ⭐⭐⭐⭐ 结构清晰，理论和实验衔接好，Figure 1 的框架概览直观；证明放附录保持主文流畅
• 价值: ⭐⭐⭐⭐ 实用性强——可直接插入现有因果发现流水线；对大规模因果发现有实际意义

相关论文

• [ACL 2025] IRIS: An Iterative and Integrated Framework for Verifiable Causal Discovery
• [ICLR 2026] Direct Doubly Robust Estimation of Conditional Quantile Contrasts
• [ICLR 2026] Synthesising Counterfactual Explanations via Label-Conditional Gaussian Mixture Variational Autoencoders
• [CVPR 2026] MaskDiME: Adaptive Masked Diffusion for Precise and Efficient Visual Counterfactual Explanations
• [AAAI 2026] MUG: Multi-agent Undercover Gaming — Hallucination Removal via Counterfactual Test for Multimodal Reasoning