计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (3): 181-187.doi: 10.11896/jsjkx.250300002

• 数据库 & 大数据 & 数据科学 • 上一篇    下一篇

类型引导边匹配的异质图相似度学习方法

桑士龙1, 陈可佳1,2,3,   

  1. 1 南京邮电大学计算机学院 南京 210023
    2 江苏省大数据安全与智能处理重点实验室(南京邮电大学) 南京 210023
    3 计算机软件新技术国家重点实验室(南京大学) 南京 210023
  • 收稿日期:2025-03-03 修回日期:2025-05-19 发布日期:2026-03-12
  • 通讯作者: 陈可佳(chenkj@njupt.edu.cn)
  • 作者简介:(1022040812@njupt.edu.cn)
  • 基金资助:
    国家自然科学基金(62476137);南京大学计算机软件新技术国家重点实验室开放课题(KFKT2022B01);南京邮电大学校级科研基金(NY221071)

Type-steered Edge Matching for Heterogeneous Graph Similarity Learning

SANG Shilong1, CHEN Kejia1,2,3   

  1. 1 School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
    2 Jiangsu Key Laboratory of Big Data Security & Intelligent Processing (Nanjing University of Posts and Telecommunications), Nanjing 210023, China
    3 State Key Laboratory for Novel Software Technology at Nanjing University, Nanjing 210023, China
  • Received:2025-03-03 Revised:2025-05-19 Online:2026-03-12
  • About author:SANG Shilong,born in 2000,postgra-duate,is a member of CCF(No.Z4415G).His main research interests include graph similarity learning and graph representation learning.
    CHEN Kejia,born in 1980,Ph.D,associate professor,is a member of CCF(No.14589M).Her main research interests include graph learning and complex network analysis.
  • Supported by:
    National Natural Science Foundation of China(62476137),Foundation of State Key Laboratory for Novel Soft-ware Technology at Nanjing University(KFKT2022B01) and Research Foundation of Nanjing University of Posts and Telecommunications(NY221071).

PDF (PC)

113

摘要： 图相似度学习是通过学习图的结构特征来匹配图之间相似程度的方法。目前,基于图神经网络的图相似度学习方法仍局限于节点级或图级的匹配范式,忽视了边级表示及其对图结构匹配的贡献。此外,现实图中的边通常具有不同类型,代表节点间不同的语义关系,可用于引导跨图交互。因此,提出了一种类型引导边匹配的异质图相似度学习方法(TEM-HGSL),首先设计基于线图的异质图同构网络以更好地学习边的嵌入,然后通过类型对齐的边匹配机制以更好地利用边的语义信息,最终实现边-图双层级的图相似度计算。在4个异质图据集上的实验结果表明,TEM-HGSL方法计算的均方误差比最优基线平均降低了25.65%,能有效实现细粒度相似度计算。

关键词: 图相似度学习, 异质图, 线图, 类型引导边匹配, 图结构匹配

Abstract: Graph similarity learning aims to measure the similarity between graphs by learning their structures.Graph similarity learning methods based on graph neural networks are still limited to the node-graph level matching paradigms,failing to perceive the edge-level representation and its contribution to graph structure matching.Moreover,edges in real-world graphs usually have different types,representing different semantic relationships between nodes,which are remain underutilized in cross-graph interaction methods.To address this problem,a type-steered edge matching for heterogeneous graph similarity learning(TEM-HGSL) framework is proposed.Firstly,a heterogeneous graph isomorphism network based on the line graph is designed to better learn edge embeddings.Then,a type-aligned edge matching mechanism is introduced to make better use of the semantic information of edges.Finally,the graph similarity calculation at both the edge and graph levels is realized.Experiments results on four heterogeneous graph datasets show that TEM-HGSL can reduce the mean square error in average of 25.65% compared with the best baseline,effectively achieving fine-grained similarity calculation.

Key words: Graph similarity learning, Heterogeneous graph, Line graph, Type-steered edge matching, Graph structure matching

中图分类号: 

  • TP391
[1]HOU L,LIU J H,YU X,et al.Review of Graph Neural Net-works[J].Computer Science,2024,51(6):282-298.
[2]COUPRY D E,POGANY P.Application of Deep Metric Lear-ning to Molecular Graph Similarity[J].Journal of Cheminforma-tics,2022,14(1):11.
[3]WU Y,LIU X,FENG Y,et al.Neighborhood Matching Net-work for Entity Alignment[C]//Proceedings of the Annual Meeting of the Association for Computational Linguistics.2020:6477-6487.
[4]BUNKE H.On a Relation between Graph Edit Distance andMaximum Common Subgraph[J].Pattern Recognition Letters,1997,18(8):689-694.
[5]BLUMENTHAL D B,GAMPER J.On the Exact Computation of the Graph Edit Distance[J].Pattern Recognition Letters,2020,134:46-57.
[6]KIPF T N,WELLING M.Semi-supervised Classification withGraph Convolutional Networks[C]//Proceedings of the International Conference on Learning Representations.2017.
[7]XU K,HU W,LESKOVEC J,et al.How Powerful are Graph Neural Networks?[C]//Proceedings of the International Conference on Learning Representations.2018.
[8]VELICKOVIC P,CUCURULL G,CASANOVA A,et al.Graph Attention Networks[C]//Proceedings of the International Conference on Learning Representations.2018.
[9]张辉宜,夏媛龙,周克武,等.一种融合标签间强相关性的多标签图像分类方法[J].重庆工商大学学报(自然科学版),2023,40(5):8-15.
[10]LI Y,GU C,DULLIEN T,et al.Graph Matching Networks for Learning the Similarity of Graph Structured Objects[C]//Proceedings of the International Conference on Machine Learning.2019:3835-3845.
[11]TAN W,GAO X,LI Y,et al.Exploring Attention Mechanism for Graph Similarity Learning[J].Knowledge-Based Systems,2023,276:110739.
[12]BAI Y,DING H,GU K,et al.Learning-based Efficient Graph Similarity Computation via Multi-scale Convolutional Set Ma-tching[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2020:3219-3226.
[13]WADAYAMA T,NAKAI-KASAI A.Mean Squared ErrorAnalysis of Noisy Average Consensus[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2025,108(3):435-441.
[14]BAI Y,DING H,BIAN S,et al.SimGNN:A Neural NetworkApproach to Fast Graph Similarity Computation[C]//Procee-dings of the ACM International Conference on Web Search & Data Mining.2019:384-392.
[15]BAI J,ZHAO P.TaGSim:Type-aware Graph Similarity Lear-ning and Computation[J].VLDB Endowment,2021,15(2):335-347.
[16]LING X,WU L,WANG S,et al.Multilevel Graph MatchingNetworks for Deep Graph Similarity Learning[J].IEEE Transactions on Neural Networks and Learning Systems,2021,34(2):799-813.
[17]ZHUO W,TAN G.Efficient Graph Similarity Computation with Alignment Regularization[J].Advances in Neural Information Processing Systems,2022,35:30181-30193.
[18]ZHENG H,SHI J,YANG R.GraSP:Simple yet Effective Graph Similarity Predictions[C]//Proceedings of the AAAI Confe-rence on Artificial Intelligence.2025.
[19]SHI C,WANG R J,WANG X.Survey on Heterogeneous Information Networks Analysis and Applications[J].Journal of Software,2022,33(2):598-621.
[20]WANG X,JI H,SHI C,et al.Heterogeneous graph attention network[C]//Proceedings of the World Wide Web Conference.2019:2022-2032.
[21]YANG Y X,CHEN H M,ZHOU L H,et al.Heterogeneous Graph Attention Network Based on Data Augmentation[J].Computer Science,2025,52(3):180-187.
[22]LYU Q,DING M,LIU Q,et al.Are We Really Making Much Progress? Revisiting,Benchmarking and Refining Heterogeneous Graph Neural Networks[C]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery & Data Mining.2021:1150-1160.
[23]ZHAO M X,JIA A L.DAHGN:Degree-Aware Heterogeneous Graph Neural Network[J].Knowledge-Based Systems,2024,285:111355.
[24]SCHLICHTKRULL M,KIPF T N,BLOEM P,et al.Modeling Relational Data with Graph Convolutional Networks[C]//The Semantic Web:International Conference.2018:593-607.
[25]CORSO G,CAVALLERI L,BEAINI D,et al.Principal Neighbourhood Aggregation for Graph Nets[J].Advances in Neural Information Processing Systems,2020,33:13260-13271.
[26]YANG Y,LI D.Nenn:Incorporate Node and Edge Features in Graph Neural Networks[C]//Proceedings of the Asian Confe-rence on Machine Learning.2020:593-608.
[27]JIANG X,JI P,LI S.CensNet:Convolution with Edge-NodeSwitching in Graph Neural Networks[C]//Proceedings of the International Joint Conference on Artificial Intelligence.2019:2656-2662.
[28]CHEN X Y,LI S Z,LIU R M,et al.Molecular Graph Contrastive Learning with Line Graph[J].Pattern Recognition,2025,162:111380.
[29]THANH T H T,LE B.Unified Node,Edge and Motif Learning Networks for Graphs[J].Engineering Applications of Artificial Intelligence,2024,138:109354.
[30]SPEARMAN C.The Proof and Measurement of Association between Two Things[J].The American Journal of Psychology,1987,100(3/4):441-471.
[31]KENDALL M G.A New Measure of Rank Correlation[J].Biometrika,1938,30(1/2):81-93.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发