{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:40:54Z","timestamp":1773895254667,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T00:00:00Z","timestamp":1747872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Subgraph matching is the problem of finding all the occurrences of a small graph, called the query, in a larger graph, called the target. Although the problem has been widely studied in simple graphs, few solutions have been proposed for multigraphs, in which two nodes can be connected by multiple edges, each denoting a possibly different type of relationship. In our new algorithm MultiGraphMatch (MGM), nodes and edges can be associated with labels and multiple properties. MGM introduces a novel data structure called bit matrix to efficiently index both the query and the target and filter the set of target edges that are matchable with each query edge. In addition, the algorithm proposes a new technique for ordering the processing of query edges based on the cardinalities of the sets of matchable edges. Using the CYPHER query definition language, MGM can perform queries with logical conditions on node and edge labels. We compare MGM with SuMGra and graph database systems Memgraph and Neo4J, showing comparable or better performance in all queries on a wide variety of synthetic and real-world graphs.<\/jats:p>","DOI":"10.1145\/3728361","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T18:24:48Z","timestamp":1744136688000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["MultiGraphMatch: A Subgraph Matching Algorithm for Multigraphs"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4953-026X","authenticated-orcid":false,"given":"Giovanni","family":"Micale","sequence":"first","affiliation":[{"name":"University of Catania, Catania, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9300-2297","authenticated-orcid":false,"given":"Antonio","family":"Di Maria","sequence":"additional","affiliation":[{"name":"University of Catania, Catania, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7641-1979","authenticated-orcid":false,"given":"Roberto","family":"Grasso","sequence":"additional","affiliation":[{"name":"University of Catania, Catania, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1637-7545","authenticated-orcid":false,"given":"Vincenzo","family":"Bonnici","sequence":"additional","affiliation":[{"name":"University of Parma, Parma, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9431-5788","authenticated-orcid":false,"given":"Alfredo","family":"Ferro","sequence":"additional","affiliation":[{"name":"University of Catania, Catania, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7036-3312","authenticated-orcid":false,"given":"Dennis","family":"Shasha","sequence":"additional","affiliation":[{"name":"New York University, New York, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9843-7638","authenticated-orcid":false,"given":"Rosalba","family":"Giugno","sequence":"additional","affiliation":[{"name":"University of Verona, Verona, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9764-0295","authenticated-orcid":false,"given":"Alfredo","family":"Pulvirenti","sequence":"additional","affiliation":[{"name":"University of Catania, Catania, Italy"}]}],"member":"320","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"7","volume-title":"Proceedings of the 4th International Conference on Smart City Applications (SCA \u201919)","author":"Alaoui K.","year":"2019","unstructured":"K. Alaoui. 2019. A categorization of RDF triplestores. In Proceedings of the 4th International Conference on Smart City Applications (SCA \u201919). ACM, New York, NY, Article 66, 7 pages. DOI: 10.1145\/3368756.3369047"},{"key":"e_1_3_2_3_2","first-page":"1","volume-title":"Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data ManagementCEUR Workshop Proceedings","volume":"2100","author":"Angles R.","year":"2018","unstructured":"R. Angles. 2018. The property graph database model. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management. CEUR Workshop Proceedings, Vol. 2100, CEUR-WS.org, 1\u201310."},{"key":"e_1_3_2_4_2","unstructured":"R. Angles J. B. Antal A. Averbuch A. Birler P. Boncz M. B\u00far O. Erling A. Gubichev V. Haprian M. Kaufmann et al. 2020. The LDBC social network benchmark. arXiv:2001.02299. Retrieved from http:\/\/arxiv.org\/abs\/2001.02299"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.3390\/math10244830"},{"key":"e_1_3_2_6_2","first-page":"131","volume-title":"Proceedings of the 12th International Conference on Practical Applications of Computational Biology and Bioinformatics","author":"Aparo A.","year":"2019","unstructured":"A. Aparo, V. Bonnici, G. Micale, A. Ferro, D. Shasha, A. Pulvirenti, and R. Giugno. 2019. Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. In Proceedings of the 12th International Conference on Practical Applications of Computational Biology and Bioinformatics. Springer International Publishing, Cham, 131\u2013138."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.3390\/genes12071004"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"1447","DOI":"10.1145\/3299869.3300086","volume-title":"Proceedings of the 2019 International Conference on Management of Data (SIGMOD \u201919)","author":"Bhattarai B.","year":"2019","unstructured":"B. Bhattarai, H. Liu, and H. H. Huang. 2019. CECI: Compact embedding cluster index for scalable subgraph matching. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD \u201919). ACM, New York, NY, 1447\u20131462. DOI: 10.1145\/3299869.3300086"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1145\/2882903.2915236","volume-title":"Proceedings of the 2016 International Conference on Management of Data (SIGMOD \u201916)","author":"Bi F.","year":"2016","unstructured":"F. Bi, L. Chang, X. Lin, L. Qin, and W. Zhang. 2016. Efficient subgraph matching by postponing cartesian products. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD \u201916). ACM, New York, NY, 1199\u20131214. DOI: 10.1145\/2882903.2915236"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2016.2515595"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2696940"},{"key":"e_1_3_2_14_2","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC \u201971)","author":"Cook S. A.","year":"1971","unstructured":"S. A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC \u201971). ACM, New York, NY, 151\u2013158. DOI: 10.1145\/800157.805047"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0061183"},{"key":"e_1_3_2_17_2","unstructured":"A. Deutsch Y. Xu M. Wu and V. E. Lee. 2019. TigerGraph: A native MPP graph database. arXiv:1901.08248. Retrieved from http:\/\/arxiv.org\/abs\/1901.08248"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"1433","DOI":"10.1145\/3183713.3190657","volume-title":"Proceedings of the 2018 International Conference on Management of Data (SIGMOD \u201918)","author":"Francis N.","year":"2018","unstructured":"N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, P. Selmer, and A. Taylor. 2018. Cypher: An evolving query language for property graphs. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD \u201918). ACM, New York, NY, 1433\u20131445. DOI: 10.1145\/3183713.3190657"},{"issue":"10","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0076911","article-title":"GRAPES: A software for parallel searching on biological graphs targeting multi-core architectures","volume":"8","author":"Giugno R.","year":"2013","unstructured":"R. Giugno, V. Bonnici, N. Bombieri, A. Pulvirenti, A. Ferro, and D. Shasha. 2013. GRAPES: A software for parallel searching on biological graphs targeting multi-core architectures. PLoS One 8, 10 (2013), 1\u201311.","journal-title":"PLoS One"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1145\/3299869.3319880","volume-title":"Proceedings of the 2019 International Conference on Management of Data (SIGMOD \u201919)","author":"Han M.","year":"2019","unstructured":"M. Han, H. Kim, G. Gu, K. Park, and W. Han. 2019. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD \u201919). ACM, New York, NY, 1429\u20131446. DOI: 10.1145\/3299869.3319880"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/2463676.2465300","volume-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201913)","author":"Han W.","year":"2013","unstructured":"W. Han, J. Lee, and J. Lee. 2013. TurboISO: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201913). ACM, New York, NY, 337\u2013348. DOI: 10.1145\/2463676.2465300"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/1376616.1376660","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201908)","author":"He H.","year":"2008","unstructured":"H. He and A. K. Singh. 2008. Graphs-at-a-Time: Query language and access methods for graph databases. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201908). ACM, New York, NY, 405\u2013418. DOI: 10.1145\/1376616.1376660"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0097896"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/978-3-319-44403-1_24","volume-title":"Database and Expert Systems Applications","author":"Ingalalli V.","year":"2016","unstructured":"V. Ingalalli, D. Ienco, and P. Poncelet. 2016. SuMGra: Querying multigraphs via efficient indexing. In Database and Expert Systems Applications. S. Hartmann and H. Ma (Eds.), Springer International Publishing, Cham, 387\u2013401."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02433-7"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129501003577"},{"issue":"1","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2898361","article-title":"SNAP: A general-purpose network analysis and graph-mining library","volume":"8","author":"Leskovec J.","year":"2016","unstructured":"J. Leskovec and R. Sosi\u010d. 2016. SNAP: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology 8, 1 (2016), 1.","journal-title":"ACM Transactions on Intelligent Systems and Technology"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-030-51372-6_19","volume-title":"Graph Transformation","author":"McCreesh C.","year":"2020","unstructured":"C. McCreesh, P. Prosser, and J. Trimble. 2020. The Glasgow subgraph solver: Using constraint programming to tackle hard subgraph isomorphism problem variants. In Graph Transformation. F. Gadducci and T. Kehrer (Eds.), Springer International Publishing, Cham, 316\u2013324."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_3_2_32_2","first-page":"11","volume-title":"Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (Virtual Event) (GRADES-NDA \u201921)","author":"Mhedhbi A.","year":"2021","unstructured":"A. Mhedhbi, M. Lissandrini, L. Kuiper, J. Waudby, and G. Sz\u00e1rnyas. 2021. LSQB: A large-scale subgraph query benchmark. In Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (Virtual Event) (GRADES-NDA \u201921). ACM, New York, NY, Article 8, 11 pages. DOI: 10.1145\/3461837.3464516"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/028\/14"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.3390\/app13095770"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2021.3056329"},{"key":"e_1_3_2_36_2","first-page":"617","volume-title":"Proceedings of the VLDB Endowment","volume":"8","author":"Ren X.","year":"2015","unstructured":"X. Ren and J. Wang. 2015. Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. Proceedings of the VLDB Endowment 8, 5 (2015), 617\u2013628. DOI: 10.14778\/2735479.2735493"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0303-4"},{"key":"e_1_3_2_38_2","first-page":"364","volume-title":"Proceedings of the VLDB Endowment","volume":"1","author":"Shang H.","year":"2008","unstructured":"H. Shang, Y. Zhang, X. Lin, and J. X. Yu. 2008. Taming verification hardness: An efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment 1, 1 (2008), 364\u2013375. DOI: 10.14778\/1453856.1453899"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.05.002"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"1083","DOI":"10.1145\/3318464.3380581","volume-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201920)","author":"Sun S.","year":"2020","unstructured":"S. Sun and Q. Luo. 2020. In-memory subgraph matching: An in-depth study. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD \u201920). ACM, New York, NY, 1083\u20131098. DOI: 10.1145\/3318464.3380581"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0360-y"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1093\/database\/baab026"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1921702"},{"key":"e_1_3_2_45_2","first-page":"727","volume-title":"Proceedings of the On the Move to Meaningful Internet Systems (OTM \u201910)","author":"Vila\u00e7a R.","year":"2010","unstructured":"R. Vila\u00e7a, F. Cruz, and R. Oliveira. 2010. On the expressiveness and trade-offs of large scale tuple stores. In Proceedings of the On the Move to Meaningful Internet Systems (OTM \u201910). Springer, Berlin, 727\u2013744."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2023.3236028"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-009-9074-3"},{"key":"e_1_3_2_48_2","unstructured":"L. Zeng Y. Jiang W. Lu and L. Zou. 2021. Deep analysis on subgraph isomorphism. arXiv:2012.06802. Retrieved from http:\/\/arxiv.org\/abs\/2012.06802"},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/1516360.1516384","volume-title":"Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT \u201909)","author":"Zhang S.","year":"2009","unstructured":"S. Zhang, S. Li, and J. Yang. 2009. GADDI: Distance index based subgraph matching in biological networks. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT \u201909). ACM, New York, NY, 192\u2013203. DOI: 10.1145\/1516360.1516384"},{"key":"e_1_3_2_50_2","first-page":"340","volume-title":"Proceedings of the VLDB Endowment","volume":"3","author":"Zhao P.","year":"2010","unstructured":"P. Zhao and J. Han. 2010. On graph query optimization in large networks. Proceedings of the VLDB Endowment 3, 1\u20132 (2010), 340\u2013351. DOI: 10.14778\/1920841.1920887"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728361","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:36Z","timestamp":1750295916000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,22]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3728361"],"URL":"https:\/\/doi.org\/10.1145\/3728361","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,22]]},"assertion":[{"value":"2024-01-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}