源自论文：Survey on Graph Neural Networks

图神经网络（GNNs）中的符号与定义详解

本文使用了图论和深度学习领域的标准符号体系，以确保对图结构数据的描述清晰一致。以下是核心符号和定义的详细说明：

一、基础图结构符号

• 图（Graph）：用 $G=(V,E)$ 表示，其中：

  • $V$：节点（vertices/nodes）的集合，$|V|=n$ 表示节点数量。
  • $E$：边（edges）的集合，$E\subset V\times V$，$|E|=m$ 表示边数量。

• 边（Edge）：用 $e_{ij}=(v_i,v_j)\in E$ 表示连接节点 $v_i$ 和 $v_j$ 的边，其中 $i,j\in \mathbb{N}$ 且 $1\le i,j\le |V|$。

• 邻居（Neighborhood）：节点 $v$ 的邻居集合定义为 N(v)={u∈V∣(v,u)∈E}N(v) = \{ u \in V \mid (v, u) \in E \}N(v)={u∈V∣(v,u)∈E}，即所有与 $v$ 直接相连的节点。

二、矩阵与特征符号

1. 邻接矩阵（Adjacency Matrix）：

   • 用 $A=(a_{ij})$ 表示，是一个 $n\times n$ 的矩阵，其中：
     • $a_{ij}=1$ 若 $e_{ij}\in E$（节点 $i$ 和 $j$ 相连）；
     • $a_{ij}=0$ 若 $e_{ij}\notin E$（节点 $i$ 和 $j$ 不相连）。

2. 带自环的邻接矩阵：

   • 用 $\tilde{A}=A+I$ 表示，其中 $I$ 是单位矩阵（对角线元素为1，其余为0），用于将节点自身纳入邻居计算。

3. 归一化邻接矩阵：

   • 用 $\hat{A}={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$ 表示，其中 $\tilde{D}$ 是 $\tilde{A}$ 的度矩阵（对角线元素为节点的度，即邻居数量）。归一化可避免因节点度差异导致的特征偏差。

4. 节点特征矩阵：

   • 用 $X\in {\mathbb{R}}^{n\times d}$ 表示，其中 $d$ 是节点特征维度，$x_v\in {\mathbb{R}}^d$ 表示节点 $v$ 的特征向量。

5. 边特征矩阵：

   • 用 $X^e\in {\mathbb{R}}^{m\times c}$ 表示，其中 $c$ 是边特征维度，$x_{(v,u)}^e\in {\mathbb{R}}^c$ 表示边 $(v,u)$ 的特征向量。

6. 隐藏特征矩阵：

   • 用 $H\in {\mathbb{R}}^{n\times b}$ 表示，其中 $b$ 是隐藏特征维度，$h_v\in {\mathbb{R}}^b$ 表示节点 $v$ 的隐藏特征向量（经GNN层处理后的值）。

7. 嵌入矩阵：

   • 用 $Z\in {\mathbb{R}}^{n\times b}$ 表示，是节点的低维嵌入向量矩阵，$z_v\in {\mathbb{R}}^b$ 表示节点 $v$ 的嵌入向量。

三、时间相关符号

• 时间步特征矩阵：用 $X^{(t)}\in {\mathbb{R}}^{n\times d}$ 表示，用于动态图中，描述时间步 $t$ 时的节点特征。

四、其他关键符号

• 转置矩阵：用 $A^T$ 表示矩阵 $A$ 的转置。
• 拼接操作：用 $\Vert$ 表示向量或矩阵的拼接（如 $[a\Vert b]$ 表示将向量 $a$ 和 $b$ 拼接）。
• 度矩阵（Degree Matrix）：用 $D$ 表示，对角线元素为节点的度（即邻居数量），非对角线元素为0。

符号汇总表

符号	描述
$G=(V,E)$	图（节点集 $V$ 和边集 $E$）
$V$	节点集合，$
$v$	单个节点（$v\in V$）
$E$	边集合，$
$e_{ij}$	连接节点 $v_i$ 和 $v_j$ 的边
$N(v)$	节点 $v$ 的邻居集合
$A$	邻接矩阵（$n\times n$）
$\tilde{A}$	带自环的邻接矩阵（$\tilde{A}=A+I$）
$\hat{A}$	归一化带自环邻接矩阵
$D$	度矩阵
$n$	节点数量
$m$	边数量
$d$	节点特征维度
$b$	隐藏特征/嵌入维度
$c$	边特征维度
$X\in {\mathbb{R}}^{n\times d}$	节点特征矩阵
$x_v\in {\mathbb{R}}^d$	节点 $v$ 的特征向量
$X^e\in {\mathbb{R}}^{m\times c}$	边特征矩阵
$x_{(v,u)}^e\in {\mathbb{R}}^c$	边 $(v,u)$ 的特征向量
$H\in {\mathbb{R}}^{n\times b}$	节点隐藏特征矩阵
$h_v\in {\mathbb{R}}^b$	节点 $v$ 的隐藏特征向量
$Z\in {\mathbb{R}}^{n\times b}$	节点嵌入矩阵
$z_v\in {\mathbb{R}}^b$	节点 $v$ 的嵌入向量
$X^{(t)}$	时间步 $t$ 的节点特征矩阵
$|$	向量/矩阵拼接操作

图神经网络（GNNs）的核心任务详解

图神经网络（GNNs）主要用于处理图结构数据，其任务可分为节点级、边级、图级以及新兴的图生成和图结构学习，每类任务针对图数据的不同层面进行预测或学习。以下是各任务的详细说明：

一、节点分类（Node Classification）

• 定义：预测图中节点的未知标签，利用节点自身特征及其与其他节点的连接关系（拓扑结构）。
• 形式化描述：设图 $G=(V,E)$，已知部分节点 $V_l\subset V$ 的标签，通过学习映射函数 $f$ 预测剩余节点 $V_u=V\setminus V_l$ 的标签。
• 应用场景：
  • 社交网络中预测用户的政治倾向或兴趣标签；
  • 蛋白质-蛋白质相互作用网络中预测蛋白质的功能角色；
  • 网页分类（如将网页分为“新闻”“教育”等语义类别）。
• 典型数据集：Cora（学术论文分类）、Citeseer（文献分类）、Pubmed（生物医学文献分类）、Chameleon、Wisconsin等。

二、链路预测（Link Prediction）

• 定义：预测图中节点间潜在的未观测边，即判断两个节点是否存在连接。
• 形式化描述：设图 $G=(V,E)$，所有可能的边集合为 $M$，未观测边集合为 $E^{\prime }=M\setminus E$，任务是从 $E^{\prime }$ 中识别最可能存在的边。
• 应用场景：
  • 社交网络中预测潜在的好友关系；
  • 知识图谱补全（如预测“人物-出生地”等缺失关系）；
  • 推荐系统中预测用户可能感兴趣的物品（用户-物品交互图）。
• 典型数据集：WN18、WN18RR（基于WordNet的知识图谱）、FB15k、FB15k-237（基于Freebase的知识图谱）、ICEWS05-15（事件时序知识图谱）等。

三、图分类（Graph Classification）

• 定义：将整个图作为样本，分类到预定义的类别中，预测结果反映图的全局特征。
• 形式化描述：给定带标签的图集合 $S=\{(G_i,y_i)\}$（$y_i$ 为图 $G_i$ 的标签），学习函数 $f$ 预测新图的标签。
• 应用场景：
  • 分子结构分类（如判断分子是否具有致癌性）；
  • 社交网络类型分类（如区分“学术合作网络”和“社交好友网络”）；
  • 蛋白质结构分类（如酶与非酶的区分）。
• 典型数据集：PROTEINS（蛋白质结构分类）、MUTAG（诱变化合物分类）、NCI1（抗癌化合物分类）、ENZYMES（酶分类）、IMDb-B（电影合作网络分类）等。

四、图生成（Graph Generation）

• 定义：学习图数据的潜在分布，生成与原始图结构相似的新图。
• 形式化描述：给定图集合 G={G1,...,GM}G = \{G_1, ..., G_M\}G={G1​,...,GM​}，学习分布 $P(G)$ 并从中采样生成新图 $\hat{G}$。
• 应用场景：
  • 药物发现中生成具有特定药理特性的分子结构；
  • 社交网络模拟（生成符合真实网络拓扑特性的 synthetic 网络）；
  • 知识图谱扩展（生成合理的新实体与关系）。
• 典型数据集：QM9（分子生成，含134k小分子的3D结构数据）、ZINC（含250k药物分子的结构数据）、MOSES（分子生成基准数据集）。

五、图结构学习（Graph Structure Learning）

• 定义：从非图结构数据中学习潜在的图拓扑，或优化已有图的结构（解决原始图可能存在的噪声、缺失或冗余问题）。
• 核心目标：
  • 对于非图数据（如图片、文本），推断数据点间的潜在关联（如文本中词语的共现关系）；
  • 对于已有图，修正错误边或补充缺失边，提升GNN模型的鲁棒性。
• 相关方法：GRCN（图修正卷积网络）、IDGL（迭代深度图学习）、SLAPS（自监督结构学习）、SUBLIME（无监督图结构学习）等。

任务总结与关联

任务类型	核心目标	输入	输出	典型应用领域
节点分类	预测节点标签	图 + 部分节点标签	剩余节点标签	社交网络、知识图谱
链路预测	预测潜在边	图	边存在概率	推荐系统、知识补全
图分类	预测图的类别	图集合 + 图标签	新图的类别	分子分类、网络类型识别
图生成	生成新图	图集合	新图（结构/特征）	药物发现、网络模拟
图结构学习	学习/优化图拓扑	非图数据或噪声图	优化后的图结构	数据建模、鲁棒性提升

这些任务相互关联，例如图结构学习可为节点分类或链路预测提供更准确的输入图，而图生成可辅助扩充训练数据以提升其他任务的性能。GNN通过捕捉图的局部与全局依赖关系，在这些任务中展现出远超传统方法的优势。

图神经网络（GNN）的分类与框架详解

五大类：递归图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自编码器、图的深度生成模型和动态图上的图神经网络。以下是各类别的详细说明：

一、递归图神经网络（Recurrent Graph Neural Networks, RecGNNs）

递归图神经网络（RecGNNs）是最早出现的图神经网络架构之一，其核心思想是通过节点与邻居之间的迭代信息交换，使每个节点的状态逐渐收敛到稳定值，从而学习图的结构特征。以下从核心原理、关键模型及特点展开详细说明：

一、核心原理

• 信息传递机制：假设图中每个节点会持续与邻居交换信息，直到所有节点的状态达到稳定平衡（即状态更新量趋近于0）。
• 权重共享：递归层之间共享参数，避免因图结构不规则导致的参数爆炸问题。
• 收敛保证：早期模型通过设计收缩映射（contraction mapping） 确保迭代过程收敛，即节点状态的更新函数需满足 Lipschitz 条件（函数输出变化幅度不超过输入变化幅度）。

二、关键模型

1. GNN（Graph Neural Network）

   • 提出背景：首次将递归神经网络推广到任意图结构，是RecGNNs的基础模型。
   • 状态更新公式：
     $$h_v=f\left(x_v,x_{(u,v)}^e,h_{N(v)},x_{N(v)}\right)$$
     其中，$h_v$ 是节点 $v$ 的状态，$x_v$ 是节点特征，$x_{(u,v)}^e$ 是边特征，$h_{N(v)}$ 和 $x_{N(v)}$ 分别是邻居的状态和特征，$f$ 为局部转换函数（需满足收缩映射性质）。
   • 特点：通过迭代更新节点状态直至收敛，适用于静态图的节点分类等任务，但计算复杂度较高。

2. GraphESN（Graph Echo State Network）

   • 改进思路：基于回声状态网络（ESN），简化训练过程。
   • 核心设计：
     • 固定的收缩编码函数（随机初始化，无需训练），负责节点状态的迭代更新；
     • 仅训练输出层（前馈神经网络），大幅提升效率。
   • 优势：相比GNN训练速度更快，适合处理大规模图。

3. GGNNs（Gated Graph Neural Networks）

   • 突破点：去除收缩映射限制，引入门控循环单元（GRU） 控制信息流动，解决收敛难题。
   • 机制：
     • 递归过程固定步数展开（如3-5步），无需等待收敛；
     • 通过时间反向传播（BPTT） 计算梯度，支持端到端训练。
   • 扩展：GGS-NNs（Gated Graph Sequence Neural Networks）将GGNNs应用于序列输出任务（如生成图的节点序列）。

4. SSE（Successive Stochastic Embedding）

   • 目标：提升大规模图上的训练效率，同时保证收敛。
   • 关键步骤：
     • 更新阶段：通过算子更新节点嵌入；
     • 投影阶段：将嵌入投影到满足稳态条件的子空间，强制收敛。
   • 特点：适合需要快速部署的场景，如实时图分析。

5. Graph LSTM

   • 设计思路：将长短期记忆网络（LSTM）推广到图结构，替换GRU以更好地捕捉长距离依赖。
   • 应用：自然语言处理（如跨句关系抽取）、语义目标解析等需要处理复杂依赖的任务。

三、特点与局限性

• 优势：
  • 能有效捕捉图中节点的长期依赖关系（通过多轮信息传递）；
  • 权重共享机制适应图的不规则结构。
• 局限性：
  • 早期模型依赖收缩映射，限制了函数表达能力；
  • 迭代过程可能导致计算效率低下（尤其对大规模图）；
  • 难以处理动态图（节点/边随时间变化的场景）。

四、应用场景

• 节点分类（如社交网络用户标签预测）；
• 图序列建模（如动态分子结构变化预测）；
• 语义解析（如基于图结构的文本关系抽取）。

RecGNNs为后续图神经网络的发展奠定了基础，其信息传递的核心思想被广泛借鉴（如ConvGNNs的消息传递机制）。尽管被更高效的架构（如GCN、GAT）部分替代，但在需要捕捉长期依赖的任务中仍有独特价值。

二、卷积图神经网络（Convolutional Graph Neural Networks, ConvGNNs）

卷积图神经网络（ConvGNNs）是图神经网络中最具影响力的类别之一，其核心思想借鉴了卷积神经网络（CNNs）的局部特征聚合能力，但针对图结构的不规则性进行了适配。根据卷积操作的定义方式，ConvGNNs可分为谱域方法（Spectral-based） 和空间域方法（Spatial-based） 两大类。以下是详细说明：

一、核心思想与挑战

• 灵感来源：CNNs通过滑动窗口在规则网格（如图像）上聚合局部特征，而ConvGNNs旨在将这一思想推广到非欧几里得结构的图中。
• 关键挑战：图节点无固定顺序、邻居数量可变，传统网格卷积无法直接应用。ConvGNNs通过定义“图卷积”操作解决这一问题，核心是聚合节点的局部邻居特征以更新自身表示。
• 与RecGNNs的区别：ConvGNNs使用固定层数且层间权重不同，无需迭代至稳态，计算效率更高。

二、谱域卷积图神经网络（Spectral-based ConvGNNs）

谱域方法基于谱图理论和图信号处理，通过图的傅里叶变换将卷积操作转换到谱域进行计算，具有坚实的数学基础。

1. 理论基础

• 图拉普拉斯矩阵（Laplacian Matrix）：定义为 $L=D-A$（$D$ 为度矩阵，$A$ 为邻接矩阵），其特征值和特征向量刻画了图的全局结构。
• 图傅里叶变换：将节点信号 $x$ 映射到谱域：$\mathcal{F}(x)=U^{T}x$，其中 $U$ 是 $L$ 的特征向量矩阵。
• 谱域卷积：利用卷积定理，定义为谱域中信号与滤波器的点积：
  $$g\ast x={\mathcal{F}}^{-1}(\mathcal{F}(g)\odot \mathcal{F}(x))=U(U^{T}g\odot U^{T}x)$$
  简化后为 $g_w\ast x=U{g}_w{U}^{T}x$（$g_w$ 为对角化的滤波器参数）。

2. 关键模型

• Spectral Networks（2014）
  首个将CNN推广到图域的模型，基于图拉普拉斯谱设计卷积层，通过分层聚类和谱分解实现参数共享，但计算复杂度高（依赖特征分解）。

• ChebNet（2017）
  用切比雪夫多项式近似谱滤波器，将卷积操作局部化：
  $$h^{(l+1)}=\sum _{k=0}^K{W}_k{T}_k(\tilde{L})h^{(l)}$$
  其中 $T_k$ 为切比雪夫多项式，$\tilde{L}$ 为归一化拉普拉斯矩阵。该模型避免了特征分解，降低了计算量。

• GCN（Graph Convolutional Network, 2017）
  对ChebNet进行一阶近似，简化为：
  $$h^{(l+1)}=\sigma (\hat{A}{h}^{(l)}{W}^{(l)})$$
  其中 $\hat{A}={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$（$\tilde{A}=A+I$ 为带自环的邻接矩阵）。GCN平衡了效率与性能，成为谱域与空间域的桥梁。

• 其他重要模型

  • CayleyNets：使用Cayley多项式构建谱滤波器，支持对特定频率带的关注。
  • GWNN（Graph Wavelet Neural Network）：基于图小波变换，无需特征分解，计算更高效。
  • BernNet：用伯恩斯坦多项式近似滤波器，改进ChebNet的数值不稳定性。

三、空间域卷积图神经网络（Spatial-based ConvGNNs）

空间域方法直接在图的节点空间中定义卷积，通过聚合邻居节点的特征更新中心节点表示，更直观且易于理解。

1. 核心思想

• 局部聚合：节点的新特征由自身特征和邻居特征通过可学习的函数聚合得到（如加权求和、池化等）。
• 挑战：邻居节点无序性需通过对称函数（如求和、均值）处理；邻居数量差异需通过归一化（如度归一化）缓解。

2. 关键模型

• MPNN（Message Passing Neural Network, 2017）
  通用框架，包含两个阶段：

  1. 消息传递：邻居向中心节点传递消息：
     $$m_v^{(l+1)}=\sum _{u\in N(v)}{M}^{(l)}(h_v^{(l)},h_u^{(l)},e_{vu})$$
     （$M^{(l)}$ 为消息函数，$e_{vu}$ 为边特征）
  2. 读出（Readout）：聚合所有节点特征得到图表示：
     y^=R({hvT∣v∈G}) \hat{y} = R(\{h_v^T \mid v \in G\}) y^​=R({hvT​∣v∈G})
     MPNN统一了多数空间域模型的设计范式。

• GraphSAGE（2017）
  支持归纳学习（对未见过的节点进行预测），包含两个步骤：

  1. 邻居采样：为每个节点采样固定数量的邻居（如20个），控制计算量；
  2. 聚合函数：通过均值、LSTM或池化（max/min）聚合邻居特征，例如：
     hv(l+1)=σ(W(l)⋅mean({hv(l)}∪{hu(l)∣u∈N(v)})) h_v^{(l+1)} = \sigma(W^{(l)} \cdot \text{mean}(\{h_v^{(l)}\} \cup \{h_u^{(l)} \mid u \in N(v)\})) hv(l+1)​=σ(W(l)⋅mean({hv(l)​}∪{hu(l)​∣u∈N(v)}))

• GAT（Graph Attention Network, 2017）
  引入注意力机制，为不同邻居分配动态权重：
  $$h_i^{(l+1)}=\sigma \left(\sum _{j\in N(i)}{\alpha }_{ij}{W}^{(l)}{h}_j^{(l)}\right)$$
  其中注意力系数 ${\alpha }_{ij}$ 通过以下方式计算：
  $${\alpha }_{ij}={\text{softmax}}_j\left(\text{LeakyReLU}\left(a^T\left[W{h}_i\Vert W{h}_j\right]\right)\right)$$
  GAT解决了邻居重要性差异的问题，性能优于GCN。

• 其他重要模型

  • GATv2：调整注意力计算顺序（先激活后拼接），增强动态适应性。
  • HAN（Heterogeneous Graph Attention Network）：针对异构图（多类型节点/边），使用节点级和语义级双层注意力。
  • JK-Nets：融合不同跳数的邻居信息（如拼接、LSTM-attention），缓解过平滑问题。

四、谱域与空间域方法的对比

维度	谱域方法（Spectral-based）	空间域方法（Spatial-based）
理论基础	谱图理论，依赖图拉普拉斯矩阵的特征分解	直接在节点空间操作，依赖邻居聚合规则
计算效率	高复杂度（特征分解为 $O(n^3)$），难扩展	低复杂度（局部聚合为 $O(m)$），易扩展到大规模图
局部性	需通过多项式近似实现局部化	天然局部（仅聚合邻居）
灵活性	依赖全局图结构，难处理动态图	不依赖全局结构，支持动态图和归纳学习
代表模型	ChebNet、GCN	GraphSAGE、GAT、MPNN

五、应用场景

• 节点分类：如文献主题分类（Cora数据集）、蛋白质功能预测。
• 链路预测：如社交网络好友推荐、知识图谱补全。
• 图分类：如分子毒性预测（MUTAG数据集）、网络类型识别。
• 推荐系统：如基于用户-物品交互图的个性化推荐（LightGCN）。

ConvGNNs通过谱域或空间域的卷积操作，有效捕捉图的局部结构和节点依赖关系，成为处理图数据的主流工具。其中，空间域方法因灵活性和可扩展性，近年来更受关注，衍生出大量变体（如注意力机制、采样策略优化等），持续推动GNN领域的发展。

三、图自编码器（Graph Autoencoders）

图自编码器（Graph Autoencoders）详解

图自编码器（Graph Autoencoders）是一类专为图结构数据设计的无监督学习模型，通过编码-解码框架学习图的低维表示（嵌入），同时保留图的结构特征和节点属性。其核心目标是通过重构输入图的关键信息（如邻接结构、节点特征），捕捉图的本质模式。以下从核心原理、关键模型及应用展开详细说明：

一、核心原理

• 框架结构：由编码器（Encoder） 和解码器（Decoder） 两部分组成：

  • 编码器：将输入图（节点特征矩阵 $X$ 和邻接矩阵 $A$）映射到低维潜在空间，输出节点嵌入矩阵 $Z\in {\mathbb{R}}^{n\times b}$（$n$ 为节点数，$b$ 为嵌入维度）。
  • 解码器：从嵌入矩阵 $Z$ 重构原始图的关键信息（如邻接矩阵 $\hat{A}$ 或节点特征 $\hat{X}$），通过最小化重构误差优化模型参数。

• 学习目标：通过重构损失（如重构邻接矩阵与原始矩阵的差异）训练模型，使嵌入 $Z$ 尽可能保留图的结构和特征信息，支持下游任务（如节点分类、链路预测）。

二、关键模型

1. 基础图自编码器（Graph Autoencoder, GAE）

   • 设计：编码器采用图卷积网络（GCN），解码器通过内积重构邻接矩阵。
   • 公式：
     • 编码：$Z=GCN(X,A)$（GCN输出节点嵌入）；
     • 解码：$\hat{A}=\sigma (Z{Z}^T)$（$\sigma$ 为sigmoid函数，通过节点嵌入的内积预测边存在概率）。
   • 特点：首次将GCN与自编码器结合，同时利用节点特征和图结构，适用于链路预测和节点嵌入学习。

2. 变分图自编码器（Variational Graph Autoencoder, VGAE）

   • 改进：基于变分自编码器（VAE），引入概率建模，编码器输出嵌入的均值和方差（而非确定值），增强嵌入的鲁棒性。
   • 公式：
     • 编码：$\mu =GC{N}_{\mu }(X,A)$，$\log \sigma =GC{N}_{\sigma }(X,A)$（通过两个GCN分别预测均值和方差）；
     • 采样：$Z=\mu +\sigma \cdot ϵ$（$ϵ\sim \mathcal{N}(0,I)$ 为噪声，实现重参数化）；
     • 解码：与GAE一致，$\hat{A}=\sigma (Z{Z}^T)$。
   • 损失函数：重构损失 + KL散度（正则化嵌入分布接近标准正态分布）。
   • 优势：生成的嵌入更平滑，泛化能力更强，适合图生成任务。

3. LINE（Large-scale Information Network Embedding）

   • 设计：针对大规模网络优化，通过保留一阶邻近性（直接连接的节点相似性）和二阶邻近性（邻居结构相似性）学习嵌入。
   • 目标函数：
     • 一阶损失：${\mathcal{L}}_1=-{\sum }_{(u,v)\in E}\log \sigma ({\mathbf{z}}_u^T{\mathbf{z}}_v)$；
     • 二阶损失：${\mathcal{L}}_2=-{\sum }_{u\in V}{\sum }_{v\in N(u)}\log \sigma ({\mathbf{z}}_u^T{\mathbf{z}}_v^{\prime })$（${\mathbf{z}}_v^{\prime }$ 为节点 $v$ 的上下文嵌入）。
   • 特点：计算高效（复杂度 $O(m)$），可处理百万级节点网络（如社交网络）。

4. SDNE（Structural Deep Network Embedding）

   • 设计：结合深层神经网络与图结构约束，捕捉图的非线性结构。
   • 机制：
     • 编码器：用堆叠的自编码器将节点特征映射到嵌入空间；
     • 解码器：重构节点的邻接关系；
     • 损失函数：结合重构损失（二阶邻近性）和拉普拉斯正则项（一阶邻近性）。
   • 优势：适合处理非线性强的复杂网络（如生物网络），保留全局和局部结构。

5. DNGR（Deep Neural Network for Graph Representation）

   • 设计：基于随机游走构建节点共现矩阵，再通过堆叠去噪自编码器学习嵌入。
   • 步骤：
     1. 生成随机游走序列，计算节点共现概率；
     2. 转换为PPMI（正点互信息）矩阵作为输入；
     3. 用去噪自编码器（添加噪声增强鲁棒性）学习低维嵌入。
   • 特点：专注于捕捉图的拓扑结构，不依赖节点特征，适合无属性图。

6. ARGA（Adversarially Regularized Graph Autoencoder）

   • 创新：引入对抗训练，用生成对抗网络（GAN）正则化自编码器。
   • 机制：
     • 生成器：即图自编码器的编码器，生成节点嵌入；
     • 判别器：区分生成的嵌入与真实数据分布的嵌入；
     • 目标：通过对抗损失使生成的嵌入分布更接近真实分布。
   • 优势：缓解嵌入分布过拟合，提升下游任务性能（如节点聚类）。

三、关键特点与局限性

• 优势：

  • 无监督学习：无需节点标签即可训练，适用于标签稀缺场景；
  • 结构保留：同时捕捉节点特征和拓扑关系，嵌入包含丰富信息；
  • 灵活性：编码器和解码器可灵活选择（如GCN、MLP、RNN等），适配不同图类型。

• 局限性：

  • 重构偏差：过度关注重构精度可能导致嵌入冗余，忽略关键特征；
  • ** scalability挑战**：部分模型（如SDNE）计算复杂度高，难处理超大规模图；
  • 动态图适配差：多数模型针对静态图设计，对节点/边动态变化的图适应性弱。

四、应用场景

• 节点聚类：将学习到的嵌入输入k-means等算法，实现图节点的无监督分类（如社区检测）；
• 链路预测：通过解码器重构的邻接矩阵预测潜在边（如社交网络好友推荐）；
• 图可视化：将高维图数据映射到2D/3D空间，直观展示节点间关系；
• 异常检测：利用重构误差识别偏离正常模式的节点或边（如欺诈检测）。

模型对比表

模型	编码器类型	解码器目标	核心优势	适用场景
GAE	GCN	重构邻接矩阵（内积）	结合特征与结构，简单高效	中小型图、链路预测
VGAE	GCN（输出分布）	重构邻接矩阵	嵌入分布更鲁棒，支持生成任务	图生成、半监督学习
LINE	无显式编码器	保留一阶/二阶邻近性	超大规模网络适用，计算高效	社交网络、推荐系统
SDNE	堆叠自编码器	重构非线性结构	捕捉复杂非线性关系	生物网络、复杂拓扑图
DNGR	堆叠去噪自编码器	重构节点共现模式	专注拓扑结构，无属性图适用	纯拓扑图（如引文网络）
ARGA	GCN + 对抗训练	重构邻接矩阵 + 对抗正则	嵌入分布更真实，泛化能力强	节点聚类、异常检测

图自编码器通过无监督学习从图数据中提取有效特征，为图分析提供了强大工具。随着研究推进，其与注意力机制、动态图模型的结合（如动态图自编码器）正成为新方向，进一步扩展了在实时场景（如动态社交网络）中的应用。

四、图的深度生成模型（Deep Generative Models for Graphs）

图的深度生成模型是一类专注于学习图结构数据的潜在分布并生成新图的深度学习模型。这类模型能够捕捉图中节点与边的复杂依赖关系，生成与原始图具有相似拓扑特征或属性的新图，在药物发现、社交网络模拟等领域有重要应用。以下从核心原理、分类及关键模型展开详细说明：

一、核心原理

• 目标：给定一组图 G={G1,G2,...,GM}G = \{G_1, G_2, ..., G_M\}G={G1​,G2​,...,GM​}，学习其潜在分布 $P(G)$，并从该分布中采样生成新图 $\hat{G}$，使 $\hat{G}$ 在结构（如节点连接模式）和属性（如节点/边特征）上与原始图一致。
• 挑战：图的非欧几里得特性（节点无序性、边的依赖关系）使生成过程比图像、文本等规则数据更复杂，需特殊设计以保证生成图的有效性（如无孤立节点、符合领域约束）。

二、分类与关键模型

根据生成机制，图的深度生成模型可分为自编码器基（Autoencoder-based）、对抗基（Adversarial-based） 和自回归基（Autoregressive-based） 三类。

1. 自编码器基模型（Autoencoder-based）

通过编码-解码框架学习图的潜在表示，再从表示中重构或生成新图，代表模型如下：

• VGAE（Variational Graph Autoencoder, 2016）

  • 机制：基于变分自编码器（VAE），编码器用GCN输出节点嵌入的均值和方差，解码器通过内积 $\sigma (z_i^T{z}_j)$ 预测边存在概率。
  • 生成方式：从学习到的高斯分布中采样嵌入，再通过解码器生成邻接矩阵。
  • 局限：仅能从单张图学习分布，生成图规模受限于输入图。

• GraphVAE（2018）

  • 改进：支持从多张图中学习分布，编码器输出图级嵌入，解码器通过递归方式生成节点和边。
  • 特点：生成的图规模可变，但仅适用于小规模图（如分子结构）。

• Graph2Gauss（2017）

  • 创新：将节点嵌入建模为高斯分布（$z_i\sim \mathcal{N}({\mu }_i,{\sigma }_i^2)$），捕捉嵌入的不确定性。
  • 解码：通过KL散度衡量节点相似性，重构图结构。
  • 优势：生成的图更鲁棒，适合噪声图数据。

• GraphMAE（2022）

  • 焦点：通过掩码机制重构节点特征（而非仅重构结构），编码器和解码器可灵活选用任意GNN。
  • 特点：提升特征保留能力，适用于节点属性重要的场景（如知识图谱）。

2. 对抗基模型（Adversarial-based）

借鉴生成对抗网络（GAN）的思想，通过生成器与判别器的对抗训练优化图生成过程：

• NetGAN（2018）

  • 机制：生成器学习图上带偏随机游走的分布，判别器区分真实游走与生成游走。
  • 生成方式：通过生成的随机游走序列重构新图。
  • 优势：适合生成大规模图，保留图的全局拓扑特征（如度分布）。

• GraphGAN（2017）

  • 设计：生成器预测节点对的连接概率，判别器区分真实边与生成边。
  • 目标函数：最小化生成器与判别器的对抗损失，同时保留图的局部结构。
  • 应用：知识图谱补全、社交网络生成。

• ARVGA（Adversarially Regularized Variational Graph Autoencoder, 2018）

  • 融合：结合VGAE与GAN，用对抗损失正则化VAE的潜在分布，使生成的嵌入更接近真实数据分布。
  • 优势：平衡变分推断与对抗训练，提升生成图的多样性。

3. 自回归基模型（Autoregressive-based）

通过序列生成方式逐步构建图，每次生成一个节点或边，依赖已生成的部分结构：

• GraphRNN（2018）

  • 机制：分为图级RNN和边级RNN：
    • 图级RNN：决定新节点的添加；
    • 边级RNN：为新节点生成与已有节点的连接关系。
  • 特点：生成图的规模可变，能捕捉节点顺序依赖，但生成速度较慢。

• DeepGMG（2018）

  • 设计：以节点为中心逐步生成图，每次添加一个节点并连接到现有图，通过LSTM捕捉生成历史。
  • 优势：生成过程直观，适合分子等有明确构建规则的图。

• GraphVRNN（2019）

  • 改进：在GraphRNN基础上引入节点属性建模，生成同时包含结构和属性的图。
  • 应用：带属性的社交网络生成、分子属性预测。

三、关键技术挑战

• 图的有效性：生成的图需满足领域约束（如分子图需符合化学价键规则），需引入额外约束机制（如RGVAE的正则化框架）。
• 计算效率：自回归模型生成过程串行化，速度慢；对抗模型训练不稳定，易模式崩溃。
• 多样性与真实性平衡：生成图需在结构上与原始图相似（真实性），同时避免重复（多样性），需优化损失函数（如Wasserstein距离）。

四、应用场景

• 药物发现：生成具有特定药理特性的分子结构（如QM9、ZINC数据集），加速新药研发。
• 社交网络模拟：生成符合真实拓扑的 synthetic 网络，用于算法测试（如社区检测算法）。
• 知识图谱扩展：自动生成合理的实体与关系，补全不完整的知识图谱。
• 推荐系统：生成用户-物品交互图的潜在连接，提升推荐准确性。

模型对比表

类别	代表模型	生成方式	优势	局限
自编码器基	VGAE、GraphVAE	从潜在分布采样重构	生成稳定，适合小规模图	依赖输入图分布，多样性有限
对抗基	NetGAN、GraphGAN	对抗训练优化生成分布	生成图真实感强，适合大规模图	训练不稳定，需精心调参
自回归基	GraphRNN、DeepGMG	逐步生成节点/边	可控性强，支持可变规模	生成速度慢，依赖节点顺序

图的深度生成模型通过多样化的生成机制，实现了从已知图数据到新图的泛化，为解决图数据稀缺、结构复杂等问题提供了有效工具。未来方向包括提升生成效率、增强领域约束整合，以及拓展动态图生成能力。

五、动态图上的图神经网络（GNNs on Dynamic Graphs）

动态图是指节点、边或其特征随时间变化的图结构（如动态社交网络、交通流量网络）。动态图上的图神经网络（GNNs）旨在捕捉图的时空演化规律，解决静态GNN无法处理时序依赖的问题。本文重点关注离散时间动态图（Discrete-Time Dynamic Graphs, DTDGs），其核心是融合图的结构信息与时间维度的变化模式。以下从定义、处理方法及关键模型展开说明：

一、动态图的定义与分类

• 离散时间动态图（DTDG）：表示为图快照序列 $[G_1,G_2,...,G_M]$，其中每个快照 $G_t=(V_t,A_t,X_t)$ 包含 $t$ 时刻的节点集 $V_t$、邻接矩阵 $A_t$ 和节点特征矩阵 $X_t$。
  • 特点：时间步离散（如按天、小时划分），快照间可能存在节点/边的增减或特征变化。
• 连续时间动态图：边的发生时间为连续值（如瞬时交易记录），需特殊处理时间戳信息（本文暂不涉及）。

二、动态图的处理方法

针对DTDG，主要通过以下三类方法将静态GNN扩展到动态场景：

1. 动态图→静态图转换（快照聚合）

• 核心思想：将多时间步的图快照聚合为单张静态图，再应用静态GNN（如GCN、GAT）。
• 具体操作：
  • 邻接矩阵聚合：对各时间步的邻接矩阵加权求和：
    $$A_{agg}=\sum _{t=1}^M\varphi (t,M)A_t$$
    其中 $\varphi (t,M)$ 为时间权重（如近期快照权重更高）。
  • 节点特征聚合：若节点特征随时间变化，对 $X_t$ 进行类似加权得到 $X_{agg}$。
  • 节点集扩展：若快照间节点不一致，将所有快照的节点合并为 $V_{all}$，空缺节点的特征和边用0填充。
• 优势：简单直观，可直接复用静态GNN的成熟模型。
• 局限：丢失时序信息（如节点关系的动态变化趋势），仅适用于时间依赖性弱的场景。

2. GNN与序列模型结合（时空融合）

• 核心思想：先用GNN提取每个快照的空间特征，再用序列模型（如RNN、LSTM）捕捉时间演化。
• 两步框架：
  1. 空间特征提取：对每个快照 $G_t$ 应用静态GNN（如GCN），得到节点嵌入序列 $[Z_1,Z_2,...,Z_M]$，其中 $Z_t=GNN(G_t)$。
  2. 时间依赖建模：将嵌入序列输入RNN/LSTM/Transformer，输出最终的时空嵌入。例如：
     • GCN-LSTM：GCN提取空间特征，LSTM处理时序依赖；
     • GAT-GRU：用GAT的注意力机制优化空间特征，GRU替代LSTM减少计算量。
• 优势：同时捕捉空间局部性和时间连续性，适用于节点集固定的动态图（如交通网络）。
• 局限：对节点增减的动态图适应性弱，需额外处理新节点嵌入的初始化。

3. 时空图神经网络（Spatio-Temporal GNNs, ST-GNNs）

• 核心思想：专为时空依赖设计的端到端模型，统一建模空间邻居关系和时间序列模式。
• 典型应用：交通流量预测、人类活动识别（节点为空间位置，边为位置间的关联，特征随时间变化）。
• 关键模型：
  • ST-GCN：在GCN层中引入时间卷积（如1D-CNN），同时聚合空间邻居和时间窗口内的特征。
  • ASTGCN：结合注意力机制，对不同时间步和空间邻居分配动态权重，提升对关键时空信息的捕捉能力。

三、动态图GNN的挑战与优化

1. 节点动态性：新节点（未出现在历史快照中）的嵌入初始化困难，通常采用零向量或基于特征的映射（如用MLP初始化）。
2. 计算效率：快照序列可能长达数百步，需通过时间采样（如仅用最近K步）或轻量化模型（如LightGCN变体）降低复杂度。
3. 长期依赖：传统RNN易受梯度消失影响，可改用Transformer的自注意力机制（如时空Transformer）捕捉长程时间依赖。

四、应用场景

• 交通预测：基于道路网络快照预测未来车流量（如ASTGCN在PeMS数据集上的应用）。
• 动态社交网络：预测用户间潜在的新连接（结合历史互动记录）。
• 欺诈检测：通过账户交易图的动态变化识别异常行为。

方法对比表

处理方法	核心思路	代表模型	优势	局限
快照聚合	多时间步→静态图，复用静态GNN	聚合GCN	简单高效，适合时间依赖弱的场景	丢失时序信息
GNN+序列模型	GNN提空间特征，RNN/LSTM捕时间依赖	GCN-LSTM、GAT-GRU	平衡时空建模，适合节点固定场景	新节点处理困难
时空GNN	端到端统一建模时空依赖	ST-GCN、ASTGCN	专为时空数据设计，精度高	复杂度高，调参困难

动态图上的GNN通过融合空间结构与时间演化，突破了静态GNN的局限性。未来方向包括提升对节点动态性的适应性、优化长时序依赖建模，以及拓展至连续时间动态图场景，进一步推动在实时决策领域的应用（如智能交通调度、应急响应）。

分类框架总结

类别	核心机制	代表模型	典型应用场景
递归图神经网络	节点与邻居迭代交换信息至稳态	GNN、GGNNs	图序列预测、节点状态跟踪
卷积图神经网络	聚合局部邻居特征（谱域/空间域）	GCN、GAT、GraphSAGE	节点分类、链路预测、图分类
图自编码器	编码-解码重构图结构/特征	GAE、VGAE、LINE	无监督嵌入、链路预测
图的深度生成模型	学习分布并生成新图	GraphRNN、NetGAN、GraphVAE	分子生成、社交网络模拟
动态图上的GNN	融合时空信息	GCN-LSTM、ST-GNNs	交通预测、动态社交网络分析

该分类法覆盖了GNN的核心架构，尤其将图的深度生成模型作为独立类别，凸显了其在生成任务中的重要性，为研究者提供了清晰的框架参考。