图卷积神经网络

　　一、 背景与概念
　　图神经网络的概念首先由Gori et al.[1]在2005年提出概述，Scarselli et al.[2]在2009中进一步阐述。这些早期的研究通过循环神经结构迭代地传播邻居信息来学习目标节点的表示，直到到达一个稳定的不动点。这个过程在计算上代价是非常昂贵的，最近有越来越多的研究者努力来克服这些挑战[3，4]。
　　受卷积神经网络在计算机视觉领域产生巨大成功的启发，最近出现了大量重新定义基于图数据的卷积符号方法。这些方法都属于Graph Convolutional Networks (GCNs)的范畴。Bruna等人在2013年对GCNs进行了首次深入研究，在图谱理论[5]的基础上发展了一种图卷积的变体。从那时起，基于频谱的图卷积神经网络有了越来越多的改进、扩展和近似[6]。由于光谱方法通常同时处理整个图，难以并行或缩放成大图，因此近年来基于空间的图卷积神经网络得到了快速发展[7，8]。这些方法直接在图域内通过聚合相邻节点信息来实现卷积。结合采样策略，可以在一批节点中进行计算，而不是整个图，具有提高效率的潜力。除了图卷积神经网络之外，在过去的几年中，许多替代性的图神经网络也得到了发展。这些方法包括图注意网络、图形自动编码器、图生成网络和图时空网络，这些方法会在图卷积神经网络的架构部分简单阐述。
　　此外，CNN的平移不变性在非欧结构数据上不适用。为了在拓扑图上提取空间特征来进行学习，GCN引入可以优化的卷积参数。GCN将卷积运算从传统数据推广到图数据。其核心思想是学习一个函数映射f，通过该映射图中的节点 可以聚合它自己的特征 与它邻居的特征 , , 来生成节点 的新表示。GCN是许多复杂图神经网络模型的基础，包括基于自动编码器的模型、生成模型和时空网络等。传播过程对于图网络的训练是至关重要的，目前主流的方法是将卷积应用到图结构上，也就是图卷积网络(GCN)[9]。此外，还有将注意力机制（如：graph attention network，GAT）、门机制（如：gated graph neural network，GGNN）和残差机制（如：highway-GCN）引入图网络的方法。最近，越来越多的研究开始将深度学习方法应用到图数据领域。受到深度学习领域进展的驱动，研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器的思想。例如，图2.6.1展示了受标准2D卷积启发得到的图卷积。为了应对图数据的复杂性，重要运算的泛化和定义在过去几年中迅速发展。
　　图2.6.1 2D卷积 VS. 图卷积
　　二、 图卷积神经网络的现有方法与架构
　　图2.6.2 GCNs学习节点表示的过程结构图
　　1图卷积神经网络的现有方法
　　图卷积网络(GCNs)将传统数据(图像或网格)的卷积运算推广到图数据中。关键是学习一个函数f通过聚合其自身特征 和邻居特征 来生成一个节点 的表示，其中 。图2.6.2显示了GCNs学习节点表示的过程。图卷积网络在构建其他许多复杂的图神经网络模型中起着核心作用，包括基于自动编码器的模型、生成模型和时空网络等。图神经网络的架构如图2.6.3所示。
　　（1） 图注意力网络：图注意网络类似于GCNs，它寻求一个聚合函数来融合图中的邻近节点、随机游动和候选模型，从而学习一种新的表示。关键的区别在于，图注意网络采用了给更重要的节点、行走或模型分配更大权重的注意机制。注意权值是与神经网络一起学习的端到端框架中的参数。图卷积网络在聚合的过程中，采用了一个非参数化的权重 给 的邻居 。而图注意力网络[10]通过端到端神经网络架构隐式捕获权值 ，使更重要的节点获得更大的权值。
　　（2） 图自动编码器：图自动编码器是无监督学习的一种框架，旨在通过编码器学习低维节点矢量，然后通过解码器重建图数据。图自动编码器是一种学习图嵌入的流行方法，对于无属性信息的纯图以及属性图都是如此。对于普通图，许多算法直接预先占有邻接矩阵，通过构造一个具有丰富信息的新矩阵(点态交互信息矩阵)，或提供邻接矩阵到一个自动编码器模型来捕获一阶和二阶信息。对于属性图，图自动编码器模型倾向于使用GCN[11]作为编码器的构建块，并通过链接预测解码器重构结构信息。
　　（3） 图生成网络：图生成网络旨在从数据中生成可信的结构。给定图的经验分布，生成图从根本上是具有挑战性的，主要是因为图是复杂的数据结构。为了解决这个问题，研究人员探索了将生成过程作为节点和边交替形成的因素，采用生成式对抗训练[12]。图生成网络的一个很有前途的应用领域是化合物合成。在化学图中，原子被视为节点，化学键被视为边。其任务是发现新的可合成的具有一定化学和物理性质的分子。
　　（4） 图时空网络:图时空网络的目标是从时空图中学习不可见的特征，这些特征在交通预测和人类活动预测等许多应用中越来越重要。例如，基础道路交通网络是一个自然图，其中每个关键位置都是一个节点，其交通数据被连续监控。通过建立有效的图时空网络模型，可以准确预测整个交通系统的交通状态[13]。图时空网络的核心思想是同时考虑空间依赖性和时间依赖性。目前的许多方法都使用GCNs来捕获依赖关系，同时使用一些RNN或CNN来建立时间依赖关系。
　　图2.6.3 图神经网络架构
　　2图卷积神经网络的现有架构
　　GCNs方法分为两类，基于光谱的和基于空间的。基于频谱的方法从图形信号处理的角度通过引入滤波器来定义图卷积，其中图卷积操作被解释为从图形信号中去除噪声。基于空间的方法将图的卷积表示为来自邻居的特征信息的聚合。当GCNs在节点层运行时，图池模块可以与GCN层交叉，从而将图粗化为高级子结构。下面分别介绍基于频谱的GCNs、基于空间的GCNs和图池模块。
　　图卷积神经网络主要包括卷积算子和池化算子的构建，其中卷积算子的目的是刻画节点的局部结构，而池化算子的目的是学到网络的层级化表示，降低参数。在解决节点级别的任务时，研究人员更关注如何给每个节点学到更好的表达，此时池化算子并不必要，因为池化算子通常用在图级别的任务上。
　　基于谱（spectral-based）：从图信号处理的角度引入滤波器来定义图卷积，其中图卷积操作被解释为从图信号中去除噪声。核心思想：通过引入傅里叶变换将时域信号转换到频域进行分析，进而完成一些在时域上无法完成的操作。
　　方法：在频谱域上进行定义图卷积，它基于对图的拉普拉斯矩阵进行特征值分解的操作。对于图而言，与二维矩阵数据不同，其卷积是难以直接进行离散化的定义的，所以要将空间域的卷积运算变换为频谱域的矩阵相乘。
　　原理：图信号处理
　　正则化图拉普拉斯矩阵L：无向图的鲁棒数学表示。
　　L矩阵分解：L是实对称半正定的。
　　图x的傅里叶（反）变换。
　　对输入信号X的图卷积操作
　　现有模型:Spectral CNN；Chebyshev Spectral CNN (ChebNet)；Adaptive Graph Convolution Network (AGCN)
　　缺点:需要将整个图加载到内存中以执行图卷积，这在处理大型图时是不高效的。依赖于对拉普拉斯矩阵进行特征值分析，这就削弱了泛化能力。
　　基于空间（spatial-based）: 直接在图上定义卷积，从邻域聚合特征信息，当图卷积网络的算法在节点层次运行时，图池化模块可以与图卷积层交错，将图粗化为高级子结构。如图2.6.4所示，这种架构设计可用于提取图的各级表示和执行图分类任务。
　　图2.6.4 图卷积网络与池化模块架构图
　　主要挑战： 既要对不同大小的邻域定义卷积，又要保证CNN的局部不变性。
　　常用方法： GraphSAGE(graph sampling and aggregating)，对顶点的局部邻域进行采样和聚合来生成embedding.具有池化模块的图卷积网络用于图分类。在GCN层之后是一个池化层，用于将一个图粗化为子图，以便粗化图上的节点表示更高的图级表示。为了计算每个图标签的概率，输出层是一个带有SoftMax函数的线性层。
　　每个像素代表一个节点，每个像素直接连接到其附近的像素。通过一个3×3的窗口，每个节点的邻域是其周围的8个像素。这8个像素的位置表示一个节点的邻居的顺序。然后，通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均，对该3×3窗口应用一个滤波器。由于相邻节点的特定顺序，可以在不同的位置共享可训练权重。
　　以下是两种GCN比较，基于效率、通用性、灵活性三方面比较：
　　Spectral-based： 最早的GCN在图信号处理方面有一定的理论基础；通过设计新的图信号滤波器，可以从理论上设计新的图卷积网络。
　　Spatial-based： 近年来空间模型越来越受到关注。
　　效率：Spectral-based：计算成本随着图的大小而急剧增加，因为它们要么需要执行特征向量计算，要么同时处理整个图，这使得它们很难适用于大型图。Spatial-based：有潜力处理大型图，因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行，而不是在整个图中执行。当相邻节点数量增加时，可以引入采样技术来提高效率。
　　通用性：Spectral-based：假定是一个固定的图，使得它们很难在图中添加新的节点。Spatial-based：在每个节点本地执行图卷积，可以轻松地在不同的位置和结构之间共享权重。
　　灵活性：Spectral-based：仅限于在无向图上工作，有向图上的拉普拉斯矩阵没有明确的定义，因此将基于谱的模型应用于有向图的唯一方法是将有向图转换为无向图。Spatial-based：更灵活地处理多源输入，这些输入可以合并到聚合函数中。