图神经网络全面解析

### 图神经网络全面解析 #### 1. 图与图神经网络基础 图由一组节点构成，节点对之间通过边相连。节点和边都可以附带数据，分别称为节点嵌入和边嵌入。许多现实世界的问题都可以用图来表示，目标是确定整个图的属性、每个节点或边的属性，或者图中是否存在额外的边。 图神经网络是应用于图的深度学习模型。由于图中节点的顺序是任意的，图神经网络的层必须对节点索引的排列具有等变性。基于空间的卷积网络是一类图神经网络，它聚合节点邻居的信息，然后用这些信息更新节点嵌入。 处理图的一个挑战是，图通常出现在归纳式设置中，即只有一个部分标记的图，而不是训练图和测试图的集合。这个图可能非常大，这在训练方面带来了进一步的挑战，从而催生了采样和分区算法。边图为原始图中的每条边设置一个节点，通过转换为这种表示，图神经网络可用于更新边嵌入。 #### 2. 图神经网络的应用 图神经网络的应用广泛，包括： - **图分类**：对整个图进行分类。 - **节点分类**：确定图中每个节点的类别。 - **边预测**：预测图中是否存在额外的边。 - **图聚类**：将图中的节点分组。 - **推荐系统**：根据用户和物品之间的关系进行推荐。 #### 3. 图神经网络的发展历程 - **早期模型**：图神经网络由Gori等人（2005）和Scarselli等人（2008）引入，他们将其表述为递归神经网络的推广。后者模型使用迭代更新公式： \[h_n \leftarrow f[x_n, x_{m\in ne[n]}, e_{e\in nee[n]}, h_{m\in ne[n]}, \phi]\] 其中，每个节点嵌入 \(h_n\) 从初始嵌入 \(x_n\)、相邻节点的初始嵌入 \(x_{m\in ne[n]}\)、相邻边的初始嵌入 \(e_{e\in nee[n]}\) 以及相邻节点嵌入 \(h_{m\in ne[n]}\) 更新而来。为了收敛，函数 \(f[\cdot, \cdot, \cdot, \cdot, \phi]\) 必须是收缩映射。 - **后续扩展**：后续工作将图神经网络扩展为使用门控循环单元（Li等人，2016b）和长短期记忆网络（Selsam等人，2019）。 #### 4. 图神经网络的方法 ##### 4.1 谱方法 Bruna等人（2013）在傅里叶域应用卷积操作。傅里叶基向量可以通过对图拉普拉斯矩阵 \(L = D - A\)（其中 \(D\) 是度矩阵，\(A\) 是邻接矩阵）进行特征分解得到。但这种方法存在缺点，滤波器不局部化，且对于大图，分解计算成本过高。 Henaff等人（2015）通过强制傅里叶表示平滑来解决第一个问题。Defferrard等人（2016）引入ChebNet，利用切比雪夫多项式的递归性质高效近似滤波器，既提供了空间局部化的滤波器，又减少了计算量。Kipf和Welling（2017）进一步简化，构建仅使用1跳邻域的滤波器，为谱方法和空间方法之间架起了桥梁。 ##### 4.2 空间方法 谱方法最终基于图拉普拉斯矩阵，因此如果图发生变化，模型必须重新训练。这促使了空间方法的发展。 - **Duvenaud等人（2015）**：在空间域定义卷积，为每个节点度使用不同的权重矩阵来组合相邻嵌入。但如果某些节点的连接数非常多，这种方法就不实用。 - **扩散卷积神经网络（Atwood和Towsley，2016）**：使用归一化邻接矩阵的幂来融合不同尺度的特征，求和后逐点乘以权重，再通过激活函数创建节点嵌入。 - **消息传递神经网络（Gilmer等人，2017）**：将图上的卷积定义为从空间邻居传播消息。GraphSAGE（Hamilton等人，2017a）的“聚合与组合”公式符合这个框架。 #### 5. 聚合与组合方法 - **图卷积网络（Kipf和Welling，2017）**：对邻居和当前节点进行加权平均，然后应用线性映射和ReLU。 - **GraphSAGE（Hamilton等人，2017a）**：对每个邻居应用神经网络层，取元素级最大值进行聚合。 - **Chiang等人（2019）**：提出对角增强，即对前一个嵌入的加权比邻居更大。 - **Kipf和Welling（2017）**：引入Kipf归一化，根据当前节点及其邻居的度对相邻嵌入的和进行归一化。 - **混合模型网络（MoNet，Monti等人，2017）**：根据当前节点和邻居的度学习权重，为每个节点关联一个伪坐标系，通过学习基于高斯混合的连续函数并在邻居的伪坐标处采样得到权重。 - **Pham等人（2017）**：对节点嵌入和邻居进行线性插值，每个维度使用不同的加权组合，门控机制的权重作为数据的函数生成。 #### 6. 高阶卷积层 - **Zhou和Li（2017）**：使用高阶卷积，将邻接矩阵 \(A\) 替换为 \(\tilde{A} = Min[AL + I, 1]\)，其中 \(L\) 是最大步长，更新时会汇总所有距离为 \(L\) 的节点的贡献。 - **Abu - El - Haija等人（2019）**：提出MixHop，从邻居（使用邻接矩阵 \(A\)）、邻居的邻居（使用 \(A^2\)）等计算节点更新，并在每层连接这些更新。 - **Lee等人（2018）**：使用几何图案（图中的小局部几何模式）组合来自直接邻居之外节点的信息。 #### 7. 残差连接 - **Kipf和Welling（2017）**：提出残差连接，将原始嵌入添加到更新后的嵌入中。 - **Hamilton等人