{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T06:15:40Z","timestamp":1778220940270,"version":"3.51.4"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62076015"],"award-info":[{"award-number":["62076015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:sec><jats:title>Abstract<\/jats:title><jats:p>Graphs are widely used to model real-life information, where graph similarity computation is one of the most significant applications, such as inferring the properties of a compound based on similarity to a known group. Definition methods (e.g., graph edit distance and maximum common subgraph) have extremely high computational cost, and the existing efficient deep learning methods suffer from the problem of inadequate feature extraction which would have a bad effect on similarity computation. In this paper, a double-branch model called DeepSIM was raised to deeply mine graph-level and node-level features to address the above problems. On the graph-level branch, a novel embedding relational reasoning network was presented to obtain interaction between pairwise inputs. Meanwhile, a new local-to-global attention mechanism is designed to improve the capability of CNN-based node-level feature extraction module on another path. In DeepSIM, double-branch outputs will be concatenated as the final feature. The experimental results demonstrate that our methods perform well on several datasets compared to the state-of-the-art deep learning models in related fields.<\/jats:p><\/jats:sec><jats:sec><jats:title>Graphical abstract<\/jats:title><\/jats:sec>","DOI":"10.1007\/s00500-023-09288-1","type":"journal-article","created":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T16:02:45Z","timestamp":1697126565000},"page":"61-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["DeepSIM: a novel deep learning method for graph similarity computation"],"prefix":"10.1007","volume":"28","author":[{"given":"Bo","family":"Liu","sequence":"first","affiliation":[]},{"given":"Zhihan","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Jidong","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Jiahui","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Guangzhi","family":"Qu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,12]]},"reference":[{"key":"9288_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Aisheh Z et al (2015) An exact graph edit distance algorithm for solving pattern recognition problems. In: 4th International conference on pattern recognition applications and methods","DOI":"10.5220\/0005209202710278"},{"key":"9288_CR2","unstructured":"Bai Y et al (2018) Convolutional set matching for graph similarity. arXiv preprint arXiv:1810.10866"},{"key":"9288_CR3","doi-asserted-by":"crossref","unstructured":"Bai Y et al (2019) Simgnn: a neural network approach to fast graph similarity computation. In: Proceedings of the Twelfth ACM international conference on web search and data mining","DOI":"10.1145\/3289600.3290967"},{"key":"9288_CR4","doi-asserted-by":"crossref","unstructured":"Bai Y et al (2020) Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In: Proceedings of the AAAI conference on artificial intelligence, vol 34, No. 04","DOI":"10.1609\/aaai.v34i04.5720"},{"issue":"04","key":"9288_CR5","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1142\/S0218001493000339","volume":"7","author":"J Bromley","year":"1993","unstructured":"Bromley J et al (1993) Signature verification using a \u201csiamese\u2019\u2019 time delay neural network. Int J Pattern Recogn Artif Intell 7(04):669\u2013688","journal-title":"Int J Pattern Recogn Artif Intell"},{"issue":"4","key":"9288_CR6","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","volume":"34","author":"MM Bronstein","year":"2017","unstructured":"Bronstein MM et al (2017) Geometric deep learning: going beyond Euclidean data. IEEE Signal Process Mag 34(4):18\u201342","journal-title":"IEEE Signal Process Mag"},{"issue":"4","key":"9288_CR7","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0167-8655(83)90033-8","volume":"1","author":"H Bunke","year":"1983","unstructured":"Bunke H, Allermann G (1983) Inexact graph matching for structural pattern recognition. Pattern Recogn Lett 1(4):245\u2013253","journal-title":"Pattern Recogn Lett"},{"issue":"3-4","key":"9288_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0167-8655(97)00179-7","volume":"19","author":"H Bunke","year":"1998","unstructured":"Bunke H, Shearer K (1998) A graph distance metric based on the maximal common subgraph. Pattern Recogn Lett 19(3\u20134):255\u2013259","journal-title":"Pattern Recogn Lett"},{"key":"9288_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/LGRS.2021.3105448","volume":"19","author":"U Chaudhuri","year":"2022","unstructured":"Chaudhuri U, Banerjee B, Bhattacharya A, Datcu M (2022) Attention-driven graph convolution network for remote sensing image retrieval. IEEE Geosci Remote Sens Lett 19:1\u20135. https:\/\/doi.org\/10.1109\/LGRS.2021.3105448","journal-title":"IEEE Geosci Remote Sens Lett"},{"key":"9288_CR10","doi-asserted-by":"crossref","unstructured":"Chen X et al (2020) One-shot adversarial attacks on visual tracking with dual attention. In: Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition","DOI":"10.1109\/CVPR42600.2020.01019"},{"key":"9288_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/ATSIP.2020.13","volume":"9","author":"F Chen","year":"2020","unstructured":"Chen F et al (2020) Graph representation learning: a survey. APSIPA Trans Signal Inf Process 9:e15","journal-title":"APSIPA Trans Signal Inf Process"},{"key":"9288_CR12","doi-asserted-by":"crossref","unstructured":"Chopra S, Hadsell R, LeCun Y (2005) Learning a similarity metric discriminatively, with application to face verification. In: 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR\u201905), vol 1. IEEE","DOI":"10.1109\/CVPR.2005.202"},{"issue":"1","key":"9288_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","volume":"13","author":"X Gao","year":"2010","unstructured":"Gao X et al (2010) A survey of graph edit distance. Pattern Anal Appl 13(1):113\u2013129","journal-title":"Pattern Anal Appl"},{"key":"9288_CR14","doi-asserted-by":"crossref","unstructured":"Grover A, Leskovec J (2016) \"node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining","DOI":"10.1145\/2939672.2939754"},{"key":"9288_CR15","unstructured":"Hamilton WL, Ying R, Leskovec J (2017) Inductive representation learning on large graphs. In: Proceedings of the 31st international conference on neural information processing systems"},{"key":"9288_CR16","doi-asserted-by":"crossref","unstructured":"He K et al (2016) Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition","DOI":"10.1109\/CVPR.2016.90"},{"key":"9288_CR17","doi-asserted-by":"crossref","unstructured":"Hu J, Shen L, Sun G (2018) Squeeze-and-excitation networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition","DOI":"10.1109\/CVPR.2018.00745"},{"key":"9288_CR18","unstructured":"Kingma DP, Ba J (2014) Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980"},{"key":"9288_CR19","unstructured":"Kipf TN, Welling M (2016) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907"},{"key":"9288_CR20","unstructured":"Koch G, Zemel R, Salakhutdinov R (2015) Siamese neural networks for one-shot image recognition. ICML deep learning workshop, vol 2"},{"issue":"1","key":"9288_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0195-3","volume":"5","author":"NM Kriege","year":"2020","unstructured":"Kriege NM, Johansson FD, Morris C (2020) A survey on graph kernels. Appl Netw Sci 5(1):1\u201342","journal-title":"Appl Netw Sci"},{"key":"9288_CR22","doi-asserted-by":"crossref","unstructured":"Ktena SI et al (2017) Distance metric learning using graph convolutional networks: application to functional brain networks. In: International conference on medical image computing and computer-assisted intervention. Springer, Cham","DOI":"10.1007\/978-3-319-66182-7_54"},{"key":"9288_CR23","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/j.neuroimage.2017.12.052","volume":"169","author":"SI Ktena","year":"2018","unstructured":"Ktena SI et al (2018) Metric learning with spectral graph convolutions on brain connectivity networks.\". NeuroImage 169:431\u2013442","journal-title":"NeuroImage"},{"key":"9288_CR24","doi-asserted-by":"crossref","unstructured":"Lagunas E et al (2018) Graph similarity based on graph Fourier distances. In: 2018 26th European signal processing conference (EUSIPCO). IEEE","DOI":"10.23919\/EUSIPCO.2018.8553486"},{"key":"9288_CR25","unstructured":"Le Quoc MT (2014) Distributed representations of sentences and documents. In: International conference on machine learning, PMLR"},{"key":"9288_CR26","unstructured":"Ling X et al (2020) Multi-level graph matching networks for deep and robust graph similarity learning"},{"key":"9288_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-16-6054-2_13","volume-title":"Graph Neural Networks: Foundations, Frontiers, and Applications","author":"X Ling","year":"2022","unstructured":"Ling X, Wu L, Wu C, Ji S (2022) Graph neural networks: graph matching. In: Wu L, Cui P, Pei J, Zhao L (eds) Graph Neural Networks: Foundations, Frontiers, and Applications. Springer, Singapore. https:\/\/doi.org\/10.1007\/978-981-16-6054-2_13"},{"key":"9288_CR28","doi-asserted-by":"crossref","unstructured":"Ma G et al (2019) Deep graph similarity learning for brain data analysis. In: Proceedings of the 28th ACM international conference on information and knowledge management","DOI":"10.1145\/3357384.3357815"},{"key":"9288_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10618-020-00733-5","volume":"35","author":"G Ma","year":"2021","unstructured":"Ma G et al (2021) Deep graph similarity learning: a survey. Data Min Knowl Discov 35:1\u201338","journal-title":"Data Min Knowl Discov"},{"key":"9288_CR30","unstructured":"Narayanan A et al (2017) graph2vec: learning distributed representations of graphs. arXiv preprint arXiv:1707.05005 (2017)"},{"issue":"10","key":"9288_CR31","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1016\/j.patcog.2006.04.012","volume":"39","author":"M Neuhaus","year":"2006","unstructured":"Neuhaus M, Bunke H (2006) Edit distance-based kernel functions for structural pattern classification. Pattern Recogn 39(10):1852\u20131863","journal-title":"Pattern Recogn"},{"key":"9288_CR32","doi-asserted-by":"crossref","unstructured":"Nikolentzos G, Meladianos P, Vazirgiannis M (2017) Matching node embeddings for graph similarity. In: Thirty-first AAAI conference on artificial intelligence","DOI":"10.1609\/aaai.v31i1.10839"},{"key":"9288_CR33","first-page":"1","volume":"33","author":"S Ok","year":"2020","unstructured":"Ok S (2020) A graph similarity for deep learning. Adv Neural Inf Process Syst 33:1\u201312","journal-title":"Adv Neural Inf Process Syst"},{"issue":"5","key":"9288_CR34","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1109\/JPROC.2018.2820126","volume":"106","author":"A Ortega","year":"2018","unstructured":"Ortega A et al (2018) Graph signal processing: overview, challenges, and applications. Proc IEEE 106(5):808\u2013828","journal-title":"Proc IEEE"},{"key":"9288_CR35","doi-asserted-by":"crossref","unstructured":"Papadimitriou P, Dasdan A, Garcia-Molina H (2010) Web graph similarity for anomaly detection. J Internet Serv Appl 1(1):19\u201330","DOI":"10.1007\/s13174-010-0003-x"},{"key":"9288_CR36","doi-asserted-by":"crossref","unstructured":"Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining","DOI":"10.1145\/2623330.2623732"},{"key":"9288_CR37","doi-asserted-by":"crossref","unstructured":"Qin Z, Bai Y, Sun Y (2020) Ghashing: semantic graph hashing for approximate similarity search in graph databases. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining","DOI":"10.1145\/3394486.3403257"},{"issue":"7","key":"9288_CR38","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1016\/j.imavis.2008.04.004","volume":"27","author":"K Riesen","year":"2009","unstructured":"Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27(7):950\u2013959","journal-title":"Image Vis Comput"},{"key":"9288_CR39","unstructured":"Shervashidze N et al (2011) Weisfeiler-lehman graph kernels. J Mach Learn Res 12(9)"},{"key":"9288_CR40","unstructured":"Socher R et al (2013) Reasoning with neural tensor networks for knowledge base completion. Adv Neural Inf Process Syst"},{"key":"9288_CR41","first-page":"129","volume-title":"On graph kernels: hardness results and efficient alternatives. Learning theory and kernel machines","author":"G Thomas","year":"2003","unstructured":"Thomas G, Peter F, Stefan W (2003) On graph kernels: hardness results and efficient alternatives. Learning theory and kernel machines. Springer, Berlin, pp 129\u2013143"},{"key":"9288_CR42","doi-asserted-by":"crossref","unstructured":"Tixier AJ-P et al (2019) Graph classification with 2d convolutional neural networks. In: International conference on artificial neural networks. Springer, Cham","DOI":"10.1007\/978-3-030-30493-5_54"},{"issue":"10","key":"9288_CR43","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1093\/bioinformatics\/btg130","volume":"19","author":"H Toivonen","year":"2003","unstructured":"Toivonen H et al (2003) Statistical evaluation of the predictive toxicology challenge 2000\u20132001. Bioinformatics 19(10):1183\u20131193","journal-title":"Bioinformatics"},{"key":"9288_CR44","unstructured":"Veli\u010dkovi\u0107 P et al (2017) Graph attention networks. arXiv preprint arXiv:1710.10903"},{"key":"9288_CR45","doi-asserted-by":"crossref","unstructured":"Wang X et al (2012) An efficient graph indexing method. In: 2012 IEEE 28th international conference on data engineering. IEEE","DOI":"10.1109\/ICDE.2012.28"},{"issue":"9","key":"9288_CR46","first-page":"12","volume":"2","author":"B Weisfeiler","year":"1968","unstructured":"Weisfeiler B, Leman A (1968) The reduction of a graph to canonical form and the algebra which appears therein. NTI Ser 2(9):12\u201316","journal-title":"NTI Ser"},{"issue":"1","key":"9288_CR47","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","volume":"32","author":"Z Wu","year":"2020","unstructured":"Wu Z et al (2020) A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 32(1):4\u201324","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"9288_CR48","unstructured":"Xu Zhou-bo ZK et al (2018) Summary of graph edit distance. Comput Sci"},{"key":"9288_CR49","doi-asserted-by":"crossref","unstructured":"Yanardag P, Vishwanathan SVN (2015) Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining","DOI":"10.1145\/2783258.2783417"},{"key":"9288_CR50","doi-asserted-by":"crossref","unstructured":"Zagoruyko S, Komodakis N (2015) Learning to compare image patches via convolutional neural networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition","DOI":"10.1109\/CVPR.2015.7299064"},{"issue":"12","key":"9288_CR51","doi-asserted-by":"publisher","first-page":"i259","DOI":"10.1093\/bioinformatics\/btp196","volume":"25","author":"M Zaslavskiy","year":"2009","unstructured":"Zaslavskiy M, Bach F, Vert J-P (2009) Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics 25(12):i259-1267","journal-title":"Bioinformatics"},{"issue":"1","key":"9288_CR52","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/1687627.1687631","volume":"2","author":"Z Zeng","year":"2009","unstructured":"Zeng Z et al (2009) Comparing stars: on approximating graph edit distance. Proc VLDB Endow 2(1):25\u201336","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"9288_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40649-019-0069-y","volume":"6","author":"S Zhang","year":"2019","unstructured":"Zhang S et al (2019) Graph convolutional networks: a comprehensive review. Comput Soc Netw 6(1):1\u201323","journal-title":"Comput Soc Netw"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-09288-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-023-09288-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-09288-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T18:53:15Z","timestamp":1730314395000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-023-09288-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["9288"],"URL":"https:\/\/doi.org\/10.1007\/s00500-023-09288-1","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]},"assertion":[{"value":"16 September 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors confirm that the content of this article has no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research involving human and animal participants"}}]}}