Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper looks the problem of finding change point of networks sequences for two networks under edge and node LDP. For each setting, it shows the feasible regime and an algorithm that guarantee LDP.
strengths_and_weaknesses: Strength: The paper looks at an important problem which hasn't been worked on before.

Weakness: The privacy definitions is a bit hard to follow.
questions: I mainly have some questions regarding the setup.

- I'm a bit confused by Assumption 1 & 2. I think they define the change point and some properties of the change point for the two networks. But isn't there a unified definition for any network? Why would we need two? (And, why are they "assumption" not "definition"?)

- Line 118 says we want the estimated change points to be close to the actual change points as sample size T grows. Is that under the assumption that the number of change points K does not grow with T?

- I think $A$ is used for both the adjacency matrix and the set $A \subset Z$. Maybe you can considering change the notation.

- For the privacy definitions in Section 2
  - what is Q? If it is a mechanism (as is stated in Line 144), I feel like its should be a function that operate on the input so the expression should be something like Z = Q(X)? But the way it is used in the formula make it seems like some probability measure.
  - what is X? Is that the adjacency matrix (so the same as A in Section 1)? And what is $X_i$? Is that one row of the adjacency matrix?
  - Regarding the edge-LDP definition:
    - You mentioned that some prior work is looking at $X_i$ instead of $X_{ij}$ and it requires trust between nodes. I didn't follow that part. Does that refer to the case where user $i$ is supposed to privatize the edge (or lack of edge) between $i$ and $j$? But if so, wouldn't (3) also have the same problem?
    - I don't quite follow the definition. I think what you mean is that for user i, even if every {i, j} changes, we would still be able to hide the change. But if so, isn't that the same as node-LDP?
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 studies the problem of change detection (or change point localization as mentioned by the authors) in dynamically evolving graphs subject to differential privacy. Focusing on two generative models, namely, inhomogeneous Bernoulli networks (IBNs) and bipartite IBNs, conditions are provided under which change localization is infeasible. Subsequently, a simple randomized response mechanism is studied (applied together with CUSUM type statistic for change detection) and analyzed. 
strengths_and_weaknesses: + This is a technically strong and very well written paper, which I enjoyed reading. I very much appreciated the care taken by the authors in describing the similarities/differences in techniques which they borrowed/adapted from prior works. In addition, some of the discussions along with the technical results (such as impact of privacy constraints on the graph sparsity) were quite intriguing. Overall, I believe this could be a useful contribution to the broader ML community working on the area of privacy preserving graph based algorithms. 

Some minor weaknesses and suggestions for the authors:

- While I understand that this is a theoretically oriented paper, and the technical results are solid, I would have still liked to see some numerical results to actually see the finite sample performance of the proposed algorithm (RR + CUSUM) on some dynamic networks in practice.  

- I would like to point out a somewhat related work on "Differentially Private Community Detection For Stochastic Block Models", ICML 2022, which also derives some tradeoffs between privacy and the phase-transition boundary (for community recovery). In contrast to the conclusions of this submission (which show that RR is almost optimal for edge LDP), the above reference shows that RR may not be a good choice for private community detection with edge DP, as it significantly increases the average node degree (and other mechanisms, such as exponential, and stability based methods can fare better and provide a better privacy-recovery tradeoff). This is a complementary viewpoint, which authors may wish to discuss in the paper, i.e., what (if any) are the limitations of RR based perturbations. 
 
questions: See comments above
limitations: Yes, limitations were appropriately discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of change point detection in sequences of networks/graphs with respect to local differential privacy constraints (respectively edge and node LDP). Under assumptions on the random structure of the graphs (IBN for instance), the authors establish minimax rates for change point detection using Le Cam’s method. Then, the authors show that using randomized response to obtain edge privacy alongside the NBS algorithm obtains the minimax rate for change point detection. The authors show similar results for node LDP for bipartite IBNs.
strengths_and_weaknesses: Strengths: To the best of my knowledge this problem has not been attempted before. Moreover, the need for edge/node LDP is clearly presented in the paper with practical examples. The problem is concisely contained, as both lower and upper bounds rates are presented for the change point estimation. The paper was clearly presented, although presenting the key results/rates as an informal theorem e.g. in the introduction may be useful. There is also thorough discussion in the conclusion of why the techniques do not generalize to the interactive setting.

Weaknesses: The problem discussed and approaches used in the paper are not particularly novel, as the paper is concerned with taking existing statistical procedures and studying them in through the lens of (local) privacy. Moreover, it would be interested to have some experimentation to demonstrate the empirical performance of these estimators when being run on privatized networks. Lastly, the random structure assumed on the families of graphs (IBN, bipartite IBN) seems somewhat restrictive, especially when considering practical network data (e.g. is it realistic to assume that networks connections are independently generated?). Is there a way to incorporate correlation between the network edge indicators into this result (outside of that included in the bipartite IBN)?

questions: As aforementioned, it may be valuable to introduce an informal theorem for your main results in the introduction of the paper. Other questions and comments can be found above.
limitations: The authors discuss the limitations of their paper in the conclusion. In particular, they point out that their paper and arguments do not go through in the setting of interactive LDP. Investigating the problem in this setting seems important, especially for network data where one would expect the edge/node inclusion probabilities to be correlated.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors consider consistently localizing change points under both node and edge local differential privacy (LDP). The authors proposed an algorithm under edge LDP that is shown to be optimal. For node LDP, the authors show there is a gap exists between upper and lower bounds.
strengths_and_weaknesses: Strengths:
S1. The work seems solid. I didn't check for all the technical details, but the formal definitions and results seem to be finished well.
S2. The authors provide theoretical results to the problems.

Weaknesses:
W1. I did not fully get the reason why we should focus on these problems. I can understand network data is important, but I do not see why we focus on these two network models. The paper could benefit from better motivating why these problems are important in practice, more concrete examples of the two network definitions, and how close these two definitions model real-world scenarios.

questions: Q1. Is it possible to provide some empirical evaluation since you have provided an algorithm?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper considers the important problem of change point detection in networks under local differential privacy. The paper provides bounds for the problem under both node and edge privacy constraints. While the bounds in all cases are not matching the results are timely and will be interesting for several researchers. 
confidence: Certain
Decision: Accept