{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T07:23:18Z","timestamp":1763018598798,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Graph data are widely collected and exploited by organizations, providing convenient services from policy formation and market decisions to medical care and social interactions. Yet, recent exposures of private data abuses have caused huge financial and reputational costs to both organizations and their users, enabling designing efficient privacy protection mechanisms a top priority. Local differential privacy (LDP) is an emerging privacy preservation standard and has been studied in various fields, including graph data aggregation. However, existing research studies of graph aggregation with LDP mainly provide single edge privacy for pure graph, leaving heterogeneous graph data aggregation with stronger privacy as an open challenge. In this paper, we take a step toward simultaneously collecting mixed attributed graph data while retaining intrinsic associations, with stronger local differential privacy protecting more than single edge. Specifically, we first propose a moderate granularity attributewise local differential privacy (ALDP) and formulate the problem of aggregating mixed attributed graph data as collecting two statistics under ALDP. Then we provide mechanisms to privately collect these statistics. For the categorical-attributed graph, we devise a utility-improved PrivAG mechanism, which randomizes and aggregates subsets of attribute and degree vectors. For heterogeneous graph, we present an adaptive binning scheme (ABS) to dynamically segment and simultaneously collect mixed attributed data, and extend the prior mechanism to a generalized PrivHG mechanism based on it. Finally, we practically optimize the utility of the mechanisms by reducing the computation costs and estimation errors. The effectiveness and efficiency of the mechanisms are validated through extensive experiments, and better performance is shown compared with the state-of-the-art mechanisms.<\/jats:p>","DOI":"10.3390\/e25010130","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T07:28:10Z","timestamp":1673249290000},"page":"130","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization"],"prefix":"10.3390","volume":"25","author":[{"given":"Zichun","family":"Liu","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liusheng","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongli","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,9]]},"reference":[{"unstructured":"(2021, January 12). Marketing Firm Exactis Leaked a Personal Info Database with 340 Million Records. Available online: https:\/\/www.wired.com\/story\/exactis-database-leak-340-million-records\/.","key":"ref_1"},{"unstructured":"(2021, January 12). Facebook Security Breach Exposes Accounts of 50 Million Users. Available online: https:\/\/www.nytimes.com\/2018\/09\/28\/technology\/facebook-hack-data-breach.html.","key":"ref_2"},{"unstructured":"(2021, January 12). Marriott Hacking Exposes Data of Up to 500 Million Guests. Available online: https:\/\/www.nytimes.com\/2018\/11\/30\/business\/marriott-data-breach.html.","key":"ref_3"},{"key":"ref_4","first-page":"10","article-title":"The eu general data protection regulation (gdpr)","volume":"Volume 10","author":"Voigt","year":"2017","journal-title":"A Practical Guide"},{"unstructured":"Goldman, E. (2021, January 12). An Introduction to the California Consumer Privacy Act (CCPA). Santa Clara Univ. Legal Studies Research Paper 2020. Available online: https:\/\/ssrn.com\/abstract=3211013.","key":"ref_5"},{"doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., and Smith, A.D. (2006, January 4\u20137). Calibrating Noise to Sensitivity in Private Data Analysis. Proceedings of the TCC, New York, NY, USA.","key":"ref_6","DOI":"10.1007\/11681878_14"},{"doi-asserted-by":"crossref","unstructured":"McSherry, F., and Talwar, K. (2007, January 21\u201323). Mechanism Design via Differential Privacy. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907), Providence, RI, USA.","key":"ref_7","DOI":"10.1109\/FOCS.2007.66"},{"doi-asserted-by":"crossref","unstructured":"Duchi, J.C., Jordan, M.I., and Wainwright, M.J. (2013, January 2\u20134). Local privacy and statistical minimax rates. Proceedings of the 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","key":"ref_8","DOI":"10.1109\/Allerton.2013.6736718"},{"unstructured":"(2021, January 12). Learning with Privacy at Scale. Available online: https:\/\/machinelearning.apple.com\/research\/learning-with-privacy-at-scale.","key":"ref_9"},{"unstructured":"Tang, J., Korolova, A., Bai, X., Wang, X., and Wang, X. (2017). Privacy loss in apple\u2019s implementation of differential privacy on macos 10.12. arXiv.","key":"ref_10"},{"doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Korolova, A., and Pihur, V. (2014). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. arXiv.","key":"ref_11","DOI":"10.1145\/2660267.2660348"},{"doi-asserted-by":"crossref","unstructured":"Fanti, G., Pihur, V., and Erlingsson, \u00da. (2015). Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries. arXiv.","key":"ref_12","DOI":"10.1515\/popets-2016-0015"},{"key":"ref_13","first-page":"3574","article-title":"Collecting telemetry data privately","volume":"30","author":"Ding","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"unstructured":"Kairouz, P., Bonawitz, K., and Ramage, D. (2016, January 20\u201322). Discrete distribution estimation under local privacy. Proceedings of the International Conference on Machine Learning, PMLR, New York, NY, USA.","key":"ref_14"},{"doi-asserted-by":"crossref","unstructured":"Li, C., Hay, M., Miklau, G., and Wang, Y. (2014). A data-and workload-aware algorithm for range queries under differential privacy. arXiv.","key":"ref_15","DOI":"10.14778\/2732269.2732271"},{"key":"ref_16","first-page":"492","article-title":"Extremal mechanisms for local differential privacy","volume":"27","author":"Kairouz","year":"2014","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1080\/01621459.2017.1389735","article-title":"Minimax optimal procedures for locally private estimation","volume":"113","author":"Duchi","year":"2018","journal-title":"J. Am. Stat. Assoc."},{"unstructured":"Nguy\u00ean, T.T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., and Shin, J. (2016). Collecting and analyzing data from smart device users with local differential privacy. arXiv.","key":"ref_18"},{"doi-asserted-by":"crossref","unstructured":"Wang, S., Huang, L., Nie, Y., Wang, P., Xu, H., and Yang, W. (2018, January 15\u201319). PrivSet: Set-Valued Data Analyses with Locale Differential Privacy. Proceedings of the IEEE INFOCOM 2018\u2014IEEE Conference on Computer Communications, Honolulu, HI, USA.","key":"ref_19","DOI":"10.1109\/INFOCOM.2018.8486234"},{"doi-asserted-by":"crossref","unstructured":"Qin, Z., Yang, Y., Yu, T., Khalil, I.M., Xiao, X., and Ren, K. (2016, January 24\u201328). Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","key":"ref_20","DOI":"10.1145\/2976749.2978409"},{"doi-asserted-by":"crossref","unstructured":"Wang, T., Li, N., and Jha, S. (2018, January 20\u201324). Locally Differentially Private Frequent Itemset Mining. Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.","key":"ref_21","DOI":"10.1109\/SP.2018.00035"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2151","DOI":"10.1109\/TIFS.2018.2812146","article-title":"LoPub: High-dimensional crowdsourced data publication with local differential privacy","volume":"13","author":"Ren","year":"2018","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"doi-asserted-by":"crossref","unstructured":"Wang, N., Xiao, X., Yang, Y., Zhao, J., Hui, S.C., Shin, H., Shin, J., and Yu, G. (2019, January 8\u201311). Collecting and analyzing multidimensional data with local differential privacy. Proceedings of the 2019 IEEE 35th International Conference on Data Engineering (ICDE), Macao, China.","key":"ref_23","DOI":"10.1109\/ICDE.2019.00063"},{"doi-asserted-by":"crossref","unstructured":"Ye, Q., Hu, H., Meng, X., and Zheng, H. (2019, January 19\u201323). PrivKV: Key-Value Data Collection with Local Differential Privacy. Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.","key":"ref_24","DOI":"10.1109\/SP.2019.00018"},{"unstructured":"Gu, X., Li, M., Cheng, Y., Xiong, L., and Cao, Y. (2020, January 12\u201314). {PCKV}: Locally Differentially Private Correlated {Key-Value} Data Collection with Optimized Utility. Proceedings of the 29th USENIX Security Symposium (USENIX Security 20), Boston, MA, USA.","key":"ref_25"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","article-title":"Defining and evaluating network communities based on ground-truth","volume":"42","author":"Yang","year":"2015","journal-title":"Knowl. Inf. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1109\/TMC.2014.2322373","article-title":"Friendbook: A Semantic-Based Friend Recommendation System for Social Networks","volume":"14","author":"Wang","year":"2015","journal-title":"IEEE Trans. Mob. Comput."},{"doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., and Wang, Y. (2010, January 24\u201328). Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","key":"ref_28","DOI":"10.1145\/1835804.1835934"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jbi.2016.05.005","article-title":"Using online social networks to track a pandemic: A systematic review","volume":"62","author":"Khan","year":"2016","journal-title":"J. Biomed. Inform."},{"unstructured":"Qin, Z., Yu, T., Yang, Y., Khalil, I.M., Xiao, X., and Ren, K. (November, January 30). Generating Synthetic Decentralized Social Graphs with Local Differential Privacy. Proceedings of the ACM Conference on Computer and Communications Security, Dallas, TX, USA.","key":"ref_30"},{"doi-asserted-by":"crossref","unstructured":"Sun, H., Xiao, X., Khalil, I., Yang, Y., Qin, Z., Wang, H., and Yu, T. (2019, January 11\u201315). Analyzing subgraph statistics from extended local views with decentralized differential privacy. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.","key":"ref_31","DOI":"10.1145\/3319535.3354253"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"3239","DOI":"10.1109\/TIFS.2020.2985524","article-title":"AsgLDP: Collecting and Generating Decentralized Attributed Graphs With Local Differential Privacy","volume":"15","author":"Wei","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/01621459.1965.10480775","article-title":"Randomized response: A survey technique for eliminating evasive answer bias","volume":"60","author":"Warner","year":"1965","journal-title":"J. Am. Stat. Assoc."},{"unstructured":"Wang, T., Blocki, J., Li, N., and Jha, S. (2017, January 16\u201318). Locally Differentially Private Protocols for Frequency Estimation. Proceedings of the USENIX Security Symposium, Vancouver, BC, Canada.","key":"ref_34"},{"doi-asserted-by":"crossref","unstructured":"Zhang, Z., Wang, T., Li, N., He, S., and Chen, J. (2018, January 15\u201319). CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada.","key":"ref_35","DOI":"10.1145\/3243734.3243742"},{"doi-asserted-by":"crossref","unstructured":"Ye, Q., Hu, H., Au, M., Meng, X., and Xiao, X. (2020, January 20\u201324). Towards Locally Differentially Private Generic Graph Metric Estimation. Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE), Dallas, TX, USA.","key":"ref_36","DOI":"10.1109\/ICDE48307.2020.00204"},{"doi-asserted-by":"crossref","unstructured":"Liu, Z., Xu, H., Huang, L., and Yang, W. (2021, January 25\u201327). Estimating Clustering Coefficient of Multiplex Graphs with Local Differential Privacy. Proceedings of the WASA, Nanjing, China.","key":"ref_37","DOI":"10.1007\/978-3-030-86137-7_42"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random Graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Statist."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/3187009.3177733","article-title":"Towards practical differential privacy for SQL queries","volume":"11","author":"Johnson","year":"2018","journal-title":"Proc. Vldb Endow."},{"unstructured":"Raskhodnikova, S., Smith, A., Lee, H.K., Nissim, K., and Kasiviswanathan, S.P. (2013, January 26\u201329). What can we learn privately. Proceedings of the 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","key":"ref_40"},{"doi-asserted-by":"crossref","unstructured":"Pastore, A., and Gastpar, M. (2016, January 10\u201315). Locally differentially-private distribution estimation. Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","key":"ref_41","DOI":"10.1109\/ISIT.2016.7541788"},{"doi-asserted-by":"crossref","unstructured":"Bassily, R., and Smith, A. (2015, January 14\u201317). Local, private, efficient protocols for succinct histograms. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","key":"ref_42","DOI":"10.1145\/2746539.2746632"},{"doi-asserted-by":"crossref","unstructured":"Chen, R., Li, H., Qin, A.K., Kasiviswanathan, S.P., and Jin, H. (2016, January 16\u201320). Private spatial data aggregation in the local setting. Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, Finland.","key":"ref_43","DOI":"10.1109\/ICDE.2016.7498248"},{"doi-asserted-by":"crossref","unstructured":"Li, Z., Wang, T., Lopuha\u00e4-Zwakenberg, M., Li, N., and \u0160koric, B. (2020, January 14\u201319). Estimating numerical distributions under local differential privacy. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, OR, USA.","key":"ref_44","DOI":"10.1145\/3318464.3389700"},{"doi-asserted-by":"crossref","unstructured":"Du, L., Zhang, Z., Bai, S., Liu, C., Ji, S., Cheng, P., and Chen, J. (2021, January 15\u201319). AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual.","key":"ref_45","DOI":"10.1145\/3460120.3485668"},{"doi-asserted-by":"crossref","unstructured":"Hay, M., Li, C., Miklau, G., and Jensen, D.D. (2009, January 6\u20139). Accurate Estimation of the Degree Distribution of Private Networks. Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, Miami, FL, USA.","key":"ref_46","DOI":"10.1109\/ICDM.2009.11"},{"doi-asserted-by":"crossref","unstructured":"Kasiviswanathan, S.P., Nissim, K., Raskhodnikova, S., and Smith, A.D. (2013, January 3\u20136). Analyzing Graphs with Node Differential Privacy. Proceedings of the TCC, Tokyo, Japan.","key":"ref_47","DOI":"10.1007\/978-3-642-36594-2_26"},{"unstructured":"Day, W.Y., Li, N., and Lyu, M. (July, January 26). Publishing Graph Degree Distribution with Node Differential Privacy. Proceedings of the SIGMOD Conference, San Francisco, CA, USA.","key":"ref_48"},{"doi-asserted-by":"crossref","unstructured":"Zhang, J., Cormode, G., Procopiuc, C.M., Srivastava, D., and Xiao, X. (June, January 31). Private release of graph statistics using ladder functions. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Victoria, Australia.","key":"ref_49","DOI":"10.1145\/2723372.2737785"},{"doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S., and Smith, A. (2016, January 9\u201311). Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, USA.","key":"ref_50","DOI":"10.1109\/FOCS.2016.60"},{"key":"ref_51","first-page":"985","article-title":"Kronecker Graphs: An Approach to Modeling Networks","volume":"11","author":"Leskovec","year":"2008","journal-title":"J. Mach. Learn. Res."},{"doi-asserted-by":"crossref","unstructured":"Lu, W., and Miklau, G. (2014, January 24\u201327). Exponential random graph estimation under differential privacy. Proceedings of the KDD, New York, NY, USA.","key":"ref_52","DOI":"10.1145\/2623330.2623683"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1109\/TPDS.2016.2615020","article-title":"Preserving privacy with probabilistic indistinguishability in weighted social networks","volume":"28","author":"Liu","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"doi-asserted-by":"crossref","unstructured":"Liu, Z., Huang, L., Xu, H., Yang, W., and Wang, S. (2020, January 2\u20134). PrivAG: Analyzing attributed graph data with local differential privacy. Proceedings of the 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), Hong Kong, China.","key":"ref_54","DOI":"10.1109\/ICPADS51040.2020.00063"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/130\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:04:32Z","timestamp":1760119472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":54,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["e25010130"],"URL":"https:\/\/doi.org\/10.3390\/e25010130","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,1,9]]}}}