{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:34:23Z","timestamp":1767832463328,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"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","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Symmetry, a phenomenon of self-similarity, is common in many networks, which often incurs a lot of redundant accesses and computations, even duplicate results when executing graph matching tasks. Many approaches (e.g. symmetry-breaking methods) try to disrupt symmetry by translating symmetry into restrictions and then imposing restrictions on the exploration order. However, the restrictions are finer-grained. If the pattern graph is complex, more restrictions are generated from symmetry breaking methods, thus complicating the exploration process and degrading the performance. Here, we present novel SymmPi, which exploits symmetry removal for fast graph matching. SymmPi first identifies the coarse-grained axisymmetric subgraphs of the given pattern graphs instead of finer relationships. If a pattern graph is not axisymmetric, SymmPi will remove some of its edges until axisymmetric subgraphs are found. Thus, the original pattern graph is transformed to a set of axisymmetric subgraphs plus some edges. Then, SymmPi finds the matches of the axisymmetric subgraph and extends these matches to the original pattern graphs by permuting the matches with additional checks. Our experiments on both directed and undirected graphs, demonstrate that SymmPi achieves a significant performance improvement over the state-of-the-art undirected and directed graph matching methods and systems.<\/jats:p>","DOI":"10.1007\/s41019-024-00271-w","type":"journal-article","created":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T08:35:32Z","timestamp":1736930132000},"page":"230-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["SymmPi: Exploiting Symmetry Removal for Fast Subgraph Matching"],"prefix":"10.1007","volume":"10","author":[{"given":"Yujiang","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Cao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhaobo","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1656-5634","authenticated-orcid":false,"given":"Pingpeng","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,15]]},"reference":[{"issue":"1","key":"271_CR1","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1111\/1365-2656.13356","volume":"90","author":"GF Albery","year":"2021","unstructured":"Albery GF, Kirkpatrick L, Firth JA, Bansal S (2021) Unifying spatial and social network analysis in disease ecology. J Anim Ecol 90(1):45\u201361","journal-title":"J Anim Ecol"},{"key":"271_CR2","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ins.2020.10.057","volume":"551","author":"X Zhao","year":"2021","unstructured":"Zhao X, Liang J, Wang J (2021) A community detection algorithm based on graph compression for large-scale social networks. Inf Sci 551:358\u2013372","journal-title":"Inf Sci"},{"issue":"1","key":"271_CR3","first-page":"1","volume":"21","author":"Q Zou","year":"2020","unstructured":"Zou Q, Lin G, Jiang X, Liu X, Zeng X (2020) Sequence clustering in bioinformatics: an empirical study. Brief Bioinform 21(1):1\u201310","journal-title":"Brief Bioinform"},{"issue":"3","key":"271_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3474379","volume":"40","author":"G Zhang","year":"2022","unstructured":"Zhang G, Li Z, Huang J, Wu J, Zhou C, Yang J, Gao J (2022) efraudcom: an e-commerce fraud detection system via competitive graph neural networks. ACM Trans. Inf. Syst. 40(3):1\u201329","journal-title":"ACM Trans. Inf. Syst."},{"issue":"4","key":"271_CR5","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s41019-022-00198-0","volume":"7","author":"T Sun","year":"2022","unstructured":"Sun T, Xu J, Hu C (2022) An efficient algorithm of star subgraph queries on urban traffic knowledge graph. Data Sci. Eng. 7(4):383\u2013401","journal-title":"Data Sci. Eng."},{"key":"271_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.ins.2016.01.074","volume":"346\u2013347","author":"F Emmert-Streib","year":"2016","unstructured":"Emmert-Streib F, Dehmer M, Shi Y (2016) Fifty years of graph matching, network alignment and network comparison. Inf Sci 346\u2013347:180\u2013197. https:\/\/doi.org\/10.1016\/j.ins.2016.01.074","journal-title":"Inf Sci"},{"key":"271_CR7","doi-asserted-by":"publisher","DOI":"10.1145\/3639315","author":"Z Zhang","year":"2024","unstructured":"Zhang Z, Lu Y, Zheng W, Lin X (2024) A comprehensive survey and experimental study of subgraph matching: trends, unbiasedness, and interaction. Proc ACM Manag Data. https:\/\/doi.org\/10.1145\/3639315","journal-title":"Proc ACM Manag Data"},{"key":"271_CR8","doi-asserted-by":"crossref","unstructured":"Sun S, Luo Q(2020) In-memory subgraph matching: an in-depth study. In: Proceedings of the 2020 ACM SIGMOD international conference on management of data. SIGMOD \u201920, pp. 1083\u20131098. ACM, New York, NY, USA","DOI":"10.1145\/3318464.3380581"},{"key":"271_CR9","unstructured":"Teixeira CH, Fonseca AJ, Serafini M, Siganos G, Zaki MJ, Aboulnaga A Arabesque: a system for distributed graph mining. In: SOSP\u201915, pp. 425\u2013440"},{"key":"271_CR10","unstructured":"Wang K, Zuo Z, Thorpe J, Nguyen TQ, Xu GH (2018) Rstream: Marrying relational algebra with streaming for efficient graph mining on a single machine. In: OSDI\u201918, pp. 763\u2013782"},{"key":"271_CR11","unstructured":"Dias V, Teixeira CH, Guedes D, Meira W, Parthasarathy S Fractal: a general-purpose graph pattern mining system. In: SIGMOD\u201919, pp. 1357\u20131374"},{"key":"271_CR12","doi-asserted-by":"crossref","unstructured":"Chen H, Liu M, Zhao Y, Yan X, Yan D, Cheng J (2018) G-miner: an efficient task-oriented graph mining system. In: EuroSys\u201918, pp. 1\u201312","DOI":"10.1145\/3190508.3190545"},{"key":"271_CR13","doi-asserted-by":"crossref","unstructured":"Mawhirter D, Wu B (2019) Automine: harmonizing high-level abstraction and high performance for graph mining. In: SOSP\u201919, pp. 509\u2013523","DOI":"10.1145\/3341301.3359633"},{"issue":"1","key":"271_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s41019-019-0090-z","volume":"4","author":"X Wang","year":"2019","unstructured":"Wang X, Chai L, Xu Q, Yang Y, Li J, Wang J, Chai Y (2019) Efficient subgraph matching on large RDF graphs using mapreduce. Data Sci. Eng. 4(1):24\u201343","journal-title":"Data Sci. Eng."},{"key":"271_CR15","doi-asserted-by":"crossref","unstructured":"Shi T, Zhai M, Xu Y, Zhai J Graphpi: High performance graph pattern matching through effective redundancy elimination. In: SC\u201920, pp. 1\u201314. IEEE","DOI":"10.1109\/SC41405.2020.00104"},{"key":"271_CR16","doi-asserted-by":"crossref","unstructured":"Jamshidi K, Mahadasa R, Vora K (2020) Peregrine: a pattern-aware graph mining system. In: EuroSys\u201920, pp. 1\u201316","DOI":"10.1145\/3342195.3387548"},{"key":"271_CR17","unstructured":"Mawhirter D, Reinehr S, Holmes C, Liu T, Wu B (2019) Graphzero: breaking symmetry for efficient graph mining. arXiv preprint arXiv:1911.12877"},{"key":"271_CR18","unstructured":"Gui C, Liao X, Zheng L, Jin H (2023) Cyclosa: redundancy-free graph pattern mining via set dataflow. In: USENIX ATC 23, pp. 71\u201385"},{"key":"271_CR19","doi-asserted-by":"crossref","unstructured":"Gui C, Liao X, Zheng L, Yao P, Wang Q, Jin H Sumpa: efficient pattern-centric graph mining with pattern abstraction. In: PACT\u201921, pp. 318\u2013330. IEEE","DOI":"10.1109\/PACT52795.2021.00030"},{"key":"271_CR20","unstructured":"Han W-S, Lee J, Lee J-H (2013) Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD\u201913, pp. 337\u2013348"},{"key":"271_CR21","doi-asserted-by":"crossref","unstructured":"Che J, Jamshidi K, Vora K (2024) Contigra: graph mining with containment constraints. In: Proceedings of the 19th European conference on computer systems. EuroSys \u201924, pp. 50\u201365. ACM, New York, NY, USA","DOI":"10.1145\/3627703.3629589"},{"key":"271_CR22","doi-asserted-by":"crossref","unstructured":"Jiang Z, Zhang S, Hou X, Yuan M, You H (2024) Ive: accelerating enumeration-based subgraph matching via exploring isolated vertices. In: 2024 IEEE 40th International conference on data engineering (ICDE), pp. 4208\u20134221","DOI":"10.1109\/ICDE60146.2024.00321"},{"key":"271_CR23","doi-asserted-by":"crossref","unstructured":"Cao H, Wang Q, Li X, Najafi M, Chang KC, Cheng R(2024) Large subgraph matching: a comprehensive and efficient approach for heterogeneous graphs. In: 2024 IEEE 40th International conference on data engineering (ICDE), pp. 2972\u20132985","DOI":"10.1109\/ICDE60146.2024.00231"},{"key":"271_CR24","doi-asserted-by":"crossref","unstructured":"Kim H, Choi Y, Park K, Lin X, Hong S-H, Han W-S (2021) Versatile equivalences: speeding up subgraph query processing and subgraph matching. In: SIGMOD\u201921, pp. 925\u2013937","DOI":"10.1145\/3448016.3457265"},{"issue":"2","key":"271_CR25","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00778-022-00749-x","volume":"32","author":"H Kim","year":"2023","unstructured":"Kim H, Choi Y, Park K, Lin X, Hong S, Han W (2023) Fast subgraph query processing and subgraph matching via static and dynamic equivalences. VLDB J 32(2):343\u2013368","journal-title":"VLDB J"},{"issue":"5","key":"271_CR26","doi-asserted-by":"publisher","first-page":"97896","DOI":"10.1371\/journal.pone.0097896","volume":"9","author":"M Houbraken","year":"2014","unstructured":"Houbraken M, Demeyer S, Michoel T, Audenaert P, Colle D, Pickavet M (2014) The index-based subgraph matching algorithm with general symmetries (ismags): exploiting symmetry for faster subgraph enumeration. PLoS ONE 9(5):97896","journal-title":"PLoS ONE"},{"key":"271_CR27","doi-asserted-by":"crossref","unstructured":"Bi F, Chang L, Lin X, Qin L, Zhang W (2016) Efficient subgraph matching by postponing cartesian products. In: SIGMOD\u201916, pp. 1199\u20131214","DOI":"10.1145\/2882903.2915236"},{"key":"271_CR28","doi-asserted-by":"crossref","unstructured":"Han M, Kim H, Gu G, Park K, Han W-S(2019) Efficient subgraph matching: harmonizing dynamic programming, adaptive matching order, and failing set together. In: SIGMOD\u201919, pp. 1429\u20131446","DOI":"10.1145\/3299869.3319880"},{"issue":"1","key":"271_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann JR (1976) An algorithm for subgraph isomorphism. J ACM (JACM) 23(1):31\u201342","journal-title":"J ACM (JACM)"},{"key":"271_CR30","doi-asserted-by":"crossref","unstructured":"Mhedhbi A, Salihoglu S (2019) Optimizing subgraph queries by combining binary and worst-case optimal joins. arXiv preprint arXiv:1903.02076","DOI":"10.14778\/3342263.3342643"},{"issue":"2","key":"271_CR31","doi-asserted-by":"publisher","first-page":"176","DOI":"10.14778\/3425879.3425888","volume":"14","author":"S Sun","year":"2020","unstructured":"Sun S, Sun X, Che Y, Luo Q, He B (2020) Rapidmatch: a holistic approach to subgraph query processing. Proc VLDB Endow 14(2):176\u2013188","journal-title":"Proc VLDB Endow"},{"key":"271_CR32","doi-asserted-by":"crossref","unstructured":"Kim J, Han W-S, Lee S, Park K, Yu H (2014) Opt: a new framework for overlapped and parallel triangulation in large-scale graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data (SIGMOD \u201914), pp. 637\u2013648. ACM, New York, NY, USA","DOI":"10.1145\/2588555.2588563"},{"key":"271_CR33","doi-asserted-by":"crossref","unstructured":"Kim H, Lee J, Bhowmick SS, Han, W-S, Lee J, Ko S, Jarrah MHA (2016) Dualsim: Parallel subgraph enumeration in a massive graph on a single machine. In: Proceedings of the 2016 international conference on management of data (SIGMOD \u201916), pp. 1231\u2013245. ACM, New York, NY, USA","DOI":"10.1145\/2882903.2915209"},{"key":"271_CR34","doi-asserted-by":"crossref","unstructured":"Zhao C, Zhang Z, Xu P, Zheng T, Guo J (2020) Kaleido: an efficient out-of-core graph mining system on A single machine. In: Proceedings of the 36th IEEE international conference on data engineering (ICDE 2020), pp. 673\u2013684. IEEE","DOI":"10.1109\/ICDE48307.2020.00064"},{"issue":"4","key":"271_CR35","doi-asserted-by":"publisher","first-page":"1846","DOI":"10.1109\/TNSE.2023.3236028","volume":"10","author":"D Yang","year":"2023","unstructured":"Yang D, Ge Y, Nguyen T, Molitor D, Moorman JD, Bertozzi AL (2023) Structural equivalence in subgraph matching. IEEE Trans Netw Sci Eng 10(4):1846\u20131862","journal-title":"IEEE Trans Netw Sci Eng"},{"key":"271_CR36","unstructured":"SNAP: SNAP datasets. http:\/\/snap.stanford.edu\/data\/index.html"},{"key":"271_CR37","unstructured":"Lab LI . UNIMI legal informatics lab. https:\/\/law.di.unimi.it\/index.php"},{"key":"271_CR38","doi-asserted-by":"crossref","unstructured":"Yang Z, Lai L, Lin X, Hao K, Zhang W (2021) Huge: An efficient and scalable subgraph enumeration system. In: SIGMOD\u201921, pp. 2049\u20132062","DOI":"10.1145\/3448016.3457237"},{"key":"271_CR39","doi-asserted-by":"publisher","DOI":"10.1145\/3639315","author":"Z Zhang","year":"2024","unstructured":"Zhang Z, Lu Y, Zheng W, Lin X (2024) A comprehensive survey and experimental study of subgraph matching Trends, unbiasedness, and interaction. Proc ACM Manag Data. https:\/\/doi.org\/10.1145\/3639315","journal-title":"Proc ACM Manag Data"},{"key":"271_CR40","doi-asserted-by":"crossref","unstructured":"Bindschaedler L, Malicevic J, Lepers B, Goel A, Zwaenepoel W (2021) Tesseract: distributed, general graph pattern mining on evolving graphs. In: EuroSys\u201921, pp. 458\u2013473","DOI":"10.1145\/3447786.3456253"},{"key":"271_CR41","doi-asserted-by":"crossref","unstructured":"Chen X, Dathathri R, Gill G, Hoang L, Pingali K (2021) Sandslash: a two-level framework for efficient graph pattern mining. In: ICS\u201921, pp. 378\u2013391","DOI":"10.1145\/3447818.3460359"},{"issue":"2","key":"271_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3446980","volume":"46","author":"A Mhedhbi","year":"2021","unstructured":"Mhedhbi A, Kankanamge C, Salihoglu S (2021) Optimizing one-time and continuous subgraph queries using worst-case optimal joins. ACM Trans Database Syst 46(2):1\u201345","journal-title":"ACM Trans Database Syst"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00271-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-024-00271-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-024-00271-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T08:58:04Z","timestamp":1749200284000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-024-00271-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["271"],"URL":"https:\/\/doi.org\/10.1007\/s41019-024-00271-w","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,15]]},"assertion":[{"value":"1 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}