Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper proposes algorithms that compute personalized PageRank (PPR) under edge differential privacy (DP), and extends the algorithms to compute graph embeddings.
strengths_and_weaknesses: The paper studies an interesting problem, and is relatively well written. However, there are several major issues with the paper.

First, the proposed PPR algorithm is relatively straightforward: it computes the PPR values and then adds noise based on the sensitivity of the values. The sensitivity analysis is mostly based on the triangle inequality and is rather loose. As a consequence, the significance of the algorithm is unclear.

Second, the proposed algorithm relies on unreasonable parameter settings. In particular, the algorithm set a threshold $\sigma$, and requires that when each node pushes residues to its neighbors, the total amount of residues pushed along each edge is at most $\sigma$. As a consequence, if a node $v$ has $d$ edges, then the total amount of residues pushed from $v$ is upper bounded by $d \cdot \sigma$. Therefore, if the initial residue of $v$ is $x$, then the approximate PPR for $v$ returned by the algorithm is at most $x - d \cdot \sigma$. In the experiments, we have $x = 1$ for each initial node and $\sigma = 10^{-6}$, and the average degree of each node is only a few dozens. As a result, the approximate PPR for each initial node is almost identical to the initial residue $x = 1$. Apparently, such approximate PPR values are far from the ground truth PPR values. This issue cannot be addressed by using a larger $\sigma$, because the amount of noise used by the algorithm is linear to $\sigma$. 

Third, the paper presents algorithms for both edge DP and joint edge DP, but the experiments only evaluate the joint edge DP algorithms. As a consequence, it is unclear whether the proposed edge DP algorithms work well or not.
questions: N/A
limitations: N/A
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 Personalized PageRank (PPR) problem (which is a very popular quantity
used in graphmining) under differential privacy constraints. The first contribution of
the paper involves analyzing the sensitivity of a prior algorithm for PPR, Push-Flow,
in terms of the min-degree of the graph; this could be large if the min-degree is low.
The authors design a natural variant, PUSHFLOWCAP, which has a better sensitivity,
allowing the Laplace mechanism to give privacy bounds. Finally, the authors combine their
method with a recent algorithm for embeddings. The methods are evaluated on real-world datasets.
strengths_and_weaknesses: PPR is a very commonly used metric, and differentially private algorithms are not known. So the
paper is studying an important problem. The main technical idea is quite nice, and pretty natural.
The sensitivity analysis of the Push-Flow and PUSHFLOWCAP algorithms is technically
interesting, though not particularly involved.

The statements in the final results are somewhat complicated since the utility analysis
holds under some conditions. These would become stronger if a lower bound could be shown.

The experiments section could be strengthened. While there is no private algorithm for PPR,
randomized response seems like too weak a baseline.

The presentation could be improved quite a bit. The authors could simplify the notation and present
it in a way that the symbols are easier to parse.
questions: Is the notion of (\xi, \eta)-approximate PPR well established? What is the impact of the \eta
parameter on the utility of PRR in practice?

There are a lot of symbols, some of which are defined as they are encountered or after. For instance,
T_v is not yet defined in Obs 4.1 and Lemma 4.2, making it hard to parse. A table of notation
might make the paper more readable.  The statements with join/non-joint, while concise,
are also harder to read.

Section 6: while the values of hyperparameters \xi, \alpha and k might make sense in a non-private
setting, it is not clear if those are the best choices for this paper. It would be interesting
to see how they are impacted under privacy, and it might provide a way to improve the results
further.

Section 6.1: it would be useful to define the metrics.

Section 6.2: for evaluating embeddings, it might be useful to compare with the DPNE method of
(Xu et al., PAKDD 2018), which gives an algorithm for this problem. Also, how is micro-F1 defined?
The results in Figure 2 are not particularly great. Maybe considering larger \epsilon is helpful
limitations: The discussion is limited but seems ok
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: In this paper, the authors propose an algorithm which outputs an approximate PPR and
has provably bounded sensitivity to input edges.
strengths_and_weaknesses: Pros:

Paper is organized well

Paper topic is interesting

Cons:

Algorithms theoretical bounds are not studied (NP-Complete etc)

Experimental analysis is brief and does not give comparative analysis to SOA algorithms

questions: Why is their no theoretical proofs in the paper?

Why is comparative analysis lacking from the Experiments?
limitations: N/A
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 focuses on computing approximate Personalized PageRank (PPR) vectors with differential privacy (DP) in graph representation learning. First, the authors analyze the non-private version $\xi$-approximate PPR push algorithm with sensitivity. Then, the authors develop a variant of the push algorithm with bounded sensitivity called PushFlowCap. By applying Laplace mechanism with PushFlowCap, they also propose an algorithm called DPPushFlowCap to obtain an non-joint or joint $\epsilon$-DP approximate PPR vector. Finally, based on InstantEmbedding, the authors provide a sensitivity-bounded version for graph embedding.
strengths_and_weaknesses: Strengths:

- The theoretical foundation is solid.
    
- The algorithms are written clearly.

Weaknesses:

- The idea of this paper is based on an assumption that a GNN with the Personalized PageRank filter is highly sensitive to edge changes on a graph such as a single edge addition or removal. However, according to research works about stability for polynomial spectral graph filters[1,2] which include the Generalized PageRank filter[3,4], a generalization of all PageRank filter variants, polynomial spectral graph filters are robust for edge modifications so long as the endpoint degrees are high. Therefore, the assumption for this work is not entirely valid.
    
- The introduction of relations among the $(\xi,\eta)$-approximate PPR vector, non-joint and joint DPPPR vector, PushFlowCap algorithm, and DPPushFlowCap algorithm are vague.

References:
1. Kenlay, H., Thanou, D., & Dong, X. (2020). On The Stability of Polynomial Spectral Graph Filters. In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 5350–5354).
2. Kenlay, H., Thanou, D., & Dong, X. (2021). Interpretable Stability Bounds for Spectral Graph Filters. In Proceedings of the 38th International Conference on Machine Learning (pp. 5388–5397). PMLR.
3. Baeza-Yates, R., Boldi, P., & Castillo, C. (2006). Generalizing PageRank: Damping Functions for Link-Based Ranking Algorithms. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 308–315). Association for Computing Machinery.
4. Gleich, D. (2015). PageRank Beyond the Web. SIAM Review, 57(3), 321–363.
questions: 1. Why do the authors specifically choose the Laplace distribution? There are no citations or explanations in Section 2 from line 78 to line 88.
limitations: The authors have sufficiently addressed limitations of this work. In Section 7, the authors concern the safety of any application of this work.
review_title: null

Meta-review: metareview: Paper studies computing PPR in differential privacy setting. Given the importance of PPR in real world applications, we recommend accepting the paper as it brings an important problem to the DP community. However, we encourage authors to incorporate the comments from the authors, make sure that all the details of the proofs are made available in the final version, and clarify any comments reviewers raised. In particular, we encourage the authors to adequately address the criticisms of @Reviewer MDNv in the true spirit of science.
confidence: Less certain
Decision: Accept