- 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:
- 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?
- Utility under matched defect budgets: Because your method and
RR+Greedyoperate 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:
- 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
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 must incur expected defects, even on graphs with at most edges. Its proof charges the privacy constraint to every pair of vertices of a random graph. At , this matches the upper bound of Corollary 3.3, so the defect rate of our algorithm cannot be improved beyond constants depending on . 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 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 , so a user who wants more vertices and accepts more defects can simply choose a smaller . 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 vertices w.h.p., and thinning cannot enlarge a set, so it cannot reach our 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 . 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.
Thank you very much for your helpful comments and questions.
We thank the reviewer for their helpful comments and questions.
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 r must incur Ω(n/r2) expected defects, even on graphs with at most n edges. Making defects a vanishing fraction of the output therefore forces a growing approximation ratio, that is, a smaller output. At r=Θ(logn), our algorithm matches this bound: no private algorithm can select more vertices, by more than a constant factor depending on ε, while keeping O(n/log2n) defects. The shift is the parameter that chooses a point on this unavoidable trade-off. Privacy holds for every c, and a smaller shift selects more vertices at the cost of more defects. The default c=⌈4ε−1logn⌉ is the choice at which defects become a vanishing fraction of the output.
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.
On a two-round protocol: a second round can reduce defects, but only by a constant factor. Split the budget as ε=ε1+ε2. Round 1 runs our algorithm with ε1. The curator then publishes S and a random priority order, and each candidate reports, by randomized response with ε2, whether it has a higher-priority neighbour in S. Let p=eε2/(1+eε2). A defect survives with probability at most p(1−p), whereas thinning S with retention probability p keeps it with probability p2. At essentially the same output size, the second round therefore has about e−ε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) 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.