《Expert Systems with Applications》:Exploiting Bidirectional Mamba Interaction for Graph Similarity Learning
编辑推荐:
宋高|陶璐|崔金明|王晓轩|苗胜法|艾哈迈德·扎希尔|亚当·哈立德|姚少文中国云南大学网络空间工程研究中心与软件与人工智能学院,昆明,650504摘要图相似性学习在图数据分析中起着至关重要的作用,特别是在社交网络分析、推荐系统和生物信息学等领域。当前的方法主要依赖于深度学习技术(
宋高|陶璐|崔金明|王晓轩|苗胜法|艾哈迈德·扎希尔|亚当·哈立德|姚少文
中国云南大学网络空间工程研究中心与软件与人工智能学院,昆明,650504
摘要
图相似性学习在图数据分析中起着至关重要的作用,特别是在社交网络分析、推荐系统和生物信息学等领域。当前的方法主要依赖于深度学习技术(如图神经网络GNN)来进行图相似性学习,并取得了优异的性能。然而,现有方法在处理图对时往往忽略了局部相似性比较,仅使用GNN通常无法完全捕捉图内的局部信息。在本文中,我们提出了一种名为Mamba图相似性(MGS)的新方法用于图相似性学习。我们的方法首先将自注意力机制和Mamba模块与GNN结合,以充分提取图中的潜在信息。然后,我们采用双向Mamba来增强图对之间节点的交互,进一步提高图相似性的准确性。在LINUX、AIDS和IMDBMulti上的广泛实验表明,我们提出的方法在图相似性任务中表现优于现有的基于深度学习的方法。
引言
图相似性度量衡量了两个图之间的相似程度或差异,提供了一个反映它们相似性的数值。它们在多个领域有广泛的应用,例如化合物分析(Guo等人,2018年);社交网络分析(Wang等人,2019年)和推荐系统(Fan等人,2019年)。传统的图相似性学习方法,如图编辑距离(GED)和最大公共子图(MCS)(Bunke & Shearer,1998年),通常需要找到将一个图转换为另一个图所需的最小成本编辑操作序列,或识别两个图共有的最大公共子图。这些过程计算成本较高,使得传统方法难以适用于大规模图比较任务。
当前的图相似性计算方法主要基于深度学习,通常将任务分解为两个阶段:图嵌入学习和相似性估计。在图嵌入学习阶段,常用图神经网络(GNN)(Ktena等人,2017年;Scarselli, Gori, Tsoi, Hagenbuchner, & Monfardini,2009年)将整个图编码为固定维度的向量。然而,GNN存在一个众所周知的局限性,即特征过度平滑:随着消息传递层的加深,节点表示变得难以区分,导致关键的局部结构细节(如小子图或独特模式)被稀释或完全丢失。这损害了学习到的嵌入的真实性,特别是在细粒度拓扑结构重要的任务中。在相似性估计阶段,许多方法(Jin等人,2022年;Ling等人,2021年;Tan等人,2023年)通过全局图嵌入(例如使用余弦相似度或MLP)来估计相似性(Ling, Wu, Wu, & Ji,2022年;Zhang等人,2021年)。虽然计算效率高,但这种仅基于全局的交互忽略了节点级别的跨图对应关系,无法捕捉一个图中的局部结构与另一个图中的局部结构的对应关系。这在生物信息学或社交网络对齐等领域尤为成问题,因为在这些领域,相似性往往由局部模式而非全局图特征决定。
为应对上述挑战,我们提出了Mamba图相似性学习(MGS),这是一种新颖的图相似性学习方法,将Mamba模块(Gu & Dao,2024年)集成到图特征提取和相似性比较过程中。尽管注意力机制在模拟长距离依赖关系和突出显著节点方面表现出色,但它们缺乏模拟图内节点之间结构化序列上下文的明确能力。相比之下,Mamba模块可以通过沿图结构序列自适应聚合信息,有效捕捉局部上下文信息和节点之间的长距离结构依赖关系。通过将Mamba与GNN结合在双流架构中,MGS能够同时保留全局语义并增强局部表达能力。此外,我们引入了一个基于双向Mamba的交互模块,允许一个图中的每个节点与另一个图中的所有节点动态交互,从而实现精确的局部到局部匹配。我们提出的方法不仅标记了重要节点,还有效捕捉了相邻节点之间的复杂关系,从而提供了更丰富、更细致的图结构表示。这些改进使我们的方法在图相似性学习任务中表现出色,为现有方法面临的挑战提供了稳健的解决方案。
总体而言,本研究的主要贡献如下:
- 1.
我们提出了一种新的双流网络,将注意力机制和Mamba模块与GNN集成在一起。这种集成增强了我们的双流网络捕捉全局和局部图特征的能力,加强了其在图嵌入中的表示能力。
- 2.
我们提出了一种以节点为中心的图相似性学习方法,该方法利用双向图Mamba的节点交互模式来学习有效的节点级表示。对于具有复杂结构的图,我们的方法可以在全局级别和子结构级别反映不同图之间的相似性。
- 3.
我们进行了一系列实验,包括参数敏感性实验、案例研究、多方法比较实验和消融实验。实验结果证明了我们的方法在不同数据集上的优越性,在关键指标上优于现有的图相似性学习方法。
本文的其余部分组织如下。第2节详细介绍了图相似性学习,并总结了以往的相关方法。第3节详细描述了我们提出的方法。第4节展示了实验结果和分析。第5节总结了这项工作,并对我们的未来研究提出了一些建议。
章节片段
相关工作
图相似性学习方法大致可以分为传统方法和基于深度学习的方法。接下来,我们简要介绍图相似性学习、传统方法和基于深度学习的方法。
Mamba图相似性学习
在本节中,我们详细介绍了我们提出的Mamba图相似性学习(MGS)。如图2所示,我们的方法由三个主要部分组成:图嵌入模块、图交互模块和对齐与预测模块。
实验
在本节中,我们通过基线比较实验、参数敏感性实验、案例研究和消融研究全面评估了我们的方法。
结论
在本文中,我们提出了一种基于Mamba的图相似性学习方法,该方法强调学习有效的节点级表示,并模拟节点对之间的交互。所提出的方法采用双流架构,每个输入图都通过一个流进行编码,该流将自注意力模块和Mamba模块集成到GNN中。这种设计使得每个图都能进行深度的、结构感知的表示学习,同时保留各自的特征。随后,这两个流
CRediT作者贡献声明
宋高:概念化、方法论、写作——初稿、审稿与编辑 陶璐:写作——初稿、可视化、数据管理 崔金明:调查、数据管理 王晓轩:方法论、可视化、验证 苗胜法:调查、验证 艾哈迈德·扎希尔:监督、验证 亚当·哈立德:监督、验证 姚少文:资金筹集
利益冲突声明
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。