Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization
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 t...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/1/130 |
| _version_ | 1827626114493710336 |
|---|---|
| author | Zichun Liu Liusheng Huang Hongli Xu Wei Yang |
| author_facet | Zichun Liu Liusheng Huang Hongli Xu Wei Yang |
| author_sort | Zichun Liu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T12:49:21Z |
| format | Article |
| id | doaj.art-b9612ccd797e4a8abcde03fb870f4a71 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T12:49:21Z |
| publishDate | 2023-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-b9612ccd797e4a8abcde03fb870f4a712023-11-30T22:09:06ZengMDPI AGEntropy1099-43002023-01-0125113010.3390/e25010130Locally Differentially Private Heterogeneous Graph Aggregation with Utility OptimizationZichun Liu0Liusheng Huang1Hongli Xu2Wei Yang3School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, ChinaSchool of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, ChinaSchool of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, ChinaSchool of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, ChinaGraph 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.https://www.mdpi.com/1099-4300/25/1/130data privacylocal differential privacygraph aggregationheterogeneous graph |
| spellingShingle | Zichun Liu Liusheng Huang Hongli Xu Wei Yang Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization Entropy data privacy local differential privacy graph aggregation heterogeneous graph |
| title | Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization |
| title_full | Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization |
| title_fullStr | Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization |
| title_full_unstemmed | Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization |
| title_short | Locally Differentially Private Heterogeneous Graph Aggregation with Utility Optimization |
| title_sort | locally differentially private heterogeneous graph aggregation with utility optimization |
| topic | data privacy local differential privacy graph aggregation heterogeneous graph |
| url | https://www.mdpi.com/1099-4300/25/1/130 |
| work_keys_str_mv | AT zichunliu locallydifferentiallyprivateheterogeneousgraphaggregationwithutilityoptimization AT liushenghuang locallydifferentiallyprivateheterogeneousgraphaggregationwithutilityoptimization AT honglixu locallydifferentiallyprivateheterogeneousgraphaggregationwithutilityoptimization AT weiyang locallydifferentiallyprivateheterogeneousgraphaggregationwithutilityoptimization |