Sensitivity reduction of degree histogram publication under node differential privacy via mean filtering

摘要

Publication of nodes' degree information in the form of histogram provides useful information about the graph as well as the risk of privacy disclosure. Under the robust protection of node-differential privacy (node-DP), publishing result's accuracy mainly depends on the global sensitivity of this publishing task. Thus, the reduction of sensitivity is of great importance. Existing methods for degree histogram publication under node-DP are mostly based on limitation of maximum degree, whose sensitivity is still high, leading an unbearable noise scale. In this paper, we innovatively propose a method to tackle this issue. Firstly, we introduce mean filtering to process the histogram, almost halve the original sensitivity. Then, we use a series of techniques to further improve publishing accuracy, instituting a complete workflow for degree histogram publication under node-DP. Experimental results show that our method effectively improves the accuracy.