Graph similarity computation method based on structure mining of direct product graphs

ZHANG Longyue; ZHAO Tong

doi:10.7523/j.ucas.2026.022

Journal of University of Chinese Academy of Sciences >

0 73

DOI: https://doi.org/10.7523/j.ucas.2026.022

Graph similarity computation method based on structure mining of direct product graphs

ZHANG Longyue ,
ZHAO Tong

Expand

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Received date: 2025-12-04

Revised date: 2026-04-15

Online published: 2026-04-21

Fold

Abstract

Graph similarity computation is a fundamental yet challenging task that reveals functional or behavioral similarities by quantifying the intrinsic structures and relational patterns of graph data. It plays a pivotal role in applications such as molecular structure alignment in bioinformatics, code plagiarism detection in software engineering, and community detection in social network analysis. Although methods based on Graph Neural Networks (GNN) offer effective approximations for classical metrics like Graph Edit Distance (GED), they often struggle to capture fine-grained topological relationships. This limitation constrains the representational capacity of learned graph embeddings, rendering them unable to adequately reflect structural discrepancies between graphs. To address this, this paper proposes a Graph Similarity Computation method based on Direct Structure Mining (DSM-GSC). At its core, the method constructs a product graph to explicitly model all potential node pairing relationships between two graphs. To overcome the limited representational capacity of traditional GNN embeddings, we introduce a structural learning module designed to identify and extract discriminative substructures—representing key topological correspondences—from the vast search space of the product graph. These structural patterns are subsequently utilized to guide the joint optimization of node alignment and similarity computation. This mechanism enables the model to break the reliance on global embeddings alone, achieving precise alignment driven by key structural patterns. Extensive experiments on multiple benchmark datasets demonstrate the unique advantages of the proposed method, verifying the feasibility and effectiveness of this new paradigm for graph similarity computation.

Key words： graph data; graph neural networks; graph similarity computation; graph structure learning

Cite this article

ZHANG Longyue , ZHAO Tong . Graph similarity computation method based on structure mining of direct product graphs[J]. Journal of University of Chinese Academy of Sciences, 0 : 73 . DOI: 10.7523/j.ucas.2026.022

References

[1] Coupry D E, Pogány P.Application of deep metric learning to molecular graph similarity[J]. Journal of Cheminformatics, 2022, 14(1): 11. DOI: 10.1186/s13321-022-00595-7.
[2] Ktena S I, Parisot S, Ferrante E, et al.Distance metric learning using graph convolutional networks: Application to functional brain networks[C]//Medical Image Computing and Computer Assisted Intervention - MICCAI 2017. Cham: Springer, 2017: 469-477. DOI: 10.1007/978-3-319-66182-7_54.
[3] Bibi N, Maqbool A, Rana T, et al.Enhancing semantic code search with deep graph matching[J]. IEEE Access, 2023, 11: 52392-52411. DOI: 10.1109/ACCESS.2023.3263878.
[4] Ferrante J, Ottenstein K J, Warren J D.The program dependence graph and its use in optimization[C]//International Symposium on Programming. Berlin, Heidelberg: Springer, 1984: 125-132. DOI: 10.1007/3-540-12925-1_33.
[5] Gabel M, Jiang L X, Su Z D.Scalable detection of semantic clones[C]//2008 ACM/IEEE 30th International Conference on Software Engineering. May 10-18, 2008, Leipzig, Germany. IEEE, 2009: 321-330. DOI: 10.1145/1368088.1368132.
[6] Bunke H.On a relation between graph edit distance and maximum common subgraph[J]. Pattern Recognition Letters, 1997, 18(8): 689-694. DOI: 10.1016/S0167-8655(97)00060-3.
[7] Sanfeliu A, Fu K S. A distance measure between attributed relational graphs for pattern recognition[J]. IEEE Transactions on Systems, Man,Cybernetics, 1983, SMC-13(3): 353-362. DOI: 10.1109/TSMC.1983.6313167.
[8] Bai Y S, Xu D, Sun Y Z, et al.GLSearch: Maximum common subgraph detection via learning to search[C]//International Conference on Machine Learning (ICML). PMLR, 2020: 588-598.
[9] Neuhaus M, Riesen K, Bunke H.Fast suboptimal algorithms for the computation of graph edit distance[C]//Structural, Syntactic, and Statistical Pattern Recognition. Berlin, Heidelberg: Springer, 2006: 163-172. DOI: 10.1007/11815921_17.
[10] Liang Y J, Zhao P X.Similarity search in graph databases: A multi-layered indexing approach[C]//2017 IEEE 33rd International Conference on Data Engineering (ICDE). April 19-22, 2017, San Diego, CA, USA. IEEE, 2017: 783-794. DOI: 10.1109/ICDE.2017.129.
[11] Riesen K, Bunke H.Approximate graph edit distance computation by means of bipartite graph matching[J]. Image and Vision Computing, 2009, 27(7): 950-959. DOI: 10.1016/j.imavis.2008.04.004.
[12] Zhuo W, Tan G.Efficient graph similarity computation with alignment regularization[C]//Proceedings of the 36th International Conference on Neural Information Processing Systems. 28 November 2022, New Orleans, LA, USA. ACM, 2022: 30181-30193. DOI: 10.5555/3600270.3602458.
[12] Zhuo W, Tan G.Efficient graph similarity computation with alignment regularization[C]//Advances in Neural Information Processing Systems. Curran Associates, Inc., 2022, 35: 30181-30193.
[13] Jiang N, Ning B, Dong J Y.A survey of GNN-based graph similarity learning[C]//2023 8th International Conference on Image, Vision and Computing (ICIVC). July 27-29, 2023, Dalian, China. IEEE, 2023: 650-654. DOI: 10.1109/ICIVC58118.2023.10269885.
[14] Ling X, Wu L F, Wu C M, et al.Graph neural networks: Graph matching[M]//Graph Neural Networks: Foundations, Frontiers, and Applications. Singapore: Springer Nature Singapore, 2022: 277-295. DOI: 10.1007/978-981-16-6054-2_13.
[15] Tao T, Wang Q Q, Ruan Y, et al.Graph embedding with similarity metric learning[J]. Symmetry, 2023, 15(8): 1618. DOI: 10.3390/sym15081618.
[16] Liu Z, Liu N, Chen Y, et al.Graph Theory-Based Deep Graph Similarity Learning: A Unified Survey of Pipeline, Techniques, and Challenges[J]. Transactions on Machine Learning Research (TMLR), 2025.
[17] Li Y J, Gu C J, Dullien T, et al.Graph matching networks for learning the similarity of graph structured objects[C]//International Conference on Machine Learning (ICML). PMLR, 2019: 3835-3845.
[18] Bai Y S, Ding H, Bian S, et al.SimGNN: A neural network approach to fast graph similarity computation[C]//Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. Melbourne VIC Australia. ACM, 2019: 384-392. DOI: 10.1145/3289600.3290967.
[19] Bai Y S, Ding H, Gu K, et al.Learning-based efficient graph similarity computation via multi-scale convolutional set matching[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(4): 3219-3226. DOI: 10.1609/aaai.v34i04.5720.
[20] Jia R Q, Feng X B, Lyu X Q, et al.Graph-graph context dependency attention for graph edit distance[C]//ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). June 4-10, 2023, Rhodes Island, Greece. IEEE, 2023: 1-5. DOI: 10.1109/ICASSP49357.2023.10094975.
[21] Piao C Z, Xu T Y, Sun X G, et al.Computing graph edit distance via neural graph matching[J]. Proceedings of the VLDB Endowment, 2023, 16(8): 1817-1829. DOI: 10.14778/3594512.3594514.
[22] Veličković P, Cucurull G, Casanova A, et al.Graph attention networks[C]//Proceedings of the 6th International Conference on Learning Representations (ICLR). 2018.
[23] Wang P Y, Gui J P, Chen Z Z, et al.A generic edge-empowered graph convolutional network via node-edge mutual enhancement[C]//Proceedings of The Web Conference 2020. April 20 - 24, 2020, Taipei, Taiwan. ACM, 2020: 2144-2154. DOI: 10.1145/3366423.3380280.
[24] Xia Y K, Chen J Z, Li X C, et al.DeepNM: Incremental graph matching based on sinkhorn similarity[J]. IEEE Transactions on Knowledge and Data Engineering, 2025, 37(9): 5141-5157. DOI: 10.1109/TKDE.2025.3583059.
[25] Tan W H, Cao P, Jin Z Y, et al.DGE-GSIM: A multi-task dual graph embedding learning for graph similarity computation[C]//Proceedings of the 2022 6th International Conference on Machine Learning and Soft Computing. January 15 - 17, 2022, Haikou, China. ACM, 2022: 39-47. DOI: 10.1145/3523150.3523157.
[26] Roy I, Velugoti V S B R, Chakrabarti S, et al. Interpretable neural subgraph matching for graph retrieval[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2022, 36(7): 8115-8123. DOI: 10.1609/aaai.v36i7.20784.
[27] Liu J F, Zhou M, Ma S, et al.MATA*: Combining learnable node matching with A* algorithm for approximate graph edit distance computation[C]//Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. Birmingham United Kingdom. ACM, 2023: 1503-1512. DOI: 10.1145/3583780.3614959.
[28] Cho M, Lee J, Lee K M.Reweighted random walks for graph matching[C]//Computer Vision - ECCV 2010. Berlin, Heidelberg: Springer, 2010: 492-505. DOI: 10.1007/978-3-642-15555-0_36.
[29] Tan W H, Gao X, Li Y Y, et al.Exploring attention mechanism for graph similarity learning[J]. Knowledge-Based Systems, 2023, 276: 110739. DOI: 10.1016/j.knosys.2023.110739.
[30] Qin C, Zhao H, Wang L, et al.Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation[C]//Advances in Neural Information Processing Systems. 2021, 34: 14110-14121.
[31] Jin D, Wang L Z, Zheng Y Z, et al.CGMN: A contrastive graph matching network for self-supervised graph similarity learning[C]//Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. July 23-29, 2022. Vienna, Austria. International Joint Conferences on Artificial Intelligence Organization, 2022: 2101-2107. DOI: 10.24963/ijcai.2022/292.
[32] Zhang Z, Bu J J, Ester M, et al.H2MN: Graph similarity learning with hierarchical hypergraph matching networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. Virtual Event Singapore. ACM, 2021: 2274-2284. DOI: 10.1145/3447548.3467328.
[33] Ling X, Wu L F, Wang S Z, et al.Multilevel graph matching networks for deep graph similarity learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34(2): 799-813. DOI: 10.1109/TNNLS.2021.3102234.
[34] Cheng Q H, Yan D, Wu T H, et al.Computing approximate graph edit distance via optimal transport[J]. Proceedings of the ACM on Management of Data, 2025, 3(1): 1-26. DOI: 10.1145/3709673.
[35] Jin W, Ma Y, Liu X R, et al.Graph structure learning for robust graph neural networks[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. July 6 - 10, 2020, Virtual Event, CA, USA. ACM, 2020: 66-74. DOI: 10.1145/3394486.3403049.
[36] Chen Y, Wu L F, Zaki M J. Iterative deep graph learning for graph neural networks: better and robust node embeddings[EB/OL].2020: arXiv: 2006.13009(2020-06-21)[2026-02-28]. https://arxiv.org/abs/2006.13009.
[37] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[EB/OL].2016: arXiv: 1609.02907(2016-09-09)[2026-02-28]. https://arxiv.org/abs/1609.02907.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References