Integrating Background Knowledge for Scalable Causal Discovery¶

会议: NeurIPS 2026
arXiv: 2607.10456
OpenReview: https://openreview.net/forum?id=GBk2ivbt6U
领域: 因果推理
关键词: 因果发现, 背景知识, 可扩展因果发现, 局部因果发现, 条件独立性检验

一句话总结¶

针对传统因果发现算法在融合背景知识时仅停留在后处理阶段、无法降低计算复杂度的瓶颈，本文提出在因果搜索过程中深度融合直接因果背景知识的统一框架，通过剪枝分隔集、跳过已知邻接检验和延迟间隙检验，使全局与局部因果算法的独立性检验次数呈数量级下降，并严格证明了算法的可靠性与完备性。

研究背景与动机¶

因果图是刻画可观测数据底层因果生成机制的基石工具，因果发现旨在从观测数据中恢复（部分）因果图结构以支撑因果效应估计与策略制定。然而，经典的全局因果发现算法（如 PC 算法）在变量维度升高时计算开销呈组合爆炸，严重限制了其在高维现实场景中的落地。为了打破这一计算瓶颈，近年来学界提出了以目标导向局部结构为核心的可扩展因果发现方法（如局部因果发现 MB-by-MB、LDECC，以及非祖先剪枝算法 SNAP 和目标因果效应算法 LOAD），将计算集中于与下游效应估计直接相关的局部子图上。

然而，这些前沿的高效算法几乎未考虑领域专家背景知识（Background Knowledge, BK）的深度结合。在生物学、流行病学与经济学等实际应用中，专家往往能提供变量间是否存在直接因果关联、特定因果方向或无直接因果关联（间隙，gap）的先验约束。令人遗憾的是，现有因果发现范式大多将背景知识局限在后处理阶段——即先盲目跑完全部高昂的因果图发现流程，再利用 Meek 规则将先验方向传播到马尔可夫等价类（CPDAG）上；亦或像 pcalg、causal-learn 等主流开源库那样，简单粗暴地在初始化阶段直接剔除已知间隙的边，因缺失必要的分隔集记录而导致 v-结构错误定向。

这两类做法的根本矛盾在于：后处理机制完全浪费了背景知识大幅缩减图搜索空间的潜力，而朴素的预过滤机制则破坏了条件独立性推断的图论严谨性。本文切入的角度是：背景知识中的直接因果关系（邻接、定向与间隙）本质上直接约束了因果 DAG 中的父节点候选集与非邻接可分离性，完全可以在因果搜索的每一个阶段即时生效。核心 idea：在因果发现全流程中深度嵌入背景知识——跳过已知邻接的冗余检验、依据可能父节点动态剪枝候选分隔集，并对已知间隙采用延迟搜索策略补全分隔集，从而在保障理论可靠性与完备性的前提下实现算法计算量与效应估计精度的双重飞跃。

方法详解¶

整体框架¶

本文构建了一套将直接因果背景知识 $\mathcal{B}$ 原生嵌入约束类因果发现算法的通用方法学体系。框架处理三类直接因果先验约束：已知邻接 $X - Y \in \mathcal{B}$、已知有向边 $X \to Y \in \mathcal{B}$ 以及已知间隙（非邻接）$X \not- Y \in \mathcal{B}$。整个机制由三大核心准则驱动：一是针对已知邻接或定向边跳过所有无谓的条件独立性（CI）检验；二是利用背景知识剔除不可能作为父节点的变量，大幅压缩候选条件分隔集的大小；三是针对已知间隙，在第一轮骨架搜索中跳过检验以加速剪枝，随后在更稀疏的骨架上执行延迟分隔集搜索，既保留了 v-结构定向所需的分隔集，又规避了有限样本误差的雪崩传播。

基于这三大通用准则，作者将技术方案自底向上扩展至两大全局因果发现算法（PC-BK、SNAP-BK）与三大前沿局部因果发现算法（MB-by-MB-BK、LDECC-BK、LOAD-BK），并扩展了马尔可夫毯发现子模块（Grow-Shrink-BK 与 Total Conditioning-BK）。算法整体流程如下所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    Input["输入：观测数据 + 直接因果背景知识 ℬ<br/>(邻接 / 定向 / 间隙)"] --> P1["已知邻接跳过检验：<br/>跳过 ℬ 中已有连接变量对的 CI 检验"]
    P1 --> P2["候选分隔集剪枝：<br/>仅在可能父节点集合 PossPa(X, ℬ) 中搜索条件集"]
    P2 --> P3["间隙延迟处理：<br/>第一阶段跳过已知间隙，第二阶段在稀疏骨架补全分隔集"]
    P3 --> Ext["扩展至目标发现与局部算法：<br/>融入 SNAP / MB-by-MB / LDECC / LOAD"]
    Ext --> Output["输出：极大定向部分有向无环图 (MPDAG)<br/>或目标因果效应最优调整集"]

关键设计¶

1. 已知邻接跳过检验与候选分隔集剪枝：直接规避冗余测试并收缩条件组合 在约束类因果算法中，判断节点间是否存在边依赖于高阶条件独立性测试。痛点在于当专家已知两变量必然直接相连时，传统算法仍会从 0 阶到高阶穷举条件集试图分离它们，带来沉重的无效计算。针对此问题，框架在首轮骨架遍历中判定若两节点间存在任意直接连接先验（即 $(X, Y) \in \mathcal{B}$ 或 $X *-* Y \in \mathcal{B}$），则直接跳过该节点对的全部条件检验。

更关键的是，Spirtes 等人的理论指出，若两节点在真实 DAG 中不相邻，则它们必然可被其中某一节点的真实父节点集 d-分离。因此，在寻找分离 $X$ 与 $Y$ 的候选集合 $\mathbf{S}$ 时，完全无需在当前骨架的所有邻居中穷举，而仅需在排除掉不可能成为父节点的子集 $\text{PossPa}_{\hat{G}}(X, \mathcal{B})$ 中搜索： $$\text{PossPa}_{\hat{G}}(X, \mathcal{B}) = \text{Adj}_{\hat{G}}(X) \setminus \{V \in \mathbf{V} \mid X \to V \in \mathcal{B} \vee X \not- V \in \mathcal{B}\}$$ 此机制将条件集的组合搜索空间自指数级急剧收缩，从根本上降低了每次判定邻接关系的计算阶数。

2. 间隙延迟处理：解决因缺失分隔集导致的 v-结构定向失效 现有主流库（如 pcalg、causal-learn、pgmpy）在处理已知间隙 $X \not- Y \in \mathcal{B}$ 时，往往在一开始就直接将边从骨架中删除且不执行任何 CI 检验。然而这会导致致命缺陷：为了将未遮蔽三元组 $X - Z - Y$ 正确定向为 v-结构 $X \to Z \leftarrow Y$，算法不仅要求 $X$ 与 $Y$ 不相邻，还必须校验中间节点 $Z$ 不在 $X$ 与 $Y$ 的分隔集 $\text{sepset}(X, Y)$ 中。如果直接删边而未记录分隔集，后续算法要么无法判定 v-结构，要么产生虚假的碰撞定向（例如在真实结构 $X \to Y \to Z$ 伴随已知先验 $X \not- Z$ 时，错误定向为 $X \to Y \leftarrow Z$）。

本文设计了两阶段骨架发现机制（SkelStep-BK 与 MissingSepsets-BK）。第一阶段（SkelStep-BK）跳过所有带有背景知识的变量对（包括已知间隙），以极快速度基于数据消除大量真实非相邻边；第二阶段（MissingSepsets-BK）仅针对已知间隙遍历阶数 $i$，在经过第一阶段大幅稀疏化的骨架上专门搜索并记录它们的分隔集 $\text{sepset}(X, Y)$。这种“延迟搜索”机制不仅极大减小了寻找分隔集时的候选搜索集基数，而且具备鲁棒的自愈能力：若在有限噪声样本下无法找到合法的分隔集，算法会保守保留骨架中的边，避免因背景知识与数据噪声冲突而导致错误向全图级联蔓延。

3. 局部与目标导向算法的定制化嵌入：兼顾计算边界与定向完备性 将上述原则推广至更具可扩展性的局部与目标导向算法时，需解决不同算法特有的局部拓扑限制。对于顺序非祖先剪枝算法 SNAP，作者设计了 SNAP($k$)-BK 与 SNAP($\infty$)-BK，证明了在每一轮阶数剪枝后保留的节点集严格构成包含目标节点的 b-可能祖先闭包集；针对剪枝可能误删祖先的边界情况，框架将 RFCI v-结构定向规则从原版的第 2 阶提前到第 1 阶执行。对于局部发现算法 MB-by-MB，由于学习局部马尔可夫毯时外部邻接信息不全，作者调整了可能父节点定义：仅对中心变量 $X$ 启用背景知识剪枝约束，而对马尔可夫毯内的其他节点保留全邻接候选集合： $$\text{PossPa}_{\hat{G}}^{*}(V, \mathcal{B}) = \begin{cases} \text{PossPa}_{\hat{G}}(V, \mathcal{B}) & \text{若 } V = X \\ \text{Adj}_{\hat{G}}(V) & \text{其他情况} \end{cases}$$ 对于目标因果效应算法 LOAD-BK，若专家先验已直接给出目标对的处理-结果因果方向（$X \to Y$ 或 $Y \to X$），算法直接跳过开销巨大的第一步关系判定，并在修改后的禁忌投影中有效剔除无效变量，实现端到端的最优调整集发现。

一个完整示例¶

考虑三节点真实因果链 $X \to Y \to Z$，专家提供已知间隙先验 $\mathcal{B} = \{X \not- Z\}$。 1. 传统库朴素做法的缺陷：pcalg 或 causal-learn 在初始化时直接根据先验剔除边 $X - Z$，骨架剩余 $X - Y$ 与 $Y - Z$。随后执行 v-结构检测时，由于 $X$ 与 $Z$ 之间没有任何 CI 检验被触发，分隔集 $\text{sepset}(X, Z) = \emptyset$。算法检测到未遮蔽三元组 $X - Y - Z$ 且 $Y \notin \text{sepset}(X, Z)$，错误地将其定向为碰撞节点 $X \to Y \leftarrow Z$，导致因果推断完全颠倒。 2. 本文 PC-BK 执行流程： - 第一阶段（SkelStep-BK）：初始化全连通骨架。处理无先验边 $X - Y$ 与 $Y - Z$，CI 检验均拒绝独立，保留边；跳过先验对 $(X, Z)$。 - 第二阶段（MissingSepsets-BK）：针对先验 $X \not- Z$，在当前骨架中搜索条件集。在 1 阶检验中发现 $X \perp\kern-6.0pt\perp Z \mid \{Y\}$，成功记录 $\text{sepset}(X, Z) = \{Y\}$，并正式从骨架中确认剔除边 $X - Z$。 - 碰撞定向与 Meek 规则：检测三元组 $X - Y - Z$，由于 $Y \in \text{sepset}(X, Z)$，正确拒绝判定为 v-结构；后续经 Meek 规则传播出与真实等价类完全一致的有效结构，消除了错误累积。

实验关键数据¶

主实验¶

在 100 节点、平均度数为 3、最大度数为 10 的 Erdős–Rényi 合成因果模型上（样本量 10000，检验显著性水平 $\alpha=0.01$），作者评估了不同背景知识比例（BK Rate）下各算法的独立性检验次数（CI Tests）、运行时间及下游因果干预距离（Intervention Distance）。下表展示了在 Oracle d-separation 检验以及有限样本 Linear Gaussian（Fisher-Z 检验）下，背景知识从 0%（无先验）提升至 40% 时的核心指标表现（以典型代表算法为例）：

算法	数据/测试类型	评估指标	无先验 (BK=0.0)	融入先验 (BK=0.4)	改善幅度
PC-BK	Oracle d-sep	CI 检验次数	~2,800	~700	-75.0%
PC-BK	Linear Gaussian	运行时间 (s)	~18.5	~2.3	-87.6%
PC-BK	Linear Gaussian	干预距离 (Inv. Dist)	~0.35	~0.12	-65.7%
SNAP($\infty$)-BK	Oracle d-sep	CI 检验次数	~1,200	~420	-65.0%
SNAP($\infty$)-BK	Linear Gaussian	干预距离 (Inv. Dist)	~0.28	~0.09	-67.9%
MB-by-MB+-BK	Linear Gaussian	CI 检验次数	~850	~310	-63.5%
LDECC+-BK	Linear Gaussian	运行时间 (s)	~25.0	~2.1	-91.6%

消融实验¶

在合成网络与不同先验类型消融分析中（固定总先验率或单独分析先验类型对各算法的具体增益），实验对比了不同背景知识形式的作用差异：

算法 / 评估配置	关键指标变化趋势	说明
全模型 (综合所有 BK)	计算开销最低，干预距离最小	邻接、定向与间隙产生高度协同加速效果
仅提供已知间隙 (Gaps Only)	全局算法 (PC/SNAP) CI 检验数下降极显著	间隙先验能快速稀疏化大图骨架，对全局搜索最有效
仅提供定向先验 (Orientations Only)	局部算法 (MB/LDECC) 效应估计误差降幅最大	方向先验直接界定了处理-结果关系与调整集，效应估计立竿见影
仅提供邻接先验 (Adjacencies Only)	各算法 CI 检验数稳步下降，效应改善中等	直接跳过邻接判断，但无法辅助 v-结构与方向消除
引入 10%-30% 噪声先验 (Imperfect BK)	局部算法指标平缓恶化，SNAP 耗时明显增加	局部算法对噪声展现出较强容错韧性，SNAP 因祖先闭包破坏更敏感

关键发现¶

计算加速达数量级：随着背景知识占比提升，所有算法的 CI 检验次数与执行耗时均呈现单调显著下降，在 PC-BK 和 LDECC+-BK 上运行时间缩减均达到了 1 个数量级以上（下降超过 85%-90%）。
解决实际网络计算不可行问题：在真实生物网络 ARTH150（107 变量、150 边）的高维稠密结构中，原始 PC 和 LDECC 因组合爆炸耗时过长完全无法跑出结果；而在注入哪怕少量的背景知识后，算法得以在可接受时间内顺利收敛。
定向先验与间隙先验分工明确：消融分析证明，已知间隙先验是全局算法（PC 与 SNAP）削减骨架搜索计算量的最主要推动力；而定向先验则是所有算法压低因果效应干预距离、消除混杂偏倚的决定性因素。

亮点与洞察¶

提出延迟间隙检验机制：敏锐指出现存 causal-learn 与 pcalg 等主流库在处理已知非邻接时因缺失分隔集而导致 v-结构错判的代码漏洞，通过设计两阶段延迟搜索兼顾了效率与因果方向的数学正确性。
打通全局与局部因果算法的统一知识嵌入：不仅将先验嵌入传统 PC 框架，更成功推导并证明了其在 SNAP、MB-by-MB、LDECC 及 LOAD 等前沿局部/效应导向算法中的完备性与相容性边界。
理论保障扎实完整：严格证明了在真实图无隐变量与忠实性假设下，除 LDECC-BK 因局部视野无法传播外部 Meek 规则而仅满足可靠性外，其余拓展算法均达到了对真实 MPDAG 或局部因果结构的健全完备保证。

局限与展望¶

因果充分性强假设：正文核心理论与算法主要建立在无隐变量混杂和无选择偏倚的因果充分性（Causal Sufficiency）假设之上，尽管附录初步探讨了 FCI-BK，但在存在潜变量的高阶因果图中的普适嵌入仍有待完善。
对含噪背景知识的理论界限有待深入：虽然消融实验通过人工注入错误验证了算法具有经验容错性，但尚未建立针对概率性或带噪背景知识（Noisy/Soft BK）的严格理论保证与置信度校准机制。
未来方向：未来工作计划将该嵌入范式进一步泛化至时序因果图、多上下文数据集以及与大语言模型提取的先验概率进行鲁棒对齐。

评分¶

新颖性: ⭐⭐⭐⭐ [针对背景知识长期停留在后处理的痛点，提出了搜索中深度嵌入的三大原则并解决了间隙分隔集缺陷]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖合成模型、高维生物现实网络，涵盖连续/离散数据、噪声先验、消融及下游因果干预距离评估]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严谨自洽，算法伪代码与对照示例清晰，问题切入点与工程动机极强]
价值: ⭐⭐⭐⭐⭐ [直接修复并升级了工业界与学术界主流因果发现工具链，为高维实际因果推断落地提供了关键抓手]