第三代图卷积网络：使用图卷积网络进行半监督分类

论文标题：Semi-Supervised Classification with Graph Convolutional Networks
论文链接：https://arxiv.org/abs/1609.02907
论文来源：ICLR 2017

之前的文章：
①傅里叶级数与傅里叶变换
②图神经网络中的谱图理论基础
③第一代图卷积网络：图的频域网络与深度局部连接网络
④第二代图卷积网络：应用快速局部谱卷积的图卷积网络

一、概述

考虑分类图中节点这样一个问题，每个节点可以是一篇文章，那么图可以代表引用关系，并且只有一部分节点有标签。这样的问题就是一个基于图的半监督学习问题。解决这个问题的一种方法是为损失函数添加一个基于图的正则项，比如采用图的拉普拉斯矩阵正则项：

$L=L_{0}+\lambda L_{reg}\\ 其中L_{reg}=\sum _{i,j}A_{ij}||f(X_{i})-f(X_{j})||^{2}=f(X)^{T}\Delta f(X)$

这里的 $L_{0}$ 代表监督损失，也就是图中有标签的那些节点的损失， $f(\cdot )$ 可以是一个神经网络， $\lambda$ 是一个权衡因子， $X$ 是一个包含所有节点特征向量 $X_i$ 的矩阵， $A$ 代表邻接矩阵， $\Delta=D-A$ 代表未标准化的拉普拉斯矩阵。另外 $G=(V,E)$ 代表要处理的无向图，有 $N$ 个节点， $v_i\in V$ ， $(v_i,v_j)\in E$ ，它的邻接矩阵用 $A\in \mathbb{R}^{N\times N}$ 来表示， $A$ 可以是binary的也可以是weighted的，度矩阵 $D_{ii}=\sum _{j}A_{ij}$ 。

上式之所以能够采用这样的损失函数是基于这样的假设：在图中相邻的节点更倾向于拥有相同的标签。然而这个假设可能会限制模型的容量，因为图的边不一定需要编码节点相似度，但可能包含额外的信息。

本文所采用的的方法设计了神经网络模型 $f(X,A)$ （ $X$ 和 $A$ 作为神经网络的输入），并且在所有有标签节点的监督损失 $L_0$ 进行训练，避免了使用前述正则项。这种将 $A$ 作为 $f(\cdot )$ 的输入条件的方法可以从监督损失 $L_0$ 中分配梯度信息并且能够让模型学习所有节点的表示（无论有无标签）。

本文主要内容包括三部分：
①网络的架构，也就是设计的卷积层是如何前向传播的，以及它如何从前两代GCN中获得启发并对其进行改进；
②如何利用设计的GCN解决前述半监督问题；
③通过实验来证明本文设计的模型是有效且高效的。

二、图上的快速近似卷积

在本文中所设计的GCN的卷积层结构如下：

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

这里 $\tilde{A}=A+I_{N}$ ，是邻接矩阵与自连接的加和， $\tilde{D}_{ii}=\sum _{j}\tilde{A}_{ij}$ ， $W^{(l)}$ 是第 $l$ 层的训练参数， $\sigma (\cdot )$ 是激活函数，比如 $ReLU(\cdot )=max(0,\cdot )$ ， $H^{(l)}\in \mathbb{R}^{N\times D}$ 是每一层的数据的特征矩阵， $H^{(0)}=X$ 。

谱卷积核

这一部分介绍上述设计的卷积层是如何从第二代GCN演化而来的。第一代GCN定义图信号 $x\in \mathbb{R}^{N}$ 上的卷积核 $g_{\theta }=diag(\theta )$ ，这里 $\theta \in \mathbb{R}^{N}$ 是参数向量，定义的卷积过程如下：

$g_{\theta }\star x=Ug_{\theta }U^{T}x$

这里 $U$ 是标准化的拉普拉斯矩阵 $L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{T}$ 的特征向量矩阵， $\Lambda$ 是特征值的对角矩阵， $U^{T}x$ 相当于对 $x$ 进行傅里叶变换， $g_{\theta }$ 可以看做是特征值的函数 $g_{\theta }(\Lambda )$ 。上式由于需要与 $U$ 进行相乘，因此计算上是昂贵的（ $O(N^2)$ ），另外计算 $L$ 的特征分解也需要消耗一定的计算资源，尤其对于大规模的图来说计算上也是相当昂贵的。为了解决上述问题，于是有了第二代GCN，其中 $g_{\theta }(\Lambda )$ 被使用 $K$ 阶切比雪夫多项式来逼近：

$g_{\theta ^{'}}(\Lambda )\approx \sum_{k=0}^{K}\theta _{k}^{'}T_{k}(\tilde{\Lambda })$

其中 $\tilde{\Lambda }=2\Lambda /\lambda _{max}-I_{N}$ ， $\lambda _{max}$ 代表最大的特征值， $\theta ^{'}\in \mathbb{R}^{K}$ 现在是切比雪夫多项式的系数向量。利用这种卷积核的卷积过程就可以表示为：

$g_{\theta ^{'}}\star x=\sum_{k=0}^{K}\theta _{k}^{'}T_{k}(\tilde{L})x$

这里 $\tilde{L}=2L/\lambda _{max}-I_{N}$ 。这样的卷积核是K-localized的，复杂度为 $O(|E|)$ ，也就是与边的数量成线性关系。

第三代谱卷积核

上面介绍了前两代谱卷积核，本节介绍如何由第二代谱卷积核进行改进从而得到本文所设计的第三代谱卷积核。对于第二代卷积核，首先我们设置 $K=1$ ，那么现在有：

$\sum_{k=0}^{K}\theta _{k}^{'}T_{k}(\tilde{L})=\sum_{k=0}^{1}\theta _{k}^{'}T_{k}(\tilde{L})\\ =\theta _{0}^{'}T_{0}(\tilde{L})+\theta _{1}^{'}T_{1}(\tilde{L})\\ =\theta _{0}^{'}+\theta _{1}^{'}\tilde{L}\\ =\theta _{0}^{'}+\theta _{1}^{'}(2L/\lambda _{max}-I_{N})$

上式和 $L$ 成线性关系。即使将 $K$ 设置成 $1$ ，也仍然可以通过堆叠多层来使得模型具备足够的容量和复杂度，而且本文认为这样设置还可以缓解社交网络、引文网络、知识图谱或者其他真实世界的这种大规模图的局部邻域的过拟合问题。另外，这样的设计也能够允许我们构建更深的深度网络。

接着，本文近似使用 $\lambda _{max}\approx 2$ ，本文认为在训练过程中神经网络可以适应这种假设，那么现在，卷积的过程就变成：

$g_{\theta ^{'}}\star x\approx \sum_{k=0}^{1}\theta _{k}^{'}T_{k}(\tilde{L})x\\ =[\theta _{0}^{'}+\theta _{1}^{'}(2L/\lambda _{max}-I_{N})]x\\ =[\theta _{0}^{'}+\theta _{1}^{'}(L-I_{N})]x\\ =\theta _{0}^{'}x-\theta _{1}^{'}D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x$

一共有两个参数 $\theta _{0}^{'}$ 和 $\theta _{1}^{'}$ 。连续应用这种卷积层也可以达到卷积图的 $K$ 阶邻域的效果，这是由于每次卷积 $1$ 阶邻域内的节点信息都会流向当前节点，这里的 $K$ 代表连续的卷积操作数或者卷积的层数。

接下来进一步限制参数的数量以解决过拟合和最小化每层的操作(如矩阵乘法)的数量，具体的，限制 $\theta =\theta _{0}^{'}=-\theta _{1}^{'}$ ，现在卷积的过程就变成：

$g_{\theta}\star x\approx \theta (I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$

现在 $I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 的特征值在 $[0, 2]$ 之间。在深度神经网络中重复应用上述过程会造成数值不稳定以及梯度爆炸或梯度消失，为了缓解这个问题，本文采用再标准化（renormalization）技巧：

$I_{N}+D^{-\frac{1}{2}}AD^{-\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}$ 。

上述卷积过程的一种泛化的表达形式如下，信号 $X\in \mathbb{R}^{N \times C}$ ，有 $C$ 个channel，也就是说每个节点用 $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 \mathbb{R}^{N \times F}$ 是卷积后的信号矩阵。这样的卷积操作的复杂度为 $O(|E|FC)$ ，由于 $\tilde{A} X$ 作为一个稀疏矩阵乘以一个稠密矩阵可以被高效地实现。

三、半监督节点分类

正如之前所说的，对于半监督分类问题，由于我们将数据 $X$ 和邻接矩阵 $A$ 同时作为模型 $f(X,A)$ 的输入条件，因而我们可以放宽某些典型的基于图的半监督学习的假设。我们期待这种方法在邻接矩阵包含 $X$ 中没有的信息时能够是powerful的，解释一下这一点就是说传统的基于图的半监督学习（正如开篇介绍的）要求图的邻接矩阵表征节点的相似度，而节点的相似度信息是利用 $X$ 计算得到的，也就是说 $X$ 本身就包含相似度信息，这就造成了重复和浪费，而使用本文的模型后，邻接矩阵就可以用来表征一些其他信息（比如文章的引用关系或者知识图谱中的关系），相当于将邻接矩阵解放了出来。

对于模型的具体架构，使用一个两个卷积层的神经网络作为例子。在预处理阶段首先计算 $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ ，然后模型架构可以表示为：

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

注意没有池化层。这里 $W^{(0)} \in \mathbb{R}^{C\times H}$ 是input-to-hidden权重矩阵（隐层有 $H$ 个feature map）， $W^{(1)}\in \mathbb{R}^{H\times F}$ 是hidden-to-output权重矩阵。 $softmax$ 函数计算为：

$softmax(x_{i})=\frac{1}{\mathbb{Z}}exp(x_{i})\; with\; \mathbb{Z}=\sum _{i}exp(x_{i})$

softmax函数被应用到矩阵的每一行。损失函数采用所有有标签节点的交叉熵损失：

$loss=-\sum _{l\in \Phi }\sum _{f=1}^{F}Y_{lf}lnZ_{lf}$

$\Phi$ 代表有标签节点的集合。整个模型架构如下图所示：

架构图

在实验中采用batch gradient descent对整个数据集进行迭代。对于稀疏矩阵 $A$ ，需要的内存复杂度为 $O(|E|)$ 。随机性通过dropout引入。对于mini-batch stochastic gradient descent的方法需要后续进行研究。

四、实验

实验数据集信息如下：

数据集信息

实验结果如下：

实验结果

具体实验设置请参照原文。

多种架构对比：

多种架构对比

训练时间与图边数的关系：

训练时间与图边数的关系

五、模型的局限性

内存的需求

采用batch gradient descent，内存需求与图边数成线性关系。而如果采用mini-batch，则需要考虑模型的层数，因为模型的层数代表了卷积的感受野，对于非常大且稠密连接的图，可能需要更进一步的近似。

有向图和边的特征

本文提出的模型只适用于无向图模型。不过NELL数据集的结果表明，通过将原始有向图表示为无向二部图，并使用额外的节点表示原始图中的边，可以同时处理有向边和边的特征。

有限的假设

前述模型的定义有两个假设：
①局部性假设，也就是 $K$ 层对应 $K$ 阶邻域的假设；
②自连接与相邻节点的边等同重要性，也就是 $\tilde{A}=A+I_{N}$

对于一些数据集，最好引入一个权衡参数：

$\tilde{A}=A+\lambda I_{N}$

这个权衡参数可以被学习。

最后编辑于：2024.06.20 11:49:41

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,589评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,615评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,933评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,976评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,999评论 6赞 393
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,775评论 1赞 307
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,474评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,359评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,854评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,007评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,146评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,826评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,484评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,029评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,153评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,420评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,107评论 2赞 356