为什么需要图神经网络
传统深度学习主要处理规则结构的数据：
然而，现实世界中大量数据具有非欧几里得结构：
这些数据天然适合用图（Graph）表示，需要专门的图神经网络（Graph Neural Networks, GNN）来处理。
图的基本定义
图$G$由节点（顶点）和边组成：
$$G = (V, E)$$
其中：
图的类型：
1. 有向图/无向图：边是否有方向
2. 加权图/无权图：边是否有权重
3. 同构图/异构图：节点和边是否只有一种类型
4. 静态图/动态图：图结构是否随时间变化
图的特征表示：
与传统深度学习的差异：
1.3.1 从CNN到GCN
CNN在图像上的成功源于：
将CNN思想扩展到图：
1.3.2 频域图卷积
基于谱图理论，图卷积可以定义为频域的乘法。
图傅里叶变换：
归一化的拉普拉斯矩阵：
$$L = I_n - D^{-1/2}AD^{-1/2}$$
其中$D$是度矩阵，$D_{ii} = \sum_j A_{ij}$
对$L$进行特征分解：$L = U\Lambda U^T$，其中$U$是特征向量矩阵。
图傅里叶变换：$\hat{x} = U^T x$
谱域卷积：
$$x *_{G} g = U((U^T g) \odot (U^T x)) = U g_{\theta} U^T x$$
其中$g_{\theta}$是频域滤波器。
计算复杂度问题：
1.3.3 简化：Kipf & Welling的GCN
使用切比雪夫多项式近似，并限制在一阶，得到简化的GCN：
$$H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$$
其中：
归一化的直观理解：
$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$对邻接矩阵进行对称归一化：
GCN的传播规则可以写成：
$$h_i^{(l+1)} = \sigma\left(\sum_{j \in \mathcal{N}(i) \cup \{i\}} \frac{1}{\sqrt{\tilde{d}_i\tilde{d}_j}} h_j^{(l)} W^{(l)}\right)$$
其中$\tilde{d}_i$是加入自连接后的度数。
1.3.4 GCN的特点与局限
特点：
局限：
1.4.1 动机
GCN对所有邻居使用相同的权重，这在实际中可能不够灵活：
图注意力网络引入注意力机制，让模型学习邻居的权重。
1.4.2 GAT的注意力机制
计算注意力系数：
$$e_{ij} = \text{LeakyReLU}(a^T[Wh_i || Wh_j])$$
其中：
Softmax归一化：
$$\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \exp(e_{ik})}$$
聚合：
$$h_i' = \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij} Wh_j\right)$$
1.4.3 多头注意力
与Transformer类似，GAT使用多头注意力增加表达能力：
$$h_i' = \mathop{||}\limits_{k=1}^{K} \sigma\left(\sum_{j \in \mathcal{N}(i)} \alpha_{ij}^{(k)} W^{(k)} h_j\right)$$
最后层使用平均：
$$h_i' = \sigma\left(\frac{1}{K}\sum_{k=1}^{K} \sum_{j \in \mathcal{N}(i)} \alpha_{ij}^{(k)} W^{(k)} h_j\right)$$
1.4.4 GAT的优势
1. 灵活性：不同邻居有不同的权重
2. 可解释性：注意力权重可以可视化
3. 效率：与GCN类似的计算复杂度
4. 通用性：可以处理有向图（只关注入边）
1.5.1 归纳式学习
GCN和GAT是直推式（Transductive）的：
GraphSAGE（Sample and Aggregate）支持归纳式（Inductive）学习：
1.5.2 GraphSAGE的核心思想
采样（Sample）：
聚合（Aggregate）：
1.5.3 聚合函数
Mean Aggregator：
$$h_{\mathcal{N}(i)}^{(l)} = \text{mean}(\{h_j^{(l-1)}, \forall j \in \mathcal{N}(i)\})$$
类似于GCN，但先聚合再变换。
LSTM Aggregator：
$$h_{\mathcal{N}(i)}^{(l)} = \text{LSTM}(\text{shuffle}(\{h_j^{(l-1)}, \forall j \in \mathcal{N}(i)\}))$$
表达能力更强，但需要打乱邻居顺序以保持置换不变性。
Pooling Aggregator：
$$h_{\mathcal{N}(i)}^{(l)} = \max(\{\sigma(W_{pool}h_j^{(l-1)} + b), \forall j \in \mathcal{N}(i)\})$$
逐元素最大池化，可以学习每个维度的重要性。
1.5.4 节点表示生成
$$h_i^{(l)} = \sigma(W^{(l)} \cdot [h_i^{(l-1)} || h_{\mathcal{N}(i)}^{(l)}])$$
拼接自身表示和邻居聚合表示，进行线性变换和非线性激活。
1.5.5 无监督训练
GraphSAGE可以使用无监督损失训练：
$$J = -\log(\sigma(z_i^T z_j)) - Q \cdot \mathbb{E}_{v_n \sim P_n} \log(\sigma(-z_i^T z_n))$$
1.6.1 表达能力问题
GNN的表达能力受限于其区分不同图结构的能力。研究发现：
1.6.2 Weisfeiler-Lehman测试
WL测试是一种迭代的图同构检测算法：
1. 初始时，每个节点有相同的标签（或特征）
2. 每轮迭代：节点的新标签 = hash(原标签, 邻居标签多重集)
3. 若多轮后两个图的标签分布不同，则判定为非同构
WL测试可以区分大多数但非全部非同构图。
1.6.3 GIN的设计
GIN（Graph Isomorphism Network）被证明与WL测试一样强大。
更新公式：
$$h_i^{(k)} = \text{MLP}^{(k)}((1 + \epsilon^{(k)}) \cdot h_i^{(k-1)} + \sum_{j \in \mathcal{N}(i)} h_j^{(k-1)})$$
关键设计：
为什么求和更强大：
平均和最大池化会丢失邻居多重集的信息。例如：
1.7.1 图池化的作用
对于图级别的任务（如分子属性预测、图分类），需要将节点表示聚合成图表示。
1.7.2 简单池化方法
全局平均池化：
$$h_G = \frac{1}{n} \sum_{i=1}^n h_i$$
全局最大池化：
$$h_G = \max_{i=1}^n h_i$$
全局求和池化：
$$h_G = \sum_{i=1}^n h_i$$
这些简单方法的问题是：丢失图的层次结构信息。
1.7.3 层次化图池化
DIFFPOOL：
学习节点的软分配矩阵：
$$S^{(l)} = \text{softmax}(GNN_{pool}(A^{(l)}, X^{(l)}))$$
$$X^{(l+1)} = S^{(l)^T} Z^{(l)}, \quad Z^{(l)} = GNN_{embed}(A^{(l)}, X^{(l)})$$
$$A^{(l+1)} = S^{(l)^T} A^{(l)} S^{(l)}$$
通过迭代粗化，构建图的层次化表示。
SAGPool（Self-Attention Graph Pooling）：
基于自注意力选择重要节点：
$$y = \text{GNN}(A, X), \quad \text{idx} = \text{topk}(y, k)$$
$$X' = X_{idx} \odot \tanh(y_{idx}), \quad A' = A_{idx, idx}$$
1.7.4 读出（Readout）函数
结合不同层次的表示：
$$h_G = \text{READOUT}(\{h_i^{(l)} | l \in L, i \in V\})$$
常用READOUT包括拼接、求和、平均，以及更复杂的注意力机制。
1.8.1 时空图神经网络
处理动态变化的图：
ST-GCN：
DCRNN：
1.8.2 异构图神经网络
处理多种节点和边类型的图：
HAN（Heterogeneous Graph Attention Network）：
RGCN（Relational GCN）：
1.8.3 大规模图训练
邻居采样：
采样效率：
题目：给定一个3节点无向图，邻接矩阵$A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$，节点特征$H = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}$，权重矩阵$W = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$（单位矩阵简化）。计算GCN一层后的特征。
分析过程：
步骤1：添加自连接
$$\tilde{A} = A + I = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix}$$
步骤2：计算度矩阵
$$\tilde{D} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2 \end{bmatrix}$$
步骤3：计算归一化矩阵
$$\tilde{D}^{-1/2} = \begin{bmatrix} 1/\sqrt{2} & 0 & 0 \\ 0 & 1/\sqrt{3} & 0 \\ 0 & 0 & 1/\sqrt{2} \end{bmatrix}$$
$$\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$$
逐元素计算：
$$\hat{A} \approx \begin{bmatrix} 0.5 & 0.408 & 0 \\ 0.408 & 0.333 & 0.408 \\ 0 & 0.408 & 0.5 \end{bmatrix}$$
步骤4：GCN传播
$$H^{(1)} = \hat{A}HW = \hat{A}H$$
$$= \begin{bmatrix} 0.5 & 0.408 & 0 \\ 0.408 & 0.333 & 0.408 \\ 0 & 0.408 & 0.5 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}$$
节点1： $$h_1^{(1)} = [0.5 \times 1 + 0.408 \times 0 + 0 \times 1,\; 0.5 \times 0 + 0.408 \times 1 + 0 \times 1]$$ $$= [0.5, 0.408]$$
节点2： $$h_2^{(1)} = [0.408 \times 1 + 0.333 \times 0 + 0.408 \times 1,\; 0.408 \times 0 + 0.333 \times 1 + 0.408 \times 1]$$ $$= [0.816, 0.741]$$
节点3： $$h_3^{(1)} = [0 \times 1 + 0.408 \times 0 + 0.5 \times 1,\; 0 \times 0 + 0.408 \times 1 + 0.5 \times 1]$$ $$= [0.5, 0.908]$$
结论： $$H^{(1)} \approx \begin{bmatrix} 0.5 & 0.408 \\ 0.816 & 0.741 \\ 0.5 & 0.908 \end{bmatrix}$$
可以看到每个节点的特征变成了自身和邻居特征的加权平均。
题目：在GAT中，节点$i$的特征$h_i = [1, 0]$，邻居$j_1$的特征$h_{j_1} = [0, 1]$，邻居$j_2$的特征$h_{j_2} = [1, 1]$。设$W = I$（单位矩阵），注意力参数$a = [1, 1, 1, 1]^T$（拼接后）。使用LeakyReLU（负斜率0.2）计算$\alpha_{ij_1}$和$\alpha_{ij_2}$。
分析过程：
步骤1：线性变换
由于$W = I$：
步骤2：拼接
步骤3：计算注意力分数
$e_{ij} = \text{LeakyReLU}(a^T[Wh_i || Wh_j])$
对于$j_1$： $$e_{ij_1} = \text{LeakyReLU}([1,1,1,1] \cdot [1,0,0,1])$$ $$= \text{LeakyReLU}(1 + 0 + 0 + 1) = \text{LeakyReLU}(2) = 2$$
对于$j_2$： $$e_{ij_2} = \text{LeakyReLU}([1,1,1,1] \cdot [1,0,1,1])$$ $$= \text{LeakyReLU}(1 + 0 + 1 + 1) = \text{LeakyReLU}(3) = 3$$
步骤4：Softmax归一化
$$\alpha_{ij_1} = \frac{\exp(2)}{\exp(2) + \exp(3)} = \frac{7.389}{7.389 + 20.086} = \frac{7.389}{27.475} \approx 0.269$$
$$\alpha_{ij_2} = \frac{\exp(3)}{\exp(2) + \exp(3)} = \frac{20.086}{27.475} \approx 0.731$$
结论：
节点$i$更关注邻居$j_2$，因为其特征与$i$有重叠（第一个维度都是1）。
题目：在GraphSAGE中，节点$i$的特征$h_i = [2, 1]$，有两个邻居$j_1$和$j_2$，特征分别为$h_{j_1} = [1, 2]$和$h_{j_2} = [3, 0]$。使用Mean Aggregator，计算聚合后的邻居表示$h_{\mathcal{N}(i)}$和更新后的$h_i'$。
分析过程：
步骤1：邻居聚合（Mean）
$$h_{\mathcal{N}(i)} = \text{mean}(\{h_{j_1}, h_{j_2}\}) = \frac{h_{j_1} + h_{j_2}}{2}$$
$$= \frac{[1, 2] + [3, 0]}{2} = \frac{[4, 2]}{2} = [2, 1]$$
步骤2：拼接与变换
假设权重矩阵$W = \begin{bmatrix} 1 & 0 & 0.5 & 0 \\ 0 & 1 & 0 & 0.5 \end{bmatrix}$（将4维输入映射到2维输出）
拼接自身和邻居表示： $$[h_i || h_{\mathcal{N}(i)}] = [2, 1, 2, 1]$$
线性变换： $$h_i' = W \cdot [h_i || h_{\mathcal{N}(i)}]^T$$
$$= \begin{bmatrix} 1 & 0 & 0.5 & 0 \\ 0 & 1 & 0 & 0.5 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \\ 2 \\ 1 \end{bmatrix}$$
$$= [1 \times 2 + 0 \times 1 + 0.5 \times 2 + 0 \times 1,\; 0 \times 2 + 1 \times 1 + 0 \times 2 + 0.5 \times 1]$$
$$= [2 + 0 + 1 + 0,\; 0 + 1 + 0 + 0.5]$$
$$= [3, 1.5]$$
步骤3：激活函数
应用ReLU（假设）： $$h_i' = \text{ReLU}([3, 1.5]) = [3, 1.5]$$
结论：
有趣的是，在这个例子中，邻居的平均特征恰好等于节点自身的特征，导致信息融合后特征增强。
1. GCN中的归一化$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$的主要目的是：
A. 加速计算 B. 防止高度节点主导 C. 增加参数量 D. 支持有向图
2. GAT与GCN的主要区别是：
A. GAT使用注意力机制 B. GAT层数更深 C. GAT只能处理小图 D. GAT不能处理节点特征
3. GraphSAGE支持什么类型的学习？
A. 只支持直推式 B. 只支持归纳式 C. 同时支持直推式和归纳式 D. 不支持任何学习
4. GIN使用什么聚合方式以达到与WL测试相同的表达能力？
A. 平均 B. 最大池化 C. 求和 D. LSTM
5. 以下哪个不是图池化的目的？
A. 节点级别预测 B. 图级别表示 C. 层次化特征学习 D. 减少图规模
6. 图神经网络处理的三种预测任务是$\_\_\_\_\_$预测、$\_\_\_\_\_$预测和$\_\_\_\_\_$预测。
7. GCN的全称是$\_\_\_\_\_$，GAT的全称是$\_\_\_\_\_$。
8. 在GCN中，$\tilde{A} = A + I$表示在邻接矩阵中添加了$\_\_\_\_\_$。
9. GraphSAGE的两个核心步骤是$\_\_\_\_\_$和$\_\_\_\_\_$。
10. WL测试的全称是$\_\_\_\_\_$测试，用于检测图同构。
11. 给定2节点图的邻接矩阵$A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$，计算$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$。
12. 某节点有3个邻居，注意力分数分别为1, 2, 3，计算softmax归一化后的注意力权重。
13. 节点特征为$[1, 2]$，两个邻居特征为$[2, 1]$和$[0, 3]$，使用mean聚合后拼接，求聚合结果（仅计算聚合，不进行线性变换）。
一、选择题答案：
1. 答案：B
解析：对称归一化考虑了邻居节点的度数，避免高度节点主导信息传播。
2. 答案：A
解析：GAT引入注意力机制，允许不同邻居有不同的权重，比GCN更灵活。
3. 答案：C
解析：GraphSAGE学习可泛化的聚合函数，既可以在训练图上直推，也可以泛化到新图。
4. 答案：C
解析：GIN证明使用求和聚合可以达到WL测试的表达能力上限。
5. 答案：A
解析：图池化用于图级别预测、层次化学习和图粗化，节点预测不需要池化。
二、填空题答案：
6. 答案：节点级别；边级别；图级别
解析：GNN可以执行三种不同粒度的预测任务。
7. 答案：Graph Convolutional Network；Graph Attention Network
解析：两种经典的图神经网络架构。
8. 答案：自连接（或自环）
解析：添加自连接确保节点在聚合时考虑自身特征。
9. 答案：采样（Sample）；聚合（Aggregate）
解析：GraphSAGE的名称即来源于这两个步骤。
10. 答案：Weisfeiler-Lehman
解析：WL测试是图同构检测的经典算法，也是GNN表达能力的上限。
三、计算题答案：
11. 解答：
$\tilde{A} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$
$\tilde{D} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$
$\tilde{D}^{-1/2} = \begin{bmatrix} 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} \end{bmatrix}$
$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} = \begin{bmatrix} 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} \end{bmatrix}$
$= \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{bmatrix} \begin{bmatrix} 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} \end{bmatrix}$
$= \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix}$
12. 解答：
$\exp(1) = 2.718$，$\exp(2) = 7.389$，$\exp(3) = 20.086$
和 $= 2.718 + 7.389 + 20.086 = 30.193$
$\alpha_1 = 2.718 / 30.193 \approx 0.090$
$\alpha_2 = 7.389 / 30.193 \approx 0.245$
$\alpha_3 = 20.086 / 30.193 \approx 0.665$
权重：$[0.090, 0.245, 0.665]$
13. 解答：
邻居聚合：$\text{mean} = \frac{[2,1] + [0,3]}{2} = \frac{[2,4]}{2} = [1, 2]$
拼接自身和邻居：$[1, 2, 1, 2]$
聚合结果：$[1, 2, 1, 2]$