Simplifying Graph Convolutional Networks

一、相关介绍

在CNN处理的图像和视频数据中，像素点以按规律排列的形式构成矩阵（Euclidean Structure），见图2所示。然而，在社交网络和信息网络等复杂系统中，则包含一些非欧几里得结构的数据（Non-Euclidean Structure），如图3所示。

图1 图像矩阵示意图

图2 社交网络拓扑示意图

在GCN框架中，Graph代表了数学领域中基于顶点和边构建的拓扑结构描述其连接关系。这一特性源于以下几个关键原因：首先，在欧几里得空间或其他非欧几何体中存在难以满足的条件时（即常规卷积操作不具备平移不变性），传统的CNN架构无法有效处理此类数据特征；其次，在拓扑图中各节点的邻居数量可能存在差异性（即不同节点周围的连接数目不一），因此无法采用统一尺寸的标准滤波器来进行有效的局部特征提取和计算。

什么是图卷积神经网络

GCN是一种能对图数据进行深度学习的方法；

图卷积算子：

其中，i 为中心节点

如何理解图卷积算法

第一步：发送（send），每个节点通过转换机制将自身携带的特征信息传递给相邻的邻居节点，旨在完成特征提取过程。

第二步：接收（Receive），每个节点将来自邻居节点的特征向量进行集成处理；这一过程是在对节点的局部结构信息进行融合。

第三步：通过transform函数进行数据转换（Transform），整合相关信息后执行非线性转换（Nonlinear Transformation），从而提升模型的表示力（Expressive Power）。

在这三个步骤中，在起初阶段每个节点会携带与之直接相连节点的相关信息；随后在第二层计算过程中就能够实现将间接相连节点的相关信息也纳入其中；这样参与运算的信息就会更加丰富全面地参与到计算中去；随着层数递增，在关联领域范围扩大的情况下，在层次更深的时候会有更多的数据参与到计算过程中来。

GCN输入是一张图，经过一层一层计算变换，最后输出一张图

拉普拉斯矩阵（Laplacian）

定义如下：L = D - A。其中L为Laplacian矩阵，D代表顶点度数构成的对角矩阵（其主对角线元素对应各顶点的度数值），而A则为图论中的邻接矩阵。其计算流程如图5所示。

图3 拉普拉斯矩阵计算方法

为什么GCN要用拉普拉斯矩阵：

拉普拉斯矩阵是一种对称矩阵，并且能够完成特征分解，在理论层面与GCN的谱域相对应。

拉普拉斯矩阵仅限于中心顶点及其直接邻居顶点（1-hop neighbor）处具有非零元素，在其他所有位置均为零值。

二、简化的图卷积

每个图中的卷积层和节点表示都是使用三个策略来更新：

1、特征传播；

2、线性转换；

3、逐点非线性激活

与CNN类似，在图卷积网络（GCN）中感受野与层数呈正比例关系；然而随着层数的增加其计算量也逐渐变得更为复杂。本文旨在将非线性图卷积网络（GCN）转化为一个简单的线性模型SGC即通过持续地消除GCN层之间的非线性操作并将其整合为一个线性变换从而有效降低GCN所带来的额外计算负担。

图4 网络结构示意图

在传统的GCN网络中，特征传播可以表示为以下公式：

其中，A为图的邻接矩阵，D为A的度矩阵；

GCN的分类器可以写作：

基于假设GCN层之间的非线性并非至关重要，在这种情况下核心在于对局部邻居进行平均聚合操作。因此，在不牺牲整体性能的前提下探讨是否能够去除各层之间的非线性转换函数（例如ReLU），仅保留最终的softmax运算（以便生成概率输出）。所得模型呈现出完全线性的特性：

三、谱分析

1、证明了SGC在图谱域上对于应一个固定的滤波器。

表明基于原图的基础上添加自连接边能够通过归一化技巧有效地减少谱的规模。

四、实验结果

实验中GCN为2层，SGC中的k=2。

1、text classification

文本识别中，SGC的效率可以达到GCN的83.6倍。

2、semi-supervised user geolocation

半监督用户地理定位（Semi-supervised user geolocation）是一种方法论，在社交媒体分析中利用用户的社交网络数据、其行为特征以及少量已标注的数据点来进行用户的地理位置识别。