- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies differentially private PageRank under replacement of a single node’s entire outgoing-link profile on a fixed public node set. The authors combine degree flooring and source-mass clipping to construct a regularized PageRank query, then develop two mechanisms: Gaussian perturbation for releasing the full score vector and Gumbel perturbation for releasing an ordered list of top- nodes. They establish global row-level sensitivity bounds, quantify regularization bias relative to original PageRank, and derive utility guarantees for score estimation and exact top- set recovery, without guaranteeing the set’s internal order.
The main theoretical contribution is matching upper and lower bounds on dense directed graphs with minimum out-degree proportional to the number of nodes, under uniform restart,$ \delta=n^{-2}k$ result establishes matching separation-gap orders for fixed in the nonsaturated regime. Privacy guarantees hold over the full input domain, whereas these optimality results concern the restricted dense graph class. Experiments on synthetic graphs and three real-world networks demonstrate improvements in selected head-ranking tasks, with performance varying across privacy budgets, output sizes, and evaluation metrics.
Critical strengths
-
Outgoing-row replacement protects an entire outgoing-link profile, addressing a meaningful privacy objective distinct from edge-level and full node-level privacy.
-
The shared regularized query supports both release mechanisms, with global sensitivity bounds covering dangling rows and explicit regularization-bias guarantees relative to original PageRank.
-
Row-preserving embeddings and packing constructions establish matching full-vector risk bounds on dense graphs under uniform restart and the stated privacy conditions, together with matching recovery-gap orders for fixed in the specified nonsaturated regime.
Critical weaknesses
-
The matching theory assumes dense graphs with minimum out-degree and , whereas the real-data experiments use sparse networks, , and relatively large . Additional experiments under stricter privacy settings would clarify practical utility beyond the theoretical regime. Top- configurations selecting the pure-DP branch of Equation (9) should be distinguished, since their performance does not depend on .
-
Table 1 shows higher overall relative error for Full Vector than Uniform on all three datasets at . Table 2 also reports lower mean overlap for Top- than Full Vector at . These results do not support “overwhelming superiority.” Although Section 5 acknowledges the tradeoffs, the abstract and contribution statements should qualify improvements by task, budget, and metric.
-
The PDF does not fully specify Edge Flipping’s row-level privacy calibration or Naive Gaussian’s sensitivity and noise calibration, limiting reproducibility. Evaluating consistent Euclidean projection onto the probability simplex would also strengthen the vector comparisons. Such postprocessing preserves privacy and cannot increase full-vector error, although it offers no corresponding general guarantee for subgroup errors or ranking metrics.
-
The experiments keep fixed, leaving its effect on practical utility insufficiently explored. A small sweep and evaluation of the noiseless regularized query would help quantify the empirical bias–noise tradeoff. The real-data tables also omit uncertainty estimates; Appendix D mentions standard errors in a result CSV, but the supplied PDF provides no link to that file.
Questions for authors
-
Could you fully specify the Edge Flipping mechanism and its row-level privacy calibration, together with Naive Gaussian’s global sensitivity and noise calibration? How do the vector-error comparisons change after applying identical probability-simplex projection, and can you provide uncertainty estimates, result CSVs, and an anonymous implementation?
-
How do both mechanisms perform for and ? Could noiseless-query results and a small sweep of in distinguish the Top-5 errors already present after regularization from the changes introduced by each mechanism’s noise?
4 comments
Weakness 2: Unproper claim in abstract
Thank you for this comment. We will update our statement in the revised manuscript. It will be available at Nov. 17th, AOE.
Weakness 3 (Question 1)
Thank you for raising this question. We will clarify all the following points in our manuscript.
1. Details of comparison methods.
-
Edge Flipping. Consider the row-level DP budget . We take Edge-flipping with flipping probability , i.e. -edge-DP. Since replacing one outgoing row changes at most edges, the entire perturbed graph satisfies -row-DP. Therefore, in our experiments, we use edge-flipping with -edge-DP, and then compute PageRank on the perturbed graph.
-
Naive Gaussian. We add independent Gaussian noise to the original PageRank vector, using the global sensitivity upper bound . This follows because , with fixed public restart , and is a probability vector. With , the bound is approximately 1.1314.
We release , where , and numerically calibrate using the analytical Gaussian mechanism (AGM). This guarantees -row-DP for the entire released vector.
We believe this is a fair comparison.
2. Identical Euclidean simplex projection.
Thank you for this suggestion! Now we apply the same Euclidean projection onto the probability simplex to every vector method. This preserves privacy and cannot increase overall error.
At , , , and , overall relative errors after projection are (with 95% CI):
| Method | Email-Eu-core | CollegeMsg | Wiki-Vote |
|---|---|---|---|
| Full Vector | .731 [.726, .736] | .831 [.828, .834] | .879 [.878, .881] |
| Uniform* | .644 | .735 | .844 |
| Edge Flipping | .643 [.643, .643] | .735 [.734, .735] | .844 [.844, .844] |
| Naive Gaussian | 7.475 [7.283, 7.667] | 9.014 [8.681, 9.348] | 13.169 [12.746, 13.591] |
*: Uniform assigns the PageRank vector to be at each entry, and it is deterministic.
Using the same releases before and after projection, Full Vector's overall errors decrease from .893 to .731, 1.002 to .831, and .999 to .879, respectively. Projection also substantially improves Naive Gaussian; Uniform and Edge Flipping are unchanged. Full Vector remains better than Naive Gaussian but worse than Uniform and Edge Flipping on overall error at this budget.
The head-score advantage over Uniform remains: Full Vector's Top 5% score errors are .315 [.309, .320], .514 [.511, .517], and .673 [.671, .674], versus Uniform's .475, .605, and .749. These errors use the paper's full-vector reference norm for normalization.
3. Documentation. We will make the calibration details explicit in the revised manuscript and provide the result CSVs, including uncertainty estimates, together with the anonymous implementation in a ZIP file.
Weakness 4 (Part of Question 2)
Thank you for this suggestion. We evaluated the noiseless query and in for Email-Eu-core dataset, focusing on the Top 5 score error and Top 5 overlap. The results are in the following table. Noiseless indicates the scenario before noises are introduced. Noisy entries report mean ± pointwise 95% Student-t CI over 50 releases. Bold represents the choices in our manuscript.
| Noiseless Top-5 score error | Full Vector Top-5 score error | Full Vector Top-5 overlap (%) | PR Top- Top-5 overlap (%) | |
|---|---|---|---|---|
| 1 | .514 | .513 ± .005 | 68.0 ± 3.2 | 79.6 ± 1.4 |
| 1.5 | .472 | .472 ± .008 | 60.8 ± 3.6 | 77.2 ± 2.3 |
| 2 | .452 | .456 ± .011 | 55.2 ± 4.1 | 73.6 ± 3.1 |
| 2.5 | .443 | .453 ± .013 | 47.2 ± 3.9 | 68.4 ± 4.0 |
| 3 | .440 | .457 ± .016 | 38.0 ± 3.9 | 65.2 ± 4.3 |
| 3.5 | .439 | .466 ± .018 | 33.6 ± 4.4 | 59.2 ± 4.7 |
| 4 | .439 | .477 ± .021 | 29.2 ± 4.5 | 51.6 ± 4.7 |
| 5 | .439 | .505 ± .025 | 20.4 ± 4.7 | 39.2 ± 5.5 |
| 6 | .439 | .536 ± .028 | 15.2 ± 4.4 | 28.4 ± 4.9 |
| 8 | .439 | .599 ± .032 | 7.6 ± 3.4 | 14.8 ± 4.4 |
*The top 5 overlap is always 80%.
- Noiseless sensitivity. The noiseless top 5 score error is very stable when , and the noiseless top 5 overlap is always 80% for all considered sweep.
- Noisy sensitivity. Increasing will cause a larger noise calibration, and hence induce a worse noisy performance.
The diagnostics show that regularization already limits head accuracy, while privacy noise can substantially worsen set recovery. It suggests us to choose a smaller to reduce the noise level in privacy mechanism, which effect is more significant than the bias in regularization.
Thanks for the detailed responses. The authors have addressed my concerns about the experimental results. The author should further enlarge the epsilon values to cover the mechanisms to strength the contributions. I maintain my rating of 3.
Thank you for the additional comment! In our response and revised manuscript, we have enlarged to cover the range from 0.5 to 8. We further included the Top 5 overlap in our manuscript, where we could see the improvement when . We believe that this certifies our contribution, given the difference between row-level and edge-level DP.
Weakness 1 (Part of Question 2): Choices of ε and δ
1. Results with δ=n−2.
Our original numerical analysis sets δ=0.1. Following this suggestion, we set δ=1/n2 and re-run the results.
For full vector mechanism, we have employed the Euclidean projection following Reviewer vMZn's suggestion, and the overall errors increase. Results can be found in the following table. Our original main observations persist: PR Full Vector achieves the lowest top-5% error and best average top-10 rank on all three datasets, while Uniform and Edge Flipping have smaller overall errors.
For Top-k mechanism, the change of δ only affects the case ε=8, where the reported Top-L overlaps decrease by at most 1.2 percentage points. Hence, we omit the table in this response, and we will update these affected entries in the revised manuscript.
Updated results at ε=64, δ=n−2.
2. Scaling of ε under different privacy definitions.
The different scaling of ε comes from the differential privacy of our interest. Our work protects an entire outgoing-link profile, whereas Epasto et al. evaluate PageRank under edge-level DP. In their definition, the personalized output delivered to a source node is protected against changes to an individual edge. An outgoing-link profile contains up to n edges. Consequently, the numerical ε values do not represent the same privacy guarantee.
Consider Email-Eu-core data, which has n=1005. An ordinary pure edge-DP guarantee with εedge=10 yields a worst-case row-level guarantee of εrow≤(n−1)εedge=1004×10=10040 by group privacy. It illustrates the difference between edge-DP and row-DP, and it explains the reason our DP budget seems much larger.
Our lower-bound construction further illustrates the difficulty of row-level private ranking. Again consider the Email-Eu-core data where n=1005. Let the minimum out-degree at least m=16 and δ=n−2, uniformly achieving 90% exact Top-k set recovery requires $\varepsilon\ge \log\left[ \frac{0.9-\delta}{0.1} \left(\binom{n-m+k-1}{k}-1\right) \right].$ It means ε≈10 for Top-1 and ε≈32 for Top-5. These worst-case bounds provide theoretical motivation for investigating larger row-level privacy budgets.
Just as an exploration, we compare our method with other methods for small ε∈0.5,1,2,4,8, with δ=n−2 and the same m and κ. The results are as follows. As indicated by the lower bound, there are no gains when ε is small. When ε=8, some improvements can be found. For Top-5/10 overlap, the results are similar.
The table reports mean relative score errors on the true Top-5/10 nodes over 50 releases; lower is better.