2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane
Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.
academic

Local Causal Discovery for Statistically Efficient Causal Inference

基本信息

  • 论文ID: 2510.14582
  • 标题: Local Causal Discovery for Statistically Efficient Causal Inference
  • 作者: Mátyás Schubert (University of Amsterdam), Tom Claassen (Radboud University Nijmegen), Sara Magliacane (University of Amsterdam)
  • 分类: stat.ML cs.AI cs.LG
  • 发表时间: 2025年10月16日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.14582v1

摘要

因果发现方法可以为一对目标变量的因果效应估计识别有效的调整集，即使在潜在因果图未知的情况下。全局因果发现方法专注于学习整个因果图，因此能够恢复最优调整集（即具有最低渐近方差的集合），但随着变量数量的增长，它们很快变得计算上难以承受。局部因果发现方法通过专注于目标变量的局部邻域提供了更可扩展的替代方案，但仅限于统计上次优的调整集。在这项工作中，作者提出了局部最优调整发现（LOAD），这是一种结合了局部方法的计算效率和全局方法的统计最优性的可靠且完整的因果发现方法。

研究背景与动机

问题定义

在因果推断中，估计两个变量之间的因果效应是一个核心任务。当潜在的因果图未知时，需要通过因果发现方法来识别有效的调整集用于因果效应估计。现有方法面临一个根本性的权衡：

  1. 全局方法的困境：全局因果发现方法（如PC算法）能够学习完整的因果图并恢复最优调整集，但计算复杂度随变量数量指数增长，在大规模问题中不可行。
  2. 局部方法的局限：局部因果发现方法（如MB-by-MB、LDECC）计算效率高，但只能恢复次优的调整集，导致因果效应估计的渐近方差较高。

研究动机

作者发现现有局部方法存在以下问题：

  • LocalPC算法在识别邻接变量时不够可靠，可能错误地将非邻接的配偶识别为邻接
  • LDECC算法不完整，在某些情况下无法定向所有可定向的边
  • LDP算法在某些可识别效应为零时可能错误地报告效应不可识别

因此，需要一种既保持局部方法计算效率又能达到全局方法统计最优性的新方法。

核心贡献

  1. 开发了基于局部信息确定因果效应可识别性的方法：提出了仅使用局部信息就能判断因果效应是否可识别的充分必要条件。
  2. 提出了LOAD算法：一个可靠且完整的方法，仅使用变量周围的局部信息就能识别最优调整集。
  3. 全面的实验评估：在合成数据和真实数据上评估LOAD，证明它能以低计算成本恢复高质量的调整集。
  4. 理论保证：证明了LOAD在确定因果效应可识别性和找到最优调整集方面的可靠性和完整性。

方法详解

任务定义

给定一对目标变量X和Y，目标是：

  1. 确定X和Y之间的因果关系（显式祖先、可能祖先或确定非祖先）
  2. 判断因果效应是否可识别
  3. 如果可识别，找到最优调整集；否则返回局部有效的父调整集

LOAD算法架构

LOAD算法分为5个主要步骤：

步骤1：确定目标变量间的因果关系

使用LocalRelate算法（算法1），通过以下定理确定关系：

  • 显式祖先关系（定理4.1）：对于CPDAG G中的任意两个不同节点X和Y，X ∈ ExplAn_G(Y) 当且仅当 X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
  • 确定非祖先关系（定理4.2）：X是Y的确定非祖先当且仅当 X ⊥⊥ Y | Pa_G(X)

步骤2：测试因果效应的可识别性

提出了基于局部信息的适应性测试：

引理4.3：对于CPDAG G中X ∈ PossAn_G(Y)，G相对于(X,Y)是调整适应的当且仅当：

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

这个条件可以通过LocalAmenTest算法（算法2）高效检测。

步骤3-5：构建最优调整集

如果因果效应可识别，LOAD通过以下步骤构建最优调整集：

  1. 找到显式后代：识别所有T的显式后代
  2. 识别中介节点：找到既是T的显式后代又是O的显式祖先的节点
  3. 构建最优调整集： 
    Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

技术创新点

  1. 局部适应性测试：首次提出仅使用局部信息就能测试适应性的充分必要条件，避免了检查所有可能有向路径的需要。
  2. 缓存机制：改进的MB-by-MB算法使用缓存重用先前运行中识别的Markov毯和局部结构，显著提高计算效率。
  3. 理论完备性：证明了LOAD在确定因果关系、可识别性和最优调整集方面都是可靠且完整的。

实验设置

数据集

  1. 合成数据：
    • 使用随机生成的Erdős–Rényi图
    • 变量数量：100-1000
    • 期望度数：d=2，最大度数：dmax=10
    • 样本数：nD=10000
  2. 真实网络：
    • MAGIC-NIAB网络：44个节点，平均度数3
    • ANDES网络：223个节点，平均度数3.03

评价指标

  1. 计算效率：条件独立性测试次数
  2. 调整集质量：最优调整集的F1分数
  3. 因果效应估计质量：干预距离（intervention distance）

对比方法

  • 全局方法：PC、MARVEL、SNAP(∞)
  • 局部方法：MB-by-MB+、LDECC+、LDP+（扩展版本）

实现细节

  • 显著性水平：α = 0.01
  • 三种条件独立性测试：oracle d-separation、Fisher-Z测试、G²测试
  • 每个设置运行100次，去除最好和最差的5次结果

实验结果

主要结果

计算效率

LOAD在所有设置中的条件独立性测试次数始终低于全局方法，略高于局部方法：

  • 在1000个节点时，LOAD需要9.43×10³次测试，而PC需要542.52×10³次
  • 相比MB-by-MB+的5.64×10³次测试，LOAD的额外开销是合理的

调整集质量（F1分数）

  • Oracle设置：LOAD达到完美的F1=1.0，与全局方法相当
  • Fisher-Z测试：LOAD在所有节点数上都优于基线方法，F1分数约为0.91-0.95
  • G²测试：LOAD表现次优，但仍是第二好的方法

干预距离

LOAD在大多数设置中实现了最低的干预距离：

  • Oracle设置：0.003（与PC、SNAP相当）
  • Fisher-Z测试：0.014-0.026（最佳）
  • G²测试：0.022-0.036（第二好，仅次于PC）

真实数据结果

在MAGIC-NIAB网络上：

  • LOAD达到最佳F1分数（0.62）
  • 实现最低干预距离（0.007）
  • 条件独立性测试次数（4.35×10³）介于局部和全局方法之间

消融实验

  1. 已知治疗-结果关系：当提供背景知识时，LOAD*在二元数据上超越PC
  2. 可识别目标对：在确保因果效应可识别的设置中，结果模式保持一致
  3. 参数敏感性：LOAD对不同样本数量和期望度数表现稳健

相关工作

全局因果发现方法

  • PC算法：经典的基于约束的方法，但计算复杂度高
  • MARVEL：递归方法，仍难以扩展到数百个变量
  • SNAP：渐进识别和移除确定非祖先，但仍需要在所有可能祖先上进行因果发现

局部因果发现方法

  • MB-by-MB：序贯Markov毯发现，但限于次优调整集
  • LDECC：高效的collider检查，但存在可靠性和完整性问题
  • LDP：通过分区学习调整集，但仍可能次优且有假设限制

本文优势

LOAD是首个同时实现以下目标的方法：

  1. 仅使用局部信息
  2. 恢复最优调整集
  3. 提供理论保证（可靠性和完整性）

结论与讨论

主要结论

  1. LOAD成功结合了局部方法的计算效率和全局方法的统计最优性
  2. 提出的局部适应性测试为因果效应可识别性提供了高效的判断方法
  3. 在多种数据类型和网络结构上，LOAD都表现出优越的性能

局限性

  1. 因果充分性假设：当前版本假设没有潜在混淆因子或选择偏差
  2. 大规模网络的计算瓶颈：在极大图上，Markov毯搜索仍可能成为计算瓶颈
  3. 二元数据性能：在使用G²测试的二元数据上性能有限

未来方向

  1. 扩展到因果不充分设置：处理潜在混淆因子的情况
  2. 优化Markov毯发现：进一步提高大规模网络的计算效率
  3. 改进有限样本性能：特别是在二元数据上的表现

深度评价

优点

  1. 理论贡献显著：首次提出仅基于局部信息的适应性测试，具有重要理论价值
  2. 实用性强：在保持计算效率的同时实现统计最优性，解决了实际应用中的关键问题
  3. 实验全面：涵盖多种数据类型、网络规模和评价指标，结果说服力强
  4. 算法完备：提供可靠性和完整性的理论保证，算法设计严谨

不足

  1. 假设限制：因果充分性假设在实际应用中可能不满足
  2. 扩展性问题：虽然比全局方法好，但在超大规模网络上仍有计算挑战
  3. 有限样本表现：在某些有限样本设置下性能不够稳定

影响力

  1. 学术价值：为因果发现领域提供了新的理论框架和算法设计思路
  2. 实用价值：在需要因果效应估计的实际应用中具有重要价值
  3. 可复现性：提供了详细的算法描述和实验设置，便于复现和扩展

适用场景

  1. 中等规模因果推断：变量数量在数百到数千的因果效应估计任务
  2. 计算资源受限：需要平衡计算效率和统计性能的应用场景
  3. 因果充分环境：没有重要潜在混淆因子的观察性研究

参考文献

论文引用了因果推断领域的重要文献，包括：

  • Pearl (2009): Causality - 因果推断的经典教科书
  • Spirtes et al. (2000): 约束基因果发现的基础工作
  • Henckel et al. (2022): 最优调整集的图形化准则
  • Perković et al. (2015): 适应性的定义和性质

总体评价：这是一篇高质量的因果推断论文，在理论和实践层面都有重要贡献。LOAD算法巧妙地解决了因果发现中计算效率与统计最优性的权衡问题，具有重要的学术价值和应用前景。