Differentially Private Graph Diffusion with Applications in Personalized PageRanks

Summary

The authors study the important problem graph learning methods (graph diffusion) with differential privacy. There is limited work in this important problem space (one exception being some work on PPR with DP). The authors present a non-trivial use of the PABI framework which uses Contractive Noisy Iterations to prove differential privacy for a process that adds noise iteratively and applies a contractive function. This is a novel and interesting result that might have impact on a variety of learning problems beyond DP. The authors prove formally privacy guarantees of the method. Then the perform an empirical analysis on real data of moderate size and show that their method exceeds all existing baselines (prior DP PPR paper and trivial edge flipping baseline). This paper addresses an important problem with novel and practical ideas showing improvements both theoretically and practically.

Strengths

Important problem: graph learning with privacy Novel algorithmic method that appears to be general enough to have impact on multiple graph problems. Theoretical guarantees for privacy Good evidence of improving empirically over all prior baselines

Weaknesses

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

Questions

No question

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

Summary

The paper titled "Differentially Private Graph Diffusion with Applications in Personalized PageRanks" proposes a novel graph diffusion framework that ensures edge-level differential privacy (DP) by injecting Laplace noise into the diffusion process. This framework leverages Privacy Amplification by Iteration (PABI) and introduces a new method for tracking privacy leakage using the ∞-Wasserstein distance. The proposed approach is evaluated in the context of Personalized PageRank (PPR) computation and demonstrates superior performance under stringent privacy conditions compared to existing methods.

Strengths

The paper introduces a novel method for achieving edge-level differential privacy in graph diffusion processes by incorporating Laplace noise and utilizing Privacy Amplification by Iteration (PABI). This approach is innovative and adds to the existing body of knowledge on privacy-preserving graph algorithms. The authors provide a thorough theoretical analysis of the privacy guarantees of their method, including a novel ∞-Wasserstein distance tracking method to tighten privacy leakage bounds. This rigorous analysis enhances the credibility and potential impact of the work. The application of the proposed framework to Personalized PageRank (PPR) is highly relevant, as PPR is widely used in various real-world applications such as recommendation systems, community detection, and targeted marketing. The paper includes extensive experiments on real-world datasets (BlogCatalog, Flickr, TheMarker) demonstrating that the proposed method achieves better privacy-utility trade-offs compared to baseline methods, particularly under stringent privacy settings.

Weaknesses

Complexity of Implementation: The proposed method involves complex theoretical constructs such as PABI and ∞-Wasserstein distance tracking, which may pose challenges for implementation and adoption in practical applications. Specific Focus on PPR: While the application to Personalized PageRank is well-justified, the paper's focus on a single type of graph diffusion might limit its generalizability. Scalability Concerns: The scalability of the proposed method, particularly for very large graphs, is not thoroughly addressed. Additional experiments or discussions on the computational efficiency and scalability of the approach would strengthen the paper.

Questions

Generalizability: Can the proposed framework be easily adapted to other types of graph diffusion processes beyond Personalized PageRank? If so, what modifications would be necessary? Scalability: How does the proposed method scale with increasing graph size and complexity? Are there any optimizations or approximations that could improve scalability? Parameter Tuning: How sensitive is the performance of the proposed method to the choice of the noise scale σ and the degree-based thresholding parameter? Are there guidelines for selecting these parameters in practice?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See above

Summary

The paper presents a new differentially private personalized PageRank (PPR) algorithm. The paper extends and theoretically analyzes the privacy amplification by iterations (PABI) technique applied to a graph diffusion setting. Rigorous theoretical results demonstrate the privacy guarantees achieved by the approach. An experimental evaluation shows that the proposed approach achieves better results than known algorithms

Strengths

- The considered problem is important as diffusion vectors might be used to reveal the edges in the graph. - The proposed technique appears to be interesting. - The theoretical results and proof techniques are non-trivial and require in-depth subject knowledge.

Weaknesses

The paper is extremely difficult to read. I admit I am no expert in the area but, for example, I didn't have a problem following Epasto et al. [20]. The paper is overloaded with advanced mathematical terms and concepts that are never properly defined. Maybe terms like Banach space, the diameter of a convex bounded set, contraction maps, Lipschitz continuous graph diffusions, essential supremum, etc are standard terms for a mathematical paper but, after all, NeurIPS is not a mathematical venue. Even the $\infty$-Wasserstein distance is only defined in the appendix. The paper would become much more accessible if the authors provided some intuition above the approach. For example, a paragraph can be devoted to Figure 1, a vanilla version of the main result simplifying some of the terms can be presented, pseudocode of the approach can be added to the appendix.

Questions

- When computing Recall@R and NDCG@R, do you use as a ground truth the rankings computed by the non-private PPR algorithm, like in [20]? - Would it be possible to show some theoretical results on how the quality of the diffusion vectors degrades by enhancing the privacy parameters, for some intuitive notion of "quality"?

Rating

5

Confidence

2

Soundness

4

Presentation

2

Contribution

3

Limitations

I am not really happy with the discussion of limitations. The required noise to achieve privacy guarantees, as defined in (3), appears to be substantial. Also, as evident from Figure 5, the recall scores are considerably worse compared to the baselines. I want to emphasize that this is not meant as a criticism of the proposed algorithm, it clearly improves upon previous work. But the price that one has to pay for obtaining diffusion vectors with privacy guarantees is a limitation that needs to be acknowledged.

Summary

Graph diffusion iteratively propagates signals through the graph, that are subsequently used for real-world applications like personalized page rank. This paper develops edge-level Differentially Private (DP) guarantees for personalized PageRank using Laplace noise addition. Unlike traditional perturbation-based DP algorithms, the Laplace noise addition is done during the diffusion phase and not added directly to the output. This allows the algorithm to achieve better utility-privacy tradeoffs compared to existing approaches. The authors identify the graph diffusion process as a composition of contraction maps and aim to extend the Privacy Amplification by Iteration (PABI), guarantees to the graph setting. To this end, the authors introduce degree-based thresholding of signals to bound distance between coupled diffusions over adjacent graphs. The authors prove the DP guarantees for the general setting of delayed noise injection where, noise is injected into the signals starting from diffusion iteration step “m”. They first bound the L1 norm between the two signals for all < m-th iterations. The Renyi Divergence (RD) between the final signal iterates are then upper bounded by the sum of shift absorption term and a PABI term using the properties of RD and the previous bound. The shift absorption term is finally bounded by the strong composition rule of RD and bounding the shift “h_k” per iteration. The PABI term is bounded by the infinite Wasserstein distance between the coupled iterates using the identity mapping. The authors empirically demonstrate the utility gains (NDCG, RECALL) of the algorithm on BlogCatalog, Flickr and TheMarker datasets with respect to two baselines: DP-PUSHFLOWCAP and Edge-Flipping.

Strengths

1. The algorithm performs Laplace noise injection during the signal diffusion phase, as opposed to output perturbation, resulting in better privacy utility tradeoffs. 2. Develops theoretical guarantees in epsilon-RDP based on tractable hyperparameters. 3. The method guarantees the RD Privacy budget remains bounded w.r.t the number of iterations.

Weaknesses

1. Edge differential privacy is quite weak. I think the authors should try node differential privacy or atleast some stronger notion of privacy. Just with Edge DP, the privacy guarantee is quite weak. 2. The iterative privacy framework is quite well known since Thakurta et al.'s work. PageRank is well known iterative algorithm. In that sense, the contribution of the paper is limited. I was expecting to see some graph specific insights from either experiments or theory, which I did not find. 3. Since the algorithm is quite generic, can one extend it to learning or inference of a graph neural network? The key weaknesses therefore are lack of novelty and impact.

Questions

1. Since Theorem B.1. holds for any “m”, have you observed the utility privacy tradeoffs for different “m” values? Specifically are there any advantages to performing delayed noise injection instead of starting at m=0? 2. Graph prediction tasks are usually performed over node embeddings. These embeddings are typically generated by graph convolution operators which perform an operation similar to graph diffusion followed by a non-linearity. Is it possible to extend the DP guarantees to node embeddings in such settings? Such a guarantee can possibly extend the results in this paper to more general graph prediction tasks (other than PBR). 3. In the paper titled “GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation” which was referenced in this paper, the authors have conducted a “Resilience Against Privacy Attacks” study in their experimental results to emphasize the resilience of their model against node membership inference attacks. Is it possible to perform similar experiments in this work?

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

1

Limitations

Limitations are addressed.