摘要
图编辑距离(GED)是一种常用的图相似性度量函数,其精确计算为NP-hard问题。因此,近期研究者们提出诸多基于图神经网络的图相似度计算方法。现有方法在特征提取时忽略了两个图节点之间的跨图交互信息,并且缺乏对图中节点高阶关系的学习。针对以上问题,提出了一种基于跨图特征融合和结构感知注意力的图相似度计算模型(cross-graph feature fusion with structure-aware attention for graph similarity computation,CFSA)。首先,该模型提出了一种跨图节点特征学习方法,引入跨图注意力机制提取节点的跨图交互信息,并将节点的局部特征和跨图交互特征进行有效融合;其次,提出了一种结构感知型多头注意力机制,结合节点特征信息和图结构信息,有效捕捉节点间的高阶关系。在三个公共数据集上的实验结果表明,CFSA模型的预测准确率相较于现有模型分别提升4.8%、5.1%、15.8%,且在大多项性能指标上均有优势,证明了CFSA在GED预测任务上的有效性和效率。
GED is a commonly used graph similarity metric function whose exact computation is an NP-hard problem.Therefore,recently researchers have proposed numerous graph neural network-based graph similarity computation methods.The existing methods ignore the cross-graph interaction information between two graph nodes during feature extraction and lack the learning of higher-order relationships between nodes in the graph.To address the above problems,this paper proposed a model for graph similarity computation based on cross-graph feature fusion and structure-aware attention.Firstly,the model proposed a cross-graph node feature learning method,which introduced a cross-graph attention mechanism to extract the cross-graph interaction information of nodes,and effectively fused the local features of nodes and the cross-graph interaction features.Se-condly,the model proposed a structure-aware multi-attention mechanism,which combined the feature information of nodes with the graph structural information to efficiently capture the higher-order relationships among nodes.Experimental results on three public datasets show that the prediction accuracy of the CFSA model is improved by 4.8%,5.1%,and 15.8%,respectively,compared to the existing models,and has advantages in a large number of performance metrics,which proves the effectiveness and efficiency of CFSA for the GED prediction task.
作者
庞俊
闫炳鑫
林晓丽
王蒙湘
Pang Jun;Yan Bingxin;Lin Xiaoli;Wang Mengxiang(College of Computer Science&Technology,Wuhan University of Science&Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Intelligent Information Processing&Real-time Industrial System,Wuhan 430065,China;China Institute of Standardization,Beijing 100088,China)
出处
《计算机应用研究》
北大核心
2025年第8期2320-2328,共9页
Application Research of Computers
基金
国家自然科学基金资助项目(62372342,62372343)
湖北省自然科学基金资助项目(2024AFB865)
武汉科技大学“十四五”湖北省优势特色学科(群)项目(2023D0301)
中央级公益性科研院所基本科研业务费专项资金项目(602025Y-12515)。
关键词
图编辑距离
图相似度
图神经网络
图嵌入学习
graph edit distance(GED)
graph similarity
graph neural network(GNN)
graph embedding learning
