基于元结构匹配与有偏采样的图相似度计算方法

作     者：安丽霞 吴安彪 袁野 孙思琪 王国仁 AN Li-Xia;WU An-Biao;YUAN Ye;SUN Si-Qi;WANG Guo-Ren

作者机构：东北大学计算机科学与工程学院 北京理工大学计算机学院 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2023年第46卷第7期

页      面：1513-1531页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金(61932004 62225203 U21A20516)资助~~ 

主　　题：图相似度计算 图神经网络 图编辑距离 图嵌入 最大公共子图 

摘      要：作为图分类、图相似搜索等诸多图数据分析任务的核心步骤,图相似度计算一直是备受研究者们所重视的一个热点问题.由于传统图相似度计算方法的复杂性,无法适用于实时计算节点较多的图相似度任务,针对此问题研究者们提出了新型的基于图神经网络的图相似度计算方法.然而这些算法虽有效加快了图相似度的计算,但是仍然存在两方面的不足,从而影响了他们的性能:(1)多数现有工作通过节点级或图级嵌入的比较来衡量图之间的相似度,忽略了大图中丰富的局部结构特征;(2)所有现有工作均随机采样生成图对数据,导致样本包含的结构不均匀,训练所得模型只对部分特定结构敏感因而误差较大.为此,本文提出了一种新颖的基于元结构匹配与有偏采样的图相似度计算方法 MB-GSC(Meta-Structure Matching and Biased Sampling based Graph Similarity Computation).首先提出GSE(Graph Structure Extraction)算法提取图中元结构并构建图的结构分布向量,然后基于此向量提出有偏采样策略RSG(Representative Sample Generation)进行代表性样本的生成,用于后续模型训练.同时,提出算法MSA(Meta Structure Alignment)对提取到的元结构进行最优匹配对齐,从而获取公有结构形状差异与特有结构数量差异,进而构建蕴含有效的局部相似信息的子结构相似向量.最后,在模型中集成节点级成对比较相似向量、图级神经张量网络相似向量、子结构相似向量进行图对相似性计算.为验证算法的有效性,采用5个评估指标在4个真实数据集上与基准方法进行了大量对比实验,对模型性能进行全面评估.实验结果验证了本文所提算法MB-GSC能够更准确且高效地计算图之间的相似度,在GED预测、MCS预测任务上的准确度比现有模型分别提升11.16%、7.45%,且在保证相同准确率的同时使训练样本数平均减少54%.