.tocmtchapter mtchaptersubsection mtappendixnone

# Differentially Private Graph Diffusion with Applications in Personalized
PageRanks

Rongzhe Wei
Georgia Institute of Technology
<EMAIL_ADDRESS>&Eli Chien
Georgia Institute of Technology
<EMAIL_ADDRESS>
Pan Li
Georgia Institute of Technology
<EMAIL_ADDRESS>

###### Abstract

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
differential 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 $\infty$-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.

##  1 Introduction

Graph diffusion, characterized by propagating signals across networks, is used
in a variety of real-world applications. Variants of graph diffusion such as
PageRank [1] and heat kernel diffusion [2] has revolutionized the domains such
as web searching [3], community detection [4, 5, 6, 7], network analysis [8,
9] and advancements in graph neural networks [10, 11, 12, 13]. Despite their
widespread applications, directly releasing diffusion vectors can
inadvertently leak sensitive graph information and raise privacy concerns.
Hoskins et al. [14] demonstrate that the access to a small subset of random
walk-based similarities (e.g., commute times, personalized PageRank scores)
could disclose significant portions of network’s edges, a phenomenon known as
link disclosure [15]. Such attacks, for instance, may enable advertisers to
deploy invasive advertising tactics [16] or reveal sensitive transaction
information within financial networks [17]. Consequently, it becomes
critically important to design graph diffusion algorithms with privacy
safeguards.

Differential privacy (DP) is recognized as a gold standard used for
characterizing the privacy risk of data processing algorithms [18]. However,
the inherently interconnected nature of graph-structured data renders the
adaptation of DP to graphs non-trivial [19]. Previous studies often conduct
the analysis of output sensitivity and adopt output perturbation to keep graph
data private, which include the study on differentially private personalized
PageRanks (PPRs) [20], and other relevant graph algorithms such as max flow-
min cut [21], graph sparsification [22], spectral analysis [23, 24]. However,
output perturbation-based approaches often provide a less-than-ideal utility-
privacy tradeoff. Numerous studies suggest that incorporating noise during the
process, rather than at the output, can potentially enhance utility-privacy
tradeoffs [25].

In this work, we introduce a graph diffusion framework that ensures edge-level
DP guarantees based on noisy diffusion iterates. Our framework is the first to
incorporate privacy amplification by iterations (PABI) technique [26] into
graph diffusions. As graph diffusion can be viewed as iterating contraction
maps in $\ell_{1}$ space, we adopt per-iterate Laplace noise due to its better
performance than the Gaussian mechanism commonly adopted in previous PABI
frameworks and provide new analysis dedicated to Laplace noise. We also
propose a novel $\infty$-Wasserstein distance tracking analysis that can
tighten the state-of-the-art PABI bound [27] that relies on the space
diameter, which makes the bound valid for practical usage. Noticing diffusion
from low-degree nodes may introduce high sensitivity, our framework also also
proposes a theory-informed degree-based thresholding function at each step
diffusion to improve the utility-privacy tradeoff. Lastly, we specialize our
framework in the computation of PPR for node ranking tasks. Extensive
experiments reveal the advantages of our framework over baselines, especially
under stringent privacy requirements.

###  1.1 More Related Works

Extensive research has been dedicated to privacy protection within graphs,
specifically in the release of graph statistics and structures under DP
guarantees [28, 29]. The primary techniques to safeguard graph structures
involve the Laplace and exponential mechanisms [30]. Early contributions by
Nissim et al.[31] calibrated noise based on the smooth sensitivity of graph
queries, expanding beyond output perturbation. Karwa et al.[32] improved the
efficiency of privacy-preserving subgraph-counting queries by calibrating
Laplace noise according to smooth sensitivity. Different from these methods,
Zhang et al. [33] employed the exponential mechanism [34] to enhance privacy
protections. Concurrently, Hay et al.[35] developed a constraint-based
inference algorithm as a post-processing step to improve the quality of degree
sequences derived from output perturbation mechanisms. Further,
Kasiviswanathan et al.[36] used a top-down degree projection technique to
limit the maximum degree in graphs, thus controlling the sensitivity of degree
sequence queries. Additional efforts in privately releasing graph statistics
include outlinks [37], cluster coefficients [38], graph eigenvectors [39], and
edge weights [40].

In the realm of graph diffusion, the most related work to ours is by Epasto et
al. [20], which focuses on releasing the PPR vector using forward push [41]
and Laplace output perturbation. Some studies have shown that injecting noise
during the process may offer better privacy-utility trade-offs compared to
output perturbation methods [25] and our study compared with [20] provides
another use case. Traditionally, the composition theorem [42] is used to track
privacy guarantees for iterative algorithms, but it results in a bound that
may diverge with the number of iterations. Recently, the technique of PABI
[26, 27] was introduced to strengthen the privacy analysis of adding noise
during the process, which demonstrates a non-divergent privacy bound for
releasing final results if the iterations adopt contraction maps [27]. This
substantially tightens the divergent bound given by the naive application of
the DP composition theorem [43, 44]. Our framework also benefits from this
advantage and we further adapt Altschuler et al.’s analysis [27] to
incorporate the Laplace mechanism and provide a tightened space diameter
tracking, which makes the bound practically applicable in the graph diffusion
application.

##  2 Preliminaries

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ represent an undirected graph,
where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of edges,
equipped with an adjacency matrix $\mathbf{A}\in\\{0,1\\}^{n\times n}$, where
$n$ denotes the total number of nodes, i.e., $n=|\mathcal{V}|$. By
establishing an order for the nodes within the graph, we denote
$\mathbf{d}=[d_{1},d_{2},...,d_{n}]^{T}$ as the degree vector. Additionally,
let $\mathbf{D}=\text{diag}(\mathbf{d})$ and $\mathbf{e}_{i}$ signifies the
$i$-th standard basis. We denote $\mathcal{L}(\mathbf{0},\sigma)$ and
$\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I})$ as the zero mean Laplace and
Gaussian distributions, respectively. We define the set
$[n]=\\{1,2,\ldots,n\\}$, and $X_{i:j},i,j\in\mathbb{Z}_{+},i\leq j$ as joint
couple of $(X_{i},X_{i+1},\ldots,X_{j})$.

Graph Diffusion. First, we introduce the concept of Graph Diffusion
$\mathscr{D}$, which is commonly characterized by a series of diffusion map
$\phi_{k}$ defined by the random walk matrix
$\mathbf{P}=\mathbf{A}\mathbf{D}^{-1}$ [6, 12, 45]. Formally, We define the
graph diffusion $\mathscr{D}(\mathbf{s})$ with the initial seed $\mathbf{s}$
as

$\displaystyle\mathscr{D}(\mathbf{s})=\lim_{K\to\infty}\mathbf{s}_{K}=\lim_{K\to\infty}\phi_{K}\circ\cdots\circ\phi_{1}(\mathbf{s}),\;\text{where
}\phi_{k}(\mathbf{x})=\left(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\right)\mathbf{x}+\gamma_{3,k}\mathbf{s}.$
(1)

where $\mathbf{s}\in\mathbb{R}^{|\mathcal{V}|}$ is a stochastic vector on the
graph, and $\gamma_{1,k}+\gamma_{2,k}+\gamma_{3,k}=1$. Let
$\gamma_{\text{max}}=\max_{k}|\gamma_{1,k}|+|\gamma_{2,k}|$ denote the
Lipschitz constant of the graph diffusion mapping. $\mathbf{s}_{K}$ is the
diffusion vector at time $K$. The essence of a diffusion process is to model
how an initial vector $\mathbf{s}$ propagates through the graph over time.
Coefficient $\gamma_{i,k}$’s control how different resources contribute to the
$k$th step diffusion. When taking $\gamma_{1,k}=1-\gamma_{3,k}=\beta$ and
$\gamma_{2,k}=0$, Eq. (1) is recognized as the PageRank Diffusion [46] with
teleport probability $1-\beta$. The Exponential kernel diffusion, which
includes the specific case of the Heat Kernel diffusion [2], can also be
characterized with the composition of diffusion mappings via the infinitely
divisible property [47].

Personalization. Personalized graph diffusions, tailored to individual nodes
or localized neighborhoods, play a crucial role in many real-world
applications. These include recommendation systems [48], where personalized
diffusions improve suggestion relevance, community detection for identifying
subgroups within larger networks [7], targeted marketing strategies for
enhancing campaign effectiveness [49]. These diffusions are defined by setting
the graph diffusion vector $\mathbf{s}$ as $\mathbf{e}_{i}$ for an individual
node or $\mathbf{s}=\sum_{i\in S}\mathbf{e}_{i}/|S|$ for a neighborhood set
$S$. In this paper, we primarily discuss the single-node case while our
analysis can be generalized to a set of seed nodes.

Privacy Definition. Differential Privacy (DP)[18, 42] is widely recognized as
the standard framework for providing formal privacy guarantees for algorithms
that process sensitive data. This framework has further been extended under
Rényi divergence [44]. Its principles have been applied to safeguard sensitive
structures within graph algorithms, an metric noted as Edge-level Rényi
Differential Privacy (RDP). Details on the conversion from RDP to DP are
elaborated in App. E.

######  Definition 1 (Edge-level RDP[50, 51]).

A randomized graph algorithm $\mathcal{A}$ is $(\alpha,\epsilon)$-edge-level
RDP if for any adjacent graphs $\mathcal{G},\mathcal{G}^{\prime}$ that differs
in a single edge, we have
$\mathcal{D}_{\alpha}(\mathcal{A}(\mathcal{G})\|\mathcal{A}(\mathcal{G}^{\prime}))\leq\epsilon$,
where the Rényi Divergence
$\mathcal{D}_{\alpha}(X\|Y)=\frac{1}{\alpha-1}\log\mathbb{E}_{x\sim\nu}\left(\frac{\mu(x)}{\nu(x)}\right)^{\alpha}$
with $X\sim\mu,Y\sim\nu$.

More practical cases find that the seed node (user) of personalized graph
diffusion algorithms is already aware of their direct connections within the
network, such as one’s friend list in social networks, and one’s transaction
record in financial networks, and therefore protecting the edges directly
attached to the seed node becomes unnecessary. Instead, the focus of privacy
protection shifts towards obscuring the connections between the remaining
nodes. To address this specific need, we follow the previous study [20] and
introduce Personalized Edge-level RDP.

######  Definition 2 (Personalized Edge-level RDP[52, 20]).

Consider a graph $\mathcal{G}$ and a personalized graph algorithm
$\mathcal{A}$. The algorithm $\mathcal{A}$ satisfies personalized
$(\alpha,\epsilon)$-edge-level RDP if for any node $v$ as the seed node in
$\mathcal{G}$, and for any graph $\mathcal{G}^{\prime}$ adjacent to
$\mathcal{G}$ differing by one edge not incident to $v$, we have
$\mathcal{D}_{\alpha}(\mathcal{A}(\mathcal{G},v)\|\mathcal{A}(\mathcal{G}^{\prime},v))\leq\epsilon.$

##  3 Methodology

This study centers on a category of $\gamma_{\text{max}}<1$ Lipschitz
continuous graph diffusions, encompassing prevalent techniques such as
PageRank [1] and PPR [53]. It is noted that each diffusion map $\phi_{k}$
within graph diffusion maintains the total probability mass of the diffusion
vector $\mathbf{s}_{k}$, owing to the condition $\sum_{i\in[3]}\gamma_{i,k}=1$
and the property of the random walk matrix $\mathbf{P}$ being a left
stochastic matrix. This observation entails that the diffusion map $\phi_{k}$
in Eq. (1) constitutes a strictly contraction map in the metric space
$(\mathbb{R}^{|\mathcal{V}|},\|\cdot\|_{1})$. Consequently, graph diffusion
can be construed as a composite of contraction maps. The PABI technique has
been devised to privatize contractive iterations by injecting random noise per
iteration. Empirical studies suggest that distributing noise throughout the
diffusion steps can provide improved utility-privacy trade-offs compared to
output perturbation alone [25]. This insight serves as a key motivation for
employing PABI to establish privacy-preserving graph diffusion.

###  3.1 Preliminaries: Privacy Amplification by Iteration

The technique of Privacy Amplification by Iteration (PABI), originally
introduced by Feldman et al. [26] for convex risk minimization problems via
noisy gradient descent, bounds the privacy loss of an iterative algorithm
without releasing the full sequence of iterates. This approach applies to
processes generated by Contractive Noisy Iteration (CNI) defined as follows.

######  Definition 3 (Contractive Noisy Iteration (CNI) [26]).

Consider a Banach space $(\mathcal{X},\|\cdot\|)$ with an initial random state
$X_{0}\in\mathcal{X}$, a series of contractions (i.e., c-Lipschitz functions,
$c\leq 1$) $\psi_{k}:\mathcal{X}\to\mathcal{X}$, and a sequence of noise
random variables $\\{\xi_{k}\\}$. Defining $\mathcal{B}$ as a convex bounded
set, the Contractive Noisy Iteration
$\text{CNI}(X_{0},\\{\psi_{k}\\},\\{\xi_{k}\\},\mathcal{B})$ is governed by
the update rule:

$\displaystyle X_{k+1}=\mathscr{P}_{\mathcal{B}}[\psi_{t}(X_{k})+\xi_{k+1}]$
(2)

where $\mathscr{P}_{\mathcal{B}}$ is the projection operator onto
$\mathcal{B}$, respecting the norm $\|\cdot\|$.

In the PABI analysis by Feldman et al.[26], gradient descent is conceptualized
as a contractive mapping $\psi_{t}$ in the $\ell_{2}$ space. Leveraging an
additive Gaussian noise mechanism after each iteration, i.e.,
$\xi_{k}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbf{I})$, leads to the
observation that the Rényi divergence of identical CNIs with differing initial
conditions $X_{0}$ and $X_{0}^{\prime}$ decays inversely with respect to the
total number of iterations $K$. Specifically, it is observed that
$\mathcal{D}_{\alpha}(X_{K}\|X^{\prime}_{K})\leq\frac{\alpha\|\mathbf{X}_{0}-\mathbf{X}_{0}^{\prime}\|_{2}}{2K\sigma^{2}}$.
Altschuler et al.[27] further extended this framework with improved bound as
follows:

######  Proposition 1.

Let $X_{K}$ and $X^{\prime}_{K}$ denote the outputs from
$\text{CNI}(X_{0},\\{\psi_{k}\\},\\{\xi_{k}\\},\mathcal{B})$ and
$\text{CNI}(X_{0},\\{\psi_{k}^{\prime}\\},\\{\xi_{k}^{\prime}\\},\mathcal{B})$,
respectively, where
$\xi_{k},\xi_{k}^{\prime}\sim\mathcal{N}(0,\sigma^{2}I_{d})$. Define
distortion $\rho:=\sup_{k,x}\|\psi_{k}(x)-\psi^{\prime}_{k}(x)\|$ and let
$\mathcal{B}$ have diameter $D$. If $\\{\psi_{k}\\}$ and
$\\{\psi_{k}^{\prime}\\}$ are contractions with coefficient $c<1$, then for
any $\tau\in\\{0,\ldots,K-1\\}$,

$\displaystyle\mathcal{D}_{\alpha}(X_{K}\|X^{\prime}_{K})\leq\frac{\alpha}{\sigma^{2}}\biggl{[}\underbrace{(K-\tau)\rho^{2}\vphantom{c^{2(K-\tau)}D^{2}}}_{\text{Distortion
Absorption}}+\underbrace{c^{2(K-\tau)}D^{2}\vphantom{(T-\tau)\rho^{2}}}_{\text{PABI}}\biggl{]}.$
(3)

The bound in Eq. (3) demonstrates that the Rényi divergence between two CNIs
can be quantified by the cumulative Rényi divergence over Gaussian noise with
a distortion factor $\rho$ (the Distortion Absorption term), complemented by a
PABI term. The latter indicates that identical contractive transformations
applied to bounded processes reduce privacy leakage in an exponential manner.
Note that the bound in Eq. (3) is convex with respect to $\tau$, optimized
selection of $\tau$ leads to non-divergent upper bound
$\tilde{\rho}(\ln(D^{2}/\tilde{\rho})+1)$ where
$\tilde{\rho}=\rho^{2}/2\ln(1/c)$.

Note on Parameter Set Diameter $\bm{D}$. The privacy bound in Eq. (3) relies
on the assumption of bounded diameter $D$ of the parameter set $\mathcal{B}$
to upper bound $\infty$-Wasserstein distance (definition in App. A) between
the coupled CNI processes $X_{\tau}$ and $X_{\tau}^{\prime}$. Although in
theory, the upper bound of Eq. (3) only depends on $\log D$ by optimizing
$\tau$, we notice that the value $D$ is important to get a _practically
meaningful_ privacy bound. To tighten this term, we will introduce a novel
$\infty$-Wasserstein distance tracking method that circumvents the need for
the diameter parameter in Lemma 3 (detailed later): A high-level idea is to
track the $\infty$-Wasserstein distance between noisy iterates via constructed
couplings instead of using the default set diameter as an upper bound.

Note on Noise Random Variables $\bm{\xi_{k}}$. The traditional PABI analysis
primarily examines gradient descent within the $\ell_{2}$ space employing the
Gaussian mechanism. In contrast, in the context of graph diffusions,
modifications to Proposition 1 are necessary to accommodate the $\ell_{1}$
norm and the application of Laplace noise. This adaptation to the Laplace
mechanism, crucial for the graph diffusion applications, has not been
previously addressed in the literature to our knowledge.

###  3.2 Private Graph Diffusions

We now introduce our noisy graph diffusion framework, designed to ensure edge-
level RDP and its personalized variant. Our approach consists of injecting
Laplace noise into the contractive diffusion process and integrating a graph-
dependent thresholding function to mitigate the high sensitivity associated
with perturbations of low-degree nodes.

Given a graph diffusion process $\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$,
we introduce a noisy graph diffusion $\mathscr{D}_{K,\sigma}$ where $K$
denotes the diffusion steps and $\sigma$ is the standard deviation of the
added noise, constructed by a series of composing noisy graph diffusion
mappings $\phi_{k,\sigma}$:

$\displaystyle\mathscr{D}_{K,\sigma}=\phi_{K,\sigma}\circ\phi_{K-1,\sigma}\circ\cdots\circ\phi_{1,\sigma},\;\text{where
}\phi_{k,\sigma}(\mathbf{s}_{k-1})=\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}+\xi_{k}^{(2)}.$
(4)

where $f$ is a graph-dependent degree-based function set as
$f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot\mathbf{d})$ for
$\phi_{k,\sigma}$, Noise variables $\xi_{k}^{(1)}$ and $\xi_{k}^{(2)}$ are
independently sampled from a Laplace distribution
$\mathcal{L}(\mathbf{0},\sigma)$. It is noteworthy that our framework can also
be extended to accommodate Gaussian distributions. However, Gaussian noise has
been shown to be suboptimal for graph diffusion in $\ell_{1}$ space, with
empirical evidence provided in App. D.4.

Design of Thresholding Function $\bm{f}$. In the noisy graph diffusion
process, the role of the graph-dependent thresholding function $f$ is twofold.
Firstly, $f$ ensures a bounded distance between the coupled diffusions over
two adjacent graphs, analogous to the role of the general projection operator
$\mathscr{P}_{\mathcal{B}}$ in the standard CNI as defined in Eq. (2).

Figure 1: Illustration of Distortion from Edge Perturbations over Adjacent
Graphs for Nodes with Low and High Degrees.

Such a bounding effect is also crucial for the later analysis of
$\infty$-Wasserstein distance tracking in Lemma 3. Secondly, and more
critically, our theoretical analysis reveals that edge perturbation affecting
low-degree nodes results in increased distortion at each diffusion step
(illustrated in Fig. 1). Uniform thresholding coupled with randomness
injection for all nodes typically yields suboptimal performance in such cases.
Our degree-dependent design naturally controls the distortion per iteration
caused by low-degree nodes which helps with reducing the added noise. More
detailed distortion analysis on $f$ is shown later in Lemma 2. The threshold
parameter $\eta$ is commonly employed to optimize the privacy-utility trade-
off in practical applications[20]. The empirical benefits of $f$ are explored
in experiments detailed in Sec. 4.2.

Discussion on Dual Noise Injection. Our framework employs a noise-splitting
technique, injecting dual Laplace noise at each diffusion step to construct
non-divergent privacy bounds, as outlined in Eq. (3). Theoretical
justifications for this design is provided in the proof sketch.

Following this, we present our main result on the privacy guarantee of noisy
graph diffusion:

######  Theorem 1 (Privacy Guarantees of Noisy Graph Diffusions).

Given a graph $\mathcal{G}$, an associate graph diffusion
$\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$, then noisy graph diffusion
mechanism $\mathscr{D}_{K,\sigma}$ ensures edge-level $(\alpha,\epsilon)$-RDP
with $\epsilon$ satisfies:

$\displaystyle\epsilon\leq\min_{\tau\in\\{0,1,...,K-1\\}}\left[(K-\tau)\cdot
g_{\alpha}\left(\sigma,\rho_{\text{diff}}\right)+g_{\alpha}\left(\sigma,\frac{\rho_{\text{diff}}}{1-\gamma_{\text{max}}}\cdot\gamma_{\text{max}}^{K-\tau}\right)\right]$
(5)

where
$g_{\alpha}(\sigma,\rho)=\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma}\rho))$
denotes the Rényi divergence induced by the Laplace mechanism [44]. The
distortion
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$
involves Lipschitz continuity coefficient $\gamma_{\text{max}}$, and maximum
diffusion coefficient
$\gamma_{\text{max}}^{(1)}=\max_{k\in[K]}|\gamma_{1,k}|$.

By selecting $\tau=\lceil
K-\ln((\frac{1}{\rho_{\text{diff}}}+\frac{1}{1-\gamma_{\text{max}}})\ln\frac{1}{\gamma_{\text{max}}})/\ln(\frac{1}{\gamma_{\text{max}}})\rceil$,
privacy budget $\epsilon$ remains bounded by

$\displaystyle\epsilon\lesssim\frac{\rho_{\text{diff}}}{\sigma\cdot\ln\left(\frac{1}{\gamma_{\text{max}}}\right)}\left[\ln\left(\left(\frac{1}{\rho_{\text{diff}}}+\frac{1}{1-\gamma_{\text{max}}}\right)\ln\frac{1}{\gamma_{\text{max}}}\right)+1\right].$
(6)

The privacy bound in Eq. (5) consists of two components: the distortion
absorption term (the first term on the RHS) and the PABI term (the second term
in RHS). Distortion absorption quantifies the cumulative Rényi divergence over
Laplace noise with distortion $\rho_{\text{diff}}$, while the PABI term
quantifies the exponential decay rate, echoing the result in Eq. (3). However,
a key difference lies in our approach; instead of leveraging the projected set
diameter $D$ to control the distance between coupled CNIs, our proposed
$\infty$-Wasserstein tracking method yields a more practical term,
$\frac{\rho_{\text{diff}}}{1-\gamma_{\text{max}}}$. Further details and
utility evaluations of this tool are presented in the proof sketch and Sec.
4.2, respectively.

The function $g_{\alpha}(\sigma,\rho)$, which measures Rényi divergence for
the Laplace mechanism, increases with distortion $\rho$ and decreases with
noise scale $\sigma$. This behavior implies that reducing distortion and
increasing the noise scale enhances privacy. To achieve better calibrated
noise within a given privacy budget $\epsilon$, we calculate the two terms in
Eq. (5) for each $\tau$. Leveraging the monotonicity of
$g_{\alpha}(\sigma,\rho)$, we employ a binary search to identify the
appropriate noise scale $\sigma$. The optimal noise scale is then determined
by selecting the minimum value across various $\tau$ values, achieving this
efficiently with linear complexity relative to $\tau$.

In Eq. (6), we demonstrate the convergence of the privacy budget with respect
to diffusion steps $K$. This approach differs from the adaptive composition
theorem [42], which analyzes how privacy guarantees degrade when composed
mechanisms are applied. Although this method has commonly been employed to
protect privacy in graph learning models [50, 54, 51], it leads to a linear
increase in the privacy budget with the number of iterations $K$ under Rényi
divergence [44], potentially resulting in unbounded losses as $K$ grows to
infinity.

Figure 2: RDP vs. Total Diffusion Step $K$ with $\eta=10^{-5}$.

More importantly, even for a small number of diffusion steps, our framework
achieves a significantly better privacy budget under practical PPR diffusion
settings, as illustrated in Fig. 2. Further empirical evaluations are detailed
in App. D.4.

Note that our framework employs a uniform noise scale throughout the diffusion
process. However, our analysis can adapt to varied noise allocations, as
detailed in App. B. This flexibility supports potentially better utility under
specific privacy constraints.

###  3.3 Proof Sketch of Theorem 1

Proof Idea. Similar to Eq. (3), the privacy loss of adjacent graph diffusion
processes can be bounded as the sum of distortion absorption term incurred by
Laplace noise and a PABI term at intermediate step $\tau$ (Step 1 & 2).
Subsequently, we explore degree-based thresholding to manage distortion,
achieving a superior utility-privacy tradeoff (Step 3), and introduce
$\infty$-Wasserstein distance tracking to further tighten the divergence at
$\tau$ (Step 4).

Step 1: Interpretation of Iterates as Conditional CNI Sequences. Consider the
coupled graph diffusions $\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$ and
$\mathscr{D}^{\prime}=\\{\phi_{k}^{\prime}\\}_{k=1}^{\infty}$, and the
thresholding functions $f$ and $f^{\prime}$, operating over adjacent graphs
$\mathcal{G}$ and $\mathcal{G}^{\prime}$, respectively. In each diffusion
step, the first noise component constructs noisy iterates, while the second
noise component is used to absorb distortion incurred between the adjacent
graphs. We encapsulate the discussion as follows:

$\displaystyle\mathbf{s}_{k}=\underbrace{\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}}_{\text{Identical
CNI}}+\xi_{k}^{(2)},\;\mathbf{s}_{k}^{\prime}=\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}+\xi_{k}^{\prime(2)}\stackrel{{\scriptstyle
d}}{{=}}\underbrace{\phi_{k}(f(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}}_{\text{Identical
CNI}}+\tilde{\xi}_{k}^{\prime(2)}.$

where
$\xi_{k}^{(1)},\xi_{k}^{(2)},\xi_{k}^{\prime(1)},\xi_{k}^{\prime(2)}\sim\mathcal{L}(\mathbf{0},\sigma)$,
and
$\tilde{\xi}_{k}^{\prime(2)}\sim\mathcal{L}\left(\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))-\phi_{k}(f(\mathbf{s}_{k-1}^{\prime})),\sigma\right)$,
and $\stackrel{{\scriptstyle d}}{{=}}$ denotes equality in distribution.

When the distortion
$\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))-\phi_{k}(f(\mathbf{s}_{k-1}^{\prime}))$
is absorbed by the conditional event of noise variables, i.e.,
$\xi_{k}^{(2)}=\tilde{\xi}_{k}^{(2)}$, the coupled diffusion vectors evolve
with identical CNIs through the contractive mapping $\phi_{k}\circ f$. Note
that the Laplace distribution is essential for fully exploiting $\ell_{1}$
distortion in our analysis.

Step 2: Bounding Privacy Loss through Distortion Absorption and PABI. The
privacy loss of coupled iterates
$\mathcal{D}_{\alpha}(\mathbf{s}_{K}\|\mathbf{s}_{K}^{\prime})$ can be bounded
by the distortion from graph diffusion, and PABI:

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}\|\mathbf{s}_{K}^{\prime})\leq$
$\displaystyle\underbrace{\mathcal{D}_{\alpha}(\xi_{\tau+1:K}^{(2)}\|\tilde{\xi}_{\tau+1:K}^{\prime(2)})\vphantom{\sup_{\zeta_{\tau+1:K}}}}_{\text{Distortion
Absorption}}+\underbrace{\sup_{\zeta}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta)}_{\text{PABI}}$
(7)

This inequality arises from leveraging the post-processing and strong
composition rules of Rényi divergence. Here, $\zeta$ represents a joint noise
realization, and the parameter $\tau$ is introduced to balance the privacy
leakage from the two terms — the divergence between the shifted noise
variables accumulated from step $\tau+1$ to step $K$ (Distortion Absorption),
and the divergence across conditional CNIs employing identical transformations
$\phi_{k}\circ f$ (PABI).

Step 3: Bounding Distortion Absorption

######  Lemma 2 (Absorption of Distortion in Laplace Distribution).

For any $\tau\geq 0$, we have

$\displaystyle\mathcal{D}_{\alpha}(\xi_{\tau+1:K}^{(2)}\|\tilde{\xi}_{\tau+1:K}^{\prime(2)})\leq(K-\tau)g_{\alpha}(\sigma,\tilde{\rho})$
(8)

Here ,
$\tilde{\rho}=4\gamma_{\text{max}}^{(1)}\cdot\max_{\mathbf{x}\in\mathbb{R}^{n}}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|+\gamma_{\text{max}}\cdot\Delta
f$ measures the distortion incurred by single step diffusion, where $\Delta
f=\sup_{\mathbf{x}\in\mathbb{R}^{n}}\|f(\mathbf{x})-f^{\prime}(\mathbf{x})\|_{1}$.

The distortion $\tilde{\rho}$ depends on the thresholding function $f$
normalized by node degrees, i.e.,
$\max_{\mathbf{x}\in\mathbb{R}^{n}}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|$.
This observation highlights the importance of a degree-based design for the
thresholding function $f$. Uniform thresholding across all nodes results in
distortion proportional to $\frac{1}{d_{\text{min}}}$, introducing
unnecessarily large noise induced by low-degree nodes and degrading overall
performance. This in principle inspires the choice of $f$ relying on node
degrees. Consequently, $\tilde{\rho}$ is bounded by
$\rho_{\text{diff}}=(4\gamma_{1,\text{max}}+2\gamma_{\text{max}})\eta$.

Figure 3: Setting: Graph Diffusion with $\gamma_{1,k}=0.8,\gamma_{3,k}=0.2$.

Step 4: Upper Bounding PABI with $\bm{\infty}$-Wasserstein distance tracking.
To perform tight privacy analysis for the second term in Eq. (7), we develop a
novel $\infty$-Wasserstein distance tracking method for coupled CNIs. This
method discards the original boundedness condition in PABI (Eq. (3) Second
Term), which relies on the diameter $D$.

######  Lemma 3 (PABI with $\infty$-Wasserstein Distance Tracking).

Given two coupled graph diffusions mentioned above, for any $\tau\geq 0$, any
noise realization $\zeta$, we have

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta)\leq
g_{\alpha}(\sigma,\gamma_{\text{max}}^{K-\tau}w)$ (9)

where $w=\frac{\rho_{\text{diff}}}{1-\gamma_{\text{max}}}$ represents the
tracked $\infty$-Wasserstein distance over coupled CNIs.

We argue that using $w$ instead of the default diameter $D$ is crucial to make
the algorithm practically useful. There is no numerical evaluation in the
previous study [27]. Numerical comparison between $w$ and the diameter of
thresholding function $D=\eta\cdot\sum_{i=1}^{|\mathcal{V}|}d_{i}$, using the
real-world BlogCatalog dataset (detailed in Sec. 4), is illustrated in Fig.3.
$w$ achieves orders-of-magnitude improvement, which is still significant even
if $D$ impacts privacy loss via a logarithmic term. Further empirical
validations demonstrating significant utility improvements are detailed in
Sec. 4.2.

By substituting the bounds from Eq. (8) and Eq. (9) into Eq. (7), we establish
Theorem 1.

###  3.4 Personalized Graph Diffusion Algorithms with Application in PPR
Diffusion

In practice, graph diffusions often originate from a single node
$\mathbf{e}_{i}$, personalizing the algorithm to this seed node (user). Since
the output is provided only to the seed node, protecting its edge connections
becomes unnecessary, ensuring no privacy leakage in the first diffusion step
under personalized privacy guarantees. Consequently, the thresholding function
is tailored as follows:
$f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot\tilde{\mathbf{d}})$, where
$[\tilde{\mathbf{d}}]_{j}=[\mathbf{d}]_{j}$ for $j\neq i$ and
$[\tilde{\mathbf{d}}]_{i}$ can be set to any positive threshold. We employ
personalized edge-level RDP (Definition 2), caring two adjacent graphs with a
difference only in a single edge not linked directly to the seed node. This
approach is encapsulated in the following theorem:

######  Theorem 4 (Privacy Guarantees for Personalized Noisy Graph
Diffusions).

Given a graph $\mathcal{G}$, an associate graph diffusion
$\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$, then personalized noisy graph
diffusion mechanism $\mathscr{D}_{K,\sigma}$ with corresponding
$f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot\tilde{\mathbf{d}})$ ensures
personalized edge-level $(\alpha,\epsilon)$-RDP with $\epsilon$ satisfies:

$\displaystyle\epsilon\leq\min_{\tau\in\\{0,1,...,K-1\\}}\left[g_{\alpha}\left(\sigma,\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})\cdot\gamma_{\text{max}}^{K-\tau}}{1-\gamma_{\text{max}}}\right)+(K-\tau)\cdot
g_{\alpha}\left(\sigma,\rho_{\text{diff}}\cdot\mathbbm{1}_{\tau\neq
0}\right)\right]$ (10)

where $\mathbbm{1}$ denote indicator function.

PPR Application. Among various graph diffusions, PPR stands out as a prevalent
node proximity metric extensively used in graph mining and network analysis.
We may apply our noisy diffusion framework to PPR diffusion. We consider PPR
with lazy random walk as follows:

$\displaystyle\mathscr{D}(\mathbf{s})=(1-\beta)\sum_{k=0}^{\infty}\beta^{k}\mathbf{W}\mathbf{s}=\lim_{K\to\infty}\phi_{K}\circ\cdots\circ\phi_{1}(\mathbf{s}),\;\text{where
}\phi_{k}(\mathbf{x})=\beta\mathbf{W}\mathbf{x}+(1-\beta)\mathbf{s}.$ (11)

where lazy random walk matrix
$\mathbf{W}=\frac{1}{2}(\mathbf{P}_{\text{rw}}+\mathbf{I})$ and $(1-\beta)$
represents teleport probability.

Our framework incorporates noise into the diffusion process of each step of
PPR. The privacy guarantees for this noisy PPR are derived from Theorem 4 with
$\rho_{\text{diff}}=4\beta\eta$ and $\gamma_{\text{max}}=\beta$.

##  4 Experiments

In this section, we present empirical evaluations to support our theoretical
findings. Specifically, we apply the widely-used PPR algorithm (Sec. 3.4) to
real-world graphs. We focus on the accuracy of noisy PPR in ranking tasks
under personalized edge-level DP due to its practicality as noted in [20].

Benchmark Datasets. We conduct experiments on the following datasets:
BlogCatalog [55], a social network of bloggers with 10,312 nodes and 333,983
edges; Flickr [55], a photo-sharing social network with 80,513 nodes and
5,899,882 edges; and TheMarker [56], an online social network with 69,400
nodes and 1,600,000 edges.

Baselines. Our experimental study includes two baselines. DP-PUSHFLOWCAP [20]
is the only private PPR method using Laplace output perturbation, adapting the
approximate PPR algorithm with push operations [41]. Edge-Flipping is the
other baseline, which uses a randomized response mechanism [42] on the
adjacency matrix, excluding seed node-connected edges in personalized
scenarios. Entries are replaced with values in $\\{0,1\\}$ uniformly at random
with probability $p$ (detailed in App. E), or retained otherwise. This method
requires $\mathcal{O}(|\mathcal{V}|^{2})$ time to generate a private adjacency
matrix and increases its edge density, which limits its practicality. Both our
approach and DP-PUSHFLOWCAP offer better scalability. A comparison of running
times between different approaches is provided in App. D.2. In all
experiments, we only report results if a single trial can be completed within
12 hours on an AMD EPYC 7763 64-Core Processor, and thus Edge-Flipping cannot
be run on Flickr.

Metrics. For utility, we employ two ranking-based metrics: normalized
discounted cumulative gain at R (NDCG@R) and Recall@R [57], where R denotes
the cutoff point for the top-ranked items in the list. In our experiments, R
is set to 100. For privacy assessments, we utilize the personalized edge-level
$(\epsilon,\delta)$-DP, with $\delta$ set to $\frac{1}{\\#\text{edges}}$
following [51]. To ensure a fair comparison, both DP-PUSHFLOWCAP and Edge-
Flipping are analyzed using RDP. The privacy budgets for all methods are
subsequently converted to DP from RDP results, as elaborated in App. E. All
results are reported as averages over 100 independent trials, with 95%
confidence intervals.

###  4.1 Evaluating Privacy-Utility Tradeoffs on Ranking Tasks

In this series of experiments, we aim to assess the ranking performance of our
noisy graph diffusion (as delineated in Sec. 3.4) compared with baselines on
real-world graphs. We specifically examine privacy budget $\epsilon$ ranging
from $10^{-2}$ to $1$, PPR with parameter $\beta=0.8$. Considering that both
our approach and DP-PUSHFLOWCAP employ a thresholding parameter $\eta$ to
balance the privacy-utility trade-off, we select $\eta$ from a set of seven
values spanning orders of magnitude from $10^{-10}$ to $10^{-4}$, a range
empirically determined to be optimal across various datasets for both methods
($\eta=10^{-6}$ is chosen for DP-PUSHFLOWCAP in [20]). For each experiment, we
randomly choose an initial seed for diffusion and execute PPR for $100$
iterations following [20]. We report the average NDCG@100 score and Recall@100
compared to the standard noise-free PPR diffusion (Eq. (11)) over 100
independent trials in Fig. 4 and Fig. 5 respectively.

Figure 4: Trade-off between NDCG and Personalized Edge-level Privacy.

Results for NDCG@100. As illustrated in Fig. 4, our noisy graph diffusion
surpasses both baselines across all three datasets, where values below 0.7 are
ignored. In a strong privacy regime ($\epsilon\leq 0.1$), our approach
demonstrates significant improvement over DP-PUSHFLOWCAP, which relies on
output perturbation. This validates our claim that a noisy process achieves a
superior privacy-utility trade-off in stringent privacy settings.

Results for Recall@100. Fig. 5 illustrates the overlap of the top-100
predictions of privacy-preserving PPR variants with standard PPR. Across all
datasets, our method outperforms two baselines for $\epsilon$ values ranging
from $10^{-2}$ to $1$, further substantiating the advantages of our framework.

Figure 5: Trade-off between Recall and Personalized Edge-level Privacy.

Additional experiments on the sensitivity of ranking performance over
variations in $\eta$ are deferred to App. D.3, which demonstrate that our
approach is significantly more robust on the choice of the hyperparameter
$\eta$.

###  4.2 Ablation Study

In this section, we conduct an ablation study to verify the effectiveness of
our theory-guided designs, including the degree-based thresholding function
$f$, the $\infty$-Wasserstein distance tracking tool. Experiments were
conducted on BlogCatalog, utilizing PPR diffusion with parameter $\beta=0.8$,
and a total of $K=100$ diffusion steps. Additional ablation studies focusing
on variations in noise type and comparative analyses of noise scales across
different methods are detailed in App. D.4.

Degree-based Thresholding Function & $\bm{\infty}$-Wasserstein Tracking. We
evaluate the effectiveness of our graph-dependent thresholding function $f$
and $\infty$-Wasserstein distance tracking. We vary $\eta$ uniformly across
seven discrete values in from $10^{-4}$ to $10^{-10}$ and report the optimal
performance for all methods in Fig. 6. Firstly, we compare the degree-based
thresholding function
$f(\mathbf{s})=\min(\max(\mathbf{x},0),\eta\cdot\mathbf{d})$ (Red $\bullet$)
against its graph-independent variant
$\tilde{f}(\mathbf{s})=\min(\max(\mathbf{x},0),\eta\cdot\bm{1})$ (Red
$\times$), which uniformly clips over nodes regardless of their degree. As
$\epsilon$ varies from $0.1$ to $3$, the degree-based thresholding function
consistently outperforms its graph-independent counterpart, with a margin of
$0.1$ to $0.16$ in the NDCG score. This verifies the effectiveness of graph-
dependent thresholding function $f$, which can balance the privacy-utility
trade-off more effectively by focusing less on sensitive low-degree nodes.
Note that the graph-dependent (in)dependent thresholding function $f$
($\tilde{f}$) naturally induces a diameter $\eta|\mathcal{V}|$
($2\eta|\mathcal{E}|$), respectively, which can be utilized in the
modification of Theorem 1 for privacy accounting. However, the graph dependent
thresholding function $f$ results in a significantly larger diameter, which
substantially degrades utility. This underscores the importance of leveraging
$\infty$-Wasserstein tracking.

Figure 6: Effectiveness of degree-based thresholding function $f$ and
$\infty$-Wasserstein distance tracking.

We showcase the benefits of our $\infty$-Wasserstein distance tracking
analysis (Red Lines) on the privacy-utility tradeoff against diameter induced
bounds derived from $\ell_{1}$ projection (Green Lines) or thresholding
function-induced diameter (Blue Lines). The privacy bound of the $\ell_{1}$
projection is established based on a Laplace modification of Eq. (3) with a
diameter of 1. As shown in Fig. 6, methods employing $\infty$-Wasserstein
distance tracking analysis consistently outperform those based on $\ell_{1}$
projection and thresholding-induced diameter. We conclude that our
$\infty$-Wasserstein tracking analysis and the design of graph-dependent
thresholding function $f$ markedly enhance the privacy-utility tradeoff.

##  5 Conclusion

In summary, we introduce a noisy graph diffusion framework for edge-level
privacy protection, utilizing a novel application of PABI in $\ell_{1}$ space.
By incorporating a theory-guided design for a graph-dependent thresholding
function and employing a new $\infty$-Wasserstein distance tracking tool, we
outperform SOTA methods in ranking performance on benchmark graph datasets.

Societal Impact and Limitations. Our work advances the development of DP graph
algorithms, offering strong privacy protection when properly implemented. At
present, we do not aware of any negative social impact resulting from this
research. The effectiveness of our noisy graph diffusion framework has been
demonstrated primarily in the context of PPR diffusion. Extending these
results to other types of graph diffusions, such as heat kernel diffusion, is
a promising direction for future research. This paper focuses on edge-level
privacy protections; exploring extensions to node-level DP protections could
further broaden the scope of our research.

## Acknowledge

This work is supported by NSF awards CCF-2402816, IIS-2239565, and JPMC
faculty award 2023. The authors would like to thank Haoyu Wang, Haoteng Yin
for the valuable discussion. The authors also would like to thank Alessandro
Epasto for the discussion about the implementation of the output-perturbation-
based differentially private Personalized Pagerank.

## References

  * [1] L. Page, S. Brin, R. Motwani, T. Winograd, et al., “The pagerank citation ranking: Bringing order to the web,” 1999.
  * [2] F. Chung, “The heat kernel as the pagerank of a graph,” Proceedings of the National Academy of Sciences, vol. 104, no. 50, pp. 19735–19740, 2007.
  * [3] J. Cho and U. Schonfeld, “Rankmass crawler: A crawler with high pagerank coverage guarantee.,” in VLDB, vol. 7, pp. 23–28, Citeseer, 2007.
  * [4] R. Andersen, F. Chung, and K. Lang, “Using pagerank to locally partition a graph,” Internet Mathematics, vol. 4, no. 1, pp. 35–64, 2007.
  * [5] S. Fortunato, “Community detection in graphs,” Physics reports, vol. 486, no. 3-5, pp. 75–174, 2010.
  * [6] K. Kloster and D. F. Gleich, “Heat kernel based community detection,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1386–1395, 2014.
  * [7] P. Li, I. Chien, and O. Milenkovic, “Optimizing generalized pagerank methods for seed-expansion community detection,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [8] G. Iván and V. Grolmusz, “When the web meets the cell: using personalized pagerank for analyzing protein interaction networks,” Bioinformatics, vol. 27, no. 3, pp. 405–407, 2011.
  * [9] D. F. Gleich, “Pagerank beyond the web,” siam REVIEW, vol. 57, no. 3, pp. 321–363, 2015.
  * [10] J. Gasteiger, A. Bojchevski, and S. Günnemann, “Predict then propagate: Graph neural networks meet personalized pagerank,” arXiv preprint arXiv:1810.05997, 2018.
  * [11] J. Gasteiger, S. Weißenberger, and S. Günnemann, “Diffusion improves graph learning,” Advances in neural information processing systems, vol. 32, 2019.
  * [12] E. Chien, J. Peng, P. Li, and O. Milenkovic, “Adaptive universal generalized pagerank graph neural network,” arXiv preprint arXiv:2006.07988, 2020.
  * [13] B. Chamberlain, J. Rowbottom, M. I. Gorinova, M. Bronstein, S. Webb, and E. Rossi, “Grand: Graph neural diffusion,” in International Conference on Machine Learning, pp. 1407–1418, PMLR, 2021.
  * [14] J. Hoskins, C. Musco, C. Musco, and B. Tsourakakis, “Inferring networks from random walk-based node similarities,” Advances in Neural Information Processing Systems, vol. 31, 2018.
  * [15] L. Backstrom, C. Dwork, and J. Kleinberg, “Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography,” in Proceedings of the 16th international conference on World Wide Web, pp. 181–190, 2007.
  * [16] I. Ullah, R. Boreli, and S. S. Kanhere, “Privacy in targeted advertising: A survey,” arXiv preprint arXiv:2009.06861, 2020.
  * [17] Q. Zhong, Y. Liu, X. Ao, B. Hu, J. Feng, J. Tang, and Q. He, “Financial defaulter detection on online credit payment via multi-view attributed heterogeneous information network,” in Proceedings of the web conference 2020, pp. 785–795, 2020.
  * [18] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265–284, Springer, 2006.
  * [19] C. Liu, S. Chakraborty, and P. Mittal, “Dependence makes you vulnberable: Differential privacy under dependent tuples.,” in NDSS, vol. 16, pp. 21–24, 2016.
  * [20] A. Epasto, V. Mirrokni, B. Perozzi, A. Tsitsulin, and P. Zhong, “Differentially private graph learning via sensitivity-bounded personalized pagerank,” Advances in Neural Information Processing Systems, vol. 35, pp. 22617–22627, 2022.
  * [21] A. Gupta, K. Ligett, F. McSherry, A. Roth, and K. Talwar, “Differentially private combinatorial optimization,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1106–1125, SIAM, 2010.
  * [22] R. Arora and J. Upadhyay, “On differentially private graph sparsification and applications,” Advances in neural information processing systems, vol. 32, 2019.
  * [23] S. Wang, Y. Zheng, X. Jia, and X. Yi, “Privacy-preserving analytics on decentralized social graphs: The case of eigendecomposition,” IEEE Transactions on Knowledge and Data Engineering, 2022.
  * [24] Y. Wang, X. Wu, and L. Wu, “Differential privacy preserving spectral graph analysis,” in Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, April 14-17, 2013, Proceedings, Part II 17, pp. 329–340, Springer, 2013.
  * [25] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016.
  * [26] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, “Privacy amplification by iteration,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521–532, IEEE, 2018.
  * [27] J. Altschuler and K. Talwar, “Privacy of noisy stochastic gradient descent: More iterations without more privacy loss,” Advances in Neural Information Processing Systems, vol. 35, pp. 3788–3800, 2022.
  * [28] S. Ji, P. Mittal, and R. Beyah, “Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: A survey,” IEEE Communications Surveys & Tutorials, vol. 19, no. 2, pp. 1305–1326, 2016.
  * [29] J. H. Abawajy, M. I. H. Ninggal, and T. Herawan, “Privacy preserving social network data publication,” IEEE communications surveys & tutorials, vol. 18, no. 3, pp. 1974–1997, 2016.
  * [30] Y. Li, M. Purcell, T. Rakotoarivelo, D. Smith, T. Ranbaduge, and K. S. Ng, “Private graph data release: A survey,” ACM Computing Surveys, vol. 55, no. 11, pp. 1–39, 2023.
  * [31] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75–84, 2007.
  * [32] V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, “Private analysis of graph structure,” Proceedings of the VLDB Endowment, vol. 4, no. 11, pp. 1146–1157, 2011.
  * [33] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao, “Private release of graph statistics using ladder functions,” in Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp. 731–745, 2015.
  * [34] F. McSherry and K. Talwar, “Mechanism design via differential privacy,” in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pp. 94–103, IEEE, 2007.
  * [35] M. Hay, C. Li, G. Miklau, and D. Jensen, “Accurate estimation of the degree distribution of private networks,” in 2009 Ninth IEEE International Conference on Data Mining, pp. 169–178, IEEE, 2009.
  * [36] S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith, “Analyzing graphs with node differential privacy,” in Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pp. 457–476, Springer, 2013.
  * [37] C. Task and C. Clifton, “A guide to differential privacy theory in social network analysis,” in 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 411–417, IEEE, 2012.
  * [38] Y. Wang, X. Wu, J. Zhu, and Y. Xiang, “On learning cluster coefficient of private networks,” Social network analysis and mining, vol. 3, pp. 925–938, 2013.
  * [39] F. Ahmed, A. X. Liu, and R. Jin, “Publishing social network graph eigenspectrum with privacy guarantees,” IEEE Transactions on Network Science and Engineering, vol. 7, no. 2, pp. 892–906, 2019.
  * [40] X. Li, J. Yang, Z. Sun, J. Zhang, et al., “Differential privacy for edge weights in social networks,” Security and Communication Networks, vol. 2017, 2017.
  * [41] R. Andersen, F. Chung, and K. Lang, “Local graph partitioning using pagerank vectors,” in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 475–486, IEEE, 2006.
  * [42] C. Dwork, A. Roth, et al., “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014.
  * [43] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in International conference on machine learning, pp. 1376–1385, PMLR, 2015.
  * [44] I. Mironov, “Rényi differential privacy,” in 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263–275, IEEE, 2017.
  * [45] W. Ye, Z. Huang, Y. Hong, and A. Singh, “Graph neural diffusion networks for semi-supervised learning,” arXiv preprint arXiv:2201.09698, 2022.
  * [46] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bring order to the web,” in Proc. of the 7th International World Wide Web Conf, 1998.
  * [47] R. Kondor and J.-P. Vert, “Diffusion kernels,” kernel methods in computational biology, pp. 171–192, 2004.
  * [48] M. Göksedef and Ş. Gündüz-Öğüdücü, “Combination of web page recommender systems,” Expert Systems with Applications, vol. 37, no. 4, pp. 2911–2922, 2010.
  * [49] S. Hwang and Y. Lee, “Identifying customer priority for new products in target marketing: Using rfm model and textrank,” Innovative Marketing, vol. 17, no. 2, p. 125, 2021.
  * [50] S. Sajadmanesh, A. S. Shamsabadi, A. Bellet, and D. Gatica-Perez, “$\\{$GAP$\\}$: Differentially private graph neural networks with aggregation perturbation,” in 32nd USENIX Security Symposium (USENIX Security 23), pp. 3223–3240, 2023.
  * [51] E. Chien, W.-N. Chen, C. Pan, P. Li, A. Ozgur, and O. Milenkovic, “Differentially private decoupled graph convolutions for multigranular topology protection,” Advances in Neural Information Processing Systems, vol. 36, 2024.
  * [52] M. Kearns, M. Pai, A. Roth, and J. Ullman, “Mechanism design in large games: Incentives and privacy,” in Proceedings of the 5th conference on Innovations in theoretical computer science, pp. 403–410, 2014.
  * [53] G. Jeh and J. Widom, “Scaling personalized web search,” in Proceedings of the 12th international conference on World Wide Web, pp. 271–279, 2003.
  * [54] S. Sajadmanesh and D. Gatica-Perez, “Progap: Progressive graph neural networks with differential privacy guarantees,” in Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pp. 596–605, 2024.
  * [55] R. Zafarani and H. Liu, “Social computing data repository at ASU,” 2009.
  * [56] R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in AAAI, 2015.
  * [57] K. Järvelin and J. Kekäläinen, “Cumulated gain-based evaluation of ir techniques,” ACM Transactions on Information Systems (TOIS), vol. 20, no. 4, pp. 422–446, 2002.
  * [58] T. Van Erven and P. Harremos, “Rényi divergence and kullback-leibler divergence,” IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3797–3820, 2014.
  * [59] M. Gil, F. Alajaji, and T. Linder, “Rényi divergence measures for commonly used univariate continuous distributions,” Information Sciences, vol. 249, pp. 124–131, 2013.

Appendix .tocmtappendix mtchapternone mtappendixsubsection

###### Contents

  1. 1 Introduction
    1. 1.1 More Related Works
  2. 2 Preliminaries
  3. 3 Methodology
    1. 3.1 Preliminaries: Privacy Amplification by Iteration
    2. 3.2 Private Graph Diffusions
    3. 3.3 Proof Sketch of Theorem 1
    4. 3.4 Personalized Graph Diffusion Algorithms with Application in PPR Diffusion
  4. 4 Experiments
    1. 4.1 Evaluating Privacy-Utility Tradeoffs on Ranking Tasks
    2. 4.2 Ablation Study
  5. 5 Conclusion
  6. A Preliminaries
  7. B Privacy Guarantees for General Noisy Graph Diffusion: Analytical Proofs
    1. B.1 Noisy Graph Diffusion with General Noise Allocations
    2. B.2 Main Proof
    3. B.3 Proof of Theorem 1
  8. C Discussion on Personalized Graph Diffusion
  9. D Additional Experiments
    1. D.1 Datasets and Experimental Environment
    2. D.2 Running Time
    3. D.3 Sensitivity of Ranking Performance to Variations in Threshold Parameter $\eta$.
    4. D.4 Ablation Study
  10. E RDP to DP Conversion
  11. F Proof of Lemmas
    1. F.1 Proof of Lemma B.1
    2. F.2 Proof of Lemma B.2
    3. F.3 Proof of Lemma B.3
    4. F.4 Proof of Lemma B.4.
    5. F.5 Proof of Lemma B.5.

##  Appendix A Preliminaries

In this section, definitions and lemmas are introduced to facilitate the
presentation of proofs. Recall that the contraction mapping denote a self-
mapping $l$-Lipschitz continuous function with $l\in[0,1]$, and the
$\infty$-Wasserstein distance is defined as
$W_{\infty}(\mu,\nu)=\inf_{\gamma\in\Gamma(\mu,\nu)}\mathrm{ess\,sup}_{(x,y)\sim\gamma}\|x-y\|$,
where $\Gamma(\mu,\nu)$ represents the collection of all couplings between
$\mu$ and $\nu$. Further, define
$\mathcal{R}_{\alpha}(\sigma,\rho):=\sup_{\mathbf{r}:\|\mathbf{r}\|\leq\rho}\mathcal{D}_{\alpha}(\xi+\mathbf{r}\|\xi)$,
where $\xi\sim\mathcal{L}(\mathbf{0},\sigma)$, measures the extent to which
the Laplacian distribution can absorb shifts of magnitude $\rho$. For clarity,
$\mathcal{D}_{\alpha}(\mu\|\nu)$ and $\mathcal{D}_{\alpha}(X\|Y)$, with
$X\sim\mu$ and $Y\sim\nu$, are used interchangeably when the context is clear.
Besides, we denote $X_{i:j},i,j\in\mathbb{Z}_{+},i\leq j$ as joint couple of
$(X_{i},X_{i+1},\ldots,X_{j})$. We introduce Shifted Rényi Divergence as
follows:

######  Definition A.1 (Shifted Rényi Divergence).

Let $\mu$ and $\nu$ be distributions defined over a Banach space
$(\mathcal{X},\|\cdot\|)$. For parameter $z\geq 0$ and $\alpha\geq 1$, the
$z$-shifted Rényi divergence between $\mu$ and $\nu$ is defined as

$\displaystyle\mathcal{D}_{\alpha}^{(z)}(\mu\|\nu)=\inf_{\mu^{\prime}:W_{\infty}(\mu,\mu^{\prime})\leq
z}\mathcal{D}_{\alpha}(\mu^{\prime}\|\nu)$ (12)

The following two lemmas illustrate how shifted Rényi divergence behaves under
noise convolution and contraction mapping.

######  Lemma A.1 (Shift-reduction lemma [26]).

Let $\mu,\nu,\varrho$ be probability distributions on $\mathbb{R}^{n}$. For
any $\rho\geq 0$,

$\displaystyle\mathcal{D}_{\alpha}^{(z)}(\mu*\varrho\|\nu*\varrho)\leq\mathcal{D}_{\alpha}^{(z+\rho)}(\mu\|\nu)+\sup_{\mathbf{r}:\|\mathbf{r}\|\leq\rho}\mathcal{D}_{\alpha}(\varrho+\mathbf{r}\|\varrho).$
(13)

######  Lemma A.2 (Contraction-reduction lemma [27]).

Suppose $\psi,\psi^{\prime}$ are random functions from $\mathbb{R}^{n}$ to
$\mathbb{R}^{n}$ such that (i) each is a strict $c$-contraction almost surely,
and (ii) there exists a coupling of $(\psi,\psi^{\prime})$ under which
$\sup_{\mathbf{x}}\|\psi(\mathbf{x})-\psi^{\prime}(\mathbf{x})\|\leq\rho$
almost surely. Then for any probability distributions $\mu$ and $\nu$ on
$\mathbb{R}^{n}$,

$\displaystyle\mathcal{D}_{\alpha}^{(cz+\rho)}(\psi_{\\#}\mu\|\psi^{\prime}_{\\#}\nu)\leq\mathcal{D}_{\alpha}^{(z)}(\mu\|\nu).$
(14)

Further, we recall two properties of RDP in our analysis.

######  Lemma A.3 (Post-processing Property of Rényi Divergence).

For any Rényi parameter $\alpha\geq 1$, any random function $f$, and any
probability measures $\mu,\nu$, we have

$\displaystyle\mathcal{D}_{\alpha}(f_{\\#}\mu\|f_{\\#}\nu)\leq\mathcal{D}_{\alpha}(\mu\|\nu)$
(15)

######  Lemma A.4 (Strong composition for RDP).

For any Rényi parameter $\alpha\geq 1$, and any two sequences of random
variables $X_{1},\ldots,X_{k}$ and $Y_{1},\ldots,Y_{k}$,

$\mathcal{D}_{\alpha}(\mathbb{P}_{X_{1:k}}\|\mathbb{P}_{Y_{1:k}})\leq\sum_{i=1}^{k}\sup\mathcal{D}_{\alpha}(\mathbb{P}_{X_{i}|X_{i-1}=x_{i-1}}\|\mathbb{P}_{Y_{i}|Y_{i-1}=x_{i-1}}).$

##  Appendix B Privacy Guarantees for General Noisy Graph Diffusion:
Analytical Proofs

In this section, we first extend our noisy graph diffusion to accommodate
general noise allocations and provide the corresponding privacy guarantees. We
then present the main proof for these results. Additionally, we consider
uniform noise allocation as a special case within this framework and derive
the results for Theorem 1 as detailed in Sec. 3.

###  B.1 Noisy Graph Diffusion with General Noise Allocations

In Sec. 3, we mainly considers noisy graph diffusion framework based on
uniform noise scheduling while in this section, we introduce noisy graph
diffusions with general noise allocations. Specifically, we introduce our
noisy graph diffusion framework as follows:

Given a graph diffusion $\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$ and a
total diffusion step $K$, the general noisy graph diffusion
$\mathscr{D}_{K,\Pi}$ is defined by a series of composed noisy graph diffusion
mappings $\phi_{k,\sigma_{k}}$, noise-free diffusion mappings $\phi_{l,f}$,
and a noise allocation tuple
$\Pi=(m,\sigma_{m+1},\sigma_{m+2},\ldots,\sigma_{K})$:

$\displaystyle\mathscr{D}_{K,\Pi}=\phi_{K,\sigma_{K}}\circ\phi_{K-1,\sigma_{K-1}}\circ\cdots\circ\phi_{m+1,\sigma_{m+1}}\circ\phi_{m,f}\circ\cdots\circ\phi_{1,f}$
(16)

where
$\phi_{k,\sigma_{k}}(\mathbf{s}_{k-1})=\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}+\xi_{k}^{(2)}$
and $\phi_{l,f}(\mathbf{s}_{l-1})=\phi_{l}(f(\mathbf{s}_{l-1}))$ with the
degree-based function $f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot d)$.
The noise allocation tuple determines when to introduce randomness and the
noise scales at each step.

The privacy guarantees of the noisy graph diffusion with general noise
allocations, as defined in Eq. (16), are summarized in the following theorem:

######  Theorem B.1 (Privacy Guarantees of Noisy Graph Diffusions).

Given a graph $\mathcal{G}$, an associate graph diffusion
$\mathscr{D}=\\{\phi_{k}\\}_{k=1}^{\infty}$ and a noise allocation tuple
$\Pi=(m,\sigma_{m+1},\cdots,\sigma_{K})$, define degree-based thresholding
function $f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot d),\forall
k\in\\{m+2,...,K\\}$, then noisy graph diffusion mechanism
$\mathscr{D}_{K,\Pi}$ satisfies edge-level $(\alpha,\epsilon)$-RDP with
$\epsilon$ satisfies:

$\displaystyle\epsilon=\min_{\tau\in\\{m,...,K-1\\}}\left[g_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})+\sum_{k=\tau+1}^{K}g_{\alpha}(\sigma_{k},\rho_{\text{diff}}^{\mathbbm{1}_{k\neq
m+1}}\lambda_{m+1}^{1-\mathbbm{1}_{k\neq m+1}})\right]$ (17)

where
$g_{\alpha}(\sigma,\rho)=\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma}\rho))$,
the distortion
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$,
noise-free shift
$\lambda_{m+1}=\frac{(1-\gamma_{\text{max}}^{m+1})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$,
and distortion
$w_{\tau}=\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})}{1-\gamma_{\text{max}}}$
with Lipschitz constant
$\gamma_{\text{max}}=\max_{k\in[K]}\sum_{j=1}^{2}|\gamma_{j,k}|$, and maximum
diffusion coefficient
$\gamma_{\text{max}}^{(1)}=\max_{k\in[K]}|\gamma_{1,k}|$.

###  B.2 Main Proof

###### Proof of Theorem B.1.

Given a seed $\mathbf{s}$, a total diffusion step $K$, a noise allocation
tuple $\Pi=(0,\sigma_{m+1},...,\sigma_{K})$, and thresholding functions
$f,f^{\prime}$, we consider two coupled graph diffusions
$\mathscr{D}_{K,\Pi}(\mathbf{s}),\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s})$
which propogate on two joint edge-level adjacent graphs
$\mathcal{G},\mathcal{G}^{\prime}$ respectively with diffusion mapping
$\phi_{k},\phi_{k}^{\prime},k\in[K]$. Specifically, we have

$\displaystyle\mathscr{D}_{K,\Pi}(\mathbf{s}):\quad$
$\displaystyle\mathbf{s}_{k}=\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}+\xi_{k}^{(2)},m+1\leq
k\leq K,$ $\displaystyle\mathbf{s}_{l}=\phi_{l}(f(\mathbf{s}_{l-1})),1\leq
l\leq m;$ (18) $\displaystyle\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s}):\quad$
$\displaystyle\mathbf{s}_{k}^{\prime}=\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}+\xi_{k}^{\prime(2)},m+1\leq
k\leq K,$
$\displaystyle\mathbf{s}_{l}^{\prime}=\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}^{\prime})),1\leq
l\leq m..$ (19)

where $\xi_{k}^{(1)},\xi_{k}^{\prime(1)},\xi_{k}^{(2)},\xi_{k}^{\prime(2)}$
are distributed according to the law $\mathcal{L}(\mathbf{0},\sigma_{k})$.

Step 1: Distortion of Single-Step Graph Diffusion In each diffusion step, a
distortion over the diffusion mappings $\phi_{k}\circ f$ is introduced due to
the graph adjacency between the graph diffusions
$\mathscr{D}_{K,\Pi}(\mathbf{s})$ and
$\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s})$. This distortion, which is crucial
for the subsequent analysis, is characterized by the following lemma:

######  Lemma B.1 (Distortion of Graph Diffusion).

Given two graph diffusions
$\mathscr{D}_{K,\Pi}(\mathbf{s}),\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s})$
mentioned above. Let $f,f^{\prime}$ denote corresponding thresholding
operators. The diffusion distortion:

$\displaystyle\sup_{\mathbf{x}\in\mathbb{R}^{n}}\|\phi_{k}(f(\mathbf{x}))-\phi_{k}^{\prime}(f^{\prime}(\mathbf{x}))\|_{1}\leq
4\gamma_{\text{max}}^{(1)}\cdot\max_{\mathbf{x}\in\mathbb{R}^{n}}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|+\gamma_{\text{max}}\cdot\Delta
f$ (20)

where $\Delta f=\sup_{x\in\mathbb{R}^{n}}\|f(x)-f^{\prime}(x)\|_{1}$,
$\gamma_{\text{max}}=\max_{k}\sum_{j=1}^{2}|\gamma_{j,k}|$, and
$\gamma_{\text{max}}^{(1)}=\max_{k}|\gamma_{1,k}|$.

We define the distortion as
$h=4\gamma_{1}\cdot\max_{\mathbf{x}\in\mathbb{R}^{n}}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|+\gamma_{\text{max}}\cdot\Delta
f$. The $\ell_{1}$ sensitivity between the thresholding functions $f$ and
$f^{\prime}$ over edge-adjacent graphs, i.e., $\Delta f$, is easily controlled
since only one edge differs. Therefore, the dominant term to control in the
distortion is
$\max_{\mathbf{x}\in\mathbb{R}^{n},i}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|$.
When selecting $f$ as the degree-based thresholding function, i.e.,
$f(\mathbf{x})=\min(\max(\mathbf{x},0),\eta\cdot\mathbf{d})$, the distortion
$h$ can be further simplified to
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$.

Step 2: Shift of Graph Diffusions without Randomness. Further, we examine the
coupled diffusion processes. For diffusion step from $l\in[m]$, as shown in
Eq. (18) and Eq. (19), no randomness is injected in the iterates. However,
since $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are edge-level adjacent, the
difference in $\phi_{k}$ and $\phi_{k}^{\prime}$ lead to a distortion in each
diffusion step. Therefore, at time step $m$, two processes are different from
each other with a shift described by the following lemma:

######  Lemma B.2 (Shift of Graph Diffusions without Randomness).

Consider two graph diffusions $\mathscr{D}_{K,\Pi}(\mathbf{s})$ and
$\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s})$ as previously described. The
difference in their states at any step $m$ is bounded as follows:

$\displaystyle\|\mathbf{s}_{m}-\mathbf{s}_{m}^{\prime}\|_{1}\leq\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}.$
(21)

Step 3: Bounding the Privacy Loss via Shift Absorption and PABI. Further, we
consider the noisy diffusion process, where we introduce Laplacian randomness
during graph propagation. For $k\geq m+1$, we can regard these two diffusion
processes as coupled CNIs starting from different initial points with maximum
shift
$\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$.
If both processes share identical diffusion mappings, then according to the
PABI principle, privacy guarantees will be amplified at an exponential rate.
With this in mind, and drawing upon the noise-splitting approach outlined in
[27], we mitigate the shifts caused by diffusion and thresholding by
integrating these factors into the noise distribution. Consequently, we
construct conditional CNI sequences with identical diffusion mappings for both
processes. Specifically, we reformulate the diffusion process
$\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s})$ as follows:

$\displaystyle\mathbf{s}_{k}^{\prime}=\phi_{k}(f(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}+\tilde{\xi}_{k}^{\prime(2)},\;\text{where
}\tilde{\xi}_{k}^{\prime}\sim\mathcal{L}(\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))-\phi_{k}(f(\mathbf{s}_{k-1}^{\prime})),\sigma_{k})$
(22)

where we introduce $\tilde{\xi}_{k}^{\prime(2)}$ as shifted Laplacian noise.
Therefore, the coupled graph diffusion processes can be summarized as follows:

$\displaystyle\mathbf{s}_{k}=\underbrace{\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}}_{\text{Identical
CNI}}+\xi_{k}^{(2)},\;\mathbf{s}_{k}^{\prime}=\underbrace{\phi_{k}(f(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}}_{\text{Identical
CNI}}+\tilde{\xi}_{k}^{\prime(2)},\;\forall k\geq m+1.$ (23)

Note that our objective is to establish an upper bound for
$\mathcal{D}_{\alpha}(\mathbf{s}_{K}\|\mathbf{s}_{K}^{\prime})$, we claim that
for any parameter $\tau\in\\{m,m+1,...,K-1\\}$,

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}\|\mathbf{s}_{K}^{\prime})\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K},\xi_{\tau+1:K}^{(2)}\|\mathbf{s}_{K}^{\prime},\tilde{\xi}_{\tau+1:K}^{\prime(2)})$
(24) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\underbrace{\mathcal{D}_{\alpha}(\xi_{\tau+1:K}^{(2)}\|\tilde{\xi}_{\tau+1:K}^{\prime(2)})\vphantom{\sup_{\zeta_{\tau+1:K}}}}_{\text{Shift
Absorption}}+\underbrace{\sup_{\zeta_{\tau+1:K}}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})}_{\text{PABI}}$
(25)

where $\zeta_{\tau+1:K}$ is a noise realization, $(a)$ is by the post-
processing inequality of Rényi Divergence (Lemma A.3), and $(b)$ is from the
strong composition rule for Rényi divergence (Lemma A.4).

As demonstrated in Eq. 25, the privacy leakage can be upper bounded by the
Rényi divergence across joint Laplacian distributions with a shift (shift
absorption term) and the divergence across conditional CNIs employing
identical transformations $\phi_{k}\circ f$ (PABI term). The parameter $\tau$
is introduced to balance the privacy leakage from shifts between noise
distributions against the leakage from CNIs starting from different initial
conditions. Both terms can be further bounded as detailed in the following
lemmas. It is important to emphasize that, for the latter, we leverage
$\infty$-Wasserstein distance tracking method that get rid of the diameter
requirement in original PABI analysis.

(1) Upper bounding shift absorption term:

######  Lemma B.3 (Absorption of Shift in Laplacian Distribution).

Given two coupled graph diffusions mentioned above, for any $\tau\geq m$, the
shift absorption term can be upper bounded by

$\displaystyle\mathcal{D}_{\alpha}(\xi_{\tau+1:K}^{(2)}\|\tilde{\xi}_{\tau+1:K}^{\prime(2)})\leq\sum_{k=\tau+1}^{K}g_{\alpha}(\sigma_{k},\rho_{\text{diff}}^{\mathbbm{1}_{k\neq
m+1}}\lambda_{m+1}^{1-\mathbbm{1}_{k\neq m+1}})$ (26)

where distortion
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$,
noise-free shift
$\lambda_{m+1}=\frac{(1-\gamma_{\text{max}}^{m+1})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$
and shifted laplace function
$g_{\alpha}(\sigma,\rho)=\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma}\rho))$.

(2) Upper bounding PABI term:

######  Lemma B.4 (PABI with Laplacian Distribution).

Given two coupled graph diffusions mentioned above, for any $\tau\geq m$, we
have

$\displaystyle\sup_{\zeta_{\tau+1:K}}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})\leq\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})+g_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})$
(27)

The lemma demonstrates that the PABI term is controlled by the shifted Rényi
divergence at step $\tau$ and a privacy amplification term that decays
exponentially at a rate of $\gamma_{\text{max}}^{K-\tau}w_{\tau}$. In previous
analyses of the PABI for the Gaussian mechanism, [27] utilized the diameter of
the bounded parameter set to further constrain the shift $w_{\tau}$. However,
we have found that this bound does not satisfactorily achieve a favorable
privacy-utility trade-off in practice. Subsequently, we develop a
$\infty$-Wasserstein distance tracking method to more effectively bound this
PABI term, offering a more practical approach.

######  Lemma B.5 (PABI with $\infty$-Wasserstein Distance Tracking).

Given two coupled graph diffusions mentioned above, for any $\tau\geq m$, we
have

$\displaystyle
W_{\infty}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})\leq\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})}{1-\gamma_{\text{max}}}=w_{\tau},\;\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})=0$
(28)

where distortion
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$.

By summarizing the above results (Lemma B.3, B.4, and B.5), we conclude the
final results:

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}\|\mathbf{s}_{K}^{\prime})\leq$
$\displaystyle\mathcal{D}_{\alpha}(\xi_{\tau+1:K}^{(2)}\|\tilde{\xi}_{\tau+1:K}^{\prime(2)})\vphantom{\sup_{\zeta_{\tau+1:K}}}+\sup_{\zeta_{\tau+1:K}}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})$
$\displaystyle\leq$
$\displaystyle\sum_{k=\tau+1}^{K}g_{\alpha}(\sigma_{k},\rho_{\text{diff}}^{\mathbbm{1}_{k\neq
m+1}}\lambda_{m+1}^{1-\mathbbm{1}_{k\neq
m+1}})+g_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})$ (29)

∎

###  B.3 Proof of Theorem 1

According to the proof in Sec. B.2, by setting $m=0$, we have
$\lambda_{1}=\rho_{\text{diff}}$. Furthermore, since
$w_{\tau}\leq\frac{\rho_{\text{diff}}}{1-\gamma_{\text{max}}}$, by selecting a
uniform noise allocation schedule, i.e., $\sigma_{k}=\sigma$, we obtain the
result in Theorem 1:

$\displaystyle\epsilon=\min_{\tau\in\\{0,...,K-1\\}}\left[g_{\alpha}(\sigma,\frac{\rho_{\text{diff}}\cdot\gamma_{\text{max}}^{K-\tau}}{1-\gamma_{\text{max}}})+\sum_{k=\tau+1}^{K}g_{\alpha}(\sigma,\rho_{\text{diff}})\right]$
(30)

##  Appendix C Discussion on Personalized Graph Diffusion

As discussed in Sec. 3.4, in many personalized scenarios, the definition of
personalized edge-level privacy shifts to protect edges that are not incident
to the source node. This adjustment offers additional benefits in distortion
analysis (Lemma B.1): no distortion occurs in the first step. According to the
proof of Lemma B.1, given a seed node $s$ with the corresponding initial
vector $\mathbf{s}$, and letting $(u,v)$ denote the edge differing on adjacent
graphs $\mathcal{G}$ and $\mathcal{G}^{\prime}$ where $s\notin\\{u,v\\}$, we
have:

$\displaystyle\|(\mathbf{A}\mathbf{D}^{-1}-\mathbf{A}^{\prime}\mathbf{D}^{\prime-1})\mathbf{s}\|_{1}\leq
2\left(\frac{[\mathbf{s}]_{u}}{d_{u}}+\frac{[\mathbf{s}]_{v}}{d_{v}}\right)=0$
(31)

since $[\mathbf{s}]_{u}=[\mathbf{s}]_{v}=0$. Thus, when analyzing noisy graph
diffusion in a personalized scenario, this distinction results in a better
bound for Lemma B.2 and B.3. Further, Eq. (31) demonstrate that we can relax
the thresholding over seed node to seek for better privacy-utility trade-offs.
Therefore, for uniform noise scheduling, we obtain the corresponding results
in Theorem 4:

$\displaystyle\epsilon=\min_{\tau\in\\{0,...,K-1\\}}\left[g_{\alpha}(\sigma,\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})\cdot\gamma_{\text{max}}^{K-\tau}}{1-\gamma_{\text{max}}})+(K-\tau)\cdot
g_{\alpha}(\sigma,\rho_{\text{diff}}\cdot\mathbbm{1}_{\tau\neq 0})\right]$
(32)

##  Appendix D Additional Experiments

###  D.1 Datasets and Experimental Environment

As mentioned in Section 4, this paper includes three benchmark datasets:
BlogCatalog, TheMarker, and Flickr. Their details are included in Table 1.

Dataset | Size | Statistics
---|---|---
Nodes $|\mathcal{V}|$ | Edges $|\mathcal{E}|$ | Classes $|\mathcal{C}|$ | Avg. Deg. | Density
Blogcatalog | 10k | 334k | 39 | 64.8 | $6.3\times 10^{-3}$
TheMarker | 69.4k | 1.6M | NA | 47 | $6.8\times 10^{-4}$
Flickr | 80k | 5.8M | 195 | 146 | $1.5\times 10^{-3}$
Table 1: Benchmark datasets and their statistics.

Experiments were performed on a server with two AMD EPYC 7763 64-Core
Processors, 2TB DRAM, six NVIDIA RTX A6000 GPUs (each with 48GB of memory).

###  D.2 Running Time

We report the running time for a single trial of each method across all
datasets in Fig. 7. As illustrated in the figure, all single trial experiments
of our method and DP-PUSHFLOWCAP are completed within 1 minute. In contrast,
the edgeflipping mechanism exhibits significantly longer running times,
ranging from 16 minutes to over 12 hours as the size of the graph increases.

Figure 7: Running Time for a Single Trial of Experiments with a Privacy Budget
of $\epsilon=0.1$.

###  D.3 Sensitivity of Ranking Performance to Variations in Threshold
Parameter $\eta$.

In this series of experiments, we further investigate the sensitivity of the
NDCG ranking performance with respect to the selection of $\eta$.
Specifically, we enhance the granularity of the $\eta$ values within the
existing range from $1\times 10^{-10}$ to $1\times 10^{-4}$ by selecting 20
equidistant points for each dataset within this interval. The NDCG ranking
performance is depicted in Fig. 8. The left column represents the transition
curve of our method, the middle column denotes the performance of DP-
PUSHFLOWCAP, and the right column illustrates the performance gap between the
two methods. For each privacy budget $\epsilon$, we highlight the optimal
$\eta$ corresponding to the best performance (yellow for our method, cyan for
DP-PUSHFLOWCAP). As demonstrated in the right column, when $\eta$ varies from
$1\times 10^{-10}$ to $1\times 10^{-4}$, our method consistently outperforms
DP-PUSHFLOWCAP up to $1\times 10^{-6}$. This indicates the superior stability
of hyperparameter selection for our method in terms of ranking performance.

Figure 8: Transition Curves of Thresholding Parameter $\eta$ Relative to
Privacy Budget $\epsilon$ for Three Benchmark Datasets.

###  D.4 Ablation Study

In this section, we conduct additional ablation studies to compare the noise
distributions, and noise schedules between our Theorem 1 and the Composition
Theorem. Following the experimental settings outlined in Sec. 4.2, we perform
experiments on the BlogCatalog dataset, utilizing PPR diffusion with a
parameter $\beta=0.8$ and a total of $K=100$ diffusion steps.

Noise Distributions: Laplace versus Gaussian. We investigate the effectiveness
of injecting Laplace noise as compared to Gaussian noise within our analysis
framework. Recall that standard PABI analysis has primarily focused on the
case of Gaussian noise. We report the ranking performance in Fig. 9 (Left).
Within a strong privacy regime where $\epsilon$ ranges from $0.1$ to $1$, the
performance gap between the two noise types is approximately 0.04. This
finding supports the superiority of Laplace noise injection for graph
diffusion processes in $\ell_{1}$ space and is of practical importance.

Figure 9: Left: Ranking performance with Laplace and Gaussian noise injection.
Right: Comparison of noise scales between our method (Theorem 1) and the
composition theorem under the DP metric.

Theorem 1 versus Composition Theorem. As we discussed in Section 3.2, one can
naively adopt the DP composition theorem [43, 44] to establish the privacy
guarantee for the same noisy graph diffusion. However, it is a general
approach and does not take the contraction properties of graph diffusion into
account, which leads to a worse privacy bound in our case. We examine the
calibrated noise scales $\sigma$ under edge-level DP, converted from RDP.
Figure 9 (Right) compares noise scales derived from our Theorem 1 (Red Line)
against those from the standard RDP composition theorem (Blue Line). Our
method achieves a noise scale that is 10 times smaller than that required by
the composition theorem.

##  Appendix E RDP to DP Conversion

First, we present the standard results on converting RDP to DP:

######  Proposition E.1 (Conversion from RDP to DP [44]).

If $\mathcal{M}$ is an $(\alpha,\epsilon_{\text{RDP}})$-RDP mechanism, then it
also satisfies $(\epsilon_{\text{DP}},\delta)$-differential privacy, where
$\epsilon_{\text{DP}}=\epsilon_{\text{RDP}}+\frac{\log\frac{1}{\delta}}{\alpha-1}$
for any $\delta\in(0,1)$.

To determine the DP guarantees of the three mechanisms, we first calculate the
RDP for each mechanism. Specifically, we use Theorem 4 for our method,
sensitivity analysis in Theorem 4.3 from [20] with the dimensional Laplace
mechanism under Rényi divergence (Eq. (58)) for DP-PUSHFLOWCAP, and
Proposition 5 from [44] for EdgeFlipping. For all three mechanisms, the
expression $\epsilon_{\text{RDP}}+\frac{\log\frac{1}{\delta}}{\alpha-1}$ is
convex in $\alpha$. By setting $\delta=\frac{1}{\\#\text{edges}}$, we then
search for the optimal $\alpha$ to minimize this expression and obtain
$\epsilon_{\text{DP}}$.

##  Appendix F Proof of Lemmas

###  F.1 Proof of Lemma B.1

From definition that $f,f^{\prime}$ are $1$-Lipschitz continuous, while for
$\phi_{k}$ and $\phi_{k}^{\prime}$, since
$\phi_{k}(\mathbf{x})=\left(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\right)\mathbf{x}+\gamma_{3,k}\mathbf{s},\phi_{k}^{\prime}(\mathbf{x})=\left(\gamma_{1,k}\mathbf{P}^{\prime}+\gamma_{2,k}\right)\mathbf{x}+\gamma_{3,k}\mathbf{s}$
where $\gamma_{k,1},\gamma_{k,2},\gamma_{k,3}$ are all nonnegative constants
such that $\sum_{j=1}^{3}\gamma_{k,j}=1$, we have

$\displaystyle\|\phi_{k}(\mathbf{x})-\phi_{k}(\mathbf{y})\|_{1}=\|\left(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\right)\mathbf{x}+\gamma_{3,k}\mathbf{s}-\left(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\right)\mathbf{y}-\gamma_{3,k}\mathbf{s}\|_{1}$
(33) $\displaystyle\leq$
$\displaystyle\|(\gamma_{1,k}\mathbf{P}+\gamma_{2,k})(\mathbf{x}-\mathbf{y})\|_{1}\leq\gamma_{1,k}\|\mathbf{P}(\mathbf{x}-\mathbf{y})\|_{1}+\gamma_{2,k}\|\mathbf{x}-\mathbf{y}\|_{1}$
(34) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle(\gamma_{1,k}+\gamma_{2,k})\cdot\|\mathbf{x}-\mathbf{y}\|_{1}$
(35)

where $(a)$ stems from the property that the random walk matrix $\mathbf{P}$
is a left stochastic matrix with each column summing to 1, thus constituting a
$1$-contraction mapping w.r.t $\|\cdot\|_{1}$. Similar derivation can be done
for $\phi_{k}^{\prime}$, and we conclude that $\phi_{k},\phi_{k}^{\prime}$ are
$(\gamma_{1,k}+\gamma_{2,k})$-contraction mappings.

Now, we will focus on distortion analysis: given any
$\mathbf{x}\in\mathbb{R}^{n}$, WLOG, we assume edge sets of two graphs
satisfies $\mathcal{E}=\mathcal{E}^{\prime}\cup\\{(1,2)\\}$, i.e. we drop edge
$(1,2)$ on graph $\mathcal{G}$ which lands in graph $\mathcal{G}^{\prime}$.

$\displaystyle\|\phi_{k}(f(\mathbf{x}))-\phi_{k}^{\prime}(f^{\prime}(\mathbf{x}))\|_{1}$
(36) $\displaystyle\leq$
$\displaystyle\|\phi_{k}(f(\mathbf{x}))-\phi_{k}^{\prime}(f(\mathbf{x}))\|_{1}+\|\phi_{k}^{\prime}(f(\mathbf{x}))-\phi_{k}^{\prime}(f^{\prime}(\mathbf{x}))\|_{1}$
(37) $\displaystyle=$
$\displaystyle\|(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\mathbf{I})f(\mathbf{x})-(\gamma_{1,k}\mathbf{P}^{\prime}+\gamma_{2,k}\mathbf{I})f(\mathbf{x})\|_{1}$
$\displaystyle+\|(\gamma_{1,k}\mathbf{P}^{\prime}+\gamma_{2,k}\mathbf{I})f(\mathbf{x})-(\gamma_{1,k}\mathbf{P}^{\prime}+\gamma_{2,k}\mathbf{I})f^{\prime}(\mathbf{x})\|_{1}$
(38) $\displaystyle\leq$
$\displaystyle\gamma_{1,k}\|(\mathbf{P}-\mathbf{P}^{\prime})f(\mathbf{x})\|_{1}+(\gamma_{1,k}+\gamma_{2,k})\cdot\|f(\mathbf{x})-f^{\prime}(\mathbf{x})\|_{1}$
(39) $\displaystyle=$
$\displaystyle\gamma_{1,k}\|(\mathbf{A}\mathbf{D}^{-1}-\mathbf{A}^{\prime}\mathbf{D}^{\prime-1})f(\mathbf{x})\|_{1}+(\gamma_{1,k}+\gamma_{2,k})\cdot\|f(\mathbf{x})-f^{\prime}(\mathbf{x})\|_{1}$
(40)

Further, we consider
$\mathbf{A}\mathbf{D}^{-1}-\mathbf{A}^{\prime}\mathbf{D}^{\prime-1}$, define
$n=|\mathcal{V}|$:

$\displaystyle\mathbf{A}\mathbf{D}^{-1}-\mathbf{A}^{\prime}\mathbf{D}^{\prime-1}=$
$\displaystyle\begin{bmatrix}0&\frac{1}{d_{2}}&\frac{a_{13}}{d_{3}}&\cdots&\frac{a_{1n}}{d_{n}}\\\
\frac{1}{d_{1}}&0&\frac{a_{23}}{d_{3}}&\cdots&\frac{a_{2n}}{d_{n}}\\\
\cdots&\cdots&\cdots&\cdots&\cdots\\\
\frac{a_{n1}}{d_{1}}&\frac{a_{n2}}{d_{2}}&\frac{a_{n3}}{d_{3}}&\cdots&\frac{a_{nn}}{d_{n}}\end{bmatrix}-\begin{bmatrix}0&0&\frac{a_{13}}{d_{3}}&\cdots&\frac{a_{1n}}{d_{n}}\\\
0&0&\frac{a_{23}}{d_{3}}&\cdots&\frac{a_{2n}}{d_{n}}\\\
\cdots&\cdots&\cdots&\cdots&\cdots\\\
\frac{a_{n1}}{d_{1}-1}&\frac{a_{n2}}{d_{2}-1}&\frac{a_{n3}}{d_{3}}&\cdots&\frac{a_{nn}}{d_{n}}\end{bmatrix}$
(41) $\displaystyle=$
$\displaystyle\begin{bmatrix}0&\frac{1}{d_{2}}&0&\cdots&0\\\
\frac{1}{d_{1}}&0&0&\cdots&0\\\ \cdots&\cdots&\cdots&\cdots&\cdots\\\
a_{n1}(\frac{1}{d_{1}}-\frac{1}{d_{1}-1})&a_{n2}(\frac{1}{d_{2}}-\frac{1}{d_{2}-1})&0&\cdots&0\end{bmatrix}$
(42)

Therefore, we have

$\displaystyle\|(\mathbf{A}\mathbf{D}^{-1}-\mathbf{A}^{\prime}\mathbf{D}^{\prime-1})f(\mathbf{x})\|_{1}$
(43) $\displaystyle=$
$\displaystyle\frac{|[f(\mathbf{x})]_{2}|}{d_{2}}+\frac{|[f(\mathbf{x})]_{1}|}{d_{1}}+\sum_{j\in\mathcal{N}(1)\backslash\\{2\\}}\frac{|[f(\mathbf{x})]_{1}|}{d_{1}(d_{1}-1)}+\sum_{l\in\mathcal{N}(2)\backslash\\{1\\}}\frac{|[f(\mathbf{x})]_{2}|}{d_{2}(d_{2}-1)}$
(44) $\displaystyle=$ $\displaystyle
2\left(\frac{|[f(\mathbf{x})]_{1}|}{d_{1}}+\frac{|[f(\mathbf{x})]_{2}|}{d_{2}}\right)\leq
4\max\left\\{\frac{|[f(\mathbf{x})]_{1}|}{d_{1}},\frac{|[f(\mathbf{x})]_{2}|}{d_{2}}\right\\}\leq
4\max_{\mathbf{x}\in\mathbb{R}^{n},i}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|$
(45)

where $\mathcal{N}(i)$ denote the neighbors of node $i$. Similarly, the above
derivation works for $\mathcal{E}\cup\\{(1,2)\\}=\mathcal{E}^{\prime}$ with
same bound by adding and subtracting
$(\gamma_{1,k}\mathbf{P}+\gamma_{2,k}\mathbf{I})f^{\prime}(\mathbf{x})$ in Eq.
(36). Since $(1,2)$ can be replaced by an arbitrary edge,
$\max_{\mathbf{x}\in\mathbb{R}^{n},i}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|$
upper bounds any edge-level adjacency graphs. Therefore, define
$\gamma_{\text{max}}=\max_{j\in\\{1,2\\},k\in[K]}|\gamma_{j,k}|,\gamma_{\text{max}}^{(1)}=\max_{k\in[K]}|\gamma_{1,k}|$,

$\displaystyle\|\phi_{k}(f(\mathbf{x}))-\phi_{k}^{\prime}(f^{\prime}(\mathbf{x}))\|_{1}\leq$
$\displaystyle
4\gamma_{1,k}\max_{\mathbf{x}\in\mathbb{R}^{n},i}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|+(\gamma_{1,k}+\gamma_{2,k})\Delta
f$ (46) $\displaystyle\leq$ $\displaystyle
4\gamma_{\text{max}}^{(1)}\cdot\max_{\mathbf{x}\in\mathbb{R}^{n}}\left|\frac{[f(\mathbf{x})]_{i}}{d_{i}}\right|+\gamma_{\text{max}}\cdot\Delta
f$ (47)

where $\Delta
f=\sup_{\mathbf{x}\in\mathbb{R}^{n}}\|f(\mathbf{x})-f^{\prime}(\mathbf{x})\|_{1}$
defines the sensitivity of graph-dependent thresholding function.

###  F.2 Proof of Lemma B.2

WLOG, we assume edge sets of two graphs satisfies
$\mathcal{E}=\mathcal{E}^{\prime}\cup\\{(1,2)\\}$. During no randomness phase,
we have

$\displaystyle\mathbf{s}_{l}=\phi_{l}(f(\mathbf{s}_{l-1})),\;\mathbf{s}_{l}^{\prime}=\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}^{\prime})),\;1\leq
l\leq m.$ (48)

Since two diffusion process start from the same seed $\mathbf{s}$, from Lemma
B.1, we have

$\displaystyle\|\mathbf{s}_{1}-\mathbf{s}_{1}^{\prime}\|_{1}=$
$\displaystyle\|\left(\gamma_{1,1}\mathbf{P}+\gamma_{2,1}\right)f(\mathbf{s})+\gamma_{3,1}\mathbf{s}-\left(\gamma_{1,1}\mathbf{P}^{\prime}+\gamma_{2,1}\right)f^{\prime}(\mathbf{s})-\gamma_{3,1}\mathbf{s}\|_{1}$
(49) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
4\gamma_{\text{max}}^{(1)}\cdot\left|\frac{[f(\mathbf{s})]_{i}}{d_{i}}\right|+\gamma_{\text{max}}\cdot\Delta
f\stackrel{{\scriptstyle(b)}}{{=}}(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$
(50)

where $(a)$ is derived from Lemma B.1 and $(b)$ is from the definition of $f$.
The bound is tight when the differed edge is attached to the nodes with lowest
degrees, which demonstrate that adding or removing an edge attached two low-
degree nodes will lead to significant privacy leakage.

For any step $l\geq 1$, we have

$\displaystyle\|\mathbf{s}_{l}-\mathbf{s}_{l}^{\prime}\|_{1}=\|\phi_{l}(f(\mathbf{s}_{l-1}))-\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}^{\prime}))\|_{1}$
(51) $\displaystyle\leq$
$\displaystyle\|\phi_{l}(f(\mathbf{s}_{l-1}))-\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}))\|_{1}+\|\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}))-\phi_{l}^{\prime}(f^{\prime}(\mathbf{s}_{l-1}^{\prime}))\|_{1}$
(52) $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta+\gamma_{\text{max}}\|\mathbf{s}_{l}-\mathbf{s}_{l}^{\prime}\|_{1}$
(53)

where $(a)$ arises from Lemma B.1 and the Lipschitzness of $\phi_{l}\circ f$.
Define
$\rho_{\text{diff}}=(4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}})\eta$,
thus, by induction, we conclude that

$\displaystyle\|\mathbf{s}_{m}-\mathbf{s}_{m}^{\prime}\|_{1}\leq$
$\displaystyle\gamma_{\text{max}}\cdot\|\mathbf{s}_{m-1}-\mathbf{s}_{m-1}^{\prime}\|_{1}+\rho_{\text{diff}}$
(54) $\displaystyle\leq$
$\displaystyle\gamma_{\text{max}}^{2}\cdot\|\mathbf{s}_{m-2}-\mathbf{s}_{m-2}^{\prime}\|_{1}+\rho_{\text{diff}}(1+\gamma_{\text{max}})$
(55) $\displaystyle\leq$
$\displaystyle\cdots\leq\gamma_{\text{max}}^{m-1}\cdot\|\mathbf{s}_{1}-\mathbf{s}_{1}^{\prime}\|_{1}+\rho_{\text{diff}}(1+\gamma_{\text{max}}+\cdots+\gamma_{\text{max}}^{m-2})$
(56) $\displaystyle\leq$
$\displaystyle\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$
(57)

###  F.3 Proof of Lemma B.3

To prove this lemma, we introduce result on the Rényi divergence for high-
dimensional Laplacian distributions with shift. The details of this result and
its proof are presented following the lemma.

Result: Given a shift $\mathbf{h}\in\mathbb{R}^{|\mathcal{V}|}$, for two
Laplacian distributions $\mathcal{L}(\bm{0},\sigma)$ and
$\mathcal{L}(\mathbf{h},\sigma)$, if $\|\mathbf{h}\|_{1}\leq\rho$,

$\displaystyle\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))\leq\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma}\rho))$
(58)

Lemma Proof. With the above result, we can upper bound the Rényi divergence
over joint noise distributions. We consider two cases for the chosen parameter
$\tau$:

(1) When $\tau>m$,

$\displaystyle\mathcal{D}_{\alpha}(\xi_{{\tau+1}:K}^{(2)}\|\tilde{\xi}_{{\tau+1}:K}^{\prime(2)})\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\sum_{k=\tau+1}^{K}\sup_{\zeta_{\tau+1:k-1}}\mathcal{D}_{\alpha}(\xi_{k}^{(2)}|\xi_{\tau+1:k-1}^{(2)}=\zeta_{\tau+1:k-1}\|\tilde{\xi}_{k}^{\prime(2)}|\tilde{\xi}_{\tau+1:k-1}^{\prime(2)}=\zeta_{\tau+1:k-1})$
(59) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\sum_{k=\tau+1}^{K}\mathcal{D}_{\alpha}(\mathcal{L}(\mathbf{0},\sigma_{k})\|\mathcal{L}(\mathbf{h}_{k},\sigma_{k}))\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{k=\tau+1}^{K}g_{\alpha}(\sigma_{k},\rho_{\text{diff}})$
(60)

where $(a)$ arises from strong composition rule for Rényi divergence (Lemma
A.4), $(b)$ is from the definition of $\xi_{k}^{(2)},\tilde{\xi}_{k}^{(2)}$
with shift $\mathbf{h}_{k}=(\phi_{k}\circ
f)(\mathbf{x})-(\phi_{k}^{\prime}\circ f^{\prime})(\mathbf{x})$, and $(c)$ is
derived by combining the results that the $\ell_{1}$ norm of the shift is
upper bounded by
$\|\mathbf{h}_{k}\|_{1}\leq\rho_{\text{diff}}=4\gamma_{\text{max}}^{(1)}+2\gamma_{\text{max}}$
(Lemma B.1) and the above Laplace bound under Rényi divergence (Eq. (58)) with
$g_{\alpha}(\sigma,\rho)=\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma}\rho_{\text{diff}}))$.

(2) When $\tau=m$, the shift between noise terms $\xi_{m+1}^{(2)}$ and
$\tilde{\xi}_{m+1}^{\prime(2)}$ differs from $\rho_{\text{diff}}$. Instead, it
should account for the shift of the entire noise-free diffusion and the
distortion incurred at step $m+1$. Specifically, define
$\lambda_{m+1}=\frac{(1-\gamma_{\text{max}}^{m+1})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$
(Lemma B.2, and the distortion at step $m+1$). Therefore, following the above
analysis, we have

$\displaystyle\mathcal{D}_{\alpha}(\xi_{m+1:K}^{(2)}\|\tilde{\xi}_{m+1:K}^{(2)}])\leq$
$\displaystyle\sum_{k=m+1}^{K}\sup_{\zeta_{m+1:k-1}}\mathcal{D}_{\alpha}(\xi_{k}^{(2)}|\xi_{m+1:k-1}^{(2)}=\zeta_{m+1:k-1}\|\tilde{\xi}_{k}^{\prime(2)}|\tilde{\xi}_{m+1:k-1}^{\prime(2)}=\zeta_{m+1:k-1})$
(61) $\displaystyle\leq$ $\displaystyle
g_{\alpha}(\sigma_{m+1},\lambda_{m+1})+\sum_{k=m+2}^{K}g_{\alpha}(\sigma_{k},\rho_{\text{diff}})$
(62)

Summarizing the above, we prove the lemma.

Proof of Result. Now consider Laplacian distribution, for
$\mathbf{h}\in\mathbb{R}^{|\mathcal{V}|}$,

$\displaystyle\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))\stackrel{{\scriptstyle(a)}}{{=}}\sum_{i=1}^{|\mathcal{V}|}\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}|\mathbf{h}_{i}|)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma})|\mathbf{h}_{i}|)$
(63)

where $(a)$ is from the additivity of Rényi divergence [58] and the Rényi
divergence over one-dimensional Laplacian noise [59]. By considering the worst
case $\mathbf{h}$, we can reformulate the problem as:

$\displaystyle\mathop{\text{maximize}}\limits_{h}\sum_{i=1}^{|\mathcal{V}|}\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}|\mathbf{h}_{i}|)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma})|\mathbf{h}_{i}|)$
(64) $\displaystyle\text{s.t. }\|\mathbf{h}\|_{1}\leq\rho$ (65)

For the above optimization problem, let
$\mathbf{x}_{i}=\|\mathbf{h}_{i}\|_{1},\lambda_{1}=\frac{\alpha}{2\alpha-1},\lambda_{2}=\frac{\alpha-1}{\sigma},\lambda_{3}=\frac{\alpha-1}{2\alpha-1}$
and $\lambda_{4}=\frac{\alpha}{\sigma}$. Define
$f(\mathbf{x}_{i})=\frac{1}{\alpha-1}\ln(\lambda_{1}\exp(\lambda_{2}\mathbf{x}_{i})+\lambda_{3}\exp(-\lambda_{4}\mathbf{x}_{i})$.
Consider the gradient term
$\nabla\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))$:

$\displaystyle\frac{\partial\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))}{\partial\mathbf{x}_{i}}=\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{x}_{i}}=\frac{\lambda_{1}\lambda_{2}\exp(\lambda_{2}\mathbf{x}_{i})-\lambda_{3}\lambda_{4}\exp(-\lambda_{4}\mathbf{x}_{i})}{\lambda_{1}\exp(\lambda_{2}\mathbf{x}_{i})+\lambda_{3}\exp(-\lambda_{4}\mathbf{x}_{i})}$
(66)

Further for Hessian matrix
$\nabla^{2}\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))$,

$\displaystyle\frac{\partial^{2}\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))}{\partial\mathbf{x}_{i}^{2}}=\frac{\lambda_{1}\lambda_{3}(\lambda_{2}+\lambda_{4})^{2}\exp(\lambda_{2}\mathbf{x}_{i})\exp(-\lambda_{4}\mathbf{x}_{i})}{\lambda_{1}\exp(\lambda_{2}\mathbf{x}_{i})+\lambda_{3}\exp(-\lambda_{4}\mathbf{x}_{i})}>0,$
(67)
$\displaystyle\frac{\partial^{2}\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))}{\partial\mathbf{x}_{i}\mathbf{x}_{j}}=0,i\neq
j.$ (68)

From the eigenvalue criterion for positive definiteness,
$\nabla^{2}\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))\succ
0$, i.e.
$\mathcal{D}_{\alpha}(\mathcal{L}(\bm{0},\sigma)\|\mathcal{L}(\mathbf{h},\sigma))$
is a convex function. As the feasible set is convex, maximum is obtained on
the boundary of feasible set. Thus, the problem can be further formulated as:

$\displaystyle\mathop{\text{maximize}}\limits_{h}\sum_{i=1}^{|\mathcal{V}|}\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}|\mathbf{h}_{i}|)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma})|\mathbf{h}_{i}|)\;\text{s.t.
}\|\mathbf{h}\|_{1}=\rho$ (69)

Next, we use the adjustment method to solve the above objective methods.
First, we define
$L(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{|\mathcal{V}|})=\sum_{i=1}^{|\mathcal{V}|}f(\mathbf{x}_{i})$
and we fix $\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|}$. We aim to
optimize:

$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{1},\mathbf{x}_{2}}L(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})$
(70)

with respect to $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$, considering the
constraints $\|\mathbf{h}\|_{1}=\rho$. This is equivalent to

$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{1},\mathbf{x}_{2}}\sum_{i=1}^{2}L(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{|\mathcal{V}|}),\;\text{s.t.
}\mathbf{x}_{1}+\mathbf{x}_{2}=\rho-\sum_{i=3}^{|\mathcal{V}|}\mathbf{x}_{i}.$
(71)

Define $\mathbf{c}_{t}=\rho-\sum_{i=t}^{\mathcal{V}}\mathbf{x}_{i}$. Since
$\mathbf{c}_{3}$ is fixed, and $\mathbf{x}_{2}=\mathbf{c}_{3}-\mathbf{x}_{1}$,
the objective function become a univariate function, by calculating the
derivative

$\displaystyle\frac{\partial
L}{\partial\mathbf{x}_{1}}=\frac{(\lambda_{1}\lambda_{3}\lambda_{4}+\lambda_{1}\lambda_{2}\lambda_{3})(\exp(\lambda_{2}\mathbf{x}_{1}+\lambda_{4}(\mathbf{x}_{1}-\mathbf{c}_{3}))-\exp(\lambda_{2}(\mathbf{c}_{3}-\mathbf{x}_{1})-\lambda_{4}\mathbf{x}_{1}))}{(\lambda_{1}\exp(\lambda_{2}\mathbf{x}_{1}+\lambda_{3}\exp(-\lambda_{4}\mathbf{x}_{1})))(\lambda_{1}\exp(\lambda_{2}(\mathbf{c}_{3}-\mathbf{x}_{1}))+\lambda_{3}\exp(-\lambda_{4}(\mathbf{c}_{3}-\mathbf{x}_{1})))}$
(72)

The derivative $\frac{\partial L}{\partial\mathbf{x}_{1}}$ reaches 0 when
$\mathbf{x}_{1}=\frac{\mathbf{c}_{3}}{2}$. Furthermore, $\frac{\partial
L}{\partial\mathbf{x}_{1}}<0$ for $\mathbf{x}_{1}<\frac{\mathbf{c}_{3}}{2}$,
and $\frac{\partial L}{\partial\mathbf{x}_{1}}>0$ for
$\mathbf{x}_{1}>\frac{\mathbf{c}_{3}}{2}$. Thus, the maximum value of the
function is attained at the endpoints.

$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{1},\mathbf{x}_{2}}L(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})\leq\max\left[L(\mathbf{c}_{3},0,\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|}),L(0,\mathbf{c}_{3},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})\right]$
(73)

As the function is symmetric, two endpoints attain the same value, i.e.
$L(\mathbf{c}_{3},0,\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})=L(0,\mathbf{c}_{3},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})$.
Now, we aim to maximize the objective function by each time adjustment two
variables and fixed the rest variables unchanged:

$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{|\mathcal{V}|}}L(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})=\mathop{\text{maximize}}\limits_{\begin{subarray}{c}\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},...,\mathbf{x}_{|\mathcal{V}|}\\\
\mathbf{x}_{1}+\mathbf{x}_{2}+\mathbf{c}_{3}=\rho\end{subarray}}L(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})$
(74) $\displaystyle\leq$
$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{3},...,\mathbf{x}_{|\mathcal{V}|}}\mathop{\text{maximize}}\limits_{\begin{subarray}{c}\mathbf{x}_{1},\mathbf{x}_{2}\\\
\mathbf{x}_{1}+\mathbf{x}_{2}=\rho-\mathbf{c}_{3}\end{subarray}}L(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})$
(75) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\mathop{\text{maximize}}\limits_{\mathbf{x}_{3},\mathbf{x}_{4},...,\mathbf{x}_{|\mathcal{V}|}}L(\rho-\mathbf{c}_{3},0,\mathbf{x}_{3},\ldots,\mathbf{x}_{|\mathcal{V}|})\leq\mathop{\text{maximize}}\limits_{\mathbf{x}_{4},...,\mathbf{x}_{|\mathcal{V}|}}L(\rho-\mathbf{c}_{4},0,0,\ldots,\mathbf{x}_{|\mathcal{V}|})$
(76) $\displaystyle\leq$ $\displaystyle\cdots\leq
L(\rho,0,0,...,0)=\frac{1}{\alpha-1}\ln(\frac{\alpha}{2\alpha-1}\exp(\frac{\alpha-1}{\sigma}\rho)+\frac{\alpha-1}{2\alpha-1}\exp(-\frac{\alpha}{\sigma})\rho)$
(77)

where $(a)$ is from Eq. (73), and for each inequality, we adjust the values of
$\mathbf{x}_{1}$ and $\mathbf{x}_{i}$ to maximized the objective function
while keep the rest variables fixed. From the above reasoning, we maximized
the Rényi divergence over two Laplacians with shift.

###  F.4 Proof of Lemma B.4.

To prove the upper bound of
$\sup_{\zeta_{\tau+1:K}}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})$,
we mainly leverage the definition of shifted Rényi divergence (Def. A.1) with
two properties under noise convolution and contraction mapping (Lemma A.1 and
Lemma A.2). Specifically, recall that
$\mathcal{R}_{\alpha}(\sigma,\rho)=\sup_{\mathbf{r}:\|\mathbf{r}\|\leq\rho}\mathcal{D}_{\alpha}(\xi+\mathbf{r}\|\xi)$
where $\xi\sim\mathcal{L}(\mathbf{0},\sigma)$, define
$\varphi_{k}=\phi_{k}\circ f$, for any $\zeta_{\tau+1:K}$, define $w_{K}=0$,

$\displaystyle\phantom{\stackrel{{\scriptstyle(a)}}{{\leq}}}\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})$
(78)
$\displaystyle=\mathcal{D}_{\alpha}^{(w_{K})}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})$
(79)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathcal{D}_{\alpha}^{(w_{K}+\mathbf{a}_{K})}(\varphi_{K}(\mathbf{s}_{K-1})|\xi_{\tau+1:K-1}^{(2)}=\zeta_{\tau+1:K-1}\|\varphi_{K}(\mathbf{s}_{K}^{\prime})|\tilde{\xi}_{\tau+1:K-1}^{\prime(2)}=\zeta_{\tau+1:K-1})+\mathcal{R}_{\alpha}(\sigma_{K},\mathbf{a}_{K})$
(80)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathcal{D}_{\alpha}^{(\frac{w_{K}+\mathbf{a}_{K}}{\gamma_{\text{max}}})}(\mathbf{s}_{K-1}|\xi_{\tau+1:K-1}^{(2)}=\zeta_{\tau+1:K-1}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K-1}^{\prime(2)}=\zeta_{\tau+1:K-1})+\mathcal{R}_{\alpha}(\sigma_{K},\mathbf{a}_{K})$
(81)
$\displaystyle\xlongequal{w_{K-1}=\frac{w_{K}+\mathbf{a}_{K}}{\gamma_{\text{max}}}}\mathcal{D}_{\alpha}^{(w_{K-1})}(\mathbf{s}_{K-1}|\xi_{\tau+1:K-1}^{(2)}=\zeta_{\tau+1:K-1}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K-1}^{\prime(2)}=\zeta_{\tau+1:K-1})+\mathcal{R}_{\alpha}(\sigma_{K},\mathbf{a}_{K})$
(82) $\displaystyle\leq\cdots$ (83)
$\displaystyle\leq\mathcal{D}_{\alpha}^{(w_{\tau+1})}(\mathbf{s}_{\tau+1}|\xi_{\tau+1}^{(2)}=\zeta_{{\tau+1}}\|\mathbf{s}_{{\tau+1}}^{\prime}|\tilde{\xi}_{{\tau+1}}^{\prime(2)}=\zeta_{{\tau+1}})+\sum_{k={\tau+2}}^{K}\mathcal{R}_{\alpha}(\sigma_{k},\mathbf{a}_{k})$
(84)
$\displaystyle\leq\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})+\sum_{k=\tau+1}^{K}\mathcal{R}_{\alpha}(\sigma_{k},\mathbf{a}_{k})$
(85)

where $(a)$ is from Lemma A.1, and $(b)$ is derived from Lemma A.2 as
$\varphi_{k}$ is $\gamma_{\text{max}}$-contractive (composition of two
contractions). Further, we have

$\displaystyle\left\\{\begin{aligned}
&w_{\tau+1}=\gamma_{\text{max}}w_{\tau}-\mathbf{a}_{\tau+1}\\\
&w_{\tau+2}=\gamma_{\text{max}}w_{\tau+1}-\mathbf{a}_{\tau+2}=\gamma_{\text{max}}^{2}w_{\tau}-\gamma_{\text{max}}\mathbf{a}_{\tau+1}-\mathbf{a}_{\tau+2}\\\
&\cdots=\cdots\\\
&w_{K}=\gamma_{\text{max}}^{K-\tau}w_{\tau}-\sum_{k=0}^{K-\tau-1}\gamma_{\text{max}}^{k}\mathbf{a}_{K-k}\end{aligned}\right.$
(86)

By setting $\mathbf{a}_{\tau+1}=0,...,\mathbf{a}_{K-1}=0$, we have
$\mathbf{a}_{K}=\gamma_{\text{max}}^{K-\tau}w_{\tau}$. Therefore, we have

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})\leq\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})+\mathcal{R}_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})$
(87)

From the result in the proof of Lemma B.3,
$\mathcal{R}_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})=g_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})$.
Summarizing the above, we obtain

$\displaystyle\mathcal{D}_{\alpha}(\mathbf{s}_{K}|\xi_{\tau+1:K}^{(2)}=\zeta_{\tau+1:K}\|\mathbf{s}_{K}^{\prime}|\tilde{\xi}_{\tau+1:K}^{\prime(2)}=\zeta_{\tau+1:K})\leq\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})+g_{\alpha}(\sigma_{K},\gamma_{\text{max}}^{K-\tau}w_{\tau})$
(88)

###  F.5 Proof of Lemma B.5.

To prove this lemma, we consider tracking the $\infty$-Wasserstein distance of
the coupled iterates. Given $\mathscr{D}_{K,\Pi}$ and
$\mathscr{D}_{K,\Pi}^{\prime}$,

(1) When $\tau=m$: no randomness is injected for $k$ from $1$ to $\tau$, and
from Lemma B.2, we have

$\displaystyle\|\mathbf{s}_{\tau}-\mathbf{s}_{\tau}^{\prime}\|_{1}\leq\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$
(89)

Let $\delta_{\mathbf{s}_{\tau}}$ and $\delta_{\mathbf{s}_{\tau}^{\prime}}$
denote the Dirac measure for two processes at step $\tau$, and therefor,

$\displaystyle
W_{\infty}(\delta_{\mathbf{s}_{\tau}},\delta_{\mathbf{s}_{\tau}^{\prime}})\leq\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}$
(90)

(2) When $\tau\geq m+1$: recall that for any $k(k\geq m+1)$,

$\displaystyle\mathscr{D}_{K,\Pi}(\mathbf{s}):\mathbf{s}_{k}=\phi_{k}(f(\mathbf{s}_{k-1}))+\xi_{k}^{(1)}+\xi_{k}^{(2)},\;\mathscr{D}_{K,\Pi}^{\prime}(\mathbf{s}):\mathbf{s}_{k}^{\prime}=\phi_{k}^{\prime}(f^{\prime}(\mathbf{s}_{k-1}^{\prime}))+\xi_{k}^{\prime(1)}+\tilde{\xi}_{k}^{\prime(2)}.$
(91)

For any step $k(k\geq m+1)$, let $\mu_{k}$ and $\nu_{k}$ denote the
distribution of $\mathbf{s}_{k}$ and $\mathbf{s}_{k}^{\prime}$ respectively.
Further, define $\tilde{\mu}_{k}$ and $\tilde{\nu}_{k}$ denote the
distribution of $\mathbf{S}_{k}=(\xi_{m+1:k},\tilde{\xi}_{m+1:k})$ and
$\mathbf{S}_{k}^{\prime}=(\xi_{m+1:k}^{\prime},\tilde{\xi}_{m+1:k}^{\prime})$,
respectively. For step $m+1$, we have

$\displaystyle
W_{\infty}(\mu_{m+1},\nu_{m+1})=\inf_{\pi_{m+1}\in\Gamma(\mu_{m+1},\nu_{m+1})}\mathop{\mathrm{ess\,sup}}_{(\mathbf{s}_{m+1},\mathbf{s}_{m+1}^{\prime})\sim\pi_{m+1}}\|\mathbf{s}_{m+1}-\mathbf{s}_{m+1}^{\prime}\|_{1}$
(92) $\displaystyle=$
$\displaystyle\inf_{\tilde{\pi}_{m+1}\in\Gamma(\tilde{\mu}_{m+1},\tilde{\nu}_{m+1})}\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{m+1},\mathbf{S}_{m+1}^{\prime})\sim\tilde{\pi}_{m+1}}\|\phi_{m+1}(f(\mathbf{s}_{m}))+\xi_{m+1}^{(1)}+\xi_{m+1}^{(2)}-\phi_{m+1}^{\prime}(f^{\prime}(\mathbf{s}_{m}^{\prime}))-\xi_{m+1}^{\prime(1)}-\xi_{m+1}^{\prime(2)}\|_{1}$
(93) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{m+1},\mathbf{S}_{m+1}^{\prime})\sim\tilde{\pi}_{m+1}^{*}}\|\phi_{m+1}(f(\mathbf{s}_{m}))-\phi_{m+1}^{\prime}(f^{\prime}(\mathbf{s}_{m}^{\prime}))\|_{1}\stackrel{{\scriptstyle(b)}}{{\leq}}\gamma_{\text{max}}\|\mathbf{s}_{m}-\mathbf{s}_{m}^{\prime}\|_{1}+\rho_{\text{diff}}$
(94) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\frac{(1-\gamma_{\text{max}}^{m})\rho_{\text{diff}}}{(1-\gamma_{\text{max}})}+\rho_{\text{diff}}=\frac{(1-\gamma_{\text{max}}^{m+1})\rho_{\text{diff}}}{1-\gamma_{\text{max}}}:=\lambda_{m+1}$
(95)

where $(a)$ is from selecting a coupling $\tilde{\pi}^{*}$ such that r.v.s
$\mathbf{S}_{m+1}$ and $\mathbf{S}_{m+1}^{\prime}$ are identical, $(b)$ is
derived from Eq. (53) and $(c)$ is obtained from Lemma B.2.

Next, for any $\tau$, following the above procedure, define
$\tilde{\pi}_{k}^{*}\in\Gamma(\mu_{k},\nu_{k})$ such that
$\mathbf{S}_{k},\mathbf{S}_{k}^{\prime}$ are identical, we have

$\displaystyle
W_{\infty}(\mu_{\tau},\nu_{\tau})=\inf_{\pi_{\tau}\in\Gamma(\mu_{\tau},\nu_{\tau})}\mathop{\mathrm{ess\,sup}}_{(\mathbf{s}_{\tau},\mathbf{s}_{\tau}^{\prime})\sim\pi_{\tau}}\|\mathbf{s}_{\tau}-\mathbf{s}_{\tau}^{\prime}\|_{1}$
(96) $\displaystyle\leq$
$\displaystyle\inf_{\tilde{\pi}_{\tau}\in\Gamma(\tilde{\mu}_{\tau},\tilde{\nu}_{\tau})}\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau},\mathbf{S}_{\tau}^{\prime})\sim\tilde{\pi}_{\tau}}\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}))+\xi_{\tau}^{(1)}+\xi_{\tau}^{(2)}-\phi_{\tau}^{\prime}(f_{\tau}^{\prime}(\mathbf{s}_{\tau-1}^{\prime}))-\xi_{\tau}^{\prime(1)}-\xi_{\tau}^{\prime(2)}\|_{1}$
(97) $\displaystyle\leq$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau},\mathbf{S}_{\tau}^{\prime})\sim\tilde{\pi}_{\tau}^{*}}\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}))+\xi_{\tau}^{(1)}+\xi_{\tau}^{(2)}-\phi_{\tau}^{\prime}(f_{\tau}^{\prime}(\mathbf{s}_{\tau-1}^{\prime}))-\xi_{\tau}^{\prime(1)}-\xi_{\tau}^{\prime(2)}\|_{1}$
(98) $\displaystyle=$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau-1},\mathbf{S}_{\tau-1}^{\prime})\sim\tilde{\pi}_{\tau-1}^{*}}\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}))-\phi_{\tau}^{\prime}(f_{\tau}^{\prime}(\mathbf{s}_{\tau-1}^{\prime}))\|_{1}$
(99)

Following the analysis in Lemma B.1, by induction,

$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau-1},\mathbf{S}_{\tau-1}^{\prime})\sim\tilde{\pi}_{\tau-1}^{*}}\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}))-\phi_{\tau}^{\prime}(f_{\tau}^{\prime}(\mathbf{s}_{\tau-1}^{\prime}))\|_{1}$
(100) $\displaystyle\leq$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau-1},\mathbf{S}_{\tau-1}^{\prime})\sim\tilde{\pi}_{\tau-1}^{*}}\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}))-\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}^{\prime}))\|_{1}+\|\phi_{\tau}(f_{\tau}(\mathbf{s}_{\tau-1}^{\prime}))-\phi_{\tau}^{\prime}(f_{\tau}^{\prime}(\mathbf{s}_{\tau-1}^{\prime}))\|_{1}$
(101) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{\tau-1},\mathbf{S}_{\tau-1}^{\prime})\sim\tilde{\pi}_{\tau-1}^{*}}\gamma_{\text{max}}\cdot\|\mathbf{s}_{\tau-1}-\mathbf{s}_{\tau-1}^{\prime}\|_{1}+\rho_{\text{diff}}$
(102) $\displaystyle\leq$ $\displaystyle\cdots$ (103)
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\mathop{\mathrm{ess\,sup}}_{(\mathbf{S}_{m+1},\mathbf{S}_{m+1}^{\prime})\sim\tilde{\pi}_{m+1}^{*}}\gamma_{\text{max}}^{\tau-(m+1)}\cdot\|\mathbf{s}_{m+1}-\mathbf{s}_{m+1}^{\prime}\|_{1}+\rho_{\text{diff}}\left(1+\gamma_{\text{max}}+\cdots+\gamma_{\text{max}}^{\tau-m-2}\right)$
(104) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\gamma_{\text{max}}^{\tau-(m+1)}\cdot\frac{(1-\gamma_{\text{max}}^{m+1})\cdot\rho_{\text{diff}}}{1-\gamma_{\text{max}}}+\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau-(m+1)})}{1-\gamma_{\text{max}}}$
(105) $\displaystyle=$
$\displaystyle\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})}{1-\gamma_{\text{max}}}$
(106)

where $(a)$ is from Lemma B.1, $(b)$ is from induction, and $(c)$ arises from
Eq. (95).

Therefore,

$\displaystyle
W_{\infty}(\mu_{\tau},\nu_{\tau})\leq\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})}{1-\gamma_{\text{max}}}$
(107)

Further, when we set
$w_{\tau}=\frac{\rho_{\text{diff}}\cdot(1-\gamma_{\text{max}}^{\tau})}{1-\gamma_{\text{max}}}$,
we have

$\displaystyle\mathcal{D}_{\alpha}^{(w_{\tau})}(\mathbf{s}_{\tau}\|\mathbf{s}_{\tau}^{\prime})=\inf_{\mu_{\tau}^{\prime}:W_{\infty}(\mu_{\tau},\mu_{\tau}^{\prime})\leq
w_{\tau}}\mathcal{D}_{\alpha}(\mu_{\tau}^{\prime}\|\nu_{\tau})=0$ (108)

where the equality is achieved by selecting $\mu_{\tau}^{\prime}=\nu_{\tau}$.