arXiv:2605.17465cs.LG2026-05被引 1

提出新算法TriOpt,高效发现高维数据中的因果关系。

TriOpt: A Scalable Algorithm for Linear Causal Discovery

论文配图:TriOpt: A Scalable Algorithm for Linear Causal Discovery
图 1 · 摘自论文原文
  • 结合排序与连续优化,分两阶段快速推断因果顺序和结构
  • 在高维数据上速度比现有方法快数十倍,准确率相当或更好
  • 适合大规模因果分析,尤其适用于高维真实数据

从观测数据中学习因果关系极具挑战性,因图搜索空间随变量数呈超指数增长。基于排序的方法通过先识别拓扑顺序来缩小搜索空间,而连续优化方法则将有向无环图(DAG)学习建模为带无环约束的可微目标。尽管概念上吸引人,两类方法在高维场景下均面临显著可扩展性瓶颈。本文提出一种新型线性因果发现框架TriOpt,紧密融合两种范式,在不牺牲精度的前提下实现显著的可扩展性提升。该方法分为两个高效阶段:首先利用Sherman-Morrison秩-1更新与线性核的加性结构,快速估计拓扑顺序;其次,在已知顺序下,将结构学习重构为凸连续优化问题,完全避免昂贵的无环性约束。理论上证明,在正确顺序下,TriOpt可精确恢复底层线性DAG。实验表明,无论在合成、半合成还是真实数据集上,TriOpt在高维情形下相比当前最优线性因果发现方法实现数量级的速度提升,同时保持相当或更优的准确性。

原文摘要 · Abstract (English)

Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.

因果发现线性模型可扩展性优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。