|
SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS基于图卷积网络的半监督分类摘要通过谱图卷积（spectral graph convolutions） 的局部一阶近似，来确定卷积网络结构。 该模型在图的边数上线性缩放 该模型学习隐藏层表示，这些表示既编码局部图结构、也编码节点特征 通过图结构数据中部分有标签的节点数据对卷积神经网络结构模型训练，使网络模型对其余无标签的数据进行进一步分类
1 INTRODUCTION使用神经网络模型 f(X,A)f(X,A)f(X,A) 对所有带标签节点进行基于监督损失的训练。 在图的邻接矩阵上调整 f(⋅)f(\cdot)f(⋅) 将允许模型从监督损失 L0L_0L0中分配梯度信息，并使其能够学习所有节点（带标签或不带标签）的表示。 2 Graph中的快速卷积具有以下分层传播规则的多层图形卷积网络（GCN）：
H(l+1)=σ(D˜−12A˜D˜−12H(l)W(l))(1)H^{(l+1)}=\sigma(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}) \tag{1}H(l+1)=σ(D~−21A~D~−21H(l)W(l))(1)
其中： A˜=A+IN\tilde{A}=A+I_NA~=A+IN为无向图G的带自环邻接矩阵 INI_NIN为单位矩阵 D˜ii=∑jA˜ij\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}D~ii=∑jA~ij W(l)W^{(l)}W(l)为layer-specific可训练权重向量 σ(⋅)\sigma(·)σ(⋅)为激活函数，例：ReLU H(l)∈RN×DH^{(l)}\in\mathbb{R}^{N\times D}H(l)∈RN×D为第lthl^{th}lth层的激活矩阵；H(0)=XH^{(0)}=XH(0)=X
2.1 谱图卷积推荐阅读：【GCN】图卷积网络初探——基于图（Graph）的傅里叶变换和卷积 在上面这篇文章中，我们推导出基于图的卷积公式如下：
⎛⎝⎜⎜⎜⎜⎜f∗h⎞⎠⎟⎟⎟⎟⎟G=U⎛⎝⎜⎜⎜⎜⎜hˆ(λ1)⋱hˆ(λn)⎞⎠⎟⎟⎟⎟⎟UTf(f*h)_G=U\begin{pmatrix}\hat{h}(\lambda_1) & & \\& \ddots & \\& & \hat{h}(\lambda_n) \end{pmatrix}U^Tf(f∗h)G=U⎝⎛h^(λ1)⋱h^(λn)⎠⎞UTf fff为待卷积函数（比如图的特征向量） hhh为按需设计的卷积核，hˆ\hat{h}h^为卷积核的傅里叶变换 UUU为【图的拉普拉斯矩阵】的【特征向量矩阵】 λ\lambdaλ为图的拉普拉斯矩阵的特征值
之后，我们又提到了两种卷积核的设计：
第一代GCN：卷积核：diag(hˆ(λl))：diag(θl)diag(\hat{h}(\lambda_l))： diag(\theta_l)diag(h^(λl))：diag(θl)
推导出的公式如下：
youtput=σ⎛⎝⎜⎜U⎛⎝⎜⎜θ1⋱θn⎞⎠⎟⎟UTx⎞⎠⎟⎟y_{output}=\sigma\begin{pmatrix}U\begin{pmatrix}\theta_1 & & \\& \ddots & \\& & \theta_n\end{pmatrix} U^Tx\end{pmatrix}youtput=σ⎝⎛U⎝⎛θ1⋱θn⎠⎞UTx⎠⎞
第一代GCN的缺点为计算量大，因此提出第二代GCN如下
第二代GCN：卷积核：hˆ(λl)：∑Kj=0αjλjl\hat{h}(\lambda_l)：\sum_{j=0}^K \alpha_j\lambda_l^jh^(λl)：∑j=0Kαjλlj
（经过矩阵变换后的）公式如下：
youtput=σ(∑Kj=0αjLjx)y_{output}=\sigma\left(\sum_{j=0}^{K} \alpha_j L^j x\right)youtput=σ(j=0∑KαjLjx)
在这篇论文里，对上述引用中提到的这两种卷积核有着更为详细的解释。 第一种卷积回到论文中，作者在2.1节的开头首先提出：考虑如下图卷积公式：
gθ∗x=UgθUTx(2)g_{\theta}*x=Ug_{\theta}U^Tx \tag{2}gθ∗x=UgθUTx(2) 可以看到，公式(2)就是上面引用中第一代GCN所使用的卷积公式，作者在论文中也提到，这个公式的缺点在于计算太过复杂，卷积核的选取不合适，需要改进。 改进：第二种卷积作者接下来说，有人提出一种卷积核设计方法，即gθ(Λ)g_{\theta}(\Lambda)gθ(Λ)可以用切比雪夫Chebyshev多项式Tk(x)T_k(x)Tk(x)到KthK^{th}Kth的截断展开来近似。 切比雪夫多项式：
Tk(x)=2xTk−1(x)−Tk−2(x)T0(x)=1T1(x)=x(3)\begin{aligned}&T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x) \tag{3}\\&T_{0}(x)=1\\&T_{1}(x)=x\end{aligned}Tk(x)=2xTk−1(x)−Tk−2(x)T0(x)=1T1(x)=x(3) 新的卷积核：
gθ‘(Λ)≈∑Kk=0θ′kTk(Λ˜)(4)g_{\theta‘}(\Lambda)\approx\sum_{k=0}^{K} \theta'_k T_k(\tilde{\Lambda}) \tag{4}gθ‘(Λ)≈k=0∑Kθk′Tk(Λ~)(4) 基于该卷积核，得到的卷积公式如下：
gθ‘∗x=∑Kk=0θ′kTk(L˜)x(5)g_{\theta‘}*x=\sum_{k=0}^{K} \theta'_k T_k(\tilde{L})x \tag{5}gθ‘∗x=k=0∑Kθk′Tk(L~)x(5) 可以看到，公式(4)与上面引文中的第二代GCN用到的卷积公式非常相似，最终都将参数简化到了KKK个，并不再需要做特征分解，直接用拉普拉斯矩阵LLL进行变换，计算复杂性大大降低。 但本文使用了切比雪夫多项式Tk(x)T_k(x)Tk(x)，这是与上面引文中提到的第二代GCN中的卷积公式的不同点。 以上，都是前人的工作，都可以在本节开头的推荐阅读中找到详细推导和讲解。接下来是作者的改进部分。 2.2 线性模型K=1：2个参数的模型在2.1节中，我们定义了基于图的卷积公式(5)如下：
gθ′∗x=∑Kk=0θ′kTk(L˜)x(5)g_{\theta'}*x=\sum_{k=0}^{K} \theta'_k T_k(\tilde{L})x \tag{5}gθ′∗x=k=0∑Kθk′Tk(L~)x(5) 现在我们可以通过堆叠多个形式为公式(5)的卷积层来建立一个GCN模型。 首先，我们将分层卷积操作限制为K=1K=1K=1，即关于LLL是线性的，因此在拉普拉斯谱上有线性函数。 在GCN的这个线性公式中，我们进一步近似λmax≈2\lambda_{max}\approx2λmax≈2，我们可以预测到GCN的参数能够在训练中适应这一变化，此时公式(5)将简化为下式：
gθ′∗x≈θ′0x+θ′1(L−IN)x=θ′0x−θ′1D−12AD−12x(6)\begin{aligned}g_{\theta'}*x&\approx\theta'_{0}x+ \theta'_{1}(L-I_N)x\\&=\theta'_{0}x- \theta'_{1}D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x \tag{6}\end{aligned}gθ′∗x≈θ0′x+θ1′(L−IN)x=θ0′x−θ1′D−21AD−21x(6) 简化：1个参数的模型令θ=θ′0=−θ′1\theta=\theta'_{0}=-\theta'_{1}θ=θ0′=−θ1′，将两个参数化为单参数θ\thetaθ，得到卷积公式如下：
gθ′∗x≈θ(IN+D−12AD−12)x(7)g_{\theta'}*x \approx \theta(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x \tag{7}gθ′∗x≈θ(IN+D−21AD−21)x(7) 注意IN+D−12AD−12I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}IN+D−21AD−21拥有范围为[0,2][0,2][0,2]的特征值，这将会导致数值不稳定性和梯度爆炸/消失。因此我们介绍下面的归一化技巧：
IN+D−12AD−12→D˜−12A˜D˜−12I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \to \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}IN+D−21AD−21→D~−21A~D~−21 推广：特征映射公式将该定义推广到具有CCC个输入通道（即每个节点的CCC维特征向量）的信号X∈RN×CX\in\mathbb{R^{N\times C}}X∈RN×C，和FFF个滤波器，则特征映射（feature maps）如下：
Z=D˜−12A˜D˜−12XΘ(8)Z=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta \tag{8}Z=D~−21A~D~−21XΘ(8) 3 半监督节点分类我们已经有了模型f(X,A)f(X,A)f(X,A)，可以在图上有效的传播信息，现在回到半监督节点分类问题上。 我们可以通过调整我们的模型f(X,A)f(X,A)f(X,A)，来放松通常在半监督学习中所做的假设。希望模型可以在【邻接矩阵AAA中包含着（数据XXX没有表达出来的）信息】这种情况下更有用。 一个整体的多层半监督GCN模型如下图所示：
上图中，左(a)是一个GCN网络示意图，在输入层拥有CCC个输入，中间有若干隐藏层，在输出层有FFF个特征映射；图的结构（边用黑线表示）在层之间共享；标签用YiY_{i}Yi表示。
右(b)是一个两层GCN在Cora数据集上（使用了5%的标签）训练得到的隐藏层激活值的形象化表示，颜色表示文档类别。 3.1 例子考虑一个用于半监督图节点分类问题的两层GCN，邻接矩阵为AAA（二进制/加权）。 预处理操作在预处理操作中，计算Aˆ=D˜−12A˜D˜−12\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}A^=D~−21A~D~−21， 这使得我们之前的模型更加简洁：
Z=f(X,A)=softmax(Aˆ ReLU(AˆXW(0))W(1))(9)Z=f(X,A)=softmax(\hat{A}\ ReLU(\hat{A}XW^{(0)})W^{(1)}) \tag{9}Z=f(X,A)=softmax(A^ ReLU(A^XW(0))W(1))(9) W(0)∈RC×HW^{(0)}\in\mathbb{R}^{C\times H}W(0)∈RC×H为输入层-到-隐藏层的权重矩阵，该隐藏层具有HHH个特征映射 W(1)∈RH×FW^{(1)}\in\mathbb{R}^{H\times F}W(1)∈RH×F为隐藏层-到-输出层的权重矩阵 softmax激活函数：softmax(xi)=1∑iexp(xi)exp(xi)softmax(x_i)=\frac{1}{\sum_i exp(x_i)} exp(x_i)softmax(xi)=∑iexp(xi)1exp(xi)，作用在每一行上
交叉熵误差接下来，对于半监督多类别分类，我们评估所有标记标签的交叉熵误差：
L=−∑l∈YL∑Ff=1YlflnZlf(10)\mathcal{L}=-\sum_{l\in\mathcal{Y}_L}\sum_{f=1}^{F}Y_{lf}lnZ_{lf}\tag{10}L=−l∈YL∑f=1∑FYlflnZlf(10) 训练网络中的权重W(0)W^{(0)}W(0)和W(1)W^{(1)}W(1)通过梯度下降训练。 我们对每个【训练迭代】使用完整的数据集执行【批量梯度下降】，这是一个可行的选择，只要数据集适合内存。 对于AAA使用稀疏表示，即边数是线性的。 通过Dropout引入训练过程中的随机性。 我们将内存效率扩展与小批随机梯度下降留作以后的工作。 3.2 实现利用TensorFlow，基于GPU的【稀疏-密集矩阵乘法】高效实现公式(9)：
Z=f(X,A)=softmax(Aˆ ReLU(AˆXW(0))W(1))(9)Z=f(X,A)=softmax(\hat{A}\ ReLU(\hat{A}XW^{(0)})W^{(1)}) \tag{9}Z=f(X,A)=softmax(A^ ReLU(A^XW(0))W(1))(9) 5 实验引文网络：半监督文档分类 从知识图中提取的二分图：半监督实体分类
5.1 数据集
5.2 实验参数1、引文网络数据集最大200迭代期 Adam算法 学习率为0.01 停止条件：验证集loss连续十个迭代期没有下降 权重初始化方法：Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, volume 9, pp. 249–256, 2010. （按行）对输入特征向量归一化
2、随机图数据集6 结果6.1 半监督节点分类
|
