(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210630673.X (22)申请日 2022.06.06 (71)申请人 东北大学 地址 110819 辽宁省沈阳市和平区文化路 三号巷11号 (72)发明人 林健亚　曹鹏　温广琪　杨金柱　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 专利代理师 李在川 (51)Int.Cl. G06F 16/53(2019.01) G06N 3/04(2006.01) G06N 3/08(2006.01) G06V 10/74(2022.01) G06V 10/774(2022.01)G06V 10/82(2022.01) (54)发明名称 一种基于子图划分的图检索方法 (57)摘要 本发明提出一种基于子图划分的图检索方 法， 涉及图相似性计算领域； 利用图卷积神经网 络提取节 点特征时， 考虑了节 点的一阶邻接性和 二阶邻接性； 构建图对间交互模块， 通过交叉图 注意力机制计算节点注意力系数， 实现两图间的 相互交互； 子图划分不仅考虑图的节点特征， 还 引入图的结构信息； 构建图对间的相似矩阵， 将 相似性计算转换成模式识别问题， 利用多尺度特 征获取更多图相似性的特征信息； 利用图的多层 结构信息， 充分考虑了图对之间的不同粒度大小 的信息交互， 最终有效的提高了图检索的准确 性。 权利要求书3页 说明书8页 附图2页 CN 115080776 A 2022.09.20 CN 115080776 A 1.一种基于 子图划分的图检索方法， 其特 征在于， 具体包括以下步骤： 步骤1： 将节点和边组成的图数据作为训练数据集， 对训练数据集进行预处理， 统计训 练数据集中的数据特征， 将训练数据集中的图进行一对一匹配， 构造训练图对数据集用于 后续模型的训练； 步骤2： 构建基于GNN的节点卷积网络， 对步骤1中训练图对中的节点特征进行训练， 根 据充分利用不同距离信息的思想， 拼接聚合节点不同距离大小的领域信息， 生成新的节点 的特征； 步骤3： 构建图对间交互模块， 将步骤2得到的节点特征通过交叉图注意力机制计算节 点注意力系数， 实现图对之间的相互 交互， 生成包 含交互信息的新的节点特 征； 步骤4： 构建子图划分模块， 根据步骤3得到的节点特征以及图的结构信息， 通过端到端 的方式为节点学习分配矩阵， 以适应不同的图神经网络体系 结构的层次结构， 划分相 应的 子图； 步骤5： 构建子图卷积网络， 根据步骤4划分得到的子图， 对子图内的节点进行卷积计算 强化子图内节点的关联性， 进一 步得到包 含着子图信息的节点特 征； 步骤6： 利用步骤5得到的节点特征构建图对之间的相似矩阵， 搭建基于卷积神经网络 即CNN的深度学习网络， 将相似性计算转换成模式识别问题， 利用多尺度特征获取更多图相 似性的特 征信息； 步骤7： 通过注意力读出函数， 将步骤3和步骤5得到的节点特 征分别计算 生成图表示； 步骤8： 将步骤7计算得到图表示， 与步骤6中CNN部分的输出结果一起进行相似性得分 计算， 得到图对的相似性得分； 步骤9： 根据步骤8得到的相似性得分， 查询图数据库中与给定图相似的结果。 2.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤1具体为： 训练图对的基本单元是(G1， G2， y)， 图G＝(V， E)， 其中 V是图的节点集， E是图 的边集， V的节点数为N＝|V|； 节点初始特征X＝{x1,x2,x3,…,xN}， 如果训练数据中未包含 节点的初始特征， 则根据one ‑hot编码生成节点的初始特征； 对节点 的度dv进行one ‑ hot编码， 并将其拼接到节点的初始特征上， 作为后续训练所用的节点特征， 生成可以用于 训练的图对数据集。 3.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤2具体为： 节点卷积网络采用改进的图同构网络即 GIN对节点特 征进行训练， 其计算公式如下： 其中， MLP(k)是多层感知机， k表示第k层网络， 表示第k层的节点v的特征， ∈是一个 可学习的参数， 表示节点v的邻域节点 集合 中的一个节点u； 由边集E构造图的一阶邻接矩阵A1， 从而计算出图的二阶邻接矩阵A2， 其计算公式如下： T＝A1·A1 拼接通过A1训练得到的节点特征和通过A2训练得到的节点特征， 将节点的一阶邻接性权　利　要　求　书 1/3 页 2 CN 115080776 A 2和二阶邻接性结合 起来， 扩展卷积网络的感受域以提取 更多的节点特 征。 4.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤3具体为： 图对G1和G2间的交互， 对于G1中的每一个节点， 计算其与G2中所有节点的余弦相似性 评分， 其计算公式如下： 其中， 是G1中节点 i特征， 是G2中节点j特 征， N2是G2的节点数； 然后利用上述的相似性评分计算图G2对图G1中节点 i的影响， 其计算公式如下： 其中， [αi,j]+＝max( αi,j， 0)， 是图G1中节点 i经过与图G2的交 互后生成的节点特 征； 将图G1和图G2进行互换， 得到图G1对图G2的影响， 通过一个多视角匹配余弦匹配函数 来计算输出的节点特 征， 其计算公式如下： 其中， Xin是交互部分输入的节点特征矩阵， 是图对之间相互 交互后的节点特征矩阵， W 是学习的参数矩阵。 5.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤4具体为： 通过使用单独的图卷积网络即GCN来生成图节点分配矩阵S， 利用节点的特征矩阵X和 图的一阶邻接矩阵A1将节点划分到相应的子图中， 其计算公式如下： S＝softmax(GCN(A1,X)) 其中， softmax按行进行计算的； 分配矩阵S的输出维度为数据集中图的最大节点数 Nmax， 然后对分配矩阵S进 行进一步的池化操作， 根据每行计算得到节 点归属对应子图的隶 属度， 只保留隶属度较大的子图分配， 一个节点可以被多个子图拥有， 该部 分参数是模型预 定义的超参数。 6.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤5具体为： 使用超图神经网络即HGNN对划分好的子图进行卷积计算， 将一个子图作为一个超边进 行计算， 其计算公式如下： 其中， σ()是非线性激活函 数， Dv是超图中节点度的对角矩阵， De是超图中超边度的对角 矩阵， W是超图中的超边权重矩阵， Θ是可训练参数矩阵； 将同一子图中的节点看作位于同 一超边之上， 超图中节点度等价于节点出现在不同超边中的次数， 超图中超边度是指超边 中包含的节点数。 7.根据权利要求1所述的一种基于 子图划分的图检索方法， 其特 征在于， 步骤6具体为： 将图对节点的特征矩阵分别扩展到Nmax*128， 扩展的部分用0进行填充， 然后图G1的节 点特征矩阵乘以图G2的节点特征矩阵， 计算图对之间所有节点特征之间的内积， 其结果作 为图对的相似矩阵， 将其作为CN N部分的输入；权　利　要　求　书 2/3 页 3 CN 115080776 A 3