{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T05:55:21Z","timestamp":1781330121536,"version":"3.54.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"Natrual Science Foundation of China","award":["62272170"],"award-info":[{"award-number":["62272170"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    In many real-world applications such as social network analysis, knowledge graph discovery, biological network analytics, and so on, graph data management has become increasingly important and has drawn much attention from the database community. While many graphs (e.g., Twitter, Wikipedia, etc.) are usually evolving over time, it is of great importance to study the\n                    <jats:italic toggle=\"yes\">continuous subgraph matching<\/jats:italic>\n                    (CSM) problem, a fundamental, yet challenging, graph operator, which continuously monitors subgraph matching results over dynamic graphs with a stream of edge updates. To efficiently tackle the CSM problem, we carefully design a general CSM processing framework, based on novel\n                    <jats:italic toggle=\"yes\">DynamIc Vertex DomINance Embedding<\/jats:italic>\n                    (DIVINE), which maps vertex neighborhoods into an embedding space to enable efficient subgraph matching and incremental maintenance under dynamic updates. Inspired by low pruning power for high-degree vertices, we propose a new\n                    <jats:italic toggle=\"yes\">degree grouping<\/jats:italic>\n                    technique to decompose high-degree star patterns into groups of lower-degree star substructures, and devise\n                    <jats:italic toggle=\"yes\">degree-aware star substructure synopses<\/jats:italic>\n                    (DAS\n                    <jats:sup>3<\/jats:sup>\n                    ) over embeddings of star substructure groups. We develop efficient algorithms to incrementally maintain dynamic graphs and answer CSM queries by traversing DAS\n                    <jats:sup>3<\/jats:sup>\n                    synopses and applying our designed\n                    <jats:italic toggle=\"yes\">vertex dominance<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">range pruning strategies.<\/jats:italic>\n                    Through extensive experiments, we confirm the efficiency of our proposed DIVINE approach over both real and synthetic graphs.\n                  <\/jats:p>","DOI":"10.1145\/3769774","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6874-5741","authenticated-orcid":false,"given":"Yutong","family":"Ye","sequence":"first","affiliation":[{"name":"East China Normal University, Shanghai, China and Kent State University, Kent, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7681-3807","authenticated-orcid":false,"given":"Xiang","family":"Lian","sequence":"additional","affiliation":[{"name":"Kent State University, Kent, OH, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1392-8689","authenticated-orcid":false,"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3922-0989","authenticated-orcid":false,"given":"Mingsong","family":"Chen","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3004153"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19212-9_2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290967"},{"key":"e_1_2_1_5_1","first-page":"509","volume-title":"Science","volume":"286","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science, Vol. 286, 5439 (1999), 509-512."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0503-60"},{"key":"e_1_2_1_7_1","volume-title":"Proc. of the International Conference on Very Large Data Bases (PVLDB). 28-39","author":"Berchtold Stefan","year":"1996","unstructured":"Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel. 1996. The X-tree: An Index Structure for High-Dimensional Data. In Proc. of the International Conference on Very Large Data Bases (PVLDB). 28-39."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914855"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.67"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559907"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of the International Conference on Extending Database Technology (EDBT). 157-168","author":"Choudhury Sutanay","year":"2015","unstructured":"Sutanay Choudhury, Lawrence Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A selectivity based approach to continuous pattern detection in streaming graphs. In Proc. of the International Conference on Extending Database Technology (EDBT). 157-168."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198515906.001.0001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446097"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of the International Conference on Data Engineering (ICDE). 1316-1319","author":"Fan Wenfei","year":"2013","unstructured":"Wenfei Fan, Xin Wang, and Yinghui Wu. 2013a. Expfinder: Finding experts by graph pattern matching. In Proc. of the International Conference on Data Engineering (ICDE). 1316-1319."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_21_1","first-page":"498","article-title":"Computers and intractability: A guide to the theory of NP-completeness","volume":"48","author":"Garey Michael R.","year":"1983","unstructured":"Michael R. Garey and David S. Johnson. 1983. Computers and intractability: A guide to the theory of NP-completeness. The Journal of Symbolic Logic, Vol. 48, 2 (1983), 498-500.","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372123"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/615204.615206"},{"key":"e_1_2_1_25_1","volume-title":"Networkx: Network analysis with python. URL: https:\/\/networkx. github. io","author":"Hagberg Aric","year":"2020","unstructured":"Aric Hagberg and Drew Conway. 2020. Networkx: Network analysis with python. URL: https:\/\/networkx. github. io (2020)."},{"key":"e_1_2_1_26_1","first-page":"1025","article-title":"Inductive representation learning on large graphs","volume":"30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Proc. of the Advances in Neural Information Processing Systems (NeurIPS), Vol. 30 (2017), 1025-1035.","journal-title":"Proc. of the Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_28_1","volume-title":"Proc. of the International Conference on Management of Data (SIGMOD). 337-348","author":"Han Wook-Shin","year":"2013","unstructured":"Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proc. of the International Conference on Management of Data (SIGMOD). 337-348."},{"key":"e_1_2_1_29_1","first-page":"1700","article-title":"Ks-gnn: Keywords search over incomplete graphs via graphs neural network","author":"Hao Yu","year":"2021","unstructured":"Yu Hao, Xin Cao, Yufan Sheng, Yixiang Fang, and Wei Wang. 2021. Ks-gnn: Keywords search over incomplete graphs via graphs neural network. In Proc. of the Advances in Neural Information Processing Systems (NeurIPS). 1700-1712.","journal-title":"Proc. of the Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.141"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492576"},{"key":"e_1_2_1_33_1","volume-title":"Able: Meta-path prediction in heterogeneous information networks. ACM Transactions on Knowledge Discovery from Data","author":"Huang Chenji","year":"2022","unstructured":"Chenji Huang, Yixiang Fang, Xuemin Lin, Xin Cao, and Wenjie Zhang. 2022. Able: Meta-path prediction in heterogeneous information networks. ACM Transactions on Knowledge Discovery from Data, Vol. 16, 4 (2022), 1-21."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599483"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrm2503"},{"key":"e_1_2_1_40_1","volume-title":"Proc. of the International Conference on Extending Database Technology (EDBT). 25-36","author":"Katsarou Foteini","year":"2017","unstructured":"Foteini Katsarou, Nikos Ntarmos, and Peter Triantafillou. 2017. Subgraph querying with parallel use of query rewritings and alternative algorithms. In Proc. of the International Conference on Extending Database Technology (EDBT). 25-36."},{"key":"e_1_2_1_41_1","volume-title":"Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong.","author":"Kim Kyoungmin","year":"2018","unstructured":"Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018. Turboflux: A fast continuous subgraph matching system for streaming graph data. In Proc. of the International Conference on Management of Data (SIGMOD). 411-426."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_43_1","volume-title":"Proc. of the International Conference on Machine Learning (ICML). 3835-3845","author":"Li Yujia","year":"2019","unstructured":"Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. 2019. Graph matching networks for learning the similarity of graph structured objects. In Proc. of the International Conference on Machine Learning (ICML). 3835-3845."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457395"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933267.2933316"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554869"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3372716.3372720"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3243177"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098061"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735504"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i8.28754"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i4.20333"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457290"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523218"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gku1003"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939753"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00900-8"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00878-3"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/183"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. (1994).","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_69_1","first-page":"440","volume-title":"Nature","volume":"393","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world'networks. Nature, Vol. 393, 6684 (1998), 440-442."},{"key":"e_1_2_1_70_1","volume-title":"Central Limit Theorem. https:\/\/en.wikipedia.org\/wiki\/Central_limit_theorem","year":"2023","unstructured":"Wikipedia. 2023. Central Limit Theorem. https:\/\/en.wikipedia.org\/wiki\/Central_limit_theorem (2023)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00058"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/3654621.3654630"},{"key":"e_1_2_1_73_1","unstructured":"Yutong Ye Xiang Lian Nan Zhang and Mingsong Chen. 2024b. Dynamic Subgraph Matching via Cost-Model-based Vertex Dominance Embeddings (Technical Report). arXiv:2407.16660 [cs.DB] https:\/\/arxiv.org\/abs\/2407.16660"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517875"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0337-7"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:55:39Z","timestamp":1781326539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":76,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769774"],"URL":"https:\/\/doi.org\/10.1145\/3769774","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}