基于直积图结构挖掘的图相似度计算方法&#x0002A;

张龙跃; 赵彤

doi:10.7523/j.ucas.2026.022

中国科学院大学学报 >

0 73

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

基于直积图结构挖掘的图相似度计算方法^*

张龙跃 ,
赵彤

展开

中国科学院大学数学科学学院,北京 100049

收稿日期: 2025-12-04

修回日期: 2026-04-15

网络出版日期: 2026-04-21

基金资助

^*国家自然科学基金 (12271504,T2341006）和教育部学科先导突破项目（JYB2025XDXM612）资助

收起

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

摘要

图相似度计算是一项基础而富有挑战性的任务,其通过量化图数据的内在结构与关联模式来揭示它们功能或行为上的相似性。该任务在生物信息学、软件工程及社交网络分析等领域扮演着核心角色,广泛应用于分子结构比对、代码抄袭检测及社群发现。尽管基于图神经网络（graph neural network,GNN）的方法有效近似了图编辑距离（graph edit distance,GED）等经典度量,但它们往往难以捕捉细粒度的拓扑关系。这种局限性限制了图嵌入向量的表征能力,导致模型无法充分反映图与图之间的结构差异。本文提出了一种基于直积图结构挖掘的图相似度计算方法（DSM-GSC）。该方法核心是构建直积图,以显式建模图对间所有潜在的节点配对关系。针对传统 GNN 嵌入表征能力不足的问题,引入了一个结构学习模块,旨在从直积图庞大的搜索空间中,甄别并提取出能表征关键拓扑对应的子结构,并利用这些子结构指导节点对齐与相似性的联合优化。这一机制使得模型突破了对全局嵌入的单一依赖,实现了基于关键结构模式的精准对齐。在多个基准数据集上的实验表明,该方法展现出了独特的优势,证实本文提出的图相似度计算新方法是可行且有效的。

关键词： 图数据; 图神经网络; 图相似度计算; 图结构学习

本文引用格式

张龙跃 , 赵彤 . 基于直积图结构挖掘的图相似度计算方法^*[J]. 中国科学院大学学报, 0 : 73 . DOI: 10.7523/j.ucas.2026.022

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

参考文献

[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

文章导航

摘要

本文引用格式

Abstract

参考文献

访问统计

联系我们

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献

访问统计

联系我们