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

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