一种基于自适应结构感知池化图匹配的图相似度计算模型  

A graph similarity computation model based on adaptive structure aware pooling graph matching

作　　者：贾康 李晓楠 李冠宇[1] JIA Kang;LI Xiao-nan;LI Guan-yu(Information Science and Technology College,Dalian Maritime University,Dalian 116000,China)

机构地区：[1]大连海事大学信息科学技术学院,辽宁大连116000

出　　处：《计算机工程与科学》2023年第11期1999-2007,共9页Computer Engineering & Science

基　　金：国家自然科学基金(61976032,62002039)。

摘　　要：图相似度计算在许多有关图的任务中起着重要作用,例如图相似性搜索、图分类和图聚簇等。由于计算2个图之间的精确距离/相似度通常是NP-hard的,因此基于神经网络提出了自适应结构感知池化图匹配网络模型(ASAPMN),用端到端的方式来计算任意2个图结构之间的相似性。利用一种新颖的自我注意网络和一种改进的图神经网络来确定给定图中每个节点的重要性,通过学习对每一层的节点进行稀疏软集群分配,从而有效地池化子图,形成池化图。在池化后的图对上利用结点-图匹配网络有效地学习一个图的每个节点与另一整个图之间的跨层交互提取图间相似度。在4个公共数据集上的综合实验结果表明,ASAPMN在图-图分类和回归任务中优于最先进的基线模型。Graph similarity computation is one of the core operations in many graph related tasks such as graph similarity search,graph classification,graph clustering,etc.Since computing the exact distance/similarity between two graphs is typically NP-hard,based on the neural network,an Adaptive Structure Aware Pooling graph Matching Network(ASAPMM)model is proposed.ASAPMN calculates the similarity between any pair of graph structures in an end-to-end way.In particular,ASAPMN utilizes a novel self-attention network along with a modified GNN formulation to capture the importance of each node in a given graph.It also learns a sparse soft cluster assignment for nodes at each layer to effectively pool the subgraphs to form the pooled graph.On the pooled graph pairs,a node-graph match-ing network is used to effectively learn cross-level interactions between each node of one graph and the other whole graph.Comprehensive experiments on four public datasets empirically demonstrate that our proposed model can outperform state-of-the-art baselines with different gains for graph-graph classification and regression tasks.

关 键 词：图相似度计算 图池化 图匹配 注意力机制 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]