5. 图神经网络

# 什么是图神经网络（GNN）？

GNN 是一种基于图结构数据的神经网络模型，用于处理节点（ $V$ ）、边（ $E$ ）和全局（ $U$ ）信息。

# GNN 的基本步骤

GNN 的核心思想是通过迭代地聚合和更新节点信息来学习节点的表示。具体步骤如下：

收集信息： 聚合节点自身及其邻居节点的信息，有时也会聚合全局信息。这些信息会被映射到相同的维度空间。
聚合信息： 对收集到的信息进行聚合操作，例如求和、取最大值或取平均值，以得到聚合后的表示。
更新节点： 使用一个更新函数 $f$ 来整合聚合后的信息和节点自身上一层的表示，从而得到该节点在下一层的表示。

# GNN 的矩阵表示

在数学上，图通常用以下矩阵表示：

邻接矩阵 $A$ ： 描述图中节点之间的连接关系。
度矩阵 $D$ ： 一个对角矩阵，对角线上的元素是每个节点的度（即连接的边数）。
拉普拉斯矩阵 $L$ ： 定义为 $L=D-A$ 。

# 图傅里叶变换（GFT）

GNN 中的图卷积操作可以从图傅里叶变换的角度来理解。

# 图上的拉普拉斯算子

在图上，节点 $i$ 的拉普拉斯算子可以表示为：

$\Delta f_i = \sum_{j \in N_i} (f_i - f_j) = D_i f_i - \sum_{j \in N_i} f_j$

其中， $N_i$ 是节点 $i$ 的邻居集合。

以矩阵形式表示为：

$\Delta f = Lf$

图信号的总方差（或平滑度）可以表示为：

$TV(f) = f^TLf = \frac{1}{2} \sum_{i,j=1}^N A_{ij}(f(i)-f(j))^2$

# 图傅里叶变换与滤波器

图傅里叶正变换 定义为 $\hat{f} = U^Tf$ ，逆变换 定义为 $f=U\hat{f}$ 。其中， $U$ 是拉普拉斯矩阵 $L$ 的特征向量矩阵， $L = U\Lambda U^T$ 。

图傅里叶变换的谱分解性质：

$L$ 的特征值是非负的。
零特征值的个数等于图的连通子图的个数。
如果图是连通的，最小特征值为 0，其对应的特征向量为常数向量 $1$ 。
拉普拉斯矩阵的每一行元素之和为 0。

图滤波器 $h$ 在频域上与信号 $\hat{f}$ 的乘积对应于空域上的图卷积操作：

$h *_g f = U(U^Th \odot U^Tf) = Uh_\theta U^Tf = UWU^Tf$

其中， $W$ 是一个对角矩阵，对角线元素是滤波器 $h_\theta$ 的值。

基于 GFT 的卷积存在的问题：

无法跨图泛化： 滤波器依赖于图的基（即特征向量 $U$ ），这使得它无法直接应用于具有不同图结构的数据。
仅适用于无向图： 需要对称的拉普拉斯矩阵来进行特征分解，不适用于有向图。
计算复杂度高： 进行正交特征分解的计算复杂度为 $O(N^3)$ ，其中 $N$ 是节点数。

# 改进的图傅里叶变换

为了解决上述问题，研究人员提出了使用切比雪夫多项式（Chebyshev polynomial）来近似图滤波器，从而避免了特征分解。

切比雪夫多项式近似：

将滤波器 $W$ 近似为拉普拉斯矩阵特征值的多项式函数 $W = \Theta(\Lambda) = \sum_{k=0}^{K-1} \theta_k \Lambda^k$ 。因此，图卷积可以表示为：

$h *_g f = \sum_{k=0}^{K-1} \theta_k L^k f$

进一步，使用切比雪夫多项式 $T_k(L')$ 来近似 $L^k$ ，得到：

$h *_g f = \sum_{k=0}^{K-1} \theta_k T_k(L')f$

其中， $L' = 2L/\lambda_{max}-I$ ， $\lambda_{max}$ 是 $L$ 的最大特征值。

使用切比雪夫多项式近似的优势：

显著提升计算速度： 无需进行耗时的特征分解。
参数量大幅减少： 每层的参数数量是常数级别。
高效的信息捕捉： 滤波器能够捕捉 KKK-跳邻域的信息。
降低计算复杂度： 计算复杂度降至 $O(N)$ 。

完整的 GNN 传播公式：

$H^{(l+1)} = \sigma (D'^{-\frac{1}{2}}A' D'^{-\frac{1}{2}}H^{(l)}W^{(l)})$

其中， $H^{(l)}$ 是第 $l$ 层的节点特征矩阵， $\sigma$ 是激活函数， $W^{(l)}$ 是可学习的权重矩阵。 $A' = A+I$ 是加上自连接的邻接矩阵， $D'$ 是 $A'$ 的度矩阵。

# GNN 的局限性

尽管 GNN 取得了巨大成功，但仍存在一些局限性：

无法区分邻居的重要性： 在聚合过程中，简单的求和或平均操作将所有邻居视为同等重要，无法区分不同邻居对中心节点的影响。
不适用于动态图或有向图： 依赖于固定且对称的邻接矩阵。当图结构发生变化时（动态图），需要重新计算所有矩阵。此外，由于非对称矩阵的特征分解较为困难，该方法在有向图中无法很好地工作。