为什么需要图神经网络
传统深度学习主要处理规则结构的数据:
然而,现实世界中大量数据具有非欧几里得结构:
这些数据天然适合用图(Graph)表示,需要专门的图神经网络(Graph Neural Networks, GNN)来处理。
图的基本定义
图$G$由节点(顶点)和边组成:
$$G = (V, E)$$
其中:
图的类型:
图的特征表示:
与传统深度学习的差异:
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.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测试是一种迭代的图同构检测算法:
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]$$
结论:
有趣的是,在这个例子中,邻居的平均特征恰好等于节点自身的特征,导致信息融合后特征增强。
一、选择题答案:
二、填空题答案:
三、计算题答案: