Constraint-based difference graph discovery in a linear setting¶

作者: Daria Bystrova, Emilie Devijver
主题: 因果推断
相关性: 9/10
链接: https://arxiv.org/abs/2606.13947

一、领域脉络与小综述¶

这个方向是什么¶

本子方向致力于从多环境（通常为两个）观测数据中，直接推断因果图的结构性差异，即“差异图”（difference graph）。核心的统计/科学问题是：在多个系统（环境）共享大部分因果骨架的前提下，如何精确识别哪些因果机制发生了改变，而不必在每个环境中重新学习全图。当前成熟度处于方法论初步成型但理论基础薄弱的阶段——已有若干算法，但缺乏类似标准 d-separation 的图准则来系统刻画差异的识别条件。

发展脉络（history）¶

奠基工作：经典约束基因果发现与多环境思路的开端
- Spirtes et al. (2000) 的 PC 算法建立了约束基因果发现的范式，以 d-separation 和 Faithfulness 为支柱。
- Eberhardt & Scheines (2007) 为干预的类型（强/软）与因果推断的关系提供了形式化，成为后续多环境问题的基础。
主要进展：从“全图发现”转向“差异发现”
- Wang et al. (2018) 的 DCI 算法是早期标志性工作：它利用不变性检验（invariance tests）直接估计两个因果图之间的差异，不再要求先重建每张全图。其关键设定是“共享拓扑序”（shared topological ordering），由“软干预”的假设保证。
- Chen et al. (2024) 的 iSCAN 进一步扩展了非参数/半参数设定（加性噪声模型），首先推断发生移位的节点（shifted nodes），再通过基于条件独立的特征排序恢复差异 DAG。
- Malik et al. (2024) 在线性 SEM 框架下研究因果变化识别，作者引用时强调其与本文在“共享拓扑序”假设上一致，但未采用 PC 风格的策略。
- 本文作者指出这些方法的共同局限：缺乏一个类似 d-separation 的图准则，来解释统计量在环境间的相等/不等何时反映真实的因果变化。它们要么采用参数检验（DCI），要么使用半参数方法（iSCAN），但没有系统地刻画“哪些路径可以诱导差异”。
当前 frontier：图准则的缺失
- Assaad (2025) 近期论证了差异图可直接用于因果推理（不需无参数化假设），因此差分图发现的质量直接下游应用。
- 作者在 intro 中明确 frame 缺口：“there is currently no analogue of d-separation that explains when equality (or inequality) of statistical quantities across environments reflects underlying causal changes.” 当前方法缺乏一个图论层面的识别理论。

子线索聚类¶

线索 1：基于全图重建再比较的“间接”方法（例如 Guo et al. 2011 的联合图模型、Liu et al. 2013 / Zhao et al. 2014 的差异 Markov 网络直接估计）。这些方法在无向图/高斯图模型中较为成熟，但独立于当前以 DAG 差异为核心的问题。
线索 2：直接学习 DAG 差异的“直接”方法：DCI (Wang et al., 2018)、iSCAN (Chen et al., 2024)、Malik et al. (2024)。它们直接在两个环境间进行变化检测，但均未提供类似 d-separation 的图准则，且各有特定参数/结构假设（大多数共享“线性+高斯”或“加性噪声”+“共享拓扑序”）。
线索 3：差异图的理论扩展与因果推理应用：Assaad (2025) 将差异图用于因果估计，强调其无参数化潜力。这一线索暗示了“良好图准则”的必要性——如果用于后续推理，差异图发现本身必须避免继承不必要的参数假设。

这个方向在追问的核心问题¶

图准则问题：是否存在一个与经典 d-separation 平行的“diff-separation”准则，系统刻画在何种条件下，跨环境的特定统计量（如回归系数）相等/不等对应图结构的存在/缺失？
识别条件：仅通过环境间统计量的相等性测试，能否唯一地恢复差异图（骨架 + 方向），需要怎样的 faithfulness 型假设？
算法效率：PC 的“限制条件集为邻接点”策略是否适用于差异图发现？如果不能，如何设计高效的约束基搜索策略？
假设的脆弱性：共享拓扑序、无隐变量（因果充分性）、线性等假设，在多大程度上是必要的？可否在更弱的设定下进行差异图识别？

⚠️ 作者的 framing（必须明确标注成“这是作者的说法”）¶

作者把缺口 frame 成：现有方法（DCI、iSCAN）没有系统图准则，不能在约束基框架下解释回归系数相等/不等与差异图间的关系；本文填补这一空白，提出 diff-separation 作为“差异图中的 d-separation”。
被淡化/回避的竞争路线：
- 作者引用了 Shojaie (2021) 的综述，但仅泛泛提及，没有仔细对比差异 Markv 网络（Liu et al. 2013, Zhao et al. 2014）与本文 DAG 差异问题的优劣。
- iSCAN (Chen et al. 2024) 是一个明显更强的竞争对手——它可以处理非线性加性噪声模型，而本文限制在线性 SCM。作者将“线性”作为“避免定义非参数直接效应的困难”的合理性辩护（Section 4.1），但这一选择显然限制了方法的一般性。
什么明显该被引/该存在、却没出现在 intro 里：
- 见未见明显的本文引用的最新工作：2024-2026 年间是否出现了其他工作同时提出类似“diff-separation”的图准则？这是一个值得您去亲自检索的问题。
- 隐变量（latent confounding）的处理：论文结尾顺带提到“扩展 FCI 以处理隐变量”，但正文中没有任何文献讨论“在差异图中存在隐变量”时的识别问题——这似乎是一个明显的被回避的复杂点。
- 随机矩阵理论/高维统计的视角：作者使用回归系数等式的置换检验，但没有涉及多变量检验中可能的维度问题（当 p 较大难做穷举条件集）。这与本文的理论焦点不一致，但在您看来可能是一个衔接点。

张力¶

未见明显对立引用。所有被引工作在因果发现或差异图发现上大致互补，未发现同一设定下得出明显矛盾结论的情况。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：

记号	含义	类型
\(M^{*}\)	底层结构因果模型（SCM）	假设存在但未知的模型
\(\mathcal{V} = \{X_{1}, \ldots, X_{p}\}\)	观测变量集合（共 p 个）	随机变量
\(\mathcal{U}\)	外生噪声变量集	不可观测
\(G^{} = (V, E^{})\)	\(M^{*}\) 对应的底层 DAG	未知真实图
\(G_{1}, G_{2}\)	环境 1 与环境 2 各自对应的 DAG	未知，由干预导致
\(P_{1}, P_{2}\)	环境 1、2 的联合分布（可观测样本来自它们）	可观测
\(D = (V, E)\)	差异 DAG：边 \((X_i \rightarrow X_j)\) 当且仅当 \(X_i\) 到 \(X_j\) 的直接效应在两环境间不同	目标 estimand
\(Pa_{G}(X_i)\)	在 DAG \(G\) 中 \(X_i\) 的父节点集	图对象
\(r^{(P_\ell)}_{X_i X_j . Z}\)	在分布 \(P_\ell\) 下，将 \(X_j\) 对 \(X_i\) 和向量 \(Z\) 做线性回归时 \(X_i\) 的回归系数	可估统计量

模型：

底层 SCM \(M^{*}\) 是线性的：每个机制 \(f_i\) 是父节点的线性函数加独立噪声。
两个环境 \(e_1, e_2\) 通过干预从 \(M^{*}\) 衍生：干预可以是硬干预（切断一个节点所有父关系）或软干预（仅改变系数但仍保留部分父关系）。
共享拓扑序（Assumption 1）：任何干预不能引入新父节点，因此 \(G_{1}, G_{2}\) 共享同一个全体观测变量的拓扑顺序。
因果充分性：无未观测混杂（所有共同原因都被包括在 \(\mathcal{V}\) 中）。
线性 SCM 假设（Assumption 2）：所有机制是线性的。

可观测数据：

你有：来自环境 1 的 \(n_1\) 个样本 \(\mathbf{x}_1^{(1)}, \ldots, \mathbf{x}_{n_1}^{(1)}\)，和来自环境 2 的 \(n_2\) 个样本 \(\mathbf{x}_1^{(2)}, \ldots, \mathbf{x}_{n_2}^{(2)}\)，其中每个 \(\mathbf{x}_i^{(\ell)} \in \mathbb{R}^p\)。
你想要但观测不到的是：每个环境下的真实 DAG \(G_1, G_2\) 和差异 DAG \(D\)。
你只能通过对比两环境下的回归系数 \(r^{(P_1)}_{X_i X_j.Z}\) 与 \(r^{(P_2)}_{X_i X_j.Z}\) 是否相等来推断 \(D\)。

第二步：讲最小内核¶

最简特例：p=3，单干预，不共享改变的路径

考虑三个变量 \(X, Z, Y\)，底层真实图 \(G^{*}\) 为链 \(X \rightarrow Z \rightarrow Y\)（见论文图 2(a)）。假设： - 环境 2 无干预（\(G_2 = G^{*}\)）； - 环境 1 仅进行一次 硬干预 在 \(Y\) 上：即切断 \(Z \rightarrow Y\) 边（所以 \(G_1\) 中 \(Z\) 不再是 \(Y\) 的父节点，只有 \(X \rightarrow Z\) 与 \(G^{*}\) 相同）。

那么差异 DAG \(D\) 只包含一条边：\(Z \rightarrow Y\)（因为 \(Y\) 的机制在两环境间不同）。

现在了解回归系数 \(r_{XY.\emptyset}\) 在两环境中的行为： - 在环境 1（硬干预 \(Y\)）：由于 \(Z \not\to Y\) 在 \(G_1\) 中，\(Y\) 的变异性仅来自其干预分配的噪声，与 \(X\) 独立，所以 \(r^{(P_1)}_{XY.\emptyset} = 0\)。 - 在环境 2（无干预）：\(X \rightarrow Z \rightarrow Y\)，所以 \(X\) 和 \(Y\) 相关，\(r^{(P_2)}_{XY.\emptyset} \neq 0\)（具体取决于系数）。

因此 \(r^{(P_1)}_{XY.\emptyset} \neq r^{(P_2)}_{XY.\emptyset}\) ——尽管 \(X\) 与其父节点/子节点没有任何边在 \(D\) 中。这就是为什么标准 d-separation（在 \(D\) 中看 \(X\) 与 \(Y\) 无连接）不能直接用于差异图：仅凭差异 DAG 中两节点间无边，并不能保证它们对应的回归系数相等；跨环境路径的“间接改变”也可以产生差异。

论文的关键想法：必须将“路径本身是否包含差异边”与“路径上的节点是否因差异边的祖先而分布改变”一并考虑，才能区分何时回归系数相等等于图上的“diff-separated”。于是有了 diff-relevant path 和 conditionally diff-relevant path 的定义。

三、这篇论文做了什么¶

三句话¶

研究问题：在两个环境下，如何仅通过回归系数的跨环境相等性测试，推断线性 SCM 的差异 DAG（即哪些直接效应发生了变化）。
核心工具：提出一个全新的图准则——“diff-separation”（定义 4），并在相应的“diff-faithfulness”假设（假设 3）下，将 diff-separation 与回归系数的等式约束建立双向联系（Proposition 2 + diff-faithfulness 假设）。
主要结论：提出 LDiffPC 算法（Algoritm 1），证明它在 perfect equality information 和 diff-faithfulness 下正确地恢复差异 DAG 的骨架、V-structures 及所有由 Meek 规则推出的定向（Theorem 1）。

关键设定与假设¶

完整设定：
两个线性 SCM \(M_1, M_2\)，由同一个底层 \(M^{*}\) 经干预得到（Assumption 2）；
外生噪声分布跨环境不变（Proposition 2 需要）；
因果充分性（无隐变量）；
共享拓扑序（Assumption 1）。
Diff-faithfulness (Assumption 3)：

\[r^{(P_1)}_{X_i X_j.Z} = r^{(P_2)}_{X_i X_j.Z}\]

当且仅当集合 \(Z\) diff-separates \(X_i\) 与 \(X_j\)。

与经典 Faithfulness 的比较：
- 经典 Faithfulness 要求：d-separation ←→ 条件独立。
- 这里的 Diff-faithfulness 要求：diff-separation ←→ 回归系数相等。
- 作者指出，经典 Faithfulness 的违反（如路径系数恰好相互抵消）不必然违反 diff-faithfulness，因为如果抵消在两环境中不一致（如系数稍有变化），那么回归系数会在跨环境时发生变化，diff-faithfulness 仍然保持。

与已有文献的比较：
相比 DCI (Wang et al. 2018)：本文提供了明确的图准则，而 DCI 是直接基于不变性检验的算法。
相比 iSCAN (Chen et al. 2024)：iSCAN 适用于非线性加性噪声模型，而本文限于线性；但本文提供了坚实的图论识别基础。

主要结果¶

Proposition 1（识别条件）：两节点 \(X_i, X_j\) 在差异图 \(D\) 中不相邻 ⇔ 存在某个条件集 \(Z\) diff-separates 它们。这是用于骨架恢复的关键。

Proposition 2（方向联系）：若存在一个 \(Z\) diff-separates \(X_i\) 与 \(X_j\)，则 \(r^{(P_1)}_{X_i X_j.Z} = r^{(P_2)}_{X_i X_j.Z}\)。给了“diff-separation → 系数相等”的方向。

Diff-faithfulness + Lemma 1 & Lemma 2 提供了另一方向：系数相等 → diff-separated，使得真正的双向关系成立。由此： - Lemma 1：\(X_i\) 与 \(X_j\) 相邻在 \(D\) 中 ⇔ 对所有 \(Z\)，\(r^{(P_1)}_{X_i X_j.Z} \neq r^{(P_2)}_{X_i X_j.Z}\)。这个“对所有”是骨架恢复的关键。
- Lemma 2（V-structure 定向）：对于非屏蔽三元组 \(X_i - X_k - X_j\)（且 \(X_i, X_j\) 不相邻），定向为 \(X_i \rightarrow X_k \leftarrow X_j\) ⇔ 对所有包含 \(X_k\) 的 \(Z\)，有 \(r^{(P_1)}_{X_i X_j.Z} \neq r^{(P_2)}_{X_i X_j.Z}\)。

Theorem 1（LDiffPC 的完备性与正确性）：在 diff-faithfulness 及 perfect equality information 下，LDiffPC 输出图 \(\hat{D}\) 与真实差异 DAG \(D\) 有相同骨架，且 \(\hat{D}\) 中的所有定向也在 \(D\) 中。

证明路线与技术技巧¶

整体路线（以骨架恢复为例）：

骨架初步阶段：从全连接图开始，对所有相邻节点 \(X_i-X_j\)，在每次循环中遍历条件集 \(Z\) 大小固定为 \(card=0,1,\ldots,p-2\)。
关键步骤：发现第一个使 \(r^{(P_1)}_{X_i X_j.Z} = r^{(P_2)}_{X_i X_j.Z}\) 的 \(Z\) → 删去边 \(X_i - X_j\)，记录该 \(Z\) 到Sepset。
正确性依据：Lemma 1 保证：
若真实 \(D\) 中无 \(X_i - X_j\) 边 → 至少有一个 \(Z\) diff-separates → 系数相等 → 可删；
若真实 \(D\) 中有边 → 对所有 \(Z\) 系数不等 → 算法不会删。
定向阶段：对每个无屏蔽三元组，检查Sepset中是否包含中间节点 \(X_k\)：若不包含→定向为V-structure。Lemma 2 保证这是正确的。
Meek规则定向剩余边，Lemma 3 保证正确。

关键跳跃点

证明 Proposition 2（diff-separation → 系数相等）的核心在于 Lemma 4（附录 Lemma 4）：它证明了如果残余协方差或残余方差出现跨环境差异，则必然由某种 diff-relevant 或 conditionally diff-relevant 路径导致。这一归纳式论证利用了线性 SCM 下“路径系数乘积 + 外生噪声方差”的可分解性，加上“外生噪声不变”的假设，将任何跨环境贡献归结到系数变化上。
Lemma 4 的困难在于处理 conditionally diff-relevant 路径：通过条件化操作（projection onto \(Z\)），即使路径本身不含差异边，也可能因条件集与差异边连接点的交互而产生差异。这是论文引理中最吃功夫的部分。
技术技巧点名：
路径贡献分解 + 外生噪声不变：利用线性模型的结构分解，将回归系数的差异问题简化为路径贡献差异问题。
d-separation 的组合扩展：将经典 d-separation 的“阻塞”机制扩展到“diff-relevant 阻塞 + conditionally diff-relevant 阻塞”，本质上是对可变化路径的穷举分类。
条件化/残差化操作：通过 residual on \(Z\) 将回归系数转化为残余协方差与方差比，从而用路径分解处理。
PC 算法的适配问题：论文用了 Example 2（图 5）展示为什么 PC 的“条件集只限邻接点”策略在差异图发现中失败——必须检查更大范围的条件集（如 \(Y, M, Z\) 或 \(U\) 等远离的节点），从而为了完备性而牺牲效率。

真实例子与应用¶

本文为纯理论 + 模拟例子：
- 没有真实数据实验。
- 包含了三个构造性例子：
- 例 1（图 3）：展示了违反经典 faithfulness 但不违反 diff-faithfulness 的场景（路径系数精确抵消在一种环境中但不在另一种中），说明 LDiffPC 在这种情况下能正确恢复差异图，而 PC 不能。
- 例 2（图 5）：展示了为什么 PC 的邻接限制条件集策略在差异图设定下失败，以此 justify LDiffPC 使用穷举条件集（至少在搜索的环路中不限于邻接节点）。
- 图 4 的例子展示了厄米型 diff-faithfulness 的另一种违反形式：“系数互换”——两环境中来自两个节点的系数互换，导致回归系数不变但差异图有变化。
- 说明目的：这些例子主要验证理论的边界，展示假设的必要性和算法的限制，而非展示相对于其他方法（如 DCI, iSCAN）的实证优势。

🔎 结论是否比证明窄¶

有！最明显的是：Theorem 1 的证明假设了 对外生噪声分布不变（Proposition 2 需要）和 线性SCM。但在文中的宣言式陈述（如“Proved that LDiffPC is both sound and complete”）没有指明：这种 soundness 依赖于 diff-faithfulness，而 diff-faithfulness 自身在线性 + 噪声不变 + 共享拓扑序 + 无隐变量下才被证明。
扩散型表述：在“Conclusion”中作者说 LDiffPC 可用来为“difference DAGs in linear SCMs”提供稳健推断，但没有限制噪声不变。实际上，如果噪声方差在环境中不同，Proposition 2 中的“等价”可能不成立——路径贡献相同但因为噪声方差不同，残余方差差异仍可能导致回归系数变化。
“Complete”的实度：论文证明“所有定向正确”，但未证明算法能找到所有可能的定向——仅给出了一个部分定向图（partially directed difference graph），条目中只保证定向存在于真图，不保证得到最大可能定向。这是一个 imply 的但未显式讨论的限制。

四、开放问题¶

（扎根具体语句，每条点明来源）

放松拓扑序假设
来源：Conclusion 第一句 “By relaxing topological ordering constraints, we may gain deeper insights into causal relationships, although this remains a challenging problem.”
问题：当前 LDiffPC 依赖 Assumption 1（共享拓扑序），即边方向一致。能否在允许边反向或部分反向的环境（如在基因调控网络中不同环境可能产生不同调节方向）下设计 diff-separation 准则？这需要新的图论刻画。
引入隐变量：差异 FCI
来源：Conclusion 第二句 “Another promising extension is the incorporation of latent variables, following the spirit of FCI, but adapted to the inference of difference graphs.”
问题：当因果充分性被违反（有隐变量共同原因）时，diff-separation 需要如何修改？需要定义“条件在什么集合上能阻断由隐变量导致的变化”这可能需要类似 latent projection（latent causal graph）和相关的分离准则。
非线性扩展
来源：Section 4.1 作者在定义直接效应遇到障碍时选择限制到线性 SCM。
问题：能否在非参数或加性噪声模型下定义“在条件集中回归系数相等”的类似物？已有工作（Chen et al. 2024）部分处理了非线性，但在图准则层面尚无 diff-separation 的对应版本。
条件集搜索的效率问题
来源：Example 2（图 5）展示了 PC 策略（限制邻接点）不足，LDiffPC 需要测试更广的集合。
问题：是否存在一个多项式时间的搜索策略，在 diff-faithfulness 下保证正确性？或者能否在某种稀疏性假设下（如差异图的节点度有界）设计更高效的版本？这是算法理论与计算统计学的交汇点。

确认提示：要检查最后一条是否是真正的 gap，建议快速阅读 iSCAN (Chen et al. 2024) 和 Malik et al. (2024) 的算法部分——它们如何处理高效搜索？共识缺失即可能面临真正的挑战。

Maintained by 陈星宇 · Homepage · Source on GitHub