【论文阅读】SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

论文阅读

论文阅读

论文阅读

• • • 1. Introduction
    • 2. Fast Approximate Convolutions on Graphs
    • • 2.1 Spectral Graph Convolution

  • 2.2 Layer-wise Linear model

    • 3. Semi-supervised Node Classification
    • • 3.1 Example

  • Ref.:

本文针对图结构数据提出了一种半监督学习方法。采用了一种局部的一阶谱图卷积逼近来构建本文的网络架构，并在citation networks以及一个知识图谱数据集（knowledge graph dataset）上进行了实验验证。

1. Introduction

旨在解决如何对图中的一小部分数据点进行分类任务。
这一任务可被视为一种半监督式图学习问题，在该框架下通过显式的图正则化机制将标签信息平滑分布在整个图结构中。
引入拉普拉斯正则化项到损失函数中。

其中损失函数\mathcal{L}_0基于有标签数据进行计算；函数f(\cdot)通常代表如神经网络等可微分的非线性变换；节点特征矩阵X由每个节点对应的特征向量x_ix组成；图拉普拉斯矩阵\Delta = D - A对应于无向图\mathcal{G} = (V, E)；该图包含节点集合\mathcal{V}中的元素v_iv；边(v_i, v_j)属于边集\mathcal{E}；邻接矩阵（Adjacency Matrix）A属于实数域上的NxN矩阵空间；度矩阵（Degree Matrix）D在第i个对角元素处的值等于行i中所有元素之和：D_{ii} = \sum_j A_{ij}；相当于通过引入该正则化项进行约束，在经过神经网络运算后得到的结果应尽量平滑以避免过拟合

该文章建议以神经网络f(X,A)为基础进行图结构编码，并采用监督学习框架中的损失函数项\mathcal L_0进行训练。具体而言，在构建网络架构时无需引入额外的正则化项。值得注意的是，在设计过程中通过将邻接矩阵嵌入网络架构中这一创新手段，在不依赖标签的情况下实现了有效的学习目标定位能力。

2. Fast Approximate Convolutions on Graphs

考虑一个多层的图卷积网络（Graph Convolutional Network，GCN）：

其中，\tilde{A}=A+I_N表示无向图的邻接矩阵加上self-connections，I_N为单位矩阵，\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}，W^{(l)}表示可训练的权重矩阵，H^{(l)}\in \mathbb{R}^{N\times D}表示上一层的激活值，H^{(0)}=X。以下说明可以通过一个局部谱图滤波的一阶近似来推导上式。

2.1 Spectral Graph Convolution

图中所示的谱卷积本质上是将信号序列 x\in \mathbb{R}^N 通过滤波器 g_{\theta}=diag(\theta) 进行傅里叶域内的乘法操作实现的一种算法，在该区域内的处理过程中，\theta \in \mathbb{R}^N被设定为空间位置相关的参数：

其中，U 表示归一化图 Laplacian 矩阵（参考[2],[3]） L=I_N-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^T 的特征向量，\Lambda为对角为特征值的对角阵，U^Tx 为 x 的图傅里叶变换，因此，可以将 g_\theta 看作关于矩阵L特征值的函数 g_\theta(\Lambda)，可以通过K阶切比雪夫多项式T_k(x)估计该值：

其中，

\tilde{\Lambda} = \frac{2}{\lambda_{\text{max}} \Lambda} - I_N

代表了矩阵的最大特征值，
而 \theta' \in \mathbb{R}^K 是用于描述切比雪夫系数的一个向量空间。
这些切比雪夫系数通过递归地定义为 T_k(x) = 2x T_{k-1}(x) - T_{k-2}(x) 来实现，
其中初始条件设定为 T_0(x) = 1, T_1(x) = x 以确保多项式的正确性。

代入（3）得到：

其中，\tilde{L}定义为\frac{2}{\lambda_{max}}L - I_N；因为(U\Lambda U^T)^k = U\Lambda^k U^T的关系存在。
值得注意的是，在拉普拉斯矩阵L的多项式表示中，
其取值仅受中心节点及其K步范围内的节点影响

2.2 Layer-wise Linear model

令变量K赋值为1（考虑到多层迭代能够捕获更深层的信息特征），设定λ_max为2（假设网络具有足够的近似能力），从而得到对式（5)的简化表达式：

涉及两个参数\theta_0', \theta_1' 通过进一步避免模型过拟合并降低计算复杂度 可以将其表示为以下形式

仅包含单一参数θ=θ₀'=-θ₁'的情况下，在分析该表达式所导致的特征值位于区间[0,2]后，则可能出现梯度爆炸或消失问题。为此需进行归一化处理：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}

假设图中的每个节点都表示为一个向量，则当且仅当该节点属于\mathbb{R}^{N\times C}空间时（其中C代表特征向量的空间维度），式（7）将被拓展为...

其中，\Theta\in \mathbb{R}^{C\times F}代表滤波参数矩阵；Z\in \mathbb R^{N\times F}经过卷积运算得到的信号矩阵。该表达式与式（2）完全相同。

3. Semi-supervised Node Classification

此处提出了一种简洁且具适应性的图传播模型f(X,A)。在此前的基础上进一步优化与改进，在该模型中巧妙地融入了邻接矩阵这一关键组件，并在此基础上构建了一个具有良好扩展性的框架体系。具体而言，在该框架下可以通过合理的参数设置实现对不同拓扑结构数据的有效建模与学习，并在此过程中充分体现了算法的高度可解释性与灵活性特点。其结构示意图如图所示：

3.1 Example

在设计一个包含两层的GCN架构时，请先通过计算\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}的方式确定基础连接矩阵，并在此基础上构建前向传播机制

其中，在数学空间\mathbb{R}^{C\times H}中定义了输入到隐层的权重矩阵W^{(0)}；而在空间\mathbb R^{H\times F}中定义了隐层至输出的权重矩阵W^{(1)}；该模型采用了交叉熵损失函数来衡量预测值与真实标签之间的差异

其中，\mathcal{Y}_L表示有标签数据集，F表示类别数量

Ref.:

[1] Kipf, T. N. and M. Welling (2016). “Proposing a novel approach for semi-supervised classification task using graph convolutional network structures.” arXiv preprint arXiv:1609.02907.
此外，
[2] 例如，《图卷积网络在半监督分类中的应用》，该文详细阐述了研究者提出的系统性方法。
[3] 例如，《图卷积网络在半监督分类中的应用》，该文详细阐述了研究者提出的系统性方法。