# 为什么需要图神经网络

随着时代发展，深度学习在语音、图像、自然语言处理方面有很大突破，针对这种很结构化的序列、网格数据，有很好的处理效果。然而，现实世界中，不是所有数据都能描绘成序列或网格化的数据的。图数据有这些特点

图的大小是任意的，图的拓扑结构复杂，没有像图像一样的空间局部性
图没有固定的节点顺序，或者说没有一个参考节点
图经常是动态图，而且包含多模态的特征

# 图的基本概念

感恩算法竞赛，你应该大概已经懂了（有向图、无向图）

# 图的预备知识

邻接矩阵
度矩阵（如果仅已知度矩阵，不能还原出图）
- 度矩阵 $D_{i,i} = d(i)$ ， $d(i)$ 是 $i$ 的度
拉普拉斯矩阵： $L = D - A$ $L = D - A$
- 对称归一化拉普拉斯矩阵：L_{sym}=D^{-1/2}·L·D^
- 随机游走归一化拉普拉斯矩阵： $L_{rw}=D^{-1}·L$
聚类系数：描述一个节点的邻居之间有多少实际连边，相对于它们之间可能的最大连边数。取值为 $[0, 1]$ $[0, 1]$ ，连接越紧密，聚类系数越高
- C_v = \frac{2 \times E_v}
  - $E_v$ 指的是点 $v$ 的邻居之间，互相连边的边数
  - $D_v$ 是点 $v$ 的度

# GCN

$GCN~(Graph~Convolution~Network)$ 是图神经网络的开山之作，它首次将图像处理中的卷积操作用到图结构的数据处理中来。

目标：让每个节点吸收邻居的信息，更新自己的特征
关键步骤
- 收集邻居信息，把周围邻居特征加起来（或取平均）
- 加权融合，考虑邻居的数量
- 非线性变换，用激活函数让模型能学习到复杂的规律

# GCN 数学原理

单层 $GCN$ 的核心公式

$H^{l+1}=\sigma(\hat{D}^{-1/2}·\hat{A}·\hat{D}^{-1/2}·H^{(l)}·W^{(l)})$

$\hat{A}$ ：图的邻接矩阵
$\hat{D}$ ：图的度矩阵
$H^{(l)}$ ：第 $l$ 层的节点特征
$W^{(l)}$ ：可学习的权重参数
$\sigma$ ：激活函数

这个公式做了森么呢？

$\hat{D}^{-1/2}·\hat{A}·\hat{D}^{-1/2}$ ：对邻居信息做归一化处理，防止节点邻居太多导致数值爆炸
$H^{(l)}·W^{(l)}$ ：对当前节点特征做线性变换

# GCN 的缺点

$GCN$ 要把整个图放入训练，难以处理大图
$GCN$ 在训练时需要知道整个图的结构信息（包括待预测的节点）

# Transductive learning 和 Inductive learning 的对比

学习类型	关键特点	典型应用场景
直推学习（ $Transductive$ ）	训练时已知全部测试数据的结构信息（如图结构），但不知道部分标签	社交网络分群、节点分类
归纳学习（ $Inductive$ ）	训练模型后可以预测完全未见过的数据	图像分类、传统监督学习
方面	$Transductive~Learning$	$Inductive~Learning$
----------	-----------------------	---------------------
数据可见性	测试数据（不含标签）在训练时可见	测试数据完全不可见
图任务应用	节点分类、链接预测	新图分类、新节点预测
模型更新	新增节点需重新训练	可直接预测新数据
您的代码体现	用整个图训练，预测图中已有节点	需像 $GraphSAGE$ 那样采样邻居

# GraphSAGE

传统的 $GNN$ （如 $GCN$ ），在训练时，就要把整个邻居信息一次性聚合，而 $GraphSAGE~(Graph~Sample~and~Aggregate)$ 的创新便是

不需要一次性看完所有邻居
- 比如一个人有 1000 个朋友，你只取 10 个代表性的朋友来考虑。
可以采样一部分邻居，然后做聚合
可以生成节点表示，可以处理新节点（ $Inductive~learning$ ）

# GraphSAGE 数学原理

采样邻居：假设我们要更新节点 $v$ 的表示（ $embedding$ ），我们先从它的邻居 $N(v)$ 中随机采样固定数量的节点
聚合邻居信息：把邻居特征压缩成一个固定维度的邻居意见， $GraphSAGE$ $G r a p h S A G E$ 设计了多种 aggregator ，常见的有
- $Mean~aggregator$ （平均聚合）： $h_{N_s(v)}^{(k)}=mean(\{h_u^{(k-1)},\forall u \in N_s(v)\})$
- $LSTM~aggregator$ （序列聚合）： $h_{N_s(v)}^{(k)}=LSTM(\{h_u^{(k-1)},\forall u \in N_s(v)\})$
- $Pooling~aggregator$ （池化聚合）： $h_{N_s(v)}^{(k)}=max(ReLU(W·h_{u}^{(k-1)}+b),\forall u \in N_s(v))$
合并自身意见：聚合邻居信息后，把自己节点的特征和邻居的聚合结果结合起来（听朋友的意见，同时保持自己的立场，综合形成新的观点）
- $h_v^{(k)} = \sigma(W^{(k)}·CONCAT(h_v^{(k-1)}, h_{N_s(v)}^{(k)}))$ $h_{v}^{(k)} = σ (W^{(k)} \cdot C O N C A T (h_{v}^{(k - 1)}, h_{N_{s} (v)}^{(k)}))$
  - $h_v^{(k)}$ ：节点 $v$ 在第 $k$ 层的表示
  - $W^{(k)}$ ：可训练权重矩阵
堆叠多层： $GraphSAGE$ 可以堆叠多层，每层采样邻居并聚合，这样不仅能捕捉一阶邻居的信息，还能捕捉二阶、三阶甚至更远的节点信息

聚合器	数学操作	特点	适用场景
$Mean$	$mean$	简单、效率高、信息粗略	大规模图、邻居特征差异不大
$LSTM$	$LSTM$	捕捉顺序依赖、表达能力强	小规模或邻居顺序有意义
$Pooling$	$ReLU(W \cdot h_u + b) + max-pooling$	保留重要信号、特征差异大的情况好	邻居特征差异大，想强调突出特征

# GraphSAGE 的缺点

只采取固定数量的邻居，而不是使用全部邻居，可能导致信息丢失
针对 $LSTM$ 聚合，邻居顺序会导致结果不同，但在图中，邻居应该是没有顺序的，会带来不稳定性
$GraphSAGE$ 堆叠层数有限，远距离信息难以获取
采样没有考虑到不同邻居节点的重要性不同

# GAE（Graph Auto-Encoder）

# 自编码器

$Auto-Encoder~(AE)$ 通过学习数据的低维表示，尽可能重建原始输入。它的目标不是直接预测标签，而是通过压缩和解压的过程，来提取数据的潜在特征

编码器：将输入数据 $x$ 映射到低维潜在空间 $z$ ， $z = f_\theta(x)$
解码器：从潜在表示 $z$ 重建输入数据，得到 \hat
目标函数：最小化输入输出的差异，如均方误差（ $MSE$ ）等

$AE$ 的最终目的就是通过训练，找到一个最优的 $z$ ，使得我们可以通过 $z$ 来描述训练的数据
$AE$ 是在网络中自由学习，所以 $z$ 的结果可能很奇怪，可能针对训练集效果很好，但泛化能力差

# 变分自编码器

$Variational~Auto-Encoder~(VAE)$ 在 $AE$ 的基础上引入了概率图模型思想，使潜在空间具有概率分布结构，从而具备更好的生成能力。它不仅学习到一个固定的潜在向量，而是学习一个潜在分布

潜在分布假设：假设潜在变量 $z$ 服从一个先验分布，如高斯分布 $N(0, I)$
重参数化技巧：为了能够反向传播，采样过程写成 $z=\mu(x)+\sigma(x)\odot\epsilon,\quad\epsilon\sim N(0, I)$
解码器：从 $z$ 重建输入， $p_{\theta}(z\mid x) = N(z\,;\,\mu(x),\, \sigma^{2}(x)I )$ ，与 $AE$ 不同， $VAE$ 是重建分布的参数
目标函数： $\mathcal{L} = \mathbb{E}_{q_{\theta}(z\mid x)}\left[\log p_{\phi}(x\mid z)\right] - D_{\text{KL}}\left(q_{\theta}(z\mid x)\| p(z)\right)$ $L = E_{q_{θ} (z ∣ x)} [lo g p_{ϕ} (x ∣ z)] - D_{KL} (q_{θ} (z ∣ x) ∥ p (z))$
- 前半部分是对数似然，指的是还原的值和实际的值的误差
- 后半部分是为了使得还原分布尽可能接近先验分布

$VAE$ 还原了分布，它学习的是分布而不是杂乱无章的点

# GAE 原理

$GAE~(Graph~Auto-Encoder)$ 本质上是 图上的自编码器

$Encoder$ （编码器）：把节点的特征和图结构信息编码成一个低维向量
$Decoder$ （解码器）：通过这些向量，预测节点之间的连接

图神经网络