1. 图分类的应用价值

图分类，或称网络分类，主要根据图的拓扑结构来预测其标签信息，是图数据挖掘领域中一个重要的学习任务。不同于节点分类、链路预测等利用图的局部结构进行推理，图分类需要关注图数据的全局信息来建模图到标签的映射。该任务常用于生物、化学、社交等领域，典型的应用有药物分类、毒性检测、蛋白质分析、社交模式识别等。例如，在生物化学领域中，化合物可以看成一个带标签的分子图，图中的节点代表原子，边代表原子之间的化学键，图分类的目的在于根据分子结构特征去确定化合物的性质，例如是否具有致癌性、是否具有某种催化效果等。

2. 探索图上的数据增强

图数据挖掘算法如图分类等，极度依赖于大量的标签数据来训练模型。而生物、化学领域中，一些用于图分类的标准数据集，如MUTAG、KKI等，存在数据量过少的问题。即使图分类算法不断地被优化创新，数据集规模的限制依旧会给模型带来过拟合、泛化能力低等问题。

数据增强（data augmentation）是一种通过让有限的数据产生更多的等价数据来人工扩展训练数据集的技术，是解决模型过拟合的有效途径。在计算机视觉领域，常用的数据增强技术主要有几何变换、颜色调整、风格迁移、加噪声等。例如，通过对一张猫的图片经过简单的数据增强（如旋转、放缩、锐化），可以生成大量等价的图片。然而，对于图结构数据而言，由于其不规则、非欧的结构以及强烈的语义拓扑依赖性，我们无法直接将图像领域的数据增强技术直接应用于图数据。

鉴于此，来自浙江工业大学·网络空间安全研究院的宣琦教授团队对此问题进行了研究——探索图结构数据上的数据增强。这项研究工作的结果于2020年发表在IEEE Transactions on Network Science and Engineering (IEEE TNSE) 期刊。

这项工作中，主要研究的对象是图分类任务。对该任务，作者提出了针对图的若干启发式的数据增强技术，包括随机映射、节点相似度映射、模体随机映射以及模体-相似度映射。其中随机映射通过对原始图进行一定比例的随机重连生成新的图；节点相似度映射删除相似度较低的节点对之间的连边，增加相似度较高的节点对之间的连边；模体-随机映射通过对网络中的特定模体进行边交换来丰富网络结构，如图3所示；模体-相似度映射在模体随机映射的基础上，将节点相似度作为采样权重，如图4所示。

图3：模体中的边交换示意图

图4：模体-相似度映射示意图

通过提出的启发式数据增强方法，我们可以生成大量的弱标注样本，扩充图数据集的规模。然而，考虑到数据增强会引入一定的噪声，生成得到的弱标注样本是否可以直接用于训练依旧值得思考。在计算机视觉中，数据增强对图像的语义信息几乎不会造成破坏，然而对于图结构数据，由于其性质极度依赖于拓扑结构，通过修改图结构生成的样本可能会丢失原本的语义信息，原本的标签不一定适用于新生成的样本。鉴于此，作者引入了“标签可信度”的概念，用于衡量样本和其标签的匹配程度，达到数据筛选的目的。

最后，作者提出了一个模型演化框架M-Evolve，该框架结合了数据增强、数据筛选、模型迭代重训练三个部分，如图5所示，可以有效地逐步优化图分类器，缓解过拟合，提高泛化能力。

3. 模型演化框架对图模型的优化效果

作者在6个小规模标准数据集、5种图分类模型上进行了实验，得出了如下结论：1）四种图数据增强方法结合“标签可信度”指导数据筛选均可以有效增强图分类模型，增强效果视数据集而定，从2.78%-13.36%不等；2) M-Evolve中的数据筛选机制非常重要，可以稳定增强后的模型性能；3) 该框架可以有效地提升数据规模、丰富数据分布、优化分类器的决策边界（模型在优化前后训练数据分布以及决策边界的比较见图6、7所示）；4) 该框架可以有效地缓解模型在小数据集上训练时产生的过拟合问题，提升模型的泛化能力。

图6：模型演化前后训练数据分布可视化

图7：模型演化前后模型决策边界可视化

4. 新方向：图上的数据增强

相比于计算机视觉和自然语言处理，图挖掘领域中对数据增强的相关研究仍处于起步阶段。本文的工作较早地探索了如何设计图上的数据增强方法，研究表明，简单的启发式网络重连方法就可以作为有效的数据增强策略，对图模型的优化起到一定的帮助。笔者认为，这项工作为图数据挖掘及算法安全领域提供了新的研究思路。同时，结合自监督学习、图对抗学习等新兴的研究热点，相信图数据增强将会逐步体现出其在该领域重要的研究和应用价值。

集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：

点击“阅读原文”，追踪复杂科学顶刊论文