Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a privacy model in between the guarantees of local DP and shuffle DP. It does so by shuffling each user with a group of "similar" users as opposed to all users. As a result, it achieves better utility than LDP. The group that the user belongs to is publicly available, hence the adversary can tell that the user is one of k particular users but not which one. Hence, the "shuffler" instead of choosing a random uniform  permutation chooses a permutation that satisfies this per-group shuffle. It is intractable to choose a permutation with these properties, hence the authors propose a heuristic method for choosing such permutation.
main_review: The model is interesting and strikes a good balance between LDP and Shuffle model. The experimental section also combines utility with plausibility of inference attacks.

The motivation behind the model (even though I think the model is nice) is confusing as the main example is that people in one's household can be used to infer a secret of a particular user. But then the approach proposed by the paper is to reveal that the user is part of some group. Cannot just belonging to this group also be used to infer the privacy parameter? That is, it seems the method just changes which group the user belongs to. It would be good to see why it is ok.

The privacy definition also feel a bit like k-anonymity which is is know to be susceptible to attacks based on belonging to a group. This and above question could probably be answered by providing a more-DP looking definition. That is, can one say you achieve shuffle DP for a group of users? Can one present your definition as a special case of shuffle model and LDP by change \alpha?

The technical method in Alg 1 does not take as input privacy parameters. Hence, it seems that a permutation is chosen only based on G. Can this be changed, i.e., get "more permuted" data is one increases privacy parameters.
summary_of_the_review: A very well written paper and nice experimental section.
The paper can be strengthened with motivation of the new definition and its (formal) relation to existing definitions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a neighbouring-information based DP framework to bridge between local DP and shuffling-based global DP. The neighbouring information is represented as undirected graph. Depending on this structure, the concept of neighbouring permutations and d_{\sigma} privacy is developed. d_{\sigma} privacy shows interesting resilience results against Bayesian and decision-theoretic adversaries. Further a shuffling mechanism is proposed to achieve this definition. The utility of this framework is validated using experimental evaluations on three datasets.
main_review: Strength:
1. The paper deals with an interesting problem of bridging between local DP and shuffling-based global DP using a neighbouring-information based DP framework. As both the models represent two extremes of assuring DP and also lots of real-life data has a local neighbouring structure, it is pertinent problem to study.
2. The paper proposes to encode the neighbouring information as an undirected graph and use it to define the d_{\sigma} privacy definition. The definition is intuitive and reasonable. It also yields interesting resilience results against Bayesian and decision-theoretic adversaries. 
3. A shuffling mechanism is proposed to achieve d_{\sigma} privacy. The mechanism applies Mallow's model while using a heuristic to choose the reference permutation.
4. The experimental evaluations show utility of this new framework and its functionality to bridge between LDP and unif. shuffling DP, which is the central problem of the paper.

Weakness:
1. The heuristics used in the proposed privacy preserving mechanism is not well-analysed and well-justified. Depending on the choice of \sigma_0, the sensitivity can vary exponentially on n or k. Though it is evident that the underlying problem of computing sensitivity is combinatorial and NP-hard, a methodological choice of stable \sigma_0 is expected to ensure stability of the framework. It would be imperative to empirically or theoretically justify the heuristic for choosing \sigma_0 and showing it leads to a stable estimate.
2. How does the privacy level depend on the connectivity of the underlying graph G? For example, how would the privacy level \alpha would vary if the graph changes from a clique to a chain or a completely disconnected graph? An insight on this will be useful to explicitly understand the dependency on existence of neighbouring structure.
3. a. What is (\eta, \delta) preservation? A formal definition would have been helpful. Also, it seems a bit out of place and confusing in the main paper as it never discussed thereafter. 
b. though an empirical evaluation is proposed in A.14, it is not clear how to choose a good \eta or \delta, and what are the corresponding trade-offs.
4. The images used in the paper are very hard to read. This part of the paper could probably be edited to have a better presentation. Specially from the beginning to the end, I find a gradual decline in readability and presentation.
summary_of_the_review: The paper addresses an interesting problem of assuring DP with a novel framework using neighbouring information of data. The results derived for the decision theoretic and Bayesian attackers are useful and provides insights. A mechanism is proposed to achieve this new DP definition but the method seems to be hastily presented and descriptions of certain concepts are unclear. This is the part where the contribution could be improved. The usefulness of the proposed framework is validated through reasonable experiments.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies a variant of Local Differential Privacy with shuffling. Local DP is susceptible to inference attacks by using the order of the data. A way to fix the previous is to do “shuffling”, pool LDP responses, apply a permutation and pass that to the analyst. Shuffling gets rid of inference attacks however it severely hurts data learnability. This paper introduces d_sigma-privacy which provides a “tuning knob” between unshuffled LDP and shuffled DP, which rigorously allows trading off privacy and data learnability. Additionally, the authors provide a very general algorithm that achieve’s d_sigma-privacy and run experiments in some datasets validating their results.
main_review: The paper is original, motivated by allowing more data learnability in the shuffled LDP setting, the authors introduce a new notion of privacy called d_sigma-privacy and show it has desirable properties. Along with the new privacy notion they provide an algorithm that achieves it. 
The paper is very well written, clear, and easy to follow, I appreciate the examples. The paper is relevant since it introduces new and useful ideas in the space of privacy and it has practical applications.
I did not verify every single proof but what I looked at seemed correct.
summary_of_the_review: The paper is novel and well written. I recommend its acceptance.
review_title: null

Meta-review: Thank you for your submission. The reviewers agree that this paper provides new contributions to data privacy. In particular, the proposed definition interpolates between the local differential privacy and shuffled differential privacy definitions. As argued in the paper, mechanisms under this framework can prevent certain inferential attacks based on the relationships across the individuals (e.g., which individuals belong to the same household). The paper also provides good evidence that their mechanism guards against a specific type of inferential attacks and provides stronger utility than mechanisms based on uniform shuffling.
Decision: Accept (Poster)