图与图表示基础

1. 图为什么难学

1.1 从欧式空间到图结构

在图像和文本任务中，数据具有清晰的空间或时间结构：

图像：像素排列在规则的网格上，每个像素有固定的邻域（上下左右四个近邻）。
序列（文本、时间序列）：数据呈线性排列，每个位置有明确的前后继关系。

这些结构有一个共同特点：数据的排列方式本身包含语义信息，且这种排列是全局一致的。我们可以用卷积核在图像上滑动，可以用 Transformer 的位置编码注入顺序信息。

然而，图数据打破了这些假设。一个社交网络中，用户的”邻居”数量不固定，拓扑结构也不规则。你无法像图像那样用一个固定大小的卷积核在所有节点上以相同方式滑动——每个节点的局部邻域结构可能截然不同。

这就是图学习最核心的挑战：不规则的拓扑结构 + 排列不变性要求。

1.2 图与网格、序列、集合的本质区别

数据类型	元素关系	邻域结构	排列敏感性	经典模型
网格数据（图像）	二维规则网格	固定（如3×3卷积核覆盖8邻域）	敏感（空间位置编码重要）	CNN
序列数据（文本）	一维线性序列	固定（如前后各k个词）	敏感（位置编码决定顺序）	RNN, Transformer
集合数据	无序集合	无邻域概念	不敏感（集合不变性）	DeepSet
图数据	不规则拓扑	度数不固定	不敏感（节点编号无关）	GNN

图与集合的关键区别在于：图不仅是无序的元素集合，还编码了元素之间的关系。但这些关系不像图像那样被嵌入到一个连续的空间中，而是离散地存储在邻接结构里。

1.3 排列不变性：为什么节点编号不能决定语义

假设我们有一个三节点的简单图，节点编号为 1、2、3。重新给节点编号为 3、1、2 不会改变图所代表的真实系统——但如果我们的模型依赖于节点编号（如直接用索引做 embedding lookup），模型就会给出完全不同的预测。

排列不变性（Permutation Invariance） 意味着：

其中是任意排列矩阵。这意味着我们的模型必须对节点顺序”视而不见”——它只能通过图的拓扑结构和节点自身特征来做出判断。

这正是 CNN 不能直接用于图数据的原因之一：CNN 天然依赖于空间位置（卷积核的位置与输入像素的位置是对应的），而图没有这种内在的空间坐标。

2. 图的数学定义与分类

2.1 图的基本定义

定义（无向图）：一个无向图由以下部分组成：

：节点集合，为节点数
：边集合，每条边是无序节点对

定义（有向图）：有向图中，每条边是有序节点对，表示从指向的方向。

定义（加权图）：若每条边关联一个标量权重，则图是加权的；否则是无权的。

2.2 图的分类体系

图
├── 按方向性
│   ├── 无向图：边无方向，对称邻接
│   └── 有向图：边有方向，邻接矩阵不对称
│       ├── 出度 / 入度
│       └── 强连通分量
├── 按权重
│   ├── 无权图：所有边权重相同（通常为1）
│   └── 加权图：边有权重（距离、相似度等）
├── 按节点/边的异质性
│   ├── 同质图（Homogeneous Graph）：所有节点和边同类型
│   └── 异构图（Heterogeneous Graph）：节点/边有多种类型
│       ├── 知识图谱（实体-关系-实体）
│       └── 用户-商品-交互异构图
└── 按时间维度
    ├── 静态图：拓扑结构不随时间变化
    └── 动态图（Dynamic Graph）：拓扑或特征随时间演化
        ├── 离散时间动态图（DTNG）：按时间片快照
        └── 连续时间动态图（CTNG）：边带时间戳事件流

2.2.1 异构图举例

以推荐系统中的用户-商品交互图为例：

节点类型：用户、商品、品牌、类别
边类型：购买、浏览、收藏、属于（品牌）、属于（类别）

在异构图上，节点和边的类型本身是重要的语义信息。普通的同质 GNN 无法区分这些类型，需要设计专门的异构图神经网络（如 R-GCN、HAN）。

2.2.2 动态图举例

社交网络随时间演变：新用户加入、新 friendships 建立、用户注销。动态图建模是图学习的重要前沿，因为许多真实系统的行为模式与时间紧密相关。

3. 图的矩阵表示

3.1 邻接矩阵

邻接矩阵是图的核心表示之一：

$如果否则$

对于加权图，。

对于有向图，不再是对称矩阵：

行的非零元素表示从节点出发的边（出度）
列的非零元素表示指向节点的边（入度）

对于无向图，是对称矩阵：。

注意：邻接矩阵编码了图的稀疏性。真实世界的图往往是稀疏的（），这既是存储优化的机会，也是计算上的挑战。

3.2 度矩阵

度矩阵是对角矩阵：

对于无向图，这就是节点连接的边数；对于有向图，通常区分出度（按行求和）和入度（按列求和）。

在图神经网络的归一化操作中，度矩阵起到关键作用（详见后续章节）。

3.3 拉普拉斯矩阵

拉普拉斯矩阵是图信号处理和图神经网络的核心工具，定义为：

3.3.1 拉普拉斯矩阵的数学性质

对称半正定：对于无向图，是对称的，且所有特征值。
行和为零：，其中是全1向量。这意味着最小的特征值对应特征向量，对应特征值 0。
二次型形式：对于任意向量：

这个二次型形式极其重要——它度量了图上信号的平滑性。

3.3.2 拉普拉斯矩阵与平滑性的关系

平滑性（smoothness）衡量的是相邻节点上信号值的一致程度。

观察上式：

当相邻节点的信号值接近时（即图很”平滑”），这个二次型取值小
当相邻节点信号差异大时，这个值大

因此，最小化就是在鼓励相邻节点拥有相似的信号值——这就是图上的”平滑先验”。

这也是为什么拉普拉斯正则项（如在图嵌入方法中）能够防止过拟合：它确保学到的表示在图结构上平滑变化，而非在无关节点间产生虚假的相关性。

3.3.3 拉普拉斯矩阵的归一化形式

在实际应用中，更常用的是归一化版本的拉普拉斯矩阵：

对称归一化：

随机游走归一化：

归一化后的拉普拉斯矩阵特征值都在范围内，是对称的，不是对称的但在随机游走理论中有重要意义。

3.4 节点特征矩阵

节点特征矩阵存储每个节点的特征向量：

其中是节点的维特征向量。

在引文网络（如 Cora、CiteSeer）中，特征可能是词袋向量或摘要的 TF-IDF 表示；在社交网络中，特征可能是用户画像；在分子图中，节点特征可能是原子类型、价电子数等化学属性。

3.5 边特征

边特征矩阵存储每条边的属性。对于加权的简单图，可以将权重标量视为一维边特征。

常见的边特征包括：

时间权重（动态图中边的建立时间）
交互强度（信任度、交易金额）
关系类型（社交网络中的朋友/家人/同事）

3.6 统一表示框架

综合以上，一个图可以被完整地表示为：

：邻接矩阵（拓扑结构）
：节点特征矩阵（节点属性）
：边特征矩阵（边属性，可选）

4. 图论核心概念

4.1 节点（Vertex / Node）

图中的基本元素，记作。每个节点可以关联属性（特征向量）。

4.2 边（Edge）

连接两个节点的元素，记作。

有向边 vs 无向边：

无向边：，如友谊关系
有向边：，如关注关系、论文引用

自环（Self-loop）：从节点到自身的边，在邻接矩阵中表现为对角元素。

4.3 路径（Path）

路径是节点序列，满足相邻节点间都有边相连。

路径长度：路径上边的数量（或加权图中边权重的和）。

最短路径（Shortest Path）：两节点间边数最少的路径，其长度称为图距离（Graph Distance）。

直径（Diameter）：图中所有节点对之间最短路径长度的最大值。

4.4 子图（Subgraph）

子图满足且。

诱导子图（Induced Subgraph）：只保留指定节点的子图，所有端点都在中的边都被保留。

-阶邻居子图：节点及其跳内的所有节点构成的子图，是图神经网络局部感受野的核心概念。

4.5 连通分量（Connected Component）

在无向图中，连通分量是极大的连通子图。如果图中只有一个连通分量，则称该图为连通图。

在有向图中，相应的概念是强连通分量：任意两个节点可以互相到达。

5. 图上的局部平稳性假设

5.1 从频域看图卷积：基本直觉

在传统信号处理中，傅里叶变换将信号分解为不同频率的正弦和余弦分量。类似地，图傅里叶变换将图上的信号分解为拉普拉斯矩阵的特征向量：

其中是的特征向量矩阵，是特征值的对角矩阵。

关键直觉：

传统信号处理	图信号处理
傅里叶基是拉普拉斯算子的特征函数	图傅里叶基是图拉普拉斯矩阵的特征向量
频率由特征值决定	图频率由决定
低频 = 全局平滑趋势	最低频率 = 常量信号（所有节点相同）
高频 = 局部剧烈变化	最高频率 = 节点间差异最大的模式

图信号的低频分量对应全局平滑的模式（相邻节点几乎相同），高频分量对应局部剧烈变化的模式。

5.2 局部平稳性假设

图上的局部平稳性假设（Local Stationarity Assumption） 是图神经网络能够泛化的核心假设：

相似的局部邻域结构应该有相似的响应/表示。

这个假设的数学表达是：若两个节点的阶邻居子图（在拓扑意义上）相似，则它们的表示应该接近。

这与 CNN 的平移不变性类似，但比 CNN 更复杂——因为”邻居子图的相似性”不能简单地用卷积核的滑动来定义（回顾：图没有规则网格）。

GNN 通过消息传递机制来实现这一假设：

每一层的聚合操作只考虑局部邻域，但通过堆叠多层，节点的感受野逐步扩大，最终能够捕获全局信息。

5.3 为什么 CNN / Transformer 不能直接用于图

CNN 的问题：

固定的邻域大小：CNN 的卷积核有固定的空间范围（如 3×3），但图的节点度不固定
规则网格假设：卷积核在网格上滑动，隐式假设了像素的空间位置有明确定义，而图的拓扑是离散的、无坐标的
参数共享的拓扑约束：CNN 的参数共享基于网格的空间平移，而图上的”平移”没有良好定义

Transformer 的问题：

全局注意力计算贵：标准 Transformer 对序列中所有位置两两计算注意力，复杂度，而图的节点数可能达百万级
需要定义位置编码：Transformer 依赖位置编码注入序列顺序信息，但图没有自然的节点顺序——排列不变性意味着我们不能简单地给节点分配 1, 2, 3… 的位置
稀疏注意力机制：虽然稀疏注意力可以缓解计算问题，但它仍然缺乏图结构所带来的局部性归纳偏置

6. 图学习任务类型

6.1 节点级任务（Node-level Tasks）

目标：为图中每个节点预测一个标签或属性。

典型任务：

节点分类（Cora 引文网络中的论文主题分类）
节点回归（预测用户的购买意愿分数）
节点聚类（基于表示的社区发现）

示例：在引文网络中，每个节点是一篇论文，目标是根据论文内容和引用关系预测其所属领域。

6.2 边级任务（Edge-level Tasks）

目标：为图中的一对节点（或边本身）预测标签。

典型任务：

链接预测（推荐系统中预测用户是否会购买某商品）
边分类（知识图谱中预测关系的类型）
边属性预测（交通网络中预测路段的通行时间）

示例：在社交网络的好友推荐中，给定用户和用户，预测他们成为朋友的概率。

6.3 图级任务（Graph-level Tasks）

目标：为整个图预测一个标签或属性。

典型任务：

图分类（分子图中判断分子是否有某种化学性质）
图回归（预测分子的溶解度）
图生成（生成符合特定性质的分子结构）

示例：在药物发现中，给定一个分子图（节点是原子，边是化学键），判断该分子是否与特定蛋白质有亲和力。

7. 图数据的存储与工程实践

7.1 图数据的存储格式

对于大规模图，常见的存储格式包括：

格式	描述	适用场景
COO（Coordinate）	边列表：(row, col, value)	简单、构建快
CSR（Compressed Sparse Row）	行指针 + 列索引	高效随机访问出边
CSC（Compressed Sparse Column）	列指针 + 行索引	高效随机访问入边
邻接表	每个节点的邻居列表	度分布稀疏的场景

在 PyTorch Geometric 中，Data 对象的核心存储形式是 COO 格式的边索引：

from torch_geometric.data import Data
 
# 边索引：每列是一条边 (source, target)
edge_index = torch.tensor([[0, 1, 1, 2],
                           [1, 0, 2, 1]], dtype=torch.long)
 
# 节点特征
x = torch.tensor([[-1, 0.5], [0.2, 0.1], [0.7, -0.3]], dtype=torch.float)
 
# 节点标签（如节点分类任务）
y = torch.tensor([0, 1, 0], dtype=torch.long)
 
data = Data(x=x, edge_index=edge_index, y=y)
# data.num_nodes = 3
# data.num_edges = 4

7.2 特征、边、标签与掩码的组织

7.2.1 节点特征

形状：[num_nodes, node_feat_dim]
节点特征矩阵每行对应一个节点的特征向量

7.2.2 边特征

形状：[num_edges, edge_feat_dim]
与 edge_index 的列顺序一一对应

# 带边特征的图
edge_attr = torch.tensor([[1.0], [1.0], [0.5], [0.5]], dtype=torch.float)
data = Data(x=x, edge_index=edge_index, edge_attr=edge_attr, y=y)

7.2.3 标签与掩码

对于半监督节点分类，通常需要：

# 全图节点特征
x = ...
# 全图标签
y_all = torch.tensor([0, 1, 2, 0, 1, -1, -1, ...], dtype=torch.long)
 
# -1 表示无标签
train_mask = torch.tensor([True, True, True, False, False, False, False, ...])
val_mask = torch.tensor([False, False, False, True, True, False, False, ...])
test_mask = torch.tensor([False, False, False, False, False, True, True, ...])
 
data = Data(x=x, edge_index=edge_index, y=y_all,
            train_mask=train_mask, val_mask=val_mask, test_mask=test_mask)

7.3 训练 / 验证 / 测试划分：避免信息泄漏

图学习中防止信息泄漏是一个微妙但至关重要的问题。

7.3.1 节点级任务的划分

错误做法：随机划分节点，同时让模型看到测试节点的邻居信息（这会导致跨集信息泄漏）。

正确做法：

按节点划分：将节点随机分为训练/验证/测试集，确保模型在训练时完全看不到测试节点的标签信息
转导式学习 vs 归纳式学习：
- 转导式（Transductive）：训练时可以看到验证/测试节点的特征和邻接结构（但看不到它们的标签）。这是常见的半监督学习场景，图结构在训练和测试时保持一致。
- 归纳式（Inductive）：训练和测试使用完全不同的图结构，测试集的节点和边在训练时完全不可见。对模型泛化能力要求更高。

7.3.2 链接预测的划分

链接预测任务中，如果直接随机划分正负样本：

可能出现”未来链接”泄漏：当前时间步的模型在训练时看到了测试时间才会出现的链接
可能出现邻居泄漏：负采样时采到了实际上存在但被当作负例的边

正确做法：

按时间切片：只使用时间之前的边构建训练图，预测时刻的链接
负样本要与真实的正样本在拓扑分布上匹配

7.3.3 图级任务的划分

图分类任务中，各图之间应是独立的。确保来自同一个大图的子图不会被拆分到不同集合中（否则子图间会通过原始图的结构产生信息泄漏）。

8. 图表示方式对比

8.1 表示方法总览

方法	表示维度	捕获信息	优点	缺点
邻接矩阵		拓扑结构	完整表达图的连通性	存储，无法直接用于大图；排列敏感
度矩阵		节点度数	归一化必需；揭示节点重要性	只保留度数信息，不包含拓扑
拉普拉斯矩阵		拓扑 + 平滑性	谱域分析基础；二次型揭示平滑性	计算特征分解昂贵
邻接列表	度数求和	拓扑（稀疏）	存储效率高 $O(N +	\mathcal{E}
节点特征		节点属性	提供语义信息	独立于拓扑；可与拓扑结合
图签名 / 指纹	固定长度	全局属性	可直接用于图分类	丢失精细的拓扑信息
图嵌入		拓扑 + 特征	低维、适合下游任务	丢失可解释性；需要学习
拉普拉斯特征映射		低频谱信息	保留全局平滑结构	只捕获低频；计算代价高

8.2 谱域 vs 空域

这是图神经网络的两大范式：

范式	核心思想	代表方法	计算代价
谱域（Spectral）	在图傅里叶域中定义卷积	ChebNet, GCN, GIN（理论上）	涉及特征分解，但可近似
空域（Spatial）	通过邻居聚合定义卷积	GraphSAGE, GAT, GIN	无需特征分解，适合大规模图

谱域方法具有严格的数学基础（基于图信号滤波理论），但计算复杂度高；空域方法更灵活、更适合工业级大规模图数据。

9. 图学习任务总览与路线图

学习完本章后，你应该对以下任务体系有全局认知：

图学习任务
├── 节点层面
│   ├── 节点分类（半监督 / 全监督）
│   ├── 节点回归
│   └── 节点聚类 / 社区检测
├── 边层面
│   ├── 链接预测
│   ├── 边分类
│   └── 边属性推断
├── 图层面
│   ├── 图分类
│   ├── 图回归
│   └── 图生成
└── 表征学习
    ├── 图嵌入（基于随机游走）
    ├── 图自编码器
    ├── 图对比学习
    └── 图预训练（大规模预训练 + 下游微调）

这些任务将在后续章节逐一展开。本章建立的核心概念——图的结构表示、矩阵定义、平滑性假设、排列不变性——是理解所有后续模型设计的基础。

10. 小结

本章从图学习为什么困难这一核心问题出发，建立了图表示的数学框架。

关键要点：

不规则拓扑是图与图像/序列最本质的区别。CNN 的滑动卷积和 Transformer 的位置编码都无法直接移植到图上。
排列不变性要求模型对节点编号”视而不见”，这驱动了 GNN 的设计哲学。
拉普拉斯矩阵是连接图论与机器学习的桥梁：它的二次型度量平滑性，它的特征向量构成图上的傅里叶基。
局部平稳性假设是 GNN 能够泛化的根本：相似的局部结构应该产生相似的表示。
工程实践中的信息泄漏问题需要严肃对待——图上的邻接关系本身就是一种”信息通道”，训练/测试划分时必须阻断这个通道。

在下一章中，我们将看到这些抽象的数学概念如何转化为具体的神经网络架构——从谱域的图卷积到空域的消息传递，完整覆盖主流 GNN 模型的设计思路。

Huajishe Notes

Explorer

1-图与图表示基础

图与图表示基础

1. 图为什么难学

1.1 从欧式空间到图结构

1.2 图与网格、序列、集合的本质区别

1.3 排列不变性：为什么节点编号不能决定语义

2. 图的数学定义与分类

2.1 图的基本定义

2.2 图的分类体系

2.2.1 异构图举例

2.2.2 动态图举例

3. 图的矩阵表示

3.1 邻接矩阵

3.2 度矩阵

3.3 拉普拉斯矩阵

3.3.1 拉普拉斯矩阵的数学性质

3.3.2 拉普拉斯矩阵与平滑性的关系

3.3.3 拉普拉斯矩阵的归一化形式

3.4 节点特征矩阵

3.5 边特征

3.6 统一表示框架

4. 图论核心概念

4.1 节点（Vertex / Node）

4.2 边（Edge）

4.3 路径（Path）

4.4 子图（Subgraph）

4.5 连通分量（Connected Component）

5. 图上的局部平稳性假设

5.1 从频域看图卷积：基本直觉

5.2 局部平稳性假设

5.3 为什么 CNN / Transformer 不能直接用于图

6. 图学习任务类型

6.1 节点级任务（Node-level Tasks）

6.2 边级任务（Edge-level Tasks）

6.3 图级任务（Graph-level Tasks）

7. 图数据的存储与工程实践

7.1 图数据的存储格式

7.2 特征、边、标签与掩码的组织

7.2.1 节点特征

7.2.2 边特征

7.2.3 标签与掩码

7.3 训练 / 验证 / 测试划分：避免信息泄漏

7.3.1 节点级任务的划分

7.3.2 链接预测的划分

7.3.3 图级任务的划分

8. 图表示方式对比

8.1 表示方法总览

8.2 谱域 vs 空域

9. 图学习任务总览与路线图

10. 小结

Graph View

Table of Contents