Private analysis of graph structure

By Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, Grigory Yaroslavtsev. Proceedings of the VLDB Endowment, 2011

308 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3b14361fea745ff88b1e4615565d8ed1d2fbf31e

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

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “Nissim et al [NRS07] (see full version) studied the case of estimating the number of triangles in a graph, and Karwa et al [KRSY11] extended this result to other graph structures.”
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso (2013, unknown): “…parameter. θ̂(D) = arg min θ∈C 1 2n ‖y −Xθ‖22 + Λ n ‖θ‖1 (3) [27, 17] showed that under certain “niceness” conditions on the data set D = (y, X) and the underlying parameter vector θ∗, the support of θ̂(D) equals the support of θ∗ and ‖θ̂(D)− θ∗‖2 goes down to zero as n goes to infinity.”
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso (2013, methodology): “Kifer et al. (2012) gave the first results on private sparse regression in high dimension.”
Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics (2017, background): “Thus, edge[31] and node-differentially private techniques [18, 20, 32] can be applied to protect the data (Sec.”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, unknown): “Examples include learning decision forests [17], principal component analysis [20], analysis of outliers [28], and analysis of graphical data [23, 25, 34, 30].”
A workflow for differentially-private graph synthesis (2012, background): “Bespoke analyses have recently emerged for degree distributions [3], joint degree distribution (and assortativity) [13], triangle counting [9], and some generalizations of triangles [5].”
DStress: Efficient Differentially Private Computations on Distributed Data (2017, methodology): “, in [42]), as we did for the two algorithms we used in section 4.”
Analyzing Graphs with Node Differential Privacy (2013, background): “Roughly, differential privacy guarantees that changes to one person’s data will not significantly affect the output distribution of an analysis procedure.”
Differentially private data analysis of social networks via restricted sensitivity (2012, background): “Triangle counting queries can be answered in the edge adjacency model by efficiently computing the smooth sensitivity [18], and this result can be extended to answer other counting queries [16].”
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].”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “[31] to release counts on k-triangles and k-stars.”
Correlated network data publication via differential privacy (2013, methodology): “With the recent wide acknowledgment of differential privacy, some papers [16,18,22,31,32] have started to apply differential privacy to network data from different perspectives.”
A Guide to Differential Privacy Theory in Social Network Analysis (2012, background): “differential privacy in this paper, but we recommend looking at [7] for more information on alternative approaches.”
GUPT: privacy preserving data analysis made easy (2012, unknown): “A number of advances in diﬀerential privacy have sought to improve the accuracy of very speciﬁc types of data queries such as linear counting queries [14], graph queries [12] and histogram analysis [11].”
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].”
PrivateSQL: A Differentially Private SQL Query Engine (2019, methodology): “Edge-DP [25] is captured by P -DP by setting Edge as the primary private relation R, Node-DP [26] is captured if we set Node as R.”