GCN原理详解：图卷积网络的数学推导与理论基础

图神经网络 深度学习 图卷积网络
GCN GNN
系列文章 图神经网络第 4 篇 / 共 8 篇

从基础概念到异构图与医学应用，系统掌握图神经网络的理论推导与 PyTorch 实战。

  1. 图神经网络基础概念与历史发展
  2. 循环神经网络与图神经网络的联系：从序列到图的学习
  3. 图回声状态网络(GESN)：图神经网络的重要先驱
  4. GCN原理详解：图卷积网络的数学推导与理论基础
  5. GCN实战：PyTorch实现图卷积网络
  6. 图神经网络在医学图像处理中的应用：从理论到实践
  7. 异构图神经网络与多模态学习：处理复杂图结构数据
  8. 图神经网络综述写作指南：从文献调研到论文撰写

GCN原理详解：图卷积网络的数学推导与理论基础

图卷积网络（Graph Convolutional Networks, GCN）[1]是现代图神经网络发展的里程碑，它将卷积操作成功扩展到图结构数据上。理解GCN的数学原理对于掌握图神经网络至关重要。

图信号处理基础

图的基本表示

图可以表示为 $G = (V, E)$，其中：

  • $V = {v_1, v_2, \ldots, v_n}$ 是节点集合
  • $E \subseteq V \times V$ 是边集合

邻接矩阵 $A$： \(A_{ij} = \begin{cases} 1, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}\)

度矩阵 $D$： \(D_{ii} = \sum_{j} A_{ij}\)

拉普拉斯矩阵 $L$： \(L = D - A\)

图信号

图上的信号可以表示为向量 $f \in \mathbb{R}^n$，其中 $f_i$ 表示节点 $v_i$ 的信号值 [4]。

图结构示例

考虑一个简单的图结构： \(A = \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{bmatrix}, \quad H = \begin{bmatrix} 1 & 11 \\ 2 & 22 \\ 3 & 33 \\ 4 & 44 \\ 5 & 55 \end{bmatrix}\)

其中 $A$ 是邻接矩阵，$H$ 是节点特征矩阵。

归一化拉普拉斯矩阵

为了数值稳定性，通常使用归一化拉普拉斯矩阵：

对称归一化： \(\tilde{L} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\)

随机游走归一化： \(\tilde{L}_{rw} = D^{-1} L = I - D^{-1} A\)

图卷积的数学推导

从传统卷积到图卷积

传统卷积操作可以表示为： \((f * g)(t) = \int f(\tau) g(t - \tau) d\tau\)

在图上，我们需要定义类似的卷积操作。关键思想是：图上的卷积应该保持局部性，即每个节点只与其邻居节点进行信息交换。

graph LR
    FT["图傅里叶变换<br/>f*g = U((Uᵀf)⊙(Uᵀg))"] --> CHEB["切比雪夫近似<br/>Σ θₖ Tₖ(Λ̃)"]
    CHEB --> K1["K=1 一阶近似<br/>g_θ ≈ θ₀ + θ₁Λ̃"]
    K1 --> SIMP["λ_max≈2 化简<br/>θ₀ + θ₁(Λ-I)"]
    SIMP --> FINAL["GCN 层<br/>H⁽ˡ⁺¹⁾ = σ(ÃH⁽ˡ⁾W⁽ˡ⁾)"]

图傅里叶变换

图上的傅里叶变换基于拉普拉斯矩阵的特征分解 [3]：

\[L = U \Lambda U^T\]

其中：

  • $U$ 是特征向量矩阵
  • $\Lambda$ 是特征值对角矩阵

图信号的傅里叶变换： \(\hat{f} = U^T f\)

图信号的逆傅里叶变换： \(f = U \hat{f}\)

图卷积定理

根据卷积定理，图上的卷积可以定义为 [3]： \(f * g = U((U^T f) \odot (U^T g))\)

其中 $\odot$ 表示逐元素相乘。

图卷积的简化

为了计算效率，GCN对图卷积进行了简化。假设卷积核 $g_\theta$ 是特征值的函数： \(g_\theta(\Lambda) = \text{diag}(\theta)\)

其中 $\theta \in \mathbb{R}^n$ 是参数向量。

图卷积操作变为： \(f * g_\theta = U g_\theta(\Lambda) U^T f\)

切比雪夫近似

为了进一步简化计算，使用切比雪夫多项式近似 [2]：

\[g_\theta(\Lambda) \approx \sum_{k=0}^{K-1} \theta_k T_k(\tilde{\Lambda})\]

其中：

  • $T_k$ 是切比雪夫多项式
  • $\tilde{\Lambda} = \frac{2\Lambda}{\lambda_{max}} - I$
  • $K$ 是多项式的阶数

一阶近似

当 $K=1$ 时，得到一阶近似 [2]： \(g_\theta(\Lambda) \approx \theta_0 + \theta_1 \tilde{\Lambda}\)

其中 $\tilde{\Lambda} = \frac{2\Lambda}{\lambda_{max}} - I$。

进一步假设 $\lambda_{max} \approx 2$，得到 [1]： \(g_\theta(\Lambda) \approx \theta_0 + \theta_1 (\Lambda - I)\)

GCN的最终形式

通过一系列近似和简化，GCN的最终形式为 [1]：

\[H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)})\]

其中：

  • $\tilde{A} = A + I$：添加自连接的邻接矩阵
  • $\tilde{D}{ii} = \sum_j \tilde{A}{ij}$：度矩阵
  • $H^{(l)}$：第$l$层的节点特征矩阵
  • $W^{(l)}$：第$l$层的权重矩阵
  • $\sigma$：激活函数

GCN的数学性质

自连接的重要性

问题：为什么需要自连接？[1]

答案：没有自连接时，节点无法区分”自身节点”与”无连接节点”。只使用 $A$ 的话，由于 $A$ 的对角线上都是0，所以在和特征矩阵 $H$ 相乘的时候，只会计算一个节点的所有邻居的特征的加权和，该节点本身的特征却被忽略了。

归一化的必要性

问题：为什么需要归一化？[1]

答案：$A$ 是没有经过归一化的矩阵，这样与特征矩阵 $H$ 相乘会改变特征原本的分布，所以对 $A$ 做一个标准化处理，平衡度很大的节点的重要性。

归一化公式： \(\text{Norm}A_{ij} = \frac{A_{ij}}{\sqrt{d_i}\sqrt{d_j}}\)

这来自傅里叶变换的理论，可以找到解释：知乎回答

对称归一化的优势

对称归一化 $\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$ 具有以下优势：

  1. 保持对称性：归一化后的矩阵仍然是对称的
  2. 数值稳定性：避免梯度爆炸或消失
  3. 理论保证：有良好的数学性质

GCN的层间信息传播

单层GCN的信息传播

对于单层GCN，信息传播过程为：

  1. 线性变换：$H^{(l)} W^{(l)}$
  2. 邻接聚合：$\tilde{A} (H^{(l)} W^{(l)})$
  3. 归一化：$\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} (H^{(l)} W^{(l)})$
  4. 激活：$\sigma(\cdot)$
graph LR
    HL["H⁽ˡ⁾"] --> LIN["线性变换<br/>H⁽ˡ⁾·W⁽ˡ⁾"]
    LIN --> AGG["邻居聚合<br/>÷H⁽ˡ⁾·W⁽ˡ⁾"]
    AGG --> NORM["对称归一化<br/>D̃⁻¹⸍²·Ã·D̃⁻¹⸍²"]
    NORM --> ACT["激活 σ(·)"]
    ACT --> HL1["H⁽ˡ⁺¹⁾"]

多层GCN的累积效应

多层GCN可以捕获更大范围的信息：

  • 1层GCN：每个节点只能看到直接邻居
  • 2层GCN：每个节点可以看到2跳邻居
  • k层GCN：每个节点可以看到k跳邻居

过平滑问题

随着层数增加，GCN面临过平滑问题：

现象：所有节点的表示趋于相同 原因：信息传播过程中的过度平均化 数学表达：$\lim_{l \to \infty} h_v^{(l)} = c$，其中 $c$ 是常数

GCN的变体

GraphSAGE

GraphSAGE使用不同的聚合函数：

\[h_v^{(l+1)} = \sigma(W^{(l)} \cdot \text{CONCAT}(h_v^{(l)}, \text{AGG}(\{h_u^{(l)} : u \in \mathcal{N}(v)\})))\]

GAT

图注意力网络为不同邻居分配不同权重：

\[h_v^{(l+1)} = \sigma(\sum_{u \in \mathcal{N}(v)} \alpha_{vu} W^{(l)} h_u^{(l)})\]

其中注意力权重： \(\alpha_{vu} = \frac{\exp(\text{LeakyReLU}(a^T [W^{(l)} h_v^{(l)} \| W^{(l)} h_u^{(l)}]))}{\sum_{k \in \mathcal{N}(v)} \exp(\text{LeakyReLU}(a^T [W^{(l)} h_v^{(l)} \| W^{(l)} h_k^{(l)}]))}\)

总结

GCN的成功在于：

  1. 理论基础扎实：基于图信号处理和傅里叶变换
  2. 计算效率高：通过近似简化了计算复杂度
  3. 实现简单：只需要矩阵乘法操作
  4. 效果显著：在多个任务上取得了优异性能

理解GCN的数学原理对于：

  • 设计新的图神经网络架构
  • 解决过平滑等问题
  • 优化模型性能
  • 理解图神经网络的工作原理

在下一篇文章中，我们将通过PyTorch代码实现GCN，并展示如何在实际任务中使用GCN。

参考文献

  1. Kipf, T. N., & Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017. arXiv:1609.02907
  2. Defferrard, M., Bresson, X., & Vandergheynst, P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems (NeurIPS), 2016. arXiv:1606.09375
  3. Hammond, D. K., Vandergheynst, P., & Gribonval, R. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.
  4. Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83–98, 2013.
↑
文章目录