title:”图神经网络”
data:2025-3-5
author:”朱宇阳”

深度学习-图神经网络学习笔记,欢迎访问我的主页

图神经网络概述

随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，然而语音、图像、文本都是很简单的序列或者网格数据，是很结构化的数据，深度学习很善于处理该种类型的数据。然而现实世界中并不是所有的事物都可以表示成一个序列或者一个网格，例如社交网络、知识图谱、复杂的文件系统等，也就是说很多事物都是非结构化的。

相比于简单的文本和图像，这种网络类型的非结构化的数据非常复杂，处理它的难点包括：

图的大小是任意的，图的拓扑结构复杂，没有像图像一样的空间局部性
图没有固定的节点顺序，或者说没有一个参考节点
图经常是动态图，而且包含多模态的特征

相比较于神经网络最基本的网络结构全连接层（MLP），特征矩阵乘以权重矩阵，图神经网络多了一个邻接矩阵。计算形式很简单，三个矩阵相乘再加上一个非线性变换（图3）。

因此一个比较常见的图神经网络的应用模式如下图，输入是一个图，经过多层图卷积等各种操作以及激活函数，最终得到各个节点的表示，以便于进行节点分类、链接预测、图与子图的生成等等任务。

GCN

GCN的本质目的就是用来提取拓扑图的空间特征。而图卷积神经网络主要有两类，一类是基于空间域或顶点域vertex domain(spatial domain)的，另一类则是基于频域或谱域spectral domain的。通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。所谓的两类其实就是从两个不同的角度理解，关于从空间角度的理解可以看本文的从空间角度理解GCN

一.顶点域（空间域）

基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上，它跟传统的卷积神经网络中的卷积更相似一些。在这个类别中比较有代表性的方法有

这段话主要介绍了图神经网络（GNN）中一种基于空域卷积（Spatial Convolution）的核心思想及其代表性方法。以下是对这段话的逐层解析：

1. 核心概念：空域卷积

与传统卷积的区别：
- 在传统卷积神经网络（CNN）中，卷积操作是固定在网格状数据（如图像、音频）上的局部模式匹配（通过滑动窗口提取特征）。例如，图像的卷积核会在像素的二维平面上滑动。
- 空域卷积则针对图结构数据（非欧几里得空间），将卷积操作直接定义在节点的连接关系（即图的邻接关系）上。它的核心是聚合节点及其邻居的信息，而非固定窗口内的像素。
关键特点：
- 动态邻域：每个节点的“感受野”由其邻居决定，而非固定的网格位置。
- 图同构不变性：卷积操作能适应图的拓扑结构变化（如不同形状的分子结构）。

2. 典型方法：空域卷积的代表模型

以下方法均通过不同的方式实现了空域卷积的思想：

(1) Message Passing Neural Networks (MPNN) [1]

思想：明确提出了消息传递框架（Message Passing），将节点间的信息交互建模为两步：
1. 消息传递：节点将自己的特征与邻居的特征结合，生成新的消息。
2. 聚合：节点将接收到的所有邻居的消息进行聚合（如求和、均值），更新自身特征。
优势：提供了统一的图神经网络建模范式，被许多后续研究继承（如GCN）。

(2) GraphSAGE [2]

思想：采用归纳式学习（Inductive Learning），通过聚合节点的局部邻居信息生成节点嵌入。其核心步骤包括：
1. 节点采样邻居（如随机选取固定数量的邻居）。
2. 聚合邻居特征并更新当前节点表示。
优势：
计算高效，支持大规模图的训练（如社交网络）。

(3) Diffusion Convolution Neural Networks (DCNN) [3]

思想：
将卷积操作与扩散过程（Diffusion Process）结合。通过多轮扩散（类似热传导），将节点的局部信息逐步传播到整个图，形成全局感知的特征。
数学形式：
使用图的拉普拉斯矩阵的幂次（L**k）对节点特征进行变换，隐式地模拟了信息扩散的步数 k。
优势：
明确关联了卷积操作与图的谱分解（频域方法），但计算成本较高。

(4) PATCHY-SAN [4]

思想：将图划分为若干个小块（PATCHES），并在每个小块内应用类似于CNN的局部卷积操作。具体步骤：
1. 对图进行超图划分，提取节点及其邻居组成的子图（PATCH）。
2. 在每个PATCH内对节点特征进行卷积（如权重共享的全连接层）。
3. 汇总所有PATCH的结果生成全局特征。
优势：
直接复用CNN的成熟架构，增强了对局部结构的建模能力。

二. spectral domain：频域方法（谱方法）

这就是谱域图卷积网络的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。从整个研究的时间进程来看：首先研究GSP（graph signal processing）的学者定义了graph上的Fourier Transformation，进而定义了graph上的convolution，最后与深度学习结合提出了Graph Convolutional Network。

基于频域卷积的方法则从图信号处理起家，包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7]　等。论文Semi-Supervised Classification with Graph Convolutional Networks就是一阶邻居的ChebNet。认真读到这里，脑海中应该会浮现出一系列问题：

1.基础导引

Q1 什么是Spectral graph theory？

Spectral graph theory请参考维基百科的介绍，简单的概括就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

Q2 GCN为什么要利用Spectral graph theory？这是论文（Semi-Supervised Classification with Graph Convolutional Networks）中的重点和难点，要理解这个问题需要大量的数学定义及推导

过程：

（1）定义graph上的Fourier Transformation傅里叶变换（利用Spectral graph theory，借助图的拉普拉斯矩阵的特征值和特征向量研究图的性质）

（2）定义graph上的convolution卷积

三.频域方法下图卷积网络的推导

1.拉普拉斯矩阵

拉普拉斯矩阵，主要应用在图论中，作为一个图的矩阵表示。对于图 G=(V,E)，其Laplacian 矩阵的定义为 L=D-A，

其中 L 是Laplacian 矩阵，D=diag(d)是顶点的度矩阵,对角线上元素依次为各个顶点的度，
A 是图的邻接矩阵。频域卷积的前提条件是图必须是无向图，只考虑无向图，那么L就是对称矩阵。

（1）拉普拉斯矩阵是半正定矩阵。（最小特征值大于等于0）

（2）特征值中0出现的次数就是图连通区域的个数。

（3）最小特征值是0，因为拉普拉斯矩阵（普通形式： $L=D−A$）每一行的和均为0，并且最小特征值对应的特征向量是每个值全为1的向量；

（4）最小非零特征值是图的代数连通度。

要证明拉普拉斯矩阵是半正定的，只需要证明其二次型$ f^{T} L f \geq 0 $证明：
$$
\begin{aligned}f^{T} L f &=f^{T} D f-f^{T} A f \&=f^{T} * \operatorname{diag}(d) * f-f^{T} A f \&=\sum_{i=1}^{m} d_{i} f_{i}^{2}-\sum_{j=1}^{m}\left[\sum_{i=1}^{m} f_{j} * a_{i j}\right] f_{j} \&=\sum_{i=1}^{m} d_{i} f_{i}^{2}-\sum_{i, j=1}^{m} f_{i} * f_{j} * a_{i j} \&=\frac{1}{2}\left[\sum_{i=1}^{m} d_{i} f_{i}^{2}-2 \sum_{i, j=1}^{m} f_{i} f_{j} a_{i j}+\sum_{j=1}^{m} d_{j} f_{j}^{2}\right] \&=\frac{1}{2} \sum_{i, j=1}^{m} a_{i j}\left(f_{i}-f_{j}\right)^{2}\end{aligned}
$$
所以，对于任意一个属于实向量fff都有此公式成立。

特征分解，又称谱分解是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有对可对角化矩阵或有n个线性无关的特征向量的矩阵才可以施以特征分解。不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。

拉普拉斯矩阵是半正定矩阵（半正定矩阵本身就是对称矩阵），有如下三个性质：

对称矩阵一定n个线性无关的特征向量
半正定矩阵的特征值一定非负
对阵矩阵的不同特征值对应的特征向量相互正交，这些正交的特征向量构成的矩阵为正交矩阵。
由上拉普拉斯矩阵对称知一定可以谱分解，且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为：

$L=U \Lambda U^{-1}=U \Lambda U^{-1}=U\left[\begin{array}{lll}\lambda_{1} & & & \& & \ddots & \& & \lambda_{n}\end{array}\right] U^{-1}$

其中$U=\left(\vec{u}{1}, \vec{u}{2}, \cdots, \overrightarrow{u_{n}}\right),$ 是列向量为单位特征向量的矩阵, 也就说 $\vec{u_1}$ 是列向量,$\wedge $是n个特征值构成的对角阵。由于 $U$正交矩阵, 即 $U U^{T}=E$, 所以特征分解又可以写成:$L=U \Lambda U^{-1}=U \Lambda U^{T}$

2. 拉普拉斯算子

定义：拉普拉斯算子是n维欧几里德空间中的一个二阶微分算子，定义为梯度 (∇f)(\nabla f)$(\nabla f) $的散度 (∇⋅f(\nabla \cdot f(\nabla \cdot f, 即 ∇f⋅f)\nabla f \cdot f)\nabla f $\cdot f) $。因此如果fff是二阶可微的实函数，则的拉普拉斯算子 Δ\Delta\Delta 定义为:

$$\Delta f=\nabla^{2} f=\nabla \cdot \nabla f$$

fff的拉普拉斯算子也是笛卡尔坐标系xix_ix_i中的所有非混合二阶偏导数：

$\Delta f=\sum_{i=1}^{n} \frac{\partial^{2} f}{\partial x_{i}^{2}}$

函数的拉普拉斯算子也是该函数的黑塞矩阵(是一个多元函数的二阶偏导数构成的方阵)的迹:

$\Delta f=\operatorname{tr}(H(f))$

拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导, 准确定义是：标量梯度场中的散度, 一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律，一般可以用拉普拉斯算子来描述。

3. 离散形式的一维卷积

对于定义在整数 $\mathbb{Z} $上的函数 $\mathrm{g}$, 卷积定义为

$ (f * g)(t)=\sum_{\tau=-\infty}^{\infty} f(\tau) g(t-\tau)$

所谓卷积，其实就是把一个函数卷(翻)过来，然后与另一个函数求内积。

对应到不同方面，卷积可以有不同的解释：**g 既可以看作我们在深度学习里常说的核(Kernel)，也可以对应到信号处理中的滤波器(Filter)**。而 f 可以是我们所说的机器学习中的特征(Feature)，也可以是信号处理中的信号(Signal)。f和g的卷积 (f∗g)就可以看作是对f的加权求和。下面两个动图就分别对应信号处理与深度学习中卷积操作的过程。

4. 傅里叶变换

4.1 连续形式的傅立叶变换

4.1.1 如何直观地理解傅立叶变换？

傅里叶级数：任何周期函数，只要满足一定条件都可以表示为不同频率的正弦和/或余弦之和的形式，该和成为傅里叶级数。

傅里叶变换：任何非周期函数（但该曲线下的面积是有限的），也可以用正弦和/或余弦乘以加权函数的积分来表示，在这种情况下的公式就是傅里叶变换。

傅里叶级数与傅里叶变换的关系：周期函数的周期可以趋向无穷大，这样就可以将傅里叶变换看成是傅里叶级数的推广。

4.2傅里叶级数与傅里叶变换

4.2.1 傅里叶级数的三角形式

假设 $f(x)$ 是周期为 $T$ 的函数，并且满足傅里叶级数的收敛条件，那么可以写作傅里叶级数：

$$
f(x) = \frac{a_0}{2} + \sum_{n=1}^{+\infty} \left( a_n \cos \frac{2 \pi n x}{T} + b_n \sin \frac{2 \pi n x}{T} \right)
$$

其中，系数 $a_0$、$a_n$ 和 $b_n$ 的计算公式为：

$$
\begin{gathered}
a_0 = \frac{2}{T} \int_{x_0}^{x_0 + T} f(x) , dx \
a_n = \frac{2}{T} \int_{x_0}^{x_0 + T} f(x) \cos \left( \frac{2 \pi n x}{T} \right) dx \
b_n = \frac{2}{T} \int_{x_0}^{x_0 + T} f(x) \sin \left( \frac{2 \pi n x}{T} \right) dx
\end{gathered}
$$

• $a_0$：表示函数 $f(x)$ 的平均值。
• $a_n$ 和 $b_n$：分别表示余弦和正弦分量的权重。

4.2.2 傅里叶级数的复指数形式

借助欧拉公式，可以将傅里叶级数的三角形式转换为复指数形式：

$$
f(x) = \sum_{n=-\infty}^{+\infty} c_n e^{i \frac{2 \pi n x}{T}}
$$

其中，系数 $c_n$ 的计算公式为：

$$
c_n = -\frac{1}{T} \int_{-\frac{F}{2}}^{\frac{\tau}{2}} f(x) e^{-i \frac{2 \pi n x}{T}} dx
$$

解释：
• 曲线可以理解为无数旋转的叠加，将 $f(x)$ 看作是圆周运动的组合。
• $x$ 的不断增大称为时域。

4.3、傅里叶变换

4.3.1 一维连续傅里叶变换

对于定义域为整个时间轴（$-\infty < t < +\infty$）的非周期函数 $f(x)$，无法通过周期拓延将其扩展为周期函数，此时需要用到傅里叶变换：

$$
F(u) = \int_{-\infty}^{+\infty} f(x) e^{-i 2 \pi u x} dx
$$

其中：
• $F(u)$ 是 $f(x)$ 的频域表示。
• $u$ 是频率，单位为 $1/T$。

根据傅里叶反变换公式，可以从频域恢复到时域：

$$
f(x) = \int_{-\infty}^{+\infty} F(u) e^{i 2 \pi u x} du
$$

4.3.2 傅里叶变换与傅里叶级数的关系

• 对比：
• 傅里叶级数中的 $a_n$ 和 $b_n$ 是离散的频域系数，而傅里叶变换的结果 $F(u)$ 是连续的频域表示。
• 傅里叶级数是对周期函数的分解，而傅里叶变换适用于非周期函数。

• 频率的连续化：
• 当周期 $T \to +\infty$ 时，频率 $u = 1/T$ 趋近于连续变化，因此离散的求和变为积分形式。

总结：
• 傅里叶变换的结果 $F(u)$ 实际上相当于傅里叶级数展开中的傅里叶系数。
• 傅里叶反变换公式体现了不同频率复指数函数的加权和形式，只不过这里的频率 $u$ 是连续的，因此采用了积分的形式。

$$
h_v = f\left(\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} W x_u + b\right) \quad \forall v \in \mathcal{V}
$$
1. 符号解释

节点和邻居
• $\mathcal{V}$：图中的所有节点集合。
• $\mathcal{N}(v)$：节点 $v$ 的邻居节点集合。
• $|\mathcal{N}(v)|$：节点 $v$ 的邻居节点数量（即邻居集合的大小）。

特征表示
• $x_u$：节点 $u$ 的特征向量，通常是一个 $d$ 维向量。
• $W$：可学习的权重矩阵，维度为 $d \times d’$，用于对节点特征进行线性变换。
• $b$：可学习的偏置向量，维度为 $d’$。

聚合与变换
• $\sum_{u \in \mathcal{N}(v)}$：对节点 $v$ 的所有邻居节点 $u$ 的特征进行求和。
• $\frac{1}{|\mathcal{N}(v)|}$：对邻居节点的特征求和结果进行归一化，确保聚合结果的值与邻居数量无关。

输出特征
• $h_v$：节点 $v$ 的输出特征向量，经过聚合和变换后得到。
• $f(\cdot)$：激活函数（如 ReLU），用于引入非线性。

2. 公式的含义
这个公式描述了 GCN Layer 的核心操作，主要包括以下几个步骤：

(1) 邻居特征的聚合
$$
\sum_{u \in \mathcal{N}(v)} x_u
$$
• 对节点 $v$ 的所有邻居节点 $u$ 的特征向量 $x_u$ 进行求和。
• 这一步的目的是捕捉节点 $v$ 的局部结构信息，即通过邻居节点的特征来更新节点 $v$ 的表示。

(2) 归一化
$$
\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} x_u
$$
• 将邻居节点的特征求和结果除以邻居节点的数量 $|\mathcal{N}(v)|$，进行归一化。
• 归一化的目的是避免节点特征的聚合结果受到邻居数量的影响。例如，某些节点可能有很多邻居，而另一些节点可能只有很少的邻居。

(3) 线性变换
$$
W \cdot \left(\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} x_u\right) + b
$$
• 对归一化后的邻居特征进行线性变换：
• $W$ 是可学习的权重矩阵，用于将输入特征映射到新的特征空间。
• $b$ 是可学习的偏置向量，用于调整特征的偏移。
• 这一步的目的是让模型能够学习到更复杂的特征表示。

(4) 非线性激活
$$
f\left(W \cdot \left(\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} x_u\right) + b\right)
$$
• 对线性变换的结果应用激活函数 $f(\cdot)$（如 ReLU），引入非线性。
• 非线性的引入使得模型能够捕捉更复杂的图结构信息。

(5) 输出特征
$$
h_v = f\left(\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} W x_u + b\right)
$$
• 最终得到节点 $v$ 的输出特征 $h_v$，它是节点 $v$ 及其邻居节点特征的聚合结果，经过线性变换和非线性激活后的表示。

3. 公式的特点
(1) 局部性
• 该公式只考虑了节点 $v$ 的直接邻居节点的特征，而没有考虑更远的节点。这种局部性使得 GCN 能够捕捉图的局部结构信息。

(2) 归一化
• 通过 $\frac{1}{|\mathcal{N}(v)|}$ 的归一化操作，确保了不同节点的特征聚合结果不会因为邻居数量的差异而产生偏差。

(3) 可学习性
• 权重矩阵 $W$ 和偏置向量 $b$ 是可学习的，模型能够通过训练自动调整这些参数，从而适应不同的图结构和任务。

(4) 非线性
• 激活函数 $f(\cdot)$ 的引入使得模型能够捕捉非线性的图结构特征。

4. 公式的改进与扩展
在实际应用中，GCN 的公式可能会有一些改进和扩展，例如：
(1) ChebNet（切比雪夫多项式近似）
• 使用切比雪夫多项式来近似拉普拉斯矩阵的特征值分解，从而减少计算复杂度。
• 公式形式为：
$$
h_v = f\left(\sum_{k=0}^K \theta_k T_k(\tilde{L}) x_v\right)
$$
其中 $T_k(\cdot)$ 是切比雪夫多项式，$\tilde{L}$ 是归一化的拉普拉斯矩阵。

(2) GraphSAGE
• 在 GCN 的基础上引入了采样机制，支持大规模图的训练。
• 公式形式与 GCN 类似，但邻居节点的选择是动态的。

(3) 无归一化的 GCN
• 在某些情况下，可能会去掉归一化项 $\frac{1}{|\mathcal{N}(v)|}$，直接对邻居特征求和：
$$
h_v = f\left(\sum_{u \in \mathcal{N}(v)} W x_u + b\right)
$$

这段文字主要介绍了 GraphSAGE 的背景、动机以及其核心思想，特别是它如何解决 GCN 的两个主要缺点，并引入了 Inductive Learning 和 Transductive Learning 的概念。以下是对这段文字的逐层解读：

GCN的两个缺点

在介绍 GraphSAGE 之前，先明确 GCN 的两个主要缺点：

Transductive Learning（传导学习）：
• GCN 在训练时需要输入整个图，包括训练集、验证集和测试集的所有节点。
• 在训练过程中，GCN 会利用所有节点的邻居信息来更新节点的表示，这意味着测试集和验证集的节点信息也会被用来训练模型。
• 这种方式限制了 GCN 的泛化能力，因为它无法处理图中新加入的节点。
无法处理动态图：
• GCN 的训练依赖于整个图的拓扑结构，因此当图中加入新节点或边时，需要重新训练整个模型。

1. Inductive Learning 和 Transductive Learning

为了更好地理解 GraphSAGE 的动机，需要先了解 Inductive Learning（归纳学习） 和 Transductive Learning（传导学习） 的区别：

(1) Transductive Learning

• 定义：在训练过程中，模型会看到所有的样本（包括训练集、验证集和测试集），并通过这些样本之间的关系（如图中的边）来学习节点的表示。
• GCN 的问题：
• GCN 是一个典型的 Transductive Learning 模型。
• 在训练时，GCN 会利用测试集和验证集的节点信息来更新训练集节点的表示，这会导致模型在测试集上的表现可能过于依赖训练时的特定图结构。

(2) Inductive Learning

• 定义：在训练过程中，模型只使用训练样本，训练样本和测试样本是完全分离的。
• GraphSAGE 的优势：
• GraphSAGE 是一个 Inductive Learning 框架。
• 在训练时，GraphSAGE 只使用训练样本的节点信息，而不需要访问测试集或验证集的节点。
• 这种方式使得 GraphSAGE 能够处理动态图，并且可以为图中新加入的节点生成嵌入（embedding）。

GraphSAGE 的核心思想

GraphSAGE 是为了解决 GCN 的上述问题而提出的，它的核心思想是归纳学习，即通过已知节点的信息为未知节点生成嵌入。

1.关键步骤

以下是 GraphSAGE 的两个关键步骤：

(1) Sample（采样）

• 问题：
• 在图数据中，每个节点的邻居数量可能非常不均衡。例如，某些节点可能有成百上千个邻居，而另一些节点可能只有几个邻居。
• 如果直接对所有邻居进行聚合，计算成本会非常高，尤其是当图的规模很大时。
• 解决方法：
• GraphSAGE 提出了邻居采样的方法，即在每次更新节点表示时，只随机选择一部分邻居节点进行聚合。
• 这种方式显著降低了计算复杂度，同时仍然能够捕捉到图的全局结构信息。

(2) Aggregate（聚合）

• 问题：
• 在聚合邻居节点的信息时，需要设计一种有效的机制来将这些邻居的嵌入信息整合到当前节点的表示中。
• 解决方法：
• GraphSAGE 提出了多种聚合函数（Aggregator），包括：
1. 均值聚合（Mean Aggregator）：
◦ 将邻居节点的嵌入取均值，作为当前节点的聚合结果。
2. 池化聚合（Pooling Aggregator）：
◦ 对邻居节点的嵌入进行池化操作（如最大池化、平均池化），以捕捉邻居节点的重要特征。
3. LSTM 聚合（LSTM Aggregator）：
◦ 使用 LSTM 模型对邻居节点的嵌入进行序列建模，从而捕捉邻居节点的顺序信息。
4. 注意力机制聚合（Attention Aggregator）：
◦ 使用注意力机制为每个邻居节点分配不同的权重，从而更灵活地聚合邻居信息。

2. GraphSAGE 的训练过程

GraphSAGE 的训练过程可以总结为以下几个步骤：

采样邻居节点：
• 对每个节点，随机采样一定数量的邻居节点。
聚合邻居信息：
• 使用某种聚合函数（如均值、池化、LSTM 或注意力）将邻居节点的嵌入信息整合到当前节点的表示中。
更新节点表示：
• 将聚合后的邻居信息与当前节点的特征进行结合（通常通过线性变换和非线性激活），生成新的节点表示。
预测与优化：
• 使用生成的节点表示进行预测（如节点分类、链接预测等），并通过误差反向传播优化模型参数。

3. GraphSAGE 的优点

GraphSAGE 相较于 GCN 有以下几个显著优点：

Inductive Learning：
• GraphSAGE 是一个归纳学习框架，能够处理图中新加入的节点，而不需要重新训练整个模型。
动态图支持：
• GraphSAGE 可以处理动态图，适应图中节点和边的变化。
可扩展性：
• 通过邻居采样，GraphSAGE 显著降低了计算复杂度，适合大规模图数据。

4. 总结

• GCN 的局限性：
• GCN 是一个传导学习模型，训练时需要访问整个图，无法处理动态图和新加入的节点。
• GraphSAGE 的创新：
• GraphSAGE 是一个归纳学习框架，通过邻居采样和聚合机制，能够高效地为图中新加入的节点生成嵌入。
• GraphSAGE 的核心：
• Sample：对邻居节点进行采样。
• Aggregate：聚合邻居节点的信息。

如果需要进一步探讨 GraphSAGE 的具体实现或与其他图神经网络模型的对比，请随时告诉我！

公式结构

$$
\alpha_{i,j} = \frac{\exp\left(\text{LeakyReLU}\left(\vec{a}^T [W\vec{h}_i | W\vec{h}j]\right)\right)}{\sum{k \in N_i} \exp\left(\text{LeakyReLU}\left(\vec{a}^T [W\vec{h}_i | W\vec{h}_k]\right)\right)}
$$

关键步骤解析

线性变换（共享权重）
• 每个节点 $i$ 和其邻居节点 $j$ 的原始特征 $\vec{h}_i$ 和 $\vec{h}_j$ 通过共享的权重矩阵 $W$ 进行线性变换，得到 $W\vec{h}_i$ 和 $W\vec{h}_j$。
• 作用：将原始特征映射到高维空间，增强表达能力。
拼接与注意力得分计算
• 将变换后的特征拼接为 $[W\vec{h}_i | W\vec{h}_j]$（维度从 $d$ 变为 $2d$）。
• 通过可学习的参数向量 $\vec{a}$（维度 $2d$）与拼接向量做点积，得到标量注意力得分：
$$
\text{Score}(i,j) = \vec{a}^T [W\vec{h}_i | W\vec{h}_j]
$$
• 作用：衡量节点 $i$ 和 $j$ 之间的相关性。
非线性激活与归一化
• 对得分应用 LeakyReLU 激活函数（允许负值输入，缓解梯度消失）。
• 通过 Softmax 归一化：
$$
\alpha_{i,j} = \frac{\exp(\text{LeakyReLU}(\text{Score}(i,j)))}{\sum_{k \in N_i} \exp(\text{LeakyReLU}(\text{Score}(i,k)))}
$$
• 作用：归一化权重，使 $\sum_{j \in N_i} \alpha_{i,j} = 1$。

关键点说明

共享参数
• 权重矩阵 $W$ 和参数向量 $\vec{a}$ 对所有节点共享，减少参数量并增强模型泛化能力。
分母修正
• 原公式分母可能存在笔误，正确的求和项应为 $\sum_{k \in N_i} \exp(\text{LeakyReLU}(\vec{a}^T [W\vec{h}_i | W\vec{h}_k]))$，即用 $k$ 替换 $j$，确保归一化时遍历所有邻居节点。
注意力机制的优势
• 动态分配权重：根据节点特征自适应学习连接重要性，优于预定义的图结构权重（如邻接矩阵）。
• 局部性：仅计算节点与其邻居的权重，复杂度为 $O(|E|)$，适合大规模图数据。

示例计算

假设节点 $i$ 的邻居为 ${j, k, l}$，特征维度 $d=2$，则计算过程如下：

对每个邻居 $j, k, l$，计算 $W\vec{h}_i$ 和 $W\vec{h}_j$，并拼接为 $4$ 维向量。
通过 $\vec{a}^T$ 计算得分，应用 LeakyReLU。
对得分取指数并归一化：
$$
\alpha_{i,j} = \frac{\exp(s_{i,j})}{\exp(s_{i,j}) + \exp(s_{i,k}) + \exp(s_{i,l})}
$$

应用场景

该公式用于图注意力网络的 消息传递 阶段，节点 $i$ 的新特征为其邻居特征的加权和：
$$
\vec{h}i’ = \sigma\left(\sum{j \in N_i} \alpha_{i,j} W \vec{h}_j\right)
$$
其中 $\sigma$ 是非线性激活函数（如 ReLU）。

通过这一机制，图注意力网络能够显式建模节点间关系，适用于节点分类、链接预测等任务。

DiffPool 详解：层次化图池化赋能图分类任务

背景与问题

传统的图分类方法通常在图神经网络（GNN）后接全局池化（如求和、平均等），将所有节点嵌入压缩为一个向量。然而，这种做法忽略了图中潜在的层级结构，例如分子中的官能团或社交网络中的社区，导致模型难以捕捉多层次特征。DiffPool（Differentiable Pooling）由斯坦福团队提出，通过可微的层次化池化，逐步将细粒度节点聚合成粗粒度簇，构建多层抽象表示，显著提升图分类性能。

核心思想

DiffPool 的核心是逐层粗化图结构，每层包含两个关键操作：

分配矩阵生成：动态决定当前层节点如何分配到下一层的簇。
图结构更新：根据分配结果，生成下一层的节点特征和邻接矩阵。

通过堆叠多层，图从局部到全局的层级特征被逐层提取，最终通过顶层全局池化得到图的整体表示。

分层池化步骤

1. 分配矩阵生成（关键：可微与动态）

• 输入：当前层的节点特征 $X^{(l)} \in \mathbb{R}^{N_l \times d}$ 和邻接矩阵 $A^{(l)} \in \mathbb{R}^{N_l \times N_l}$（$N_l$ 为当前层节点数）。

• 过程：使用一个独立的GNN（称为 GNN_pool）生成分配矩阵 $S^{(l)} \in \mathbb{R}^{N_l \times N_{l+1}}$，其中 $N_{l+1}$ 是下一层的簇数：
$$
S^{(l)} = \text{softmax}\left(\text{GNN}_\text{pool}(X^{(l)}, A^{(l)})\right)
$$
• softmax 按行归一化，确保每个节点分配到各簇的概率和为1。

• GNN_pool 学习节点到簇的映射关系，例如通过注意力机制或消息传递。

2. 节点特征聚合（粗化特征）

• 下一层节点特征：将当前层特征按簇加权聚合：
$$
X^{(l+1)} = {S^{(l)}}^T \cdot \left(\text{GNN}_\text{embed}(X^{(l)}, A^{(l)})\right)
$$
• GNN_embed：另一个GNN，用于更新节点特征，增强当前层的表示能力。

• ${S^{(l)}}^T \cdot (\cdot)$ 表示按簇分配权重求和，得到粗粒度特征。

3. 邻接矩阵更新（粗化连接）

• 下一层邻接矩阵：计算簇之间的连接强度：
$$
A^{(l+1)} = {S^{(l)}}^T \cdot A^{(l)} \cdot S^{(l)}
$$
• 若原图中节点 $i$ 和 $j$ 相连，则它们所属的簇 $c_i$ 和 $c_j$ 的连接强度累加 $S_{i,c_i} \cdot A_{i,j} \cdot S_{j,c_j}$。

训练与优化

• 端到端训练：所有GNN（GNN_pool 和 GNN_embed）与分类器共同训练。
• 正则化项：
• 链路预测损失：鼓励相邻节点分配到同一簇：
$$
\mathcal{L}\text{LP} = | A^{(l)} - S^{(l)} \cdot {S^{(l)}}^T |F
$$
• 熵正则化：防止分配矩阵过于稀疏或稠密：
$$
\mathcal{L}\text{Entropy} = -\frac{1}{N_l} \sum{i=1}^{N_l} \sum{c=1}^{N{l+1}} S_{i,c}^{(l)} \log S_{i,c}^{(l)}
$$
• 总损失：分类损失 + $\lambda_1 \mathcal{L}_\text{LP} + \lambda_2 \mathcal{L}_\text{Entropy}$。

示例流程

以分子图分类为例（层级：原子 → 官能团 → 分子）：

第1层：原始原子节点，GNN提取原子特征。
第1次池化：GNN_pool 将原子分配到官能团簇，生成粗化特征和邻接矩阵。
第2层：官能团作为节点，GNN学习官能团间相互作用。
第2次池化：进一步聚合成分子整体表示，输入分类器预测标签。

优势与挑战

• 优势：
• 层次化表示：显式建模图的层级结构，适合复杂图数据。
• 端到端可微：无需预定义池化规则，适应多种任务。
• 灵活整合：可与任意GNN架构（如GCN、GAT）结合。

• 挑战：
• 计算开销：矩阵乘法复杂度为 $O(N^2)$，大规模图受限。
• 超参数敏感：需预设每层簇数 $N_{l+1}$，影响模型表现。
• 训练稳定性：多任务损失需精细调参。

title:”图神经网络”data:2025-3-5author:”朱宇阳”