Graph diffusion, which iteratively propagates real-valued substances among
the graph, is used in numerous graph/network-involved applications. However,
releasing diffusion vectors may reveal sensitive linking information in the
data such as transaction information in financial network data. However,
protecting the privacy of graph data is challenging due to its interconnected
nature. This work proposes a novel graph diffusion framework with edge-level
different privacy guarantees by using noisy diffusion iterates. The algorithm
injects Laplace noise per diffusion iteration and adopts a degree-based
thresholding function to mitigate the high sensitivity induced by low-degree
nodes. Our privacy loss analysis is based on Privacy Amplification by Iteration
(PABI), which to our best knowledge, is the first effort that analyzes PABI
with Laplace noise and provides relevant applications. We also introduce a
novel Infinity-Wasserstein distance tracking method, which tightens the
analysis of privacy leakage and makes PABI more applicable in practice. We
evaluate this framework by applying it to Personalized Pagerank computation for
ranking tasks. Experiments on real-world network data demonstrate the
superiority of our method under stringent privacy conditions.

本研究提出了一种新颖的图扩散框架，通过使用噪声扩散迭代对每条边提供不同的隐私保证，以保护图数据的隐私。通过引入 Laplace 噪声和基于度的阈值函数来减轻低度节点引起的高灵敏度。我们的隐私损失分析是基于迭代的隐私放大方法，并通过引入一种新颖的无穷 - 瓦砂均距追踪方法，进一步缩紧了隐私泄露的分析，使得迭代的隐私放大方法更适用于实践。将该框架应用于个性化 PageRank 计算的排名任务中，实验证明在严格的隐私条件下，我们的方法具有优势。

具有个性化 PageRank 应用的差分隐私图扩散

Differentially Private Graph Diffusion with Applications in Personalized  PageRanks

Report Noisy Max and Above Threshold are two classical differentially private
(DP) selection mechanisms. Their output is obtained by adding noise to a
sequence of low-sensitivity queries and reporting the identity of the query
whose (noisy) answer satisfies a certain condition. Pure DP guarantees for
these mechanisms are easy to obtain when Laplace noise is added to the queries.
On the other hand, when instantiated using Gaussian noise, standard analyses
only yield approximate DP guarantees despite the fact that the outputs of these
mechanisms lie in a discrete space. In this work, we revisit the analysis of
Report Noisy Max and Above Threshold with Gaussian noise and show that, under
the additional assumption that the underlying queries are bounded, it is
possible to provide pure ex-ante DP bounds for Report Noisy Max and pure
ex-post DP bounds for Above Threshold. The resulting bounds are tight and
depend on closed-form expressions that can be numerically evaluated using
standard methods. Empirically we find these lead to tighter privacy accounting
in the high privacy, low data regime. Further, we propose a simple privacy
filter for composing pure ex-post DP guarantees, and use it to derive a fully
adaptive Gaussian Sparse Vector Technique mechanism. Finally, we provide
experiments on mobility and energy consumption datasets demonstrating that our
Sparse Vector Technique is practically competitive with previous approaches and
requires less hyper-parameter tuning.

使用高斯噪音在测量上报延时过程中的分析显示，在对底层查询进行了有界假设的前提下，对于 Report Noisy Max 可以提供纯先验差分隐私界限，而对于 Above Threshold 可以提供纯后验差分隐私界限，并且所得到的界限是紧的且取决于可使用标准方法进行数值评估的闭合表达式。