一種面向圖數(shù)據(jù)的AWG-LDP局部差分隱私保護算法研究

摘 要：針對傳統(tǒng)的圖數(shù)據(jù)隱私保護方法只關(guān)注保護屬性或結(jié)構(gòu)兩者之一易導致節(jié)點或邊隱私信息泄露的問題，提出了一種對屬性加權(quán)圖的局部差分隱私的保護算法（AWG-LDP）。首先，該算法利用GN算法將圖數(shù)據(jù)劃分成社區(qū)子圖；其次，分別計算每個社區(qū)子圖的局部敏感度，對于劃分后的每一個子圖，通過結(jié)合結(jié)構(gòu)相似性和屬性相似性并添加拉普拉斯噪聲進行邊擾動，實現(xiàn)局部差分隱私；最后，利用屬性泛化的方式將待發(fā)布的節(jié)點進行泛化，防止節(jié)點敏感信息被攻擊。利用真實的圖數(shù)據(jù)集進行了不同參數(shù)配置以及不同算法的對比實驗，實驗結(jié)果表明該算法提升了隱私保護效果，同時，降低了信息損失，提高了數(shù)據(jù)的可用性。

關(guān)鍵詞：屬性加權(quán)圖； 局部差分隱私； 拉普拉斯噪聲； 隱私保護

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695（2023）08-036-2467-06

doi：10.19734/j.issn.1001-3695.2022.10.0633

Study on AWG-LDP local differential privacy protection algorithm for graph data

Sun Tao， Li Xiaohui， Li Han， Zhao Xue

（School of Electronics amp; Information Engineering， Liaoning University of Technology， Jinzhou Liaoning 121000， China）

Abstract：Aiming at the problem that traditional graph data privacy protection methods only focus on protecting one of the attributes or structures， which can easily lead to the leakage of node or edge privacy information， this paper proposed a local diffe-rential privacy protection algorithm for attribute-weighted graphs （AWG-LDP） . Firstly， the algorithm used the GN algorithm to divide the graph data into community subgraphs. Secondly， it calculated the local sensitivity of each community respectively. For each subgraph after division， it realized local differential privacy by combining structural similarity and attribute similarity and adding Laplace noise for edge perturbation. Finally， it generalized the nodes to be published by means of attribute generalization to prevent node sensitive information from being attacked. Using the real graph data set， the paper configured different parameters and compared algorithms with others. The experimental results show that the algorithm improves the privacy protection effect. Meanwhile， it reduces the information loss and improves the availability of data.

Key words：properties weighted graph; local difference privacy; Laplace noise; privacy protection

大數(shù)據(jù)時代，數(shù)據(jù)的存儲方式越來越多元化。隨著智慧城市、智慧醫(yī)療的發(fā)展［1］，可以同時存儲數(shù)據(jù)屬性和鏈接關(guān)系的圖數(shù)據(jù)應(yīng)運而生［2］。圖數(shù)據(jù)不僅給智能道路規(guī)劃、智慧醫(yī)療診斷以及智能推薦等領(lǐng)域帶來了便利，也幫助科學研究人員的數(shù)據(jù)分析工作提高了效率。但是圖數(shù)據(jù)中存在著大量的敏感信息，例如智慧醫(yī)療服務(wù)中的醫(yī)患關(guān)系、公路網(wǎng)絡(luò)中的位置信息等，若直接將帶有此類敏感信息的圖數(shù)據(jù)發(fā)布的話容易造成隱私泄露。傳統(tǒng)的匿名化方法難以抵御基于背景知識的攻擊，例如圖1（a）是某屬性圖，圖1（b）是該屬性圖對應(yīng)的匿名圖。若已知圖數(shù)據(jù)中與Bob聯(lián)系最多的人的話依舊可以推斷出圖中的點C是Bob，并可以結(jié)合已有的背景知識推斷其年齡、歸屬地以及鏈接信息等敏感屬性。

1 相關(guān)工作

圖數(shù)據(jù)上的隱私信息主要分為圖結(jié)構(gòu)的隱私信息和圖屬性的隱私信息兩種。圖結(jié)構(gòu)的隱私信息保護包括以邊和點為主的兩類隱私，圖屬性的隱私信息主要包括身份信息、語義屬性與鏈接關(guān)系三大類［3］。為解決圖數(shù)據(jù)的隱私泄露，Rong等人［4］提出了一種K+同構(gòu)算法來實現(xiàn)圖中的子圖或者社區(qū)之間的匿名狀態(tài)，該算法首先將檢測到的子圖劃分成相似的子圖簇，然后在每個簇中進行圖修改，此方法雖然很好地保護了圖的結(jié)構(gòu)信息，但是考慮量化節(jié)點的屬性信息，難以防范攻擊者利用聚類技術(shù)和數(shù)據(jù)挖掘技術(shù)獲取原始圖的敏感屬性。Liu等人［5］為了減少對原始圖的修改，以保持數(shù)據(jù)的效用，引入了一種圖修改代價度量的方法，并提出了一種新的基于度序列的圖劃分算法，此算法先對圖中節(jié)點的度進行劃分，然后根據(jù)貪婪算法的思想劃分匿名組，最后對圖中的頂點進行匿名化保護，此方法雖保護了圖中頂點的屬性信息，但難以防范攻擊者結(jié)合邊信息攻擊原始圖中頂點的問題。Wang等人［6］為了防止攻擊者通過鄰域圖來攻擊用戶的個人身份信息，提出了一種基于圖劃分的GPPS算法，該算法通過節(jié)點聚類和圖修改并結(jié)合k匿名技術(shù)來實現(xiàn)用戶的個人身份信息保護，但是沒有量化節(jié)點間的相似性。姜火文等人［7］針對當下匿名化方案難以抵擋背景知識攻擊的問題，提出了一種基于節(jié)點連接結(jié)構(gòu)和屬性值的屬性圖聚類匿名化算法，該算法先利用節(jié)點間結(jié)構(gòu)和屬性相似度將節(jié)點聚類成一個超點，然后再對超點進行匿名化保護后發(fā)布，該算法考慮了節(jié)點相似性和屬性相似性，但是聚成一個超點致使圖結(jié)構(gòu)的整體變化過大，從而導致匿名圖的可用性降低。

差分隱私2006年被提出后［8］，逐漸受到了圖數(shù)據(jù)挖掘人員的關(guān)注。2009年，Hay等人［9］首次將差分隱私算法用于圖數(shù)據(jù)的隱私保護當中。張宇軒等人［10］針對點差分隱私定義下查詢函數(shù)敏感度過大的問題，提出了一種基于度排序的邊移除算法，該算法先將節(jié)點的度按照大小排序并刪除度過大的邊，然后經(jīng)過投影將圖壓縮后，生成相應(yīng)的度直方圖模型再對此模型添加拉普拉斯噪聲擾動后發(fā)布。此算法直接將整個圖數(shù)據(jù)投影壓縮，容易造成隱私保護過度。Ni等人［11］為了保護圖數(shù)據(jù)中的節(jié)點敏感屬性提出了一種DP-MCDBSCAN算法，該算法結(jié)合DBSCAN算法和差分隱私，在聚類過程中添加噪聲擾動實現(xiàn)對原數(shù)據(jù)的隱私保護，此算法較好地保護了原始數(shù)據(jù)的屬性信息，但未考慮用戶屬性的權(quán)重問題，易造成用戶屬性的過度保護，從而使屬性數(shù)據(jù)失真率過高。Hawkins等人［12］提出了一種利用差分隱私方法將無向圖的拉普拉斯矩陣譜私有化的框架，該框架利用有界拉普拉斯機制為圖數(shù)據(jù)的特征值提供差分隱私保護，此框架忽略了隱私預算的影響，容易導致加入的噪聲不足或者過大的問題。Huang等人［13］結(jié)合差分隱私和隨機化算法提出了一種PBCN隱私保護方法，該方法通過對度序列隨機擾動實現(xiàn)圖重構(gòu)，然后對圖中的節(jié)點利用差分隱私技術(shù)注入噪聲生成偽節(jié)點，該算法有較好的執(zhí)行效率，但也存在攻擊者根據(jù)原始圖的度序列重構(gòu)出相應(yīng)結(jié)構(gòu)的風險，隱私保護效果不足且直接對圖中的節(jié)點加入差分隱私需要耗費巨大的隱私預算成本。Liu等人［14］提出了一種針對無向無權(quán)圖的局部差分隱私算法，該算法先將圖數(shù)據(jù)進行社區(qū)劃分，生成局部不確定圖，然后再將局部不確定圖進行重構(gòu)，并且在重構(gòu)的過程中對重構(gòu)時邊生成的概率添加拉普拉斯噪聲，實現(xiàn)局部差分隱私，并發(fā)布生成圖模型，此算法考慮到使用局部差分隱私保護來保護圖數(shù)據(jù)中的結(jié)構(gòu)信息，但是忽略了圖數(shù)據(jù)中的敏感屬性的保護，容易導致發(fā)布后的圖數(shù)據(jù)中節(jié)點敏感信息的泄露。

上述相關(guān)工作都很好地實現(xiàn)了圖數(shù)據(jù)的隱私保護，但是上述算法存在只關(guān)注結(jié)構(gòu)或?qū)傩詢烧咧浑[私的問題，難以防范攻擊者結(jié)合結(jié)構(gòu)和屬性攻擊原始圖數(shù)據(jù)。同時，大多數(shù)算法都是基于整個圖數(shù)據(jù)對節(jié)點或邊直接添加噪聲擾動，此方法雖然保護了圖中的隱私信息，但也容易造成保護過度從而導致圖數(shù)據(jù)的可用性降低。針對上述問題，本文提出了一種基于屬性加權(quán)圖的局部差分隱私算法。本文的主要貢獻有：

a）建立屬性加權(quán)圖模型，屬性權(quán)重可由用戶自己分配，利用GN算法在此模型劃分。

b）分別量化社區(qū)內(nèi)兩點間結(jié)構(gòu)相似性和屬性相似性，并結(jié)合兩者添加拉普拉斯噪聲，實現(xiàn)局部差分隱私。

c）在敏感屬性處理上，本文將屬性分為數(shù)值型和非數(shù)值型。對數(shù)值型屬性，采取區(qū)間泛化法；對非數(shù)值型屬性，分析用戶屬性并建立屬性泛化樹。

d）對比實驗表明，該算法隱私保護效果良好，加噪聲后的圖數(shù)據(jù)比現(xiàn)有算法隱私保護效果更好且信息損失更低。

2 預備知識

圖數(shù)據(jù)上的差分隱私保護，主要分為基于節(jié)點的差分隱私和基于邊的差分隱私。基于節(jié)點的差分隱私是在只相差一個節(jié)點以及該節(jié)點相連的所有邊的鄰居圖的基礎(chǔ)上定義的，基于邊的差分隱私定義是在只相差一條邊的鄰居圖的基礎(chǔ)上定義的［14］。

2.1 圖數(shù)據(jù)的相關(guān)定義

2.2 差分隱私相關(guān)定義

2.3 算法設(shè)計

2.4 算法描述

2.5 算法分析

2.5.1 時間復雜度分析

2.5.2 空間復雜度分析

本文算法需要申請一個長度為N的集合存放劃分后的社區(qū)子圖，此時需要的空間復雜度為O（1）。若算法3需要建立屬性層次樹，則空間復雜度取決于泛化樹中節(jié)點的個數(shù)，假設(shè)有M個敏感屬性，其敏感屬性相對應(yīng)的值為n個，則此時需要的空間復雜度為M×O（n）。最后，對于要發(fā)布的加噪圖數(shù)據(jù)有N條記錄，則需要的空間復雜度為O（N）。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境及數(shù)據(jù)集

3.1.1 實驗環(huán)境

本節(jié)將用實驗來對提出的AWG-LDP算法進行性能評估，本實驗使用Python語言完成且實驗的運行環(huán)境為：PyCharm 2021.2，操作系統(tǒng)為Windows 11，系統(tǒng)內(nèi)存16 GB。

3.1.2 實驗數(shù)據(jù)集

3.2 基線方法

3.3 實驗結(jié)果

3.3.1 一維結(jié)構(gòu)熵

3.3.2 節(jié)點度識別保護概率

3.3.3 泛化信息損失度

3.3.4 總體邊變化率

總體的邊變化率能反映通過加入隱私保護算法后的圖數(shù)據(jù)的可用性大小。所以，本文算法參照文獻［22］提出的總體邊變化率指標且與該文提出的改進的K度匿名算法進行對比實驗（此時的K值表示K個社區(qū)），總體邊變化率如圖7所示。

實驗結(jié)果表明，隨著K值不斷增加，總體的邊變化也隨之增大。這是由于隱私保護算法對原有的圖數(shù)據(jù)進行了結(jié)構(gòu)上的改變，從而導致了圖中邊的變化。從圖7可以看出，文獻［24］中的算法較大地改變了原始圖中的邊緣，因為此算法直接將原始圖的度序列生成相應(yīng)的匿名圖，導致原有的邊總體變化較大，數(shù)據(jù)可用性降低。而本文算法通過小區(qū)域的方式對邊加入噪聲擾動，原始邊不會大幅度的改變。因此，AWG-LDP算法優(yōu)于改進的K度匿名保護算法。通過與之對比，也證實了本文算法的數(shù)據(jù)可用性較高。

通過歸納總結(jié)上述實驗，AWG-LDP算法以社區(qū)為單位兼顧屬性相似性和結(jié)構(gòu)相似性加入噪聲的同時，還分數(shù)值型和結(jié)構(gòu)性泛化了圖中的節(jié)點敏感屬性，具有較低的結(jié)構(gòu)熵值和較高的節(jié)點度識別保護概率，能提高隱私保護強度，實現(xiàn)圖數(shù)據(jù)隱私保護的有效性。同時，經(jīng)本文算法處理的圖數(shù)據(jù)具有較低的信息損失和總體變化率，能提高圖數(shù)據(jù)的可用性。

4 結(jié)束語

由于圖數(shù)據(jù)中的結(jié)構(gòu)和屬性占據(jù)同樣重要的地位，所以在進行圖數(shù)據(jù)發(fā)布時，必須要同時考慮兩者的信息以保護用戶的敏感信息不被泄露。本文提出了一種屬性加權(quán)圖的局部差分隱私保護算法（AWG-LDP），對圖數(shù)據(jù)的發(fā)布階段進行隱私保護。首先，該算法對原始圖進行社區(qū)劃分，遍歷每個社區(qū)子圖，根據(jù)用戶自設(shè)的屬性權(quán)值，計算出余弦相似度，這樣可以更好地保護用戶的重要屬性；其次，該算法根據(jù)社區(qū)內(nèi)兩點間的綜合相似性，分配隱私預算，解決了因隱私預算過大而產(chǎn)生的隱私保護過度的問題；最后，該算法對子圖內(nèi)兩點進行邊連接，實現(xiàn)局部差分隱私，降低了噪聲的使用量。通過對比圖數(shù)據(jù)中的一維結(jié)構(gòu)熵、節(jié)點識別概率以及泛化損失度和總體邊變化率表明，該算法較好地保護了節(jié)點的屬性信息和結(jié)構(gòu)信息，并盡可能地還原了原始圖結(jié)構(gòu)，更有利于后續(xù)的圖數(shù)據(jù)的挖掘和分析工作。

參考文獻：

［1］Cook D J， Duncan G， Sprint G， et al. Using smart city technology to make healthcare smarter［J］. Proceedings of the IEEE， 2018，106（4）： 708-722.

［2］Ji Shouling， Li Weiqing， Srivatsa M， et al. Structural data de-anonymization： theory and practice［J］. IEEE/ACM Trans on Networking， 2016，24（6）： 3523-3536.

［3］劉向宇， 王斌， 楊曉春. 社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護技術(shù)綜述［J］. 軟件學報， 2014，25（3）： 576-590. （Liu Xiangyu， Wang Bin， Yang Xiaochun. Overview of privacy protection technology for social network data release［J］. Journal of Software， 2014，25（3）： 576-590.）

［4］Rong Huan， Ma Tinghuai， Tang Meili， et al. A novel subgraph K+ isomorphism method in social network based on graph similarity detection［J］. Soft Computing， 2018，22（8）： 2583-2601.

［5］Liu Peng， Li Xianxian. An improved privacy preserving algorithm for publishing social network data［C］//Proc of the 10th IEEE International Conference on High Performance Computing and Communications amp; IEEE International Conference on Embedded and Ubiquitous Computing. Piscataway， NJ：IEEE Press， 2013： 888-895.

［6］Wang Yue，Wu Xintao，Wu Leting. Differential privacy preserving spectral graph analysis［C］//Proc of Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin：Springer， 2013：329-340.

［7］姜火文， 占清華， 劉文娟， 等. 圖數(shù)據(jù)發(fā)布隱私保護的聚類匿名方法［J］. 軟件學報， 2017，28（9）： 2323-2333. （Jiang Huowen， Zhan Qinghua， Liu Wenjuan， et al. Clustering-anonymity approach for privacy preservation of graph data-publishing［J］. Journal of Software， 2017，28（9）： 2323-2333.）

［8］Dwork C. Differential privacy［M］//Bugliesi M， Preneel B， Sassone V， et al. Automata， Languages and Programming. Berlin， Heidelberg： Springer， 2006： 1-12.

［9］劉宇涵， 陳紅， 劉藝璇， 等. 圖數(shù)據(jù)上的隱私攻擊與防御技術(shù)［J］. 計算機學報， 2022，45（4）： 702-734. （Liu Yuhan， Chen Hong， Liu Yixuan， et al. Privacy attacks and defense techniques on graph data［J］. Journal of Computer Science， 2022，45（4）： 702-734.）

［10］張宇軒， 魏江宏， 李霽， 等. 點差分隱私下圖數(shù)據(jù)的度直方圖發(fā)布方法［J］. 計算機研究與發(fā)展， 2019，56（3）： 508-520. （Zhang Yuxuan， Wei Jianghong， Li Ji， et al. The degree histogram release method for the point difference privacy data［J］. Computer Research and Development， 2019，56（3）： 508-520.）

［11］Ni Lian， Li Chao， Wang Xiao， et al. DP-MCDBSCAN： differential privacy preserving multi-core DBSCAN clustering for network user data［J］. IEEE Access， 2018，6： 21053-21063.

［12］Hawkins C， Chen Bo， Yazdani K， et al. Node and edge differential privacy for graph Laplacian spectra： mechanisms and scaling laws［EB/OL］. （2022-11-28）. https：//arxiv.org/abs/2211.15366.

［13］Huang Haiping， Zhang Dongjun， Xiao Fu， et al. Privacy-preserving approach PBCN in social network with differential privacy［J］. IEEE Trans on Network and Service Management， 2020，17（2）： 931-945.

［14］Liu Peng， Xu Yuanxin， Jiang Quan， et al. Local differential privacy for social network publishing［J］. Neurocomputing， 2020，391： 273-279.

［15］Bai Ling. An extended GN algorithm for identifying community structure in networks［C］//Proc of International Conference on Artificial Intelligence and Computer Applications. Piscataway， NJ：IEEE Press，2019： 83-89.

［16］Wei Chengkun， Ji Shouling， Liu Changchang， et al. AsgLDP： collecting and generating decentralized attributed graphs with local diffe-rential privacy［J］. IEEE Trans on Information Forensics and Security， 2020，15： 3239-3254.

［17］Mahmood T， Ilyas M， Ali Z， et al. Spherical fuzzy sets-based cosine similarity and information measures for pattern recognition and medical diagnosis［J］. IEEE Access， 2021，9： 25835-25842.

［18］Qin Zhan， Yu Ting， Yang Yin， et al. Generating synthetic decentra-lized social graphs with local differential privacy［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security. 2017： 425-438.

［19］Liu Changchang， Chakraborty S， Mittal P. Dependence makes you vulnerable： differential privacy under dependent tuples［C］//Proc of Network and Distributed System Security Symposium. 2016： 21-24.

［20］Sarwate A D， Sankar L. A rate-disortion perspective on local differential privacy［C］//Proc of the 52nd Annual Allerton Conference on Communication， Control， and Computing （Allerton） . Piscataway， NJ： IEEE Press， 2014： 903-908.

［21］Tassa T， Cohen D J. Anonymization of centralized and distributed social networks by sequential clustering［J］. IEEE Trans on Know-ledge and Data Engineering， 2011，25（2）： 311-324.

［22］McAuley J， Leskovec J. Learning to discover social circles in ego networks［C］//Proc of the 25th International Conference on Neural Information Processing Systems. Red Hook， NY ： Curran Associates Inc.， 2012：539-547.

［23］徐花， 田有亮. 差分隱私下的權(quán)重社交網(wǎng)絡(luò)隱私保護［J］. 西安電子科技大學學報， 2022，49（1）： 17-25. （Xu Hua， Tian Youliang. Weights under differential privacy social network privacy protection［J］. Journal of Xidian University， 2022，49（1）： 17-25.）

［24］朱黎明， 丁曉波， 龔國強. 圖數(shù)據(jù)連續(xù)發(fā)布中的隱私保護方法［J］. 計算機工程， 2022，48（5）： 154-161. （Zhu Liming， Ding Xiaobo， Gong Guoqiang. Privacy protection method in continuous publi-shing of graph data［J］. Computer Engineering， 2022，48（5）：154-161.）

［25］Campan A， Truta T M. Data and structural K-anonymity in social networks［C］//Proc of International Workshop on Privacy， Security， and Trust in KDD. Berlin：Springer， 2009： 33-54.

［26］姜火文， 曾國蓀， 胡克坤 . 一種遺傳算法實現(xiàn)的圖聚類匿名隱私保護方法［J］.計算機研究與發(fā)展， 2016，53（10）： 2354-2364. （Jiang Huowen， Zeng Guosun， Hu Kekun. A graph-clustering anonymity method implemented by genetic algorithm for privacy-preserving［J］. Journal of Computer Research and Development， 2016，53（10）： 2354-2364.）