非线性因果发现的可扩展性—准确性前沿：映射与推进

可扩展的非线性因果发现需要将灵活的机制估计器与对大规模图空间的高效搜索相结合。为应对这一挑战，人们提出了多个算法家族，但它们在准确性与运行时间之间的权衡仍缺乏充分理解。我们对四类主要方法进行了实证比较：可微结构学习、摊销结构学习、评分匹配和组合搜索。结果揭示了各类方法互补性的瓶颈：可微方法和摊销方法具有良好的可扩展性，但存在准确性差距；评分匹配方法在低维情况下可以达到较高准确性，但随着特征规模增大而迅速退化；组合方法仍能保持较高准确性，但反复且冗余的局部评分使其运行速度变慢。针对这一瓶颈，我们开发了 SPADE，这是一种基于样条的评分评估方案，可一次性编译充分统计量，并在整个组合搜索过程中重复使用。在入度有界的条件下，其高斯变体将算法复杂度从 O(nd^3) 降低至 O(nd^2+d^3)。实证结果表明，SPADE 将观测到的可扩展性—准确性前沿推进了数个数量级：它能在数秒内解决包含 100 个变量、160K 个样本的问题，并在数分钟内解决包含 1600 个变量、2.5K 个样本的问题，同时在合成数据集和真实世界基准测试中保持较高的结构准确性。这些结果表明，组合搜索的实际可处理规模已实现显著提升，并凸显了沿完整的准确性—运行时间前沿评估可扩展因果发现方法的重要性。