PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Differentially Private Analysis of Graph Statistics

Jacob Imola, Takao Murakami, Kamalika Chaudhuri

arXiv:2010.08688v2cs.CRcs.DB

TL;DR

The paper addresses private graph analysis when a trusted curator holding the entire graph is impractical. It develops local-DP algorithms for triangle and k-star counts, with error guarantees and experiments on two real datasets. The reported results include reduced triangle estimation error with an extra interaction round and order-optimal non-interactive k-star error.

  • Problem

    Many graph-analysis algorithms assume a trusted curator holds the entire graph, although a central holder may be impractical and graph statistics can reveal sensitive information.

    Source: §1 · p. 1

  • Method

    The paper develops local-DP algorithms and performance guarantees for triangle and k-star counts, including an interactive triangle method and a Laplacian-based k-star method.

    Source: §1 · p. 2

  • Results

    An additional interaction round significantly reduces triangle estimation error, the Laplacian k-star algorithm has order-optimal error in the non-interactive local model, and experiments on two real datasets report small relative errors, especially with many users.

    Source: §6 · p. 14

  • Takeaways & Limitations

    The experiments show that subgraph counts can be estimated with small relative errors under local differential privacy, especially when the number of users is large.

    Source: §6 · p. 14

    Relationship DP requires users to trust peers not to leak their shared edge; if k users deviate, up to k edges incident to a user may be compromised.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Differentially private analysis of graphs is widely used for releasing statistics from sensitive graphs while still preserving user privacy. Most existing algorithms however are in a centralized privacy model, where a trusted data curator holds the entire graph. As this model raises a number of privacy and security issues -- such as, the trustworthiness of the curator and the possibility of data breaches, it is desirable to consider algorithms in a more decentralized local model where no server holds the entire graph. In this work, we consider a local model, and present algorithms for counting subgraphs -- a fundamental task for analyzing the connection patterns in a graph -- with LDP (Local Differential Privacy). For triangle counts, we present algorithms that use one and two rounds of interaction, and show that an additional round can significantly improve the utility. For $k$-star counts, we present an algorithm that achieves an order optimal estimation error in the non-interactive local model. We provide new lower-bounds on the estimation error for general graph statistics including triangle counts and $k$-star counts. Finally, we perform extensive experiments on two real datasets, and show that it is indeed possible to accurately estimate subgraph counts in the local differential privacy model.

1 Introduction

The paper addresses private graph analysis when a trusted curator holding the whole graph is impractical, focusing on subgraph counts under local differential privacy. It develops triangle and k-star algorithms, error bounds, and experiments on two real datasets.

1 Introduction

  • A trusted curator holding the entire graph can be impractical, motivating local privacy approaches for analyzing sensitive graph statistics.Centralized graph analysis can face security or logistical obstacles, while graph statistics may leak sensitive information.Source: §1 · p. 1
  • Graph subgraph counting is challenging under LDP because overlapping subgraphs are dependent and users cannot observe edges between other users.For example, a user cannot count triangles involving herself when she cannot see the edge between two other users.Source: §1 · p. 2
  • For triangles, the paper presents one- and two-round algorithms and reports that the additional interaction can significantly reduce estimation error.The one-round method uses Warner’s randomized response and empirical estimation; the two-round method adds interaction between users and the collector.Source: §1 · p. 2
  • For k-stars, a Laplacian-mechanism algorithm achieves order-optimal estimation error in the non-interactive local model.Source: §1 · p. 2
  • The paper gives estimation-error lower bounds for general graph functions, including triangles and k-stars, illustrating limits of local relative to centralized analysis.Source: §1 · p. 2
  • Experiments on two real datasets report small estimation errors for the interactive triangle and Laplacian k-star algorithms when the user count is large.Source: §1 · p. 2

2 Related Work

Prior local-DP graph work does not address this paper’s subgraph-counting setting under its user-knowledge assumptions, and tabular-data methods do not directly transfer. The paper introduces estimation guarantees and compares triangle-counting approaches.

2 Related Work

  • Prior local-DP graph algorithms address synthetic graph generation and software usage analysis, but not subgraph counts.Source: §2 · pp. 2–3
  • Sun et al.’s subgraph-counting approach assumes users reveal all their friends’ connections, unlike this paper’s setting where users know only their own friends.Source: §2 · p. 3
  • The paper proves its one-round triangle estimate is unbiased and reports that its two-round algorithm significantly outperforms its one-round algorithm.The one-round algorithm also significantly outperforms Ye et al.’s algorithm [63] in Appendix A; Ye et al.’s bias-reduction method involves approximation, and its unbiasedness is unclear.Source: §2 · p. 3
  • Tabular-data bounds assume independent samples and do not directly apply to graph subcounts, whose motifs share edges; tabular-optimal RR with empirical estimation is suboptimal for triangle counts.Existing subgraph-counting work also differs by not providing estimation-error lower bounds.Source: §2 · p. 3

3 Preliminaries

The preliminaries specify the graph and privacy settings, distinguish two local edge-privacy definitions, describe sensitivity control, and define the statistics and utility metrics used in the paper.

3.1 Graphs and Differential Privacy

  • The paper studies undirected user graphs and distinguishes edge DP, which protects one edge, from node DP, which protects a node and its incident edges; it focuses on edge DP.The choice reflects applications where users may share their identity while wanting to hide relationship information.Source: §3.1 · p. 3

3.2 Local Differential Privacy

  • Edge LDP treats each user’s incident edge bit as a separate secret, whereas relationship DP treats the shared edge as one secret and requires some trust between users.If k users do not follow the relationship-DP protocol, up to k edges incident to a user may be compromised; edge LDP implies 2ε-relationship DP, while a lower-triangular randomized-response scheme can provide ε-relationship DP.Source: §3.2 · pp. 4–5

3.3 Global Sensitivity

  • Graph projection bounds maximum degree to reduce sensitivity, and the paper privately estimates dmax to set the projection cap without directly revealing the graph’s maximum degree.The private estimate is used as the cap d~max, a technique also known as adaptive clipping.Source: §3.3 · p. 5

3.4 Graph Statistics and Utility Metrics

  • The target statistics are triangle and k-star counts, evaluated with squared l2 loss in theory and relative error alongside l2 loss in experiments.The relative-error denominator uses max{f(G), η}, with η set to 0.001n for both statistics.Source: §3.4 · p. 5

4 Algorithms

This section develops one- and two-round locally differentially private algorithms for estimating k-star and triangle counts, including lower bounds on one-round graph-statistic estimation. It also examines the two-round triangle algorithm’s utility, efficiency, and communication tradeoffs.

4.1 One-Round Algorithms for k-Stars

  • LocalLap_k⋆ uses graph projection and Laplace noise to estimate k-star counts, achieving order-optimal expected l2 loss among one-round LDP algorithms.The guarantee assumes the graph's maximum degree is at most the projection bound; the paper also proves one-round algorithms cannot avoid the factor of n in expected l2 error.Source: §4.1 · pp. 6–7

4.2 One-Round Algorithms for Triangles.

  • Under the Erdös-Rényi model, LocalRR△ uses empirical estimation to remove bias, but its expected l2 loss is O(n^4), versus O(n) for LocalRR_k⋆.The utility analysis assumes G(n,α); the paper notes the upper bound does not cover all possible graphs.Source: §4.2 · pp. 7–8

4.3 Two-Rounds Algorithms for Triangles

  • Local2Rounds△ reduces triangle-count loss by having users count triplets with two known incident edges and one noisy edge, then correct the bias and add Laplace noise.It provides (ε1 + ε2)-edge LDP and (ε1 + ε2)-relationship DP.Source: §4.3 · pp. 8–9
  • An additional round reduces the triangle-count l2 loss from O(n^4), and estimating d_max privately can be incorporated without adding a round.With privacy budgets (ε0, ε1, ε2) = (0.1, 0.45, 0.45) or (0.2, 0.9, 0.9), the private-d_max version has almost the same utility as using the true maximum degree.Source: §4.3 · p. 9
  • The two-round triangle algorithm has time complexity O(n^2 + nd_max^2), while each user must receive a noisy graph of size O(n^2), creating communication overhead.The authors note that this overhead might limit use on very large graphs.Source: §4.3 · p. 10

4.4 Lower Bounds

  • The lower-bound analysis asks whether the factor of n in the one-round k-star estimator’s O(nd_max^(2k−2)) expected l2 loss is necessary and answers affirmatively for many queries.The comparison in the passage is with centralized Laplace-mechanism error of O(d_max^(2k−2)) for k-stars.Source: §4.4 · p. 10
  • Theorem 7 gives a lower bound for one-round estimators on statistics admitting an (n,D)-independent cube, and the paper applies this framework to k-star and triangle counts.For k-stars, the lower-bound construction uses a graph with maximum degree at most d_max; the section also reports a lower bound for triangle counts.Source: §4.4 · p. 11

5 Experiments

Experiments on IMDB, Orkut, and artificial graphs compare local and centralized estimators while varying user count and privacy budget. The two-round triangle method substantially improves on one-round randomized response, and the reported relative errors are small for large graphs under privacy budgets of 1 or 2.

5.1 Experimental Set-up

  • The experiments used sampled graphs from IMDB and Orkut, and initially assumed dmax was publicly available to assess the theoretical results.The paper also tested private calculation of dmax separately.Source: §5.1 · p. 11, §5.2 · pp. 12, 14

5.2 Experimental Results

  • About 10^2-fold lower l2 loss for triangle counts with Local2Rounds△ than LocalRR△; the gap is larger on the sparser Orkut graph.At n = 10000, average maximum degree was 73.5 in IMDB and 27.8 in Orkut.Source: Figure 5 · p. 12, §5.2 · p. 12
  • When ε fell from 0.4 to 0.1, l2 loss rose by about 5000 for LocalRR△, 200 for Local2Rounds△, and 16 for CentralLap△.These factors are reported as roughly consistent with the theoretical bounds for small ε.Source: §5.2 · pp. 12–13, Figure 7 · p. 13
  • Relative error decreases as n grows, while the local estimators' l2 loss scales as O(n), compared with O(1) for the centralized estimators.The text attributes the declining relative error to subgraph counts increasing at least proportionally with n.Source: §5.2 · pp. 13–14
  • Using a private estimate of dmax gives relative error close to using the true dmax and significantly better than setting ˜dmax = n.The authors conclude that dmax can be estimated privately without significant utility loss.Source: Figure 9 · p. 14, §5.2 · p. 14
  • At n = 200000 and ε = 1, relative error was 0.30 for triangles and 0.0028 for 2-stars; clustering-coefficient relative error was 0.30 at privacy budget 2.The clustering coefficient uses privacy budget 2 because both triangle and k-star counts must be estimated.Source: §5.2 · p. 14

6 Conclusions

The paper concludes that its LDP algorithms estimate triangle and k-star counts, with interaction improving triangle accuracy and a non-interactive Laplacian method achieving order-optimal error. Experiments on two real datasets found small relative errors, particularly with more users.

6 Conclusions

  • An additional interaction round significantly reduces triangle-count estimation error, while the Laplacian k-star algorithm has order-optimal error in the non-interactive local model.The paper also reports lower bounds for general graph functions including triangle and k-star counts.Source: §6 · p. 14
  • Experiments on two real datasets showed small relative errors for the algorithms, especially when the number of users is large.Source: §6 · p. 14
  • The authors identify counting other subgraphs, including cliques and k-triangles, as future work.Source: §6 · p. 14

A Effectiveness of empirical estimation in LocalRR△

The appendix compares LocalRR△, which applies empirical estimation after randomized response, with randomized response without that post-processing. The empirical-estimation version has significantly lower l2 loss in the reported experiments.

A Effectiveness of empirical estimation in LocalRR△

B Experiments on Barabási-Albert Graphs

Experiments on Barabási-Albert graphs show that the two-round triangle method outperforms the one-round method, especially on sparse graphs, and that observed losses broadly track theoretical upper bounds. The appendix passages also describe a graph construction and proof ingredients for results in Section 4.

B Experiments on Barabási-Albert Graphs

C Construction of an (n, dmax

  • The construction forms disjoint even-sized cliques, takes a perfect matching, and removes matching edges to create an independent cube for f△.Source: C Construction of an (n, dmax · p. 18

D Proof of Statements in Section 4

D.1 Proof of Theorem 1 / D.2 Proof of Theorem 2

  • Theorem 1's proof concludes that LocalLapk⋆ provides ε-edge LDP; Theorem 2's analysis assumes dmax ≤ ˜dmax so graph projection does not occur.Under that assumption, the proof treats Laplace noise as the algorithm's only randomness.Source: §D.1 · p. 19, §D.2 · p. 19

D.3 Proof of Proposition 2

The proof represents changes among four three-node subgraph types with a transition matrix, then uses it to estimate their counts. The resulting triangle-count estimate is unbiased.

D.3 Proof of Proposition 2

  • Q maps triangle, 2-edge, 1-edge, and no-edge types in G to types in G′.The proof describes Q as a transition matrix between these subgraph types.Source: §D.3 · p. 19
  • Cramer's rule expresses the empirical estimates of the four subgraph counts using Q⁻¹.The proof introduces the estimated count vector and identifies the entries of Q⁻¹ before deriving the estimates.Source: §D.3 · p. 19
  • The resulting triangle-count estimate is unbiased, yielding equation (4) in Proposition 2.The passage attributes unbiasedness to the empirical estimate and cites.Source: §D.3 · p. 19

D.4 Proof of Theorem 3

LocalRR△ applies randomized response to the lower triangular adjacency matrix and uses post-processing to establish its privacy guarantees.

D.4 Proof of Theorem 3

  • LocalRR△ provides ε-edge LDP and ε-relationship DP for its output.Randomized response on the lower triangular adjacency matrix provides ε-edge LDP; the remaining algorithm steps are post-processing, and each edge affects only one matrix entry.Source: §D.4 · p. 20

D.5 Proof of Theorem 4

The proof bounds the triangle estimator's variance under an Erdős–Rényi graph model by analyzing noisy subgraph counts. It also derives a correction for a two-round triangle-count statistic.

D.5 Proof of Theorem 4

  • The triangle estimator is unbiased, so its expected l2 loss is evaluated through bias–variance decomposition and bounds on its noisy subgraph-count variances.The proof assumes G follows G(n,α) when calculating those variances.Source: §D.5 · p. 20
  • V[m3] = O(β^5n^4 + β^3n^3), V[m2] = O(β^3n^4 + β^2n^3), and V[m1] = V[m0] = O(βn^4).The bounds assume G ∼ G(n,α), with p = 1/(e^ε+1) and β = α(1−p) + (1−α)p.Source: §D.5 · p. 20
  • The proof calculates joint-event probabilities for pairs of triangle or 2-edge triplets by classifying their overlap patterns.For pairs of 2-edge triplets sharing two vertices, it enumerates configurations and gives their joint probability as 4β^3(1−β)^2 + β^4(1−β).Source: §D.5 · pp. 20–21

D.6 Proof of Proposition 3

  • The two-round statistic t* counts triangles in expectation with weight 1−p1 and 2-edge triplets with weight p1; the proof uses this to recover f△(G).The passage defines p1 = 1/(e^ε1+1).Source: §D.6 · p. 21

D.7 Proof of Theorem 5

The proof analyzes neighboring adjacency lists across degree cases to establish the privacy guarantee of Local2Rounds△. The combined privacy parameter is ε1 + ε2.

D.7 Proof of Theorem 5

  • For neighboring inputs in the high-degree case, graph projection makes the corresponding adjacency lists differ in at most two bits.The proof also treats the low-degree case separately when establishing the second-round guarantee.Source: §D.7 · p. 22
  • Local2Rounds△ provides (ε1 + ε2)-edge LDP and (ε1 + ε2)-relationship DP in total.The proof combines the first- and second-round edge privacy guarantees and notes that the algorithm uses only the lower triangular adjacency matrix for relationship privacy.Source: §D.7 · p. 22

D.8 Proof of Theorem 6

The proof analyzes the two-round triangle estimator by showing it is unbiased and bounding its variance using properties of ordered 2-path counts.

D.8 Proof of Theorem 6

  • When dmax ≤ ˜dmax, no graph projection occurs, and the proof bounds the estimate using Proposition 3.It bounds the ordered 2-path counts by ˜dmax and uses a Jensen-style argument to maximize the relevant expression.Source: §D.8 · pp. 22–23
  • The Local2Rounds△ estimate of f△(G,ε) is unbiased.The proof states this after recalling that the first round releases noisy edges through randomized response.Source: §D.8 · p. 22
  • The variance analysis uses independent indicators for whether edges appear in the first-round noisy graph E′.The expression sums cjk times indicators for pairs (j,k), where cjk counts ordered 2-paths from j to k in G.Source: §D.8 · pp. 22–23

D.9 Proof of Theorem 7

The proof of Theorem 7 converts an independent cube over graph inputs into a Boolean independent cube over paired users. Theorem 8 then analyzes estimation error for such Boolean cubes under independent ε-DP randomizers.

D.9 Proof of Theorem 7

  • In the one-round Boolean setting, each user independently obfuscates one bit with an ε-DP randomizer, and an aggregate estimator uses the outputs.The randomizers may include Warner’s randomized response.Source: §D.9 · p. 23

D.10 Proof of Theorem 8

  • Theorem 8 applies to Boolean (κ,D)-independent cubes with independent ε-DP randomizers and a uniformly drawn Boolean input.It bounds the expected squared estimation loss, though the supplied theorem passage does not include the bound's formula.Source: §D.9 · p. 23

D.9 Proof of Theorem 7

  • This construction gives a one-to-one correspondence between the graph independent cube and a Boolean independent cube for g.Figure 13 illustrates the correspondence between a (4,2)-independent cube for f and a (2,2)-Boolean independent cube for g.Source: §D.9 · pp. 23–24, Figure 13 · p. 24
  • Pairing users matched by M creates κ virtual users, and each bit xi indicates whether their matching edge is added to G.The paired randomizer Si is the product of the outputs of the two users in the pair.Source: §D.9 · pp. 23–24
  • The proof concludes Theorem 7 by applying the Boolean-cube argument to the graph cube, with G drawn uniformly from A.The construction pairs vertices along a perfect matching M.Source: §D.9 · pp. 23–24

D.10 Proof of Theorem 8

  • Conditioned on the randomized outputs, the Boolean input bits are independent Bernoulli variables.Each conditional probability pi lies between 1/(1+e^ε) and e^ε/(1+e^ε), by ε-DP.Source: §D.10 · pp. 24–25

Related papers

Loading 2010.08688v2…