核心思想

  本文提出一种多级图匹配网络（MGMN）用于图相似性的度量。常见的图相似性网络都是利用图神经网络或其他图嵌入技术将整幅图转化为特征向量，然后计算两个特征向量之间的相似程度。这种做法的缺点在于只关注了图一级的信息交互，而忽略了细粒度更高的特征信息。而传统的图匹配网络更多关注的是节点一级的特征匹配，如何获取跨级别（节点-图）之间的信息交互并且充分利用多种级别的特征信息（跨级别、图级别、节点级别）进行图相似性度量是本文研究的重点。
  本文提出的NGMN包含两个部分：节点-图匹配网络（NGMN）和孪生图神经网络（SGNN），NGMN是为了获取跨级别的信息交互，SGNN是为了获取图级别的信息交互。

实现过程

  首先介绍NGMN部分，输入的两个图G1,G2G^1,G^2G1,G2分别经过两个共享权重的图卷积神经网络GCN用于特征提取，

其中Aˉl\bar{A}^lAˉl表示规范化处理后的拉普拉斯矩阵，XlX^lXl表示输入的节点特征矩阵，W(t)W^{(t)}W(t)表示GCN中可训练的权重矩阵，σ\sigmaσ表示激活函数，Hl,l∈{1,2}H^l,l\in\{1,2\}Hl,l∈{1,2}分别表示两幅图对应的节点特征。
  然后，计算节点-图之间的跨级别信息交互。图G1G^1G1中的节点viv_ivi​和图G2G^2G2中的节点vjv_jvj​之间的相似性αi,j\alpha_{i,j}αi,j​可以通过余弦相似性度量计算。反之，图G2G^2G2中的节点vjv_jvj​和图G1G^1G1中的节点viv_ivi​之间的相似性βj,i\beta_{j,i}βj,i​也可以通过余弦相似性度量计算，如下

以相似性αi,j\alpha_{i,j}αi,j​作为权重，进行加权求和可以得到图G1G^1G1中的节点viv_ivi​和图G2G^2G2之间的图级别嵌入向量，反之亦然

接下来，作者定义了一个多视角的匹配函数fmf_mfm​来计算两个向量之间的相似度

其中⊙\odot⊙表示逐元素相乘，wkw_kwk​表示可学习的权重向量，这个本质上就是一个带有可学习权重的余弦相似性度量函数。使用该度量函数计算每个节点特征向量hˉil\bar{h}_i^lhˉil​和图级别嵌入向量h~G,avgl,i\widetilde{h}^{l,i}_{G,avg}hG,avgl,i​之间的相似性，并将其作为节点-图交互特征h~il\widetilde{h}_i^lhil​

  得到节点-图交互特征h~il\widetilde{h}_i^lhil​后，利用聚合层将其融合为一个特征向量。本文选用了BiLSTM作为聚合层，

  最后，度量两个图之间的相似性，对于图-图分类认为相似性度量可以采用余弦相似度

如果是图-图回归任务，则可以将两个聚合特征向量拼接起来，再利用一个带有Sigmoid函数的MLP输出相似度

  SGNN部分于NGMN比较类似只是少了节点-图交互的部分。GCN得到的节点特征信息hˉl\bar{h}^lhˉl直接利用最大值池化层进行特征聚合，并采用与NGMN相同的方法计算聚合特征之间的相似性。最后将SGNN和NGMN输出的聚合特征hˉGl\bar{h}^l_GhˉGl​和h~Gl\widetilde{h}^l_GhGl​拼接起来，计算最终的多级相似性。

创新点

• 提出一种基于多级图匹配网络的图相似性度量算法
• 提出一种跨级别（节点-图）信息交互提取方法

算法评价

  本文提出的方法其实并不复杂，核心的部分在于节点-图的信息交互，这个非常类似于跨图注意力机制。此外使用BiLSTM进行信息聚合的方式也值得借鉴，一方面它可以解决图的节点数量不固定的问题，另一方面他比简单的最大值池化所包含的信息更多。

如果大家对于深度学习与计算机视觉领域感兴趣，希望获得更多的知识分享与最新的论文解读，欢迎关注我的个人公众号“深视”。