Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning

本文提出了名为 FLOP 的基于分数的因果发现算法，通过结合快速父节点选择与迭代 Cholesky 分数更新显著降低运行时间，从而使得在离散搜索空间中高效执行迭代局部搜索成为可能，并在基准测试中实现了接近全局最优的极高结构恢复精度。

要点

这篇论文介绍了一种名为 FLOP 的新算法，它的任务是**“因果结构学习”**。听起来很学术，但我们可以用一个生动的比喻来理解它。

🕵️‍♂️ 核心任务：解开“谁导致了谁”的谜题

想象你有一堆混乱的线索（数据），比如“下雨”、“草地湿”和“有人带伞”。你的任务是画出一张因果关系图：是雨导致草地湿，还是草地湿导致下雨？（显然不是后者）。

在科学上，这叫做从观察数据中找出有向无环图（DAG）。以前的方法要么太慢（像蜗牛），要么为了追求速度而牺牲了准确性（像走捷径的迷路者）。

🚀 FLOP 是什么？

FLOP 代表 Fast Learning of Order and Parents（快速学习顺序与父节点）。
你可以把它想象成一个超级高效的侦探，它不靠猜，而是靠**“离散搜索”**（Discrete Search）来寻找真相。

1. 以前的侦探 vs. FLOP 侦探

• 旧方法（连续优化）： 就像在迷雾中开车，试图通过平滑的曲线慢慢逼近目标。虽然路看起来是直的，但很容易在某个小坑（局部最优解）里陷进去，或者因为路况太复杂（数学约束）而开不动。
• 旧方法（离散搜索）： 就像在迷宫里一步步走。以前的侦探走得太慢，因为每走一步都要重新计算整个迷宫的地图，导致他们只能走几步就放弃了。
• FLOP 侦探： 它也是走迷宫（离散搜索），但它有两个超级外挂，让它跑得飞快且从不迷路：

2. FLOP 的两大“秘密武器”

武器一：聪明的“热身”策略 (Warm Start)

• 比喻： 想象你在整理书架。如果你把一本书从第 1 页移到第 10 页，你不需要把整本书都重新读一遍来重新分类。你只需要微调一下周围的几本书。
• FLOP 的做法： 当它尝试改变因果图的顺序时，它不会从零开始重新计算，而是基于上一次的计算结果进行微调。这就像在整理书架时，只移动那几本受影响的书，而不是把整个图书馆重新建一遍。这让它的速度提升了100 倍以上。

武器二：动态的“数学快照” (Cholesky Updates)

• 比喻： 以前计算一个复杂的数学公式（比如计算概率），就像每次都要重新拍一张高清全家福，然后重新数人头。
• FLOP 的做法： 它使用一种叫Cholesky 分解的数学技巧。当只有一两个人（变量）发生变化时，它不需要重拍全家福，只需要在原来的照片上 P 一下（更新）就能得到新结果。这极大地节省了计算时间。

3. 它的“战术”：Iterated Local Search (ILS)

FLOP 不仅跑得快，还懂得**“坚持”**。

• 比喻： 想象你在找一座最高的山峰（全局最优解）。普通的登山者爬到一个小山包（局部最优）就以为到了顶峰，然后停下来。
• FLOP 的策略： 它采用**“迭代局部搜索”**。
  1. 先爬到一个山顶。
  2. 如果感觉不对劲，它就故意把自己“踢”下山坡（扰动），换个角度重新开始爬。
  3. 因为它跑得很快，它可以尝试成百上千次这种“爬山 - 踢下山 - 再爬”的过程。
  4. 最终，它几乎总能找到那座真正的最高峰。

📊 结果如何？

论文通过大量的实验（就像让侦探在成千上万个模拟案件中破案）证明：

• 速度快： 在处理 500 个变量的复杂网络时，FLOP 能在几分钟内完成，而以前的方法可能需要跑几个小时甚至超时。
• 准确率高： 在大多数情况下，FLOP 找到的因果关系图几乎完美还原了真相（接近 100% 的准确率）。
• 重新定义规则： 以前大家认为“离散搜索”太慢，所以转向了“连续优化”。FLOP 证明了：只要优化得当，离散搜索不仅可行，而且是最强王者。

💡 总结

这篇论文的核心思想是：不要为了追求速度而放弃寻找真理的完整性。

FLOP 就像是一个装备了涡轮增压和智能导航的赛车手。它告诉我们，在因果推断的世界里，通过巧妙的工程优化（如利用之前的计算结果、快速更新数学公式），我们可以既快又准地解开复杂的因果谜题，而不需要依赖那些容易出错的“捷径”。

一句话总结： FLOP 让寻找“谁导致了谁”这件事，从“在泥潭里跋涉”变成了“在高速公路上飙车”，而且还能保证你到达的是正确的终点。

技术摘要

这是一篇发表于 ICLR 2026 的会议论文，题为《拥抱离散搜索：因果结构学习的一种合理途径》（EMBRACING DISCRETE SEARCH: A REASONABLE APPROACH TO CAUSAL STRUCTURE LEARNING）。作者提出了名为 FLOP (Fast Learning of Order and Parents) 的新算法，旨在解决线性加性噪声模型（Linear ANM）下的因果结构学习问题。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

• 核心任务：从观测数据中学习生成数据的有向无环图（DAG）结构。
• 现有挑战：
  • 离散搜索的困境：基于分数的离散搜索算法（如局部搜索）在有限样本下容易陷入局部最优，且传统观点认为其计算复杂度呈指数级，难以处理大规模变量。
  • 连续优化的局限：近年来流行的连续优化方法（如 NOTEARS, DAGMA）将无环性约束松弛为平滑约束，但被指出存在优化复杂性、收敛困难、需要阈值处理以及依赖代理目标函数等问题。
  • 性能瓶颈：现有的基于离散搜索的算法（如 BOSS）在处理大规模或稠密图时计算成本过高，导致无法充分利用迭代局部搜索（ILS）来跳出局部最优。
• 核心论点：作者认为，离散搜索在因果发现中仍是一种合理且有效的方法，关键在于通过算法优化使其在计算上可行，从而能够进行更彻底的搜索。

2. 方法论 (Methodology)

FLOP 是一种基于分数的因果发现算法，专门针对线性加性噪声模型（ANM），使用贝叶斯信息准则（BIC）作为评分标准。它通过以下四个关键组件实现了“拥抱离散搜索”：

2.1 基于父集重用的 Grow-Shrink 优化 (Warm-started Grow-Shrink)

• 传统做法：在 BOSS 等算法中，每次评估节点重插入（reinsertion）时，都需要从头（空集）开始运行 Grow-Shrink 算法来寻找最佳父节点集合。
• FLOP 改进：利用局部搜索的特性，当节点在拓扑序中移动时，其前缀集合仅增加或减少一个节点。FLOP 将上一次 Grow-Shrink 的结果作为初始父集（Warm Start），而不是从零开始。
• 理论保证：证明了这种修改后的 Grow-Shrink 在样本量趋于无穷时，仍能收敛到受限马尔可夫边界（Restricted Markov Boundary），保证了学习到的 DAG 是马尔可夫的。

2.2 动态 Cholesky 分解更新 (Dynamic Cholesky Updates)

• 评分计算加速：在计算高斯 BIC 分数时，核心在于计算条件方差。传统方法需要重新计算协方差子矩阵的逆或 Cholesky 分解，复杂度为 $O(k^3)$。
• FLOP 改进：由于每次局部移动仅涉及父集的一个节点的增减，FLOP 使用**秩一更新（Rank-one update）和降秩更新（Downdate）**技术来更新 Cholesky 分解因子。
• 效果：将单次评分更新的复杂度从 $O(k^3)$ 降低到 $O(k^2)$，显著提升了大规模图上的计算速度。

2.3 原则化的初始序构建 (Principled Initialization)

• 问题：随机初始序在处理长路径图（Path graphs）时表现不佳，因为距离较远的祖先 - 后代节点对可能因边际依赖性弱而被 Grow-Shrink 漏掉。
• FLOP 改进：构建初始序时，优先将强相关的节点相邻放置。具体策略是：从最相关的两个节点开始，迭代地选择残差方差最小的变量加入当前序中（通过 Cholesky 分解高效计算）。
• 效果：有效解决了路径图上的局部最优问题，提高了初始解的质量。

2.4 迭代局部搜索 (Iterated Local Search, ILS)

• 策略：利用上述计算加速带来的时间盈余，实施 ILS 元启发式算法。
• 流程：
  1. 从初始序开始进行局部搜索直到局部最优。
  2. 对当前最佳序进行扰动（随机交换 $k$ 个元素，默认 $k = \ln p$）。
  3. 从扰动后的序重新开始局部搜索。
  4. 重复此过程直到计算预算耗尽。
• 意义：将计算预算作为超参数，允许用户通过增加运行时间来换取更高的准确率。

3. 关键贡献 (Key Contributions)

1. FLOP 算法：提出了一种快速学习拓扑序和父节点的算法，结合了上述四种优化技术。
2. 理论保证：证明了带有 Warm-start 的 Grow-Shrink 在样本极限下仍能恢复马尔可夫边界，且 FLOP 输出的 CPDAG（完成部分有向无环图）是马尔可夫的。
3. 计算效率：通过 Cholesky 更新和 Warm-start，FLOP 比现有的 BOSS 算法快 100 倍以上，能够处理 500 个节点的图，而 BOSS 在 150 个节点时即超时。
4. 实证性能：在多个基准测试（Erdős-Rényi 图、无标度图、Alarm 网络等）上，FLOP 实现了接近完美的结构恢复，且运行时间优于或等同于连续优化方法。

4. 实验结果 (Results)

• 基准测试表现：
  • 在 50 个节点、平均度为 8 的 Erdős-Rényi (ER) 图上，FLOP 的 SHD（结构汉明距离）显著低于 PC、GES 和 DAGMA。
  • 在 25 个节点、平均度为 16 的稠密 ER 图上，FLOP 通过 ILS 重启（如 FLOP100）达到了与精确算法（Exact）相当的准确率，但运行时间更短。
  • 在 Alarm 网络（37 节点）上，FLOP 实现了近完美的恢复（82%-94% 的实例完全恢复），而 BOSS 仅为 6%。
• BIC 分数优化：FLOP 找到的图通常具有比真实图更低的 BIC 分数（在有限样本下），这表明在有限样本下，全局 BIC 最优解并不总是对应真实图，但 FLOP 能更有效地逼近 BIC 最优解。
• 鲁棒性：即使在非高斯噪声（均匀分布）或非标准化数据下，FLOP 依然保持高性能。但在非线性数据或违反忠实性假设的复杂场景下，性能下降主要归因于评分准则（BIC）的失配，而非优化算法本身。
• 对比连续方法：FLOP 在优化 BIC 分数方面优于 DAGMA 等连续方法，且运行速度快得多。

5. 意义与结论 (Significance & Conclusion)

• 重新审视离散搜索：论文有力地反驳了“离散搜索因 NP 难而不可行”的固有偏见。作者指出，标准的 NP 难构造通常涉及未观测变量，而在常见的因果发现设定（稀疏 DAG、无隐藏变量）下，离散搜索是可行的。
• 计算与精度的权衡：FLOP 展示了通过计算效率的提升（Cholesky 更新等），可以将“计算预算”转化为“搜索深度”，从而通过 ILS 获得更高的有限样本精度。
• 研究重心转移：作者认为，因果发现的主要挑战不再仅仅是优化算法的设计（如连续 vs 离散），而在于设计能够在有限样本下识别真实图的评分准则。如果评分准则本身在有限样本下无法识别真实图（如 BIC 在有限样本下的偏差），那么再强大的优化算法也无法恢复真实结构。
• 开源实现：作者提供了基于 Rust 的高效实现（flopsearch），可通过 Python 调用，促进了该方法的实际应用。

总结：FLOP 通过算法工程上的创新（Warm-start, Cholesky 更新）和策略上的改进（原则化初始化, ILS），证明了离散搜索在因果结构学习中不仅可行，而且在精度和效率上可以超越当前的连续优化方法，呼吁社区重新重视并拥抱离散搜索方法。