差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 深度学习:图神经网络 [2026/03/02 20:29] – 创建 张叶安 | 深度学习:图神经网络 [2026/03/02 22:51] (当前版本) – 张叶安 | ||
|---|---|---|---|
| 行 8: | 行 8: | ||
| 传统深度学习主要处理规则结构的数据: | 传统深度学习主要处理规则结构的数据: | ||
| - | - **图像**:规则的2D网格,可以使用CNN | + | |
| - | - **文本**:一维序列,可以使用RNN或Transformer | + | - **文本**:一维序列,可以使用RNN或Transformer |
| - | - **表格**:独立的样本向量,可以使用全连接网络 | + | - **表格**:独立的样本向量,可以使用全连接网络 |
| 然而,现实世界中大量数据具有**非欧几里得结构**: | 然而,现实世界中大量数据具有**非欧几里得结构**: | ||
| - | - **社交网络**:用户及其关系 | + | |
| - | - **分子结构**:原子和化学键 | + | - **分子结构**:原子和化学键 |
| - | - **知识图谱**:实体和关系 | + | - **知识图谱**:实体和关系 |
| - | - **推荐系统**:用户-物品交互 | + | - **推荐系统**:用户-物品交互 |
| - | - **交通网络**:道路和交叉口 | + | - **交通网络**:道路和交叉口 |
| 这些数据天然适合用**图(Graph)**表示,需要专门的图神经网络(Graph Neural Networks, GNN)来处理。 | 这些数据天然适合用**图(Graph)**表示,需要专门的图神经网络(Graph Neural Networks, GNN)来处理。 | ||
| 行 28: | 行 28: | ||
| 其中: | 其中: | ||
| - | - $V = \{v_1, v_2, ..., v_n\}$:节点集合,$|V| = n$ | + | |
| - | - $E \subseteq V \times V$:边集合,$|E| = m$ | + | - $E \subseteq V \times V$:边集合,$|E| = m$ |
| - | - $A \in \{0, 1\}^{n \times n}$:邻接矩阵,$A_{ij} = 1$表示存在边$(v_i, | + | - $A \in \{0, 1\}^{n \times n}$:邻接矩阵,$A_{ij} = 1$表示存在边$(v_i, |
| **图的类型**: | **图的类型**: | ||
| 1. **有向图/ | 1. **有向图/ | ||
| + | |||
| 2. **加权图/ | 2. **加权图/ | ||
| + | |||
| 3. **同构图/ | 3. **同构图/ | ||
| + | |||
| 4. **静态图/ | 4. **静态图/ | ||
| + | |||
| **图的特征表示**: | **图的特征表示**: | ||
| - | - **节点特征**:$X \in \mathbb{R}^{n \times d}$,每个节点有$d$维特征 | + | |
| - | - **边特征**:$E_{feat} \in \mathbb{R}^{m \times d_e}$,每条边有特征 | + | - **边特征**:$E_{feat} \in \mathbb{R}^{m \times d_e}$,每条边有特征 |
| - | - **图级别特征**:整个图的全局特征 | + | - **图级别特征**:整个图的全局特征 |
| ==== 1.2 图神经网络的挑战 ==== | ==== 1.2 图神经网络的挑战 ==== | ||
| 行 49: | 行 53: | ||
| **与传统深度学习的差异**: | **与传统深度学习的差异**: | ||
| - | 1. **不规则结构**: | + | - |
| - | | + | - 每个节点的邻居数量不同 |
| - | | + | - 没有固定的空间顺序 |
| - | | + | - 无法直接使用卷积或池化操作 |
| - | 2. **置换不变性**: | + | - **置换不变性**: |
| - | | + | - 图的节点没有固有顺序 |
| - | | + | - 改变节点编号不应改变结果 |
| - | | + | - 需要满足$f(PAP^T, |
| - | 3. **多尺度信息**: | + | - |
| - | | + | - 节点级别的预测 |
| - | | + | - 边级别的预测 |
| - | | + | - 图级别的预测 |
| - | 4. **计算效率**: | + | - **计算效率**: |
| - | | + | - 大规模图(百万甚至十亿节点) |
| - | | + | - 稀疏邻接矩阵的高效处理 |
| ==== 1.3 图卷积网络(GCN) ==== | ==== 1.3 图卷积网络(GCN) ==== | ||
| 行 73: | 行 77: | ||
| CNN在图像上的成功源于: | CNN在图像上的成功源于: | ||
| - | - 局部连接:每个像素只与邻居交互 | + | |
| - | - 权重共享:卷积核在所有位置共享 | + | - 权重共享:卷积核在所有位置共享 |
| - | - 多层结构:捕获多尺度特征 | + | - 多层结构:捕获多尺度特征 |
| 将CNN思想扩展到图: | 将CNN思想扩展到图: | ||
| - | - 局部连接:每个节点聚合邻居信息 | + | |
| - | - 权重共享:所有节点使用相同的聚合函数 | + | - 权重共享:所有节点使用相同的聚合函数 |
| - | - 多层结构:扩大感受野,捕获高阶邻居信息 | + | - 多层结构:扩大感受野,捕获高阶邻居信息 |
| **1.3.2 频域图卷积** | **1.3.2 频域图卷积** | ||
| 行 89: | 行 93: | ||
| 归一化的拉普拉斯矩阵: | 归一化的拉普拉斯矩阵: | ||
| + | |||
| $$L = I_n - D^{-1/ | $$L = I_n - D^{-1/ | ||
| 行 104: | 行 109: | ||
| **计算复杂度问题**: | **计算复杂度问题**: | ||
| - | - 特征分解$O(n^3)$ | + | |
| - | - 与$U$相乘$O(n^2)$ | + | - 与$U$相乘$O(n^2)$ |
| - | - 对于大规模图不可行 | + | - 对于大规模图不可行 |
| **1.3.3 简化:Kipf & Welling的GCN** | **1.3.3 简化:Kipf & Welling的GCN** | ||
| 行 115: | 行 120: | ||
| 其中: | 其中: | ||
| - | - $\tilde{A} = A + I_n$:加入自连接的邻接矩阵 | + | |
| - | - $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$:对应的度矩阵 | + | - $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$:对应的度矩阵 |
| - | - $H^{(l)}$:第$l$层的节点特征 | + | - $H^{(l)}$:第$l$层的节点特征 |
| - | - $W^{(l)}$:可学习的权重矩阵 | + | - $W^{(l)}$:可学习的权重矩阵 |
| - | - $\sigma$:激活函数 | + | - $\sigma$:激活函数 |
| **归一化的直观理解**: | **归一化的直观理解**: | ||
| $\tilde{D}^{-1/ | $\tilde{D}^{-1/ | ||
| - | - 考虑邻居节点的度数,避免高度节点主导 | + | |
| - | - 保持数值稳定性 | + | - 保持数值稳定性 |
| **GCN的传播规则可以写成**: | **GCN的传播规则可以写成**: | ||
| 行 136: | 行 141: | ||
| **特点**: | **特点**: | ||
| - | - 半监督学习:少量标签即可训练 | + | |
| - | - 局部化:每个节点只聚合邻居信息 | + | - 局部化:每个节点只聚合邻居信息 |
| - | - 置换不变:矩阵运算保持置换等价性 | + | - 置换不变:矩阵运算保持置换等价性 |
| **局限**: | **局限**: | ||
| - | - 过度平滑(Over-smoothing):层数增加时,节点表示趋于一致 | + | |
| - | - 难以捕获远距离依赖 | + | - 难以捕获远距离依赖 |
| - | - 无法处理有向图和边特征 | + | - 无法处理有向图和边特征 |
| ==== 1.4 图注意力网络(GAT) ==== | ==== 1.4 图注意力网络(GAT) ==== | ||
| 行 150: | 行 155: | ||
| GCN对所有邻居使用相同的权重,这在实际中可能不够灵活: | GCN对所有邻居使用相同的权重,这在实际中可能不够灵活: | ||
| - | - 不同邻居的重要性可能不同 | + | |
| - | - 需要显式建模节点间的关系强度 | + | - 需要显式建模节点间的关系强度 |
| 图注意力网络引入**注意力机制**,让模型学习邻居的权重。 | 图注意力网络引入**注意力机制**,让模型学习邻居的权重。 | ||
| 行 162: | 行 167: | ||
| 其中: | 其中: | ||
| - | - $W$:线性变换矩阵 | + | |
| - | - $a$:注意力参数向量 | + | - $a$:注意力参数向量 |
| - | - $||$:向量拼接 | + | - $||$:向量拼接 |
| - | - 只计算邻居节点$j \in \mathcal{N}(i)$的$e_{ij}$ | + | - 只计算邻居节点$j \in \mathcal{N}(i)$的$e_{ij}$ |
| **Softmax归一化**: | **Softmax归一化**: | ||
| 行 188: | 行 193: | ||
| 1. **灵活性**:不同邻居有不同的权重 | 1. **灵活性**:不同邻居有不同的权重 | ||
| + | |||
| 2. **可解释性**:注意力权重可以可视化 | 2. **可解释性**:注意力权重可以可视化 | ||
| + | |||
| 3. **效率**:与GCN类似的计算复杂度 | 3. **效率**:与GCN类似的计算复杂度 | ||
| + | |||
| 4. **通用性**:可以处理有向图(只关注入边) | 4. **通用性**:可以处理有向图(只关注入边) | ||
| 行 197: | 行 205: | ||
| GCN和GAT是**直推式(Transductive)**的: | GCN和GAT是**直推式(Transductive)**的: | ||
| - | - 需要所有节点在训练时可见 | + | |
| - | - 无法处理新加入的节点 | + | - 无法处理新加入的节点 |
| GraphSAGE(Sample and Aggregate)支持**归纳式(Inductive)**学习: | GraphSAGE(Sample and Aggregate)支持**归纳式(Inductive)**学习: | ||
| - | - 学习节点特征的聚合函数 | + | |
| - | - 可以泛化到未见过的节点和图 | + | - 可以泛化到未见过的节点和图 |
| **1.5.2 GraphSAGE的核心思想** | **1.5.2 GraphSAGE的核心思想** | ||
| **采样(Sample)**: | **采样(Sample)**: | ||
| - | - 对每个节点,采样固定数量的邻居 | + | |
| - | - 避免大图的全局计算 | + | - 避免大图的全局计算 |
| - | - 控制每批次的计算量 | + | - 控制每批次的计算量 |
| **聚合(Aggregate)**: | **聚合(Aggregate)**: | ||
| - | - 使用聚合函数融合邻居信息 | + | |
| - | - 聚合函数必须对输入顺序不敏感(置换不变) | + | - 聚合函数必须对输入顺序不敏感(置换不变) |
| **1.5.3 聚合函数** | **1.5.3 聚合函数** | ||
| 行 247: | 行 255: | ||
| $$J = -\log(\sigma(z_i^T z_j)) - Q \cdot \mathbb{E}_{v_n \sim P_n} \log(\sigma(-z_i^T z_n))$$ | $$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 图同构网络(GIN) ==== | ==== 1.6 图同构网络(GIN) ==== | ||
| 行 255: | 行 263: | ||
| GNN的表达能力受限于其区分不同图结构的能力。研究发现: | GNN的表达能力受限于其区分不同图结构的能力。研究发现: | ||
| - | - GCN、GraphSAGE等无法区分某些非同构图 | + | |
| - | - 它们的表达能力上限是**Weisfeiler-Lehman(WL)图同构测试**的一阶形式 | + | - 它们的表达能力上限是**Weisfeiler-Lehman(WL)图同构测试**的一阶形式 |
| **1.6.2 Weisfeiler-Lehman测试** | **1.6.2 Weisfeiler-Lehman测试** | ||
| 行 263: | 行 271: | ||
| 1. 初始时,每个节点有相同的标签(或特征) | 1. 初始时,每个节点有相同的标签(或特征) | ||
| + | |||
| 2. 每轮迭代:节点的新标签 = hash(原标签, | 2. 每轮迭代:节点的新标签 = hash(原标签, | ||
| + | |||
| 3. 若多轮后两个图的标签分布不同,则判定为非同构 | 3. 若多轮后两个图的标签分布不同,则判定为非同构 | ||
| 行 277: | 行 287: | ||
| 关键设计: | 关键设计: | ||
| - | - 使用求和(sum)而非平均或最大池化 | + | |
| - | - 可学习的参数$\epsilon$调整自连接权重 | + | - 可学习的参数$\epsilon$调整自连接权重 |
| - | - MLP提供足够的非线性能力 | + | - MLP提供足够的非线性能力 |
| **为什么求和更强大**: | **为什么求和更强大**: | ||
| 平均和最大池化会丢失邻居多重集的信息。例如: | 平均和最大池化会丢失邻居多重集的信息。例如: | ||
| - | - 邻居集合$\{1, | + | |
| - | - 但它们的和不同(3 vs 3),如果考虑更多维度可以区分 | + | - 但它们的和不同(3 vs 3),如果考虑更多维度可以区分 |
| ==== 1.7 图池化与图级别预测 ==== | ==== 1.7 图池化与图级别预测 ==== | ||
| 行 346: | 行 356: | ||
| **ST-GCN**: | **ST-GCN**: | ||
| - | - 空间维度:GCN聚合邻居 | + | |
| - | - 时间维度:1D卷积聚合时间序列 | + | - 时间维度:1D卷积聚合时间序列 |
| **DCRNN**: | **DCRNN**: | ||
| - | - 使用扩散卷积捕获空间依赖 | + | |
| - | - 使用Seq2Seq建模时间序列 | + | - 使用Seq2Seq建模时间序列 |
| **1.8.2 异构图神经网络** | **1.8.2 异构图神经网络** | ||
| 行 358: | 行 368: | ||
| **HAN(Heterogeneous Graph Attention Network)**: | **HAN(Heterogeneous Graph Attention Network)**: | ||
| - | - 基于元路径(meta-path)定义邻居 | + | |
| - | - 节点级和语义级的双重注意力 | + | - 节点级和语义级的双重注意力 |
| **RGCN(Relational GCN)**: | **RGCN(Relational GCN)**: | ||
| - | - 每种边类型有独立的权重矩阵 | + | |
| - | - 或使用基分解减少参数量 | + | - 或使用基分解减少参数量 |
| **1.8.3 大规模图训练** | **1.8.3 大规模图训练** | ||
| **邻居采样**: | **邻居采样**: | ||
| - | - Node-wise:GraphSAGE方式 | + | |
| - | - Layer-wise:FastGCN,每层独立采样 | + | - Layer-wise:FastGCN,每层独立采样 |
| - | - Graph-wise:Cluster-GCN,基于图聚类 | + | - Graph-wise:Cluster-GCN,基于图聚类 |
| **采样效率**: | **采样效率**: | ||
| - | - 小批量训练,减少内存 | + | |
| - | - 控制邻居数量,避免邻居爆炸 | + | - 控制邻居数量,避免邻居爆炸 |
| ===== 2. 例题分析 ===== | ===== 2. 例题分析 ===== | ||
| 行 399: | 行 409: | ||
| 逐元素计算: | 逐元素计算: | ||
| - | - $\hat{A}_{11} = \frac{1}{\sqrt{2}} \cdot 1 \cdot \frac{1}{\sqrt{2}} = 0.5$ | + | |
| - | - $\hat{A}_{12} = \frac{1}{\sqrt{2}} \cdot 1 \cdot \frac{1}{\sqrt{3}} = \frac{1}{\sqrt{6}} \approx 0.408$ | + | - $\hat{A}_{12} = \frac{1}{\sqrt{2}} \cdot 1 \cdot \frac{1}{\sqrt{3}} = \frac{1}{\sqrt{6}} \approx 0.408$ |
| - | - $\hat{A}_{22} = \frac{1}{\sqrt{3}} \cdot 1 \cdot \frac{1}{\sqrt{3}} = 1/3 \approx 0.333$ | + | - $\hat{A}_{22} = \frac{1}{\sqrt{3}} \cdot 1 \cdot \frac{1}{\sqrt{3}} = 1/3 \approx 0.333$ |
| - | - 其他类似计算 | + | - 其他类似计算 |
| $$\hat{A} \approx \begin{bmatrix} 0.5 & 0.408 & 0 \\ 0.408 & 0.333 & 0.408 \\ 0 & 0.408 & 0.5 \end{bmatrix}$$ | $$\hat{A} \approx \begin{bmatrix} 0.5 & 0.408 & 0 \\ 0.408 & 0.333 & 0.408 \\ 0 & 0.408 & 0.5 \end{bmatrix}$$ | ||
| 行 438: | 行 448: | ||
| 由于$W = I$: | 由于$W = I$: | ||
| - | - $Wh_i = [1, 0]$ | + | |
| - | - $Wh_{j_1} = [0, 1]$ | + | - $Wh_{j_1} = [0, 1]$ |
| - | - $Wh_{j_2} = [1, 1]$ | + | - $Wh_{j_2} = [1, 1]$ |
| **步骤2:拼接** | **步骤2:拼接** | ||
| - | - $[Wh_i || Wh_{j_1}] = [1, 0, 0, 1]$ | + | |
| - | - $[Wh_i || Wh_{j_2}] = [1, 0, 1, 1]$ | + | - $[Wh_i || Wh_{j_2}] = [1, 0, 1, 1]$ |
| **步骤3:计算注意力分数** | **步骤3:计算注意力分数** | ||
| 行 466: | 行 476: | ||
| **结论**: | **结论**: | ||
| - | - $\alpha_{ij_1} \approx 0.269$ | + | |
| - | - $\alpha_{ij_2} \approx 0.731$ | + | - $\alpha_{ij_2} \approx 0.731$ |
| 节点$i$更关注邻居$j_2$,因为其特征与$i$有重叠(第一个维度都是1)。 | 节点$i$更关注邻居$j_2$,因为其特征与$i$有重叠(第一个维度都是1)。 | ||
| 行 507: | 行 517: | ||
| **结论**: | **结论**: | ||
| - | - 聚合后的邻居表示:$h_{\mathcal{N}(i)} = [2, 1]$ | + | |
| - | - 更新后的节点表示:$h_i' | + | - 更新后的节点表示:$h_i' |
| 有趣的是,在这个例子中,邻居的平均特征恰好等于节点自身的特征,导致信息融合后特征增强。 | 有趣的是,在这个例子中,邻居的平均特征恰好等于节点自身的特征,导致信息融合后特征增强。 | ||
| 行 548: | 行 558: | ||
| ==== 二、填空题 ==== | ==== 二、填空题 ==== | ||
| - | 6. 图神经网络处理的三种预测任务是________预测、________预测和________预测。 | + | 6. 图神经网络处理的三种预测任务是$\_\_\_\_\_$预测、$\_\_\_\_\_$预测和$\_\_\_\_\_$预测。 |
| - | 7. GCN的全称是________,GAT的全称是________。 | + | 7. GCN的全称是$\_\_\_\_\_$,GAT的全称是$\_\_\_\_\_$。 |
| - | 8. 在GCN中,$\tilde{A} = A + I$表示在邻接矩阵中添加了________。 | + | 8. 在GCN中,$\tilde{A} = A + I$表示在邻接矩阵中添加了$\_\_\_\_\_$。 |
| - | 9. GraphSAGE的两个核心步骤是________和________。 | + | 9. GraphSAGE的两个核心步骤是$\_\_\_\_\_$和$\_\_\_\_\_$。 |
| - | 10. WL测试的全称是________测试,用于检测图同构。 | + | 10. WL测试的全称是$\_\_\_\_\_$测试,用于检测图同构。 |
| ==== 三、计算题 ==== | ==== 三、计算题 ==== | ||
| 行 606: | 行 616: | ||
| 11. **解答:** | 11. **解答:** | ||
| | | ||
| - | | + | $\tilde{A} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ |
| | | ||
| - | | + | $\tilde{D} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}$ |
| | | ||
| - | | + | $\tilde{D}^{-1/ |
| | | ||
| - | | + | $\tilde{D}^{-1/ |
| | | ||
| - | | + | $= \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. **解答:** | 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, |
| 13. **解答:** | 13. **解答:** | ||
| | | ||
| - | | + | 邻居聚合:$\text{mean} = \frac{[2,1] + [0,3]}{2} = \frac{[2, |
| | | ||
| - | | + | 拼接自身和邻居:$[1, |
| | | ||
| - | | + | 聚合结果:$[1, |