图神经网络第5~7讲
矩阵分解
对浅层表示学习用矩阵分解表示出来
[wsdm’18]
问题和解决
$O(\vert V \vert)$
tranductive：新的节点来了要跑一遍
node features
从lookup到encoder
图神经网络
Permutation Invariance 问题：要保证同构的图的表示向量相同。对于任何置换矩阵$P$，$f(A, X)=f(PAP^\top, PX)$
Permutation Equivariance 问题：要保证同构的图的表示向量相同。对于任何置换矩阵$P$，$f(A, X)=Pf(PAP^\top, PX)$
普通的MLP不满足上面的条件，图神经网络不能直接用MLP。
GNN(GCN)
| 手动抽取特征：$X \in \R^{m × | V | }$，可以是属性、文字、图像 |
最早的图神经网络是GCN[Kipf and Welling, ICLR 2017]
思想：每个节点都是从邻居聚合来的。很容易从一个没见过的点的表示向量，解决的浅层表示学习的问题。
\[\textbf h_v^0=\textbf x_v\] \[\textbf h_v^k = \sigma(\textbf W_k\sum\limits_{u\in N(v)}\frac{\textbf h_u^{k-1}}{|N(v)|}+\textbf B_k\textbf h_v^{k-1}), \forall k \in \{1,2,...,K\}\] \[\textbf z_v = \textbf h_v^K\]Layer 0的表示向量是节点的初始特征
$\textbf W_k,\textbf B_k$的形状与节点数无关
GCN在此基础上将上述两个参数变为一个，对节点度数规范化
GNN的变种就在邻居聚合方式
Training
\[\min\limits_\Theta\mathcal{L}(\textbf y, f_\Theta(\textbf z))\]GraphSAGE
[Hamilton et al. NIPS 2017]
聚合:Mean, Pool, LSTM（随机打乱节点）
聚合邻居，和本身节点上一层串联，再加激活函数。
$l_2$归一化(trick)
很多聚合方式都可以写成矩阵运算。
GAT
| 自动学习：$\alpha_{vu}=\frac{1}{ | N(v) | }$ ，表示不同邻居的对点$u$的影响是不一样的。求取的方式就是注意力机制。 |
这种方式是Localized的。(Inductive)
Framework
A Single Layer
Message and Aggregation
\[\textbf{m}_u^{(l)}=\textrm{MSG}^{(l)}(\textbf h_u^{(l-1)}), u\in N(v)\cup \{v\}\]Message最简单的是线性层$\textbf W^{(l)}$
可以分为两部分，一个是邻居的，一个是自己上一层的信息。
Aggregetion最简单的是取平均、求和等等
GNN Layer in Practice
BN, Dropout, Attention/Gating, More(Skip)
BN
Input: $\textbf X\in \R^{N×D}$
将样本归一化为均值0，方差1.
Dropout in GNN
位置在线性层
Sigmoid 压成概率
(3)Layer Connection
Stacking GNN Layers
Receptive field：对某个节点的表示向量，决定它的向量的其他点的集合。经过3层后，Receptive field就会占满了。(小世界现象)
如果一直叠，会发生Over-smoothing，即如果两个点Receptive重合，表示向量就会相似。
增加模型的表达能力？
方式1
图的直径，任意两个节点之间最短路径中最长的值。层数不能超过这个长度。
GNN Layer的层和CNN不同，实际上可以在AGG上加入深度神经网络。
方式2
MLP 预处理 Encoder、后处理
问题需要更多层？
加入 Skip connections
参考ResNet
GCN 也有这个结构，相当于聚合后加入自己节点上一层的输出。
(4)Graph Augumentation
Manipulate Graphs
Feature 层面（缺少特征）和 Structure 层面（稀疏、稠密、大）
Feature
(1) 每个节点加一个a)常数、b)One-hot（节点数少） (2) 增加gnn难以学习的特征 聚集系数、PageRank、中心
Structure
稀疏
(1) 增加虚拟边：增加长度为2通路的邻居 $A+A^2$ （二部图） (2) 增加虚拟点：提升信息传递
稠密
邻居抽样
(5)Learning Objective
节点
k分类：从D维变换到k维，过Softmax
边
两个点的表示向量串联，降维到k 内积：相似性强的有边，k类过k头注意力
图
类似于点表示向量聚合。
Issue of Global Pooling
将节点分块逐层计算
GNN 的训练
监督学习和无监督学习
监督学习：Node Labels($y_v$), Edge Labels($y_{uv}$), Graph Labels($y_G$)，这些标签都是人工标注的。 无监督学习：只知道邻接矩阵。节点层面：聚集系数预测；边层面：链路预测
损失函数：分类和回归
prediction $\hat y$
Metrics: 回归：MSE Acc 分类：Acc, Prec, Recall, ROC/AUC(减少阈值带来的影响)
ROC Curve: AUC 是 ROC 曲线下的面积
Setup
Dataset Split
Fixed split Random split
Why Spliting GNN dateset Special?
Solution 1: Tranductive setting 整个图都参与训练，计算Loss只用对应数据集内的数据，只适用于节点和边的任务
Solution 2: Inductive setting 拆分图，还适用于图层面的任务。