Source-linked AI summary
Differentially Private Data Analysis of Social Networks via Restricted Sensitivity
Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet
TL;DR
Differentially private analysis of social networks faces high global and smooth sensitivity for natural queries. The paper introduces restricted sensitivity and transforms queries using hypotheses and projections, finding substantially lower sensitivity for local profile and subgraph-counting queries under bounded-degree assumptions.
Problem
Natural social-network queries can have very large global and smooth sensitivity, complicating accurate differentially private analysis of labeled graphs.
Method
The paper restricts sensitivity to a hypothesized dataset class and constructs f_H, including efficient projection-based constructions for bounded-degree networks.
Results
Restricted sensitivity for local profile and subgraph-counting queries can be much lower than smooth sensitivity when H is the bounded-degree class Hk.
Takeaways & Limitations
The resulting mechanism preserves privacy for all inputs while providing good estimates when the network satisfies the hypothesis.
Takeaways & Limitations
The generic construction is inefficient, and vertex-adjacency projections face an NP-hard distance-approximation issue, requiring a relaxed projection to a superset of H.
Abstract
from arXiv · showhide
We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. The definition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets. Specifically, given a query f and a hypothesis H about the structure of a dataset D, we show generically how to transform f into a new query f_H whose global sensitivity (over all datasets including those that do not satisfy H) matches the restricted sensitivity of the query f. Moreover, if the belief of the querier is correct (i.e., D is in H) then f_H(D) = f(D). If the belief is incorrect, then f_H(D) may be inaccurate. We demonstrate the usefulness of this notion by considering the task of answering queries regarding social-networks, which we model as a combination of a graph and a labeling of its vertices. In particular, while our generic procedure is computationally inefficient, for the specific definition of H as graphs of bounded degree, we exhibit efficient ways of constructing f_H using different projection-based techniques. We then analyze two important query classes: subgraph counting queries (e.g., number of triangles) and local profile queries (e.g., number of people who know a spy and a computer-scientist who know each other). We demonstrate that the restricted sensitivity of such queries can be significantly lower than their smooth sensitivity. Thus, using restricted sensitivity we can maintain privacy whether or not D is in H, while providing more accurate results in the event that H holds true.
1 Introduction
The paper addresses high sensitivity in private social-network queries by using beliefs about network structure to restrict sensitivity. It introduces restricted-sensitivity mechanisms that preserve privacy generally, remain accurate when the hypothesis holds, and can outperform smooth sensitivity for key query classes.
- Motivation: Social-network data can reveal sensitive attributes, motivating differentially private release of statistics on labeled graphs.The paper models social networks as graphs whose vertices carry attributes.
- Motivation: Global and smooth sensitivity can both be very large for natural queries under edge or vertex adjacency.Examples include queries about people connected to doctors, where a single relabeling or edge change can produce a large answer difference.
- Restricted sensitivity: Restricted sensitivity measures query variation only over a hypothesized subset H of possible datasets, such as networks with maximum degree k.The motivating bounded-degree hypothesis uses k = 5000 ≪ n ≈ 9 × 10^8.
- Restricted sensitivity: A transformed query f_H agrees with f on H while its global sensitivity is comparable to f’s restricted sensitivity, enabling privacy-preserving answers with Laplace noise.The generic construction may be inefficient, but it preserves privacy even when the hypothesis is false and is accurate when the hypothesis holds.
- Efficient constructions: Projection-based constructions efficiently exploit bounded-degree hypotheses, avoiding a separate inefficient construction for every query.A projection maps arbitrary networks into H while fixing inputs already in H; suitable smoothness properties yield sensitivity guarantees tied to restricted sensitivity.
- Results: For local profile and subgraph-counting queries under bounded degree, restricted sensitivity can be much lower than smooth sensitivity.These query classes include neighborhood-based properties and counts of specified subgraphs such as triangles.
2 Preliminaries
The preliminaries define differential privacy, sensitivity, and the labeled-graph models used for social networks. They distinguish edge adjacency from the stronger vertex-adjacency model and characterize distances between networks.
- Differential Privacy: Differential privacy limits how distinguishable mechanism outputs are on neighboring datasets differing in one individual’s information.The framework uses local, global, and smooth sensitivity to calibrate privacy-preserving noise.
- Sensitivity: The Laplace mechanism with scale GS_f/ε preserves (ε, 0)-differential privacy, but high global sensitivity limits utility for many social-network queries.Local sensitivity may be lower, yet using it directly can leak information because the noise level itself depends on the dataset.
- Graphs and Social Networks: A social network is modeled as a graph with a vertex-labeling function that can encode attributes such as age, gender, or occupation.All networks use a common public vertex set of size n and a fixed label dimension m.
- Adjacency Models: Under edge adjacency, networks differ in one edge or one vertex’s attributes, whereas vertex adjacency permits changing one vertex and all incident edges.Vertex adjacency provides stronger privacy because it protects an individual’s entire network participation rather than one relationship or attribute.
- Distance and Privacy Strength: Any edge-adjacent networks are also vertex-adjacent, making useful utility guarantees under vertex adjacency substantially harder.Network distance counts label changes plus either edge edits or a vertex cover of the difference graph; computing the latter distance is NP-hard.
3 Restricted Sensitivity
Restricted sensitivity measures query variation only within a querier’s hypothesis about the dataset, while retaining the original adjacency distance. This can substantially reduce sensitivity when outside-hypothesis neighbors cause large changes.
- Definition: Restricted sensitivity evaluates a query over a hypothesis H, a subset of all possible datasets, rather than over every dataset.Because H need not be convex, the definition considers all pairs in H and uses their shortest-path distance in the full dataset space.
- Utility: Restricted sensitivity can be lower than local sensitivity for datasets in H when a high-impact neighboring dataset lies outside H.In such cases, it can also be significantly lower than a smooth upper bound on local sensitivity.
4 Using Restricted Sensitivity to Reduce Noise
The paper transforms queries using hypotheses and projections so that privacy is preserved on all inputs while accuracy and lower noise are obtained when bounded-degree assumptions hold. Efficient constructions are available for edge and vertex adjacency, though projection smoothness has important limits.
- Generic Construction: The generic construction creates f_H equal to f on H while making its global sensitivity exactly the restricted sensitivity over H.The construction is non-efficient and must be performed separately for each query.
- Projection Framework: A projection μ maps arbitrary inputs into H while fixing every input already in H, allowing any query to define f_H = f ◦ μ.This projection-based approach avoids constructing a separate generic extension for each query.
- Smooth Projections: For a c-smooth projection, GS_fH ≤ c · RS_f(H), linking the transformed query’s global sensitivity to restricted sensitivity.Smoothness bounds the distance between projections of neighboring databases.
- Edge Adjacency: An efficiently computable 3-smooth projection to bounded-degree graphs H_k exists under edge adjacency.The projection keeps a canonical first k incident edges per vertex and deletes later incident edges.
- Edge Adjacency: The edge-adjacency mechanism adds Lap(3·RS_f(H_k)/ε) noise and preserves (ε, 0)-privacy for every graph.For every G ∈ H_k, the mechanism answers within O(RS_f(H_k)/ε) of f(G) with probability at least 2/3.
- Projection Limits: Smooth projections do not always exist: in the toy example, no projection can be c-smooth for c < n.The obstruction follows because the projection must fix both endpoint graphs while changing between consecutive inputs somewhere along the path.
- Vertex Adjacency: Under vertex adjacency, an efficiently computable projection to H_2k and a 4-smooth distance estimator are available.The relaxed projection may map into a superset of H because efficiently approximating distance to H_k is constrained by NP-hardness.
- Vertex Adjacency: The vertex-adjacency mechanism preserves (ε, δ)-privacy using the projection and a smooth upper bound on transformed-query local sensitivity.The construction uses a smooth distance estimator to obtain the required sensitivity bound.
5 Restricted Sensitivity and Hk
For bounded-degree social networks Hk, restricted sensitivity can be far below smooth sensitivity for local profile and subgraph-counting queries. The section establishes explicit bounds and examples showing this gap when k is much smaller than n.
- Restricted sensitivity over Hk offers a significant advantage over smooth sensitivity when k ≪ n.
- Local profile queries: A local profile query sums a profile over all nodes, where each profile depends only on a node and its immediate neighborhood.Examples include clustering coefficients, local bridges, and queries about nearby labeled nodes.
- Local profile queries: RSf(Hk) ≤ 2k + 1 in the vertex adjacency model and RSf(Hk) ≤ k + 1 in the edge adjacency model for local profile queries.
- Local profile queries: Smooth sensitivity for a local profile query can be O(n) even on graphs in Hk.For the query counting people friends with a spy, a star graph is adjacent to an empty graph in Hk, forcing smooth sensitivity at least n − 1.
- Subgraph counting queries: A subgraph counting query counts labeled copies of a connected graph H within a social network.Examples include counting triangles, paths, and other labeled patterns.
- Subgraph counting queries: The smooth sensitivity of triangle counting can exceed n, whereas restricted sensitivity is bounded by the bounded-degree parameters.
- Subgraph counting queries: RSf(Hk) ≤ t k^(t−1) for subgraph counting queries in the edge adjacency and vertex adjacency models.
- Subgraph counting queries: For triangle counting, f(G) ≤ n k^2 on Hk while RSf(Hk) ≤ 3k^2 ≪ n k^2.The restricted-sensitivity bound is therefore much smaller than the reduced query range under the bounded-degree hypothesis.
6 Future Questions/Directions
The paper identifies open directions involving efficient projections, answering multiple queries, and choosing alternative structural hypotheses.
- Efficient Mappings: No efficiently computable O(1)-smooth projection to Hk is known, and improving the existing construction remains open.
- Multiple Queries: It remains open whether restricted sensitivity can accurately answer an entire class of queries using mechanisms such as BLR or Private Multiplicative Weights.
- Alternate Hypotheses: The paper asks which other natural hypotheses could restrict sensitivity and whether they permit efficiently constructed queries with low global or smooth sensitivity.
A Missing Proofs
The appendix supplies proof sketches for projection constructions, smooth sensitivity bounds, and restricted-sensitivity bounds for local profile and subgraph-counting queries.
- Projection constructions: An efficient edge-adjacency construction computes a 3-smooth projection to Hk by deleting edges according to a canonical ordering.
- Projection constructions: For neighboring graphs, the projection analysis bounds how the removed edges and distance estimates change under one edge or vertex modification.
- Smooth sensitivity construction: Given a projection µ and a smooth distance estimator, composing f with µ yields fH and an efficiently computable smooth upper bound on its local sensitivity.The bound is built from restricted sensitivity and the estimated distance to the hypothesis class.
- Smooth sensitivity construction: The proof establishes the upper bound by comparing projected neighboring inputs and then proves smoothness across neighboring databases.
- Smooth sensitivity construction: The resulting smooth bound can be computed by a simple optimization once the distance estimator is known.
- Local profile bounds: For local profile queries, a label change affects at most the changed vertex and its neighbors, while an edge change affects only nearby profiles.
- Local profile bounds: These locality arguments yield RSf(Hk) ≤ 2k + 1 for vertex adjacency and RSf(Hk) ≤ k + 1 for edge adjacency.
B Additional Claims
The paper develops projection-based constructions for bounded-degree graph hypotheses, while identifying computational limits and sensitivity barriers for private queries.
- Projection-based constructions: The projection reduction is based on minimum set cover, whose approximation hardness limits efficient projection quality.The construction encodes set-cover instances as labeled graphs so graph distance corresponds to minimum set-cover size.
- Projection-based constructions: An efficiently computable projection onto Hk exists with distance at most O(ln(k) d(G,Hk)).The projection maps graphs to bounded-degree graphs while approximately minimizing the distance to Hk.
- Projection-based constructions: A greedy projection algorithm deletes high-degree vertices and repeatedly removes incident edges from vertices with highest potential.The algorithm uses a guessed distance d and a potential function based on degrees exceeding k.
- Sensitivity lower bounds: The reduction may yield low smooth sensitivity over Hk, but no efficient algorithm is known for computing the required smooth upper bound.Thus, projection can address sensitivity structurally while leaving smooth-sensitivity computation computationally difficult.
- Sensitivity lower bounds: For triangle counting under vertex adjacency, any β-smooth upper bound on local sensitivity has a stated lower bound for every graph.The proof constructs neighboring graph transformations whose local sensitivity is at least n − 2, then applies the definition of smooth sensitivity.
C Local Profile Queries
Local profile queries extend vertex predicates to neighborhood structures, supporting analyses of clustering, bridges, and other social-network properties.
- Local profile queries: Local profile queries can study clustering coefficients, local bridges, and 2-betweenness in social networks.They generalize predicates by scoring vertices according to local network structure.
- Local profile queries: The clustering coefficient c(v) measures the probability that two randomly selected friends of v are friends with each other.The passage identifies c(v) as a local profile query and connects it to identifying teenage girls more likely to consider suicide.
- Local profile queries: A local bridge is an edge whose endpoints have no friends in common, and a local profile can score vertices by incident local bridges.Such profiles can support marketing analysis of network nodes.