【斯坦福大学公开课CS224W——图机器学习】六、图神经网络1：GNN模型

【斯坦福大学公开课CS224W——图机器学习】六、图神经网络1：GNN模型

回忆一下节点嵌入任务。其目的在于将节点映射到d维向量，使得在图中相似的节点在向量域中也相似。
我们已经学习了 “Shallow” Encoding 的方法来进行映射过程，也就是使用一个大矩阵直接储存每个节点的表示向量，通过矩阵与向量乘法来实现嵌入过程。
这种方法的缺陷在于：

1. 需要 O(∣V∣) 复杂度（矩阵的元素数，即表示向量维度d×节点数|V| ）的参数，太多了。节点间参数不共享，每个节点的表示向量都是完全独特的
2. transductive：无法获取在训练时没出现过的节点的表示向量
3. 无法应用节点特征信息

本节课将介绍deep graph encoders，也就是用图神经网络GNN来进行节点嵌入。
映射函数，即之前1讲过的node embedding中的encoder：ENC(v) = 基于图结构的多层非线性转换
（对节点相似性的定义仍然可以使用之前Lecture 31中的DeepWalk、node2vec等方法）

通过网络可以解决的任务有：

1. 节点分类：预测节点的标签
2. 链接预测：预测两点是否相连
3. 社区发现：识别密集链接的节点簇
4. 网络相似性：度量图/子图间的相似性

1. Deep Learning for Graphs

我们可能很直接地想到，将邻接矩阵和特征合并在一起应用在深度神经网络上（如图，直接一个节点的邻接矩阵+特征合起来作为一个观测）。这种方法的问题在于：
需要 O(|V|)的参数
不适用于不同大小的图
对节点顺序敏感（我们需要一个即使改变了节点顺序，结果也不会变的模型）

Idea: 将网格上的卷积神经网络泛化到图上，并应用到节点特征数据

1.1 Graph Convolutional Networks

通过节点邻居定义其计算图，传播并转换信息，计算出节点表示（可以说是用邻居信息来表示一个节点）

核心思想：通过聚合邻居来生成节点嵌入

直觉：通过神经网络聚合邻居信息

直觉：通过节点邻居定义计算图（它的邻居是子节点，子节点的邻居又是子节点们的子节点……）

****

深度模型就是有很多层。
节点在每一层都有不同的表示向量，每一层节点嵌入是邻居上一层节点嵌入再加上它自己（相当于添加了自环）的聚合。
第0层是节点特征，第k层是节点通过聚合k hop邻居所形成的表示向量。
在这里就没有收敛的概念了，直接选择跑有限步（k）层

邻居信息聚合neighborhood aggregation

neighborhood aggregation方法必须要order invariant或者说permutation invariant。

基础方法：从邻居获取信息求平均，再应用神经网络

这种deep encoder的数学公式：

矩阵形式
很多种聚合方式都可以表示为（稀疏）矩阵操作的形式，如这个基础方法可以表示成图中这种形式：

1.2 如何训练GNN

2. 模型设计

1. 定义邻居聚合函数
2. 定义节点嵌入上的损失函数
3. 在节点集合（如计算图的batch）上做训练
4. 训练后的模型可以应用在训练过与没有训练过的节点上

2.1 inductive capability

因为聚合邻居的参数在所有节点之间共享，所以训练好的模型可以应用在没见过的节点/图上。比如动态图就有新增节点的情况。
模型参数数量是亚线性sublinear于 |V|的（仅取决于嵌入维度和特征维度）（矩阵尺寸就是下一层嵌入维度×上一层嵌入维度，第0层嵌入维度就是特征维度嘛）

3. Graph Convolutional Networks and GraphSAGE

GCN vs. GraphSAGE
核心思想：基于local neighborhoods产生节点嵌入，用神经网络聚合邻居信息
GCN：邻居信息求平均，叠网络层
GraphSAGE：泛化neighborhood aggregation所采用的函数