acceptodds
Under review as a conference paper at ICLR 2027

Minimax Optimal PageRank under Row-Level Differential Privacy

Abstract

PageRank turns directed links into node-importance scores, but a node's outgoing-link profile can encode sensitive behavior. We study differential privacy under replacement of one entire outgoing row on a fixed public node set. We propose two differential private PageRank mechanisms under row-level privacy, i.e., the full outgoing-link profile. Both proposed mechanisms share a regularized query that combines degree flooring with a cap on the mass transmitted by each node. We prove global row-sensitivity bounds and quantify regularization bias. DP PageRank–Full Vector adds calibrated Gaussian noise to release all ranking scores, while DP PageRank–Top uses Gumbel perturbations to release only the set of top nodes. We provide their utility guarantees as deviation from original non-private PageRank. We also develop lower bounds. The lower bounds match the upper bounds of our algorithms for dense networks, under both score estimation and the top- set recovery. Numerical studies on three real datasets and simulated networks further support the overwhelming superiority of our mechanisms.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Social network, PageRank, Differential privacy, Minimax optimal

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_vMZnOpenReview ↗
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-kk 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-kk 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},andtherespectivestatedbudgetconditions.Thefull−vectorresultcharacterizestheminimaxsquaredrelative−riskrate,whilethetop−, and the respective stated budget conditions. The full-vector result characterizes the minimax squared relative-risk rate, while the top-k$ result establishes matching separation-gap orders for fixed kk 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
  1. Outgoing-row replacement protects an entire outgoing-link profile, addressing a meaningful privacy objective distinct from edge-level and full node-level privacy.

  2. The shared regularized query supports both release mechanisms, with global sensitivity bounds covering dangling rows and explicit regularization-bias guarantees relative to original PageRank.

  3. 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 kk in the specified nonsaturated regime.

Critical weaknesses
  1. The matching theory assumes dense graphs with minimum out-degree Ω(n)\Omega(n) and δ=n−2\delta=n^{-2}, whereas the real-data experiments use sparse networks, δ=0.1\delta=0.1, and relatively large ε\varepsilon. Additional experiments under stricter privacy settings would clarify practical utility beyond the theoretical regime. Top-kk configurations selecting the pure-DP branch of Equation (9) should be distinguished, since their performance does not depend on δ\delta.

  2. Table 1 shows higher overall relative ℓ2\ell_2 error for Full Vector than Uniform on all three datasets at ε=64\varepsilon=64. Table 2 also reports lower mean overlap for Top-kk than Full Vector at K=L=5,ε=32K=L=5,\varepsilon=32. 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.

  3. 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 ℓ2\ell_2 error, although it offers no corresponding general guarantee for subgroup errors or ranking metrics.

  4. The experiments keep κ=4/n\kappa=4/n fixed, leaving its effect on practical utility insufficiently explored. A small κ\kappa 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
  1. 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?

  2. How do both mechanisms perform for ε∈{0.5,1,2,4,8}\varepsilon\in\{0.5,1,2,4,8\} and δ=n−2\delta=n^{-2}? Could noiseless-query results and a small sweep of cc in κ=c/n\kappa=c/n distinguish the Top-5 errors already present after regularization from the changes introduced by each mechanism’s noise?

4 comments

Weakness 1 (Part of Question 2): Choices of ε\varepsilon and δ\delta

1. Results with δ=n−2\delta = n^{-2}.

Our original numerical analysis sets δ=0.1\delta = 0.1. Following this suggestion, we set δ=1/n2\delta = 1/n^2 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-kk mechanism, the change of δ\delta only affects the case ε=8\varepsilon=8, where the reported Top-LL 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\varepsilon=64, δ=n−2\delta=n^{-2}.

DatasetMethodOverallTop 5%5–30%30–50%Bottom 50%Average rank of top-10 nodes
Email-Eu-corePR Full Vector.731.315.383.284.455383.1
Edge Flipping.643.474.293.043.318494.9
Uniform.644.475.294.042.318503.0
Naive Gaussian7.4751.6063.5002.7165.236502.0
CollegeMsgPR Full Vector.831.514.380.261.462802.8
Edge Flipping.735.605.288.080.290947.4
Uniform.735.605.288.080.290950.0
Naive Gaussian9.0142.1894.4792.9696.076945.5
Wiki-VotePR Full Vector.879.673.343.239.3822901.1
Edge Flipping.844.749.280.142.2303555.9
Uniform.844.749.280.142.2303558.0
Naive Gaussian13.1692.7335.4145.4609.1133563.0

2. Scaling of ε\varepsilon under different privacy definitions.

The different scaling of ε\varepsilon 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 nn edges. Consequently, the numerical ε\varepsilon values do not represent the same privacy guarantee.

Consider Email-Eu-core data, which has n=1005n=1005. An ordinary pure edge-DP guarantee with εedge=10\varepsilon_{\mathrm{edge}}=10 yields a worst-case row-level guarantee of εrow≤(n−1)εedge=1004×10=10040\varepsilon_{\mathrm{row}}\leq (n-1)\varepsilon_{\mathrm{edge}}=1004\times10=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=1005n=1005. Let the minimum out-degree at least m=16m=16 and δ=n−2\delta=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\varepsilon \approx 10 for Top-1 and ε≈32\varepsilon \approx 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\varepsilon \in {0.5, 1, 2, 4, 8}, with δ=n−2\delta = n^{-2} and the same mm and κ\kappa. The results are as follows. As indicated by the lower bound, there are no gains when ε\varepsilon is small. When ε=8\varepsilon = 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.

DatasetPR Full Vector metricε=0.5ε=1ε=2ε=4ε=8Uniform
Email-Eu-coreTop-5 score error1.1851.0771.020.958.824.828
Email-Eu-coreTop-10 score error1.2901.2001.057.989.831.811
CollegeMsgTop-5 score error1.0771.047.983.924.870.897
CollegeMsgTop-10 score error1.1531.049.984.927.866.886
Wiki-VoteTop-5 score error1.015.986.973.941.925.960
Wiki-VoteTop-10 score error1.023.988.970.943.921.953

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 ε\varepsilon. We take Edge-flipping with flipping probability p=11+exp⁡(ε/n)p=\frac{1}{1+\exp(\varepsilon/n)}, i.e. (ε/n)(\varepsilon/n)-edge-DP. Since replacing one outgoing row changes at most n−1n-1 edges, the entire perturbed graph satisfies (n−1nε,0)\left(\frac{n-1}{n}\varepsilon,0\right)-row-DP. Therefore, in our experiments, we use edge-flipping with (ε/n)(\varepsilon/n)-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 ℓ2\ell_2 sensitivity upper bound Δ=2β\Delta=\sqrt{2}\beta. This follows because π=(1−β)μ+βP⊤π\pi=(1-\beta)\mu+\beta P^\top\pi, with fixed public restart μ\mu, and P⊤πP^\top\pi is a probability vector. With β=0.8\beta=0.8, the bound is approximately 1.1314.
    We release π+Z\pi+Z, where Z∼N(0,σ2I)Z\sim\mathcal N(0,\sigma^2 I), and numerically calibrate σ\sigma using the analytical Gaussian mechanism (AGM). This guarantees (ε,δ)(\varepsilon,\delta)-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 ℓ2\ell_2 error.

At ε=64\varepsilon=64, δ=n−2\delta=n^{-2}, m=16m=16, and κ=4/n\kappa=4/n, overall relative ℓ2\ell_2 errors after projection are (with 95% CI):

MethodEmail-Eu-coreCollegeMsgWiki-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 Gaussian7.475 [7.283, 7.667]9.014 [8.681, 9.348]13.169 [12.746, 13.591]

*: Uniform assigns the PageRank vector to be 1/n1/n 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 c∈1,1.5,2,2.5,3,3.5,4,5,6,8c \in \\{1, 1.5, 2, 2.5, 3, 3.5, 4, 5, 6, 8\\} in κ=c/n\kappa=c/n 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.

ccNoiseless Top-5 score errorFull Vector Top-5 score errorFull Vector Top-5 overlap (%)PR Top-kk Top-5 overlap (%)
1.514.513 ± .00568.0 ± 3.279.6 ± 1.4
1.5.472.472 ± .00860.8 ± 3.677.2 ± 2.3
2.452.456 ± .01155.2 ± 4.173.6 ± 3.1
2.5.443.453 ± .01347.2 ± 3.968.4 ± 4.0
3.440.457 ± .01638.0 ± 3.965.2 ± 4.3
3.5.439.466 ± .01833.6 ± 4.459.2 ± 4.7
4.439.477 ± .02129.2 ± 4.551.6 ± 4.7
5.439.505 ± .02520.4 ± 4.739.2 ± 5.5
6.439.536 ± .02815.2 ± 4.428.4 ± 4.9
8.439.599 ± .0327.6 ± 3.414.8 ± 4.4

*The top 5 overlap is always 80%.

  • Noiseless sensitivity. The noiseless top 5 score error is very stable when c≥2c \geq 2, and the noiseless top 5 overlap is always 80% for all considered cc sweep.
  • Noisy sensitivity. Increasing cc 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 cc 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 ε\varepsilon 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 ε≥4\varepsilon \geq 4. We believe that this certifies our contribution, given the difference between row-level and edge-level DP.

Reviewer_4FrKOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies PageRank under row-level differential privacy on a fixed public node set, protecting each node’s entire outgoing-link profile. It combines degree flooring and source-mass clipping to control sensitivity, then releases either a Gaussian-perturbed score vector or a Gumbel-selected ordered top-k list. The analysis accounts for regularization bias relative to original PageRank and establishes sensitivity, privacy, and utility guarantees. Matching lower bounds characterize estimation rates and fixed-k set-recovery gaps under uniform restart and specified dense-graph assumptions. The capped estimation rate additionally uses a public choice between the Gaussian mechanism and the uniform vector. Experiments on three SNAP networks and synthetic graphs show gains in head-ranking accuracy, especially top-1 selection, but mixed full-vector estimation results. Benefits depend on the privacy budget, output length and metric.

Critical strengths
  1. The perturbation-guided regularization has a clear design rationale. Degree flooring bounds individual transition weights, while mass clipping bounds each source’s total contribution under outgoing-row replacement. The sensitivity bounds hold globally, including for dangling rows, and the bias analysis accounts for the interaction between the degree floor and the source contribution cap. By comparing against original PageRank, the analysis makes the tradeoff between regularization bias and privacy noise explicit.

  2. The paper establishes matching bounds on a public dense minimum-out-degree class under uniform restart. A row-preserving empirical-mean embedding yields matching full-vector relative-risk rates, while a packing construction gives a necessary gap for exact top-k recovery. For fixed k, the necessary and sufficient gap orders match in the stated nonsaturated regime. The lower bounds apply to arbitrary globally row-private mechanisms. This matching theory is the principal strength supporting acceptance.

Critical weaknesses
  1. The experimental evidence does not fully support the practical utility claims in the abstract. The smallest evaluated epsilon is 8, and PR Full Vector is evaluated only at delta = 0.1. The reported top-1 results for PR Top-k already use pure-DP calibration. Utility at smaller epsilon remains unclear, as does the utility of PR Full Vector at smaller delta. At epsilon = 64, PR Full Vector has higher overall relative L2 error than Uniform on all three real datasets: 0.736 versus 0.644, 0.884 versus 0.735, and 0.915 versus 0.844. Section 5 acknowledges these mixed results and the improvements in some head-ranking metrics, but the abstract still claims “overwhelming superiority.”

  2. The privacy calibration of Edge Flipping and Naive Gaussian is insufficiently specified. For Edge Flipping, the manuscript does not report the flip probability or explain how it translates into a total row-level privacy budget. For Naive Gaussian, it does not give the global L2 sensitivity bound or the rule used to set the noise scale. Without these details, I cannot verify that the comparisons use matched row-level privacy budgets or reproduce the baseline results.

Questions for authors
  1. What are the exact flip probability and row-level budget conversion used for Edge Flipping? What global L2 sensitivity bound and Gaussian calibration are used for Naive Gaussian? Please provide the corresponding total row-level privacy guarantees so that the comparisons can be checked under matched privacy budgets.

  2. Do the main ranking improvements persist at smaller epsilon? For PR Full Vector and the PR Top-k configurations that use approximate-DP calibration, how does utility change at substantially smaller delta, such as delta = n^(-2)?

  3. On the three real datasets, what are the overall relative error and top-k overlap of the regularized query before adding noise at m = 16 and kappa = 4/n? How sensitive are the main conclusions to the public multiplier in kappa = c/n? These results would help determine whether the observed estimation limitations are primarily due to regularization bias or privacy noise.

2 comments

Weakness 1 and Question 2. Question on the scale of ε\varepsilon and δ\delta.

1. Results with δ=n−2\delta = n^{-2}.

Our original numerical analysis sets δ=0.1\delta = 0.1. Following this suggestion, we set δ=1/n2\delta = 1/n^2 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-kk mechanism, the change of δ\delta only affects the case ε=8\varepsilon=8, where the reported Top-LL 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\varepsilon=64, δ=n−2\delta=n^{-2}.

DatasetMethodOverallTop 5%5–30%30–50%Bottom 50%Average rank of top-10 nodes
Email-Eu-corePR Full Vector.731.315.383.284.455383.1
Edge Flipping.643.474.293.043.318494.9
Uniform.644.475.294.042.318503.0
Naive Gaussian7.4751.6063.5002.7165.236502.0
CollegeMsgPR Full Vector.831.514.380.261.462802.8
Edge Flipping.735.605.288.080.290947.4
Uniform.735.605.288.080.290950.0
Naive Gaussian9.0142.1894.4792.9696.076945.5
Wiki-VotePR Full Vector.879.673.343.239.3822901.1
Edge Flipping.844.749.280.142.2303555.9
Uniform.844.749.280.142.2303558.0
Naive Gaussian13.1692.7335.4145.4609.1133563.0

2. Scaling of ε\varepsilon under different privacy definitions.

The different scaling of ε\varepsilon 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 nn edges. Consequently, the numerical ε\varepsilon values do not represent the same privacy guarantee.

Consider Email-Eu-core data, which has n=1005n=1005. An ordinary pure edge-DP guarantee with εedge=10\varepsilon_{\mathrm{edge}}=10 yields a worst-case row-level guarantee of εrow≤(n−1)εedge=1004×10=10040\varepsilon_{\mathrm{row}}\leq (n-1)\varepsilon_{\mathrm{edge}}=1004\times10=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=1005n=1005. Let the minimum out-degree at least m=16m=16 and δ=n−2\delta=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\varepsilon \approx 10 for Top-1 and ε≈32\varepsilon \approx 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\varepsilon \in {0.5, 1, 2, 4, 8}, with δ=n−2\delta = n^{-2} and the same mm and κ\kappa. The results are as follows. As indicated by the lower bound, there are no gains when ε\varepsilon is small. When ε=8\varepsilon = 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.

DatasetPR Full Vector metricε=0.5ε=1ε=2ε=4ε=8Uniform
Email-Eu-coreTop-5 score error1.1851.0771.020.958.824.828
Email-Eu-coreTop-10 score error1.2901.2001.057.989.831.811
CollegeMsgTop-5 score error1.0771.047.983.924.870.897
CollegeMsgTop-10 score error1.1531.049.984.927.866.886
Wiki-VoteTop-5 score error1.015.986.973.941.925.960
Wiki-VoteTop-10 score error1.023.988.970.943.921.953

Question 1 and Weakness 2: Clarification on ε\varepsilon and sensitivity bounds

Thank you for raising this question. We will clarify all the following points in our manuscript (still in work, after we finish all the comments).

Edge Flipping. Consider the row-level DP budget ε\varepsilon. We take Edge-flipping with flipping probability p=11+exp⁡(ε/n)p=\frac{1}{1+\exp(\varepsilon/n)}, i.e. (ε/n)(\varepsilon/n)-edge-DP. Since replacing one outgoing row changes at most n−1n-1 edges, the entire perturbed graph satisfies (n−1nε,0)\left(\frac{n-1}{n}\varepsilon,0\right)-row-DP. Therefore, in our experiments, we use edge-flipping with (ε/n)(\varepsilon/n)-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 ℓ2\ell_2 sensitivity upper bound Δ=2β\Delta=\sqrt{2}\beta. This follows because π=(1−β)μ+βP⊤π\pi=(1-\beta)\mu+\beta P^\top\pi, with fixed public restart μ\mu, and P⊤πP^\top\pi is a probability vector. With β=0.8\beta=0.8, the bound is approximately 1.1314.

We release π+Z\pi+Z, where Z∼N(0,σ2I)Z\sim\mathcal N(0,\sigma^2 I), and numerically calibrate σ\sigma using the analytical Gaussian mechanism (AGM). This guarantees (ε,δ)(\varepsilon,\delta)-row-DP for the entire released vector.

We believe this is a fair comparison.

 

Question 3: Noiseless PR vector and sensitivity on κ\kappa

Thank you for rasing this comment. We will add the following analysis to our revised manuscript.

Noiseless regularized query. Fixing m=16m=16 and κ=c/n\kappa = c/n, we obtain the following results before adding noise (no randomness here):

DatasetOverall ℓ2\ell_2 error, c=2Overall ℓ2\ell_2 error, c=4Top-5 overlap (%), both cTop-10 overlap (%), both c
Email-Eu-core.487.4718090
CollegeMsg.725.7248090
Wiki-Vote.826.8246060

These deterministic errors quantify regularization bias alone. When cc turns from 2 to 4, the change is very small.

Sensitivity on κ=c/n\kappa = c/n. We evaluated all ten values c∈1,1.5,2,2.5,3,3.5,4,5,6,8c \in \\{1, 1.5, 2, 2.5, 3, 3.5, 4, 5, 6, 8\\}, at ε=64\varepsilon=64 with δ=n−2\delta=n^{-2}. Below is the complete cc sweep at ε=64\varepsilon=64. Here we are discussing the private mechanism and results are means over 50 releases.

PR Top-kk overlap (%) with the true Top-kk set (higher is better): Bold case is the noiseless case.

ccEmail Top-5Email Top-10College Top-5College Top-10Wiki Top-5Wiki Top-10
179.678.881.277.460.058.6
1.577.270.277.663.660.453.8
273.661.271.244.660.849.2
2809080906060
2.568.448.863.228.860.439.4
365.238.450.817.259.229.4
3.559.229.642.011.456.420.0
451.623.432.47.454.412.6
539.213.816.83.848.46.4
628.48.810.03.036.83.0
814.84.64.81.616.40.8

These results show the tendency for a smaller cc. For the noiseless case, changing cc does not change the results; meanwhile, reducing cc will reduce the noise scale in noise calibration. Therefore, we always prefer a smaller cc.

The effect is not always exclusively through noise: smaller caps can introduce additional clipping bias. However, for these three graphs at m=16m=16, clipping is already inactive at c=4c=4, so larger tested cc values leave the noiseless query unchanged and only increase the calibrated noise. This explains the deterioration beyond c=4c=4.

When we change ε\varepsilon, the performance of cc may change. For example, at ε=128\varepsilon=128, Email's overall error is lower at c=1.5c=1.5 than at c=1c=1 (.409 versus .420). However, this change is not significant.

Reviewer_9LEQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

While the previous work has been limited to edge-level (pairwise) privacy, the authors introduce a row-level (entire out-going neighborhood). The authors introduce the notion of degree flooring bounds on transition weights and mass clipping bounds on total contributions. The authors perform empirical evaluation on three real-world datasets and evaluate the proposed approach. The paper is well written, easy to follow and provides all the necessary details.

Critical strengths
  • Row-level adjacency protects a stronger unit of information than changing a single edge.
  • The two regularization operations have distinct motivations (large individual transition weights and high source mass), with explicit sensitivity and bias analyses.
  • Full-vector and top-k mechanisms address different practical output goals.
  • There is a distinction between exact-set recovery guarantees from empirical average overlap.
  • Theoretical lower bounds are well defined.
Critical weaknesses

One objection I have for the evaluation, especially on error computations is that bucketing the ranks can minimize errors. Pagerank distribution for small-world power-law-like degree distributed graphs also tends to have power-law-like (exponential) pagerank values. The authors should consider other metrics such as rank biased ordering or consider the very top (like top-5 and top-10) values for measuring the error.

Questions for authors
  • How does your method compare with other methods for computing pagerank (dominant eigenvector)?
  • Can you add different ranking measure(s) (for example, top-5/top-10 score error, rank-biased overlap, or exact-set recovery with confidence intervals) and adjust your claims where the full-vector baseline loses to uniform?
  • How should mm and κ\kappa be selected using public information?
  • What happens to ranking quality when the degree floor regularizes many nodes in these low-median-degree networks?
4 comments

Thank you for these questions. We will revise our manuscript accordingly. Below please find our point-to-point response.

Q1. Comparison with other PageRank methods

Non-private methods. Standard methods such as power iteration compute PageRank as the dominant eigenvector of the transition matrix. We estimate the same target under row-level DP constraint. To protect the privacy, we use regularization and noise calibration. In our numerical analysis, we use non-private PageRank as the reference for evaluation.

Private methods. Existing private PageRank work mainly considers edge-level or joint edge-level privacy, with limited methods directly applicable to our row-level setting. We compare against Edge Flipping and Naive Gaussian/Gumbel under matched target row-level budgets. Edge Flipping uses ε/n\varepsilon/n per potential edge; pure-DP group privacy gives a row-level budget at most (n−1)ε/n≤ε(n-1)\varepsilon/n\le\varepsilon. Gaussian/Gumbel baselines are calibrated using their respective global row sensitivities.

GraphDiffusion (Wei et al., 2024) provides guarantees for undirected graphs under edge-level DP. These guarantees do not directly establish a matched-budget baseline for our directed, row-level DP setting. A simple generalization is to transform the directed network into a undirected network and apply GraphDiffusion, but that totally changes the object.

 

Q2 and Weakness. Additional score-error metrics and confidence intervals

We appreciate your suggestion on additional metrics for our private PR mechanism. In the past week, we evaluate score errors on the true top 5 and top 10 nodes, rather than percentile-based groups. For the true Top-kk set SkS_k, the metric is ∥π~(Sk)−π(Sk)∥2/∥π(Sk)∥2,k∈{5,10}\|\tilde{\pi}(S_k)-\pi(S_k)\|_2/\|\pi(S_k)\|_2,\quad k \in \{5, 10\} where π(S)\pi(S) denotes the scores restricted to SS.

The table below uses ε=64\varepsilon=64, δ=n−2\delta=n^{-2}, β=0.8\beta=0.8, m=16m=16, and κ=4/n\kappa=4/n. All vector methods receive identical Euclidean simplex projection. Entries report mean [pointwise 95% CI] over 50 releases; lower is better. Uniform is deterministic.

DatasetMethodTop-5 score errorTop-10 score error
Email-Eu-corePR Full Vector0.487 [0.465, 0.509]0.484 [0.468, 0.500]
Edge Flipping0.827 [0.826, 0.827]0.810 [0.809, 0.810]
Uniform0.8280.811
Naive Gaussian1.178 [0.977, 1.380]1.305 [1.044, 1.565]
CollegeMsgPR Full Vector0.737 [0.724, 0.750]0.728 [0.719, 0.738]
Edge Flipping0.897 [0.897, 0.897]0.886 [0.885, 0.886]
Uniform0.8970.886
Naive Gaussian1.439 [0.898, 1.981]1.887 [1.023, 2.752]
Wiki-VotePR Full Vector0.863 [0.859, 0.868]0.854 [0.850, 0.858]
Edge Flipping0.960 [0.960, 0.960]0.953 [0.953, 0.953]
Uniform0.9600.953
Naive Gaussian1.000 [1.000, 1.000]0.999 [0.998, 1.001]

PR Full Vector achieves the lowest mean Top-5 and Top-10 score errors on all three datasets. The result further demonstrates our statement, that we will distinguish these head-score improvements from overall estimation error, where Uniform remains better at this budget.

Q3. Choices of mm and κ\kappa

Choosing mm and κ\kappa using public information.

  • The degree floor mm regularizes low-out-degree nodes, and we would like mm that is still moderately large but it cannot regularize too many nodes. In networks, it is often observed that degrees increase at log⁡(n)\log(n) order, so a practical public heuristic is m≈Clog⁡nm\approx C\log n, with CC may informed by domain knowledge, a public reference network, or public subsample.

  • The parameter κ\kappa caps the source mass that each node can propagate. Since the average PageRank mass is 1/n1/n, a natural public parameterization is κ=c/n\kappa=c/n, with c>1c>1 allowing some inflation above this average. Larger cc permits greater contributions but increases the calibrated noise.

We use the common defaults m=16m=16 and κ=4/n\kappa=4/n across datasets and privacy budgets. For Email-Eu-core, where n=1005n=1005, this corresponds to m=16≈2.31log⁡nm=16\approx2.31\log n. Actually, this choice is close to 2log⁡n2\log n for all three datasets.

Parameter sensitivity.

Given the scale of mm and κ=c/n\kappa = c/n, the sensitivity to these two parameters is of interest.

Take Email-Eu-core dataset as an example, we report mm and cc sweeps at ε=64\varepsilon=64 and δ=n−2\delta=n^{-2}, averaging 50 releases per configuration. We set m=round⁡(Clog⁡n)m=\operatorname{round}(C\log n) for C∈1,1.5,2,2.5,3,3.5,4C\in\\{1,1.5,2,2.5,3,3.5,4\\}, and additionally include m∈8,16,32m\in\\{8,16,32\\}.

We consider Top 5% score error and Top-5 overlap. Bold entries mark the paper's parameter setting, m=16,c=4m=16,c=4.

\text{Varying }m\text{, with }c=4 \\\\ \begin{array}{rcc} \hline & \text{Top 5\\%} & \text{Top-5} \\\\ m & \text{score error} & \text{overlap (\\%)} \\\\ \hline 7 & .341 & 20.8 \\\\ 8 & .333 & 26.0 \\\\ 10 & .322 & 33.6 \\\\ 14 & .316 & 46.8 \\\\ \mathbf{16} & \mathbf{.317} & \mathbf{51.6} \\\\ 17 & .319 & 54.0 \\\\ 21 & .328 & 57.2 \\\\ 24 & .337 & 58.8 \\\\ 28 & .348 & 59.2 \\\\ 32 & .359 & 58.8 \\\\ \hline \end{array} \end{array} \qquad \begin{array}{c} \text{Varying }c\text{, with }m=16 \\\\ \begin{array}{rcc} \hline & \text{Top 5\\%} & \text{Top-5} \\\\ c & \text{score error} & \text{overlap (\\%)} \\\\ \hline 1 & .302 & 79.6 \\\\ 1.5 & .280 & 77.2 \\\\ 2 & .274 & 73.6 \\\\ 2.5 & .279 & 68.4 \\\\ 3 & .289 & 65.2 \\\\ 3.5 & .303 & 59.2 \\\\ \mathbf{4} & \mathbf{.317} & \mathbf{51.6} \\\\ 5 & .348 & 39.2 \\\\ 6 & .376 & 28.4 \\\\ 8 & .426 & 14.8 \\\\ \hline \end{array} \end{array}$$ These two tables demonstrate the following tendency: - When $m \geq \log n$, the difference in Top 5% score error is very small (0.316 -> 0.359). It suggests a "safe" choice of $m$. For the top 5 choices, a larger $m$ regularizes more low-degree nodes but reduces the privacy noise levels, inducing a better performance. For $m \geq 16$, the Top-5 overlap is always above 50%. - When it comes to $c$, a smaller $c$ is preferred. The Top 5% score error is stable when $c \leq 5$. For Top-5 overlap, a smaller $c$ always brings a larger overlap. Hence, we suggest a small $c = 1$ for sparse networks. Results for the other datasets will be in the revised manuscript by Nov. 17 (AoE). &nbsp; **Q4. Ranking quality when many nodes are regularized** In our real datasets, it occurs that many nodes are regularized. We would like to discuss in the following aspects. **1. Theoretical understanding.** For a node with out-degree $d<m$, degree flooring multiplies its outgoing transition row by $d/m$. This attenuates low-degree nodes' outgoing influence. Hence, the effect will be on the whole network. **2. Tail nodes in Email-Eu-core.** In Email-Eu-core, at $m=16$, 51.5% of nodes have $d<m$. These nodes carry only 18.8% of the original PageRank mass, and contains no true Top-10 nodes. It supplies 24.7% of the original link-following flow into the true Top-5 sets. Flooring these sources can therefore affect the top nodes even when the head nodes themselves have degrees above the floor. **3. Noiseless and noisy ranking quality.** We compare three settings about $m$. Noiseless means that we only apply regularization without noise. Therefore, the results are deterministic. Noisy results average 50 releases. Table 1: Each pair reports *Top-5 / Top-10 overlap (%)* with the corresponding original PageRank sets; higher is better. Bold entries mark the paper's setting. | $m$ | Nodes with $d<m$ (%) | Noiseless | Noisy Full Vector | Noisy PR Top-$k$ | |---:|---:|---:|---:|---:| | 8 | 38.2 | 80.0 / 90.0 | 23.2 / 22.4 | 26.0 / 7.2 | | **16** | **51.5** | **80.0 / 90.0** | **29.2 / 28.8** | **51.6 / 23.4** | | 32 | 72.6 | 80.0 / 90.0 | 22.0 / 24.2 | 58.8 / 34.4 | Although the fraction of nodes below the floor increases substantially, noiseless Top-5/10 overlap remains at 80%/90%. Regularization therefore preserves most of the head membership. Meanwhile, increasing $m$ reduces the privacy error calibration and hence improves PR Top-$k$ overlap.
Reviewer_9LEQOpenReview ↗

Thank you!

Thank you for the additional information and clarifications.

Thank you for your prompt response! If you have any additional comments, please let us know.

Reviewer_Nq5TOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies Page Rank on directed graphs where the privacy notion is defined as row-level DP. Authors give algorithms for releasing the full vectors of PageRank and top k ranked nodes. They also show lower bounds for identifying the top k set when the published output is ordered on dense graphs. The paper concludes with experimental evaluations.

Critical strengths

(S1) Studying page rank under a slightly stronger DP model than previously studied works that mainly studied edge-DP is strongly motivated (S2) The techniques used seem straightforward, but sound. (S3) The lower bounds for dense graphs in Section 4 are interesting theoretical contributions.

Critical weaknesses

(W1) The experiments use extremely permissive privacy parameter values of δ=0.1\delta=0.1, and \eps∈{8,32,128}\eps \in \{8, 32,128 \}. In comparison, the previous work by Epasto et al uses values ϵ≤10\epsilon \leq 10.

(W2) In Table 2, the full-vector mechanism is worse than a trivial data-independent baseline of uniform. Although the authors acknowledge that their full-vector mechanism does not uniformly outperform the data-independent baseline in overall estimation error, and show improvements in identifying highly ranked nodes, it is unclear what the practical purpose of the full-vector mechanism is. Especially since the paper separately proposes a top-k mechanism specifically targeting ranking accuracy. It would be good to clarify what additional practical benefits the full-vector mechanism provides.

(W3) The empirical results are on sparse graph datasets while the theoretical results establish optimality for dense graphs. This seems like a mismatch that should be corrected so that the paper reads more cohesively.

Questions for authors

My main concerns are regarding the experimental evaluation. (1) Could you clarify what the point of the full-vector mechanism is, considering that you only show it is useful for finding highly ranked nodes, which can be found using the top-k mechanism? (2) Can you show experiments for more reasonable privacy parameters?

2 comments

Weakness 1 and Question 2. Question on the scale of ε\varepsilon and δ\delta.

1. Results with a smaller δ\delta.

Our original numerical analysis sets δ=0.1\delta = 0.1. Following this suggestion, we set δ=1/n2\delta = 1/n^2 and re-run the results.

  • For full vector mechanism, we have employed the Euclidean projection following Reviewer vMZn's suggestion. The overall errors increase when δ\delta decreases. 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-kk mechanism, the change of δ\delta only affects the case ε=8\varepsilon=8, where the reported Top-LL 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\varepsilon=64, δ=n−2\delta=n^{-2}.

DatasetMethodOverallTop 5%5–30%30–50%Bottom 50%Average rank of top-10 nodes
Email-Eu-corePR Full Vector.731.315.383.284.455383.1
Edge Flipping.643.474.293.043.318494.9
Uniform.644.475.294.042.318503.0
Naive Gaussian7.4751.6063.5002.7165.236502.0
CollegeMsgPR Full Vector.831.514.380.261.462802.8
Edge Flipping.735.605.288.080.290947.4
Uniform.735.605.288.080.290950.0
Naive Gaussian9.0142.1894.4792.9696.076945.5
Wiki-VotePR Full Vector.879.673.343.239.3822901.1
Edge Flipping.844.749.280.142.2303555.9
Uniform.844.749.280.142.2303558.0
Naive Gaussian13.1692.7335.4145.4609.1133563.0

2. Scaling of ε\varepsilon under different privacy definitions.

The different scaling of ε\varepsilon 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 nn edges. Consequently, the numerical ε\varepsilon values do not represent the same privacy guarantee.

Consider Email-Eu-core data, which has n=1005n=1005. An ordinary pure edge-DP guarantee with εedge=10\varepsilon_{\mathrm{edge}}=10 yields a worst-case row-level guarantee of εrow≤(n−1)εedge=1004×10=10040\varepsilon_{\mathrm{row}}\leq (n-1)\varepsilon_{\mathrm{edge}}=1004\times10=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=1005n=1005. Let the minimum out-degree at least m=16m=16 and δ=n−2\delta=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\varepsilon \approx 10 for Top-1 and ε≈32\varepsilon \approx 32 for Top-5. These worst-case bounds provide theoretical motivation for investigating larger row-level privacy budgets.

AuthorsOpenReview ↗

Response to W2 (together with Q1) and W3

Weakness 2 & Question 1: Why full vector mechanism?

Thank you for this question. We would like to address it in the following two aspects: the meaning of full vector mechanism and the contribution of our paper.

1. Full vector mechanism offers scores, while Top-kk mechanism offers a selected set.

The PR Top-kk mechanism is to select a specified number kk of nodes. PR Full Vector, where a better name could be private ranking scores, is more flexible with additional information:

  • No pre-decided kk. For different size kk of interest, we simply take the top kk nodes with largest released score, based on the same released vector. We do not need to re-apply the mechanism.
    Therefore, this mechanism also provides the possiblity to release a sorted list, instead of just a subset.
  • PR Full Vector releases numerical scores beyond set membership. These scores can be used for downstream applications, such as the combination with texts. Such information is more rich than the membership only.

Thus, even though we already have the Top-kk mechanism selecting a fixed-size set, the Full Vector mechanism is still useful to address different practical needs.

2. Comparison with Uniform.

The main concern is that PR Full Vector has higher overall ℓ2\ell_2 error than Uniform on 3 real data sets. Even though it has a lower ℓ2\ell_2 error rate on the top 5% nodes, it still difficult to understand "Why we don't use Uniform?"

  • Dataset and goal. All these three networks are very sparse, which means the information is limited. Hence, many low-ranked nodes have small and similar PageRank scores, making Uniform a strong baseline for overall error.
    However, these rankings of low-ranking nodes are not informative in practice. When we search for a keyword, we wish there is a good ranking on the first page. If our expected results are on the last page, we do not care its exact ranking.
    This pratical scenario brings our focus to be on the top 5% nodes (top 50 in the Email-Eu-core network). Here, PR Full Vector mechanism performs much better than Uniform, and provides more information than Top-kk mechanism.
     
  • Score estimation on top nodes. We consider the score estimation for the top 5 and 10 nodes, which can be seen as additional information than Top-5/10 mechanism. The results can be found in the following table with δ=n−2\delta = n^{-2} and other parameters the same as the original paper.
    These results demonstrate improved score estimation, beyond identifying which nodes belong to a Top-kk set.
DatasetMethodTop-5 score errorTop-10 score error
Email-Eu-corePR Full Vector0.487 [0.465, 0.509]0.484 [0.468, 0.500]
Uniform0.8280.811
CollegeMsgPR Full Vector0.737 [0.724, 0.750]0.728 [0.719, 0.738]
Uniform0.8970.886
Wiki-VotePR Full Vector0.863 [0.859, 0.868]0.854 [0.850, 0.858]
Uniform0.9600.953

3. Private score estimation has independent theoretical value.

Our theory has established the lower bounds for full-vector estimation. These bounds characterize the fundamental privacy cost of estimating numerical PageRank scores. Furthermore, the upper bounds of our approach matches the lower bound when m≫n0.8m \gg n^{0.8} in our improved analysis (see response to next question). Understanding these limits, and further adjusting our goals to top nodes according to these limits, is important in the private ranking setting.

 

Weakness 3: Sparse networks in empirical studies vs Dense networks in theoretical results.

Thank you for highlighting this distinction. We have extended the theoretical analysis beyond the dense regime.

1. Extended theoretical results.

  • Full-vector score estimation. For lower bounds, we have extended the results beyond the dense regime. The upper bounds and utility analysis hold for all regimes. With the extend results, the upper and lower bounds match when m≍nam\asymp n^a for any fixed 4/5<a<14/5<a<1.

  • Top-kk recovery. For fixed kk, we have extended the matching result to m≍nam\asymp n^a for any fixed 0<a<10<a<1. Futhermore, we found that the lower bound and upper bound match on this generalized region. Hence, it further covers the sparse setting.

These extensions broaden the graph regimes covered by our optimality results.

2. The role of the sparse-network experiments.

Both mechanisms’ privacy guarantees and general utility bounds already apply to sparse graphs. The density restriction concerns the regimes where the upper and lower bounds match.

Our real-data experiments investigate practical performance on sparse networks. Encouragingly, the full-vector mechanism retains useful score-estimation performance, as detailed in our response to W2. It demonstrates the superiority of our privacy mechanism.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response: Revised Manuscript

We thank all reviewers for their thoughtful comments and constructive discussion. We have updated the manuscript, appendices, and supplementary materials to address these comments. Changes in the revised manuscript and appendices are highlighted in blue.

We apologize for the late update due to some personal issue. Hope there will still be sometime to review the revised materials and discuss.

Our main updates are summarized below.

1. Clarification and Positioning

  • Renamed Full Vector to Score to distinguish score estimation from Top-kk set identification.
  • Clarified the protection offered by row-level and edge-level DP and explained why their numerical privacy budgets are not directly comparable.

2. Theoretical Analysis

  • Extended the minimax matching result for Score to a broader range of minimum-outdegree conditions.
  • Extended recovery-gap matching from top-1 to any fixed kk, under the stated degree and privacy-budget conditions.
  • Incorporated Euclidean simplex projection into the Score mechanism and established the corresponding post-projection utility guarantee.

3. Data Analysis

  • Added smaller-ε\varepsilon experiments, with the main-text overlap table reporting ε=4,8,16\varepsilon=4,8,16 and supplementary results additionally covering ε=0.5,1,2\varepsilon=0.5,1,2.
  • Updated the experiments to use δ=n−2\delta=n^{-2}.
  • Added sensitivity analyses for the degree floor and mass cap, jointly reporting score error and Top-5 overlap.
  • Added a Noiseless reference to illustrate the tradeoff between regularization bias and privacy noise.
  • Clarified baseline privacy calibration, output postprocessing, and evaluation procedures.
  • Refined the definitions of relative error and overlap and expanded uncertainty reporting with pointwise 95% confidence intervals.

4. Supplementary Materials

  • Updated the complete proofs supporting the extended theoretical results.
  • Expanded the numerical implementation and reproducibility documentation, together with the accompanying code and result materials.
  • Added small-budget analyses and diagnostics of overall error, Top-10 overlap, and low-degree nodes’ PageRank mass and contributions to head-node inflow.
  • Re-ran the simulations under the updated algorithms and parameters and refreshed the corresponding results and figures.

Detailed point-to-point responses are in separate comments.

Thanks to everyone. The comments help to improve the quality of this manuscript.

AuthorsOpenReview ↗

Manuscript and Rebuttal Summary

We would like to thank the efforts of AC and all reviewers. Since it is close to the end of rebuttal period, we would like to summarize the key points of our manuscript and the rebuttal here.

 

Manuscript Take-Home Message:

  • Novel privacy target. Row-level DP protects a node’s entire outgoing edge list. This is a larger privacy unit than edge-level DP, and it is more meaningful in practice.
  • Novel, simple, and unified construction. We spot the specific challenge in row-level DP PageRank, that the global sensitivity is not under control. We propose degree flooring and source-mass clipping to address the challenge, and hence form a unified framework for both Score and Top-k releases under row-level DP.
  • Theoretical guarantees. We establish global privacy guarantees and matching utility upper and lower bounds for score estimation and exact top-k set recovery under specified conditions.
  • Empirical results. Experiments on real and synthetic directed networks demonstrate improved head-score accuracy and useful top-node recovery at larger privacy budgets, while revealing limitations at smaller budgets.

 

Main updates:

The core methodology remains unchanged. This revision strengthens two aspects:

  • Experiments. Addressing concerns about permissive privacy parameters, we use δ=n−2\delta = n^{-2} to be consistent with our theoretical analysis. We also try ε=4/8/16\varepsilon = 4/8/16 in the experiments, with even smaller ε\varepsilon results in the appendix. We further add parameter sensitivity, noiseless comparisons, and confidence intervals.
  • Theory. Addressing questions about the scope of optimality, we broaden the minimax matching regime for Score and extend the Top-k recovery analysis to arbitrary fixed k, clarifying the conditions under which the bounds match.

 

We believe the revision has improved the quality of this manuscript, without large changes on our key algorithm.

Best regards, Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.