GCN

GCN：图卷积网络

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS：基于图卷积网络的半监督分类

任务

在图结构数据中，一部节点已知标签，剩下的节点标签未知，使用已知标签的节点训练卷积神经网络，使用网络模型对无标签的节点进行分类。

方法（模型）

提出了一种可扩展的基于图结构数据的半监督分类方法。
分层传播规则：通过谱图卷积（spectral graph convolutions）的局部一阶近似，来确定卷积网络结构。

f ( X , A ) f(X,A) f(X,A)

使用神经网络 f ( X , A ) f(X,A) f(X,A)对图的结构进行编码，对所有带标签的节点进行有监督训练。
避免显式地对基于图的损失函数进行正则化计算
在图的邻接矩阵上调节 f ( ⋅ ) f (⋅) f(⋅) ，允许模型从监督损失 L 0 \mathcal{L}_{0} L0中分开梯度信息，使其能够学习所有节点的表示。
X：输入数据

A：图邻接矩阵

FAST APPROXIMATE CONVOLUTIONS ON GRAPHS

图卷积的前向传播公式：

H ( l + 1 ) = σ ( D ~ 1 2 A ~ D ~ − 1 2 H ( l ) W ( l ) ) H^{(l+1)}=σ(\tilde D^{\frac{1}{2}}\tilde A \tilde D ^{-\frac{1}{2}}H^{(l)}W^{(l)}) H(l+1)=σ(D~21A~D~−21H(l)W(l))

SPECTRAL GRAPH CONVOLUTIONS

频谱图形卷积

半监督分类图卷积网络是在先前的频谱卷积网络的基础上通过局部一阶近似得到的

对于一个输入信号 x ∈ R N x \in \mathbb{R}^N x∈RN ，在傅里叶域中取一个 θ ∈ R N \theta \in \mathbb{R}^N θ∈RN为参数的滤波器 g θ = d i a g ( θ ) g_{\theta} = diag(\theta) gθ=diag(θ)。

将图卷积通过傅里叶变换拓展到图的频域中。

第一代GCN图卷积公式

缺点：计算复杂

g θ ⋆ x = U g θ U x ⊤ gθ⋆x=U_{gθ}U^⊤_{x} gθ⋆x=UgθUx⊤

将 g θ ( Λ ) g_{\theta}(\Lambda) gθ(Λ)用切比雪夫多项式（Chebyshev）进行K阶逼近。

改进的卷积核：

g θ ‘ ( Λ ) ≈ ∑ k = 0 K θ k ′ T k ( Λ ~ ) g_{θ‘}(Λ)≈\sum_{k=0}^Kθ_k^′T_k(\tilde Λ) gθ‘(Λ)≈k=0∑Kθk′Tk(Λ~)

将该卷积核代入图卷积的公式：

将参数减少到了K个，并且不再需要对拉普拉斯矩阵做特征分解。

g θ ‘ ⋆ ∗ ≈ ∑ k = 0 K θ k ′ T k ( L ~ ) x g_{θ‘}⋆*≈\sum_{k=0}^Kθ_k^′T_k(\tilde L)x gθ‘⋆∗≈k=0∑Kθk′Tk(L~)x

LAYER-WISE LINEAR MODEL

线性模型

g θ ′ ∗ x = ∑ k = 0 K θ ′ k T k ( L ~ ) x g_{θ′}∗x=\sum _{k=0}^Kθ^′kT_k(\tilde L)x gθ′∗x=k=0∑Kθ′kTk(L~)x

限制参数数量可以进一步解决过拟合并将各层的运算量最小化，使得可以通过堆叠多个GCN来获得一个更深的模型，提取特征。

为解决数值不稳定性和梯度爆炸/消失，进行了再归一化。

限制参数的数量以解决过度拟合问题，并最小化每层的运算数量(例如矩阵乘法)。

SEMI-SUPERVISED NODE CLASSIFICATION

半监督节点分类

使用已知的数据 X X X和邻接矩阵 A A A来训练图卷积网络 f ( X , A ) f(X, A) f(X,A)。

【GCN】论文浅读：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

GCN网络示意图

输入层拥有C个输入，中间有若干隐藏层，在输出层有F个特征映射。

图的结构在层之间共享。

标签用 Y i Y_{i} Yi 表示。

两层GCN在Cora数据集上（使用了5%的标签）训练得到的隐藏层**值的形象化表示，颜色表示文档类别。

数据集

Citeseer,Cora ,Pubmed ,NELL

引文网络数据集：Citeseer,Cora,Pubmed

性能水平

比较模型：

流形正则化(ManiReg)、半监督嵌入(SemiEmb)、标签传播(LP)、基于跳跃文法的图嵌入(DeepWalk)、迭代分类算法(ICA)、两个Logistic回归分类器。

GCN在四个数据集上的表现都比较突出，分类准确性较高。
提出的GCN模型能够同时对图结构和节点特征进行编码，对半监督分类是有用的。

思考

有监督学习、无监督学习和半监督学习的分类

监督学习是使用已知正确答案的示例来训练网络的。
无监督学习适用于具有数据集但无标签的情况。
半监督学习在训练阶段结合了大量未标记的数据和少量标签数据。

【GCN】论文浅读：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

GCN

任务