Coarsening Linear Non-Gaussian Causal Models with Cycles¶
会议: NeurIPS 2026
arXiv: 2605.10163
代码: https://github.com/fmfsa/coarsening-cycles
领域: 因果推理
关键词: 因果粗化, 有向环因果模型, 强连通分量, 线性非高斯模型, 缩减图可辨识性
一句话总结¶
本文将因果粗化格结构拓展至含反馈环的线性非高斯因果模型，证明强连通分量划分构成了无环粗化格的结构基底，其凝聚缩减图（Condensation DAG）在观测分布等价类中具有完全不变性，从而实现在三次多项式时间与明确样本复杂度下辨识高维环状系统的低维因果无环图。
研究背景与动机¶
因果发现长期以有向无环图（DAG）为核心研究范式，然而生物基因调控网络、物理动力学系统以及宏观经济体系等实际系统普遍存在反馈回路（Feedback Loops）。在线性非高斯结构因果模型（Linear Non-Gaussian SCM）设定下，尽管经典 ICA-LiNG-D 方法能利用独立成分分析恢复系统的反混叠矩阵，但由于有向环的存在，观测数据在理论上只能辨识至一个包含有向环反转的分布等价类，且遍历所有容许行置换在最坏情况下具有变量数阶乘级别的指数时间复杂度。后续引入高阶矩或非对称噪声的方法虽能处理不相交环，但对噪声偏度做出了严苛假定，且在环重叠或尺度扩大时计算瓶颈骤显。
与微观层面的完整环辨识相对，宏观层面的因果粗化与抽象旨在将高维因果网络聚类为低维因果摘要。然而现有的因果粗化理论全面假定高维与低维结构同时满足无环性，排除了所有存在局部反馈回路的真实高维网络，这导致粗化理论与含环因果发现之间存在显著割裂。在存在环路的情况下，微观变量间的因果效应因循环放大难以单点干预，但宏观集群之间的祖先因果层级往往保持着清晰的单向流动。
本文的切入角度是重新审视有向图在代数格上的商图性质：既然环路内部的循环反转不会破坏集群之间的拓扑可达性，那么与其在高维微观层面强行消除不可辨识的环内方向歧义，不如寻找粗化格中保持无环性的最细划分。核心 idea：将强连通分量（SCC）划分确立为因果粗化格的唯一结构基底，利用其诱导的缩减图（Condensation DAG）在观测等价类中的置换不变性，直接绕过对环内方向的指数级枚举，在三次多项式时间内精确辨识具有因果马尔可夫性的低维因果 DAG。
方法详解¶
整体框架¶
本文方法的输入为 \(d\) 维连续观测数据矩阵 \(X \in \mathbb{R}^{n \times d}\)，其生成机制遵循含环线性非高斯结构因果模型 \(X = BX + \varepsilon\)（其中 \(I-B\) 可逆，噪声 \(\varepsilon\) 相互独立且至多一个分量为高斯），输出为聚类后的低维有向无环图（凝聚缩减图）\(\widehat{G}^{\mathrm{sc}} = (\widehat{\Pi}, \widehat{E}')\)。整体流程由连续统计估计与离散图论压缩两个阶段串联而成：首先通过 FastICA 与匈牙利算法求解单一行置换以获取候选邻接矩阵，随后经由软阈值过滤消除有限样本扰动，最后通过 Tarjan 算法提取强连通分量并构建集群间无环拓扑边。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["观测数据矩阵 X ∈ R^(n×d)"] --> B["FastICA 分离矩阵估计<br/>W_hat = FastICA(X, d)"]
B --> C["匈牙利算法对角匹配<br/>单容许行置换 P_hat"]
C --> D["候选邻接矩阵计算与阈值过滤<br/>B_hat = I - diag(PW)^(-1) PW, 阈值 τ"]
D --> E["Tarjan 算法强连通分量划分<br/>提取 SCC 格基底 Π_hat"]
E --> F["集群间有向边诱导投影<br/>构建凝聚图 G_hat^sc = (Π_hat, E'_hat)"]
F --> G["C-DAG 因果效应辨识与干预计算"]关键设计¶
1. 强连通分量结构基底定理：划定无环粗化的代数下界 因果粗化要求变量分区 \(\Pi = \{\pi_1, \ldots, \pi_k\}\) 在原图 \(G=(V, E)\) 上的商图 \(G' = (\Pi, E')\) 必须是严格的 DAG。针对含环图 \(G\)，若两个变量 \(u, v \in V\) 属于同一强连通分量（SCC），则原图中必然存在有向路径 \(u \leadsto v\) 与 \(v \leadsto u\)。一旦粗化分区将它们划分至不同聚类 \(\chi(u) \neq \chi(v)\)，商图中必将诱导对应集群间的双向路径并形成宏观环路，彻底破坏无环性要求。因此，同一 SCC 内的节点在任意有效的 DAG 粗化中必须被合并入同一聚类。这意味着 SCC 划分是粗化划分格（Coarsening Lattice）上的极小元（Structural Floor），即最细的有效 DAG 粗化，其商图恰好是经典图论中的凝聚缩减图 \(G^{\mathrm{sc}}\)。
2. 缩减图观测可辨识性定理：环路反转等价类下的拓扑不变性 在线性非高斯模型中，FastICA 恢复的解矩阵存在行置换与尺度不确定性。不同容许置换 \(P\) 对应于对原图 \(G\) 中有向环的边方向反转（Cycle Reversals），从而形成一个观测分布等价类。本文的核心理论突破在于证明了有向环反转操作严格局限在单个 SCC 内部，仅改变该分量内部结构方程的指定方式，而不会破坏分量内部节点之间的相互可达性，更不会跨分量增删或反转 inter-SCC 有向边。因此，对等价类中任意两个观测等价图 \(G_1, G_2\)，其缩减图完全同构： $\(G_1^{\mathrm{sc}} = G_2^{\mathrm{sc}}\)$ 这一不变性从根本上免去了传统方法对全部分布等价类成员的指数搜索，仅需通过匈牙利算法求解一个非零对角匹配置换 \(P\)，即可保证在大样本极限下恢复真实的 \(G^{\mathrm{sc}}\)。此外，系统的聚类边缘分布相对于 \(G^{\mathrm{sc}}\) 满足因果马尔可夫性，将含环系统的 \(\sigma\)-分离关系无损投影为标准的 \(d\)-分离关系。
3. 有限样本自适应阈值化与双重失效边界控制 在有限样本 \(n\) 条件下，估计邻接矩阵 \(\widehat{B} = I - \mathrm{diag}(P\widehat{W})^{-1}P\widehat{W}\) 包含统计扰动，需通过阈值 \(\tau\) 截断以恢复支撑集。算法面临两个方向截然相反的失效模式：模式 (a) 为真边截断（\(\beta_{\min}\) 处的有效边低于 \(\tau\)），导致原强连通分量连通度破裂并碎裂为更小聚类，破坏 DAG 粗化性质；模式 (b) 为虚假伪边保留（原本为 0 的位置高于 \(\tau\)），在两个原本不相连的 SCC 之间闭合回路，导致多个 SCC 发生错误塌缩合并。通过对第四阶矩约束下的 FastICA 误差应用高概率局部 Lipschitz 展开与联合界，定理推导给出了确切的误辨识概率上界： $\(\Pr\bigl[\widehat{G}^{\mathrm{sc}}_n \neq G^{\mathrm{sc}}\bigr] \leq \frac{K_1}{n^2 (\beta_{\min} - \tau_n)^4} + \frac{K_2}{n^2 \tau_n^4}\)$ 当选取平衡阈值 \(\tau = \frac{\beta_{\min}}{2}\) 时，样本复杂度严格受界于 \(n = \Theta\left(\frac{d}{\beta_{\min}^2 \sqrt{\delta}}\right)\)，确保了在多项式样本下的精确几何收敛。
损失函数 / 训练策略¶
算法以无监督方式运行，主要计算开销由两部分构成：首先执行 FastICA 提取反混叠矩阵，其迭代矩阵乘法在样本量 \(n\)、变量数 \(d\) 下的时间复杂度为 \(\mathcal{O}(k \cdot n \cdot d^2)\)（\(k\) 为收敛步数）；随后利用匈牙利算法（Hungarian Method）求解最大权重完全二分图匹配以寻找对角线非零的行置换 \(P\)，耗时 \(\mathcal{O}(d^3)\)；计算 \(\widehat{B}\)、阈值化、Tarjan 强连通分量遍历及有向边投影均为 \(\mathcal{O}(d^2)\)。综合全流程，最坏时间复杂度被严格约束在： $\(\mathcal{O}(k \cdot n \cdot d^2 + d^3)\)$ 相比于传统 ICA-LiNG-D 算法穷举置换带来的 \(\mathcal{O}(d!)\) 组合爆炸，实现了阶乘级到三次多项式级的本质降维。
实验关键数据¶
主实验¶
在合成数据基准上，设定变量维度 \(d=10\)，非平凡 SCC 数量 \(\kappa \in \{3, 4, 5\}\)，边密度 \(\lambda \in \{0.3, 0.5, 0.8\}\)，权重采样自 \([0.5, 0.95]\)，采用双边拉普拉斯噪声。实验针对稳定动力学机制（\(\rho(B) \approx 0.9\)）与不稳定动力学机制（\(\rho(B) = 1.5\)）分别检验。评估指标包括强连通分量划分的调整兰德系数（ARI）、聚类级别无环图边恢复 \(F_1\)（Cluster-DAG \(F_1\)）以及变量级微观边恢复 \(F_1\)（Variable-level \(F_1\)）。
| 机制设定 (\(\rho(B)\)) | 边密度 \(\lambda\) | 样本量 \(n\) | 分区准确率 (ARI) | 集群图 \(F_1\) (Cluster-DAG) | 微观边 \(F_1\) (Variable-level) |
|---|---|---|---|---|---|
| 稳定动力学 (\(\rho \approx 0.9\)) | 0.3 | \(10^2\) | 0.28 ± 0.06 | 0.45 ± 0.05 | 0.38 ± 0.04 |
| 稳定动力学 (\(\rho \approx 0.9\)) | 0.3 | \(10^3\) | 0.89 ± 0.03 | 0.92 ± 0.02 | 0.86 ± 0.02 |
| 稳定动力学 (\(\rho \approx 0.9\)) | 0.3 | \(10^5\) | 1.00 ± 0.00 | 1.00 ± 0.00 | 0.99 ± 0.01 |
| 稳定动力学 (\(\rho \approx 0.9\)) | 0.8 | \(10^5\) | 1.00 ± 0.00 | 1.00 ± 0.00 | 0.98 ± 0.01 |
| 不稳定动力学 (\(\rho = 1.5\)) | 0.3 | \(10^3\) | 0.86 ± 0.04 | 0.90 ± 0.03 | 0.54 ± 0.05 |
| 不稳定动力学 (\(\rho = 1.5\)) | 0.3 | \(10^5\) | 1.00 ± 0.00 | 1.00 ± 0.00 | 0.58 ± 0.04 (饱和停滞) |
| 不稳定动力学 (\(\rho = 1.5\)) | 0.8 | \(10^5\) | 1.00 ± 0.00 | 1.00 ± 0.00 | 0.61 ± 0.03 (饱和停滞) |
消融与扩展性对比¶
将本文方法与当前最新的不相交环因果发现基准 DisjointCycles（Drton et al., 2025，利用三阶矩估计微观环）在大规模节点维度与偏斜指数噪声分布下进行可扩展性消融对比（固定 \(\kappa=10, \lambda=0.5\)）：
| 节点维度 \(d\) | 样本量 \(n\) | 方法配置 | 分区 ARI | 集群图 \(F_1\) (Cluster-DAG) | 单次耗时 / 秒 | 理论复杂度状态 |
|---|---|---|---|---|---|---|
| \(d=20\) | \(10^4\) | DisjointCycles (基线) | 0.62 ± 0.05 | 0.74 ± 0.04 | 48.2 s | 高阶矩统计瓶颈 |
| \(d=20\) | \(10^4\) | Ours (Algorithm 1) | 1.00 ± 0.00 | 1.00 ± 0.00 | 0.8 s | \(\mathcal{O}(knd^2 + d^3)\) |
| \(d=50\) | \(10^5\) | DisjointCycles (基线) | 0.18 ± 0.04 | 0.28 ± 0.03 | 1420.0 s | 严重欠拟合 |
| \(d=50\) | \(10^5\) | Ours (Algorithm 1) | 1.00 ± 0.00 | 1.00 ± 0.00 | 3.6 s | 稳定饱和 |
| \(d=100\) | \(10^5\) | DisjointCycles (基线) | 0.05 ± 0.02 | 0.21 ± 0.02 | > 10000.0 s | 计算爆炸超时 |
| \(d=100\) | \(10^5\) | Ours (Algorithm 1) | 1.00 ± 0.00 | 1.00 ± 0.00 | 9.4 s | 极速收敛 |
关键发现¶
- 宏观可辨识性与微观不可辨识性的鲜明反差：在不稳定谱半径机制（\(\rho(B)=1.5\)）下，因等价类内部环路反转无法通过稳定性准则消除，微观变量层面的 \(F_1\) 在大样本下依然停滞在 0.58 附近；然而集群层面的 ARI 与 Cluster-DAG \(F_1\) 均平滑单调收敛至 1.00。实验直接印证了定理 1 的理论预测：缩减图对微观循环反转具有完全不变性。
- 阈值敏感性区间与失效模式分离：在 \(d=10\) 的阈值扫描实验中，当 \(n \ge 5000\) 时存在极宽的平稳安全区间 \(\tau \in [0.1, 0.5]\)，此时聚类数精确命中真实真值；当 \(\tau \le 0.01\) 时发生失效模式 (b)，所有节点坍缩为单一集群（\(|\widehat{\Pi}|=1\)）；当 \(\tau \ge 1.0\) 时发生失效模式 (a)，所有节点碎裂为孤立单点（\(|\widehat{\Pi}|=d=10\)）。
- 计算复杂度与重叠环鲁棒性优势：对比基线 DisjointCycles 依赖的三阶矩检验，本文基于 FastICA 与匈牙利算法的框架不受限于“不相交环”结构假定，即使在内部环路密集交织的强连通分量下，依然能在 10 秒内完成百维变量的凝聚结构求解，而基线耗时超过万秒且产生严重分量误判。
亮点与洞察¶
- 将代数因果粗化格理论与经典图论凝聚结构深度融合，严格确立了 SCC 划分作为有向图无环粗化“格底（Lattice Floor）”的数学地位，填补了粗化理论在非无环系统中的理论空白。
- 巧妙利用了线性非高斯循环系统中等价类反转仅局限于强连通分量内部的拓扑局部性，将不可辨识的微观混淆转化为宏观缩减图上的完全可辨识性，使无环 C-DAG 干预分析工具链能够无缝拓展至含环系统。
- 算法彻底摒弃了传统含环发现方法中对行置换空间的阶乘级穷举，通过匈牙利对角匹配将最坏时间复杂度压缩至 \(\mathcal{O}(knd^2 + d^3)\)，为大规模复杂网络反馈分析提供了高效率范式。
局限与展望¶
- 理论目前严格依赖于线性非高斯且无隐变量（No Latent Confounders）假定；若存在多个高斯噪声源，ICA 的全局正交旋转不确定性将导致不同 SCC 之间的伪混合，使缩减图可辨识性遭到破坏。
- 虽论证了整簇干预（Hard Cluster Intervention）或软干预下的因果效应可辨识性，但由于反馈环结构的存在，系统无法对单个强连通分量内的孤立微观变量执行标准 Hard-do 干预。
- 未来方向包括将超完备 ICA（Overcomplete ICA）引入该理论以容忍潜在混杂因素，以及在真实生物基因调控与宏观交通流网络中进行集群级因果效应评估。
相关工作与启发¶
- vs ICA-LiNG-D (Lacerda et al., 2008): 经典方法致力于恢复完整的微观含环图，必须依赖系统谱半径小于 1 的稳定性假设进行单向筛选，且置换搜索耗时 \(\mathcal{O}(d!)\)；本文聚焦于宏观缩减图，不仅放宽了动力学稳定性假设，且通过单次多项式图匹配将复杂度降至三次阶。
- vs Disjoint-Cycles LiNGAM (Drton et al., 2025): 该基线依赖二阶与三阶混合矩进行逐层拓扑排序，强制要求环路之间完全顶点不相交且噪声具备偏度；本文基于标准 FastICA，能够天然处理任意复杂的重叠密集环，且在计算扩展性上高出三个数量级。
- vs Causal Coarsening (Madaleno et al., 2026; Wahl et al., 2024): 先前粗化理论预先假定基底高维图为 DAG；本文将其延伸至含环图谱，证明了 SCC 是任何保证商图无环的最细必然粗化。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立含环线性因果系统在粗化格上的结构底基理论，证明缩减图在分布等价类下的代数不变性。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖不同稳定性状态、多重密度、大维度扩展性对比以及确切的有限样本失效模式扫频验证。
- 写作质量: ⭐⭐⭐⭐⭐ 概念铺垫严密，数学论证与图论直觉结合自然，定理叙述极为凝练。
- 价值: ⭐⭐⭐⭐⭐ 为含反馈回路系统的宏观因果效应辨识提供了具有多项式计算保证的普适分析工具。