与几何深度学习)
5.5 图神经网络(GNN)与几何深度学习
学习目标
掌握图神经网络的核心原理与消息传递机制，理解GNN在结构化数据上的优势，学习主流GNN架构的设计思想，了解几何深度学习的基本概念，能够将GNN应用于实际图结构数据问题。
一、图结构数据：非欧几里得空间的挑战
1.1 从规则数据到图结构数据
传统神经网络的数据假设
- 图像：规则网格，局部相邻，平移不变性
- 文本：序列顺序，固定长度
- 音频：时间序列，一维连续
图结构数据的特性
图G=(V,E)G = (V, E)G=(V,E)，其中VVV是节点集合，EEE是边集合。
核心特征：
- 不规则拓扑：每个节点具有不同的连接数
- 置换不变性：节点顺序不影响图结构
- 多尺度结构：局部到全局的层级关系
- 异构性：节点/边类型多样，属性丰富
1.2 图数据的常见类型
按连接性质分类
| 图类型 | 特点 | 应用示例 |
|---|---|---|
| 无向图 | 边无方向 | 社交网络（好友关系） |
| 有向图 | 边有方向 | 引用网络（论文引用） |
| 加权图 | 边有权重 | 交通网络（道路流量） |
| 多关系图 | 多种边类型 | 知识图谱（实体关系） |
| 动态图 | 随时间演化 | 社交网络演变 |
| 异构图 | 多种节点类型 | 推荐系统（用户-商品） |
按规模分类
- 小规模图：分子图（几十个节点）
- 中等规模图：蛋白质相互作用（数千节点）
- 大规模图：社交网络（百万节点+）
- 极大规模图：互联网链接图（十亿节点+）
1.3 图表示学习的基本问题
节点级别任务
- 节点分类：预测节点类别（用户画像）
- 节点回归：预测节点数值（蛋白质功能强度）
- 链接预测：预测边是否存在（好友推荐）
- 节点聚类：发现节点社区（社交圈子）
图级别任务
- 图分类：预测整个图的类别（分子毒性）
- 图回归：预测图的数值属性（分子性质）
- 图生成：生成新图（药物分子设计）
- 图匹配：比较图相似度（蛋白质结构比对）
1.4 传统图机器学习方法回顾
基于谱的方法
- 拉普拉斯特征映射：保留局部邻域关系的降维
- 图傅里叶变换：在谱域定义图卷积
基于游走的方法
- DeepWalk：通过随机游走生成节点序列，应用Skip-gram
- Node2Vec：带偏置的随机游走，平衡BFS和DFS
基于矩阵分解的方法
- 图分解：将邻接矩阵分解为低维表示
局限性：
- 浅层模型：无法学习深层特征
- 不可扩展：难以处理动态图和大规模图
- 泛化能力差：无法迁移到新图结构
二、图神经网络基础：消息传递框架
2.1 消息传递范式
图神经网络的核心是消息传递（Message Passing），包含三个关键步骤：
消息传递的三个阶段
消息生成（Message）：从邻居节点生成消息
[
m_{ij}^{(l)} = \phi{(l)}\left(h_i{(l)}, h_j^{(l)}, e_{ij}\right)
]消息聚合（Aggregate）：聚合来自邻居的消息
[
m_i^{(l)} = \bigoplus_{j \in \mathcal{N}(i)} m_{ij}^{(l)}
]节点更新（Update）：结合自身特征和聚合消息更新节点表示
[
h_i^{(l+1)} = \psi{(l)}\left(h_i{(l)}, m_i^{(l)}\right)
]
其中：
- hi(l)h_i^{(l)}hi(l)：节点iii在第lll层的表示
- eije_{ij}eij：边(i,j)(i,j)(i,j)的特征
- N(i)\mathcal{N}(i)N(i)：节点iii的邻居集合
- ϕ\phiϕ：消息函数
- ⨁\bigoplus⨁：聚合函数（如sum、mean、max）
- ψ\psiψ：更新函数
2.2 图神经网络的表达能力
WL图同构测试
Weisfeiler-Lehman图同构测试是衡量GNN表达能力的理论基准。
WL算法步骤：
- 初始化：为每个节点分配标签（如节点度数）
- 迭代：
a. 聚合邻居标签的多重集
b. 哈希聚合结果为新标签 - 直到标签稳定或达到最大迭代
GNN与WL等价性
- 1-WL测试：大多数GNN的表达能力不超过1-WL测试
- 高阶GNN：通过考虑高阶结构（如子图）增强表达能力
- 理论界限：消息传递GNN无法区分某些非同构图
提升表达能力的策略
- 位置编码：注入节点在图中的位置信息
- 子图编码：考虑节点所在的局部子结构
- 高阶消息传递：考虑k-hop邻居或路径信息
- 等变网络：保证对称性的同时增强表达能力
三、经典图神经网络架构
3.1 图卷积网络（GCN）
频域视角：谱图卷积
GCN基于图谱理论，将卷积定义为傅里叶域的乘积。
图拉普拉斯矩阵：
[
L = D - A
]
其中DDD为度矩阵，AAA为邻接矩阵。
归一化拉普拉斯：
[
\tilde{L} = I - D{-1/2}AD{-1/2}
]
谱卷积：
[
g_\theta \star x = U g_\theta(\Lambda) U^T x
]
其中UUU是LLL的特征向量矩阵，Λ\LambdaΛ是特征值对角矩阵。
空域视角：一阶近似
为了计算效率，GCN使用切比雪夫多项式的一阶近似：
GCN传播规则：
[
H^{(l+1)} = \sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)
]
其中：
- A~=A+I\tilde{A} = A + IA~=A+I（添加自环）
- D~ii=∑jA~ij\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}D~ii=∑jA~ij
- H(l)H^{(l)}H(l)：第lll层节点特征矩阵
- W(l)W^{(l)}W(l)：可学习权重矩阵
- σ\sigmaσ：激活函数（如ReLU）
GCN代码实现
importtorchimporttorch.nnasnnimporttorch.nn.functionalasFclassGCNLayer(nn.Module):"""GCN层实现"""def__init__(self,in_features,out_features,bias=True):super().__init__()self.linear=nn.Linear(in_features,out_features,bias=bias)defforward(self,x,adj):""" x: 节点特征矩阵 (n_nodes, in_features) adj: 归一化的邻接矩阵 (n_nodes, n_nodes) """# 线性变换x=self.linear(x)# (n_nodes, out_features)# 邻域聚合x=torch.spmm(adj,x)# 稀疏矩阵乘法returnxclassGCN(nn.Module):"""两层GCN模型"""def__init__(self,n_features,hidden_dim,n_classes,dropout=0.5):super()
