Root cause discovery via permutations and Cholesky decomposition¶

讲者: Jinzhou Li (National University of Singapore)
会场: Frontiers in Causal Inference and High-Dimensional Data Analysis
报告题目: Root Cause Discovery
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是根因发现（Root Cause Discovery），具体设定为：给定一组来自同一数据生成过程的独立同分布观测样本（如健康个体的基因表达数据），以及一个来自该过程的“干预样本”（如一位患者的基因表达数据），目标是找出该干预样本中唯一被干预的变量（即根因变量，如致病基因）。这是一个极端的“稀疏机制偏移”问题（Schölkopf et al., 2021），其核心挑战在于：干预效应会沿着因果图向下游传播，导致大量变量表现异常，从而掩盖真正的根因。该问题的统计困难在于：只有一个干预样本可用，因此只能估计干预分布的一阶矩（均值），而无法估计其方差或更高阶矩；同时，因果顺序和因果图本身可能是不可识别的。

发展脉络（history）¶

奠基工作：因果推断与结构方程模型。Pearl (2009b) 的因果图理论和 Haavelmo (1944) 的结构方程模型为根因分析提供了基础框架。Peters et al. (2016) 提出的“不变预测”（Invariant Prediction）方法，其核心思想是：在因果模型中，给定父节点后，子节点的条件分布在干预下保持不变。这一思想是根因发现的重要理论基础。
主要进展：基于因果结构的根因分析。当因果图已知时，有两种自然方法：(1) 先找出所有异常变量，再选择因果顺序中最早的那个；(2) 利用不变性：只有根因变量在给定其父节点后的条件分布会发生变化（Janzing et al., 2019; Li et al., 2022）。然而，因果图通常未知，且其估计本身就是一个极具挑战性的问题（Evans, 2020），甚至可能不可识别（Spirtes et al., 2001; Pearl, 2009b）。
当前 Frontier：结合观测与干预数据的因果发现。当因果图未知时，一系列工作尝试同时利用观测数据和干预数据来估计干预目标（即根因）或学习因果结构。这些方法通常依赖于干预分布的二阶矩（Rothenhäusler et al., 2015; Varici et al., 2021, 2022）、似然函数（Eaton and Murphy, 2007; Taeb and Bühlmann, 2021）或整个干预分布（Squires et al., 2020; Jaber et al., 2020; Ikram et al., 2022; Yang et al., 2024）。本文的位置：作者明确指出，上述方法均无法应用于本文的设定，因为只有一个干预样本可用，无法估计干预分布的方差或更高阶矩。本文在“仅有一个干预样本”这一极端约束下，首次证明了根因的可识别性，并提出了一个无需估计因果顺序或因果图的方法。

子线索聚类¶

线索一：基于因果顺序/图估计的方法。这类方法先估计因果顺序或因果图，再结合异常检测进行根因分析。代表工作包括：Shimizu et al. (2011) 的 DirectLiNGAM（用于估计线性非高斯因果顺序），Raskutti and Uhler (2018) 的 Sparsest Permutation（SP）算法（通过最稀疏的Cholesky分解学习DAG），以及 Ye et al. (2020) 的 ARCS 算法（基于正则化Cholesky分数的排序学习）。本文在模拟中与基于LiNGAM的方法进行了对比。
线索二：基于干预分布信息的方法。这类方法利用干预分布与观测分布之间的差异来推断干预目标。代表工作包括：Rothenhäusler et al. (2015) 的 BACKSHIFT（利用协方差矩阵的差异），Varici et al. (2021, 2022) 的干预目标估计（利用精度矩阵的差异），以及 Taeb and Bühlmann (2021) 的扰动与因果模型评分。这些方法均需要多个干预样本或干预分布的完整信息。
线索三：基于异常传播与贡献分析的方法。这类方法将根因分析视为一个“因果贡献”问题。代表工作包括：Budhathoki et al. (2021, 2022) 的因果结构基异常分析，以及 Okati et al. (2024) 的 SCORE ORDERING 方法（基于“小异常不太可能引起大异常”的启发式）。本文指出，SCORE ORDERING 的启发式在一般情况下不成立。

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

可识别性：在仅有一个干预样本且因果顺序未知的条件下，根因是否可识别？
有效方法：如何设计一个无需估计完整因果结构、且计算上可行的根因发现算法？
高维挑战：当变量数远大于样本量时，如何应对协方差矩阵估计的困难？

⚠️ 作者的 framing¶

作者将缺口 frame 为：现有方法要么需要知道因果结构，要么需要多个干预样本，而本文在“仅有一个干预样本”这一更弱、更现实的条件下，证明了根因的可识别性，并提出了一个基于排列和Cholesky分解的新方法。作者淡化了以下竞争路线： - 基于因果顺序估计的方法：作者承认其挑战性（Evans, 2020）和不可识别性（Spirtes et al., 2001），但并未深入讨论在非高斯或特定假设下（如LiNGAM）这些方法可能取得的成功。模拟中，作者将LiNGAM作为baseline，但指出其计算代价高昂（在真实数据上7天未完成）。 - 基于异常传播规律的方法：作者仅用了一个反例（Appendix A.1）来否定SCORE ORDERING的启发式，但未系统性地探讨其他可能的异常传播模式。

什么明显该被引/该存在、却没出现在intro里？ - 关于“单样本干预”的因果推断文献。例如，在“个体处理效应”（ITE）估计中，也有类似“只有一个反事实”的设定。相关讨论可能出现在Gelman and Imbens (2013) 或 Dawid et al. (2014) 中，但本文仅将其作为“反向因果问题”的引子，未深入探讨其与ITE估计的联系。 - 关于“Cholesky分解在因果发现中应用”的更近期工作。作者引用了Raskutti and Uhler (2018) 和 Ye et al. (2020)，但Cholesky分解在因果结构学习中的应用是一个活跃领域，可能还有其他相关进展。

张力¶

未见明显对立引用。所有被引工作基本认同“根因发现是一个困难问题”，且“需要比本文更丰富的数据或更强的假设”。本文的贡献在于证明了在更弱条件下该问题的可解性。

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

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

符号：
- p：变量个数。
- n：观测样本量。
- X = (X_1, ..., X_p)^T：观测数据中的随机向量。
- X^I = (X^I_1, ..., X^I_p)^T：单个干预样本的随机向量。
- B：p x p 矩阵，编码因果结构。B_{ji} ≠ 0 表示存在从 i 到 j 的边。
- ε：p 维误差向量，均值为0，协方差矩阵为对角阵 D_ε。
- δ：p 维干预向量，只有一个非零分量 δ_r，表示对变量 r 的均值偏移干预。
- r：根因变量的索引（未知，待估计）。
- α_{r→k}：X_r 对 X_k 的总因果效应，即 (I-B)^{-1}_{kr}。
- µ_X, Σ_X：观测分布的均值向量和协方差矩阵。
- µ_{X^I}：干预分布的均值向量。
- L_X：Σ_X 的Cholesky分解得到的下三角矩阵，满足 Σ_X = L_X L_X^T。
- π：一个排列，π = (π(1), ..., π(p))。
- X_π：按排列 π 重排后的随机向量。
- ξ(π)：对于排列 π，定义的向量 ξ(π) = L_{X_π}^{-1} (µ_{X^I_π} - µ_{X_π})。
模型：
- 观测数据生成：X ← b + B X + ε，这是一个线性结构方程模型（SEM），其中 B 对应的图是一个有向无环图（DAG）。
- 干预样本生成：X^I ← b + B X^I + ε + δ，其中 δ 是一个均值偏移干预，仅作用于根因变量 r。
- 关键假设：误差 ε 的协方差矩阵是对角阵（即无未观测的混杂因子），且 B 对应的图是无环的。
可观测数据：
- 可观测：n 个 i.i.d. 的观测样本 x_1, ..., x_n，以及一个干预样本 x^I。从这些数据中，我们可以估计观测分布的均值 µ_X 和协方差矩阵 Σ_X，以及干预样本的均值 µ_{X^I}（由于只有一个样本，µ_{X^I} 的估计就是 x^I 本身）。
- 想要但观测不到：根因变量 r、干预强度 δ_r、因果结构矩阵 B、因果顺序、误差项 ε 的实现。

第二步：讲最小内核¶

最简特例：考虑一个只有两个变量 X_1 和 X_2 的线性SEM，其因果图为 X_1 → X_2，即 B_{21} ≠ 0，B_{12} = 0。假设误差方差均为1，且 X_1 是根因（r=1）。那么： - 观测模型：X_1 = ε_1, X_2 = B_{21} X_1 + ε_2。 - 干预模型：X^I_1 = ε_1 + δ_1, X^I_2 = B_{21} X^I_1 + ε_2。 - 可观测数据：我们得到 n 个 (x_1, x_2) 对，和一个 (x^I_1, x^I_2)。

核心思路： 1. 如果变量按因果顺序排列：即 π = (1, 2)。此时，X_π = (X_1, X_2)^T。其协方差矩阵 Σ_{X_π} 的Cholesky分解为 L_{X_π}。计算 ξ(π) = L_{X_π}^{-1} (µ_{X^I_π} - µ_{X_π})。由于 X_1 是根因，µ_{X^I_1} - µ_{X_1} = δ_1，而 µ_{X^I_2} - µ_{X_2} = B_{21} δ_1。经过Cholesky分解的“去相关”后，ξ(π) 会变成一个1-稀疏向量：ξ(π) = (δ_1, 0)^T。非零元的位置（第一个）对应根因 X_1。 2. 如果变量不是按因果顺序排列：即 π = (2, 1)。此时，X_π = (X_2, X_1)^T。计算 ξ(π) 会得到一个非稀疏的向量，因为 X_2 和 X_1 之间的相关性没有被Cholesky分解正确“消除”。

关键发现：虽然我们不知道哪个排列是因果顺序，但我们可以尝试所有 p! 个排列。对于每个排列 π，计算 ξ(π)。如果某个 ξ(π) 恰好是1-稀疏的，那么该非零元对应的变量就是根因。这就是 Theorem 3.1 的核心思想：根因的可识别性来源于这个跨排列的不变性——无论排列如何，只要 ξ(π) 是1-稀疏的，其非零元必然指向同一个变量（根因）。

在这个两变量例子中，我们尝试 π=(1,2) 和 π=(2,1)。只有 π=(1,2) 会得到1-稀疏的 ξ，从而识别出 X_1 是根因。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在仅有一个干预样本且因果顺序未知的线性结构方程模型下，如何识别该干预样本中的唯一根因变量。
核心工具/方法：利用排列（permutations）和Cholesky分解，通过寻找一个“1-稀疏”的向量 ξ(π) 来识别根因，并基于此开发了计算上可行的算法（Algorithm 2）及其高维版本（Algorithm 3）。
主要结论：证明了根因是可识别的（Theorem 3.1），并给出了一个基于排列的根因发现算法，该算法在观测样本量和干预强度趋于无穷时是一致的（Theorem 3.5）。模拟和真实基因表达数据应用验证了方法的有效性。

关键设定与假设¶

线性SEM：数据生成过程由 (1) 和 (2) 式定义。这是一个关键假设，限制了方法的适用范围。
唯一根因：干预向量 δ 只有一个非零分量。这是“稀疏机制偏移假设”的极端情况。
对角误差协方差：Cov(ε) 是对角阵。这意味着不存在未观测的混杂因子。这是因果识别中的标准假设。
无环图：B 对应的图是DAG。这是保证模型可解和因果效应定义良好的基础。
可观测性：观测样本是i.i.d.的，且可以估计 µ_X 和 Σ_X。干预样本只有一个，只能估计其均值 µ_{X^I}。

相比已有文献，本文的设定更弱：它不需要知道因果顺序或因果图，也不需要多个干预样本。但更强于某些工作：它假设了线性模型和唯一的根因。

主要结果¶

Theorem 2.1 (Z-score的失效条件)：严格刻画了平方Z-score何时能/不能一致地识别根因。当 σ_k^2 > α_{r→k}^2 σ_r^2 对所有 k 成立时，Z-score有效；否则无效。这为Z-score的失败提供了理论解释。
Theorem 3.1 (根因的可识别性)：这是本文的核心理论贡献。它证明，即使因果顺序不可识别，根因也是可识别的。证明的关键在于：对于任何排列 π，ξ(π) 至少有一个非零元；如果它恰好只有一个非零元，那么这个非零元必然对应根因。这个定理的证明依赖于一个巧妙的线性代数引理（Lemma D.1）。
Theorem 3.3 (充分排列的刻画)：给出了一个排列 π 是“充分”的（即 ξ(π) 是1-稀疏的）的充要条件：根因的所有父节点必须排在它前面，所有真实后代必须排在它后面。这个定理为设计高效的算法（Algorithm 1）提供了理论基础。
Theorem 3.5 (算法一致性)：证明了基于Algorithm 1生成的排列集，Algorithm 2给出的RC-score能一致地识别根因（即根因的得分以概率1趋于最大）。

证明路线与技术技巧（理论型）¶

整体路线：
1. 建立联系：将根因识别问题转化为寻找一个“1-稀疏”的 ξ(π) 向量。ξ(π) 的定义是 L_{X_π}^{-1} (µ_{X^I_π} - µ_{X_π})。
2. 证明可识别性 (Theorem 3.1)：证明的关键是Lemma D.1。该引理指出：对于一个满足特定三角化条件的矩阵 A，如果 L^{-1}A 的某一列只有一个非零元，那么这个非零元必然在对角线上。作者将 A 设为 (I-B_π)^{-1} D_ε^{1/2}，并利用 ξ(π) 与 L^{-1}A 的某一列具有相同支撑的事实，证明了 ξ(π) 的1-稀疏性必然指向根因。
3. 刻画充分排列 (Theorem 3.3)：利用Lemma D.3，将 ξ(π) 的1-稀疏性与 (I-B_π)^{-1} 和 B_π 的稀疏模式联系起来，从而得到关于父节点和后代位置的充要条件。
4. 设计高效算法 (Algorithm 1 & 2)：基于Theorem 3.3，设计Algorithm 1来生成一个包含至少一个充分排列的排列集，从而避免枚举所有 p! 个排列。Algorithm 2则利用这个排列集计算RC-score。
5. 证明算法一致性 (Theorem 3.5)：证明分为两步。首先，证明当 n, δ_r → ∞ 时，Algorithm 1生成的排列集以概率1包含一个充分排列（Theorem 3.4）。其次，证明对于充分排列，其对应的 ˆc(π) 趋于无穷，且 ˆu(π) 趋于根因；对于非充分排列，ˆc(π) 有界。结合这两点，即可证明根因的RC-score会以概率1成为最大值。
关键跳跃点：
- 从Z-score到Cholesky分解：Z-score只考虑边际方差，而Cholesky分解考虑了整个协方差结构，从而能“去相关”，使得在因果顺序下，ξ(π) 能精确地定位根因。这是从“边际”到“联合”的关键一步。
- 从“已知因果顺序”到“未知因果顺序”：如果因果顺序已知，问题很简单。本文的关键跳跃在于，通过尝试所有排列，并利用 ξ(π) 的1-稀疏性作为“信号”，绕过了因果顺序的估计问题。这相当于将“估计因果顺序”这个困难问题，转化为了“寻找一个具有特定稀疏模式的向量”这个更简单的问题。
- 从“所有排列”到“充分排列”：枚举所有 p! 个排列是不可行的。Theorem 3.3 的刻画使得我们可以通过估计一个“异常变量集” D 来生成一个远小于 p! 的排列集，从而实现了计算可行性。
技术技巧点名：
- Cholesky分解：用于对协方差矩阵进行“去相关”，是定义 ξ(π) 和实现“1-稀疏”模式的核心工具。
- 排列矩阵：用于形式化地描述变量重排。
- QR分解：在Lemma D.1的证明中，作者使用了 A^T 的QR分解来建立 L 和 A 之间的关系。
- Chebyshev不等式：在证明Lemma D.4和D.5时，用于控制 ξ(π) 的随机波动，从而证明其在大干预强度下的渐近行为。
- Lasso：在高维版本Algorithm 3中，用于估计每个变量的马尔可夫毯，实现降维。

真实例子与应用¶

数据：来自423名疑似孟德尔疾病患者的皮肤成纤维细胞的RNA-seq基因表达数据。其中58名患者有已知的（或可能的）遗传突变，作为根因的“金标准”。
方法应用：对每个患者，将其余422名患者作为观测样本，该患者作为干预样本。应用Algorithm 3（高维版本）计算每个基因的RC-score。作为对比，也计算了平方Z-score。
结果：
- 对于患者R16472，平方Z-score和RC-score都成功识别了根因（rank 1）。
- 对于患者R96820，平方Z-score失败（根因rank不是1），而RC-score成功（rank 2）。
- 在全部58名患者中，RC-score在28名患者中给出rank 1，在38名患者中给出top 5，在46名患者中给出top 10。而平方Z-score仅在17名患者中给出rank 1。
- RC-score在30名患者中优于平方Z-score，在10名患者中劣于平方Z-score，且RC-score的改进幅度通常更大。
这个例子想说明什么：验证了本文提出的RC-score方法在真实的高维基因表达数据上，相比简单的平方Z-score方法，能更有效地发现致病基因，尤其是在干预效应传播导致大量基因异常的情况下。

🔎 结论是否比证明窄¶

高维算法 (Algorithm 3)：作者明确声明这是一个“启发式算法”，没有提供理论保证（“We emphasize that this high-dimensional root cause discovery algorithm is a heuristic algorithm, and no theoretical guarantees are provided here.”）。论文的严格理论结果（Theorem 3.1-3.5）仅适用于低维或可通过样本协方差矩阵良好估计协方差矩阵的情形。高维算法的成功仅通过模拟和真实数据验证。
“唯一根因”假设：论文的所有理论结果都建立在“唯一根因”的假设上。在“讨论”部分，作者承认“在许多应用中，可能存在多个根因”，并将其列为未来工作。因此，论文的结论严格限于单根因场景。
线性模型假设：所有理论结果都基于线性SEM。作者在讨论中也提到了“非线性关系”是未来方向。

四、开放问题（点到为止，扎根具体语句）¶

潜变量下的理论性质：论文的模拟（Appendix E.6）显示Algorithm 2对潜变量有一定鲁棒性，但作者明确指出“a formal study is important and desired”（Section 6）。扎根点：Section 6第一段：“One direction involves cases with latent variables. Although our simulations... indicate some robustness... a formal study is important and desired.”
高维算法的理论保证：Algorithm 3在真实数据上表现良好，但缺乏理论支持。作者将其列为未来工作。扎根点：Section 3.4末尾：“We emphasize that this high-dimensional root cause discovery algorithm is a heuristic algorithm, and no theoretical guarantees are provided here.”
多根因、非线性和反馈环：论文的模型假设了唯一的根因、线性关系和DAG。作者在讨论中明确将这些推广列为未来方向。扎根点：Section 6第二段：“Furthermore, in many applications, there may be multiple root causes, non-linear relationships between variables, or feedback loops. Thus, generalizing the current methodology to address these complexities would be important.”
不确定性量化：作者指出，量化根因发现的不确定性“seems challenging”，因为不确定性来源于未知的因果顺序和未知的根因。理想情况下，希望输出一个包含真根因的置信集。扎根点：Section 6第三段：“Quantifying the uncertainty of our method would be very valuable. ... Ideally, we would like to develop a method that captures both, so that we can output a set of causes with a theoretical guarantee that the true root cause is inside this set with high probability.”

Maintained by 陈星宇 · Homepage · Source on GitHub