M-Evolve

M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification

1. motivation: 由于benchmark数据集规模的限制使得图分类任务容易陷入过拟合或泛化性不足，因此作者通过数据增强从原数据集中生成更多的具有弱标签的数据，从而减轻过拟合，提升图分类的准确率

2. 主要增强方法: 通过一定策略的增删边；对下面的过程不断循环迭代

   • 数据增强

     • random mapping：随机删除一定数量的边，同时在原本不相连的节点之间连接边，增删数量相同保持边数恒定

     • vertex-similarity mapping：相较于上一个随机增强方法，该方法基于Resource Allocation (RA) index计算得到的节点相似性得分来按权重进行边增加和删除

     • motif-random mapping：随机在 motif 中增加或者删减边

     motif：图中出现频繁且特定的子结构或子图。这些子结构通常被认为是图的基本模式，可以用来揭示图的结构和特征，例如文中提到的 open-triad，open-quad

     • motif-similarity mapping：相较于上一个随机增强方法，该方法同样基于 RA 来计算权重，之后搜索出候选的motif进行按权重的增删边

   • 数据过滤：得到增强的一组图后，输入到一个分类器中，得到分类结果计算其标签可靠性：示例 \((G_i,y_i)\) 的标签可靠性定义为示例概率分布 \(p_i\) 和类概率分布 \(q_{y_i}\) 的乘积 \(r_i = p_i^\top q_{y_i}\) 如果可靠性大于设定阈值则采纳该增强图，否则使用原图

3. 方法评价: 利用了节点相似性等权重参数指导筛选出好的增强图样本，而不是随机增强，有效的同时减小了模型的过拟合；但是该算法涉及 motif 的查找；在实际应用中，可以应用于药物分类、毒性检测、蛋白质分析