图卷积网络 (GCN)

图卷积网络（Graph Convolutional Network, GCN）是由 Kipf & Welling 在 2017 年提出的半监督节点分类方法。它将卷积操作从规则的网格数据（图像）推广到了任意拓扑结构的图数据上，是图神经网络（GNN）领域最具影响力的基础工作之一。

学习路线： 图的基本概念 → 谱域图卷积 → ChebNet → GCN 简化 → 空间域理解 → GNN 变体 (GraphSAGE, GAT, GIN)

背景与动机

为什么需要图神经网络

深度学习在过去十年取得了巨大成功，但成功的领域有一个共同特点：数据具有规则结构。

CNN 处理网格数据（图像是像素的二维网格）
RNN / Transformer 处理序列数据（文本是 token 的一维序列）

然而，现实世界中大量数据天然以图（Graph）的形式存在：

场景	节点	边
社交网络	用户	好友关系
分子结构	原子	化学键
知识图谱	实体	关系
引文网络	论文	引用关系
交通网络	路口	道路

这些数据的邻居数量不固定、节点没有天然的排序、拓扑结构不规则，CNN 和 RNN 的核心假设（局部性 + 平移不变性、时序性）都不再适用。我们需要一种能直接在图结构上进行特征学习的新范式。

图的基本概念

一个图 \(G = (V, E)\) 由节点集 \(V\) 和边集 \(E\) 构成。假设图有 \(N\) 个节点，每个节点有 \(F\) 维特征，则可以用以下矩阵来描述：

邻接矩阵 \(A \in \mathbb{R}^{N \times N}\)：\(A_{ij} = 1\) 表示节点 \(i\) 和 \(j\) 之间有边，否则为 0（无权无向图）
度矩阵 \(D \in \mathbb{R}^{N \times N}\)：对角矩阵，\(D_{ii} = \sum_j A_{ij}\)，即节点 \(i\) 的邻居数量
特征矩阵 \(X \in \mathbb{R}^{N \times F}\)：第 \(i\) 行是节点 \(i\) 的特征向量

示例：3 个节点的无向图

    0 --- 1
    |   /
    |  /
    2

邻接矩阵 A:          度矩阵 D:          特征矩阵 X (2维特征):
┌ 0  1  1 ┐        ┌ 2  0  0 ┐        ┌ 1.0  0.5 ┐   节点 0
│ 1  0  1 │        │ 0  2  0 │        │ 0.3  0.8 │   节点 1
└ 1  1  0 ┘        └ 0  0  2 ┘        └ 0.7  0.2 ┘   节点 2

图上的机器学习任务

图上的学习任务大致分为三个层次：

节点分类（Node Classification）：预测每个节点的标签。例如在引文网络中判断论文的学科领域。GCN 的原始论文正是解决这个问题。
链接预测（Link Prediction）：预测两个节点之间是否存在边。例如社交网络中的好友推荐。
图分类（Graph Classification）：预测整张图的属性。例如判断一个分子是否具有某种药理活性。

传统方法的局限

在 GCN 之前，图上的表示学习主要依赖以下方法：

手工特征：节点度、聚类系数、PageRank 等统计指标，需要领域专家设计
图嵌入方法（DeepWalk, Node2Vec, LINE）：通过随机游走 + Skip-gram 学习节点嵌入，但这些方法是直推式（Transductive）的，无法泛化到训练时未见过的新节点，且嵌入学习与下游任务是分离的，不是端到端的

GCN 的目标就是提供一种端到端的、可以利用图结构和节点特征的学习框架。

图卷积的直觉

从 CNN 卷积到图卷积

回顾 CNN：一个 \(3 \times 3\) 的卷积核在图像上滑动，对每个像素的局部邻域进行加权求和，提取局部特征。

CNN 卷积：规则网格上的邻域聚合
┌───┬───┬───┐
│ a │ b │ c │     中心像素的新值
├───┼───┼───┤  =  邻域内所有像素的加权和
│ d │ e │ f │     (权重由卷积核决定)
├───┼───┼───┤
│ g │ h │ i │
└───┴───┴───┘

图卷积：不规则图上的邻域聚合

       (v2)            节点 v1 的新表示
      / |  \        =  v1 自身 + v2, v3, v4 的信息聚合
   (v1)─┼──(v3)       (权重由图结构决定)
      \ |  /
       (v4)

核心思想是一样的：在局部邻域上聚合信息。只不过 CNN 的邻域是固定大小的网格，而图卷积的邻域由图的拓扑结构决定，大小和形状各不相同。

消息传递范式

图卷积可以用消息传递（Message Passing）的视角来统一理解。每一层 GNN 都执行以下三步操作：

消息构造（Message）：每个节点将自身的特征作为"消息"发送给邻居
消息聚合（Aggregate）：每个节点收集来自所有邻居的消息，通过某种方式（求和、平均、取最大值等）聚合
状态更新（Update）：将聚合后的信息与自身特征结合，通过变换（线性层 + 激活函数）更新节点表示

直觉类比

"你的朋友定义了你。" 一个人的特征不仅取决于自身属性，还取决于他的社交圈。类似地，图中一个节点的表示应当综合考虑其自身特征和邻居特征。GCN 的每一层都在做这样的事情：让每个节点"看一看"自己的邻居，然后更新自己的表示。堆叠 \(k\) 层 GCN，就相当于每个节点能看到 \(k\) 跳（hop）范围内的邻居信息。

GCN 数学推导

谱域方法 (Spectral Approach)

GCN 的数学基础源自图信号处理中的谱图理论。这条推导线索较长，但理解它有助于真正明白 GCN 公式的来源。

图拉普拉斯矩阵

图拉普拉斯矩阵（Graph Laplacian）是图信号处理的核心工具：

\[ L = D - A \]

其中 \(D\) 是度矩阵，\(A\) 是邻接矩阵。\(L\) 是半正定对称矩阵，具有很好的数学性质。

对于上面的 3 节点示例：

\[ L = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix} - \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix} \]

归一化拉普拉斯矩阵：

\[ L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2} \]

归一化的好处是消除了节点度数差异带来的尺度问题，使得特征值落在 \([0, 2]\) 区间内。

图傅里叶变换

\(L_{\text{sym}}\) 是实对称矩阵，可以进行特征分解：

\[ L_{\text{sym}} = U \Lambda U^T \]

其中 \(U = [u_1, u_2, \dots, u_N]\) 是特征向量矩阵（正交矩阵），\(\Lambda = \text{diag}(\lambda_1, \dots, \lambda_N)\) 是特征值对角矩阵。

特征向量 \(u_i\) 就是图上的"频率基"，类比于经典傅里叶变换中的正弦/余弦基函数。对图信号 \(x \in \mathbb{R}^N\) 做图傅里叶变换：

\[ \hat{x} = U^T x \]

逆变换为 \(x = U \hat{x}\)。

谱卷积

在经典信号处理中，时域卷积等价于频域相乘。类似地，图上的卷积可以定义为：

\[ g_\theta \star x = U g_\theta(\Lambda) U^T x \]

其中 \(g_\theta(\Lambda) = \text{diag}(\theta_1, \dots, \theta_N)\) 是频域滤波器，\(\theta_i\) 是可学习参数。

谱卷积的问题

这个定义有两个致命缺陷：（1）特征分解的计算复杂度是 \(O(N^3)\)，对大图不可行；（2）滤波器有 \(N\) 个参数，不具有空间局部性，而且依赖于具体的图结构（因为 \(U\) 是图相关的），无法迁移到其他图上。

ChebNet：切比雪夫多项式近似

Hammond et al. (2011) 提出用切比雪夫多项式来近似滤波器函数，避免显式的特征分解：

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

其中 \(\tilde{\Lambda} = \frac{2}{\lambda_{\max}} \Lambda - I\) 是将特征值缩放到 \([-1, 1]\) 的归一化版本，\(T_k\) 是第 \(k\) 阶切比雪夫多项式，由递推关系定义：

\[ T_0(x) = 1, \quad T_1(x) = x, \quad T_k(x) = 2x T_{k-1}(x) - T_{k-2}(x) \]

将其代入谱卷积公式：

\[ g_\theta \star x \approx \sum_{k=0}^{K} \theta_k T_k(\tilde{L}_{\text{sym}}) x \]

其中 \(\tilde{L}_{\text{sym}} = \frac{2}{\lambda_{\max}} L_{\text{sym}} - I\)。关键优势在于 \(T_k(\tilde{L}_{\text{sym}})\) 可以通过矩阵乘法递推计算，无需做特征分解。且 \(K\) 阶多项式对应 \(K\) 跳邻域，滤波器天然具有空间局部性。Defferrard et al. (2016) 基于此构建了 ChebNet。

GCN 的简化 (Kipf & Welling, 2017)

Kipf & Welling 的核心贡献是对 ChebNet 做了大刀阔斧的简化，使模型变得极其优雅。

取 K=1 的一阶近似

令 \(K = 1\)（只保留 0 阶和 1 阶切比雪夫多项式），并进一步令 \(\lambda_{\max} \approx 2\)：

\[ g_\theta \star x \approx \theta_0 x + \theta_1 (L_{\text{sym}} - I) x = \theta_0 x - \theta_1 D^{-1/2} A D^{-1/2} x \]

为了进一步减少参数，令 \(\theta = \theta_0 = -\theta_1\)，得到：

\[ g_\theta \star x \approx \theta (I + D^{-1/2} A D^{-1/2}) x \]

重归一化技巧 (Renormalization Trick)

\(I + D^{-1/2} A D^{-1/2}\) 的特征值范围为 \([0, 2]\)，反复相乘可能导致数值不稳定（梯度爆炸或消失）。Kipf & Welling 使用了一个精妙的重归一化技巧：

\[ I + D^{-1/2} A D^{-1/2} \quad \longrightarrow \quad \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} \]

其中：

\(\tilde{A} = A + I_N\)（邻接矩阵加上自环，即每个节点将自己也视为邻居）
\(\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}\)（加自环后的度矩阵，即 \(\tilde{D} = D + I\)）

自环的意义

添加自环 \(A + I\) 意味着在消息传递时，节点不仅聚合邻居的信息，也保留自身的信息。这是非常自然的：更新节点表示时，不应该丢弃节点自身的特征。

核心传播公式

将上述简化推广到多通道特征（\(F\) 维输入，\(F'\) 维输出），得到 GCN 的逐层传播规则：

\[ \boxed{H^{(l+1)} = \sigma\!\left(\hat{A}\, H^{(l)}\, W^{(l)}\right)} \]

其中：

\(\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\) 是归一化的带自环邻接矩阵（预计算一次即可）
\(H^{(l)} \in \mathbb{R}^{N \times F_l}\) 是第 \(l\) 层的节点特征矩阵，\(H^{(0)} = X\)
\(W^{(l)} \in \mathbb{R}^{F_l \times F_{l+1}}\) 是第 \(l\) 层的可学习权重矩阵
\(\sigma(\cdot)\) 是激活函数（通常用 ReLU）

空间域理解

从空间（节点）的视角来看，上述公式对每个节点 \(i\) 做的事情非常直观：

\[ h_i^{(l+1)} = \sigma\!\left(\sum_{j \in \mathcal{N}(i) \cup \{i\}} \frac{1}{\sqrt{\tilde{d}_i} \sqrt{\tilde{d}_j}} h_j^{(l)} W^{(l)}\right) \]

即：节点 \(i\) 的新特征 = 对自身和所有邻居的特征先做加权平均（权重由两端节点的度数决定），再做线性变换，最后过激活函数。

权重 \(\frac{1}{\sqrt{\tilde{d}_i \tilde{d}_j}}\) 是对称归一化系数，度数越大的邻居贡献越小，这避免了高度节点对低度节点的信息淹没。

前向传播数值示例

用上面的 3 节点图进行完整的手算，展示一层 GCN 的前向传播。

第一步：计算 \(\tilde{A}\) 和 \(\tilde{D}\)

\[ \tilde{A} = A + I = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \]

\[ \tilde{D} = \text{diag}(3, 3, 3) \]

第二步：计算 \(\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\)

\[ \tilde{D}^{-1/2} = \text{diag}\!\left(\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}}\right) \]

\[ \hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} = \frac{1}{3} \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \]

特殊情况说明

这个例子中所有节点的度数恰好相同（都是 2，加自环后都是 3），所以 \(\hat{A}\) 每个元素都是 \(1/3\)。在一般的图中，不同位置的值会不同：\(\hat{A}_{ij} = \frac{1}{\sqrt{\tilde{d}_i \tilde{d}_j}}\)（当 \(\tilde{A}_{ij} = 1\) 时）。

第三步：邻域聚合 \(\hat{A} H^{(0)}\)

\[ \hat{A} X = \frac{1}{3} \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1.0 & 0.5 \\ 0.3 & 0.8 \\ 0.7 & 0.2 \end{pmatrix} = \frac{1}{3} \begin{pmatrix} 2.0 & 1.5 \\ 2.0 & 1.5 \\ 2.0 & 1.5 \end{pmatrix} = \begin{pmatrix} 0.667 & 0.500 \\ 0.667 & 0.500 \\ 0.667 & 0.500 \end{pmatrix} \]

由于这是一个完全图（所有节点互连），聚合后的结果是所有节点特征的均值，三个节点拿到了相同的聚合结果。在非完全图中，不同节点的聚合结果一般是不同的。

第四步：线性变换 + 激活

假设 \(W^{(0)} \in \mathbb{R}^{2 \times 3}\)（从 2 维映射到 3 维）：

\[ W^{(0)} = \begin{pmatrix} 0.5 & -0.3 & 0.1 \\ 0.2 & 0.4 & -0.5 \end{pmatrix} \]

\[ \hat{A} X W^{(0)} = \begin{pmatrix} 0.667 & 0.500 \\ 0.667 & 0.500 \\ 0.667 & 0.500 \end{pmatrix} \begin{pmatrix} 0.5 & -0.3 & 0.1 \\ 0.2 & 0.4 & -0.5 \end{pmatrix} = \begin{pmatrix} 0.433 & 0.000 & -0.183 \\ 0.433 & 0.000 & -0.183 \\ 0.433 & 0.000 & -0.183 \end{pmatrix} \]

经过 ReLU 激活 \(\sigma(x) = \max(0, x)\)：

\[ H^{(1)} = \begin{pmatrix} 0.433 & 0.000 & 0.000 \\ 0.433 & 0.000 & 0.000 \\ 0.433 & 0.000 & 0.000 \end{pmatrix} \]

这个例子因为是完全图，已经展现了一个有趣的现象：仅一层 GCN 后，所有节点的表示就完全相同了。这正是过平滑（Over-smoothing）问题的一个极端体现。

GCN 的性质与局限

半监督学习

GCN 最核心的应用场景是半监督节点分类：图中只有少量节点有标签，但所有节点都有特征和连接关系。GCN 通过图结构传播标签信息，让无标签节点也能被正确分类。

一个典型的两层 GCN 用于节点分类：

\[ Z = \text{softmax}\!\left(\hat{A}\, \text{ReLU}\!\left(\hat{A} X W^{(0)}\right) W^{(1)}\right) \]

损失函数只在有标签的节点上计算交叉熵：

\[ \mathcal{L} = - \sum_{i \in \mathcal{Y}_L} \sum_{f=1}^{F} Y_{if} \ln Z_{if} \]

其中 \(\mathcal{Y}_L\) 是有标签节点的集合。尽管损失只在部分节点上计算，但由于 \(\hat{A}\) 在前向传播中连接了所有邻居，梯度会通过图结构传播到无标签节点。

过平滑 (Over-smoothing)

GCN 的核心瓶颈

随着 GCN 层数增加，每个节点能感知的邻域范围呈指数增长。当层数足够多时，所有节点的感受野覆盖了整张图，导致所有节点的表示趋于一致，丧失了区分度。这就是过平滑问题。

直觉上，\(\hat{A}\) 的反复相乘就像在做拉普拉斯平滑：每个节点不断地与邻居取平均。多次平滑后，整张图上的信号趋于平坦，所有节点的特征向量收敛到同一个值。

实践中，GCN 通常只用 2-3 层。这与 CNN 和 Transformer 可以堆叠几十甚至上百层形成了鲜明对比。

缓解过平滑的方法包括：残差连接（类似 ResNet）、DropEdge（随机丢弃边）、JKNet（跳跃知识网络，聚合各层的输出）。

只能处理同构图

标准 GCN 假设所有节点和边的类型相同（同构图）。对于知识图谱这样有多种节点类型和边类型的异构图，需要使用 R-GCN（Relational GCN）等变体。

可扩展性问题

GCN 的前向传播需要完整的邻接矩阵 \(\hat{A}\) 和所有节点的特征矩阵，这意味着需要对整张图做全图训练（Full-batch Training）。对于百万甚至上亿节点的大图，这在内存和计算上都不可行。

解决思路： - Mini-batch 训练：GraphSAGE 通过采样邻居实现小批量训练 - Cluster-GCN：先将图分簇，每次训练一个子图 - FastGCN：通过重要性采样减少计算量

GNN 变体

GCN 开创了图神经网络的端到端学习范式后，涌现了大量变体。以下是最重要的几个。

GraphSAGE (Hamilton et al., 2017)

GraphSAGE（SAmple and aggreGatE）解决了 GCN 的两大问题：可扩展性和归纳学习能力。

核心思路：

采样：不使用所有邻居，而是对每个节点均匀采样固定数量的邻居（如 \(K\) 个）
聚合：用可学习的聚合函数（而非固定的 \(\hat{A}\)）聚合邻居信息

\[ h_{\mathcal{N}(v)}^{(l)} = \text{AGGREGATE}^{(l)}\!\left(\{h_u^{(l-1)}, \forall u \in \mathcal{N}(v)\}\right) \]

\[ h_v^{(l)} = \sigma\!\left(W^{(l)} \cdot \text{CONCAT}\!\left(h_v^{(l-1)},\ h_{\mathcal{N}(v)}^{(l)}\right)\right) \]

聚合函数可以是 Mean、LSTM、Max Pooling 等。由于 GraphSAGE 学习的是聚合函数而非固定的节点嵌入，它可以泛化到训练时未见过的新节点（归纳式学习，Inductive Learning），这是相对于 GCN 的重要进步。

GAT (Graph Attention Network, Velickovic et al., 2018)

GAT 的核心创新是用注意力机制替代 GCN 中固定的归一化系数 \(\frac{1}{\sqrt{\tilde{d}_i \tilde{d}_j}}\)，让模型自适应地学习每个邻居的重要性。

注意力系数的计算：

\[ e_{ij} = \text{LeakyReLU}\!\left(\mathbf{a}^T [W h_i \| W h_j]\right) \]

\[ \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} W h_j\right) \]

其中 \(\|\) 表示拼接，\(\mathbf{a}\) 是可学习的注意力向量。GAT 还使用了多头注意力来稳定训练，与 Transformer 中的 Multi-Head Attention 思想一致。

GCN vs GAT 的关键区别

GCN 中邻居的权重完全由图结构（度数）决定，是固定的；GAT 中邻居的权重由注意力机制动态计算，取决于节点特征。这使得 GAT 能够对不同邻居分配不同的重要性，表达能力更强。

GIN (Graph Isomorphism Network, Xu et al., 2019)

GIN 从理论角度出发，证明了大多数 GNN（包括 GCN 和 GraphSAGE）的表达能力严格弱于 Weisfeiler-Leman (WL) 图同构测试，并设计了一个与 WL 测试同等表达力的架构：

\[ h_v^{(l)} = \text{MLP}^{(l)}\!\left((1 + \epsilon^{(l)}) \cdot h_v^{(l-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(l-1)}\right) \]

其中 \(\epsilon\) 是可学习参数或固定值。GIN 使用求和（而非平均或最大值）作为聚合函数，因为求和在理论上是单射的，能区分不同的多重集。

消息传递神经网络 (MPNN)

Gilmer et al. (2017) 提出的 MPNN 框架将上述所有模型统一到一个通用范式中：

\[ m_v^{(l+1)} = \sum_{u \in \mathcal{N}(v)} M^{(l)}(h_v^{(l)}, h_u^{(l)}, e_{vu}) \]

\[ h_v^{(l+1)} = U^{(l)}(h_v^{(l)}, m_v^{(l+1)}) \]

其中 \(M^{(l)}\) 是消息函数，\(U^{(l)}\) 是更新函数，\(e_{vu}\) 是边特征。GCN、GraphSAGE、GAT 等都可以看作 MPNN 的特例，区别仅在于消息函数和更新函数的具体选择。

应用领域

社交网络分析

在社交网络中，用户是节点，关注/好友关系是边。GCN 可以用于用户分类（如识别机器人账号）、社区发现等。利用图结构传播信息，即使一个用户本身特征不明显，也可以通过其社交关系推断其属性。

分子性质预测与药物发现

分子天然是图结构（原子为节点，化学键为边）。GNN 可以预测分子的溶解度、毒性、药理活性等性质，大大加速药物筛选过程。DeepMind 的 AlphaFold 中也使用了图神经网络来建模氨基酸残基之间的相互作用。

知识图谱推理

知识图谱中的实体和关系构成异构图。R-GCN 等方法可以用于链接预测（推断缺失的关系）和实体分类。

交通流预测

将城市路网建模为图（路口为节点，道路为边），结合时间序列信息，时空图神经网络（ST-GNN）可以预测未来的交通流量和拥堵情况。

GCN vs CNN vs MLP 对比

特性	MLP	CNN	GCN
输入数据结构	向量（一维）	网格（二维/三维）	任意图结构
邻域定义	无（全连接）	固定大小的局部窗口	图中的相邻节点
参数共享	无	卷积核在空间上共享	权重矩阵 \(W\) 在所有节点上共享
感受野	全局（一层）	随层数线性增长	随层数指数增长
平移不变性	不适用	是（核心假设）	不适用（排列不变性）
归纳偏置	无	局部性 + 平移不变性	图结构先验（同质性假设）
典型深度	任意	数十到上百层	2-3 层
适用领域	表格数据、通用	图像、视频、音频	社交网络、分子、知识图谱

排列不变性 (Permutation Invariance)

GCN 的一个重要性质是排列不变性：无论节点的编号顺序如何打乱（即对邻接矩阵做行列置换），GCN 的输出不变。这与 CNN 的平移不变性类似，都是架构内建的归纳偏置。数学上，对任意置换矩阵 \(P\)，有 \(f(PAP^T, PX) = P f(A, X)\)，即输出随输入做相同的置换（排列等变性）。

思考与讨论

GNN 的表达力上限：WL Test

Weisfeiler-Leman (WL) 图同构测试是判断两个图是否同构的经典算法。Xu et al. (2019) 证明了：消息传递 GNN 的表达力上限等价于 1-WL 测试。这意味着存在某些图结构，1-WL 测试无法区分，GNN 也同样无法区分。例如，某些正则图（所有节点度数相同且邻域结构对称）对 GNN 来说是不可区分的。

突破这一上限的方向包括：高阶 WL 测试 (k-WL)、子图 GNN、等变 GNN 等。

过平滑的本质原因

从线性代数角度看，\(\hat{A}\) 的反复乘法本质上是一个低通滤波器。\(\hat{A}^k\) 随 \(k\) 增大会收敛到与图拉普拉斯最小特征值对应的特征向量方向，这意味着所有节点的表示被投影到同一个低维子空间，信息被"磨平"。

从随机游走角度看，\(\hat{A}^k\) 的每一行趋向于图的平稳分布，所有节点"看到"的全局分布相同，自然失去了局部特性。

GNN 在大模型时代的地位

随着 LLM 的兴起，一个自然的问题是：GNN 是否会被 LLM 取代？

目前的共识是：对于天然的图结构数据（分子、蛋白质、物理仿真），GNN 仍然是最合适的归纳偏置。LLM 擅长处理序列化的语言信息，但将图结构序列化后输入 LLM 会丢失拓扑信息且效率低下。更有前景的方向是GNN 与 LLM 的融合：用 GNN 编码图结构信息，用 LLM 处理文本信息，两者互补。例如在知识图谱增强的问答系统中，GNN 负责图上的推理，LLM 负责自然语言的理解和生成。

另一个趋势是图基础模型（Graph Foundation Model）的探索：能否训练一个通用的图模型，在不同领域的图数据上都能表现良好？这仍然是一个开放问题，因为不同领域图的特征空间和语义差异巨大。

参考文献

Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017.
Defferrard, M., Breber, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS 2016.
Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs (GraphSAGE). NeurIPS 2017.
Velickovic, P., et al. (2018). Graph Attention Networks. ICLR 2018.
Xu, K., et al. (2019). How Powerful are Graph Neural Networks? ICLR 2019.
Gilmer, J., et al. (2017). Neural Message Passing for Quantum Chemistry (MPNN). ICML 2017.