我们提出了一种可扩展的方法,用于对图结构数据进行半监督学习,该方法基于直接在图上运行的卷积神经网络的有效变体。 我们通过谱图卷积的局部一阶逼近来激发对卷积架构的选择。我们的模型在图边的数量上线性缩放,并学习编码局部图结构和节点特征的隐藏层表示。 在引文网络和知识图数据集的大量实验中,我们证明我们的方法明显优于相关方法。
我们考虑在图(例如引文网络)中对节点(例如文档)进行分类的问题,其中标签仅适用于一小部分节点。 这个问题可以被定义为基于图的半监督学习,其中标签信息通过某种形式的基于图的显式正则化在图上平滑,例如 通过在损失函数中使用图拉普拉斯正则化项:
式中, L 0 \mathcal L_0 L0 为仅考虑标注节点的监督损失;f ( ⋅ ) 为可微函数,如神经网络;λ为权重因子;X为节点特征向量矩阵;Δ = D − A为无向图未标准化的拉普拉斯矩阵;A为邻接矩阵;D为节点度矩阵, D i i = ∑ j A i j D_{ii}=\sum_j A_{ij} Dii=∑jAij。
在这项工作中,我们直接使用神经网络模型 f(X, A) 对图结构进行编码,并对所有带有标签的节点在监督目标 L0 上进行训练,从而避免损失函数中基于图的显式正则化。 在图的邻接矩阵上调节 f(·) 将允许模型从监督损失 L0 中分配梯度信息,并使其能够学习带标签和不带标签的节点的表示。
我们的贡献是两方面的:首先,我们为直接在图上运行的神经网络模型引入了一个简单且表现良好的逐层传播规则,并展示了如何从谱图卷积的一阶近似中激发它。 其次,我们展示了这种形式的基于图的神经网络模型如何用于对图中节点进行快速且可扩展的半监督分类。 对多个数据集的实验表明,我们的模型在分类准确性和效率(以挂钟时间衡量)方面与最先进的半监督学习方法相比具有优势。
在本节中,我们为将在本文其余部分使用的特定基于图的神经网络模型 f(X, A) 提供理论动机。 我们考虑具有以下逐层传播规则的多层图卷积网络(GCN):
式中,
这种传播规则的形式可以通过图上局部光谱滤波器的一阶近似来激发。
公式(2)通俗理解:
如果每一层的输入都是邻接矩阵A和特征H,我们直接做内积(聚合邻接点特征),再乘一个参数矩阵W,经激活函数,构建如下简单神经网络:
这种简单的神经网络已经足够强大,但具有如下局限性:
经以上替换,便可得到层传播规则,即公式(2)。
普通形式的拉普拉斯矩阵L = D − A,标准化的拉普拉斯矩阵为
无向图邻接阵A为对称阵,可正交/谱分解,Λ为特征值对角阵,U为特征向量矩阵。拉普拉斯矩阵的性质:
给定信号
x
∈
R
N
x \in R^N
x∈RN,滤波器
g
θ
=
d
i
a
g
(
θ
)
g_\theta = diag(\theta)
gθ=diag(θ)(由傅里叶空间
θ
∈
R
N
\theta \in R^N
θ∈RN参数化),谱图卷积定义为:
其中,
U
T
x
U^Tx
UTx为x的图傅里叶变换
上式的局限性:
Hammond等人利用特征值对角矩阵的切比雪夫多项式,以K阶近似滤波器
g
θ
g_\theta
gθ:
式中,各参数的意义为:
通过堆叠多个卷积层可构造图卷积神经网络。我们希望模型能够在广度分布节点的图上尽可能减轻局部领域结构的过拟合问题,例如社交网络,引用网络,以及许多真实世界的图数据集。对于固定的计算预算,逐层线性表达允许我们创建更深的模型,这可在许多领域增加模型容量。
对于含有C个通道的输入信号,使用F个过滤器,有:
使用公式(8)构造两层图卷积网络:
无监督多分类任务,在所有有标签的节点上评估损失:
我们引入了一种新方法,用于对图结构数据进行半监督分类。 我们的 GCN 模型使用基于图谱卷积的一阶近似的有效逐层传播规则。 对大量网络数据集的实验表明,所提出的 GCN 模型能够以对半监督分类有用的方式对图结构和节点特征进行编码。 在这种情况下,我们的模型大大优于最近提出的几种方法,同时具有计算效率。
论文:https://arxiv.org/pdf/1609.02907.pdf
代码:https://github.com/tkipf/gcn