【图神经网络】GCN-3（semi-GCN）

阿泽 Crz

发布于 2021-04-29 15:23:53

5220

发布于 2021-04-29 15:23:53

文章被收录于专栏：阿泽的学习笔记阿泽的学习笔记

一、Address

发表于ICLR2017的一篇论文，GNN开山之作

地址：https://arxiv.org/pdf/1609.02907.pdf

二、Introduction

本文提出了一种可扩展的图结构数据半监督学习方法，通过谱图卷积的局部一阶近似确定卷积网络结构选择。并且在引文网络和知识图数据集的大量实验中，证明了其方法有很大的优势。

考虑对图（如引文网络）中的节点（如文档）进行分类的问题，其中标签仅对一小部分节点可用。这个问题可以被定义为基于图的半监督学习，基于图的正则化形式将标签信息与图结构数据平滑的结合，通过在损失函数中使用图拉普拉斯正则化项：

\mathcal{L}=\mathcal{L}_{0}+\lambda \mathcal{L}_{\text {reg }}, \quad \text { with } \quad \mathcal{L}_{\text {reg }}=\sum_{i, j} A_{i j}\left\|f\left(X_{i}\right)-f\left(X_{j}\right)\right\|^{2}=f(X)^{\top} \Delta f(X)

其中，

\mathcal{L}_{0}

表示有标签数据的损失函数，

\mathcal{L}_{\text {reg }}

表示图结构信息的损失函数，

\lambda

是调节两者重要性的加权因子，

f()

是类似神经网络的可微分函数，

是节点节点特征向量

X_i

的矩阵，

\Delta=D-A

表示无向图

\mathcal{G}=(\mathcal{V},\mathcal{E})

的非正则化图拉普拉斯算子，

A\in R^{N\times N}

的binary或加权邻接矩阵，

D_{ii}=\sum_j A_{ij}

表示度矩阵。

在本文中，作者使用神经网络模型

f(X,A)

对图结构进行编码，并训练所有带标签的节点

\mathcal{L}_{0}

，从而避免图结构信息损失函数中的正则化。

三、Model

3.1 快速卷积近似

我们考虑具有以下分层传播规则的多层图形卷积网络（GCN）：

H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)

其中，

\tilde{A}=A+I_N

是带自环的无向图的邻接矩阵。

I_N

是单位矩阵。

\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}

。

W^{(l)}

是一个layer-specific的可训练权重矩阵。

\sigma()

是激活函数。

H^{(l)} \in R^{N \times D}

是第

层的激活矩阵，

H^{(0)}=X

接下来，我们介绍这种传播规则的形式如何可以通过图上的局部谱滤波的一阶近似推导得到。

3.2 谱图卷积

这里主要是前人工作，可以看本号图神经网络系列——GCN-1（谱图卷积）

卷积公式如下：

g_{\theta} *x \approx\sum_{k=0}^{K} \theta_{k} T_{K}(\tilde{L}) x

3.3 逐层线性模型

假设我们将逐层卷积运算限制为K=1（本文3.2节公式），即关于L的线性函数(图拉普拉斯谱上的线性函数)。这样，我们仍然可以通过叠加多个这样的层来恢复卷积的能力(k>1)，但不限于由切比雪夫多项式给出的参数。我们期望这样一个模型能够缓解具有非常宽的节点度分布（差异大）的图的局部邻域结构的过拟合问题，例如社会网络，引文网络，知识图谱和许多其他现实世界的图形数据集。此外，对于固定的计算预算，这种逐层线性模型允许我们建立更深层次的模型，这种做法可以提高许多领域的建模能力。

在GCN的线性公式中，我们进一步近似

λ_{max}≈2

，我们可以预期神经网络参数将在训练期间适应这种尺度变化。在这些近似条件下：

g_{\theta^{\prime}} \star x \approx \theta_{0}^{\prime} x+\theta_{1}^{\prime}\left(L-I_{N}\right) x=\theta_{0}^{\prime} x-\theta_{1}^{\prime} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x

上式有两个自由参数

\theta'_0

和

\theta'_1

，被图上所有节点共享。

在实际中，进一步限制参数的数量可以缓解过拟合问题并最小化每层的计算量（如矩阵乘法），于是可有以下式子：

g_{\theta} * x \approx \theta\left(I_{N}+D^{-1 / 2} A D^{-1 / 2}\right) x

只有一个参数

\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}

，注意

I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}

d的特征值范围在[0，2]。如果在深度神经网络模型中反复使用该算子会导致数值不稳定性和梯度爆炸/消失等问题。所以还有引入下面的归一化技巧：

I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}

其中

\tilde{A}=A+I_N

，

\tilde{D}_{ii}=\sum_j\tilde{A}_{ij}

。

我们可以将这一定义推广到具有C个输入通道的信号

X\in R^{N\times C}

（即每个节点的C维特征），F个滤波器或特征映射如下：

Z=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta

其中

\Theta \in \mathbb{R}^{C \times F}

是一个滤波器的参数矩阵，

Z\in R^{N\times F}

是卷积后的信号矩阵。这个滤波操作复杂度是

O(|\mathcal{E}| F C)

，因为

\tilde{A} X

可以高效地实现为稠密矩阵和稀疏矩阵的乘积。得到上式后，对比一下本文开头的公式即可对应上。

对于以上公式的理解，首先是通过度矩阵对邻接矩阵

进行归一化，也就是使得行之和为1，然后是加入自环（每个结点从自身出发，又指向自己，就是把邻接矩阵对角线上的数，全部由0变为1.），最后输入节点左乘邻接矩阵代表了节点加上了其邻居节点的特征。

3.4 半监督节点分类

使用了一个两层的GCN进行节点分类任务作为例子:

首先计算

\hat{A}=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}

，两层GCN的forward公式如下：

Z=f(X, A)=\operatorname{softmax}\left(\hat{A} \operatorname{ReLU}\left(\hat{A} X W^{(0)}\right) W^{(1)}\right)

其中

W^{(0)} \in \mathbb{R}^{C \times H}

为输入层到隐藏层的变换，

W^{(1)} \in \mathbb{R}^{H \times F}

为隐藏层到输出层的变换

对于半监督分类问题，使用所有有标签节点上的交叉熵作为损失函数：

\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{l f} \ln Z_{l f}

3.5 局限及未来工作

模型还存在的局限：（1）存储空间的需求内存需求随着数据集大小线性增长。小批量的随机梯度下降可以环节这个问题，需要考虑GCN的层数，及节点的K阶邻域必须存储在内存中。（2）不能处理有向图特征本文GCN模型只适用于无向图。但是作者在NELL数据集上实验了将有向图表示为一个无向二部图，并在原始图中添加表示边的节点，可以同时处理有向边和边特征（3）前提假设同样存在局限作者假设子环和边连的邻接结点的重要性同等，同时，作者认为对于某些数据集中引入一个权衡参数可能较有利。

作者隐式地假设局部性（依赖于具有K层的GCN的K阶邻域），自连接与相邻节点的边同等重要，然而，对于某些数据集，在Ã的定义中引入权重参数λ可能比较好：

四、Experiments

作者使用了以下数据集进行实验

其中前三个是在文献引用网络上的实验，NELL是在知识图谱上的实验

结果如下：

可以看到，基于GCN的半监督学习效果相对其他模型有较大的提高

五、Conclusion

本文采用一阶近似卷积的方式提出GCN模型，具有以下特性

局部性（以某节点为中心加上k阶邻居的信息）
一阶性，但是可以通过多层GCN叠加来获得K阶特性
参数共享,(后面会单独出一篇文章总结GCN的参数共享)

三代GCN论文阅读到这里了（前二分别为GCN-1谱图卷积，chebynet）

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除

神经网络

监督学习

本文分享自阿泽的学习笔记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

神经网络

监督学习

登录后参与评论

0 条评论

热度