论文标题 ｜ A Graph Autoencoder Approach to Causal Structure Learning
论文来源 ｜ NeurIPS (workshop) 2019
论文链接 ｜ https://arxiv.org/abs/1911.07420
源码链接 ｜ https://github.com/huawei-noah/trustworthyAI

TL;DR

对于变量间因果图结构学习的问题，论文中基于图自编码器和梯度优化的方法来学习观测数据中的因果结构，主要可以解决非线性结构等价问题并且将其应用到向量值形式的变量因果结构预测中。实验部分在人工生成数据中验证了提出的 GAE 模型优于当前其它基于梯度优化的模型 NOTEARS 和 DAG-GNN 等，尤其是在规模较大的因果图预测问题中。此外还测试了模型效率问题，在训练过程中随着图规模增大可以达到线性时间。

Problem Description

对于如何学习变量间因果图结构的问题，当前主流方法主要可以划分为三种类型：

相比于 Constraint- /Score-based 系列的方法，Gradient-based 的方法准确性和计算效率更高，目测解释性差点但奈何图深度学习🔥啊。 因此主要介绍基于梯度优化的因果图学习发展背景。

令 DAGG\mathcal{G} 表示因果图，包含节点{X1,X2,⋯ ,Xd}\{X_1,X_2,\cdots,X_d\} 其中Xi∈RlX_i\in \mathbb{R}^l，主要考虑的问题是加性噪声模型 (ANM) 下的因果结构学习方法，假设数据生成如下所示：

Xi:=fi(Xpa(i))+Zi,i=1,2,…,dX_{i}:=f_{i}\left(X_{p a(i)}\right)+Z_{i}, i=1,2, \ldots, d

其中Xpa(i)X_{pa(i)} 表示G\mathcal{G} 中存在有向边指向变量XiX_i 的节点集合，fi:R∣Xpa(i)∣×l→Rlf_{i}: \mathbb{R}^{\left|X_{p a(i)}\right| \times l} \rightarrow \mathbb{R}^{l} 为向量映射函数，Zi∈RlZ_i\in \mathbb{R}^l 表示加性噪声并假设是独立同分布的。集合表示为X:=[X1,X2,⋯ ,Xd]X:=\left[X_{1}, X_{2}, \cdots, X_{d}\right] 和Z:=[Z1,Z2,⋯ ,Zd]Z:=\left[Z_{1}, Z_{2}, \cdots, Z_{d}\right]。

NOTEARS 首先将 score-based 系列的组合优化问题转化为的线性结构等价模型（SEM）。对于上述数据生成模型改写为

Xi=AiTX+Zi,i=1,2,…,dX_{i}=A_{i}^{T} X+Z_{i}, i=1,2, \ldots, d

假设Xi,Zi∈RX_i,Z_i\in \mathbb{R} 并且Ai∈RdA_i\in \mathbb{R}^d 表示系数向量A=[A1,A2,⋯ ,Ad]∈Rd×dA=\left[A_{1}, A_{2}, \cdots, A_{d}\right] \in \mathbb{R}^{d\times d} 表示线性 SEM 的加权邻接矩阵。为了保证因果图G\mathcal{G} 是有向无环的，需要对AA 进行限制，

tr⁡(eA⊙A)−d=0\operatorname{tr}\left(e^{A \odot A}\right)-d=0

NOTEARS 将最小平方损失函数作为优化目标函数，如下所示

min⁡A12n∑j=1n∥X(j)−ATX(j)∥F2+λ∥A∥1 subject to tr⁡(eA⊙A)−d=0\begin{aligned} \min _{A} & \frac{1}{2 n} \sum_{j=1}^{n}\left\|X^{(j)}-A^{T} X^{(j)}\right\|_{F}^{2}+\lambda\|A\|_{1} \\ \text { subject to } & \operatorname{tr}\left(e^{A \odot A}\right)-d=0 \end{aligned}

其中X(j)X^{(j)} 表示XX 的第jj 个观测值。从这定义就可以看出 NOTEARS 只能处理单值变量间的因果，而且是线性结构等价模型。这也是 GAE 所优化改进的场景。

DAG-GNN 为了将上述模型适用到非线性场景，提出了的生成式模型如下

X=g2((I−AT)−1g1(Z))X=g_{2}\left(\left(I-A^{T}\right)^{-1} g_{1}(Z)\right)

其中g1,g2g_1, g_2 表示非线性函数，DAG-GNN 用到的是 MLP + GNN 方法；ZZ 作为隐变量而且维度可以小于变量数量dd。模型设计细节可以参考我另一篇文章 DAG-GNN：基于图神经网络的有向无环图结构表示学习

以上简单介绍了因果图挖掘的背景知识，也是个初学者的综述性介绍，下面进入这篇文章的正文。

Algorithm/Model

这篇论文主要是基于 NOTEARS 方法进行改进，从而使其适用更多场景。主要模型架构如下所示

模型架构

改进主要包括两部分：非线性因果学习和向量形式变量可用而不仅是标量数据。

对于 NOTEARS 优化的目标函数可以改写为

min⁡A,Θ12n∑j=1n∥X(j)−f(X(j),A)∥F2+λ∥A∥1 subject to tr⁡(eA⊙A)−d=0\begin{aligned} \min _{A, \Theta} & \frac{1}{2 n} \sum_{j=1}^{n}\left\|X^{(j)}-f\left(X^{(j)}, A\right)\right\|_{F}^{2}+\lambda\|A\|_{1} \\ \text { subject to } & \operatorname{tr}\left(e^{A \odot A}\right)-d=0 \end{aligned}

其中f(X(j),A)f\left(X^{(j)}, A\right) 表示数据生成模型，对于 NOTEARS 就是线性 SEM 即f(X(j),A)=ATX(j)f\left(X^{(j)}, A\right)=A^{T} X^{(j)}

为了将ff 扩展为非线性的，可以自定义一个非线性的关系映射，例如文章用到

f(X(j),A)=ATg1(X(j))f\left(X^{(j)}, A\right)=A^{T} g_{1}\left(X^{(j)}\right)

其中g1:Rl→Rlg_1: \mathbb{R}^l\rightarrow \mathbb{R}^l 为非线性函数可选为 MLP，和 DAG-GNN 想法类似。为了增强非线性就再加一层 MLPg2:Rl→Rlg_2: \mathbb{R}^l\rightarrow \mathbb{R}^l

f(X(j),A)=g2(ATg1(X(j)))f\left(X^{(j)}, A\right)=g_{2}\left(A^{T} g_{1}\left(X^{(j)}\right)\right)

上面的公式一看，不就和 GAE 的计算形式差不多，重写一遍

H(j)=g1(X(j))H(j)′=ATH(j)f(X(j),A)=g2(H(j)′)\begin{aligned} H^{(j)} &=g_{1}\left(X^{(j)}\right) \\ H^{(j) \prime} &=A^{T} H^{(j)} \\ f\left(X^{(j)}, A\right) &=g_{2}\left(H^{(j) \prime}\right) \end{aligned}

如果g1g_1 和g2g_2 分别表示 variable-wise 编码器和解码器，上面的计算形式和优化目标函数不就是基于重构误差训练的 GAE，GAE 不就可以处理 vector-valued 的变量了么 👏

论文中选择两个 variable-wised MLPsg1:Rl→Rl′g_1: \mathbb{R}^l\rightarrow \mathbb{R}^{l^{'}} 和g2:Rl→Rl′g_2: \mathbb{R}^l\rightarrow \mathbb{R}^{l^{'}} 其中l′l^{'} 表示隐藏层维度。最终的优化函数即为

min⁡A,Θ1,Θ212n∑j=1n∥X(j)−X^(j)∥F2+λ∥A∥1 subject to tr⁡(eA⊙A)−d=0\begin{aligned} \min _{A, \Theta_{1}, \Theta_{2}} & \frac{1}{2 n} \sum_{j=1}^{n}\left\|X^{(j)}-\hat{X}^{(j)}\right\|_{F}^{2}+\lambda\|A\|_{1} \\ \text { subject to } & \operatorname{tr}\left(e^{A \odot A}\right)-d=0 \end{aligned}

和 DAG-GNN 主要的不同点在于：论文中用的 GAE 是以Xpa(i)X_{pa(i)} 作为输入，而 DAG-GNN 是生成式模型以噪声数据ZZ 作为输入。

个人感觉就是 GAE 和 VGAE 的区别，GAE PK VGAE 怎么说好呢？作者只能在实验中证明了 GAE 比 VGAE 效果好而且快。🤔

对于上述优化函数，作者采用了增广的拉格朗日乘子法进行求解，其形式如下

Lρ(A,Θ1,Θ2,α)=12n∑j=1n∥X(j)−X^(j)∥F2+λ∥A∥1+αh(A)+ρ2∣h(A)∣2L_{\rho}\left(A, \Theta_{1}, \Theta_{2}, \alpha\right)=\frac{1}{2 n} \sum_{j=1}^{n}\left\|X^{(j)}-\hat{X}^{(j)}\right\|_{F}^{2}+\lambda\|A\|_{1}+\alpha h(A)+\frac{\rho}{2}|h(A)|^{2}

其中h(A):=tr⁡(eA⊙A)−dh(A):=\operatorname{tr}\left(e^{A \odot A}\right)-d ，α\alpha 表示拉格朗日乘子，ρ>0\rho>0 表示惩罚因子，因此对应的梯度更新规则如下

Ak+1,Θ1k+1,Θ2k+1=arg⁡min⁡A,Θ1,Θ2Lρk(A,Θ1,Θ2,αk)αk+1=αk+ρkh(Ak+1)ρk+1={βρk, if ∣h(Ak+1)∣≥γ∣h(Ak)∣ρk, otherwise \begin{aligned} A^{k+1}, \Theta_{1}^{k+1}, \Theta_{2}^{k+1} &=\underset{A, \Theta_{1}, \Theta_{2}}{\arg \min } L_{\rho^{k}}\left(A, \Theta_{1}, \Theta_{2}, \alpha^{k}\right) \\ \alpha^{k+1} &=\alpha^{k}+\rho^{k} h\left(A^{k+1}\right) \\ \rho^{k+1} &=\left\{\begin{array}{ll} \beta \rho^{k}, & \text { if }\left|h\left(A^{k+1}\right)\right| \geq \gamma\left|h\left(A^{k}\right)\right| \\ \rho^{k}, & \text { otherwise } \end{array}\right. \end{aligned}

其中 $\beta >1 $ 而且γ<1\gamma<1 表示可调的超参数。

Experiments

实验部分在人工数据集中对比 baselines NOTEARS 和 DAG-GNN。数据包括两种 Scalar-based 和 Vector-Valued。

采用的指标包括两种结构化汉明距离（SHD）和正阳率 (TPR)。实验结果如下所示

实验结果 实验结果

整体而言性能提升蛮大的，而且模型训练实验也比较短。

实验结果

Thoughts

介绍因果图挖掘的初衷是：了解如何用深度学习的方法挖掘变量间的因果图，而不要局限在 PC 或者 kNN 的思路上。

尤其是之前介绍的多变量时间序列关联挖掘，时间序列变量间存在因果关系但之前使用的因果挖掘方法却过于简单粗暴。

图作为一种广义的数据结构，任何存在某种关联的数据都可以使用当前🔥的图机器学习进行建模。目前很多任务都是已知图结构，对于未知图结构的实体就需要使用模型学习到其中关系或者因果，这往往是一个更有挑战的任务。

  1. David M Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507–554, March 2003. ↩︎

  2. Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. DAGs with NO TEARS: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems 31, 2018. ↩︎