Exploiting Non-Negativity in DAG Structure Learning

技术摘要：利用非负性进行有向无环图结构学习

问题陈述
本文解决了从线性结构方程模型（SEM）生成的节点观测数据中学习有向无环图（DAG）的挑战。虽然 DAG 学习是因果推断和网络拓扑推断的基础，但由于无环性是一种全局组合性质，该问题在计算上十分困难。现有的连续方法（如 NOTEARS 和 DAGMA）将离散的无环性约束替换为平滑的等式约束（例如，基于矩阵指数或 Hadamard 积的对数行列式）。然而，这些公式存在非凸优化景观和退化的一阶最优性条件。具体而言，标准无环性函数在可行 DAG 处的梯度消失，导致 Karush–Kuhn–Tucker (KKT) 条件退化，使得可行解与得分函数的无约束驻点无法区分。

方法论
作者提出了一种互补方法，将注意力限制在具有非负边权重的 DAG 上。这一假设在涉及兴奋性或加性相互作用的场景中是自然的，它消除了矩阵幂中的符号抵消，从而允许对无环性进行更简单的刻画。

1. 非负无环性刻画：
   作者不使用 Hadamard 积（$W \circ W$），而是直接在邻接矩阵 $W \in \mathbb{R}^{d \times d}_+$ 上定义无环性约束。他们利用函数：
   $$h(W) = d \log(s) - \log \det(sI - W)$$
   其中 $s$ 是确保谱半径 $\rho(W) < s$ 的标量。

   • 关键性质： 对于非负矩阵，$h(W) = 0$ 当且仅当 $W$ 代表一个 DAG。
   • 优势： 与基于 Hadamard 的约束不同，梯度 $\nabla h(W) = (sI - W)^{-\top}$ 在可行 DAG 处不会消失。这防止了 KKT 条件的退化，确保可行的无环矩阵不会自动成为仅由约束产生的驻点。

2. 优化公式：
   学习问题被表述为带有对数行列式无环性约束和非负性约束的正则化最小二乘估计量：
   $$\min_{W \ge 0} \frac{1}{2n}\|X - W^\top X\|_F^2 + \alpha_n \sum_{i \neq j} W_{ij} \quad \text{s.t.} \quad h(W) = 0, \rho(W) < s$$
   作者使用乘子法（增广拉格朗日法）求解该问题。该算法通过投影梯度下降（投影到非负象限）迭代更新邻接矩阵，并基于约束违反情况更新拉格朗日乘子。

主要贡献

• 简化的无环性约束： 本文证明，在非负性条件下，无环性可以通过一个平滑函数来刻画，该函数避免了 Hadamard 积，从而规避了现有连续公式中存在的梯度消失问题。
• 算法提议： 作者引入了 NOMAD（用于无环有向图的非负乘子优化），这是一种专为非负 DAG 学习定制的增广拉格朗日算法。
• 总体景观分析： 本文对总体层面的优化景观提供了严格的理论分析。在标准可识别性假设下，并配合特定的乘子设置（$\lambda \ge 2$），他们证明了：
  1. 真实 DAG 是总体增广拉格朗日函数的唯一全局极小值点。
  2. 不存在虚假的内部驻点（如果 $\lambda > 2$，则不存在任何驻点；如果 $\lambda = 2$，则唯一的驻点是真实 DAG）。
  3. 唯一的无环 KKT 点是真实 DAG。
• 实证验证： 在合成数据和真实世界的 Sachs 蛋白信号基准上的大量数值实验表明，所提出的方法在加权估计误差和结构恢复（SHD）方面均优于最先进的连续基线方法（NOTEARS、DAGMA、CoLiDE），特别是在样本量增加的情况下。

结果与意义
本文声称，利用非负性将 DAG 学习转化为一个“条件显著更好的优化问题”。理论结果表明，所提出的公式避免了现有方法中存在的局部极小值和退化驻点。在总体机制下，景观是“良性”的，真实 DAG 是唯一解。

在有限样本机制下，数值结果表明，随着观测数量的增加，所提出方法的估计误差一致下降，而某些基线方法则表现出饱和现象。在 Sachs 蛋白信号基准上，该方法实现了最低的结构汉明距离（SHD）和误报率（FDR），恢复了一个与生物学知识一致的稀疏图，且未引入虚假边。

这项工作的意义在于表明，纳入有意义的符号信息（非负性）不仅仅是一个建模先验，更是一种结构性的赋能因素，它简化了无环性约束，改善了优化景观，并在已知相互作用为非抑制性的应用中导致了更稳健和准确的因果发现。