图卷积网络-图的深度学习-轻识

作者 | Francesco Casalegno

编译 | VK
来源 | Towards Data Science

为什么是图

图是最通用的数据结构之一，由于其强大的表达能力。在许多领域，机器学习模型已被成功地用于提取和预测图上数据的信息，对复杂元素及其关系进行建模。这里一些例子。

Traffic patterns forecasting on road networks
(https://arxiv.org/abs/1802.07007)
Inferring missing information in a Knowledge Graph
(https://arxiv.org/abs/1706.05674)
Predicting protein interactions for drug discovery
(https://papers.nips.cc/paper/2017/file/f507783927f2ec2737ba40afbd17efb5-Paper.pdf)
Recommender systems based on social networks data
(https://arxiv.org/abs/1902.07243)

图是最通用的数据结构之一，由于其强大的表达能力。在许多领域，机器学习模型已被成功地用于提取和预测图上数据的信息，对复杂元素及其关系进行建模。这是一些例子。

Traffic patterns forecasting on road networks
(https://arxiv.org/abs/1802.07007)
Inferring missing information in a Knowledge Graph
(https://arxiv.org/abs/1706.05674)
Predicting protein interactions for drug discovery
(https://papers.nips.cc/paper/2017/file/f507783927f2ec2737ba40afbd17efb5-Paper.pdf)
Recommender systems based on social networks data
(https://arxiv.org/abs/1902.07243)

不幸的是，图形数据是非结构化和非欧几里德的，所以建立机器学习模型来解决这些任务并不是很明显。一方面，节点之间的连接承载着重要的信息，另一方面，要想找到一种处理这种信息的方法也并非易事。

在这篇文章中，我们将看到如何使用图卷积网络（GCN）来解决这个问题，它将经典卷积神经网络（CNN）推广到图结构数据的情况。这篇文章的主要来源是Kipf et al.2016、Defferrard et al.2016（https://arxiv.org/abs/1609.02907）和Hammond et al.2009（https://arxiv.org/abs/0912.3848）的工作。

为什么是卷积

卷积神经网络（CNNs）在提取复杂特征方面已经被证明是非常有效的，卷积层是目前许多深度学习模型的主干。CNN在任何维度的数据方面都取得了成功：

在1D中，处理音频信号-例如用于声音分类
在2D中，处理图像-例如用于早期龋齿检测
在3D技术中，处理扫描，例如核磁共振脑成像

cnn之所以如此有效，是因为它能够学习一系列滤波器来提取越来越复杂的模式。特别地，这些卷积滤波器的特征是其紧凑的，并且有平移不变的特性。

只要有一点创造性，我们就可以将这些相同的思想应用到图数据上。与处理欧几里德数据（1D、2D或3D）相比，问题更难的是，不规则图上的平移是一个毫无意义的概念，因此我们需要找到另一种定义图卷积的方法。

定义图卷积

在欧几里得定义域上，卷积是由平移函数的乘积来定义的。但是，正如我们所说的，在不规则图上是没有定义的，所以我们需要从不同的角度来看待这个概念。

关键的思想是使用傅里叶变换。在频域中，由于卷积定理，两个信号的(未定义的)卷积变成了它们的变换的(定义良好的)分量乘积。所以，我们需要知道如何计算一个函数在一个图上的傅里叶变换，我们可以把卷积定义为

这就引出了下一个问题：我们如何定义图的傅里叶变换？

我们将通过类比经典的傅里叶变换来解决这个问题。我们来看看一个在实数上定义的函数。它的傅里叶变换是它在频率项下的分解，通过将函数投影在正弦波的标准正交基上得到。事实上，这些波正是拉普拉斯函数的本征函数

如果我们推广这个观点，我们可以把函数的傅里叶变换定义为它在拉普拉斯特征函数的正交基上的投影：

在图论中，拉普拉斯矩阵定义为L=D-A，其中

D、度矩阵是对角线矩阵，包含每个顶点的边数；
A、邻接矩阵表示每对顶点是否通过边连接。

假设图中的边是间接的(定义可以推广)，则拉普拉斯矩阵L是一个实对称正半定矩阵。因此存在一个对其进行对角化的标准正交矩阵U，一个图信号的图傅里叶变换，用N个顶点的值的N维向量表示，可以定义为其在这样的基上的投影:

既然一张图片胜过千言万语，让我们用具体的例子来看看这一切意味着什么。如果我们取对应于规则二维网格的Delauney三角剖分的图形，我们可以看到该图形的傅里叶基完全对应于自由方形膜的振动模态。这是有道理的，因为振动板的基本模态正是拉普拉斯函数的本征函数。

如果我们使用随机生成的图，我们仍然可以通过观察图的正交傅里叶基，可以看到图的振动模式。

既然我们知道了如何定义图傅立叶变换，也知道了如何定义图卷积，我们就可以理解图卷积网络的体系结构了！

全神经网络的建立

所有用于图像识别的卷积网络的结构趋向于使用相同的结构。对于VGG16这样的简单网络也是如此，但是对于ResNet这样的复杂网络也是如此。

通过一系列的局部卷积滤波器和池化层来提取HxWxC输入图像的特征。
产生的特征通道被映射到一个固定大小的向量，例如使用一个全局池层。
最后，使用几个全连接的层来产生最终的分类输出。

图卷积网络的结构遵循完全相同的结构！

对于GCN，我们的输入由以下元素表示：

NxC向量x，对于图的N个节点中的每一个顶点，包含C个特征
NxN邻接矩阵

为了完全理解上面所示的体系结构，我们还需要澄清最后两个概念：如何定义池层以及如何保证卷积滤波器具有紧凑性

对于池层，我们可以选择任何一种在保持局部几何结构的同时将节点集合合并在一起的图聚类算法。鉴于最优图聚类是一个NP-hard问题，在实际应用中采用了快速贪心近似。一个流行的选择是Graclus多级聚类算法。

关于卷积滤波器的紧凑性，我们如何保证GCN的卷积层在局部工作？一般来说，输入x由g过滤为

然而，在没有进一步假设的情况下，这种滤波器不具有紧支撑，而且学习ĝ（λ）的所有分量具有O（N）复杂性。为了解决这两个问题，我们将使用K次多项式参数化：

这将学习复杂度降低到O(K)，因为我们只需要学习θ0，…，θ{K-1}。和最重要的是,它可以表明ĝ是K-localized,

在正方形和不规则处进行紧凑滤波：

关于计算优化的最后观察。计算滤波信号ĝ（L）x的成本仍然高达O（N^2），因为乘法涉及U。但是，通过用切比雪夫多项式表示多项式（具有非常方便的递归公式），可以将此成本降低到O（EK）（其中E是边数）。

结论

从知识图到社交网络，图应用无处不在。
卷积神经网络（CNNs）在许多领域都取得了成功，可以推广到图卷积网络（GCNs）。
图的卷积是通过图的傅立叶变换来定义的。
图傅里叶变换又被定义为拉普拉斯特征值的投影。
对于传统的cnn，GCN由几个卷积层和池层组成，用于特征提取，然后是最后的完全连接层。
为了确保卷积滤波器具有紧凑的支持，我们使用多项式参数化。切比雪夫多项式可以降低计算复杂度。

往期精彩回顾




适合初学者入门人工智能的路线及资料下载
机器学习及深度学习笔记等资料打印
机器学习在线手册
深度学习笔记专辑
《统计学习方法》的代码复现专辑
AI基础下载
机器学习的数学基础专辑
温州大学《机器学习课程》视频
本站qq群851320808，加入微信群请扫码：