GMN-Zoomer:通过分层解析、池化和匹配学习图相似性

《Neural Networks》:GMN-Zoomer: Learning Graph Similarity via Hierarchical Parsing, Pooling and Matching

【字体: 大 中 小 】 时间:2026年03月01日 来源:Neural Networks 6.3

编辑推荐:

  图相似性学习框架GMN-Zoomer通过结构熵理论进行层次化解析,构建多粒度图表示,并设计跨层次注意力融合机制,在AIDS700nef、LINUX、IMDBMulti三个基准数据集上较现有方法平均降低28.65%的均方误差。

  
陈克佳|陈玉生|王子月|刘林峰
南京邮电大学计算机科学学院,南京,210003,中国

摘要

图相似性学习旨在衡量学习范式内图对之间的相似性。它能够有效解决传统度量方法(如图编辑距离和最大公共子图)所面临的NP难问题。然而,现有的基于学习的方法往往无法探索图结构的层次性,而这对于捕捉不同结构粒度上的相似性至关重要。在本文中,我们提出了一个基于层次解析、池化和匹配的图相似性学习框架。首先,我们通过对每个输入图进行结构解析和层次池化来生成层次图。然后,将相同粒度级别的图进行匹配以获取跨图交互信息。最后,将所有粒度级别的匹配结果仔细融合成一个整体的图相似性得分。在三个基准数据集上的广泛实验表明,与最先进模型相比,我们提出的方法在均方误差上平均降低了28.65%。我们的方法在各种层次解析策略下的性能也表现出较强的鲁棒性。

引言

图相似性计算(GSC)是图研究中的一个关键领域,其应用范围包括图检索(Yan和Han,2002年)、恶意软件检测(Wang等人,2019年)和脑数据分析(Ma等人,2019年)等。它主要关注确定任意图对之间的结构相似性。图编辑距离(GED)(Bunke,1983年)和最大公共子图(MCS)(Bunke和Shearer,1998年)是两种常见的度量方法,但它们的计算都是NP难问题(Bunke,Shearer,1998年;Zeng,Tung,Wang,Feng,Zhou,2009年)。替代的近似方法主要依赖于剪枝-验证框架(Liang,Zhao,2017年;Zhao,Xiao,Lin,Liu,Zhang,2013年)和启发式方法(Bougleux,Brun,Carletti,Foggia,Gaüzère,Vento,2017年;Daller,Bougleux,Gaüzère,Brun,2018年;Fankhauser,Riesen,Bunke,2011年),但它们相对于图的大小仍然表现出多项式甚至亚指数级的复杂性。由于图神经网络(GNNs)(Defferrard,Bresson,Vandergheynst,2016年;Kipf,Welling,2017年;Veli?kovi?,Cucurull,Casanova,Romero,Liò,Bengio,2018年;Xu,Hu,Leskovec,Jegelka,2019年)能够捕捉图中的复杂结构,因此它们在GSC社区中得到了越来越多的应用。早期的方法如GCN-MEAN和GCN-MAX(Defferrard等人,2016年)直接将图映射到嵌入中进行比较。后续的工作则关注更细粒度的信息交互。根据用于匹配的结构类型,这些工作可以大致分为三类:1)节点级交互,例如SimGNN(Bai等人,2019年)、GraphSim(Bai等人,2020年)和GMN(Li等人,2019年);2)节点-图交互,例如HGMN(Ling等人,2020年)和CLSim(Zou等人,2025年);3)子图级交互,例如H2MN(Zhang等人,2021年)、CoSimGNN(Xu等人,2020年)。
尽管取得了成就,现有的图相似性学习方法仍受到其匹配策略的限制。它们通常在单一粒度级别上操作,并过度依赖诸如k跳邻域聚合或随机游走等机制捕获的局部结构信息。这种设计的一个关键后果是它们无法有效编码图中不同子结构之间的关系。如图1所示,苯乙醇中的羟基连接到乙基侧链,而在甲酚中,它直接连接到苯环。尽管这两种化合物具有相同的官能团,但它们的更高层次结构,即羟基与分子其余部分的连接方式不同,导致形成了不同的分子骨架。在以前的方法中,这种层次差异(即相同的官能团被整合到不同的更大分子骨架中)没有得到很好的识别。
为了解决这些挑战,我们提出了GMN-Zoomer,这是一个结合了层次结构解析和多粒度匹配的通用图相似性学习框架。具体来说,我们首先基于结构熵理论进行层次结构解析,然后提出一种多粒度匹配机制,从放大视角全面学习跨图结构交互。最后,使用自注意力机制自适应地融合所有粒度层次的匹配向量,以计算最终的图相似性得分。
我们的主要贡献如下:
  • 1)
    我们提出了一种新的图相似性学习框架,该框架引入了结构熵理论来解析图结构并从层次角度进行匹配。
  • 2)
    我们设计了一种层次图匹配方法,它在每个放大级别上进行跨图交互,然后通过自注意力融合匹配信息,从而适应不同的图结构。
  • 3)
    在三个基准数据集上的广泛实验证明了我们层次解析和匹配机制的有效性,该方法取得了最先进的结果。
  • 部分片段

    图相似性学习

    图神经网络(GNNs)在图表示学习方面展现了强大的能力(Zhang,Cheng,Yuan,Zhang,2024年;Zhang,Yuan,Cheng,Liu,Li,Zhang,2025年)。因此,它们被广泛用于学习范式中的图相似性计算。早期方法通过建立图级嵌入之间的交互来估计相似性(Defferrard等人,2016年),但它们缺乏更细粒度的结构交互。SimGNN(Bai等人,2019年)率先实现了这一目标

    初步知识

    为了便于参考,本文中使用的关键符号在表1中进行了总结。

    提出的方法

    在本节中,我们介绍了GMN-Zoomer,这是一个通过层次结构解析、池化和匹配来学习图相似性的框架。如图2所示,工作流程从左到右依次进行:1)层次结构解析首先将原始图作为输入生成聚类分配矩阵;2)层次编码和池化然后使用这些矩阵并行地对两个图进行粗化,生成多粒度嵌入;3)多粒度

    数据集

    我们在三个真实世界的图数据集上进行实验:AIDS700nef、LINUX和IMDBMulti。这些数据集代表了各种领域和特征。具体来说,AIDS700nef由带有标签的化学化合物图组成。LINUX数据集包含未标记的程序依赖图,其中节点代表语句,边代表依赖关系。IMDBMulti由未标记的自我网络组成,表示电影演员之间的共同出现关系。

    结论

    在本文中,我们研究了GED问题上的图相似性学习。我们提出了一种新的图相似性学习框架GMN-Zoomer,它结合了层次结构解析和多粒度匹配。在GMN-Zoomer中,我们首先使用结构熵理论构建灵活的多粒度层次图结构。然后,通过匹配不同粒度级别的子图,我们进行了全面的图相似性计算。

    未引用的参考文献

    缺失的引用:Fischer等人(2015年);Shannon(1948年);Socher等人(2013年)

    CRediT作者贡献声明

    陈克佳:写作——审稿与编辑、资源获取。陈玉生:写作——原始草稿、验证、软件、方法论、形式分析、数据管理、概念化。王子月:写作——审稿与编辑、形式分析。刘林峰:验证、调查。

    利益冲突声明

    作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

    致谢

    本研究得到了国家自然科学基金(项目编号62476137和项目编号62576174)、南京大学国家关键实验室新型软件技术基金会(项目编号KFKT2022B01)以及南京邮电大学自然科学基金(项目编号NY221071)的支持。
    相关新闻
    生物通微信公众号
    微信
    新浪微博
    • 搜索
    • 国际
    • 国内
    • 人物
    • 产业
    • 热点
    • 科普

    热点排行

      今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号