acceptodds
Under review as a conference paper at ICLR 2027

Distributed Randomized Sampling for Locally Private Independent Sets

Abstract

Many randomized distributed graph algorithms rely on simple local rules and few communication rounds, making them natural starting points for locally private protocols. We explore this connection through the maximum independent set problem under local edge differential privacy. Previous work shows that an edge-private algorithm that always publishes a valid independent set can select at most one vertex. We therefore allow edges between selected vertices and count each such edge as a defect. We develop a noninteractive -local edge-private algorithm that samples vertices independently using privately perturbed degrees. For fixed and -vertex graphs with bounded average degree or degeneracy, the expected output size of our algorithm is and the expected defect count is . Moreover, we also show that the ratio of defects to output size tends to zero with high probability. For a fixed and sufficiently large , we also prove that any -edge-DP or -edge-LDP algorithm achieving an expected approximation ratio on every -vertex graph with at most edges must incur expected defects on some graph in this class. For , the lower and upper bounds on the expected defect count match asymptotically.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Local Differential Privacy, Distributed Graph Algorithm, Independent Set

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pAeZOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the Maximum Independent Set (MIS) problem under local edge differential privacy (LDP). Since prior work shows that any edge-private mechanism guaranteed to output a strictly valid independent set can select at most one vertex, the authors explore two relaxations. First, they observe that Boppana's random-priority algorithm naturally satisfies local edge privacy in the billboard model when users keep their membership decisions private. Second, for standard non-interactive public release, they relax strict independence by counting induced edges within the selected set as "defects". They propose a one-bit sampling protocol where each user independently perturbs their degree with Laplace noise and a logarithmic positive shift before sampling a membership bit. They also derive matching asymptotic lower bounds on expected defects for sparse graphs and evaluate the method against a randomized response baseline.

Critical strengths
  • Clean and tight theoretical characterization: The main appeal of the paper is its self-contained theoretical story. On sparse graphs, the upper bound on expected defects achieved by the proposed one-bit sampler asymptotically matches the derived information-theoretic lower bound.

  • Minimal communication and high scalability: The algorithm is non-interactive and requires only one bit of communication per user, making it computationally lightweight and easily scalable to larger graphs where full-graph perturbation baselines struggle.

Critical weaknesses
  • Limited technical depth and low relevance to ICLR: While the proofs are clean, the technical contribution feels quite thin for a top machine learning venue. Observing that Boppana's algorithm is private in the billboard model is nearly trivial because the public transcript (a random permutation) is completely independent of the graph. Furthermore, the core algorithm is a straightforward combination of the standard Laplace mechanism on node degrees, a logarithmic shift, and independent Bernoulli sampling, relying entirely on elementary probability bounds. The paper also lacks a meaningful connection to representation learning or modern machine learning problems.
  • Severe practical utility bottleneck and a strawman baseline: To suppress false selections caused by negative Laplace noise, the algorithm adds a large logarithmic shift to every node's degree. In practice, this heavily penalizes the sampling probability even for low-degree nodes, resulting in very small output sets on finite graphs. Moreover, the only experimental baseline (RR+Greedy) flips every possible node pair across the entire graph. Applying naive randomized response to all node pairs in a sparse graph introduces a massive number of false-positive edges that destroy the graph structure. Outperforming such a weak baseline does not convincingly demonstrate practical utility.
Questions for authors
  • Clarification Requests:
    1. Comparison against stronger sparse-graph baselines: How does Algorithm 1 perform against more reasonable baselines, such as combining greedy selection with communication-efficient sparse graph LDP mechanisms (which you briefly mention as future work), or a simple two-round protocol where a portion of the privacy budget is used to resolve local conflicts?
    2. Utility under matched defect budgets: Because your method and RR+Greedy operate in very different size-defect regimes, have you compared their output sizes when post-processing (e.g., vertex subsampling) is applied to force both methods to have the exact same expected defect count?
  • Suggestions for Future Work:
    1. Exploring multi-round interactive protocols could be a much more promising direction to reduce the heavy logarithmic degree shift and improve practical utility on finite graphs.
4 comments
AuthorsOpenReview ↗

Thank you very much for your helpful comments and questions.

We thank the reviewer for their helpful comments and questions.

"the algorithm adds a large logarithmic shift to every node's degree. In practice, this heavily penalizes the sampling probability even for low-degree nodes, resulting in very small output sets on finite graphs."

On the shift: small outputs are unavoidable for any private algorithm that keeps defects small, not an artifact of our shift. Theorem 4.1 shows that any edge-DP or edge-LDP algorithm with approximation ratio rr must incur Ω(n/r2)\Omega(n/r^2) expected defects, even on graphs with at most nn edges. Making defects a vanishing fraction of the output therefore forces a growing approximation ratio, that is, a smaller output. At r=Θ(log⁡n)r=\Theta(\log n), our algorithm matches this bound: no private algorithm can select more vertices, by more than a constant factor depending on ε\varepsilon, while keeping O(n/log⁡2n)O(n/\log^2 n) defects. The shift is the parameter that chooses a point on this unavoidable trade-off. Privacy holds for every cc, and a smaller shift selects more vertices at the cost of more defects. The default c=⌈4ε−1log⁡n⌉c=\lceil 4\varepsilon^{-1}\log n\rceil is the choice at which defects become a vanishing fraction of the output.

"the only experimental baseline (RR+Greedy) flips every possible node pair across the entire graph. [...] Outperforming such a weak baseline does not convincingly demonstrate practical utility."

On the baseline: we agree that randomized response over all pairs is weak on sparse graphs. We use it because it is the standard general-purpose mechanism for edge LDP (Imola et al., 2021) and, to our knowledge, there is no existing locally private baseline for independent sets. Our main claims do not rest on outperforming it. They are the matching upper and lower bounds above, and the experiments illustrate the size–defect trade-off rather than a uniform win; RR+Greedy has fewer defects in most settings. Nor would a more efficient implementation of randomized response give a stronger baseline. The communication-efficient realization for sparse graphs (Hillebrand et al., 2026) produces exactly the same output as randomized response but incurs more privacy loss. At the same privacy budget, RR+Greedy built on it can therefore only perform worse; it improves communication and running time, not utility.

"simple two-round protocol where a portion of the privacy budget is used to resolve local conflicts?"

On a two-round protocol: a second round can reduce defects, but only by a constant factor. Split the budget as ε=ε1+ε2\varepsilon=\varepsilon_1+\varepsilon_2. Round 1 runs our algorithm with ε1\varepsilon_1. The curator then publishes SS and a random priority order, and each candidate reports, by randomized response with ε2\varepsilon_2, whether it has a higher-priority neighbour in SS. Let p=eε2/(1+eε2)p=e^{\varepsilon_2}/(1+e^{\varepsilon_2}). A defect survives with probability at most p(1−p)p(1-p), whereas thinning SS with retention probability pp keeps it with probability p2p^2. At essentially the same output size, the second round therefore has about e−ε2e^{-\varepsilon_2} times as many defects. However, Theorem 4.1 applies to any edge-DP mechanism, interactive or not, because it only uses the privacy of the released set. No number of rounds can beat the Ω(n/r2)\Omega(n/r^2) trade-off, which our one-round algorithm already attains up to constants. We focus on the noninteractive one-bit setting because extra rounds add privacy loss through composition and require users to stay online. We have added a remark after Corollary 4.2 noting that the lower bound covers interactive protocols, with the two-round variant as an example.

AuthorsOpenReview ↗

Regarding relevance and technical depth

We thank the reviewer for these points.

"The paper also lacks a meaningful connection to representation learning or modern machine learning problems."

On relevance: differentially private graph algorithms are a recurring topic at ICLR and NeurIPS. For example, He, Fichtenberger, and Peng (ICLR 2024) give a private clustering algorithm for well-clustered graphs, together with a lower bound for pure DP. Chen et al. (NeurIPS 2023) privately recover stochastic block models, Epasto et al. (NeurIPS 2022) study private graph learning via personalized PageRank, and Fan, Li, and Li (NeurIPS 2022) and Zou et al. (NeurIPS 2025) privately release shortest-path distances. Our paper belongs to this line of work. Its output is also directly useful for learning on private social data. In A/B testing on a social network, a set with few internal edges limits spillover between treated users (Ugander et al., 2013), and edge privacy protects exactly the friendships that define those edges.

"While the proofs are clean, the technical contribution feels quite thin for a top machine learning venue."

On technical depth: we agree that the billboard observation for Boppana's algorithm is simple. We present it as a baseline showing that whether the output is public determines what is achievable, not as a main contribution. The technical core is the size–defect trade-off. Theorem 4.1 shows that any edge-DP or edge-LDP algorithm with approximation ratio rr must incur Ω(n/r2)\Omega(n/r^2) expected defects, even on graphs with at most nn edges. Its proof charges the privacy constraint to every pair of vertices of a random graph. At r=Θ(log⁡n)r=\Theta(\log n), this matches the upper bound of Corollary 3.3, so the defect rate of our algorithm cannot be improved beyond constants depending on ε\varepsilon. The simplicity of the algorithm is therefore a strength: it sends one bit per user in a single round, which avoids the privacy loss of composing several messages, and still attains this rate.

Thank you for the detailed rebuttal and the additional comparisons. The new results address part of my concern about the experimental baselines. In particular, the comparisons at matched expected output size provide evidence that degree-dependent sampling can reduce defects relative to uniform sampling on heterogeneous graphs. I also appreciate the explicit acknowledgment that uniform sampling already achieves the stated worst-case sparse-graph rates, and that the simpler direct Bernoulli rule achieves comparable guarantees and empirical performance.

I have reconsidered the weight of my original criticism concerning simplicity and venue relevance. A simple algorithm is not inherently a weakness, and the lower-bound contribution deserves credit independently of the sophistication of the upper-bound construction.

However, my main reservation about the algorithmic contribution remains. The additional results support the value of degree adaptation, but do not establish an advantage of the Laplace-based construction over the direct Bernoulli rule. Moreover, the worst-case lower bound does not establish that the default shift is practically optimal on the evaluated instances. The response also does not provide the requested comparison including RR+Greedy at matched expected defect budgets.

Overall, the rebuttal improves the paper's positioning and provides meaningful additional evidence. I am therefore raising my rating from **1 to 2 **, while remaining below the acceptance threshold because the incremental algorithmic contribution and practical benefits are still insufficiently established.

We thank the reviewer for the follow-up.

"[...] do not establish an advantage of the Laplace-based construction over the direct Bernoulli rule."

The direct rule did not exist before this review; Reviewer NcmJ suggested it as a simplification of our algorithm. Our contribution is to modify Boppana's algorithm for independent sets under edge LDP: we replace its random ordering with a degree-based selection, where each user selects itself with a probability decreasing in its degree and sends one bit. The direct rule is another implementation of this selection. We credit the reviewer for it, and we hope that a variant of our own algorithm is not counted against our contribution.

"[...] does not establish that the default shift is practically optimal on the evaluated instances."

We do not claim that the default shift is optimal on every instance, and this is not the right target here. The best shift for an instance depends on the private graph, so a private algorithm must fix its shift without seeing the input. For a fixed shift, the right benchmark is the worst case, and our default cε=⌈4ε−1log⁡n⌉c_\varepsilon=\lceil4\varepsilon^{-1}\log n\rceil is optimal in this sense. Theorem 3.2 gives its guarantee, and Theorem 4.1 shows that no edge-LDP algorithm can improve it on sparse graphs by more than a constant factor. Privacy holds for every c≥0c\ge0, so a user who wants more vertices and accepts more defects can simply choose a smaller cc. We will clarify this in the revision.

"[...] comparison including RR+Greedy at matched expected defect budgets."

We do not aim to beat RR+Greedy when a small set suffices. RR+Greedy outputs only O(log⁡n)O(\log n) vertices w.h.p., and thinning cannot enlarge a set, so it cannot reach our Ω(n/log⁡n)\Omega(n/\log n) sizes at any budget. When a large set is needed, our algorithm is the one to use, and it sends one bit per user instead of Θ(n2)\Theta(n^2). We have clarified this point at the end of Section 5.4, and we wanted to reply you for this point in the previous reply. Unfortunately, we forgot to post that reply. Please accept our apologies for that.

Reviewer_ijkLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study independent set problem in the setting with local differential privacy. It is well known that independent set is trivially hard in the classical DP setting: no epsilon-DP algorithm can output more than one vertex. Therefore, the authors study two relaxed versions:

  • version with billboard, where the agents combine a differentially private public transcript which they use to compute personalized outputs, but this output is not published afterwards. Here, one can easily see that there is a 0-DP algorithm for independent set.
  • defect model: here, the final solution does not need to be an independent set, strictly speaking, but it comes with a guarantee of having small number of edges in its induced graph. This setting is less trivial: They propose an algorithm which outputs Ω(n/log⁡n)\Omega(n/\log n) vertices with at most O(n/log⁡2n)O(n/\log^2n) edges between them. Note that the number of edges is asymptotically smaller than the number of vertices.
Critical strengths
  • the paper is clearly written
  • it is an interesting view on the independent set problem in locally DP setting, including the connections to distributed algorithms
Critical weaknesses
  • their result in the billboard setting is rather straightforward
Questions for authors
  • is there some motivation for obtaining such independent set with defects beyond the fact that one cannot get anything better in the DP setting?
3 comments
AuthorsOpenReview ↗

Thank you for your comment about the motivation of our work.

"Is there some motivation for obtaining such independent set with defects beyond the fact that one cannot get anything better in the DP setting?"

We thank the reviewer. Beyond the impossibility result, defects are natural whenever the cost of a solution grows with the number of conflicts instead of being all-or-nothing. In wireless scheduling, an edge between two selected transmitters is one collision, which costs one retransmission. In A/B testing on a social network, treated users should be pairwise unconnected to limit spillover, and each edge inside the treated set adds a small bias [Ugander et al., 2013], and the social graph is exactly the kind of data that edge privacy protects. In both cases, the defect count e(S)e(S) directly measures the cost, which is why we count defects edge by edge. We have added this motivation to the introduction.

thank you for your response, I maintain my score.

Thank you very much for your kindness in confirming our response and maintaining your score.

Reviewer_NcmJOpenReview ↗
Rating
3(+1)
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies how to find an independent set under local edge differential privacy (LEDP). The authors distinguish between the billboard model (where nodes keep their membership bits private) and public release of the vertex set, where privacy forces the output to contain some conflicting edges ("defects"). Their proposed algorithm adds shifted Laplace noise to each vertex's degree and has each vertex broadcast a single sampled membership bit. For graphs with bounded average degree and constant ε\varepsilon, they prove an expected set size of Ω(n/log⁡n)\Omega(n / \log n) with O(n/log⁡2n)O(n / \log^2 n) expected defect edges. On the lower-bound side, they show that any private mechanism achieving an expected rr-approximation on graphs with ∣E∣≤n\vert{}E\vert{} \le n must suffer Ω(n/r2)\Omega(n / r^2) expected defects. They also compare their sampler empirically against randomized response plus greedy selection (RR+Greedy).

Critical strengths

-The lower bound (Theorem 4.1) is a nice result that holds even against centralized edge-DP algorithms with correlated outputs, using sparse graphs of average degree at most 2. The reduction in Lemma B.1 connecting edge privacy to the probability of picking both endpoints of an edge under a random graph distribution is clean, and bounding the complement handles the sparsity restriction well.

-The paper is very careful with its privacy and error definitions. It properly separates flipping a single bit in one node's adjacency list from adding/removing an undirected edge (which touches two nodes and introduces a factor of 2 in central DP), and clearly distinguishes total induced defect edges from max per-vertex degree in the induced subgraph.

Critical weaknesses

-The main upper bounds on sparse graphs (∣E∣≤n\vert{}E\vert{} \le n) can be achieved without looking at the graph at all. Suppose every vertex simply joins SS independently with probability p=1/rp = 1/r. This requires zero privacy budget (ε=0\varepsilon = 0) and immediately gives: E∣S∣=nr≥α(G)r,E[e(S)]=∣E∣r2≤nr2(∣E∣≤n).\mathbb{E}\vert{}S\vert{} = \frac{n}{r} \ge \frac{\alpha(G)}{r}, \quad \mathbb{E}[e(S)] = \frac{\vert{}E\vert{}}{r^2} \le \frac{n}{r^2} \quad (\vert{}E\vert{} \le n). This trivial blind sampler matches your lower bound across the entire range of rr, and plugging in r=log⁡nr = \log n recovers the exact asymptotic rates of Corollary 3.3 (with standard Chernoff and Markov bounds giving the high-probability vanishing defect-to-size ratio). While the lower bound itself is interesting, the fact that blind uniform sampling matches it means these bounds don't actually demonstrate any benefit from your Laplace degree-perturbation step.

-Even for the degree-adaptive bounds (Theorem 3.2), you don't need Laplace noise. Suppose each vertex vv directly samples and sends a single Bernoulli bit with probability qv=1dv+Cq_v = \frac{1}{d_v + C} for C≥1+1/εC \ge 1 + 1/\varepsilon. Between neighboring degrees dd and d+1d+1, the likelihood ratios for outputting 1 or 0 are 1+1d+C1 + \frac{1}{d+C} and 1+1(d+C)2−11 + \frac{1}{(d+C)^2 - 1}, both of which are at most 1+ε≤exp⁡(ε)1 + \varepsilon \le \exp(\varepsilon). This uses 1 bit of communication, satisfies your exact local privacy definition, and with C=c+1/ε+1C = c + 1/\varepsilon + 1, gives expected size exactly Σ\Sigma and expected defects: E[e(S)]=∑uv∈Equqv≤12∑vdvqv2≤Σ2,E[e(S)]≤∣E∣C2\mathbb{E}[e(S)] = \sum_{uv \in E} q_u q_v \le \frac{1}{2} \sum_v d_v q_v^2 \le \frac{\Sigma}{2}, \quad \mathbb{E}[e(S)] \le \frac{\vert{}E\vert{}}{C^2} This bound of min⁡{Σ/2,∣E∣/C2}\min\{\Sigma/2, \vert{}E\vert{}/C^2\} is actually sharper than what Theorem 3.2 proves for Algorithm 1. Because the experiments omit both uniform sampling and this direct Bernoulli rule—and compare algorithms at different defect levels—it is unclear what adding Laplace noise before sampling actually buys us theoretically or empirically.

Questions for authors

-Does the direct Bernoulli sampler qv=1dv+Cq_v = \frac{1}{d_v + C} satisfy your local privacy model and achieve the tighter utility bounds above? If so, what specific advantage does Algorithm 1's Laplace perturbation step provide, and how should the algorithmic contribution be framed?

-How do Algorithm 1, direct Bernoulli sampling, blind uniform sampling, and RR+Greedy compare when evaluated at the same expected defect budget (e.g., by plotting full size–defect curves using the public thinning step described on p. 6)?

5 comments
AuthorsOpenReview ↗

Comparison with Uniform Sampling

"The main upper bounds on sparse graphs (∣E∣≤n|E|\le n) can be achieved without looking at the graph at all. [...] the fact that blind uniform sampling matches it means these bounds don't actually demonstrate any benefit from your Laplace degree-perturbation step."

We thank the reviewer for this observation, with which we agree.

Notation.

  • SS is the released set.
  • e(S)e(S) is its defect count: the number of edges with both endpoints in SS.
  • n=∣V∣n=|V|, and dvd_v is the degree of vertex vv.
  • ε\varepsilon is the privacy budget, and c=⌈4ε−1log⁡n⌉c=\lceil 4\varepsilon^{-1}\log n\rceil is the public degree shift in Algorithm 1.
  • Uniform sampling keeps each vertex independently with a fixed probability pp.

Corollary 3.3 uses only the ∣E∣/(c/2+1)2|E|/(c/2+1)^2 term of Theorem 3.2. Uniform sampling attains that term at zero privacy cost. In fact, on a regular graph every vertex of Algorithm 1 has the same inclusion probability, so its output has exactly the distribution of uniform sampling. We now state this explicitly at the end of Section 3 in the new PDF. The noisy degree helps when degrees are non-uniform, as we now will now show below (and in the new PDF).

Theory. Let a=c/2+1a=c/2+1 and hv=(dv+a)−1h_v=(d_v+a)^{-1}. Lemma A.3 gives P(v∈S)≤hv+1/(2n2)P(v\in S)\le h_v+1/(2n^2). The proof of Lemma A.4, together with huhv≤(hu+hv)/(2a)h_uh_v\le(h_u+h_v)/(2a), gives (Lemma C.1) E[e(S)]≤12a2∑vmin⁡(dv,a)+1n.\mathbb E[e(S)]\le \tfrac{1}{2a^2}\textstyle\sum_v\min(d_v,a)+\tfrac1n . In this bound, a vertex contributes at most 1/(2a)1/(2a) however large its degree is. Under uniform sampling, it contributes p2dv/2p^2d_v/2.

Suppose the degrees follow a power law with exponent β>1\beta>1 up to a cutoff nδn^\delta, where δ∈(0,1]\delta\in(0,1]. That is, the number of vertices with degree ≥x\ge x is O(nx1−β)O(nx^{1-\beta}) for all xx, and Θ(nx1−β)\Theta(nx^{1-\beta}) for 1≤x≤nδ1\le x\le n^\delta. Then our expected size is Θ(n/log⁡n)\Theta(n/\log n), and at the same expected size (Proposition C.2):

  • if β=2\beta=2, our defects/size is O(log⁡log⁡n/log⁡n)→0O(\log\log n/\log n)\to0, while uniform's stays Θ(1)\Theta(1);
  • if 1<β<21<\beta<2, uniform sampling has Ω~(nδ(2−β))\tilde\Omega(n^{\delta(2-\beta)}) times our defects.

For fixed β>2\beta>2 (bounded average degree), the gain is only a constant factor. This is consistent with the reviewer's worst-case remark.

Experiments (Appendix C.3). We used 15 SNAP graphs with ε=1\varepsilon=1. We computed E∣S∣\mathbb E|S| and E[e(S)]\mathbb E[e(S)] exactly by integrating over the Laplace noise, and they match Monte Carlo runs. Uniform sampling is given the oracle pp that matches our expected size. It then has these multiples of our defects:

Graphwiki-Votesoc-Epinions1email-Enroncom-Youtubeloc-Gowallacom-DBLProadNet-PA
Defects, uniform / ours5.4×3.9×2.9×2.5×2.1×1.4×1.0×

The gain tracks degree heterogeneity. Road networks have nearly uniform degrees, and there the two methods tie. The ratio grows with ε\varepsilon, up to 16×16\times at ε=4\varepsilon=4.

We also used Chung-Lu random graphs with the expected degrees coming from the power-law. With β=2\beta=2, the ratio grows from 2.0×2.0\times to 3.6×3.6\times as nn goes from 10410^4 to 10610^6.

Revision. We have revised the paper accordingly:

  1. A new paragraph at the end of Section 3 notes that its rates are achieved by uniform sampling and summarises the comparison.
  2. A new Appendix C contains Lemma C.1, Proposition C.2 with a full proof, and the full experimental results (Tables 3 and 4).
AuthorsOpenReview ↗

The Bernoulli rule

"Even for the degree-adaptive bounds (Theorem 3.2), you don't need Laplace noise. [...] it is unclear what adding Laplace noise before sampling actually buys us theoretically or empirically."

We thank the reviewer. We agree, and in fact Algorithm 1 is itself a direct Bernoulli rule.

Both algorithms send the same kind of message. The noise LvL_v never leaves user vv. User vv's message is therefore a single bit zv∼Bernoulli(gc(dv))z_v\sim\mathrm{Bernoulli}(g_c(d_v)), independent across users, where gc(d)=E[1max⁡(d+c+L,0)+1],L∼Lap(1/ε).g_c(d)=\mathbb E\Big[\frac{1}{\max(d+c+L,0)+1}\Big],\qquad L\sim\mathrm{Lap}(1/\varepsilon). Both algorithms keep each vertex independently with a probability that depends only on its degree. The only difference is in the function: 1/(d+C)1/(d+C) for the reviewer's rule and gc(d)g_c(d) for ours. The Laplace step is one way to obtain such a probability with privacy by post-processing, and it does not change the form of the output.

The two functions are nearly the same. Lemmas A.2 and A.3 give 1d+c+1/ε+1≤gc(d)≤1d+c/2+1+12n2.\frac{1}{d+c+1/\varepsilon+1}\le g_c(d)\le\frac{1}{d+c/2+1}+\frac{1}{2n^2}. With C=c+1/ε+1C=c+1/\varepsilon+1, the reviewer's probability equals our lower bound, so the two rules have the same size and defect rates. Also numerically, gc(d)g_c(d) is very close to 1/(d+c+1)1/(d+c+1). On every graph considered below, the direct rule needs CC between c+0.89c+0.89 and c+0.99c+0.99 to match our expected size.

Experiments at different defect levels. We used the 15 SNAP graphs mentioned above, and computed exact expectations. For each shift cc, we chose CC so that the direct rule has the same expected size as Algorithm 1, then compared expected defects.

  • At the default shift c=⌈4ε−1log⁡n⌉c=\lceil 4\varepsilon^{-1}\log n\rceil, the two defect counts agree within 0.05%0.05\% on every graph, for ε∈{0.5,1,2,4}\varepsilon\in\{0.5,1,2,4\}.
  • At ε=1\varepsilon=1, we varied cc from 1/81/8 to 22 times the default, which moves our defects/size ratio from 0.010.01 to 0.220.22. The two defect counts agree within 1.6%1.6\% throughout.

The comparison with uniform sampling in our previous response therefore applies equally to the direct rule.

Revision. We have revised the paper accordingly:

  1. A new paragraph at the end of Section 3 states that Algorithm 1 is a degree-dependent Bernoulli sampler and introduces the reviewer's rule. We credit the reviewer in the acknowledgements.
  2. A new Appendix D contains Proposition D.1 (privacy of the direct rule, and that Theorem 3.2 and Corollary 3.3 hold for it) and the experiments above (Tables 5 and 6).

As the author–reviewer discussion period will end in two days, we would like to kindly follow up. Please let us know if you have any further questions or concerns regarding our paper. We would be happy to address them before the discussion period concludes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.