Analyzing Graphs with Node Differential Privacy

By Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith. 2013

425 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, neutral): “Examples include learning decision forests [17], principal component analysis [20], analysis of outliers [28], and analysis of graphical data [23, 25, 34, 30].”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, positive): “As we note above, there is substantial work on privacy broadly, with a line of work investigating appropriate notions of distance and what distinctions be-tween individuals and data should be protected.”
Practical Differential Privacy for SQL Queries Using Elastic Sensitivity (2017, background): “A number of less-general mechanisms for performing specific graph analysis tasks have been proposed [22, 25, 26, 35].”
PrivateSQL: A Differentially Private SQL Query Engine (2019, methodology): “, triangle counting, degree distribution) [10, 12, 21, 25, 26], and monotone queries (e.”
Towards Practical Differential Privacy for SQL Queries (2017, background): “A number of less-general mechanisms for performing specific graph analysis tasks have been proposed [31, 34, 35, 49].”
PrivEx: Private Collection of Traffic Statistics for Anonymous Communication Networks (2014, background): “Also of interest is work by Kasiviswanathan et al. [18] where network graphs are analyzed to investigate how the removal and addition of nodes in the graph affect the privacy of the information about the structure of the graph.”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “With the observation that many useful statistics have low sensitivities on graphs Gu with a small degree u, a common approach to achieve node differential privacy is to transform the graph G to a u-degree-bounded graph Gu, in which the nodes with degrees of more than u are deleted [33], [34].”
Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics (2017, methodology): “Projection techniques [18, 20, 32] modify the graph by adding or deleting edges and nodes until the maximum degree of a node is bounded by a small number θ.”
Secure Deep Graph Generation with Link Differential Privacy (2020, methodology): “For graph structured data, two types of privacy constraints can be applied, i.e., node-DP [Kasiviswanathan et al., 2013] and edge-DP [Blocki et al., 2012], which define two neighboring graphs to differ by at most one node or edge.”
Differentially private anonymized histograms (2019, background): “Hence, [12, 4, 13, 14, 15, 16, 17] considered the problem of releasing degree distributions of graphs with differential privacy.”
Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy (2019, methodology): “Kasiviswanathan et al. (2013) gave a method for computing private statistics when the degree of the node can be arbitrary, and their work proceeds by bounding the node degree and analyzing the bias this introduces.”