1. Graph Neural Networks 1: GNN Model
- 回忆一下节点嵌入1任务。其目的在于将节点映射到d维向量，使得在图中相似的节点在向量域中也相似。
我们已经学习了 “Shallow” Encoding 的方法来进行映射过程，也就是使用一个大矩阵直接储存每个节点的表示向量，通过矩阵与向量乘法来实现嵌入过程。
这种方法的缺陷在于：
- 一个GNN网络的结构如图：
- 通过网络可以解决的任务有：
- 节点分类：预测节点的标签
- 链接预测：预测两点是否相连
- 社区发现：识别密集链接的节点簇
- 网络相似性：度量图/子图间的相似性
- 传统机器学习难以应用在图结构上。具体原因在Lecture 中已经讲过，我也撰写过相应笔记，不再赘述。
2. Basics of Deep Learning
- 随机梯度下降stochastic gradient descent (SGD)
每一次梯度下降都需要计算所有数据集上的梯度，耗时太久，因此我们使用SGD的方法，将数据分成多个minibatch，每次用一个minibatch来计算梯度。
- minibatch SGD
SGD是梯度的无偏估计，但不保证收敛，所以一般需要调整学习率。
对SGD的改进优化器：Adam，Adagrad，Adadelta，RMSprop……等
术语：
- 总结
3. Deep Learning for Graphs
- 本节内容：
- local network neighborhoods
聚合策略
计算图
- 叠层
模型、参数、训练
如何学习？
无监督和有监督学习举例
- 我们可能很直接地想到，将邻接矩阵和特征合并在一起应用在深度神经网络上（如图，直接一个节点的邻接矩阵+特征合起来作为一个观测）。这种方法的问题在于：
- 需要 O(|V|) 的参数
- 不适用于不同大小的图
- 对节点顺序敏感（我们需要一个即使改变了节点顺序，结果也不会变的模型）
- Idea: 将网格上的卷积神经网络泛化到图上，并应用到节点特征数据
- 图上无法定义固定的locality或滑动窗口，而且图是permutation invariant8的（节点顺序不固定）
- Graph Convolutional Networks
通过节点邻居定义其计算图，传播并转换信息，计算出节点表示（可以说是用邻居信息来表示一个节点）
- 核心思想：通过聚合邻居来生成节点嵌入
直觉：通过神经网络聚合邻居信息
直觉：通过节点邻居定义计算图（它的邻居是子节点，子节点的邻居又是子节点们的子节点……）
- 深度模型就是有很多层。
节点在每一层都有不同的表示向量，每一层节点嵌入是邻居上一层节点嵌入再加上它自己（相当于添加了自环）的聚合。
第0层是节点特征，第k层是节点通过聚合k hop邻居所形成的表示向量。
在这里就没有收敛的概念了，直接选择跑有限步（k）层。
- 邻居信息聚合neighborhood aggregation
不同聚合方法的区别就在于如何跨层聚合邻居节点信息（这是什么废话）。neighborhood aggregation方法必须要order invariant或者说permutation invariant8。
基础方法：从邻居获取信息求平均，再应用神经网络
这种deep encoder的数学公式：
- 如何训练模型：需要定义节点嵌入上的损失函数
- 矩阵形式
很多种聚合方式都可以表示为（稀疏）矩阵操作的形式，如这个基础方法可以表示成图中这种形式：
我自己写了个求解过程（因为线性代数比较差所以没法直接看出来怎么算的，得一点点推）
补充：向量点积/矩阵乘法就是逐元素相乘然后累加，对邻接矩阵来说相当于对存在边的元素累加
对整个公式的矩阵化也可以实现：
这样就可以应用有效的稀疏矩阵操作（这部分我不了解，还没看）。
同时，也要注意，当aggregation函数过度复杂时，GNN可能无法被表示成矩阵形式。
（W和B要转置后放到右边，应该是因为矩阵尺寸的方向问题？（上一层嵌入维度×下一层嵌入维度））
- 如何训练GNN
- 模型设计：overview
- 定义邻居聚合函数
- 定义节点嵌入上的损失函数
- 在节点集合（如计算图的batch）上做训练
- 训练后的模型可以应用在训练过与没有训练过的节点上
- inductive capability
因为聚合邻居的参数在所有节点之间共享，所以训练好的模型可以应用在没见过的节点/图上。比如动态图就有新增节点的情况。
模型参数数量是亚线性sublinear于 ∣ V ∣ 的（仅取决于嵌入维度和特征维度）（矩阵尺寸就是下一层嵌入维度×上一层嵌入维度，第0层嵌入维度就是特征维度嘛）。
- 总结
通过聚合邻居信息产生节点嵌入，本节阐述了这一总思想下的一个基本变体。具体GNN方法的区别在于信息如何跨层聚合。
接下来讲GraphSAGE。
4. Graph Convolutional Networks and GraphSAGE
- GCN vs. GraphSAGE
核心思想：基于local neighborhoods产生节点嵌入，用神经网络聚合邻居信息
GCN：邻居信息求平均，叠网络层
GraphSAGE：泛化neighborhood aggregation所采用的函数
5. 总结
本节课中介绍了：
- 神经网络基础：损失函数loss，优化optimization，梯度gradient，随机梯度下降SGD，非线性non-linearity，多层感知器MLP
- 图深度学习思想
- 多层嵌入转换
- 每一层都用上一层的嵌入作为输入
- 聚合邻居和本身节点
- GCN Graph Convolutional Network：用求平均的方式做聚合，可以用矩阵形式来表示
- GraphSAGE：更有弹性的聚合函数
