This is an unedited manuscript accepted for publication and provided as an Article in Press for early access at the author’s request. The article will undergo copyediting, typesetting, and galley proof review before final publication. Please be aware that errors may be identified during production that could affect the content. All legal disclaimers of the journal apply.
Ashwani Kumar Yadav,
Prakash Dwivedi,
- Research Scholar, Department of Information Technology G. B. Pant University of Agriculture and Technology, Uttarakhand, India
- Assistant Professor, Department of Information Technology G. B. Pant University of Agriculture and Technology, Uttarakhand, India
Abstract
Graph-structured data is increasingly prevalent in many real-world applications such as social networks, biological systems, molecular chemistry, and knowledge graphs. Measuring the similarity between graphs is a fundamental task in graph analytics, enabling applications including pattern recognition, recommendation systems, network alignment, and drug discovery. Traditional approaches for graph similarity computation, such as Graph Edit Distance and graph kernels, provide effective structural comparison but often suffer from high computational complexity and limited scalability when applied to large datasets. In recent years, Graph Neural Networks (GNNs) and other deep learning methods have become highly effective for automatically learning graph representations and measuring similarity through end-to-end training. This review paper presents a comprehensive survey of graph similarity computation methods with a focus on deep learning-based approaches. We first discuss classical graph similarity techniques and their limitations, followed by an overview of graph representation learning using GNN architectures. We discuss modern deep learning frameworks for graph similarity, including graph embedding models, Siamese Graph Neural Networks, and graph matching networks. Finally, we identify key research gaps and outline future directions, including scalable graph similarity models, self-supervised learning, interpretable graph neural networks, and dynamic graph similarity analysis. This survey offers researchers a comprehensive overview of recent advancements in deep learning-based graph similarity computation while highlighting the key challenges and research opportunities that remain to be addressed.
Keywords: Graph Similarity, Graph Neural Networks, Graph Matching, Graph Representation Learning, Deep Learning on Graphs, Knowledge Graph Alignment, Graph Embedding, Geometric Deep Learning
References
[1] Zanfir A, Sminchisescu C. Deep learning of graph matching. InProceedings of the IEEE conference on computer vision and pattern recognition 2018 (pp. 2684-2693).[2] Bai Y, Ding H, Bian S, Chen T, Sun Y, Wang W. Simgnn: A neural network approach to fast graph similarity computation. InProceedings of the twelfth ACM international conference on web search and data mining 2019 Jan 30 (pp. 384-392).
[3] Li Y, Gu C, Dullien T, Vinyals O, Kohli P. Graph matching networks for learning the similarity of graph structured objects. InInternational conference on machine learning 2019 May 24 (pp. 3835-3845). PMLR.
[4] Xu K, Hu W, Leskovec J, Jegelka S. How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826. 2018 Oct 1.
[5] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. 2016 Sep 9.
[6] Veličković P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y. Graph attention networks. InInternational conference on learning representations 2018 Apr 30 (Vol. 6, No. 10.48550).
[7] Hamilton WL, Ying R, Leskovec J. Inductive representation learning on large graphs. arXiv preprint arXiv:1706.02216. 2017 Jun 7.
[8] Bunke H. Graph matching: Theoretical foundations, algorithms, and applications. InProc. Vision Interface 2000 May 14 (Vol. 2000, pp. 82-88).
[9] Riesen K, Bunke H. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing. 2009 Jun 4;27(7):950-9.
[10] Shervashidze N, Schweitzer P, Van Leeuwen EJ, Mehlhorn K, Borgwardt KM. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research. 2011 Sep 1;12(9).
[11] Kashima H, Tsuda K, Inokuchi A. Marginalized kernels between labeled graphs. InProceedings of the 20th international conference on machine learning (ICML-03) 2003 (pp. 321-328).
[12] Dwivedi SP, Singh RS. Structural Pattern Recognition using Graph Matching: Approximate and Error-Tolerant Algorithms. CRC Press; 2025 Sep 30.
[13] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. InProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining 2014 Aug 24 (pp. 701-710).
[14] Grover A, Leskovec J. node2vec: Scalable feature learning for networks. InProceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining 2016 Aug 13 (pp. 855-864).
[15] Fey M, Lenssen JE, Morris C, Masci J, Kriege NM. Deep graph matching consensus. arXiv preprint arXiv:2001.09621. 2020 Jan 27.
[16] Fey M, Lenssen JE. Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428. 2019 Mar 6.
[17] Li Y, Tarlow D, Brockschmidt M, Zemel R. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493. 2015 Nov 17.
[18] Ying R, You J, Morris C, Ren X, Hamilton WL, Leskovec J. Hierarchical graph representation learning with differentiable pooling. arXiv preprint arXiv:1806.08804. 2018 Jun 22.
[19] Bai Y, Ding H, Gu K, Sun Y, Wang W. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. InProceedings of the AAAI conference on artificial intelligence 2020 Apr 3 (Vol. 34, No. 04, pp. 3219-3226).
[20] Ma G, Ahmed NK, Willke TL, Yu PS. Deep graph similarity learning: A survey. arXiv preprint arXiv:1912.11615. 2019 Dec 25.
[21] Zhou J, Cui G, Hu S, Zhang Z, Yang C, Liu Z, Wang L, Li C, Sun M. Graph neural networks: A review of methods and applications. AI open. 2020 Jan 1;1:57-81.
[22] Liu M, Gao H, Ji S. Towards deeper graph neural networks. InProceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining 2020 Aug 23 (pp. 338-348).
[23] Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems. IEEE Transactions on Neural Networks and Learning Systems (Volume: 32, Issue: 1). 2020.
[24] Pattanaik BP, Shukla DK, Satpathy S, Muduli K, editors. Sustainable Developments in Computer Engineering, Green Technology and Smart Systems: Volume 2. CRC Press; 2026 Jul 21.
[25] Zhang M, Chen Y. Link prediction based on graph neural networks. Advances in neural information processing systems. 2018;31.
[26] You Y, Chen T, Sui Y, Chen T, Wang Z, Shen Y. Graph contrastive learning with augmentations. Advances in neural information processing systems. 2020;33:5812-23.
[27] He X, Deng K, Wang X, Li Y, Zhang Y, Wang M. Lightgcn: Simplifying and powering graph convolution network for recommendation. InProceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval 2020 Jul 25 (pp. 639-648).
[28] Morris C, Ritzert M, Fey M, Hamilton WL, Lenssen JE, Rattan G, Grohe M. Weisfeiler and leman go neural: Higher-order graph neural networks. InProceedings of the AAAI conference on artificial intelligence 2019 Jul 17 (Vol. 33, No. 01, pp. 4602-4609).
[29] Waikhom L, Patgiri R. A survey of graph neural networks in various learning paradigms: methods, applications, and challenges. Artificial Intelligence Review. 2023 Jul;56(7):6295-364.
[30] Jiao L, Chen J, Liu F, Yang S, You C, Liu X, Li L, Hou B. Graph representation learning meets computer vision: A survey. IEEE Transactions on Artificial Intelligence. 2022 Jul 29;4(1):2-2.
Journal of Computer Technology & Applications
| Volume | 17 | |
| 02 | ||
| Received | 23/04/2026 | |
| Accepted | 23/07/2026 | |
| Published | 03/09/2026 | |
| Publication Time | 133 Days |