Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (3): 181-187.doi: 10.11896/jsjkx.250300002

• Database & Big Data & Data Science • Previous Articles     Next Articles

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 Published: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)

112

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

CLC Number: 

  • 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.
[1] WANG Jinghong, WU Zhibing, WANG Xizhao, LI Haokang. Semantic-aware Heterogeneous Graph Attention Network Based on Multi-view RepresentationLearning [J]. Computer Science, 2025, 52(6): 167-178.
[2] YANG Yingxiu, CHEN Hongmei, ZHOU Lihua , XIAO Qing. Heterogeneous Graph Attention Network Based on Data Augmentation [J]. Computer Science, 2025, 52(3): 180-187.
[3] XIE Peizhong, LI Guanjin, LI Ting. Knowledge Tracing Model Based on Exercise-Knowledge Point Heterogeneous Graph andMulti-feature Fusion [J]. Computer Science, 2025, 52(3): 197-205.
[4] HU Haifeng, ZHU Yiwen, ZHAO Haitao. Network Slicing End-to-end Latency Prediction Based on Heterogeneous Graph Neural Network [J]. Computer Science, 2025, 52(3): 349-358.
[5] LIANG Jianpeng, MO Xiuliang, WANG Pengxiang, WANG Huanran, WANG Chundong. Research on Malicious Domain Detection Based on Heterogeneous Graph Inductive Learning [J]. Computer Science, 2025, 52(12): 358-366.
[6] SONG Jianhua, CAO Kai, ZHANG Yan. Smart Contract Bytecode Vulnerability Detection Method Based on Heterogeneous Graphs and Instruction Sequences [J]. Computer Science, 2025, 52(12): 367-373.
[7] LYU Shuqi, ZHANG Yunfeng. Fraud User Detection Based on Heterogeneous Information Network with Knowledge Graph Eembedding [J]. Computer Science, 2025, 52(11A): 250400085-7.
[8] MENG Lingjun, CHEN Hongchang, WANG Gengrun. Social Bots Detection Based on Multi-relationship Graph Attention Network [J]. Computer Science, 2025, 52(1): 298-306.
[9] YAN Qiuyan, SUN Hao, SI Yuqing, YUAN Guan. Multimodality and Forgetting Mechanisms Model for Knowledge Tracing [J]. Computer Science, 2024, 51(7): 133-139.
[10] MAO Xingjing, WEI Yong, YANG Yurui, JU Shenggen. KHGAS:Keywords Guided Heterogeneous Graph for Abstractive Summarization [J]. Computer Science, 2024, 51(7): 278-286.
[11] PENG Bo, LI Yaodong, GONG Xianfu, LI Hao. Method for Entity Relation Extraction Based on Heterogeneous Graph Neural Networks and TextSemantic Enhancement [J]. Computer Science, 2024, 51(6A): 230700071-5.
[12] WANG Xiaolong, WANG Yanhui, ZHANG Shunxiang, WANG Caiqin, ZHOU Yuhao. Gender Discrimination Speech Detection Model Fusing Post Attributes [J]. Computer Science, 2024, 51(6): 338-345.
[13] LIAO Jinzhi, ZHAO Hewei, LIAN Xiaotong, JI Wenliang, SHI Haiming, ZHAO Xiang. Contrastive Graph Learning for Cross-document Misinformation Detection [J]. Computer Science, 2024, 51(3): 14-19.
[14] SUN Pengzhao, BI Kejun, TANG Chao, LI Dongfen, YING Shi, WANG Ruijin. Risk Assessment Model for Industrial Chain Based on Neighbor Sampling and GraphAttention Mechanism [J]. Computer Science, 2024, 51(10): 218-226.
[15] WU Jiawei, FANG Quan, HU Jun, QIAN Shengsheng. Pre-training of Heterogeneous Graph Neural Networks for Multi-label Document Classification [J]. Computer Science, 2024, 51(1): 143-149.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.