We thank the reviewer for their insightful comments and address their main concerns below. We are glad to learn that we were able to address the reviewer's concerns with our previous rebuttal. Here, we would like to take the opportunity to provide some additional context as to why edge-LDP is the most meaningful privacy guarantee in our setting.

There are two standard notions of DP for graphs - edge DP where the information about a single edge is protected, and node-DP where the information about an entire node of the graph is protected. Although node-DP is a stronger privacy guarantee, it is not suitable for our setting. Recall that our goal is to estimate the degree of every user. Now protecting this under node-LDP would require adding noise proportional to $\frac{n}{\epsilon}$ (since under node-LDP all the edges of a user can change resulting in a sensitivity of $n$). But this means that the amount of noise itself is much higher than the true answer (a degree can be at most $n$ and for real-world graphs it is often much lower) rendering the estimates to be completely meaningless.
As a result, the current literature considers edge-DP to be the standard notion of privacy in the local setting and has been used in the context of a variety of tasks such as counting the number of triangles [a], k-core decomposition [b], training graphical neural networks [c] and synthetic graph generation [d].

[a] Triangle counting with local edge differential privacy

[b] Near-Optimal Differentially Private k-Core Decomposition

[c] LPGNet: Link Private Graph Networks for Node Classification

[d] Generating Synthetic Decentralized Social Graphs with Local Differential Privacy.

We thank the reviewer for their insightful comments and address their main concerns below. We are very glad to know that the reviewer found our work to provide both theoretical insights and practical implementations. We would like to take the opportunity to address the main concerns below.

Fit. We chose ICLR since it has long been a leading venue for research in differential privacy. Here are a few examples of papers from ICLR 2024

a. A Differentially Private Clustering Algorithm for Well-Clustered Graphs

b. Numerical Accounting in the Shuffle Model of Differential Privacy

c. Privacy Amplification for Matrix Mechanisms

d. Efficiently Computing Similarities to Private Datasets

Rate of flagging. The quoted statement was not made in reference to Fig. 3, but rather in the context of the immediately preceding discussion (lines 504-507), which we reproduce here for clarity.

Our protocols are able to flag malicious users when they target a large number of honest users. Specifically, for the strongest degree deflation attack, Hybrid flags 4.5% and 49.8% of the malicious users for FB and Syn, respectively. RRCheck, on the other hand, flags 3% and 59.3% of the malicious users for FB and Syn, respectively. Note that the number of actual honest users affected by a malicious user is bounded by its degree. This is the reason why rate of flagging is less aggressive for FB since it is a sparse graph (the maximum degree is low).
The rates of flagging are presented in Table 1.

Choice of parameters for experiments. All our theoretical results are completely general purpose meaning they do not rely on any assumptions about problem-specific parameters, such as the privacy parameter, the underlying graph, input distribution, or the type of attack. This means that our theoretical results hold for any arbitrary choice of these parameters.

For the experiments in the main body we considered two settings for the privacy parameter (i) high privacy regime with $\epsilon=0.7$ - (values $\epsilon < 1$ is considered to provide high privacy guarantees), and (ii) $\epsilon=3$ for low privacy. Similarly, we considered two settings for the number of malicious users, $m$, $m=$1% (low poisoning rate) and $m=$33% (high poisoning rate). $m=$33% for our two datasets FB and Syn gives the concrete numbers m=1332 and m=1320, respectively. Prior work has shown that $m=$1% is considered a realistic threat in practice [28]. $m=$33% corresponds to $\frac{1}{3}$ of parties being malicious which is a classic threshold considered in the literature on Byzantine robustness and cryptography [a][b][c]. Additional experiments with different choices of parameters are presented in Appendix D.

[28] Back to the drawing board: A critical evaluation of poisoning attacks on production federated learning

[a] Asynchronous consensus and broadcast protocols, 1985

[b] How to Play Any Mental Game, 1987

[c] Asynchronous Secure Computations, 1999

Impact of different problem specific parameters - One of the biggest advantages of our robustness guarantees is that they are completely general purpose and attack agnostic -- i.e., our guarantees are completely unaffected by the choice of problem-specific parameters, such as the privacy parameter, the underlying graph, input distribution, or the type of attack. Our consistency check is based on an analysis of the tail bound for the Bernoulli distribution, which stems from the properties of the classic LDP mechanism, Randomized Response -- the individual bits of the user's adjacency lists are Bernoulli random variables. This analysis is again independent of everything else about the problem setup.

Computational complexity. Our algorithm requires O(n) work to estimate the and the operations are extremely light weight.

Related Work. We will update the related work section with more concurrent work. However, we would like to highlight that all prior work still focuses on tabular data setting, the novelty of our setting is that this is the first work studying the impact of poisoning for graphs under LDP.

We thank the reviewer for their insightful comments and address the main concerns below.

Motivation We work in the setting of a distributed graphs -- i.e., nobody has access to the entire graph. Hence, if the graph is in the context of a distributed social media network, such as Mastodon, bluesky, it is impossible for the server to publish the exact degrees of the users because it simply does not have access to this information. The only way the server can get access to this information is collecting this directly from the users. Now, one of the biggest selling point of distributed social networks is privacy, hence, it is unrealistic to imagine that the users will be okay to report their degrees in the clear to the server which showcases the real-world applicability of our protocol. Another example of a distributed graph is in the context of phone call graphs. Consider that every iPhone owner is a user or node, and an edge between two users indicates a phone call between them. Apple, acting as the untrusted aggregator, wants to compute a degree vector of the entire graph. The edges are sensitive (phone calls reveal users' personal social interactions), so users cannot submit their data to Apple directly. Instead, they add noise to their data to achieve a local differential privacy guarantee before sharing it with Apple.

Studying privacy-preserving degree distribution is a fundamental and classic problem in the graph privacy literature and has been examined thoroughly in prior literature starting from the seminal works of Nissim [a], Hay et al. [b], Karwa et al. [c]. We extend this body of work to a new dimension by considering the threat of poisoning attacks which is again extremely realistic in our setting.

[a] Smooth Sensitivity and Sampling in Private Data Analysis, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith

[b] Accurate Estimation of the Degree Distribution of Private Networks, Michael Hay, Chao Li, Gerome Miklau, David Jensen

[c] Private Analysis of Graph Structure , Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev

We thank the reviewer for their insightful comments and address the main concerns below.

Factual Error. Our analysis is indeed correct and in line with the definition of edge-LDP which was introduced in the seminal paper by Nissim et al. [a] . What the reviewer points to is not edge-LDP but relationship-DP which was introduced by Imola et al in [b][c]. Nevertheless, translating between these two definitions is straightforward - any $\epsilon$-edge LDP protocol satisfies $2\epsilon$-relationship DP (Proposition 1 in [b]). Note since the privacy definitions only affect a constant term all our asymptotic conclusions from our theoretical results are completely unaffected by the choice of the privacy definition.

[a] Smooth Sensitivity and Sampling in Private Data Analysis, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith

[b] Locally differentially private analysis of graph statistics 2021, Jacob Imola, Takao Murakami, Kamalika Chaudhuri

[c] Communication-Efficient triangle counting under local differential privacy 2022, Jacob Imola, Takao Murakami, Kamalika Chaudhuri

Contributions. Ours is the first work to study the impact of poisoning under LDP for graphs -- prior work only focused on tabular data or key-value datasets. Nevertheless, showing the separation between input and response poisoning the is not at all our primary contribution. Our major contributions are

1. Providing a new framework for quantifying robustness
2. A new lower bound result on poisoning attacks for graphs (Thm. 1)
3. Providing the first provably robust degree estimation protocol that is completely attack agnostic and optimal (i.e., matches the above lower bound)

All of these theoretical contributions are completely novel and highly non-trivial. In fact, ours is the first work to give provable and attack-agnostic robustness guarantee against any LDP protocols, graphs or otherwise -- prior defenses (all in the context of tabular data) were empirical and customized to specific attacks.

Honest and Malicious Error. Honest error corresponds to the error introduced in the degree estimate of an honest client while malicious error corresponds to the error introduced in the degree estimate of a malicious client. In a nutshell, honest error and malicious error quantify the error of the two disjoint sets of clients.

Experiments. We have carried out an extremely extensive experimental evaluation with 16 different attacks capturing real-world attack scenarios. Due to lack of space, we could only include a subset of our experimental results in the main paper -- an additional set of results are presented in Appendix D. Fig. 4 plots both malicious and honest error for 1) the naive baseline 2) our proposed protocols. As seen from the plots, the main observation is that the both honest and malicious error is significantly lower for our proposed protocols. Additionally, the plot also shows the separation between input and response poisoning. As such, the plot empirically demonstrates the superiority of our proposed protocols in protecting against poisoning attacks and thereby validate our theoretical results. Could the reviewer please point out how can the evaluation be improved?

Presentation. We will do a thorough copy-edit pass of the paper.