Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes pairwise network differential privacy (PNDP) in decentralized optimization that relates privacy loss between two nodes with their communication weights after running the proposed algorithms for T steps. Several mixing matrices are considered and the paper analyzes both simple gossip averaging and baseline decentralized optimization problems. Utility and privacy analyses are conducted for different mixing matrices and problems. The new notion of differential privacy averages privacy loss for all nodes and thus gives a new perspective of designing privacy-oriented algorithms for decentralized optimization rather than only looking at worst case privacy loss. 
strengths_and_weaknesses: The idea of PNDP is a pairwise version of network DP from ref. [16], which highlights and averaged privacy loss for each node instead of the worst case privacy loss. This perspective is original. This paper has quality analyses and experiments to support its claims and is clearly written. For each case considered, the paper shows clear and solid theoretical guarantees. I think this paper is significant in introducing this new idea of pairwise privacy notion, but the main confusion when I read the paper is that how to explicitly compare the utility loss given the same privacy constraints since there is a conversion of DP and Renyi DP which I didn't figure out how these results are compared in detail. 
questions: I read the proof of Synchronous Muffiato and have the following questions. 1. In line 590, how to get the first bias-variance decomposition? It seems to the cross term has dependent parts and cannot cancel. 2. The first inequality here seems to rely on some properties of $P_t(W)$ while dealing with the 2nd term in the 2nd line. 3. The first term in the 2nd line misses an expectation symbol. in the first line, I guess there should be $\|x^t - \mathbb{1} \bar{x}^\top\|$ otherwise the dimension of $\bar{x}$ is confusing. 4. How to reach the inequality in line 495?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a relaxed notion of local differential privacy in a
distributed model of local optimization in which users share data across
a network over rounds. The key difference from LDP is that for a particular
round, a user only sees data from his neighbors, and thus data from many hops
away is aggregated more and is more private. They propose muffliato, an algorithm
for computing noisy averages with an improved accuracy guarantee over LDP for 
several important types of network topologies. They show how to use 
muffliato to perform SGD privately.

strengths_and_weaknesses: + muffliato offers a big improvement over LDP in terms of accuracy and realistic
assumptions about the network in which the compuatations are done.

+ The authors provide a tight privacy analysis of Muffliato when the Gaussian
  mechanism is used.

+ the experiments are good quality and indicate the improvements of Muffliato

- Muffliato, and especially Muffliato-SGD, still require many rounds of
  coordination between users which is often hard to achieve in the decentralized
  setting.

questions: Theorems 2,3 hold for a particular value of T^{stop} which is upper bounded as
stated and not for all values of T^{stop} up to that bound, right? The second 
case seems incorrect as early iterates would not be accurate. Please make this
more clear in the theorem statements.

In real life, the communication networks often change between rounds of
interaction, and users drop out and come back online. This seems to be  
captured well by the general analysis of
Muffliato, which allows W to change over time. However, for random muffliato,
how realistic is it to assume that some mechanism exists to sample edges randomly
and query the users? Does this require a central authority to do the sampling,
and what happens if the users are offline?

This extends to the Muffliatio-GD, where it appears one must assume a fixed
communication matrix, or use randomized muffliato, many times.

limitations: The communication/coordination limitation could be addressed by running experiments
with different communication graphs each round.

(Edit) I thank the authors for addressing this concern.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies a relaxation of local model of privacy, which they call pairwise network differential privacy. They use gossip protocols to understand the privacy loss under this relaxed notion. They show that the privacy get amplified under this notion of privacy for a range of network topology.
strengths_and_weaknesses: The main strength of the paper is the new notion of privacy studied. It seems natural for certain settings, but I am not sure if it is . They also study their new notion of privacy under the setting of colluding nodes in the network. The ring graph and complete graph was studied recently, so that result is not new. The result that is new are for expanded graphs and random graph. The proof seems correct.

The main weakness of the paper is also the new notion of privacy. For a privacy notion to be of use, it has to satisfy basic properties: group privacy, composition, and robustness to post-processing. I believe the authors can extend their collusion result to get group privacy. I would suggest the authors to do that in order to make this new relaxation more rigorous. It is also unclear what would be a good notion of composition for this new notion of privacy. Do we assume that the network topology (and collusion party) do not change over the period of composition or should we imagine the composition model to be more fitted with their time-varying graph model.

The other weakness of the paper is the interpretability of the result. Theorem 1 is stated with respect to the norm of the gossip matrix (I am guessing it is the spectral norm). It would be nice if we can have a sense of this theorem with an example. 

The mean privacy loss as the baseline to compare privacy does not make sense. 

I would expect Algorithm 2 should have improvement for all values of d and spectral gap. This does not seem to be the case for arbitrary graphs. 
questions: Please take a look at above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces Pairwise network DP, a relaxation of local DP that allows the privacy constraint to vary as a function of nodes in the decentralized graph (i.e. may allow close nodes to lose more privacy than distant nodes). Given this setting, the work introduces Muffliato which combines local noise injection and gossip protocols and it further derives DP optimization algorithms. The theoretical analysis demonstrates the magnitude of privacy amplification for the protocols.  Intuitively, since nodes only interact directly with their neighbors, the this formulation allows for much tighter privacy guarantees for distant nodes and network topology can have a large impact on privacy utility tradeoffs. Finally, they also demonstrate privacy gain on synthetic and graph datasets.
strengths_and_weaknesses: To the best of my knowledge, this work offers novel analysis to quantify the privacy amplification of the decentralized protocol for arbitrary graph types and demonstrates a strong improvement in privacy utility tradeoffs over LDP, both theoretically and empirically. 

questions: Suggestion: Additional federated learning experiments on a real world dataset (with a real world graph) demonstrating the practical utility of this method would be helpful. 
limitations: The paper adequately notes its limitations and discusses its social impacts.
review_title: null

Meta-review: metareview: The paper eventually received a perfectly consistent evaluation from all the reviewers (4 times "accept"), so I can only recommend the acceptance.
confidence: Certain
Decision: Accept