超越平滑DAG精确性的支持选择：补全几何、得分边际与选择性证书

# 超越光滑 DAG 精确性的支持选择：补全几何、分数边际与选择性证书

来源：https://arxiv.org/html/2608.08103

Rui Wu  Zongyuan Chen  Hong Xie  
计算机科学与技术学院，中国科学技术大学  
\{wurui22, chenzongyuan\}@mail.ustc.edu.cn  [email protected]

###### 摘要

光滑无环性约束回答的是：一个加权支持集是否是 DAG。而结构学习提出的是另一个问题：应当对支持集做何种修改？已有分析针对特定约束公式建立了退化性结果，但并未分离出光滑精确性本身所蕴含的结论。在 DAG 边界处，我们证明极小环补全生成一个平方自由单项式理想，任何精确表示的受限 Taylor 喷射都属于该理想。若最小补全包含 q 条边，则向量残差的第一个可能响应阶数为 q，非负标量的为 2q。在 NOTEARS 和 DAGMA 中，存在指数多个常尺度循环流形，它们在远离边界处同样表现出缺乏排序的性质。为了将该表示极限与优化联系起来，我们推导了孤立环的精确选择时间。当 Ψ′(h) ≍ h^ν 时，仅可行性时间为 T_0(ε) = Θ(ε^{−(2ν+1)})。对于 ν>0，分数边际会在 T_0^{−1} 尺度上改变主导动力学。端点 ν=0 存在对数边界层：未扰动极限要求 γ T_0 log(1/ε) → 0。受控实验检验了该规律，一个无需生成图即可计算的分离统计量在 320 条官方 NOTEARS/DAGMA 轨迹上预测了选择时间（Spearman −0.52 和 −0.66，置换 p<10^{−4}）。有限样本中分数边际未知。我们构造了一个父集置信族，其强制相反查询可证明冻结分数所有总体最优解共享的骨架和无盾对撞标签。在涉及四种前端、四种图族和四种 SEM 机制的 320 次运行审计中，每个遗憾界都覆盖了一次独立的 oracle 分数审计。3042 个已认证骨架标签和 2396 个对撞标签中，没有一个与 oracle 分数最优解不一致，尽管分别有 4.4% 和 5.5% 与生成图不一致。这些结果区分了连续 DAG 学习中常被混为一谈的三类声明：DAG 可行性、基于分数的支持选择以及因果识别。

## 1 引言

一个加权矩阵通过其零模式表示有向图。边的大小决定统计拟合度，而无环性仅在一个元素跨越零时才改变。因此，连续 DAG 学习必须在欧几里得空间上优化的同时做出离散的支持集决策。一个典型估计量结合了

min_W L(W;X) + λ R(W) + Ψ(h(W)),  (1)

其中 L 衡量拟合度，R 促进稀疏性，h 强制无环性。分数可以对竞争图排序，非光滑更新或阈值可以产生零。然而，h 的精确性仅识别无环支持集。我们问的是：精确性本身是否蕴含任何支持集排序信息。NOTEARS 提供了光滑等式

h_exp(W) = tr(exp(W∘W)) − d = 0,  (2)

其中 W ∈ R^{d×d} 是加权邻接矩阵（Zheng et al., 2018）。多项式、对数行列式和谱替代方案改变了优化问题的几何结构（Yu et al., 2019; Bello et al., 2022; Nazaret et al., 2024; Zhang et al., 2025）。它们的远场景观差异很大，但其精确性声明作出同样的承诺：h(W)=0 刻画 DAG 支持集。该承诺并不蕴含 ∇h 能区分两种都能恢复可行性的删除操作。对打结或缺失的局部信号进行重缩放无法补足缺失的排序。障碍来自支持集几何。

在 DAG 边界处，假设一组缺席边 F 会产生某个环，但任何真子集都不会。光滑精确约束在通过删除 F 中一条边得到的每个坐标面上都消失。这些面根据补全一个环所需的边数禁止低阶 Taylor 项。条件化可以改变系数和远场行为，但不能改变被该支持集几何排除的项。边界计算本身并不能描述普通大小的迭代。重标记对称性提供了缺失的联系：它产生常权重循环流形，在这些流形上可行性梯度使相互竞争的删除操作打成平手。大小为 ε 的扰动打破平局，但对于线性可行性力，达到固定边比的时间随 ε^{−1} 发散，对于冷二次罚则为 ε^{−3}。这些是最坏情况的条件性陈述，而非声称观测数据通常是对称的。它们引出了结束本文的统计问题：当分数提供排序时，有限数据能否解决它？

本文分三步展开这一论证。

- • 早期的退化性结果与某个特定的逐项幂相关。我们定义环补全理想及其初始次数 q_W(F)，它取决于若干缺席边如何共同闭合一个环。光滑精确表示的每个受限 Taylor 喷射都属于该理想，从而迫使向量残差的响应阶数至少为 q，非负标量的至少为 2q。
- • 局部 Taylor 障碍不一定支配有限尺度优化。我们用 NOTEARS 和 DAGMA 域中的 2^{0.332d} 个常尺度循环流形以及一个精确的孤立环命中时间规律填补了这一空白。该规律识别出改变支持选择的分数尺度，并在 ν=0 处揭示了一个对数过渡层。受控流和 320 条官方轨迹检验了这些预测。
- • 可行性并不能揭示数据是否解决了由此产生的分数边际。我们构造了一个父集置信族，其强制相反查询可证明冻结分数所有总体最优解共享的骨架和对撞标签。审计同时报告 oracle 分数一致性和与生成图的不一致，从而将统计选择与因果识别区分开。

已有研究考察了正 Hadamard 幂约束的退化性（Wei et al., 2020）；本文的阶数则由联合补全统计量 q_W(F) 决定。DAGMA 改善了远场路径（Bello et al., 2022），但仍受局部表示极限的约束。无环参数化、边界约束公式和离散图操作不在我们的假设范围内，并且可以打破对称性（Yu et al., 2021; Massidda et al., 2024; Gillot & Parviainen, 2022; Rey et al., 2026）。因此，前两个结果并非式 (1) 的全局迭代下界。证书同样以训练冻结的候选族和有界可分解分数为条件；它证明的是分数选择，而非因果识别。附录 C.5 给出逐条比较和精确边界。

## 2 设置与范围

令 Z = {W ∈ R^{d×d} : diag(W) = 0}，并令 D ⊂ Z 为非零支持集为 DAG 的矩阵。我们在包含感兴趣候选子空间的开域 Ω ⊆ Z 上工作；恰当选取的域可以容纳对数行列式约束。

###### 定义 2.1（精确表示）。
一个光滑映射 H: Ω → R^r 称为 *带符号/向量精确表示*，如果对每个 W ∈ Ω，

H(W) = 0  ⟺  W ∈ D.  (3)

一个光滑标量 h: Ω → R 称为 *非负精确*，如果对每个 W ∈ Ω，

h(W) ≥ 0,     h(W) = 0  ⟺  W ∈ D.  (4)

标量定义包括 EXP、迹多项式和其定义域上的 DAGMA；向量定义还允许带符号系统。非光滑函数、离散序搜索、无环参数化和边界约束域不在这些假设之内。一个沿路径的量具有 *精确阶 p*，如果 R(t) = |t|^p v + o(|t|^p)，其中 v 非零。我们的障碍给出第一个可能阶数的下界；精确性不一定达到该阶数。似然选择和稀疏正则化会影响可微程序选择马尔可夫等价类中的哪一个成员（Deng et al., 2024; Jin et al., 2026）；接下来四节在第七节回到有限数据分数选择之前，隔离可行性如何进入局部优化器。

## 3 环补全复杂度

固定一个 DAG W ∈ D 和一个有限的缺席非对角坐标集 F = {e_1, ..., e_m}。令 E_s 为 e_s 处的带符号坐标矩阵。对于 G ∈ {H, h}，定义局部限制

V_F = {x ∈ R^m : W + ∑_{s=1}^m x_s E_s ∈ Ω},    G_F(x) = G(W + ∑_{s=1}^m x_s E_s),   x ∈ V_F.  (5)

由于 Ω 是开的，V_F 是原点的一个开邻域。

###### 定义 3.1（补全数）。
候选子空间补全数为

q_W(F) = min{ |S| : S ⊆ F,  supp(W) ∪ S 是循环的 },  (6)

若无子集能补全环，则 q_W(F) = ∞。几何上，每个少于 q_W(F) 个候选坐标的坐标面都位于精确零集内；只有激活 q_W(F) 个坐标后，子空间才能离开无环集。在 W=0 时，这就是 (V,F) 的有向周长。该定义也涵盖重叠环和非空基 DAG。候选边不必以相同速率趋近零。对于正权重 a = (a_1, ..., a_m) ∈ R_{>0}^m，定义加权版本

τ_W(F;a) = min_{S ⊆ F : supp(W) ∪ S 是循环的} ∑_{e_s ∈ S} a_s.  (7)

沿 x_s = c_s t^{a_s} 当 t↓0 时，τ_W(F;a) 是最便宜的环补全指数。在空图上，它是加权有向周长。

###### 定义 3.2（环补全理想）。
无环候选支持集构成一个受限有向子图复形（Hultman, 2004），

Δ_{W,F} = { S ⊆ [m] : supp(W) ∪ {e_s : s ∈ S} 是无环的 }.  (8)

令 C_min(W,F) 收集其包含意义下极小的非面。其 Stanley–Reisner 理想为

I_{W,F} = ⟨ x^C : C ∈ C_min(W,F) ⟩ ⊂ R[x_1, ..., x_m],  (9)

其中 x^C = ∏_{s∈C} x_s。因此 q_W(F) 和 τ_W(F;a) 分别是 I_{W,F} 中最小普通次数和最小加权次数。当该理想非零时，称

r_W(F) = max_{C ∈ C_min(W,F)} |C|

为其 *补全宽度*。两个未加权次数可以不同：q_W(F) 控制最早的 Taylor 信号，而 r_W(F) 控制最坏的局部误差界。

###### 定理 3.3（环补全喷射理想）。
令 G_F 为式 (3)–(4) 中任一精确表示的限制，并假设 G_F 是 C^k 的。其在零点处的 k 阶 Taylor 多项式的每个分量都属于 I_{W,F}。反之，极小生成元向量

M_{W,F}(x) = (x^C)_{C ∈ C_min(W,F)}  (10)

恰好只在无环候选支持集上为零。

###### 证明。
若 supp(α) ∈ Δ_{W,F}，精确性使 G_F 在该坐标子空间上原点附近恒为零，因此 D^α G_F(0) = 0。因此每个存活的 Taylor 单项式都包含一个极小非面，并属于 I_{W,F}。生成元向量恰好当激活支持集不包含极小非面时为零，这正是 Δ_{W,F} 的成员关系。∎

## 4 带符号表示与向量表示

坐标面观察已经约束了向量表示。不需要符号或非负性假设：精确性本身就会迫使低阶 Taylor 系数消失。

###### 定理 4.1（向量环补全障碍）。
假设式 (3)，令 q = q_W(F) < ∞，并假设 H 在 W 附近是 C^{q−1} 的。则对每个满足 |α| ≤ q−1 的多重指标，

D^α H_F(0) = 0。  (11)

若 H 是 C^q 的，则对每个支持集在 F 上的 U，

‖H(W + tU)‖_2 = O(|t|^q),     ‖DH_F(tu)‖_op = O(|t|^{q−1})。  (12)

###### 证明。
考虑由 α 索引的 Taylor 系数，并令 S = supp(α)。若 |α| < q，则 |S| ≤ |α| < q，因此 S 不包含任何补环集；故 supp(α) ∈ Δ_{W,F}，坐标面参数化 h(tα) 恒为零，从而 D^α H_F(0)=0。当 |α|=q−1 时也如此。余项估计从 Taylor 定理和 H(W)=0 得出。∎

## 5 非负标量：带符号无关性与平方

来自第 3 节的理想也适用于非负约束；非负性给出一个更锐利的障碍。

###### 定理 5.1（非负阶加倍）。
设 h 为非负精确，q = q_W(F) < ∞，并假设 h 在 W 附近是 C^{2q} 的。若 h 在 W 附近是 C^{2q}，则对于每个支持集在 F 上的 U，

h(W + tU) = O(|t|^{2q})，    ∇h(W + tU) = O(|t|^{2q−1})。  (13)

更一般地，对每个满足 |α| ≤ 2q−1 的多重指标，D^α h_F(0) = 0。

###### 证明。
设 S ⊂ F 为一个最小补环集，|S| = q，并取 U = ∑_{s∈S} E_s。坐标面 t ↦ W + tU 在原点邻域内只含有环（去掉坐标）附近的全环支持集，因此沿该参数化在 t=0 附近，除了 t=0 外 h>0。由于最小补环集没有真子集是循环的，h 在 t=0 附近的每个低维面上恒为零；特别地，所有阶数低于 |S| 的导数均为零。由于 h ≥ 0 且在单变量限制中 h(0)=0，该限制的 Taylor 展开没有最低阶非零项；否则在 0 的任一邻域内都会变号。因此最低非零阶至少为 2q。所有阶数低于 2q 的偏导数沿任何方向均为零。梯度界由 Taylor 定理得出；注意 |α| = 2q−1 的导数为零，因此梯度为 O(|t|^{2q−1})。∎

- 式 (3) 的向量情形无需非负性，其第一阶数为 q。非负性使最小阶加倍，因为标量在一维中不能改变符号。由两个多项式组成的向量可以跟踪符号。
- 对于 DAGMA，h(W) = −log det(1 − W∘W) 在 W 的一个邻域上按 W∘W 展开，其首项为 tr(W∘W)。分量二次式 X 在非负约束下出现在 2 阶，而向量排序出现在 1 阶。
- 平方不改变在 DAG 边界处哪些支持集是可行的，但在 q 阶处将局部响应从 q 提升到 2q。这为低阶可行性梯度提供了第二种解释：精确性加非负性，而不是某个特定的约束公式，决定了低阶 Taylor 行为。

## 6 从局部障碍到有限尺度动力学

局部 Taylor 障碍表明，若某个可行点的候选补全数为 q，则一阶方法在低阶上没有排序信号。但有限尺度迭代可能不遵循 Taylor 展开；例如，远场项可以支配，或平滑边界层可以决定路径。本节通过在常尺度循环流形上分析精确可行性流，证明在 NOTES 和 DAGMA 域中，若不考虑分数，有限尺度优化同样无法排序。我们从典型的单环动力学开始。

### 6.1 两个变量的模型

在最简单的情形中，我们仅跟踪两条形成 2-环的候选边。分量可行性约束的结构为

h(W(z)) = φ(p),    p = ∏_{i=1}^L z_i^2,    φ(0) = 0,   φ′(0) > 0，

其中 φ 是 C^1 的，且在相关范围内 φ′ > 0。设 Ψ 是 C^1 的，在该范围内 Ψ′ > 0，且当 s↓0 时 Ψ′(s) = c s^ν(1+o(1))，其中 c > 0、ν ≥ 0。在 z ̇ = −∇_z(Ψ ∘ h) 下，将两条被跟踪边初始化为 (x_0, y_0) = (a+ε, a−ε)