关键词:
图相似度学习
图表示学习
图神经网络
Graph Transformer
摘要:
图相似度计算是指比较两个或多个图结构之间的相似程度的过程.在社交网络分析、生物信息学、推荐系统等应用中,图相似度计算是理解和处理复杂数据结构的关键步骤,有助于帮助识别相似的图形式,从而进行数据挖掘、模式识别、信息检索等任务.近年来,图神经网络作为一种基于图结构的深度学习方法,为传统相似性度量方法提供了全新的思路和解决方案.
根据处理图结构和节点特征方式的不同,利用图神经网络解决图相似度计算的方法,可归类为两类,分别是基于嵌入和基于匹配.前者将图中的节点或边嵌入到低维空间中,学习嵌入向量之间相似度,这种方法的局限性在于其没有关注更细粒度的差异信息,从而预测精度不高.而后者利用节点级交互或图级交互,寻找图之间的最佳匹配关系,但节点比较过程的时间复杂度是平方级,消耗大量时间.
为了避免代价高昂的节点级交互,本文利用欧拉恒等式,将图嵌入映射到复数向量空间,并将图之间的相似度定义为旋转,在复数空间中学习出一个泛化能力强,计算效率高的图相似度计算模型.其主要研究内容和创新点如下:
(1)提出基于Graph Transformer的图相似度学习方法.为了避免现有方法利用节点级交互来计算图对之间的图相似度时所带来的高成本计算问题,本文提出了基于Graph Transformer的图相似度学习方法.该方法首先设计多级联合图嵌入网络GTPool学习图嵌入,然后通过将图嵌入映射到复数空间,利用欧拉恒等式的旋转特性将两个图之间的相似度定义为旋转关系.实验结果表明基于Graph Transformer的图相似度计算模型能显著提高图相似度计算的性能.
(2)提出基于线性Graph Transformer的图相似度学习方法.在上述方法中,Graph Transformer允许节点关注图中的所有节点,导致了相对于图中节点数量的二次时间复杂度.对于图相似度计算,这显著的增加了推理时间.为此,本文通过核化的Softmax算子将Graph Transformer的时间复杂性降低到线性,在不增加额外计算负担的情况下,有效地提取节点间的潜在结构信息.实验表明,利用核化Softmax算子将Graph Transformer线性化,不仅可以节省算法运行时的内存开销,同时也能提高模型的精度.
(3)本文在AIDS、LINUX、IMDB三个公共数据集上进行了实验,并与基准算法Sim GNN、GMN、Graph Sim和MGMN进行了比较.实验结果显示,本文提出的两种图相似度学习方法在有效提高计算效率的同时,均保持了较高的准确率.具体而言,在AIDS数据集上的均方误差相较于MGMN分别降低0.233和0.294;在LINUX数据集上的均方误差相较于MGMN分别降低0.843和0.569;在IMDB数据集上的均方误差相较于MGMN分别降低0.084和0.218.此外,RGSim在所有数据集上的推理速度是基准算法的2至4倍;而ERGSim引入核化Softmax算子后,在所有数据集上的推理速度是基准算法的3至6倍.