《CGNF: CONDITIONAL GRAPH NEURAL FIELDS》阅读笔记

一.文章概述

在大多数GNNs中，并没有考虑节点标签间的依赖性。为此，作者将条件随机场（Conditional Random Fields, CRF）和图卷积网络整合在一起提出了CGNF（Conditional Graph Neural Network），该模型显式地建模了整个节点标签集的联合概率，从而在节点标签预测任务中能够利用邻域标签信息。

二.背景知识

2.1 图卷积网络

GCN中图卷积层的数学形式如下：
$${\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{D}}}^{-\frac{1}{2}}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-\frac{1}{2}}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$
其中 $\tilde{A}=\mathbf{A}+\mathbf{I}$表示添加了自环的邻接矩阵，$\tilde{D}$是$\tilde{A}$对应的度矩阵（对角阵），${\mathbf{H}}^{(l)}$表示第$l$层的节点表示，${\mathbf{W}}^{(l)}$表示第$l$层的权重矩阵，$\sigma$表示激活函数，常用的为ReLU。

2.2 条件随机场

条件随机场（CRF）是一种无向概率图模型，通常用于结构预测任务。给定输入特征$x\in {\mathbb{R}}^d$，CRF旨在找到最大化条件概率 $P(\mathbf{y}\mid \mathbf{x})$的标签集$\mathbf{y}$。在无向图上，CRF计算联合概率分布的方式是因子分解，即：
$$P(\mathbf{y}\mid \mathbf{x})=\frac{1}{Z(\mathbf{x})}\prod _c{\Phi }_a\left({\mathbf{x}}_c,{\mathbf{y}}_c\right)$$
其中$c$表示图中的团，${\mathbf{x}}_c$表示团$c$中所有顶点对应的特征，${\Phi }_c$表示势函数，$Z(\mathbf{x})={\sum }_{{\mathbf{y}}_c^{\prime }}{\prod }_c{\Phi }_a\left({\mathbf{x}}_c,{\mathbf{y}}_c^{\prime }\right)$表示归一化因子（用来保证计算出的概率值是合法的）。

团指的是所有顶点都有边连接的子图。

三.CGNF详细介绍

首先给出符号表以方便后续介绍：

3.1 训练

CGNF的第一步是将输入图$G=\{\mathbf{X},\mathbf{Y},\mathbf{A}\}$过一下Kipf和Welling提出来的2层GCN模型，即：
$$\mathbf{H}=f(\mathbf{X},\mathbf{A})=\mathrm{Softmax}\left(\hat{\mathbf{A}}\mathrm{ReLu}\left(\hat{\mathbf{A}}\mathbf{X}{\mathbf{W}}^0\right){\mathbf{W}}^1\right)$$
随后，作者考虑节点特征和标签依赖性的影响，定义能量函数（energy function）如下：
$$E(\mathbf{Y},\mathbf{X},\mathbf{A})=E_c\left({\mathbf{Y}}_c,{\mathbf{X}}_c,\mathbf{A}\right)=\sum _i\psi \left({\mathbf{y}}_i,{\mathbf{x}}_i\right)+\gamma \sum _{(i,j)\in \mathcal{E},i<j}\varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,A_{i,j}\right)$$
其中$c$表示团，$\mathcal{E}$表示边集，$\psi (\cdot )$为一元势函数（用来策略观测节点$x_i$与标签$y_i$间的相容性compatibility，即观测值为$x_i$时属于$y_i$类的概率），成对势函数$\varphi (\cdot )$ 用于捕捉标签相关性。基于该能量函数，可以导出Gibbs分布：
$$P(\mathbf{Y}\mid \mathbf{X},\mathbf{A})=\frac{\exp (-E(\mathbf{Y},\mathbf{X},\mathbf{A}))}{{\sum }_{{\mathbf{Y}}^{\prime }\in \mathcal{Y}}\exp \left(-E\left({\mathbf{Y}}^{\prime },\mathbf{X},\mathbf{A}\right)\right)}=\frac{\exp (-E(\mathbf{Y},\mathbf{X},\mathbf{A}))}{Z(\mathbf{X},\mathbf{A})}$$
作者的目标便是最大化该条件概率，即：
$$\begin{array}{rl}E(\mathbf{Y},\mathbf{X},\mathbf{A})& =\sum _i\psi \left({\mathbf{y}}_i,{\mathbf{h}}_{\mathbf{i}}\right)+\gamma \sum _{(i,j)\in \mathcal{E},i<j}\varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)\\ & =\sum _i\left(\psi \left({\mathbf{y}}_i,{\mathbf{h}}_i\right)+\frac{\gamma }{2}\sum _{j\in N(i)}\varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)\right)\end{array}$$
其中$h_i$是通过2层GCN模型获取到的节点表示，${\hat{A}}_{i,j}$是正则化后的邻接矩阵中的原始,$N(i)$是节点$i$的邻域。两个势函数的计算公式如下：
$$\begin{array}{rl}\psi \left({\mathbf{y}}_i,{\mathbf{h}}_i\right)& =-\log p\left({\mathbf{y}}_i\mid {\mathbf{h}}_i\right)=-\sum _k{y}_{i,k}\log h_{i,k}\\ \varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)& =-2{\hat{A}}_{i,j}{U}_{y_i,y_j}\end{array}$$
从上述公式可以看出$\psi \left({\mathbf{y}}_i,{\mathbf{h}}_i\right)$实际就是交叉熵，$U_{y_i,y_j}\in \mathbf{U}$ 是标签$y_i$和$y_j$之间可学习的相关性权重。采用类似传统CRF的做法，作者使用负对数似然来作为训练的目标函数：
$$\begin{array}{rl}-\log P(\mathbf{Y}\mid \mathbf{X},\mathbf{A})& =E(\mathbf{Y},\mathbf{X},\mathbf{A})+\log Z(\mathbf{X},\mathbf{A})\\ & =E(\mathbf{Y},\mathbf{X},\mathbf{A})+\log \sum _{{\mathbf{Y}}^{\prime }}\exp \left(-E\left({\mathbf{Y}}^{\prime },\mathbf{X},\mathbf{A}\right)\right)\end{array}$$
在推断（inference）的时候，只需${\min }_{\mathbf{Y}}E(\mathbf{Y},\mathbf{X},\mathbf{A})$即可。但比上述训练目标优化比较困难，为此作者采用伪似然来对其进行近似：
$$P(\mathbf{Y}\mid \mathbf{X},\mathbf{A})\approx PL(\mathbf{Y}\mid \mathbf{X},\mathbf{A})=\prod _{i}P\left({\mathbf{y}}_i\mid {\mathbf{y}}_{N(i)},\mathbf{X},\mathbf{A}\right)$$
其中：
$$\begin{array}{rl}P\left({\mathbf{y}}_i\mid {\mathbf{y}}_{N(i)},\mathbf{X},\mathbf{A}\right)& =\frac{\exp (-\psi \left({\mathbf{y}}_i,{\mathbf{h}}_{\mathbf{i}}\right)-\gamma {\sum }_{j\in N(i)}\varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)}{{\sum }_{{\mathbf{y}}_i^{\prime }}(\exp \left(-\psi \left({\mathbf{y}}_i^{\prime },{\mathbf{h}}_{\mathbf{i}}\right)-\gamma {\sum }_{j\in N(i)}\varphi \left({\mathbf{y}}_i^{\prime },{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)\right)}\\ & =\frac{\exp (-\log p\left({\mathbf{y}}_i\mid {\mathbf{h}}_{\mathbf{i}}\right)-2\gamma {\sum }_{j\in N(i)}{\hat{A}}_{i,j}{U}_{y_i,y_j}}{{\sum }_{{\mathbf{y}}_i^{\prime }}(\exp \left(-\log p\left({\mathbf{y}}_i^{\prime }\mid {\mathbf{h}}_{\mathbf{i}}\right)-2\gamma {\sum }_{j\in N(i)}{\hat{A}}_{i,j}{U}_{y_i^{\prime },y_j}\right)}\end{array}$$
${\mathbf{y}}_i^{\prime }$是节点${\mathbf{x}}_i$的所有可能标签。因此，新的训练目标为：
$$\begin{array}{rl}& -\log PL(\mathbf{Y}\mid \mathbf{X},\mathbf{A})=\sum _i-\log P\left({\mathbf{y}}_i\mid {\mathbf{y}}_{N(i)},\mathbf{X},\mathbf{A}\right)=\\ & \sum _i(\psi \left({\mathbf{y}}_i,{\mathbf{h}}_i\right)+\gamma \sum _{j\in N(i)}\varphi \left({\mathbf{y}}_i,{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)+\log \sum _{{\mathbf{y}}_i^{\prime }}\left(\exp \left(-\psi \left({\mathbf{y}}_i^{\prime },{\mathbf{h}}_{\mathbf{i}}\right)-\gamma \sum _{j\in N(i)}\varphi \left({\mathbf{y}}_i^{\prime },{\mathbf{y}}_j,{\hat{A}}_{i,j}\right)\right)\right)\\ & =-\sum _{i,k}(\mathbf{Y}\odot \log \mathbf{H}{)}_{i,k}-2\gamma \sum _{i,j,i\ne j}{\left(\hat{\mathbf{A}}\odot \left(\mathbf{Y}\mathbf{U}{\mathbf{Y}}^T\right)\right)}_{i,j}+\sum _i\log \sum _k(\mathbf{H}\odot \exp (2\gamma \hat{\mathbf{A}}\mathbf{Y}\mathbf{U}){)}_{i,k}\end{array}$$
$\odot$ 表示逐元素乘法。

3.2 推断

如前文介绍的，在推断的时候仅需优化如下目标：
$$\underset{{\hat{\mathbf{Y}}}_{te}}{\min }E\left({\hat{\mathbf{Y}}}_{te},\mathbf{X},\mathbf{A},{\mathbf{Y}}_{tr}\right)=\underset{{\hat{\mathbf{Y}}}_{te}}{\min }\left[-\log p\left({\hat{\mathbf{Y}}}_{te}\mid \mathbf{H}\right)-\gamma \sum _{i\ne j}{\left(\hat{\mathbf{A}}\odot \left(\hat{\mathbf{Y}}\mathbf{U}{\hat{\mathbf{Y}}}^T\right)\right)}_{i,j}\right]$$
其中$\hat{\mathbf{Y}}=$ concatenate $\left({\mathbf{Y}}_{tr},{\hat{\mathbf{Y}}}_{te}\right)$。作者在论文中提到了两种推断方法。

3.2.1 推断方法一

最简单的推断方法是不考虑标签间的相关性，即：
$$y_i=\underset{y_j}{\mathrm{argmin}}E\left({\mathbf{y}}_i,{\mathbf{Y}}_{tr},\mathbf{X},\mathbf{A}\right)=\underset{j}{\mathrm{argmin}}{\left[-\log \left({\mathbf{h}}_i\right)-2\gamma {\hat{\mathbf{A}}}_{tr}\mathbf{Y}{\mathbf{U}}^T\right]}_j$$

3.2.2 推断方法二

第二种方案是使用动态规划方法来寻找最优值。该方法会随机选择一个测试节点作为开始，并随机排序其它测试节点，然后沿着排序测试节点的顺序进行beam search（beam大小为$K$，即每次可以得到$K$个最佳集）。将该过程重复$T$词，然后选择所有搜索结果中的最佳结果，算法总结如下：

四.实验

作者在Cora、Pubmed、Citeseer和PPI四个数据集上进行实验，且较其它baseline取得了比较好的性能，对应结果如下：

结语

参考资料：

• 理解条件随机场
• CRF条件随机场