PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy for the Protected (Only)

Michael Kearns, Aaron Roth, Zhiwei Steven Wu, Grigory Yaroslavtsev

arXiv:1506.00242v1cs.DScs.CRcs.CYcs.SI

TL;DR

The paper addresses how to analyze network data to identify targeted individuals while preserving privacy for protected individuals and limiting costly investigations. It develops noisy graph-search algorithms with formal privacy guarantees; experiments on real social-network data find almost as many targets as non-private counterparts. The authors describe the framework as a step toward explicit management of subgroup privacy trade-offs.

  • Problem

    The paper addresses the tension between analyzing citizens’ data for societal goals and protecting privacy when targeted status may require costly investigation.

    Source: §1 · p. 2

  • Method

    The framework uses noisy network-proximity statistics to prioritize status queries and provides privacy assurances for the protected subpopulation.

    Source: §1 · p. 3, §3 · pp. 6–7

  • Results

    On real social-network data, the algorithms find almost as many targeted individuals as non-private counterparts, quantifying the effectiveness cost of privacy.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The authors present the framework as a first step toward models that explicitly manage different privacy guarantees for different subgroups.

    Source: §1 · p. 4

    The algorithm class excludes some commonly used search algorithms because they conflict with the intended privacy protection for protected individuals.

    Source: §1 · p. 4

Abstract

from arXiv · show

Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a computational model that distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the targeted subpopulation). The goal is the development of algorithms that can effectively identify and take action upon members of the targeted subpopulation in a way that minimally compromises the privacy of the protected, while simultaneously limiting the expense of distinguishing members of the two groups via costly mechanisms such as surveillance, background checks, or medical testing. Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. These algorithms are natural variants of common graph search methods, and ensure privacy for the protected by the careful injection of noise in the prioritization of potential targets. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.

1 Introduction

The paper addresses the tension between analyzing citizens’ data for societal aims and protecting privacy, especially when identifying targeted individuals can require costly investigation. It proposes a framework and noisy graph-search algorithms that protect one subpopulation while seeking members of another.

1 Introduction

  • The model distinguishes protected individuals from targeted individuals, whose membership can be discovered through costly measures such as surveillance or medical testing.The model aims to limit the cost and extent of investigations while enabling action on targeted individuals.Source: §1 · pp. 2–3
  • The algorithms add noise to network-proximity statistics to prioritize which costly status bits to query within an investigation budget.Proximity measures can include the number of short paths from a vertex to known targets.Source: §1 · p. 3
  • The framework provides a quantitative privacy guarantee for this algorithm class, with privacy depending on the proximity statistic’s sensitivity to network changes.Source: §1 · p. 3
  • On real social-network data, the algorithms find almost as many targeted individuals as non-private counterparts, quantifying the effectiveness cost of privacy.The experiments assess privacy-preserving algorithms on real social-network data.Source: §1 · p. 4
  • The algorithm class excludes some commonly used search algorithms because they conflict with the intended privacy protection for protected individuals.Source: §1 · p. 4
  • The authors describe their framework as the first to assign qualitatively different privacy rights to explicit protected and targeted subpopulations.They also characterize their algorithms as the first to provide rigorous guarantees for the protected while enabling effective discovery of the targeted.Source: §1 · p. 4

2 Preliminaries

The preliminaries define privacy for network data in terms of changes to individuals’ incident edges, then adapt that guarantee to protect only the designated subpopulation. Because status investigations are limited, the search must use network edges to guide queries without revealing much about any protected individual’s edges.

2 Preliminaries

  • A limited investigation budget makes it necessary to use private network edges to guide status queries rather than investigate the entire population.The desired number of status-bit examinations is on the order of the targeted population, potentially much smaller than the protected population.Source: §2 · p. 4
  • Vertex differential privacy compares networks that differ by arbitrary rewiring of one vertex’s incident edges; its risk multiplier is e^ε.A smaller risk multiplier corresponds to a stronger privacy guarantee.Source: §2 · p. 5
  • Protected differential privacy holds the protected-target partition fixed and protects protected individuals’ edge sets, while targeted-target edges may change the output arbitrarily.The figure contrasts standard DP’s single-edge illustration with PDP’s lack of protection for edges between targeted individuals.Source: §2 · p. 5, Figure 1 · p. 6
  • The mechanism’s output is an ordered list of targeted individuals, abstracting away the subsequent action, which may be observable.Source: §2 · p. 6

3 Algorithmic Framework

The framework uses a Statistic of Proximity (SoP) to guide searches for targeted individuals while protecting the private network data of protected individuals. PTarget adds noise when searching for new target components and provides a privacy guarantee that depends on the number of components recovered.

3 Algorithmic Framework

  • A Statistic of Proximity (SoP) scores how close a vertex is to a set of targeted vertices; its sensitivity measures how much one protected vertex can affect a targeted vertex’s score.Examples include common-neighbor counts and counts of short paths.Source: §3 · pp. 6–7
  • In statistic-first search, the algorithm examines neighboring vertices in SoP order until every neighbor of the discovered target component is found to be protected.This discovers all targets in the seed’s connected component in the subgraph induced by targeted individuals.Source: §3 · p. 7
  • After completing a component, the non-private procedure ranks unexamined vertices by SoP against the discovered targets and examines them until it finds a seed for the next component.This new-component search is skipped in the final iteration.Source: §3 · p. 7
  • PTarget leaves statistic-first search unchanged and adds Laplace noise, scaled by SoP sensitivity and ε, before sorting unexamined vertices to find a new component.The noise scale is Lap(△(f)/ε).Source: §3 · p. 7
  • In the illustrated IMDB-network example, PTarget explores more diffusely than Target and finds an additional target subnetwork, while examining protected vertices as well.The noise’s primary purpose is protecting protected vertices.Source: Figure 2 · p. 8
  • PTarget recovers k connected components of the targeted subgraph with (k −1)·ε-protected differential privacy, whose cost grows with k rather than the number of individuals examined or identified.The statistic-first search stage need not be randomized for this guarantee; privacy cost can be small when targets occupy few connected components.Source: §3 · p. 8
  • Theoretical utility comparisons require an SoP that separates targets from protected individuals by a wide enough margin; the paper instead compares utility empirically.An infinitesimal margin can let PTarget’s noise erase the signal.Source: §3 · pp. 8–9

4 Experimental Evaluation

Experiments compare PTarget with Target on two real social-network datasets using generated targeted populations, finding PTarget favorable across three component-structure regimes.

4 Experimental Evaluation

  • Experiments use DBLP and IMDB networks with diffusion-generated targeted populations, varying component structure and measuring discoveries against investigation budget.PTarget uses common-neighbor count as its proximity statistic and adds Laplace(20) noise during new-component search.Source: §4 · p. 9
  • PTarget compares favorably with Target across three component-structure regimes, and its risk multiplier remains below 2.The regimes differ in the relative sizes of targeted components.Source: §4 · p. 10
  • With a few larger components and more even component sizes, both algorithms spend more budget searching outside the targeted population, and PTarget lags more.The private algorithm's lag is more detrimental when targeted components are smaller.Source: §4 · p. 10, Figure 4 · p. 11
  • When all targeted components are small, both algorithms spend most of their budget investigating non-targeted vertices and discover only a few targets.This highly fragmented case is shown in Figure 5.Source: §4 · p. 10, Figure 5 · p. 11
  • With one dominant targeted component, PTarget closely tracks Target after finding it, with a risk multiplier leveling off around 1.17.When the starting seed is outside the dominant component, PTarget lags slightly while racing to find it.Source: Figure 3 · p. 10, §4 · p. 10

A Model & Preliminaries

The model divides a network population into targeted and protected individuals and uses costly membership queries to guide targeted search. Protected differential privacy limits what the search reveals about protected individuals, while standard noise, composition, and post-processing tools support its analysis.

A Model & Preliminaries

  • The network is partitioned into fixed targeted and protected groups, and search starts from known targeted seeds to find additional targeted members.An identity oracle reveals a queried vertex’s group membership; because queries are costly, the graph guides which vertices to query.Source: A Model & Preliminaries · p. 13
  • The private data of each individual is their incident edges, and neighboring networks differ only in the edges of one protected individual.The targeted-induced edge set remains unchanged between neighboring networks.Source: A Model & Preliminaries · p. 14
  • Querying every vertex can identify all targets with zero protected privacy loss, but may be impractical or socially unacceptable, motivating graph-guided queries.The aim is to trade off the privacy parameter against the number of identity-oracle queries.Source: A Model & Preliminaries · pp. 13–14
  • The model does not guarantee privacy for information about targeted membership, because identifying targeted individuals is the search objective.The guarantee instead concerns the edge set incident to protected individuals.Source: A Model & Preliminaries · pp. 13–14
  • Protected differential privacy requires standard differential privacy on the input containing protected-incident edges, not on the targeted-induced edges.Lemma 1 states that differential privacy in the first argument implies protected differential privacy.Source: A Model & Preliminaries · pp. 14–15

A.1 Basic Privacy Tools

  • The basic toolkit includes sensitivity-calibrated Laplace noise and Report Noisy Max, alongside post-processing and composition results for analyzing privacy.Basic composition adds privacy parameters; advanced composition can make their growth sublinear in the number of mechanisms, with a small increase in δ.Source: §A.1 · pp. 15–16

B Statistics of Proximity (SoP)

Statistics of proximity score a vertex relative to already discovered targets and can be perturbed to guide search while protecting the protected population. Their targeted sensitivity and impact cardinality determine how much noise is needed and how many scores may change.

B Statistics of Proximity (SoP)

  • A statistic of proximity (SoP) scores a vertex relative to discovered targets, and noisy SoP values can guide search while protecting the protected population.Targeted sensitivity measures the maximum change in a targeted vertex’s score when a protected vertex’s adjacency list changes; it ignores changes to targeted edges and scores on protected vertices.Source: B Statistics of Proximity (SoP) · pp. 16–17
  • Low sensitivity and small impact cardinality are desirable because they allow privacy-preserving computations to add less noise.Impact cardinality counts how many vertices’ SoPs can change when one protected vertex’s adjacency list changes.Source: B Statistics of Proximity (SoP) · p. 17
  • For graphs with maximum degree d, Flow_k and Triangle have sensitivity at most d, while common neighbors has sensitivity at most 1.For Path_k, the bound is (k − 1)d^(k−1).Source: B Statistics of Proximity (SoP) · p. 17
  • Path_1 has targeted sensitivity zero because, on targeted vertices, it depends only on targeted-induced edges, which are unchanged between neighboring networks.This property is noted as important to the analysis.Source: B Statistics of Proximity (SoP) · p. 17

C SoP Based Targeting Algorithms

C.1 Statistic-First Search

Statistic-first search (SFS) starts from a known targeted seed and explores its targeted connected component. It satisfies 0-protected differential privacy, so this component can be found without privacy cost.

C.1 Statistic-First Search

  • Given a targeted seed, SFS explores the entire targeted connected component containing that seed.Source: §C.1 · p. 18
  • SFS inspects neighbors only after their node has been verified as targeted.The algorithm queries a candidate’s targeted status and, if positive, adds that vertex and its neighbors to the search frontier.Source: §C.1 · p. 18
  • SFS satisfies 0-protected differential privacy and can find the seed’s entire targeted connected component at no additional privacy cost.Its behavior depends only on the targeted nodes and targeted links.Source: §C.1 · p. 18

C.2 Private Search for Targeted Component

SearchCom searches for a new targeted seed after the current targeted component is exhausted. It ranks candidates using noisy proximity scores, queries in that order, and uses a perturbed stopping threshold; the resulting algorithm satisfies ε-protected differential privacy.

C.2 Private Search for Targeted Component

  • After a targeted component is exhausted, SearchCom seeks a seed in another component by ranking uninvestigated vertices with noisy SoP values and querying in descending order.It stops when it finds a targeted vertex or reaches a randomly perturbed query threshold.Source: §C.2 · pp. 18–19
  • The stopping threshold is perturbed with Laplace noise scaled by 2 IC(f)/ε, and the noisy SoP scores use scale 4∆(f)/ε.Source: §C.2 · p. 19
  • SearchCom satisfies ε-protected differential privacy.Its analysis divides privacy loss between noisy maximum selection and a noisy stopping-count release.Source: §C.2 · pp. 19–20
  • SearchCom’s privacy analysis treats the search as noisy target selection followed by a noisy count-based release, with each step ε/2 differentially private.The second step releases the number of protected vertices whose noisy scores meet or exceed the selected target’s score, adjusted by noise.Source: §C.2 · pp. 19–20

C.3 The Full Algorithm: Putting the Pieces Together

PTarget alternates between finding a targeted component with SFS and using SearchCom to find a seed for the next component. Theorem 2 states a protected differential privacy guarantee for the algorithm.

C.3 The Full Algorithm: Putting the Pieces Together

  • PTarget uses SFS to identify the targeted component containing a seed, then SearchCom to find a seed for the next component, repeating for k−1 rounds.The parameter k is the maximum number of disjoint targeted components to identify.Source: §C.3 · p. 20
  • Theorem 2 states that PTarget satisfies ε1-protected differential privacy.The supplied theorem statement does not specify the remainder of its guarantee.Source: §C.3 · p. 21
  • The privacy proof composes at most k 0-differentially private SFS calls and k−1 ε-differentially private SearchCom calls.SearchCom’s stated guarantee concerns edges incident on protected vertices.Source: §C.3 · p. 21

D.1 Subpopulation Construction

The experiments use DBLP and IMDB networks, sparsify them by removing low-weight edges, and generate targeted populations synthetically. The diffusion process is designed to produce nearby but disconnected targeted components.

D.1 Subpopulation Construction

  • The two experimental networks are DBLP, where edges represent coauthorship, and IMDB, where edges represent actors who appeared together in a movie.The nodes represent authors in DBLP and actors in IMDB.Source: §D.1 · p. 21
  • The networks are sparsified by removing edges with weights below 2, where weights count coauthored papers in DBLP and shared movies in IMDB.The stated purpose is to make it easier to generate multiple targeted components.Source: §D.1 · p. 21
  • Because the networks lack an identified targeted/protected partition, the experiments generate the targeted population synthetically through a diffusion process.The authors note that the infection framing is not specific to the motivating disease example.Source: §D.1 · p. 21
  • The synthetic population is designed to have multiple distinct connected components that are close to one another in the underlying network.This makes the search challenging while leaving network data useful for finding new targeted members.Source: §D.1 · p. 21
  • In each of k rounds, each neighbor of an infected node becomes infected independently with probability p; each infected node is then made immune with probability q.The retained non-immune infected nodes form the targeted population.Source: §D.1 · p. 22

D.2 Non-Private Benchmark Target

The experiments compare private and non-private targeting by the number of identify-oracle queries needed to find targeted members. The non-private benchmark uses common neighbors as its score of promise, whose targeted sensitivity is bounded by 1.

D.2 Non-Private Benchmark Target

  • The evaluation compares Algorithm 3 with a non-private version that uses the score of promise directly, measuring identify-oracle queries needed to find a given number of targeted members.The formal non-private algorithm tracks investigated nodes and searches for further seeds before applying SFS.Source: §D.2 · p. 22, §D.3 · p. 23

D.3 SoP Instantiations

  • The common-neighbor score of promise counts neighbors shared by a candidate node and the already discovered targeted set.The experiments use this score for SearchCom.Source: §D.3 · p. 22
  • The common-neighbor score has targeted sensitivity at most 1, because changing edges associated with a protected node can change the relevant intersection by at most one node.The proof compares neighboring networks that differ only in edges associated with a protected node.Source: §D.3 · pp. 22–23
Loading 1506.00242v1…