{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:58:14Z","timestamp":1742972294690,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":45,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819997848"},{"type":"electronic","value":"9789819997855"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-99-9785-5_8","type":"book-chapter","created":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T18:02:05Z","timestamp":1706983325000},"page":"98-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Survey of\u00a0Privacy Preserving Subgraph Matching Methods"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-9385-575X","authenticated-orcid":false,"given":"Xingjiang","family":"Cheng","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9868-4774","authenticated-orcid":false,"given":"Fuxing","family":"Zhang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6358-2333","authenticated-orcid":false,"given":"Yun","family":"Peng","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3480-8780","authenticated-orcid":false,"given":"Xianmin","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7261-6398","authenticated-orcid":false,"given":"Teng","family":"Huang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0006-5299","authenticated-orcid":false,"given":"Ziye","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Duncan S.","family":"Wong","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8625-0275","authenticated-orcid":false,"given":"Changyu","family":"Dong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,4]]},"reference":[{"unstructured":"http:\/\/neo4j.org\/","key":"8_CR1"},{"doi-asserted-by":"crossref","unstructured":"Zou, L., Chen, L., \u00d6zsu, M.T.: K-automorphism: a general framework for privacy preserving network publication. In: VLDB (2009)","key":"8_CR2","DOI":"10.14778\/1687627.1687734"},{"doi-asserted-by":"crossref","unstructured":"Sweeney, L.: k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(05), 557\u2013570 (2002)","key":"8_CR3","DOI":"10.1142\/S0218488502001648"},{"doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: l-diversity: privacy beyond k-anonymity. In: ICDE, p. 24 (2006)","key":"8_CR4","DOI":"10.1109\/ICDE.2006.1"},{"doi-asserted-by":"crossref","unstructured":"Li, N., Li, T., Venkatasubramanian, S.: t-closeness: privacy beyond k-anonymity and l-diversity. In: ICDE, pp. 106\u2013115 (2007)","key":"8_CR5","DOI":"10.1109\/ICDE.2007.367856"},{"issue":"3","key":"8_CR6","first-page":"633","volume":"25","author":"M Yuan","year":"2013","unstructured":"Yuan, M., Chen, L., Philip, S.Y., Yu, T.: Protecting sensitive labels in social network data anonymization. TKDE 25(3), 633\u2013647 (2013)","journal-title":"TKDE"},{"issue":"8","key":"8_CR7","doi-asserted-by":"publisher","first-page":"2275","DOI":"10.1109\/TKDE.2015.2399292","volume":"27","author":"Z Fan","year":"2015","unstructured":"Fan, Z., Choi, B., Chen, Q., et al.: Structure-preserving subgraph query services. IEEE Trans. Knowl. Data Eng. 27(8), 2275\u20132290 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"unstructured":"https:\/\/tugraph.antgroup.com\/","key":"8_CR8"},{"issue":"2","key":"8_CR9","first-page":"1","volume":"1","author":"L Xu","year":"2023","unstructured":"Xu, L., Choi, B., Peng, Y., et al.: A framework for privacy preserving localized graph pattern query processing. Proc. ACM Manage. Data 1(2), 1\u201327 (2023)","journal-title":"Proc. ACM Manage. Data"},{"issue":"1","key":"8_CR10","first-page":"102","volume":"1","author":"M Hay","year":"2008","unstructured":"Hay, M., Miklau, G., Jensen, D., Towsley, D.F., Weis, P.: Resisting structural re-identification in anonymized social networks. PVLDB 1(1), 102\u2013114 (2008)","journal-title":"PVLDB"},{"doi-asserted-by":"crossref","unstructured":"Cao, N., Yang, Z., Wang, C., et al.: Privacy-preserving query over encrypted graph-structured data in cloud computing. In: 2011 31st International Conference on Distributed Computing Systems, pp. 393\u2013402. IEEE (2011)","key":"8_CR11","DOI":"10.1109\/ICDCS.2011.84"},{"issue":"2","key":"8_CR12","first-page":"133","volume":"6","author":"J Lee","year":"2012","unstructured":"Lee, J., Han, W., Kasperovics, R., Lee, J.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB 6(2), 133\u2013144 (2012)","journal-title":"PVLDB"},{"doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: SIGMOD, pp. 93\u2013106 (2008)","key":"8_CR13","DOI":"10.1145\/1376616.1376629"},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316\u2013329 (1998)","journal-title":"Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Wong, W.K., Cheung, D.W., Kao, B., Mamoulis, N.: Secure KNN computation on encrypted databases. In: Proceedings of SIGMOD (2009)","key":"8_CR15","DOI":"10.1145\/1559845.1559862"},{"doi-asserted-by":"crossref","unstructured":"Chang, Z., Zou, L., Li, F.: Privacy preserving subgraph matching on large graphs in cloud. In: Proceedings of ACM SIGMOD (2016)","key":"8_CR16","DOI":"10.1145\/2882903.2882956"},{"doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing cartesian products. In: SIGMOD, pp. 1199\u20131214 (2016)","key":"8_CR17","DOI":"10.1145\/2882903.2915236"},{"issue":"9","key":"8_CR18","first-page":"788","volume":"5","author":"Z Sun","year":"2012","unstructured":"Sun, Z., Wang, H., Wang, H., Shao, B., Li, J.: Efficient subgraph matching on billion node graphs. PVLDB 5(9), 788\u2013799 (2012)","journal-title":"PVLDB"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"3582","DOI":"10.1109\/TIFS.2022.3210881","volume":"17","author":"S Wang","year":"2022","unstructured":"Wang, S., Zheng, Y., Jia, X., et al.: OblivGM: oblivious attributed subgraph matching as a cloud service. IEEE Trans. Inf. Forensics Secur. 17, 3582\u20133596 (2022)","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"issue":"3","key":"8_CR20","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1109\/TKDE.2013.12","volume":"26","author":"C Tai","year":"2014","unstructured":"Tai, C., Tseng, P., Yu, P.S., Chen, M.: Identity protection in sequential releases of dynamic networks. IEEE Trans. Knowl. Data Eng. 26(3), 635\u2013651 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"doi-asserted-by":"crossref","unstructured":"Huang, K., Hu, H., Zhou, S., Guan, J., Ye, Q., Zhou, X.: Privacy and efficiency guaranteed social subgraph matching. The VLDB Journal, pp. 1\u201322 (2021)","key":"8_CR21","DOI":"10.1007\/s00778-021-00706-0"},{"doi-asserted-by":"crossref","unstructured":"Du, B., Zhang, S., Cao, N., Tong, H.: First: fast interactive attributed subgraph matching. In: SIGKDD, pp. 1447\u20131456. ACM (2017)","key":"8_CR22","DOI":"10.1145\/3097983.3098040"},{"issue":"2","key":"8_CR23","first-page":"176","volume":"11","author":"M Qiao","year":"2017","unstructured":"Qiao, M., Zhang, H., Cheng, H.: Subgraph matching: on compression and computation. PVLDB 11(2), 176\u2013188 (2017)","journal-title":"PVLDB"},{"doi-asserted-by":"crossref","unstructured":"Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In 2008 IEEE 24th International Conference on Data Engineering, pp. 506\u2013515 (2008)","key":"8_CR24","DOI":"10.1109\/ICDE.2008.4497459"},{"doi-asserted-by":"crossref","unstructured":"Tan, S., Knott, B., Tian, Y., Wu, D.J.: CryptGPU: fast privacypreserving machine learning on the GPU. In: Proceedings of IEEE S &P (2021)","key":"8_CR25","DOI":"10.1109\/SP40001.2021.00098"},{"doi-asserted-by":"crossref","unstructured":"Dauterman, E., Rathee, M., Popa, R.A., Stoica, I.: Waldo: a private time-series database from function secret sharing. In: Proceedings of IEEE S &P (2022)","key":"8_CR26","DOI":"10.1109\/SP46214.2022.9833611"},{"key":"8_CR27","first-page":"7341","volume":"35","author":"S Wang","year":"2022","unstructured":"Wang, S., Zheng, Y., Jia, X., Yi, X.: Privacy-preserving analytics on decentralized social graphs: The case of eigendecomposition. IEEE Trans. Knowl. Data Eng. 35, 7341\u20137356 (2022)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"doi-asserted-by":"crossref","unstructured":"Cheng, J., Fu, A.W.-c., Liu, J.: K-isomorphism: privacy preserving network publication against structural attacks. In: SIGMOD, pp. 459\u2013470 (2010)","key":"8_CR28","DOI":"10.1145\/1807167.1807218"},{"doi-asserted-by":"crossref","unstructured":"Wu, W., Xiao, Y., Wang, W., He, Z., Wang, Z.: K-symmetry model for identity anonymization in social networks. In: EDBT, p. 111122 (2010)","key":"8_CR29","DOI":"10.1145\/1739041.1739058"},{"key":"8_CR30","first-page":"108","volume":"35","author":"H Jiang","year":"2021","unstructured":"Jiang, H., Pei, J., Yu, D., et al.: Applications of differential privacy in social network analysis: a survey. IEEE Trans. Knowl. Data Eng. 35, 108\u2013127 (2021)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"doi-asserted-by":"crossref","unstructured":"Karypis, G., Kumar, V.: Analysis of multilevel graph partitioning. In: ICS, p. 29 (1995)","key":"8_CR31","DOI":"10.1145\/224170.224229"},{"doi-asserted-by":"crossref","unstructured":"Xu, J., Yi, P., Choi, B., et al.: Privacy-preserving reachability query services for massive networks. In: CIKM, pp. 145\u2013154 (2016)","key":"8_CR32","DOI":"10.1145\/2983323.2983799"},{"doi-asserted-by":"crossref","unstructured":"Hu, H., Xu, J., Chen, Q., et al.: Authenticating location-based services without compromising location privacy. In: SIGMOD, pp. 301\u2013312 (2012)","key":"8_CR33","DOI":"10.1145\/2213836.2213871"},{"key":"8_CR34","doi-asserted-by":"publisher","first-page":"3179","DOI":"10.1109\/TIFS.2022.3201392","volume":"17","author":"S Wang","year":"2022","unstructured":"Wang, S., Zheng, Y., Jia, X., et al.: PeGraph: a system for privacy-preserving and efficient search over encrypted social graphs. IEEE Trans. Inf. Forensics Secur. 17, 3179\u20133194 (2022)","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"doi-asserted-by":"crossref","unstructured":"Lai, S., Yuan, X., Sun, S.F., et al.: Graphse\u0161: an encrypted graph database for privacy-preserving social search. In: Asia CCS 2019: Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, pp. 41\u201354 (2019)","key":"8_CR35","DOI":"10.1145\/3321705.3329803"},{"doi-asserted-by":"crossref","unstructured":"Lindell, Y.: Secure multiparty computation (MPC). Cryptology ePrint Archive (2020)","key":"8_CR36","DOI":"10.1145\/3387108"},{"doi-asserted-by":"crossref","unstructured":"Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Proceedings of ACM CCS (2016)","key":"8_CR37","DOI":"10.1145\/2976749.2978331"},{"doi-asserted-by":"crossref","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Proceedings of EUROCRYPT (2015)","key":"8_CR38","DOI":"10.1145\/2976749.2978429"},{"doi-asserted-by":"crossref","unstructured":"Zou, L., Chen, L., \u00d6zsu, M.T.: Distancejoin: pattern match query in a large graph database. PVLDB 2(1), 886\u2013897 (2009)","key":"8_CR39","DOI":"10.14778\/1687627.1687727"},{"doi-asserted-by":"crossref","unstructured":"Chen, W., Popa, R.A.: Metal: a metadata-hiding file-sharing system. In: Proceedings of NDSS (2020)","key":"8_CR40","DOI":"10.14722\/ndss.2020.24095"},{"doi-asserted-by":"crossref","unstructured":"Sabt, M., Achemlal, M., Bouabdallah, A.: Trusted execution environment: what it is, and what it is not. In: 2015 IEEE Trustcom\/BigDataSE\/ISPA, pp. 57\u201364 (2015)","key":"8_CR41","DOI":"10.1109\/Trustcom.2015.357"},{"doi-asserted-by":"crossref","unstructured":"Araki, T., Furukawa, J., Ohara, K., Pinkas, B., Rosemarin, H., Tsuchida, H.: Secure graph analysis at scale. In: Proceedings of ACM CCS (2021)","key":"8_CR42","DOI":"10.1145\/3460120.3484560"},{"doi-asserted-by":"crossref","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of ACM CCS (2006)","key":"8_CR43","DOI":"10.1145\/1180405.1180417"},{"unstructured":"Costan, V., Devadas, S.: Intel SGX explained, Cryptology ePrint Archive (2016)","key":"8_CR44"},{"issue":"2","key":"8_CR45","first-page":"331","volume":"33","author":"X Ding","year":"2019","unstructured":"Ding, X., Wang, C., Choo, K.K.R., et al.: A novel privacy preserving framework for large scale graph data publishing. TKDE 33(2), 331\u2013343 (2019)","journal-title":"TKDE"}],"container-title":["Lecture Notes in Computer Science","Artificial Intelligence Security and Privacy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-99-9785-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,10]],"date-time":"2024-11-10T02:06:30Z","timestamp":1731204390000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-99-9785-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819997848","9789819997855"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-981-99-9785-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"4 February 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIS&P","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Artificial Intelligence Security and Privacy","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guangzhou","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ais&p2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/nsclab.org\/aisp2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"115","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23 large model and security workshop papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}