图数据与学习范式 / Graph Data and Learning Paradigms

图数据（Graph Data）作为表示复杂关系（Complex Relationships）与结构（Structures）的高效形式，已成为机器学习（Machine Learning）与人工智能（Artificial Intelligence）领域的重要研究对象。从社交网络（Social Networks）中用户之间的互动关系，到知识图谱（Knowledge Graphs）中实体间的语义关联，再到分子化学（Molecular Chemistry）中原子与化学键的拓扑排列，图结构无处不在。与传统欧氏数据（Euclidean Data）如图像（Images）、文本（Texts）不同，图数据具有明显的不规则性（Irregularity）和丰富的拓扑信息（Topological Information），这既带来了独特的挑战，也开辟了新的学习范式（Learning Paradigms）。本章将系统性地阐述图数据的基本形式化表示（Formal Representation），剖析其核心性质，对比图学习（Graph Learning）与欧氏数据学习的范式差异，深入探讨图神经网络（Graph Neural Networks, GNNs）设计中的根本挑战，并正式引入图学习的基本任务设置（Task Settings），为后续章节的理论与技术展开奠定坚实基础。

图数据的数学表示与基本概念

图（Graph）是一种由节点（Nodes）或顶点（Vertices）以及连接节点的边（Edges）组成的数学结构，用于建模实体之间的成对关系（Pairwise Relationships）。形式化地，一个图 $G$ 定义为节点集 $V$ 与边集 $E$ 的二元组，即 $G = (V, E)$。其中，$V = \{v_1, v_2, \dots, v_n\}$ 包含 $n = |V|$ 个节点，$E \subseteq V \times V$ 是边的集合，每条边 $e = (v_i, v_j) \in E$ 表示节点 $v_i$ 与 $v_j$ 之间存在连接。当边具有方向性时，称为有向图（Directed Graph），边表示为有序对 $(v_i, v_j)$；若边无方向，则为无向图（Undirected Graph），边表示为无序对 $\{v_i, v_j\}$。此外，边可以附加权重（Weight）以表示连接强度，形成加权图（Weighted Graph）；若所有权重均为1，则称为无权图（Unweighted Graph）。图 $G$ 的大小（Size）通常由节点数 $n$ 和边数 $m = |E|$ 描述，其复杂度与稠密程度（Density）密切相关。

在现实应用中，节点和边往往携带丰富的属性信息（Attribute Information）。节点属性（Node Features） 通常表示为一个矩阵 $\mathbf{X} \in \mathbb{R}^{n \times d}$，其中 $d$ 是每个节点的特征维度，第 $i$ 行 $\mathbf{x}_i$ 对应节点 $v_i$ 的特征向量。例如，在社交网络中，节点特征可能包括用户的年龄、兴趣、地理位置等；在分子图中，节点特征可能编码原子的类型（如碳、氧）、电负性、价电子数等化学性质。类似地，边属性（Edge Features） 可以表示为矩阵 $\mathbf{E} \in \mathbb{R}^{m \times p}$ 或三阶张量，描述连接关系的特性，如社交网络中用户间的互动频率、消息情感倾向，或分子图中化学键的类型（单键、双键、三键）和键长。当边属性存在时，图称为属性图（Attributed Graph）。这种属性信息为学习算法提供了丰富的语义输入，使得模型不仅能利用拓扑结构，还能融合节点和边的特征进行联合推理。

从数学表示角度，图的结构信息通常通过邻接矩阵（Adjacency Matrix） $\mathbf{A} \in \{0,1\}^{n \times n}$ 编码。对于无向图，$\mathbf{A}$ 是对称矩阵，元素 $A_{ij} = 1$ 表示节点 $v_i$ 与 $v_j$ 之间有边，否则为0；若为加权图，则 $A_{ij} \geq 0$ 表示权重。邻接矩阵的幂 $\mathbf{A}^k$ 可用于计算节点间长度为 $k$ 的路径数量。另一个重要矩阵是度矩阵（Degree Matrix） $\mathbf{D} \in \mathbb{R}^{n \times n}$，它是一个对角矩阵，对角元素 $D_{ii} = \sum_j A_{ij}$ 表示节点 $v_i$ 的度（Degree），即与之相连的边数。度分布（Degree Distribution）是刻画图全局拓扑的关键统计量，例如在社交网络中常呈现幂律分布（Power-law Distribution），即少数节点拥有大量连接（枢纽节点，Hubs），而大多数节点连接稀少，这类图称为无标度图（Scale-free Graph）。

基于邻接矩阵和度矩阵，可定义图拉普拉斯矩阵（Graph Laplacian） $\mathbf{L} = \mathbf{D} - \mathbf{A}$。其归一化形式如对称归一化拉普拉斯 $\mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2}$ 或随机游走归一化拉普拉斯 $\mathbf{L}_{\text{rw}} = \mathbf{D}^{-1} \mathbf{L}$，在谱图理论（Spectral Graph Theory）中具有核心地位。拉普拉斯矩阵的特征向量（Eigenvectors）和特征值（Eigenvalues）揭示了图的全局几何性质，如连通性（Connectivity）、聚类结构（Clustering Structure）和社群划分（Community Detection）。例如，拉普拉斯矩阵的第二小特征值（代数连通度，Algebraic Connectivity）衡量图的整体连接紧密度；对应的特征向量可用于谱聚类（Spectral Clustering）。这些矩阵表示不仅为图信号处理（Graph Signal Processing）提供了基础，也直接启发了图神经网络中卷积操作的设计。

图可根据节点和边的类型多样性进一步分类。同构图（Homogeneous Graph） 中所有节点属于同一类型，所有边属于同一类型，如简单的社交网络或引文网络。异构图（Heterogeneous Graph） 则包含多种节点类型（如用户、商品、店铺）和多种边类型（如购买、浏览、收藏），典型例子是电商平台中的用户-商品交互图或学术知识图谱（包含作者、论文、会议等实体及相应关系）。异构图通常用元路径（Meta-path） 来描述复杂类型间的语义路径，如“作者-论文-会议”表示作者发表于某会议。此外，图还可以是动态的（Dynamic），即节点、边或属性随时间演变，如社交网络中的好友关系增减、交通网络中流量的实时变化。动态图可进一步分为离散时间动态图（Discrete-time Dynamic Graph） 和连续时间动态图（Continuous-time Dynamic Graph），需要不同的建模策略。

为直观理解，考虑以下具体实例：

• **社交网络图**：节点为用户，边表示“关注”关系（有向），可能有权重（互动频率）。节点特征为用户profile信息，边特征可能为互动时间序列。此类图通常规模巨大（数十亿节点），稀疏，且具有小世界（Small-world）特性（高聚类系数、短平均路径长度）。
• **分子图**：节点为原子，边为化学键（通常无向，但可区分单双键）。节点特征为原子类型、电荷等，边特征为键类型、键长。分子图通常较小（数十至数百个节点），但结构决定化学性质，是药物发现的关键。
• **交通网络图**：节点为路口或传感器，边为道路段，权重为距离或通行时间。节点特征可能为车流量，边特征为限速。此类图常为网格状近似，但实际道路拓扑可能不规则。
• **知识图谱**：节点为实体（人、地点、概念），边为关系（如“出生地”、“职业”）。通常为异构图，节点和边均有类型。例如Freebase或Wikidata，包含数千万实体和数十亿事实。

这些实例表明，图数据能够灵活编码现实世界中实体间复杂多样的关系，其表示能力远超传统表格或网格结构。下表总结了常见图类型及其特征：

| 图类型 | 节点/边属性 | 典型应用 | 规模/稀疏性 | |--------|-------------|----------|-------------| | 无向无权图 | 可能无属性 | 友谊网络、合作网络 | 中等，较稀疏 | | 有向加权图 | 通常有权重 | 引文网络、链接分析 | 大，极稀疏 | | 属性图 | 节点/边特征丰富 | 社交推荐、分子预测 | 可变 | | 异构图 | 多类型节点/边 | 知识图谱、电商网络 | 大，稀疏 | | 动态图 | 时变结构/属性 | 动态社交、交通流 | 大，连续或离散变化 |

图数据的独特性质：置换不变性与拓扑结构

图数据区别于欧氏数据的核心在于其内在的置换不变性（Permutation Invariance） 和拓扑敏感性（Topological Sensitivity）。理解这些性质是设计有效图学习算法的基础。

置换不变性 指图的表示和学习的输出不应依赖于节点顺序的任意排列。数学上，若 $\pi: V \to V$ 是节点集的一个置换（双射），则图 $G = (V, E, \mathbf{X})$ 经置换后得到 $\pi(G) = (V, \pi(E), \mathbf{X}_\pi)$，其中 $\pi(E) = \{(\pi(u), \pi(v)) \mid (u,v) \in E\}$，$\mathbf{X}_\pi$ 是特征矩阵按 $\pi$ 重排后的矩阵。理想的图学习函数 $f$ 应满足 $f(G) = f(\pi(G))$，即输出不变。这一性质源于图作为集合的本质：节点本身没有内在顺序，其身份仅由连接关系定义。例如，一个社交网络图中，重新编号用户不应改变其整体社区结构或枢纽节点的识别。相比之下，欧氏数据如图像具有固定的网格顺序（像素坐标），顺序改变会彻底改变内容。

置换不变性对神经网络设计提出了严格要求：网络层必须对输入节点的排列保持不变。这意味着不能直接使用依赖于顺序的操作（如标准全连接层中权重矩阵与特征向量的固定乘法），因为若随机打乱输入节点顺序，全连接层的输出会剧烈变化。为实现置换不变性，图神经网络普遍采用对称聚合函数（Symmetric Aggregation Function），如求和（Sum）、平均值（Mean）或最大值（Max），对邻居信息进行聚合。例如，在消息传递框架中，节点 $v_i$ 的新表示通过聚合其邻居集合 $\mathcal{N}(i)$ 的消息得到：$\mathbf{h}_i' = \text{AGGREGATE}(\{\mathbf{m}_{j \to i} \mid j \in \mathcal{N}(i)\})$，其中聚合函数 AGGREGATE 是对称的，因此结果不依赖于邻居顺序。这种设计保证了无论节点如何编号，同一节点的聚合结果不变，从而满足置换不变性。

拓扑结构 是图数据的另一核心特征，指节点间连接关系形成的整体模式，包括路径（Paths）、环（Cycles）、聚类（Clusters）、社区（Communities）等。拓扑信息编码了实体间的间接关系与全局依赖，例如在社交网络中，“朋友的朋友”可能影响个人兴趣；在分子中，原子间的环结构决定化学稳定性。与欧氏数据中局部邻域（如图像中像素的矩形窗口）的几何邻近性不同，图的邻域由拓扑邻接定义，可能跨越任意距离，且形状不规则。这种拓扑敏感性要求学习算法能够捕捉多跳（Multi-hop）关系：节点 $v_i$ 与距离为 $k$ 的节点 $v_j$ 通过长度为 $k$ 的路径相连，其影响需通过 $k$ 层消息传递逐步传播。

拓扑结构的量化指标包括：

• **度分布（Degree Distribution）**：$P(k) = \frac{|\{v \mid \deg(v)=k\}|}{n}$，描述节点度的统计规律。幂律分布 $P(k) \sim k^{-\gamma}$ 表明无标度特性，对鲁棒性与脆弱性有深远影响。
• **聚类系数（Clustering Coefficient）**：衡量节点邻居间的连接紧密程度。对于节点 $v_i$，局部聚类系数 $C_i = \frac{2|\mathcal{N}(i)|}{k_i(k_i-1)}$，其中 $\mathcal{N}(i)$ 是邻居间实际边数，$k_i$ 是度。全局聚类系数为所有 $C_i$ 的平均。高聚类系数意味着“三角形关系”普遍，常见于社交网络。
• **平均路径长度（Average Path Length）**：所有节点对间最短路径长度的平均值，反映网络的小世界性。小世界网络具有高聚类系数和短平均路径长度，如社交网络。
• **社区结构（Community Structure）**：节点划分为若干组，组内连接密集，组间连接稀疏。模块度（Modularity）是常用度量。

这些拓扑指标不仅描述图的性质，也直接影响图学习算法的设计。例如，高聚类系数提示模型应关注三角形闭合模式；长路径依赖要求网络具备深层的消息传递能力以捕获远距离关系。

与欧氏数据的对比进一步凸显图数据的独特性：

| 特性 | 欧氏数据（图像/文本） | 图数据 | |------|----------------------|--------| | 结构 | 规则网格（图像）或序列（文本） | 不规则拓扑 | | 输入尺寸 | 固定（如 $224 \times 224$ 图像） | 可变（节点数任意） | | 不变性 | 平移不变性（Translation Invariance） | 置换不变性（Permutation Invariance） | | 邻域定义 | 固定几何邻域（如 $3 \times 3$ 卷积核） | 拓扑邻域（直接邻居集合） | | 归纳偏置 | 局部性、平移对称性 | 节点关系对称性、图同构 | | 表示学习 | 卷积/循环网络，层次化特征 | 消息传递，聚合与更新 |

欧氏数据学习（如图像分类）依赖于平移不变性：卷积核在图像不同位置共享参数，使得模型对目标位置变化鲁棒。而图学习依赖置换不变性：网络参数对所有节点一致，聚合函数对称，确保节点顺序无关。这一根本差异导致图神经网络无法直接套用卷积或循环结构，必须发展出新的架构范式。

图学习与欧氏数据学习的范式差异

传统深度学习在欧氏数据上取得了巨大成功，其成功很大程度上归功于数据固有的规则结构和强归纳偏置（Inductive Bias）。卷积神经网络（Convolutional Neural Networks, CNNs） 通过局部连接、权值共享和池化操作，有效提取图像的空间层次特征；循环神经网络（Recurrent Neural Networks, RNNs） 及其变体（如LSTM、GRU）通过时序展开处理序列数据，捕获长程依赖。这些模型均假设输入具有固定维度和平移/时序不变性，其核心操作（卷积、循环）直接建立在规则的网格或序列拓扑上。

图学习则面临完全不同的范式。由于图结构的不规则性与变体性，无法定义全局的、平移不变的卷积核。例如，一个节点的邻居数量可能从1到数百不等，邻居的排列顺序无意义，且不同节点的邻居集合可能完全不同。这迫使图学习范式必须回答两个根本问题：（1）如何定义图上的“卷积”操作，使其能适应任意拓扑并保持置换不变性？（2）如何设计可处理变尺寸图的神经网络，使其在训练时见过的图结构上训练，并能泛化到未见过的新图？

早期图学习尝试通过将图映射到欧氏空间来规避结构问题。例如，图核方法（Graph Kernels） 如Weisfeiler-Lehman核，通过比较图的结构特征（如节点标签分布）计算相似度，再结合SVM进行分类。这些方法依赖手工设计的特征提取器，可解释性强但表达能力有限。图嵌入（Graph Embedding） 方法如DeepWalk、Node2Vec，将节点映射到低维向量空间，通过随机游走生成序列，再用Skip-gram模型学习嵌入，本质上是将图结构“序列化”，损失了部分全局拓扑信息。这些方法虽有效，但未能实现端到端的深度特征学习。

图神经网络（GNNs）的提出标志着图学习进入深度学习时代。GNNs的核心思想是消息传递（Message Passing） 或邻居聚合（Neighborhood Aggregation），其通用框架可形式化为：

$$ \mathbf{h}_v^{(k)} = \text{UPDATE}^{(k)} \left( \mathbf{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)} \left( \{ \mathbf{m}_{u \to v}^{(k)} = \text{MSG}^{(k)}(\mathbf{h}_u^{(k-1)}, \mathbf{h}_v^{(k-1)}, \mathbf{e}_{uv}) \mid u \in \mathcal{N}(v) \} \right) \right) $$

其中，$\mathbf{h}_v^{(k)}$ 是节点 $v$ 在第 $k$ 层的隐藏表示，$\mathcal{N}(v)$ 是 $v$ 的邻居集合，$\mathbf{e}_{uv}$ 是边属性（可选）。MSG、AGGREGATE、UPDATE 是可学习的函数（通常为神经网络）。这一框架的优雅之处在于：（1）置换不变性自然满足：AGGREGATE 使用对称函数（如sum、mean、max），对邻居顺序不敏感；（2）拓扑结构显式编码：消息沿边传递，聚合操作直接利用邻接关系；（3）变尺寸图处理：每层更新独立应用于每个节点，不依赖全局图大小，因此训练好的模型可泛化到任意大小的图。

与欧氏数据学习范式对比可见：

| 维度 | 欧氏数据学习（CNN/RNN） | 图学习（GNN） | |------|------------------------|---------------| | 基本操作 | 卷积（固定核）、循环（时序展开） | 消息传递（邻居聚合） | | 参数共享 | 空间/时序位置共享 | 所有节点共享同一组参数 | | 归纳偏置 | 平移不变性、局部性 | 置换不变性、拓扑同构 | | 输入处理