SubMix

Model-Agnostic Augmentation for Accurate Graph Classification

1. motivation: 目前的图数据增强工作存在两个问题：一是增强过程中涉及到目标模型；二是只利用简单的启发式方法，可能增强出不可靠的结果；因此作者设计了与模型无关的数据增强算法，以实现更加准确的图分类

2. 主要增强方法：子图混合，即替换部分子图

   • 作者首先提出了五个增强方法应该满足的属性

     • 保留尺寸：即增强后节点和边的数量不变

     • 保持连通性

     • 改变节点

     • 改变边

     • 线性复杂度 \(O(|d\cdot\mathcal{V} + \mathcal{E}|),d\) 是特征维数

3. SubMix：即替换部分子图，包含子图采样、子图混合，标签混合，特征替换等工作

   • 选定两个不一样的图，之后进行使用diffusion方法进行采样得到对应的相同节点数量的子图\(S, S^\prime\)，其中使用 PageRank计算得分，将亲和度（affinity）得分高的邻居节点纳入到采样子图当中，实现diffusion

   • 根据上一步计算的得分进行排序，之后按照顺序进行一对一映射

   • 边重连：根据以下公式得到两个边集，即 \(\mathcal{E}_{1}\) 和 \(\mathcal{E}_{2}\) 的区别在于，\(\mathcal{E}_{1}\) 包含与 \(S\)中至少一个节点相关的边，而 \(\mathcal{E}_{2}\) 只包含两个相连节点都在 \(S^\prime\) 中的边。原因是因为增强的主要目标是 \(G\)

     $$ \begin{array}{l} \mathcal{E}{1} \leftarrow{(u, v) \mid(u, v) \in \mathcal{E} \wedge \neg(u \in S \wedge v \in S)} \ \mathcal{E} \leftarrow\left{(\phi(u), \phi(v)) \mid(u, v) \in \mathcal{E}^{\prime} \wedge\left(u \in S^{\prime} \wedge v \in S^{\prime}\right)\right} \end{array} $$

     新的边集 \(\bar{\mathcal{E}} = \mathcal{E}_{1}\cup\mathcal{E}_{2}\)

   • 子图特征替换：即通过一对一映射直接替换对应点的特征

   • 标签混合：$\bar{y} = qy + (1-q)y^{\prime},q =|\mathcal{E}_1|/|\bar{\mathcal{E}}| $

4. 方法评价: 作者针对图分类问题提出了两种模型无关的数据增强算法，实现了更加准确的图分类