Skip to content

NodeSam

Model-Agnostic Augmentation for Accurate Graph Classification

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

  2. 主要增强方法：对节点进行拆分或者合并

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

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

      • 保持连通性

      • 改变节点

      • 改变边

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

  3. NodeSam: 对节点进行拆分和合并 nodesam

    • 拆分：随机选择一个节点，将其拆为两个，特征复制一份，然后之间用一条边相连

    • 调整：由于后续的合并操作会减少很多边，可能会破坏拓扑结构，因此随机选择拆分出来的两个节点的邻居（作者限定为形成三角形的邻居节点），之后增加边连接邻居与拆分点

    • 合并：随机合并两个节点为一个节点，所连边为原来两个节点的并，特征为原来两个节点的平均特征

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