论文信息

1 介绍

  本文主要总结图数据增强,并对该领域的代表性方法做出归类分析。

  DGL 存在的两个问题:

    • 次优图问题:图中包含不确定、冗余、错误和缺失的节点特征或图结构边。
    • 有限标签问题:标签数据成本高,目前大部分 DGL 方法是基于监督和半监督,扩展性不足。

  图数据增强可以分为:

   论文解读(GraphDA)《Data Augmentation for Deep Graph Learning: A Survey》-LMLPHP

1 Techniques of Graph Data Augmentation

  定义:$\mathcal{G}=(\mathbf{A}, \mathbf{X})$, $\mathbf{A} \in\{0,1\}^{n \times n}$, $\mathbf{X} \in \mathbb{R}^{n \times d}$, $\mathbf{y} \in \mathbb{R}^{n}$

  GraphDA 在于找到一个映射函数 $f_{\theta}: \mathcal{G} \rightarrow \tilde{\mathcal{G}}=(\tilde{\mathbf{A}}, \tilde{\mathbf{X}})$ 来丰富图信息。

  基于属性图的 GraphDA 可以分为:

    • feature-wise
    • structure-wise
    • label-wise

  根据优化目标可以分为:

    • task-independent:$\underset{\theta}{\text{min }} \mathcal{L}_{a u g}\left(\left\{\mathcal{G}_{i}\right\},\left\{f_{\theta}\left(\mathcal{G}_{i}\right)\right\}\right)$
    • task-dependent:$\underset{\theta, \phi}{\text{min }} \mathcal{L}_{\text {all }}\left(\left\{\mathcal{G}_{i}\right\},\left\{f_{\theta}\left(\mathcal{G}_{i}\right)\right\}, \phi\right)$

   $\mathcal{L}_{a u g}(\cdot, \cdot)$, $\mathcal{L}_{a l l}(\cdot, \cdot, \cdot)$ 分别代表只对数据增强任务进行优化和联合数据增强任务及下游任务进行优化。

1.1 Feature-wise Augmentation

  特征级增强策略

    • feature generation
    • feature perturbation
    • feature calibration/denoising

1.1.1 Feature Generation

  在所有的特征增强方法中,只有特征生成方法改变特征尺寸。

  与原始特征无关,例如,将拓扑信息编码成特征,例如节点索引。之后将生成的节点特征用于下游任务或者与原有节点进行级拼接生成新的特征 $\{\tilde{\mathbf{X}}, \mathbf{X}\} $。(task-independent)

  与原始特征有关(Mixup 或者 生成模型),例如,[1] 通过生成模型来增加节点特征,生成模型的输入是目标节点的局部邻域信息,并将生成器的优化归纳到公式中。(task-dependent)

1.1.2 Feature Perturbation

  两个主要的策略: feature shufflingfeature masking

    • feature shuffling :特征矩阵 $X$ 的第 $i$ 行表示第 $i$ 个节点的节点特征,因此对节点特征矩阵的行进行变换等价于得到一个具有相同拓扑但排列过的节点的备选图。由于只对节点特征进行打乱,保留拓扑结构,会导致上述两个分布之间的差异,在多视图学习中生成负样本。(task-independent )

    • feature masking :核心操作是将节点特征矩阵 $X$ 中的一部分元设置为 $0$,该思想广泛应用于对比学习。(task-independent )

  除上述工作外,还有对抗训练的方法来扰动节点特征,该领域属于图上的对抗攻击和对抗防御,可以参考 [2]。  

1.1.3 Feature Calibration/Denoising

  由于图数据不可避免的存在噪声数据及感知器精度的问题,给定的节点特征对于下游任务不是最优的。

  此时,出现考虑对节点特征进行较小的校准,在一定程度上存在优势,同时也保留了大部分初始节点属性。例如 [3] 计算特定目标函数的梯度和节点特征矩阵,并基于计算的梯度校准节点特征矩阵。

  噪声特征的一个特例是部分特征丢失,其对应的解决方案是特征推断 [4][5]。由于难以将拓扑信息融入推断模型种,所以在图结构上还没有好好的研究,相关的代表作有 GCNMF [6] 和特征传播 [7] 。前者用高斯混合模型表示缺失的数据;后者基于热扩散方程将特征从已知特征扩散到未知特征。

1.2 Structure-wise Augmentation

  分为四种方法:

    • edge addition/dropping

    • node addition/dropping

    • graph diffusion

    • graph sampling

1.2.1 Edge Addition/Dropping

  即 保留原始节点顺序,对邻接矩阵种的元进行改写。

  基于图稀疏性(graph sparsification)的图结构优化方法 [8、9],基于图结构整洁性(graph sanitation)的方法 [3],以及图采样(graph sampling)。

  Edge Addition/Dropping 不仅可以是任务无关的随机丢边,而且还可以通过将拓扑(例如,作为可学习分布)形成到下游目标中而依赖于任务

1.2.2 Node Addition/Dropping

  添加节点需要做:

    • 在给定的邻接矩阵 $A$ 中插入一行和一列;
    • 在给定的节点特征矩阵 $X$ 中插入一行;
    • 根据特定的下游任务设置节点标签向量 $y$;

  节点的更改关联图结构和节点标签往往更加复杂,一个典型的例子:通过在给定图中插入超节点来改善整个图的传播/连通性。超节点与图中的所有现有节点相连。它的特性是可以聚合所有现有节点的特性,也可以通过下游任务来学习。

  为缓解不平衡的标签分布,GraphSMOTE[11] 插入节点来丰富少数类。从给定的图中删除节点是图采样技术的一个重要组成部分。DGL任务删除节点的共同目标是生成扰动图样本[12;13;14],并提取信息子图 [15]。

1.2.3 Graph Diffusion

  图扩散作为一种结构增强策略,图扩散通过提供底层结构的全局视图来生成增广图。图扩散通过计算权重将节点与它们的间接连接的邻居节点连接,将全局拓扑信息注入到给定的图邻接中。图扩散可以表示为:

    $\mathbf{S}=\sum\limits _{k=0}^{\infty} \gamma_{k} \mathbf{T}^{k}\quad\quad\quad(2)$

  其中:
06-01 10:12