Differentially Private Graph Diffusion with Applications in Personalized PageRanks

We extend our gratitude to Reviewer y6QA for appreciating our theoretical and practical contributions and supporting the acceptance of this paper. Here, we are to respond to the weaknesses proposed by Reviewer y6QA.

The paper lacks theoretical lower bounds showing the method is tight. (W1)

The Reviewer y6QA raises an insightful point. We agree that establishing a privacy lower bound is essential for evaluating the tightness of our framework and identifying areas for improvement. The original PABI analysis on noisy SGD [1] provides an order-tight lower bound by constructing a dataset with zero loss and an adjacent dataset with a bias introduced by a differing data sample. The parameter update processes in these adjacent datasets are thus characterized by a symmetric random process and a biased random process. The distinction between these processes is determined by test positivity [1], as one is symmetric and the other is biased. We believe a similar approach could be applied to our graph diffusion analysis, and we plan to explore this in future work.

[1] Altschuler et al. On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization.

We greatly thank Reviewer dwyJ for appreciating the novelty of our method and the corresponding theoretical analysis, and acknowledging the practical importance of the problem we studied. Here, we are to respond to the questions and weaknesses proposed by Reviewer dwyJ.

Complexity of Implementation. (W1)

We appreciate the reviewer’s question. Our framework comprises two main components: noisy graph diffusion algorithm and noise calibration. The noisy graph diffusion is straightforward and efficient to implement, involving only thresholding and noise injection after each diffusion step. The noise calibration is derived from our theoretical results (Theorem 1 & 4), which is computed before our graph diffusion algorithm. The efficiency of this part is further discussed in the text following Equation 6. For a given noisy graph diffusion algorithm (with a predefined thresholding function), our noise calibration method only requires the privacy budget to determine the appropriate noise scale, which the algorithm then outputs directly. To facilitate practical use, we will include the pseudocode for both components in the appendix. Additionally, we have released the code for noise calibration, enabling practitioners to apply it directly for effective noise calibration.

Generalizability to other graph diffusions? (W2 & Q1)

We thank Reviewer dwyJ for the insightful question. Yes, our framework (Theorem 1) includes broader graph diffusion processes, such as Global PageRanks [1] and Generalized PageRanks [2], with Heat Kernel diffusions [3] as a special case. Additionally, when viewing graph diffusion as a graph operator, our theoretical results can also be applied to graph convolution operators with non-linear transformations, provided these transformations satisfy certain Lipschitz continuity properties and do not require learnable parameters that necessitate backpropagation through the graph diffusion [4]. This approach further paves the way for obtaining edge-level private node embeddings for graph learning scenarios.

[1] Brin et al. The anatomy of a large-scale hypertextual web search engine.

[2] Li et al. Optimizing generalized pagerank methods for seed-expansion community detection.

[3] Chung Fan. The heat kernel as the pagerank of a graph.

[4] Sajadmanesh et al. GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation.

The scalability of the proposed method. (Q2)

We appreciate Reviewer dwyJ for raising this important question. In our paper, the largest graph dataset we consider is Flickr, with around 80k nodes and 6 million edges. For comparison, the largest dataset in previous research, Blogcatalog, contains around 10k nodes and 334k edges. We discuss the runtime in Appendix D.2 and Figure 7, where our method demonstrates comparable performance to the most efficient DP-PUSHFLOWCAP [1] method, completing a single trial on the Flickr dataset in under a minute. Specifically, on datasets with nodes ranging from 10k to 80k and edges from 334k to 6 million, our algorithm's runtime increases from 24s to 59s.

Our algorithm consists of two main parts: noise calibration and noisy graph diffusion. Given a specific privacy budget and the thresholding parameter $\eta$, we first calibrate the noise scale according to Theorem 1 using bisection search (pseudocode will be included in the appendix in the revised version). We then perform graph diffusion followed by a fixed thresholding and noise injection at each step with a complexity of $O$(# nodes), which is usually much smaller than $O$(# edges). However, we acknowledge that exploring further techniques to enhance scalability could be an interesting direction for future work.

[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.

Sensitivity of parameters. (Q3)

We thank Reviewer dwyJ for highlighting this point. In our framework, the degree-based thresholding parameter $\eta$ is the only parameter that can be tuned, while the noise scale is determined by the privacy budget (illustrated in Theorem 1). In practice, once the privacy budget $\epsilon$ is set, the noise scale is determined by our theorems for the noisy graph diffusion process. Regarding the degree-based thresholding parameter $\eta$, we have illustrated its performance sensitivity in Appendix D.3, Figure 8. The results show that our framework is robust to the choice of $\eta$, with performance remaining stable when $\eta$ is selected within the range of $10^{-10}$ to $10^{-6}$, consistent with the recommendations in [1]. For practical purposes, we suggest selecting $\eta$ within this interval.

[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.

We greatly thank Reviewer sGeR for appreciating our contributions to the algorithm and corresponding theoretical results. Here, we are to respond to the questions and weaknesses proposed by Reviewer sGeR.

The paper is difficult to read; consider simplifying terms, and including pseudocode. (W1)

We sincerely thank Reviewer sGeR for the valuable feedback. To improve the accessibility of the paper, we will make the following adjustments in our revised version: (1) We remove some abstract notations, such as Banach space, and replaced them with specific terms, like the Euclidean space $R^{|\mathcal{V}|}$. (2) We plan to include definitions, such as Lipschitz continuity, the $\infty$-Wasserstein distance, in the main text. We will also expand the discussion around Figure 1 and provide additional explanations for our main results in Equation 5, if space allows. (3) We include the pseudocode for our private graph diffusion algorithm along with the corresponding privacy accounting method in the appendix.

Is non-private PPR used as ground truth for Recall@R and NDCG@R, like in [20]? (Q1)

Yes, in our experiments, we use the rankings computed by the non-private PPR algorithm as the ground truth, consistent with the baseline approach described in [20].

Possible to measure utility degradation with increased privacy? (Q2)

We appreciate Reviewer sGeR's insightful question. In the privacy literature, algorithms are typically developed to meet specific privacy requirements and are often validated empirically, as seen in works like [1]. Specifically, while addressing worst-case scenarios under privacy constraints is crucial, necessitating theoretical proofs, the utility of these methods is generally assessed through empirical evaluation. That being said, we acknowledge that in some cases, worst-case utility can also be significant. While our current work emphasizes empirical evaluation, we recognize the importance of exploring the theoretical relationship between privacy parameters and the quality degradation of noisy diffusion vectors—such as in terms of approximation error [2,3]. This exploration is planned as a direction for our future research, which could enhance understanding of how increased privacy impacts the quality of diffusion vectors and ensure robustness in more challenging scenarios.

[1] Abadi et al. Deep learning with differential privacy.

[2] Andersen et al. Using pagerank to locally partition a graph.

[3] Hou et al. Massively parallel algorithms for personalized pagerank.

Discussion of limitations.(L1)

Thanks Reviewer sGeR for pointing this out. We fully acknowledge that privacy is not without cost, and this phenomenon is commonly referred to as privacy-utility trade-offs. Our experiments (Fig. 4 & 5) demonstrate these trade-offs, where enhancing privacy budget $\epsilon$ results in some degradation of utility. Following your suggestion, we will further emphasize this point in the "Limitations" section of the paper.

We are deeply grateful to Reviewer ApdU for the comprehensive feedback. Here, we will address these questions.

Edge DP is weak; consider node DP or stronger privacy notions. (W1)

We sincerely appreciate your suggestion to explore node-level differential privacy as a potential extension of our work, a direction we agree could indeed enrich the scope of our research, as noted in the "Societal Impact and Limitations" section. However, we respectfully emphasize that edge DP still holds significant value within the private graph learning community, as recognized by both Reviewer y6QA and Reviewer sGeR. Furthermore, the previous work [1] most relevant to this work also focuses exclusively on edge DP for personalized Pagerank, underscoring its significance and practical applications. Our study specifically addresses edge DP within the context of graph diffusion.

[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.

Iterative privacy framework and PageRank are well-known; lacks graph-specific insights. (W2)

We respectfully disagree with the assessment. Two things being well-known does not mean building a connection between them is well known, let alone the algorithm having to be designed specifically by taking into account the features from both sides. First and foremost, our main contribution is the first one to introduce Privacy Amplification by Iteration analysis [1] within the graph analysis and graph learning community, to the best of our knowledge, while prior research has predominantly concentrated on optimization [1,2] and sampling [3]. Regarding the work by Thakurta et al., we did not find a work first-authored by Dr. Thakurta and closely related to the iterative privacy framework. We guess Reviewer ApdU might be referring to [1]. However, the applications of PABI to graph diffusion scenarios are not standard and require many specific designs to incorporate graph properties:

(1) The degree-dependent thresholding function design in our work is motivated to achieve better control over edge perturbation. This design definitely involves graph-specific design.

(2) Since graph diffusions propagate in $\ell_1$ space, we are the first to explore the use of Laplace noise instead of Gaussian noise, while Laplace noise has seldom been considered in previous PABI analyses. The superiority of our approach is demonstrated in Appendix Figure 9 (Left). This further involves graph-specific consideration.

(3) Most importantly, we propose a novel $\infty$-Wasserstein distance tracking method, which improves upon previous PABI analyses and significantly tightens our privacy bound (as demonstrated in Figures 3 and 6), thereby making our algorithm actually practical. Additionally, this $\infty$-Wasserstein distance tracking method is generalizable to other metric spaces and may be of interest for addressing other related problems.

[1] Feldman et al. Privacy amplification by iteration.

[2] Altschuler et al. On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization.

[3] Altschuler et al. Faster high-accuracy log-concave sampling via algorithmic warm starts.

Can the algorithm be extended to GNN learning/inference? (W3)

Yes, our algorithm may be extended to some graph neural networks, such as the private version of SGC [1], where the gradient information does not need to be back propagated through the graph structure. During the training phase, the algorithm can be used to propagate features and generate private node embeddings, which can then be utilized to train a classifier. In the inference phase, applicable to both transductive and inductive settings, these features can be propagated, and the trained classifier can be employed for inference. However, for standard message passing NNs where the nonlinearity requires to backpropagate gradients across graph structures, we cannot use our framework because the backpropagation may leak private information. Note that some recent DP-GNN works such as [2] indeed adopt the framework without gradient backpropagating over graphs.

[1] Wu et al. Simplifying graph convolutional networks.

[2] Sajadmanesh et al. GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation.

Utility-privacy trade-offs for different “m” values (Q1)

We thank the reviewer for this insightful question. When adjusting “$m$” from $0$ to larger values, our algorithm transitions from noisy to noiseless graph diffusion with output perturbation. Our experiments show that noisy iterations generally outperform output perturbation in utility. Slightly delaying noise injection “$m$” leads to minor performance variations (gains or losses) depending on the dataset and privacy requirements. While practitioners can explore different “$m$” values to optimize privacy-utility trade-offs, our results suggest that $m=0$ is already an effective choice for noise injection.

Can DP guarantees be extended to node embeddings in graph prediction tasks? (Q2)

Yes, it is possible to directly extend our analysis to node embeddings with DP guarantees as long as the non-linear graph convolution operators satisfy certain constraints, such as Lipschitzness, and do not involve learnable parameters that require backpropagation through the graph diffusion.

Can similar privacy tests, like in the GAP paper, be conducted? (Q3)

In GAP paper, node-level MIA were employed to assess privacy leakage from learnable weights in GNNs under node DP, in scenarios where strong adversaries exploit overfitting to classify members based on GNN confidence. However, our algorithm does not involve a learning model (no learnable weights or data features) while only generating/output graph diffusion vectors, making it improper to be directly tested in GAP paper’s settings. We greatly value the Reviewer’s suggestion on privacy auditing for our algorithm and agree that exploring effective MIA is a promising direction for future research.