HeGMN: heterogeneous graph matching network for learning graph similarity

Abstract

Graph similarity learning (GSL), also referred to as graph matching in many scenarios, is a fundamental problem in computer vision, pattern recognition, and graph learning. However, previous GSL methods assume that graphs are homogeneous and struggle to maintain their performance on heterogeneous graphs. To address this problem, this paper proposes a Heterogeneous Graph Matching Network (HeGMN), which is an end-to-end graph similarity learning framework composed of a two-tier matching mechanism. Firstly, a heterogeneous graph isomorphism network is proposed as the encoder, which reinvents graph isomorphism network for heterogeneous graphs by perceiving different semantic relationships during aggregation. Secondly, a graph-level and node-level matching modules are designed, both employing type-aligned matching principles. The former conducts graph-level matching by node type alignment, and the latter computes the interactions between the cross-graph nodes with the same type thus reducing noise interference and computational overhead. Finally, the graph-level and node-level matching features are combined and fed into fully connected layers for predicting graph similarity scores. In experiments, we propose a heterogeneous graph resampling method to construct heterogeneous graph pairs and define the corresponding heterogeneous graph edit distance, filling the gap in missing datasets. Extensive experiments demonstrate that HeGMN consistently achieves advanced performance on graph similarity prediction across all datasets.

Graphical abstract

Keywords

Heterogeneous graph / graph matching network / graph similarity learning / type-aligned matching principles

References

[1] Cardoso C, Sousa R T, Köhler S, Pesquita C . A collection of benchmark data sets for knowledge graph-based similarity in the biomedical domain. Database, 2020, 2020: baaa078

[2] Coupry D E, Pogány P . Application of deep metric learning to molecular graph similarity. Journal of Cheminformatics, 2022, 14( 1): 11

[3] Li Y, Gu C, Dullien T, Vinyals O, Kohli P. Graph matching networks for learning the similarity of graph structured objects. In: Proceedings of the 36th International Conference on Machine Learning. 2019, 3835−3845

[4] Noble C C, Cook D J. Graph-based anomaly detection. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 631−636

[5] Wang X, Ji H, Shi C, Wang B, Ye Y, Cui P, Yu P S. Heterogeneous graph attention network. In: Proceedings of the World Wide Web Conference. 2019, 2022−2032

[6] Li L, Yan M, Tao Z, Chen H, Wu X . Semi-supervised graph pattern matching and rematching for expert community location. ACM Transactions on Knowledge Discovery from Data, 2023, 17( 1): 6

[7] Ebsch C L, Cottam J A, Heller N C, Deshmukh R D, Chin G. Using graph edit distance for noisy subgraph matching of semantic property graphs. In: Proceedings of 2020 IEEE International Conference on Big Data. 2020, 2520−2525

[8] Qi Z, Zhang Z, Chen J, Chen X, Xiang Y, Zhang N, Zheng Y. Unsupervised knowledge graph alignment by probabilistic reasoning and semantic embedding. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence. 2021, 2019−2025

[9] Wu Y, Liu X, Feng Y, Wang Z, Zhao D. Neighborhood matching network for entity alignment. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020, 6477−6487

[10] Guo M, Chou E, Huang D A, Song S, Yeung S, Fei-Fei L. Neural graph matching networks for fewshot 3D action recognition. In: Proceedings of the 15th European Conference on Computer Vision. 2018, 673−689

[11] Jain E, Roy I, Meher S, Chakrabarti S, De A. Graph edit distance with general costs using neural set divergence. In: Proceedings of the 38th International Conference on Neural Information Processing Systems. 2024, 2335

[12] Fankhauser S, Riesen K, Bunke H. Speeding up graph edit distance computation through fast bipartite matching. In: Proceedings of the 8th APR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition. 2011, 102−111

[13] Riesen K, Bunke H . Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 2009, 27( 7): 950–959

[14] Bai Y, Ding H, Bian S, Chen T, Sun Y, Wang W. SimGNN: a neural network approach to fast graph similarity computation. In: Proceedings of the 12th ACM International Conference on Web Search and Data Mining. 2019, 384−392

[15] Tan W, Gao X, Li Y, Wen G, Cao P, Yang J, Li W, Zaiane O R . Exploring attention mechanism for graph similarity learning. Knowledge-Based Systems, 2023, 276: 110739

[16] Riesen K, Emmenegger S, Bunke H. A novel software toolkit for graph edit distance computation. In: Proceedings of the 9th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition. 2013, 142−151

[17] Bunke H . What is the distance between graphs. Bulletin of the EATCS, 1983, 20: 35–39

[18] Bunke H, Shearer K. A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 1998, 19(3−4): 255−259

[19] Borgwardt K M, Kriegel H P. Shortest-path kernels on graphs. In: Proceedings of the 5th IEEE International Conference on Data Mining. 2005, 74−81

[20] Yan X, Yu P S, Han J. Substructure similarity search in graph databases. In: Proceedings of 2005 ACM SIGMOD International Conference on Management of Data. 2005, 766−777

[21] Yoshida T, Takeuchi I, Karasuyama M. Learning interpretable metric between graphs: convex formulation and computation with graph mining. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019, 1026−1036

[22] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations. 2017, 1−14

[23] Xu K, Hu W, Leskovec J, Jegelka S. How powerful are graph neural networks? In: Proceedings of the 7th International Conference on Learning Representations. 2019, 1−17

[24] Bai Y, Ding H, Gu K, Sun Y, Wang W. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 3219−3226

[25] Jin D, Wang L, Zheng Y, Li X, Jiang F, Lin W, Pan S. CGMN: a contrastive graph matching network for self-supervised graph similarity learning. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence. 2022, 2101−2107

[26] Wang L, Zheng Y, Jin D, Li F, Qiao Y, Pan S . Contrastive graph similarity networks. ACM Transactions on the Web, 2024, 18( 2): 17

[27] Ling X, Wu L, Wang S, Ma T, Xu F, Liu A X, Wu C, Ji S . Multilevel graph matching networks for deep graph similarity learning. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34( 2): 799–813

[28] Zhuo W, Tan G. Efficient graph similarity computation with alignment regularization. In: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022, 2188

[29] Zheng H, Shi J, Yang R. GraSP: simple yet effective graph similarity predictions. In: Proceedings of the 39th AAAI Conference on Artificial Intelligence. 2025, 22884−22892

[30] Dong Y, Chawla N V, Swami A. metapath2vec: scalable representation learning for heterogeneous networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 135−144

[31] Yun S, Jeong M, Kim R, Kang J, Kim H J. Graph transformer networks. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. 2019, 1073

[32] Zhang C, Song D, Huang C, Swami A, Chawla N V. Heterogeneous graph neural network. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019, 793−803

[33] Lv Q, Ding M, Liu Q, Chen Y, Feng W, He S, Zhou C, Jiang J, Dong Y, Tang J. Are we really making much progress? Revisiting, benchmarking and refining heterogeneous graph neural networks. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 1150−1160

[34] Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. Graph attention networks. In: Proceedings of the 6th International Conference on Learning Representations. 2018, 1−12

[35] Wang J, Guo Y, Yang L, Wang Y . Enabling homogeneous GNNs to handle heterogeneous graphs via relation embedding. IEEE Transactions on Big Data, 2023, 9( 6): 1697–1710

[36] Chang L, Feng X, Yao K, Qin L, Zhang W . Accelerating graph similarity search via efficient GED computation. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 5): 4485–4498

[37] Schlichtkrull M, Kipf T N, Bloem P, van den Berg R, Titov I, Welling M. Modeling relational data with graph convolutional networks. In: Proceedings of the 15th International Conference on the Semantic Web. 2018, 593−607

[38] Blumenthal D B, Gamper J . On the exact computation of the graph edit distance. Pattern Recognition Letters, 2020, 134: 46–57

[39] Bai J, Zhao P . TaGSim: type-aware graph similarity learning and computation. Proceedings of the VLDB Endowment, 2021, 15( 2): 335–347

[40] Spearman C . The proof and measurement of association between two things. The American Journal of Psychology, 1904, 15( 1): 72–101

[41] Kendall M G . A new measure of rank correlation. Biometrika, 1938, 30( 1-2): 81–93

RIGHTS & PERMISSIONS

Higher Education Press