Graph Neural Networks: A Review of Methods and Applications-2018-arXiv论文阅读笔记

最终决定深入阅读这篇论文。它是通过在知乎上查找"图卷积"这一关键词而发现的一篇综述文章：图神经网络综述：模型与应用 - 张俊的文章 - 知乎。该综述主要概述了本文所介绍的核心内容和相关进展。

1. Introduction

图神经网络的应用

图是一种数据结构, 能够将物体及其关系建模为节点node和边edge基于其强大的表示能力, 图神经网络主要应用在以下几个方面

• 社交平台
• 自然学科（生命系统, 蛋白质相互作用网络）
• 知识图谱

图神经网络的动机

第一个动机——卷积神经网络

• 稀疏链接（或者叫局部连接）

• 权重共享

• 多层叠加
  （之前的博客中也有总结过卷积神经网络：《深度学习第九章》——阅读笔记）
  这几特性在解决图领域的问题中也尤为重要：

• 图是典型的局部连接结构

• 权重共享同样能够减少计算量：在理解这一机制时，默认假设传统的谱域图理论较为复杂 [10]。

• 通过扩展感受野的概念来捕捉不同尺度的特征
  因此类比推理，在非欧几何环境下进行类比推理时会面临诸多挑战与限制因素。例如，在传统网格数据上基于卷积神经网络的方法依赖于固定的拓扑关系来进行特征提取与学习过程；而针对图数据则需要考虑其更为复杂的关联性与多样性。
  然而如前所述，在现有文献中并未找到一种普遍适用的有效方法来解决这一问题：因为这些操作通常依赖于网格状的数据结构来进行定义与实现。

第二个动机——graph embedding
什么是graph embedding呢？从字面上理解就是嵌入图。这应该是自然语言处理领域中的术语，我也不是很懂，就说说自己浅显的理解：
graph embedding是基于表示学习的一种方法，什么是表示学习呢？一本书上是这样说的：

     learning representations of the data that make it easier to extract useful information when building classifiers or other predictors。graph embedding

    
    
         
    代码解读

目的是借助图表首先通过图形来表示数据。之前的一些graph embedding的方法存在两个主要的问题:

• 参数之间相互独立，则计算量与节点数量呈正比关系；
• 将图直接嵌入网络中会导致网络在处理动态图时表现出有限的适应性，并且无法有效应对动态变化的场景，并且难以推广到新的类型网络中去。

研究神经网络的动机在于以下几点：一是CNN的三大特性能够适应这种数据结构的需求；二是graph embedding中非共享特征能够参考CNN中参数共享的技术以进一步解决问题。

图神经网络需要考虑的问题

传统的神经网络如CNN和RNN通常在处理数据时依赖于特定顺序的信息传递。然而，在这种情况下（即节点之间没有固定排列），传统的神经网络并不适用。为了能够更好地捕捉到图中各结点之间的关系和信息流动的情况，在设计模型时需要考虑所有可能的不同排列组合（例如N个节点的所有N!种排列），然而这会导致计算复杂度变得非常高。基于此，在研究图神经网络时发现其核心特点在于每个节点都能独立地进行信息处理而不依赖于其他节点的位置或排列顺序；换句话说，在这种架构下模型具有置换不变性的特性。

图中的一条连接代表两个节点间的关联/依赖关系，在传统神经网络中这种关联被视为节点特征的表现（即输入单元与输出单元之间的联系）。然而，在图神经网络中这种关联能够被传播出去而不将其视为单个节点的属性

第三个问题——从大量的经验数据中推理图
标准神经网络能够训练数据分布以生成合成图像和文档资料,但目前这类模型仍然无法从大量非结构化信息（如场景图片与故事文档）中推导出图表.这一类模型展示了强大的能力,进一步增强了对复杂模式的理解能力.

2. Models

接下来按一下内容介绍神经网络模型：

• 2.1 节阐述了原始图神经网络的基本概念，并进一步指出了其在表示能力与训练效率方面存在的局限性。
• 2.2 节探讨了几种改进方案以缓解上述局限性。这些改进方案根据不同类型的图结构采用了多样化的传播机制，并结合了多种训练优化方法。
• 2.3 节提出了三种统一架构以拓展现有研究方向。具体而言：
  • Message Passing Neural Network (MPNN) [25]成功整合了多种图神经网络与图卷积模型；
  • Non-Local Neural Network (NLNN) [26]则通过引入自注意力机制实现了跨节点信息的有效融合；
  • Graph Network (GN) [27]则具备整合并超越现有各类神经网络变体的能力。

2.1 Graph Neural Networks

原始的图神经网络

图神经网络的发展旨在推动现有技术的进步。它特别适用于处理具有复杂连接模式的数据类型。在一个图结构中，默认情况下每个节点通过其自身的特征及其关联节点的特征来定义其属性。

[注]：不动点定理：在数学中，函数的不动点（Fixed point, or shortened to fixpoint, also knowns as invariant point），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身，如下图所示：

原始的图神经网络有三个限制

1. 相较于固定点而言, 逐步更新节点的方法在效率上存在不足之处.如果我们放弃固定点假设, 可以构建一个多层图神经网络架构, 进而实现节点与其邻居之间的稳定表征.
2. 在整个迭代过程中, 图神经网络采用相同的参数矩阵进行运算, 而许多流行的人工神经网络会在不同层采用不同的参数矩阵以实现层次化的特征提取效果.另外, 节点隐藏状态的变化过程是一个有序的操作序列, 可以通过类似于GRU和LSTM等RNN核的方式来建模.
3. 当前的研究未能充分考虑边上重要信息的影响因素.例如，在知识图谱中, 边所携带的信息类型各不相同;且基于不同类型边的信息传播机制也应有所区别（例如: 有向边仅允许单方向传播信息;无向边则可双向传递信息）;此外, 如何有效学习边上所蕴含的状态变化也是一个待解决的关键问题.
4. 最终若仅关注节点自身的表征而非整个图的信息结构, 则固定点方法就不再适用了.因为这种表示形式往往具有平滑性高的特点且缺乏足够的细节来区分不同节点的独特性.

2.2 Variants of Graph Neural Networks

下面我们将重点介绍几种图神经网络的不同变种。在第2.2.1节中讨论了针对不同类型的图设计的变体，在这种设计思路下实现了对原始模型性能的有效扩展；第2.2.2节详细阐述了改进措施，在信息传递过程中引入了多种技术手段；第3个小节则深入探讨了几种基于先进训练方法设计的变体，在性能上得到了显著提升。

2.2.1 Graph Types

2.1节所介绍的基本型图神经网络中,输入由带有标签信息的节点及其无向边构成.这属于最基本的形式之一.然而世界上存在多种类型的图结构,并且接下来将介绍针对不同类型的建模方法.

1. Directed Graphs ： 无向图可以看做是两个结点之间存在两个有向边，而有向边可以带来比无向边更多的信息。例如，在知识图谱中，边从头结点指向尾结点，头结点是尾结点的父类，表明我们应该让信息从父类向子类传播。相关文献为ADGPM[29]。
2. Heterogeneous Graphs ：异质图指的是结点的类型不同。最简单的处理异质图的方法就是将每个结点的类型表示为一个one-hot特质向量和原始的每个结点的特征拼接起来。相关文献GraphInception[30]在异质图的传播中引入了metapath（元路径）的概念。有了metapath，我们可以根据结点的类型和结点之间的距离对结点分组。对每个邻接组，GraphInception将邻接组看作一个同质图去传播，然后将不同的同质图的结果拼接在一起得到一个聚合的结点表示。
3. Graphs with Edge Information ：每个边也有其信息，比如变得权重和类型。有两种方式处理这种图。第一：我们将图转化为bipartite graph（二分图）。二分图中，原始的边也变为结点，原始的一条边分割为两个新的边（即原始的开始结点和结束结点之间有两个新的边）。文献G2S[31]中的编码器即为这种做法。第二：针对不同类型的边我们采用不同的权重度量用于传播。当结点之间的关系数量十分庞大时，文献r-GCN[32]引入了两种泛化机制来对大量的关系进行建模，从而减小参数的数量

2.2.2 Propagation Types

信息传播（2.1节中的草稿图中F和G）在模型中用于推导出结点或边的隐藏状态是十分关键的过程。论文中所提及的主要发现表明，在信息传播过程中有若干显著的改进措施被提出。然而，在输出层部分，则通常采用较简单的前馈神经网络结构来处理数据。如表所示，则列举了不同类型的图神经网络架构，在这些架构中各节点邻居的信息聚合方式各有不同，并基于特定的设计理念对节点隐状态进行更新

随着图域内卷积的应用越来越广泛，在这一领域取得的研究成果也日益受到关注

谱域方法具有以下特点：其核心特征在于，在经过固定结构训练后无法直接应用于其他类型的架构

• 非谱域的方法直接在图上定义卷积操作，在空间层面处理相邻节点关系。
• **[33]**针对度数各异的节点提出采用不同权重矩阵的设计方案。
• **[21]**未能完全理解相关内容。
• • 对于每个节点而言，在其邻接点集合中提取K个特征向量，并对其进行归一化处理；归一化之后的邻居节点集合构成了该节点处卷积操作的感受野区域。
• • **[20]**提出了基于非欧几里得空间域模型的新架构设计，在此架构下构建了图卷积运算模型，并将现有工作（如图上中的图卷积[2,21]以及流形上的图卷积[22]）视为该理论体系的具体实现方案。
• • **[1]**提出了GraphSAGE框架——一种统一归纳学习模型；通过随机采样局部邻居信息并聚合其特征表示来生成嵌入表示。

然而[1]并未充分考虑所有邻居节点的信息。相反，在[1]中所采用的是等比例采样策略以获取固定大小的邻居节点。该研究中提出了三种聚合函数来处理这些邻居信息。
第一种：平均值聚合函数与其他方法不同之处在于它无需整合前一次迭代中心节点与当前迭代邻域节点之间的信息关系。这种设计可被视为一种更为高效的跳跃链接机制，并且实验结果表明其性能表现更好。
第二种：基于长短期记忆（LSTM）的方法相较于平均值聚合具有更强的信息表示能力。然而LSTM模型采用序列处理方式导致无法保证置换不变性特性。为了克服这一局限性，在[1]的研究框架下引入了特殊的设计方法。
第三种：图池化操作通过全连接层与最大值池化操作相结合（或其他对称操作）来生成各子图特征向量。
此外[42]提出了一种基于结构感知卷积及其结合深度神经网络的方法来处理欧几里得空间以及非欧几里得空间数据。
第二部分 Gate机制
第三部分 Attention机制
自注意力机制已经在多种基于序列的任务中展现出强大的性能优势例如机器翻译领域中的文本摘要任务等。其中[54]提出了一种图注意力网络（GAT）框架将自注意力机制嵌入到信息传播过程之中。
具体而言该研究设计了一个单独的图注意力层通过叠加多层注意力机制构建出完整的图注意力网络架构。
该层通过如下公式计算各节点间的注意力权重系数：

\alpha_{ij} = \text{softmax}\left( \frac{a(h_i^T W_a h_j)}{\sqrt{d}} \right)

其中a代表注意力权重参数矩阵h_i和h_j分别表示第i个及第j个节点对应的隐藏状态向量d为归一化因子。

完整的步骤理解下来应该是这样：但是a不知道是怎么学习到的？？？

4. Skip connection
许多应用重复图神经网络层来达到更高的结果，因为层数更多使得每个结点都均匀的聚合来自相邻点的更多信息。然而很多实验观察得知，网络层数增多不能改进性能反而使性能降低。主要是因为层数增加可能也会从均匀的增加的邻居结点中传播噪音。
一个直接的解决问题的办法就是借鉴图像中的残差网络，但是即使增加了残差连接，更多层的图神经网络效果都没有两层的好。
**[56]**提出了Highway GCN（涉及到门控gate，这里我看不懂）
[58]

2.2.3 Training Methods

原始图卷积神经网络在训练阶段存在明显的局限性。具体而言：

1. GCN需要为整个图计算拉普拉斯矩阵这一过程具有较高的计算复杂度。
2. 在每一层中，
   一个节点的嵌入表示是通过从前一层所有邻居节点嵌入向量进行递归聚合得到的，
   因此该节点的感受野随层数线性增长，
   这导致梯度计算量随着深度增加而急剧上升。
3. GCN对于固定结构图的学习仅能实现局部特征建模，
   无法有效归纳全局特征，
   从而限制了其扩展能力。

2.3 General Frameworks

除了现有的图神经网络的各种变体外，在论文研究中构建了一系列统一化的架构来整合不同模型为一个单一的整体框架。其中[25]开发了一种名为message passing neural network (MPNN)的方法，在整合多种图神经网络及图卷积技术方面表现尤为出色。随后[26]进一步引入了一种名为non-local neural network (NLNN)的架构，在处理长距离依赖关系方面表现尤为出色，并且该研究同时整合并推广了多个基于自注意力机制的方法。最后[27]在此基础上提出了一种称为graph networks的新框架，在实现对各种现有变体的有效整合与优化方面取得了显著成果。

2.3.1 Message Passing Neural Networks

[25]系统性地构建了一个适用于图上监督学习的信息传递神经网络框架，并将其命名为信息传递神经网络（ITNN）。该框架通过统一的方式整合了图卷积领域中广泛采用的多种主要模型（包括基于频谱域的方法、非频谱域方法、门控图网络、交互网络以及深度张量网络等）。其中信息传递阶段（即传播）负责实现节点间特征的动态交互与优化；读出阶段则通过设计有效的特征聚合方式实现全局特征的提取。其中信息传递阶段（即传播）负责完成节点间特征的动态交互与优化过程；读出阶段则通过设计有效的特征融合机制来提取全局特性。