图神经网络基础

什么是图神经网络

在学会神经网络[4]——图神经网络中我们实现了GCN和GAT两种网络，但是我们在此之前从未详细叙述过图神经网络，所以我们本期就要填上这个坑

在以前我们学过的神经网络都是传统MP结构，按照某种特定的顺序进行组合，比如全连接神经网络和卷积神经网络，那么我们不得不好奇一点，为什么神经网络可以学会知识呢？我们可以大致分为以下几点：

非线性转换：

• 激活函数引入非线性，使神经网络能够学习和表示复杂的非线性关系。如果没有激活函数，神经网络的每一层都只是简单的线性变换，最终整个网络只是一个线性变换，无论有多少层。

增加表达能力：

• 激活函数使网络能够处理复杂的数据，捕捉更细致的特征。例如，ReLU（Rectified Linear Unit）函数能够有效地处理稀疏数据和高维特征。

分段学习：

• 激活函数允许网络在不同区域应用不同的线性函数，从而在整个输入空间中实现分段线性近似。这意味着网络可以在不同输入区域中学习不同的特征。

梯度传播：

• 激活函数对梯度传播至关重要。某些激活函数（如ReLU）在计算梯度时具有简单而有效的特性，使得反向传播算法更高效，并且可以缓解梯度消失问题。

数据标准化：

• 某些激活函数（如Sigmoid和Tanh）有助于将输入标准化到某个范围内（如[0, 1]或[-1, 1]），这可以帮助稳定训练过程并提高收敛速度。

启用复杂决策边界：

• 通过引入非线性，神经网络可以形成复杂的决策边界，从而在分类任务中实现更高的准确性。简单的线性模型无法在高维空间中实现复杂的分割，而非线性激活函数使得这种复杂性成为可能。

那么我们不得不好奇，图神经网络与传统神经网络的区别是什么，我们对比以下两者的数据结构、层结构、应用场景来分析一下：

数据结构：

• 传统神经网络通常处理固定形状的结构化数据，如表格数据（前馈神经网络）或图像数据（卷积神经网络）。
• 输入数据一般是固定大小的矩阵或向量。

层结构：

• 传统神经网络由一系列全连接层、卷积层、池化层等组成。
• 层之间的连接通常是固定的，不依赖于数据的结构。

应用场景：

• 主要用于图像分类、自然语言处理、时间序列预测等任务。
• 适用于数据维度和结构固定的情况。

感受野：

• 卷积神经网络（CNN）通过卷积核在局部区域进行操作，有效捕捉局部特征。

与之不同的图神经网络确是：

数据结构：

• 图神经网络专门处理图结构数据，其中数据由节点（vertices）和边（edges）组成。
• 输入数据是一个图，其中节点可以有特征向量，边可以有权重。

层结构：

• GNN中的层是基于图的结构进行设计的，常见的层包括图卷积层、图注意力层等。
• 层之间的连接依赖于图的结构，通过邻居节点的信息聚合来更新节点表示。

应用场景：

• 广泛应用于社交网络分析、推荐系统、分子图建模、交通网络等任务。
• 适用于数据结构灵活多变且具有复杂关系的情况。

信息传递：

• GNN通过节点之间的信息传递来更新节点的表示，通常采用消息传递机制（message passing）。
• 每一层通过聚合节点及其邻居节点的信息来更新节点特征。

---

既然如此我们来说一下图神经网络的传递过程，图神经网络的前向传播主要有两步：

1. 消息传递（Message Passing）：

   • 每个节点从其邻居节点接收信息（消息）。
   • 这些消息通常是邻居节点的特征，通过某种聚合函数进行聚合。

2. 信息聚合（Aggregation）：

   • 聚合函数将邻居节点的信息聚合成一个表示，常用的聚合函数包括求和、平均或最大值等。

   • 例如，对于节点 ( v ) 和其邻居节点集 $\mathcal{N}(v) $，聚合函数可以表示为：

     $$h_{\mathcal{N}(v)}^{(k)} = \text{AGGREGATE}(\{ h_u^{(k-1)} : u \in \mathcal{N}(v) \})$$

     其中，$h_u^{(k-1)} $表示第 k-1 层中邻居节点 u 的特征，$ h_{\mathcal{N}(v)}^{(k)} $是聚合后的邻居节点特征。

而在顺利传递出参数后就需要自身进行节点的更新，他需要：

• 使用聚合后的邻居节点特征和当前节点的特征来更新节点的表示。

• 更新函数通常是一个可微函数。一般表示为：

  $$h_v^{(k)} = \sigma (W^{(k)} \cdot h_{\mathcal{N}(v)}^{(k)} + b^{(k)})$$

  其中，$ W^{(k)} $是第k层的权重矩阵，$b^{(k)}$ 是偏置向量，$\sigma$ 是激活函数。

前向传播这个过程需要反复执行，这样我们就可以获得稳定输出的序列了，而反向传播过程我们通过BP网络反向推导一下就有：

假设损失函数为$ \mathcal{L}$，它可以是负对数似然损失（nll_loss）也可以是其他的比如L1或者多标签边界损失（收敛性相对来讲比MSE好的多）

1. 反向传播（Backpropagation）：

   • 计算损失函数对每个参数的梯度。
   • 对于每一层的权重矩阵 $ W^{(k)}$，梯度计算公式为：
   • $$\frac{\partial \mathcal{L}}{\partial W^{(k)}} = \sum_{v \in \mathcal{V}} \frac{\partial \mathcal{L}}{\partial h_v^{(k)}} \cdot \frac{\partial h_v^{(k)}}{\partial W^{(k)}}$$

     其中，$ \mathcal{V} $ 是图的节点集合。

2. 参数更新（Parameter Update）：

   • 使用梯度下降或其变种（如Adam优化器）更新参数。
   • 更新公式为： $$W^{(k)} \leftarrow W^{(k)} - \eta \cdot \frac{\partial \mathcal{L}}{\partial W^{(k)}}$$ 其中，$ \eta $ 是学习率。

最后在基础板块说一下在使用图神经网络时应该注意的事项：

• 使用自己的数据集时应该对节点特征和边进行归一化，可以加速收敛
• 图尽量是个连通图，不能过于稀疏或者密集，可以使用数据结构的相关算法比如剪枝或者图采样
• 如果图过大一定要采样处理
• 使用跳跃连接和层归一化来缓解梯度消失和过平滑问题。

图卷积神经网络

图神经网络通过邻居节点的表征和节点自身的表征完成更新，我们可以将图写作一整个邻接矩阵用于表示一个图，在图神经网络里面的图都是自环的，所以邻接矩阵的副对角线都是1。我们叫邻接矩阵为A，那么自环邻接矩阵为：

$$\hat A = A + I$$

假设每个节点的表征我们可以用一个向量表达，整个图的节点间存在权重，那么整个图就是一个非0的权重矩阵，我们叫他H。最开始的H等于输入X，那么我们可以把图神经网络的更新看作两步：

• 汇总：从各个节点的信息汇总到一起
• 聚合：将信息表征到新的节点上

对于我们的GCN也是一样的道理。GCN是在做卷积，傅里叶变换是特殊的拉普拉斯变换，所以我们求卷积可以求矩阵的拉普拉斯变换。下面给出传递公式：

$$H_i^k=\sigma(\hat D^{-\frac{1}{2}}\hat A \hat D^{-\frac{1}{2}}H^kW^k)$$

也可以写作节点式：

$$h_v^{(l)} = \sum_{u \in \mathcal{N}(v) \cup \{v\}} \frac{1}{\sqrt{d_v d_u}} h_u^{(l-1)} W^{(l-1)}$$

其中矩阵D也叫做角度矩阵，它的主对角线元素为A矩阵行的和，其他位置都是0，可以写作：

$$\hat D_{ii}=\sum_j\hat A_{ij}$$

更新节点数据也显得尤为重要，我们可以写作：

$$H_i^k=\sigma(\sum_{j∈{N(i)∪i}}\frac{\hat A_{ij}}{\sqrt{\hat D_{ii}\hat D_{ij}}}H_j^{k-1}W^k)$$

提出最后的i项可以得到：

$$H_i^k=\sigma(\sum_{j∈{N(i)}}\frac{\hat A_{ij}}{\sqrt{\hat D_{ii}\hat D_{ij}}}H_j^{k-1}W^k)+\frac{1}{\hat D_{i}}H_i^{k-1}W^k$$

这就是节点更新公式。那么我们为什么需要D这个奇怪的矩阵呢？很简单卷积就是傅里叶变换，而傅里叶是特殊的拉普拉斯，所以我们这个D就是起到拉普拉斯算子的近似值作用，接下来证明一下：

令傅里叶算子F：

$$F_\theta=diag(\theta)$$

数学上有：

$$F_\theta*x=UF_\theta U^Tx$$

其中U代表归一化的图拉普拉斯矩阵的特征线了矩阵，即：

$$L=I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$$ $$L=U\Lambda U^T$$

到此我们需要近似计算一下，众所周知，直接计算的代价很大（代码也会很大）所以我们需要使用切比雪夫多项式进行近似计算。

$$F_{\theta'}(\Lambda)=\sum_{k=0}^K\theta_{k}'T_k(\hat \Lambda)$$

其中的T就是k次展开切比雪夫多项式，我们重新写一下卷积得到：

$$F_\theta*x=\sum_{k=0}^K\theta_{k}'T_k(\hat L)x$$

---

其中的L为：

$$\hat L = \frac{2}{\lambda_{max}}L-I$$

我们可以看出每个节点只与K阶邻域内的节点信息有关。我们化简并最终得到：

$$F_\theta*x≈\theta(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$$

其中的D特征值很小，我们需要进一步稳定，所以我们需要给节点套上自环以确保不会梯度爆炸：

$$H=\hat D^{-\frac{1}{2}}\hat A \hat D^{-\frac{1}{2}}XW$$

其中的W是信息矩阵，X为输入信号。到此我们做出了充分的解释。图神经网络拥有较强的扩展性、可解释性和鲁棒性。所以才能受到如此青睐。

接下来说一下GCN的反向传播过程：

我们假定损失函数为交叉熵，写作：

$$\mathcal{L} = - \sum_{v \in \mathcal{L}} \sum_{c=1}^{C} y_{vc} \log(\hat{y}_{vc})$$

输出梯度为：

$$\delta^{(i)} = \frac{\partial \mathcal{L}}{\partial H^{(i)}} = H^{(i)} - Y$$

我们向前计算，每次都乘以当前层的梯度H即可。

$$\frac{\partial \mathcal{L}}{\partial W^{(i)}} = (H^{(i)})^T \delta^{(i+1)}$$

然后利用这个梯度我们就可以更新每一层的参数了。

图注意力网络

图注意力网络也叫GAT，传递过程与之前的很类似大概可以分为：

1. 输入特征：每个节点有一个特征向量 $\mathbf{h}_i $。

2. 线性变换：对每个节点的特征进行线性变换，得到投影特征：

   $$\mathbf{h}_i' = \mathbf{W} \mathbf{h}_i$$

   其中，W 是可学习的权重矩阵。

3. 计算注意力分数：对于每对邻居节点 (i) 和 (j)，计算它们之间的注意力分数：

   $$e_{ij} = \text{LeakyReLU} (\mathbf{a}^T [\mathbf{h}_i' \| \mathbf{h}_j'])$$

   其中，a 是可学习的权重向量， || 表示向量连接操作。

4. 归一化注意力分数：使用softmax函数对注意力分数进行归一化，得到注意力权重：

   $$\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \exp(e_{ik})}$$

   其中，N(i) 表示节点 i 的邻居节点集合。

5. 聚合邻居信息：使用注意力权重对邻居节点的特征进行加权求和，得到更新后的节点特征：

   $$\mathbf{h}_i^{(l+1)} = \sigma \left( \sum_{j \in \mathcal{N}(i)} \alpha_{ij} \mathbf{h}_j' \right)$$

   其中，$\sigma$ 是激活函数，如ReLU。

注意力学习方式（Learning Attention Weights）

GAT通过端到端的方式学习注意力权重，这些权重是可学习的参数，通过反向传播进行优化。具体步骤如下：

1. 初始化：初始化注意力权重向量a 和线性变换矩阵W。
2. 前向传播：
   • 计算每对节点的注意力分数。
   • 通过softmax对注意力分数进行归一化，得到注意力权重。
   • 根据注意力权重对邻居节点的特征进行加权求和。
3. 损失计算：
   • 计算模型的预测误差，例如使用交叉熵损失。
4. 反向传播和参数更新：
   • 计算损失函数对注意力权重和线性变换矩阵的梯度。
   • 使用优化算法更新注意力权重和其他参数。

图消息网络

图消息网络也叫GMPN，传递过程与一般的GCN一样都是下面的过程：

消息传递（Message Passing）：

• 每个节点从其邻居节点接收消息。
• 消息可以是节点的特征向量或通过某种变换后的特征。

消息聚合（Message Aggregation）：

• 将接收到的消息进行聚合，例如求和、平均或最大化。
• 聚合函数可以是简单的求和或更复杂的神经网络。

节点更新（Node Update）：

• 使用聚合后的消息更新节点的特征表示。

1—WL同构测试

1-WL也叫1维同构测试，WL全名叫：Weisfeiler-Lehman，测试过程如下：

初始化：

• 在图神经网络中，节点特征初始化通常由节点的属性或度决定。

消息传递和聚合：

• 图神经网络在每一层执行类似于1-WL测试的消息传递和聚合操作，每个节点接收来自其邻居节点的特征信息，并更新自身的特征。

特征更新：

• GNN通过可学习的参数（如权重矩阵和激活函数）更新节点特征，类似于1-WL测试中的颜色更新过程。

迭代：

• 图神经网络通常包含多层结构，每层执行一次消息传递和特征更新操作，相当于1-WL测试中的迭代过程。

作业

这里留一个作业，大家阅读一下下面的pdf，我们下期可能会做出解读：