差分隐私约束下的图数据发布机制与挖掘算法研究

The widespread use of novel information systems (e.g., social networks) has generated large-scale graph data containing user-sensitive information. How to securely publish and mine these data under the premise of protecting user privacy is the key problem to be conquered for fully exploiting their potential value. Differential privacy technology has become the de facto standard for data privacy preservation and is widely used in the field of traditional data analysis. But there are few research focused on graph data. Starting from the structural characteristics of graph data itself, the goal of this proposal is to systematically study the design of publishing mechanisms and mining algorithms for graph data under differential privacy. The main research contents include: 1) To meet the practical application requirements from statistic inferences, we design actual publishing mechanisms for statistical features of graph data under edge differential privacy. 2) By relaxing the definition of differential privacy, we design more accurate and efficient publishing mechanisms for statistical features of graph data under node differential privacy. 3) Based on the hierarchical generative graph model that can capture the structure and attribute information of the graph more precisely, we study publishing mechanisms of synthetic (attribute) graphs under differential privacy. 4) Motivated by some classical graph mining algorithms, we study the design of graph mining algorithms under differential privacy. The research of this project can provide theoretical and technical support for securely publishing and mining of large-scale graph data, and thus facilitates the application of big data analysis technology.

社交网络等新型信息系统的普遍使用产生了大量含有用户敏感信息的图数据，如何在保护用户隐私的前提下安全地发布和挖掘这些数据是充分发挥其潜在价值所需解决的核心关键问题。差分隐私技术已成为数据隐私保护领域事实上的标准，并在传统数据分析领域得到了广泛应用，而在图数据领域却鲜有研究。本项目从图数据自身的结构特性出发，系统研究差分隐私约束下图数据发布机制和挖掘算法，具体内容包括：1）面向实际统计推断应用需求，设计边差分隐私约束下更为高效的图数据统计特征发布机制；2）通过扩展差分隐私定义，设计点差分隐私约束下更为精确的图数据统计特征发布机制；3）以全面刻画图的结构和属性信息的分层生成图模型为基础，设计差分隐私约束下的合成（属性）图发布机制；4）面向典型的图挖掘需求，设计差分隐私约束下的图挖掘算法。本项目的研究能为大规模图数据的安全发布和挖掘提供理论和技术支撑，促进大数据分析技术在社交网络等领域的应用。

作为一种典型的数据结构，图数据已在大数据分析的众多领域中得到了广泛应用。与此同时，如何保证图数据使用过程中的安全性也已成为数据安全领域的一个研究热点。本项目从图数据自身的结构特性出发，系统研究差分隐私约束下图数据发布机制和挖掘算法。在差分隐私下图数据统计特征发布方面，我们提出了两种点差分隐私下图的度分布直方图发布机制和动态图数据的度直方图发布机制；在差分隐私下合成图的生成方面，我们结合差分隐私、安全多方计算和本地化差分隐私技术提出了一种差分隐私约束下的图生成方法和一种新的点差分隐私下基于度序列的合成图生成算法；在差分隐私下的图数据分析算法方面，我们提出了一种边差分隐私下的图聚类算法DP-SCAN和一个满足差分隐私的约束谱聚类算法DP-CSC。另外，围绕数据隐私保护相关问题，项目组还对研究内容进行了关联性扩展研究，设计了隐私保护的用户认证协议、隐私保护的机器学习算法和口令安全性分析等，取得了一系列的研究成果。本项目的研究为隐私保护的图数据挖掘和发布提供了理论支撑，推动了数据共享和大数据分析技术在敏感数据集上的应用。在上述研究基础上，绝大部分结果已形成学术论文，在IET Information Security、Computer Standards & Interfaces、Inscrypt 2019、计算机学报等网络安全领域国内外重要期刊和会议上共发表学术论文20篇，其中SCI检索论文10篇，EI检索论文7篇；申请发明专利6项，其中4项已获授权；培养博士生5名、硕士生16名。