{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T19:03:17Z","timestamp":1782759797988,"version":"3.54.5"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T00:00:00Z","timestamp":1710979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Digital Threats"],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            Graph Neural Networks (GNNs) are known to address such tasks over graph-structured data, which is widely used to represent many real-world systems. The collection and analysis of graph data using GNNs raise significant privacy concerns regarding disclosing sensitive information. Existing works in privacy-preserving GNNs ensure the privacy of nodes\u2019 features and labels. However, its structure also needs to be privatized. To address this problem, we provide a method, Local Structural Perturbation Graph Neural Network, that adds noise to the neighborhood data of the node along with its features and label. Here, we perturb the graph structure by sampling non-neighboring nodes and randomizing them along with the neighborhood. We use differentially private mechanisms to perturb the structure of graphs with theoretical guarantees. This introduces the challenge of reducing the impact of noise in the neighborhood on accuracy. In this view, we use the\n            <jats:italic>p<\/jats:italic>\n            -hop neighborhood to compensate for the loss of actual neighbors in randomization.\n          <\/jats:p>\n          <jats:p>We use the node and label privacy as implemented in the previous methods for privacy in GNNs. We conduct extensive experiments over real-world datasets to show the impact of perturbation on the graph structure. We also perform the theoretical analysis of our proposed method.<\/jats:p>","DOI":"10.1145\/3624485","type":"journal-article","created":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T11:13:11Z","timestamp":1694862791000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Locally and Structurally Private Graph Neural Networks"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1214-7985","authenticated-orcid":false,"given":"Rucha Bhalchandra","family":"Joshi","sequence":"first","affiliation":[{"name":"National Institute of Science Education and Research, Bhubaneswar, India and Homi Bhabha National Institute, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9910-7291","authenticated-orcid":false,"given":"Subhankar","family":"Mishra","sequence":"additional","affiliation":[{"name":"National Institute of Science Education and Research, Bhubaneswar, India and Homi Bhabha National Institute, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,21]]},"reference":[{"issue":"1","key":"e_1_3_2_2_2","article-title":"Debtrank: Too central to fail? financial networks, the fed and systemic risk","volume":"2","author":"Battiston Stefano","year":"2012","unstructured":"Stefano Battiston, Michelangelo Puliga, Rahul Kaushik, Paolo Tasca, and Guido Caldarelli. 2012. Debtrank: Too central to fail? financial networks, the fed and systemic risk. Sci. Rep. 2, 1 (2012), 541.","journal-title":"Sci. Rep."},{"key":"e_1_3_2_3_2","first-page":"1136","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Bun Mark","year":"2021","unstructured":"Mark Bun, Marek Elias, and Janardhan Kulkarni. 2021. Differentially private correlation clustering. In Proceedings of the International Conference on Machine Learning. PMLR, 1136\u20131146."},{"issue":"1","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TPAMI.2021.3137605","article-title":"A comprehensive survey of scene graphs: Generation and application","volume":"45","author":"Chang Xiaojun","year":"2021","unstructured":"Xiaojun Chang, Pengzhen Ren, Pengfei Xu, Zhihui Li, Xiaojiang Chen, and Alex Hauptmann. 2021. A comprehensive survey of scene graphs: Generation and application. IEEE Trans. Pattern Anal. Mach. Intell. 45, 1 (2021), 1\u201326.","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3294996.3295115"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2023.3258977"},{"key":"e_1_3_2_8_2","first-page":"76","volume-title":"Proceedings of the 17th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (Mobiquitous\u201920)","author":"Duddu Vasisht","year":"2020","unstructured":"Vasisht Duddu, Antoine Boutet, and Virat Shejwalkar. 2020. Quantifying privacy leakage in graph embedding. In Proceedings of the 17th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (Mobiquitous\u201920). 76\u201385."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_10_2","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. Adv. Neural Inf. Process. Syst. 30 (2017).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_2_11_2","first-page":"2669","volume-title":"Proceedings of the 30th USENIX Security Symposium (USENIX Security\u201921)","author":"He Xinlei","year":"2021","unstructured":"Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. 2021. Stealing links from graph neural networks. In Proceedings of the 30th USENIX Security Symposium (USENIX Security\u201921). 2669\u20132686."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3539597.3572987"},{"key":"e_1_3_2_13_2","volume-title":"Proceedings of the 18th International Workshop on Mining and Learning with Graphs","author":"Joshi Rucha Bhalchandra","year":"2022","unstructured":"Rucha Bhalchandra Joshi and Subhankar Mishra. 2022. Edge-level privacy in Graph Neural Networks. In Proceedings of the 18th International Workshop on Mining and Learning with Graphs."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-16-3398-0_10"},{"key":"e_1_3_2_15_2","unstructured":"Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. In 18th International Workshop on Mining and Learning with Graphs."},{"issue":"3","key":"e_1_3_2_16_2","first-page":"3918","article-title":"Video pivoting unsupervised multi-modal machine translation","volume":"45","author":"Li Mingjie","year":"2022","unstructured":"Mingjie Li, Po-Yao Huang, Xiaojun Chang, Junjie Hu, Yi Yang, and Alex Hauptmann. 2022. Video pivoting unsupervised multi-modal machine translation. IEEE Trans. Pattern Anal. Mach. Intell. 45, 3 (2022), 3918\u20133932.","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2016.2583219"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2023.3241097"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2021.3128764"},{"key":"e_1_3_2_20_2","volume-title":"Proceedings of the EDBT\/ICDT Workshops","volume":"157","author":"M\u00fclle Yvonne","year":"2015","unstructured":"Yvonne M\u00fclle, Chris Clifton, and Klemens B\u00f6hm. 2015. Privacy-integrated graph clustering through differential privacy. In Proceedings of the EDBT\/ICDT Workshops, Vol. 157."},{"key":"e_1_3_2_21_2","article-title":"Membership inference attack on graph neural networks","author":"Olatunji Iyiola E.","year":"2021","unstructured":"Iyiola E. Olatunji, Wolfgang Nejdl, and Megha Khosla. 2021. Membership inference attack on graph neural networks. arXiv:2101.06570.","journal-title":"arXiv:2101.06570"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952122"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411866"},{"key":"e_1_3_2_24_2","first-page":"2130","volume-title":"Proceedings of the ACM SIGSAC Conference on Computer and Communications Security","author":"Sajadmanesh Sina","year":"2021","unstructured":"Sina Sajadmanesh and Daniel Gatica-Perez. 2021. Locally private graph neural networks. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 2130\u20132145."},{"key":"e_1_3_2_25_2","first-page":"372","volume-title":"Handbook of Research on Cyber Crime and Information Privacy","author":"Sengupta Poushali","year":"2021","unstructured":"Poushali Sengupta, Sudipta Paul, and Subhankar Mishra. 2021. Learning with differential privacy. In Handbook of Research on Cyber Crime and Information Privacy. IGI Global, 372\u2013395."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1137\/1.9781611975994.33","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Stemmer Uri","year":"2020","unstructured":"Uri Stemmer. 2020. Locally private k-means clustering. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 548\u2013559."},{"key":"e_1_3_2_27_2","unstructured":"Petar Velickovic Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Li\u00f2 and Yoshua Bengio. 2018. Graph attention networks. In 6th International Conference on Learning Representations (ICLR\u201918 Vancouver BC Canada April 30 - May 3 2018) Conference Track Proceedings OpenReview.net. https:\/\/openreview.net\/forum?id=rJXMpikCZ"},{"key":"e_1_3_2_28_2","article-title":"Fedgnn: Federated graph neural network for privacy-preserving recommendation","author":"Wu Chuhan","year":"2021","unstructured":"Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. 2021. Fedgnn: Federated graph neural network for privacy-preserving recommendation. arXiv:2102.04925. Retrieved from https:\/\/arxiv.org\/abs\/2102.04925","journal-title":"arXiv:2102.04925"},{"issue":"1","key":"e_1_3_2_29_2","article-title":"A federated graph neural network framework for privacy-preserving personalization","volume":"13","author":"Wu Chuhan","year":"2022","unstructured":"Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Tao Qi, Yongfeng Huang, and Xing Xie. 2022. A federated graph neural network framework for privacy-preserving personalization. Nat. Commun. 13, 1 (2022), 3091.","journal-title":"Nat. Commun."},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the Symposium on Security and Privacy","author":"Wu Fan","year":"2021","unstructured":"Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. 2021. LINKTELLER: Recovering private edges from graph neural networks via influence analysis. In Proceedings of the Symposium on Security and Privacy."},{"key":"e_1_3_2_31_2","first-page":"235","volume-title":"Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining","author":"Xu Depeng","year":"2018","unstructured":"Depeng Xu, Shuhan Yuan, Xintao Wu, and HaiNhat Phan. 2018. DPNE: Differentially private network embedding. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 235\u2013246."},{"key":"e_1_3_2_32_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Xu Keyulu","year":"2018","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How Powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_33_2","unstructured":"Zhilin Yang William W. Cohen and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33nd International Conference on Machine Learning (ICML\u201916 New York City NY USA June 19-24 2016) JMLR Workshop and Conference Proceedings Maria-Florina Balcan and Kilian Q. Weinberger (Eds.). Vol. 48 JMLR.org 40\u201348. http:\/\/proceedings.mlr.press\/v48\/yanga16.html"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2015.7224734"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3183586"},{"key":"e_1_3_2_36_2","article-title":"Vertically federated graph neural network for privacy-preserving node classification","author":"Zhou Jun","year":"2020","unstructured":"Jun Zhou, Chaochao Chen, Longfei Zheng, Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang. 2020. Vertically federated graph neural network for privacy-preserving node classification. arXiv:2005.11903. Retrieved from https:\/\/arxiv.org\/abs\/2005.11903","journal-title":"arXiv:2005.11903"},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/978-3-642-21521-6_13","volume-title":"Privacy Online: Perspectives on Privacy and Self-disclosure in the Social Web","author":"Ziegele Marc","year":"2011","unstructured":"Marc Ziegele and Oliver Quiring. 2011. Privacy in social network sites. In Privacy Online: Perspectives on Privacy and Self-disclosure in the Social Web. Springer, 175\u2013189."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394520"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"}],"container-title":["Digital Threats: Research and Practice"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624485","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3624485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:46Z","timestamp":1750268986000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,21]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3624485"],"URL":"https:\/\/doi.org\/10.1145\/3624485","relation":{},"ISSN":["2692-1626","2576-5337"],"issn-type":[{"value":"2692-1626","type":"print"},{"value":"2576-5337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,21]]},"assertion":[{"value":"2022-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}