Relationship privacy: output perturbation for queries with joins

By Vibhor Rastogi, Michael Hay, Gerome Miklau, Dan Suciu. 2009

163 citations recorded by the source corpus.

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

Citations in the corpus

Signal Processing and Machine Learning with Differential Privacy (2013, background): “There are a few variant definitions [5]–[7], but for the pur poses of this survey, differential privacy measures privacy risk by a parameter e that bounds the loglikelihood ratio of the output of a (private) algorithm under two databases differing in a single individual's data.”
Regression Model Fitting under Differential Privacy and Model Inversion Attack (2015, background): “…synthetic graph , 2013; Mir and Wright, 2009; Sala et al. , 2011 ] , computing graph properties such as degree distributions [ Hay et al. , 2009 ] and clustering coefﬁcient [ Rastogi et al. , 2009; Wang et al. , 2012 ] , and spectral graph analysis [ Wang et al. , 2013 ] in social network analysis.”
Protecting Locations with Differential Privacy under Temporal Correlations (2014, background): “Accordingly, we prove that for the problem of continual location sharing differential privacy is equivalent to adversarial privacy, first studied in [35].”
No free lunch in data privacy (2011, background): “[30] proposed a relaxation of differential privacy for social networks by proving an equivalence to adversarial privacy (which makes assumptions about the data), and then adding further constraints on the data-generating mechanism.”
A rigorous and customizable framework for privacy (2012, background): “[33] have proved an equivalence between a certain instantiation of adversarial privacy and a variant of differential privacy known as -indistinguishability (the main difference with differential privacy is the requirement that neighboring databases have the same size) [13].”
Accurate Estimation of the Degree Distribution of Private Networks (2009, background): “Enabling accurate analysis of social networks is an often mentioned goal, but we are aware of only a few concrete results: techniques for computing properties such as clustering coefficient that have high sensitivity [19], [20] and a forthcoming approach that estimates the parameters of a random gra”
Pufferfish (2014, methodology): “In single-prior privacy, the data curator speciﬁes only one data-generating distribution.”
Preserving Link Privacy in Social Network Based Systems (2012, background): “Also, Rastogi et al. [25] introduce a relaxed notion of differential privacy for data with relationships so that more expressive queries (e.g., joins) can be supported without hurting utility very much.”
Cardinality Estimators do not Preserve Privacy (2018, background): “Data-generating probability distributions were considered as a source of uncertainty in [7, 11, 15, 28, 30, 37, 43]; and some deterministic algorithms, which do not add noise, have been shown to preserve privacy under this assumption [7, 11, 28].”
Resisting structural re-identification in anonymized social networks (2008, methodology): “Someworkhasconsideredhowdifferentialprivacycanbe applied to network data [13,18,36, 38 ].”
Differential Privacy for Statistics: What we Know and What we Want to Learn (2010, background): “[50] provides results for a more general class of counting queries, using a weakening of differential privacy (assuming that the adversary has a particular type of prior distribution on the underlying social network).”
Analyzing Graphs with Node Differential Privacy (2013, background): “Intuitively, edge differential privacy ensures that an algorithm’s output does not reveal the inclusion or removal of a particular edge in the graph, while node differential privacy hides the inclusion or removal of a node together with all its adjacent edges.”
Private analysis of graph structure (2011, methodology): “Our results, together with those of [9, 10], raise several interesting questions beyond those mentioned so far.”
Differentially private data analysis of social networks via restricted sensitivity (2012, background): “The privacy guarantees of [19] only hold if these assumptions about the adversaries prior are true.”
A workflow for differentially-private graph synthesis (2012, methodology): “Although graph-structure data can be viewed in a tabular form (each edge has a “source” and “destination” attribute), graph queries typically result in many Join operations over the tables, requiring excessive amounts of additive noise using standard tools [11].”