基于邻居信息聚合的子图同构匹配算法

作者：徐周波; 李珍; 刘华东^*; 李萍

来源：计算机应用, 2021, 41(01): 43-47.

• 子图同构
• 约束满足问题
• 图卷积神经网络
• 信息聚合
• 图匹配

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题(CSP)模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。

• 单位
  桂林电子科技大学