Differentially Private Graph Diffusion with Applications in Personalized PageRanks
Authors: Rongzhe Wei
Eli Chien
Pan Li
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
graph diffusion
personalize pagerank
Primary area: other

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 different privacy guarantees by using noisy diffusion iterates.
    The algorithm injects Laplace noise per diffusion iteration and adopts a degree-based thresholding function to mitigate the high sensitivity induced by low-degree nodes. Our privacy loss analysis is based on Privacy Amplification by Iteration (PABI), which to our best knowledge, is the first effort that analyzes PABI with Laplace noise and provides relevant applications.
    We also introduce a novel $\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.

Differentially Private Graph Diffusion with Applications in Personalized PageRanks
Rongzhe Wei
Eli Chien
Georgia Institute of Technology rongzhe.. wei@gatech.... edu
Georgia Institute of Technology
ichien6ggatech.. edu
Pan
Georgia Institute of Technology
panliggatech. edu
Abstract
Graph diffusion, which iteratively propagates real-valued substances among the graph, used in numerous graph/network-involee applications. However, leasing diffusion vectors may reveal sensitive linking information in the data such transaction information in financial network data. Protecting the privacy of graph data is challenging due to its interconnected nature. This work proposes a novel graph diffuusin framework with edge-level differential privacy guarantees by using noisy diffusion iterates. The algorithm injects Laplace noise per diffusion iteration and adopts degree-based thresholding function 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, the first effort that analyzes PABI with Laplace noise and provides relevant applications. We also introduce a novel co- Wasserstein distance tracking method, which tightens the analysis of privacy leakage and makes PABI practically applicable. 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 PageRank (1) and heat kernel diffusion [2] has revolutionized the domains such as web searching [3], community detection [47]. network analysis [8] 9 and advancements in graph neural networks [10-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 small subset of random walk-based similarities (e.g., commute times, personalized PageRank scores) could disclose significant portions of network's edges, phenomenon known link disclosure [13]. Such attacks, for instance, may enable advertisers to deploy invasive advertising tactics (16) or reveal sensitive transaction information within financial networks (17). Consequently, becomes critically important
to design graph diffusion algorithms with privacy safeguards.
Differential privacy (DP) is recognized
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) 220), and other relevant graph
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

algorithms such as max flow-min cut (2T), graph sparsification (22), spectral analysis [23 24 However, output perturbation-bast based approaches often provide a less-thannides uuivity-prvaacy tradeoff. Numerous studies suggest that incorporating noise during the process, rather than at the output, can potentially enhance utility-privacy tradeoft's [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 incorporate privacy amplification by iterations (PABI) technique [26] into graph diffusions. As graph diffusion can be viewed as iterating contraction maps in & space, we adopt per-iterate Laplace noise due its better performance than the Gaussian mechanism commonly adopted in previous PABI frameworks and provide new analysis dedicated to Laplace noise. We also propose novel oo- Wasserstein distance tracking analysis that can tighten the state-of-the-an 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-prive pulityy-pivaacy 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] The primary techniques to safeguard graph structures involve the Laplace and exponential mechanisms [3). 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 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 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 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 tightened space diameter tracking, which makes the bound practically applicable in the graph diffusion applications. Besides, works that share a similar spirit in leveraging PABI have been conducted for other scenarios including machine unlearning 45 and improving hidden state DP (46).
2 Preliminaries
Let 9 = EV,E) represent an undirected graph, where V is the set of nodes and E is the set of edges, equipped with an adjacency matrix A E {0, 1]mX", where denotes the total number of nodes, i.c. n = [ By establishing an order for the nodes within the graph, we denote d = [d1, d2.... d.l" as the degree vector. Additionally, let D diag( d) and e; signifies the i-th standard basis. We denote [(,, .r) and A0 o I')) as the zero mean Laplace and Gaussian distributions, respectively. We define the set [n] (1, 2, .., n), and X i, j E 24, i < j as joint couple of XX,,X,+,,....
Graph Diffusion. First, we introduce the concept of Graph Diffusion 2, which is commonly characterized by a series of diffusion map Ob defined by the random walk matrix P = AD-1 6 12
2

---

47
Formally, We define the graph diffusion (s) with the initial seed s as
(s) lim sx lim ΦR o .... (s), where Φ& (x) ( + 72,k ) x Y3,4S. K-00
(1)
K-00
where E IR VI is stochastic vector the graph, and 71.k 72,4 + 73,6 1. Let 7max
max; |i,a + 172.al denote the Lipschitz constant of the graph diffusion mapping, and (01) max; mi.i denote the maximum diffusion coefficient. Sy is the diffusion vector time K. The essence of a diffusion process is to model how an initial vector s propagates through the graph over time. Coefficient %, 8 control how different resources contribute to the kth step diffusion. When taking /1.A = Ya.k = / and * O, Eq. I is recognized as the PageRank Diffusion [48] with teleport probability 1 3. 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 44
Personalization. Personalized graph diffusions, tailored to individual nodes or localized neigh- borhoods, play crucial role in many real-world applications. These include recommendation systems [50]. where personalized diffusions improve suggestion relevance, community detection for identifying subgroups within larger networks [7],, targeted marketing strategies for enhancing campaign effectiveness [5T]. These diffusions are defined by setting the graph diffusion vector s as e, for an individual node or Dies e for neighborhood set S. In this paper, we primarily discuss the single-node case while our analysis can be generalized to set of seed nodes.
Privacy Definition. Differential Privacy (DP) 18 42 is widely recognized as the standard framework for providing formal privacy guarantees for al 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 (Edge-level RDP (52 (3).. . A randomized graph algorithm A is (a, e)-edge-level RDP for any adjacent graphs G, G that differs in single edge, we have DD, A(())) S where
the Rényi Divergence D. (X --r log BEZa
[4(2)) with X X,,YY
More practical cases find that the seed node (user) of personalized graph diffusion algorithms is already aware 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 54). Consider a graph G and personalized graph algorithm A. The algorithm A satisfies personalized (a, e)-ddge-level RDP for any node v as the seed node in G. and for any graph G' adjacent to G differing by one edge not incident e, we have
Da(A(G v) A(G' v)) S
3 Methodology
This study centers category of 7ima <1 Lipschitz continuous graph diffusions, encompassing prevalent techniques such as PageRank (1) and PPR (55). is noted that each diffusion map Φa within graph diffusion maintains the total mass of the diffusion vector Sk, owing to the condition Eie Ye. = 1 and the property of the random walk matrix P being a left stochastic matrix. This observation entails that the diffusion map OR in Eq. I constitutes strictly contraction map in the metric space (TR|V), || []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 diffusson steps can provide improved utility-privacy trade-off's compared to output perturbation alone (25). This insight serves as a key motivation for employing PABI to establish mrivacy-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
3

---

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 (X, || 11) with an initial random state Xo E X, a series of contractions (i.e., c- -unntioiitfuunciinnn,, e S 1) Uh : X + &, and a sequence of noise random variables {Ex Defining B as a convex bounded set, the Contractive Noisy Iteration (X,, { {5x), B3) is governed by the update rule:
Xk+1 Pilli + Ex++1]
where PB is the projection operator onto B, respecting the norm -1--
In the PABI analysis by Feldman et al. [6)]. gradient descent is conceptualized as a contractive mapping thr in the l2 space. Leveraging an additive Gaussian noise mechanism after each iteration, i.e., & ~ (O, I²)), leads to the observation that the Rényi divergence of identical CNIs with
differing initial conditions Xo and X decays inversely with respect the total number of iterations
a Xo-xxlla Altschuler et al. [27] further extended this framework with improved bound as follows: 2Ko²
K. Specifically, it is observed that (a xkk) <
Proposition 1. Let XK and Xxs denote the outputs from CNI(Xu, [wr]. (C) and CNI(Xu, ( 1%1,11110 J.B). respectively, where Ek ~ W(0.oFIa) Define distortion P ==
supk.a 1/%% (z) (x)) and let B have diameter D. If {vha and (86) are contractions with K coefficient e < 1, then for any T (O....,K-- 11,,
Da(X X S
(K (K- Distortion Absorption
+ D2
0²
PABI
The bound in Eq. 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 (the Distortion Absorption term), complemented by PABI term. 'he latter indicates that identical contractive transformations applied to bounded processes reduce privacy leakage in an exponential manner. Note that the bound in Eq. 33 convex with respect to r, optimized selection of leads non-divergent upper bound p(In D2 pp) + 1) where p = p² 02/2 In(//c).
Note on Parameter Set Diameter D. The privacy bound in Eq. relies on the assumption of bounded diameter D of the parameter set to upper bound xo- Wasserstein distance (definition in App. Ap between the coupled CNI processes X, and X Although in theory, the upper bound of Eq. (3) only depends on log D by optimizing т, we notice that the value D is important to get a practically meaningful privacy bound. To tighten this term, we will introduce a novel co- -o-Wasserstein distance tracking method that circumvents the need for the diameter parameter in Lemma 3 (detailed later): A high-level idea is track the xc- o--aassesttenn distance between noisy iterates via constructed couplings instead of using the default set diameter as an upper bound.
Note on Noise Random Variables & The traditional PABI analysis primarily examines gradient descent within the l2 space employing the Gaussian mechanism. In contrast, in the context of graph diffusions, modifications to Proposition 1 are necessary accommodate the l 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 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 9 = {dx 1 we introduce noisy graph diffusion 2k.o where K denotes the diffusion steps and the standard deviation of the added noise, constructed by series of composing noisy graph diffusion mappings óx
DK.0 0K o 2K 0...0 o ò1,0; where Φ8.0 (f 1)) 5/5 + =(22)
(4)

---

where f is graph-dependent degree-basee function set as f(x) mix(mX -1 d), 17- d) with threshold parameter 77 to balance privacy-utility trade-off. Specifically, f clips the values of the diffusion vector according to node degrees. Notably, the thresholding function allows for negative signals, capturing scenarios where the diffusion coefficient "/.,k can be negative, Noise variables &k and e(2) are independently sampled from a Laplace distribution L(O, o). 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 & space, with empirical evidence provided in App. D.4
Design of Thresholding Function f. In the noisy graph diffusion process, the role of the graph-dependent thresholding function f is twofold. Firstly. f ensures bounded distance between the coupled diffusions over two adjacent graphs, analogous to the
role of the general projection operator PB in the standard CNI as defined in Eq. (
Such a bounding effect is also crucial for the later anal- ysis of oo- Wasserstein distance tracking in L Secondly, and more critically, our theoretical analy- sis reveals that edge perturbation affecting low-degree nodes results in increased distortion at each diffusion step (illustrated in Fig. D. Uniform thresholding cou- pled with randomness injection for all nodes typically yields suboptimal performance in such cases. Our degree-dependent design naturally controls the distor- tion per iteration caused by low-degree nodes which helps with reducing the added noise. More detailed distortion analysis on f shown later in Lemma 2 The threshold parameter 17 is commonly employed to optimize the privacy-utility trade-off in practical appli-
18 Edge Perturbution on Low-degree Node
Before Difladon
Alke Diliniiss
Dimertion 0.7
Edge on lligh degree Node
Diffision Settings
SU
TLAk 0.7,
11
40
20
Dittetion =n 0.525
50
Figure 1: Illustration of Distortion from Edge Perturbations Adjacent Graphs for Nodes with Low and High Degrees.
cations (20). The empirical benefits of J are explored in experiments detailed in Sec. 4.2
Discussion Dual Noise Injection. Our framework employs a noise-splitiing technique, injecting dual Laplace noise at each diffusion step to construct non-divergent privacy bounds, as outlined in Eq. Theoretical justifications for this design is provided in the proof sketch.
Following this, present our main result on the privacy guarantee of noisy graph diffusion:
Theorem (Privacy Guarantees of Noisy Graph Diffusions). Given a graph G, associate graph diffusion 9 (Øv 100 k== then noisy graph diffusion mechanism ØK.a ensures edge-level (a, c)-DP
with satisfies:
(K- - T) Ia (o, (ag) + Ia Paiif (1
E
min
.Ymux
Tuux
K K-r
(5)
+E ........-1..
Tima
where go (a, = - In( Za-I
a exp( (osp(am1p)
2-1 exp(- m)) denotes the Rényi divergence in- ( (4-maxx: 2 -1 represents the maximum
duced by the Laplace mechanism 144, and Pag = max single-step distortion incurred by diffusion on adjacent graphs that involves Lipschitz continuity (1)
coefficient "imar. and maximum diffusion coefficient N/max
By selecting [K-
In((
In(
b) ), privacy budget remains bounded by
Par
Toaxs
Pdiff
1 Paig
Im
In Ymmax
In
1
Ymaa
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 cumulative Rényi divergence over Laplace noise with single-step distortion Aan, while the PABI term quantifies the exponential decay rate, echoing the result in Eq. (3) However, key difference lies our approach; instead of leveraging the projected set diameter / to control the distance between coupled CNIs, proposed So-Wasserstein tracking method yields more practical term,
5

---

Pan- m Further details and utility evaluations of this tool are presented in the proof sketch and Sec. respectively.
The function 9a (a., p). which measures Rényi divergence for the Laplace mechanism, increases with distortion p and decreases with noise scale σ. This behavior implies that reducing distortion and increasing the noise scale enhances privacy. To achieve better calibrated noise within a given privacy budget e, we calculate the two terms in Eq. (5) for each Leveraging the monotonicity of do (a, p). we employ a binary search to identify the appropriate noise scale o. The optimal noise scale is then determined by selecting the minimum value across various 7 values, achieving this efficiently with linear complexity relative t.
It is important to note that the maximum single-step distortion Paitt in Eq. (5) is tight and conveys several messages. First, as defined in Eq. ( when the diffusion process is relatively slow (i.e.. ni. < A), the distortion remains tight, governed by the Lipschitz constant Ymux of the diffusion mapping. In contrast, when the diffusion is relatively fast (i.e., Y1.k 2 72,x), the distortion bound becomes asymptotically tight, depending on graph structures, with worst-case scenarios detailed in App. B.I
In Eq. 6 we demonstrate the convergence of the privacy bud-
RDP of Graph Diffusions
get with respect to diffusion steps K. This approach differs from the adaptive composition theorem [42), which analyzes
RDP Provacy Budget (e)
Durs
10-
Composition Theam
how privacy guarantees degrade when composed mechanisms
are applied. Although this method has commonly been em-
ployed to protect privacy in graph learning models [52 [5]55]]
10
it leads to linear increase in the privacy budget with the num- ber of iterations K under Rényi divergence (44). potentially resulting in unbounded losses as K grows to infinity. 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. Further empirical evaluations are detailed in App. D.4
10
Iterations (I)
Figure 2: RDP vs. Total Diffusion
Step K with 71,b = 7.,
72,6
73,8 0.2, a = 2, 0.01, and n= 10-5
3.3 Proof Sketch of Theorem
Proof Idea. Similar to Eq. 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 (Step & 2). Subsequently, we explore degree-baset thresholding to manage distortion, achieving a superior utility-privacy tradeoff (Step 3), and introduce oc- Wasserstein distance tracking to further tighten the divergence at (Step 4).
Step 1: Interpretation of Iterates as Conditional CNI Sequences. Consider the coupled graph J-kmi 1. and the thresholding functions f and f', operating over adjacent graphs G and g", 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:
diffusions 2 = {oh { and D' 1
8k = ( Sk +5(2), S/² = (1 + ((1)
(1))
((2) d (h + ((1) 2((2)
5%
SB
Identical CN1
Identical CNT
where ((2))
o), and ((22 L -1( and - denotes equality in distribution.
(()) (11)) e/(2)
is absorbed by the conditional event of noise variables, i.e., <(2) (2) the coupled diffusion vectors evolve with identical CNIs through the contractive mapping Φ f. Note that the Laplace distribution is essential for fully exploiting & distortion in our analysis.
When the distortion %% (f((s())))) - du (f
Step 2: Bounding Privacy Loss through Distortion Absorption and PABI. The privacy loss of coupled iterates D. (sx [[()]) can be bounded by the distortion from graph diffusion, and PABI:
(2)2) Da(s l|sx)) Da( (7+kkk + sup (sx 1 <|ls's
1r ))
22))
(7)
Distortion Absorption
PABI

---

This inequality arises from leveraging the prsteeroesssing and strong composition rules of Rényi divergence. Here, Ç represents a joint noise realization, and the parameter r is introduced balance the privacy leakage from the two terms - the divergence between the shifted noise variables accumulated from step 7 + step K (Distortion Absorption), and the divergence across conditional CNIs employing identical transformations Φx o f (PABI).
Step 3: Bounding Distortion Absorption
Lemma 2 (Absorption of Distortion in Laplace Distribution). For any {0,1, K 1}, we have
Da Da ( S (K ((KK-7)900 T))a(o,))
(8)
Here, e quantifies the maximum distortion introduced by single-step diffusion and is determined by the thresholding function normalized by node degrees, i.e.. d;
[f(sa]].
The observation on f highlights the importance of a degree- based design for the thresholding function f. Uniform thresholding across all nodes results in distortion proportional to -_ 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, f is tightly bounded by
Par = max(477ma maxx) 17-
Upper Bounding PABI with oo- so-Wasserstein dis- tance tracking. To perform tight privacy analysis for the second term in Eq. 77. we develop novel oo- o--Wasserstein distance tracking method for coupled CNIs, where we denote the oo- oo-aasserneein distance at step by Wy. This method discards the original boundedness condition in PABI (Eq. (3) Second Term), which relies on the diameter D.
Step 4:
19"
Comparison w
Original PABI with Dismeter Tracking
10..
10-2.
Lemma 3 (PABI with co-aasserstein Distance Tracking). Given two coupled graph diffussins mentioned above, for any T E {0, ...,, - 1}. any noise realization Ç, we have
10
10
10
10
Threshold (9)
Figure 3: Setting: Graph Diffusion
with n,k 0.8, 12, 0, Y3,k
Da(s
CI|s 1 () S ga "imxx K-r
ww)
(9)
0.2.
where the tracked oc- Wasserstein distance over coupled CNIs is given by w, naturally upper bounded by
(1- and is 1-Toor
W.
We argue that using w, (or the upper bound w) instead of the default diameter D is crucial to make the algorithm practically usefull There is no numerical evaluation in the previous study 227. Numerical comparison between w and the diameter of thresholding function D 1 Σ i= d, using the real-world BlogCatalog dataset (detailed in Sec. +. is illustrated in Fig w achieves offees--f-maantuude improvement, which is still significant even D impacts privacy loss via a logarithmic term. Further empirical validations demonstrating significant utility improvements are detailed in Sec.
By substituting the bounds from Eq.
8 and Eq.
9 into Eq.
we establish Theorem L
3.4 Personalized Graph Diffusion Algorithms with Application in PPR Diffusion
In practice, graph diffusions often originate from single node e,, personalizing the algorithm to this seed node (user). Since the output is provided only to the seed node, protecting its edge connections (one-hop neighbors) becomes unnecessary, ensuring no privacy leakage in the first diffusion step under personalized privacy guarantees. Consequently. the thresholding function is tailored as follows:
f(x) = mninmmax(x... -1) d), ndd,, where [dl; = [dl, for j * i and [d]; can be set to any positive threshold, i.e., control is needed for the diffusion over seed node. 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 G, an associate graph diffusion 2 = jo then personalized noisy graph diffusion mechanism KK, with corresponding f(x) min(max(x, -17 d), d) ensures personalized edge-level (a, RDD
7

---

with satisfies:
ES min
(K-T) 7) Ia (o, Pag 1740) + 9a
Pdig
(1
Vit Miax)
K-T
(10)
mmax
TE (0.11,...,K
Tmmax
where 1 denote indicator function.
Note that key difference from Theorem 1 is that in personalized privacy settings, there is no privacy leakage in the first diffusion step (K 1).
PPR Application. Among various graph diffusions, PPR stands out as 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 follows:
((s) (1
3 Ws
lim Φx Φ1 (s), where dx(x) = BW + B)s. (11) +00
where lazy random walk matrix W (P and - ()) represents teleport probability with 3 E (0, 1].
Our framework incorporates noise into the diffusion process of each step of PPR. The privacy guarantees for this noisy PPR are derived from Theorem with Pair = 2 and Ymax = 3. Note that, since */, > 0 for all j {,,2,3 3} in PPR scenarios, all signals propagating among nodes should be non-negative. Consequently, the degree-based thresholding function f can be further modified as f(x) = min(max(x, n)
Experiments
In this section, we present empirical evaluations to support our theoretical findings. Specifically, we apply the widely-used PPR algorithm (Sec. 3.4) real-world graphs. In practice, we also include projection step onto the unit & ball after injecting Laplace noise at each diffusion step. This adjustment has been observed to slightly improve the utility of the resulting PPR without impacting our theoretical analysis (see App. B.1 for details). We focus on the accuracy of noisy PPR in ranking tasks under personalized edge-level DP due to its practicality as noted (20).
Benchmark Datasets. We conduct experiments on the following datasets: BlogCatalog [57]. a
social network of bloggers with 10,312 nodes and 333,983 edges; Flickr (57]. a photo-sharing social network with 80,513 nodes and 5,899,882 edges; and TheMarker [58 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 mecha- nism 42 the adjacency matrix, excluding seed node-connected edges in personalized scenarios. Entries are replaced with values in (0, } uniformly at random with probability (detailed in App. F retained otherwise. This method requires O(Vi2) time to generate private adjacency matrix and increases its edge density, which limits its practicality. Both our approach and DP DP-PUSHFLORCAP 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 run Flickr.
Metrics. For utility, we employ two ranking- based metrics: normalized discounted cumulative gain at R (NDCG@) @ and @e [59]. where denotes the cutoff point for the top-ranked set to 100. For privacy assessments, we utilize the
items in the list. In our experiments, personalized edge-level (e, dDP, with 5 set to #odges following [53). To ensure fair comparison, both DP- PUSHFLOWCAPP and Sogge-Fliping are analyzed using RDP. The privacy budgets for all methods are subsequently converted to DP from RDP results, as elaborated in App. reported as averages over 100 independent trials, with 95% confidence intervals.
E
All results are
4.1 Evaluating Privacy-Utility Tradeoffs on Ranking Tasks
In this series of experiments, we aim assess the ranking performance of our noisy graph diffusion (as delineated Sec. (.4) compared with baselines on real-world graphs. We specifically examine privacy budget ranging from 10 to 1, PPR with parameter & 0.8. Considering that both our

---

approach and DP DP-PUSHFLONCAP employ a thresholding parameter ni to balance the privacy-utiligg trade-off, we select r from set of seven values spanning orders of magnitude from 10 10
range empirically determined to be optimal across various datasets for both methods (1) 10-6 is chosen for DP-PUSHFLOWCAI
(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. respectively.
BlogCatalog NDCG@100
Mhekarker NDCG@100
Flickr NDCG@100
NDCG
NDCG
LUDCO
PastdtanCip 2igettapli
0.7
10 Epsilon
101 Epsiion (6)
Epsilon
Figure 4: Trade-off between NDCG and Personalized Edge-level Privacy.
Results for NDCG@ 100. As illustrated in Fig. our noisy graph diffusion surpasses both baselines across all three datasets, where values below 0.7 are ignored. In strong privacy regime (e S 0.5), our approach demonstrates sigmificant improvement over UP-PUUSHFLOWHH which relies on output perturbation. This validates our claim that a noisy process achieves superior privacy-utility trade-off' in stringent privacy settings.
top-100 Results for Recall @ 100. Fig. |iillustrates the overlap of the top- 100 predictions of privacy-preserving preserving
PPR variants with standard PPR. Across all datasets, our method outperforms two baselines for values ranging from 10-2 to 1, further substantiating the advantages of our framework.
BlogCatalog 1ecall@:
TheMarker Recall@1100
Flickr- Recall@:
Edpe//opap Oiz
Edpettiping
Okur
Revelle1 00
Reccsllgrr 60
Epsilon (x)
Epsilon (c)
Epsiion (6)
Figure 5: Trade-off between Recall and Personalized Edge-level Privacy.
Additional experiments the sensitivity of ranking performance over variations in r are deferred to App. D.3, which demonstrate that our approach is significantly more robust on the choice of the hyperparameter 7).
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 co- ao-Wasserstein distance tracking tool. Ex- periments were conducted on BlogCatalog, utilizing PPR diffusion with parameter 0.8, and total of K = 100 diffusion steps. Additional ablation studies focusing variations in noise type and comparative analyses of noise scales across different methods are detailed App. D.4
Dagree-based Thresholding Function & co- aasasssesnn Tracking. We evaluate the effec- tiveness of our graph-dependent thresholding function ff and oosasssesteiin distance tracking. We vary n uniformly across seven discrete values in from 10-4 to 10 and report the op- timal performance for all methods in Fig. 6 Firstly, we compare the degree-based thresh- olding function f(s) = min min(max x, 0), n d) (Red .) against its graph-independent variant f(s) = min(maxx(e 0) 1) (Red x), which uniformly clips over nodes regardless of their degree. As varies from 0.1 to 3, the degree-based thresholding function consistently out- performs its graph-independent counterpart, with margin of 0.15 to 0.2 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 (f) naturally induces diameter 7/|| (2n)ET), re- spectively, which can utilized the modification of Theo- rem for privacy accounting. However, the graph dependent thresholding function I results significantly larger diam- eter, which substantially degrades utility. This underscores the importance of leveraging oc- Wasserstein tracking.
Throsholding & W. Tracking
03-
Dependent
D8: Gluph ladependent -Nussersiii Tracking
Independon:
-0- Goyh Depeedeett + -Intured Barmetr
We showcase the benefits of our oc- Wasserstenn distance track- ing analysis (Red Lines) on the privacy-utility tradeoff against diameter induced bounds derived from & projection (Green Lines) or thresholding function-induee induced diameter (Blue Lines). The privacy bound of the & projection is established based on a Laplace modification of Eq. (3) with a diameter of 1. As shown in Fig. 6 methods employing xx-Wasserstein distance tracking analysis consistently outperform those based on & projection and thresholding diameter. We conclude that oo-Wasserstein tracking analysis and the design of graph-dependent thresholding function f markedly enhance the privacy-utility tradeoff.
Gruph Depcodent Projetiin
Graph Indeperdent Projection
0.0
Epsilon
Figure 6: Effectiveness of degree- based thresholding function and oc- oc-Wasserstein distance tracking.
Conclusion
In summary, introduce noisy graph diffusion framework for edge-level privacy protection, utilizing a novel application of PABI l space. By incorporating a theory-guided design for a oc- c--aaserstein distance tracking tool, we outperform SOTA methods in ranking performance on benchmark graph datasets.
graph-dependent thresholding function and employing
Societal Impact and Limitations. Our work advances the development of DP graph algorithms, offering strong privacy protection when properly implemented. For its limitations, we refer readers to standard textbooks the subject (42). The effectiveness of our noisy graph diffusion framework has been demonstrated primarily 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, 113-2239 and JPMC faculty award 2023. The authors would like to thank Haoyu Wang, Haoteng Yin for the valuable discussion. The authors also would like thank Alessandro Epasto for the discussion about the implementation of the output-perturbatinn perttrbationn-aaseee differentially private Personalized Pagerank.
References
[1] L. Page, S. Brin, R. Motwani, T. Winograd, al., "The pagerank citation ranking: Bringing order to the web," 1999.
[2] Chung, "The heat kernel the pagerank of a graph." Proceedings of the National Academy of Sciences, vol. 104, no. 50, pp. 19735-19740, 2007.
[3] Cho and Schonfeld, "Rankmass crawler: A crawler with high pagerank coverage guaran- tee.," in VLDB, vol. 7, pp. 23-28, Citeseer, 2007.
[4] R. Andersen, Chung, and K. Lang, "Using pagerank locally partition a graph," Internet Mathematics, vol. 4, no. pp. 35-64, 2007.
[5] Fortunato, "Community detection in graphs," " Physics reports, vol. 486, no. 3-5, pp. 154174, 2010.
10

---

[6] K. Kloster and D. F. Gleich, "Heat kemel 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: 2018.
[1]] Gasteiger. S. Weißenberger, and Günnemann, "Diffusion improves graph learning," Ad- vances 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 2xXx:2006600988, 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 net- works, 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 preprini wwXiv:2009.06800 2020.
[17] Q. Zhong, Y. Liu, X. Ao, B. Hu, Feng, 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 21-24, 2016.
[20] A. Epasto, V. Mirrokni, B. Perozzi, A. Tsitsulin, and P. Zhong, "Differentially private graph personalized pagerank," Advances in Neural Information Processing Systems, vol. 35, pp. 22617-22627 2022.
learning via censitivity-bounede
[21] A. Gupta, K. Ligett, F. McSherry, A. Roth, and Talwar, "Differentially private combinatorial optimization," in Proceedings of the twenty-firs annual ACM-SIAM symposium on Discrete Algorithms, pp. 1106-1125, 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 decentralized social graphs: The case of eigendecomposition." IEEE Transactions on Knowledge and Data Engi- neering, 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 11 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, IEFE, 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," IEKE 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: 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. 1 1156-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] McSherry and K. Talwar, "Mechanism design via differential privacy." in 48th Annual IEEE Symposium 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, Zhu, and 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. J. Yang, 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. LLng, "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 "The algorithmic foundations of differential privacy." Foundations and Trends@ in Theoretical Computer Science, vol. 9, no. 3-4, pp. 211-407, 2014.
[43] 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] E. Chien, H. Wang, Z. Chen, and P. Li, "Stochastic gradient langevin unlearning"" arXiv preprint arXiv:2403. /7 105, 2024.
[46] E. Chien and P. Li, "Convergent privacy loss of noisy-sgd without convexity and smoothness." arXiv preprint 2rX0v:2410000008, 2024.
12

---

[47] W. Ye. Z. Huang. Y. Hong, and A. Singh, "Graph neural diffusion networks for semi semi-supervised learning," " arXiv preprint arXiv:2201.0900 096998 2022.
[48] 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.
[49] R. Kondor and J.-P. Vert, "Diffusion kernels," kernel methods in computational biology, pp. 171- 192, 2004.
[50] M. Göksedef and Ç. GündizzOgüdicii, "Combination of web page recommender systems," Expert Systems with Applications, vol. 37, no. 4, pp. 2911-2922, 2010.
[51] S. Hwang and Y. Lee, "Identifying customer priority for new products in target marketing:
Using rfm model and textrank," Inmovative Marketing, vol. 17, no. 2, p. 125, 2021.
[52] S. Sajadmanesh, A. S. Shamsabadi, A. Bellet, and D. Gatica-Pered "[GAP}: Differentially pri- vate graph neural networks with aggregation perturbation," in 32nd USENIX Security Symposium (USENIX Security 23), pp. 3223-324202 2023.
[53] 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.
[54] M. Kearns, M. Pai, A. Roth, and 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.
[55] G. Jeh and J. Widom, "Scaling personalized web search," in Proceedings of the 12th interna- tional conference on World Wide Web, pp. 271-279, 2003.
(56) Sajadmanesh and D. Gatica-Perez, "Progap: Progressive graph neural networks with differ- ential privacy guarantees," in Proceedings of the 17th ACM International Conference Web Search and Data Mining, pp. 596-655, 2024.
[57] R. Zafarani and H. Liu, "Social computing data repository at ASU," 2009.
[58] R. A. Rossi and N. K. Ahmed, "The network data repository with interactive graph analytics and visualization," in AAAI, 2015.
[59] K. Järvelin and Kekäläinen, "Cumulated gain-based evaluation of ir techniques," ACM Transactions on Information Systems (TOIS), vol. 20, no. 4, pp. 422-446, 2002.
[60] 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.
[61] 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.
[62] Duchi, S. Shalev-Shwartz Y. Singer, and T. Chandra, "Efficient projections onto the ball for learning in high dimensions." in Proceedings of the 25th international conference Machine learning, pp. 272-279, 2008.
13

---

Appendix
Contents
Preliminaries
15
Privacy Guarantees for Noisy Graph Diffusion: Analytical Proofs
15
B. Main Prool
15
Discussion Personalized Graph Diffusion
18
Additional Experiments
18
D.I Datasets and Experimental Environment
18
D.2 Running Time
................................
18
D33 Sensitivity Ranking Performance to Variations in Threshold Parameter f).
19
D.4 Ablation Study
19
RDP to DP Conversion
20
Proof of Lemmas
20
Proof of Lemma B.1
20
2
Proof of Lemma B.2
22
Proof of Lemma B.3
24
F4
Proof of Lemma 8.4
25
14

---

A Preliminaries
In this section, definitions and lemmas are introduced to facilitate the presentation of proofs. Recall that the contraction mapping denote self- mapping I-Lipschitz continuous function with / E [0, 1], and the oc- ac-Wasserstein distance is defined as (H, p) = inf (p. ess Sup(2.)))~71l
|| y/l, where V( represents the collection of all couplings between and v. Further, define R, Ra == s
(E + +rr()) r|(s), where ę [(0, o). measures the extent which the Laplacian distribution can absorb shifts of magnitude p. For clarity, Da (pllv) and Da (x]]))) Y), with X p and Y v, are used interchangeably when the context is clear. Besides, we denote Xzj. i,j E 2 S j as joint couple of (X,, Xit1,..... Xj). We introduce Shifted Rényi Divergence as follows:
Definition A.1 (Shifted Rényi Divergence). Let μ and be distributions defined over Banach space (x, || II) For parameter = 2 0 and a 2 1, the z-shifted Rényi divergence between and v is defined
inf (ulP)) (e
Da (a'(ll
(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 pa, v, & be probability distributions on R". For any p 0,
D (u * ellv @)
(ullu)+ + sup De + +r(e) r: =
(13)
Lemma A.2 (Contraction-reduction lemma 27 Suppose vú, v are random functions from IR" to
E" such that (i) each is strict c-contraction almost surely, and (ii) there exists coupling of (v) ei) under which supx (xx(x) - v (x)x)l S p almost surely. Then for any probability distributions and on 12".
D(aztpl ( (1bulll Va s D(
(14)
Further, we recall two properties of RDP in our analysis.
Lemma A.3 Prost-processing Property of Rényi Divergence). For any Rényi parameter 1, any random function f. and any probability measures μl, v, we have
Da (a(IvullSw)) S (1lll)
(15)
Lemma A.4 (Strong composition for RDP). For any Rényi parameter a 2 1, and any two sequences of random variables XI,...,
......,,,, X and YI...., Yk.
PP (PYx)) S Σ sup Da I
B Privacy Guarantees for Noisy Graph Diffusion: Analytical Proofs
In this section, we present the main proof for the results in Theorem detailed in Sec. 3
B.1 Main Proof
Proof of Theorem 7 Given a seed s, a total diffusion step K, a noise scale a, and degree- thresh-
olding functions f, we consider two coupled graph diffusions (s), (s) which propogate on two joint edge-level adjacent graphs G, g' respectively with diffusion mapping Φks H/ [K]. Specifically, we have
(s): Sy ch Sk + + I K,
(16)
(s): 5/ = 0% (S'(s (1) +
(12)
(17)
(18)
15

---

where 5 -60 .5k - .5% are distributed according to the law o)
Step 1: Distortion of Single-Step Graph Difffusion In each diffusion step. distortion over the diffusion mappings Øb o f is introduced due to the graph adjacency between the graph diffusions (s) and ( This distortion, which is crucial for the subsequent analysis, characterized by the following lemma:
Lemma B.1 (Distortion of Graph Diffusion). Given two graph diffusions Øk.o (s), K, (s) men- tioned above. Let f, f' denote corresponding graph-dependent degree- based thresholding operators, i.e., f(x min(max (x, -1 d), d). The diffusion distortion satisfies:
sup (f()) (x)(( S max maxx(400kx xER
(maxx Ymmax "1
(19)
where Lipschitz constant Yimax max; /.,el
max;
(1) 122, and maximum diffusion coefficient Tmax
We denote this single-step graph diffusion distortion bound as Pait,, i.e., Pai (1ax(4")mmm (1) Moreover, incorporating an l--ball projection PB into the pipeline, i.e., adopting &z o P B, does alter this distortion bound.
Ymuxx 2 fmax) ) -7-
According to the proof, this distortion analysis is tight and conveys several key insights. First, when the graph diffusion process diffuses relatively slow, i.e., 71.k < k2 the distor- tion is tight and primarily governed by the Lipschitz constant of the diffusion mapping. In contrast, when the diffusion is relatively fast, the distortion is controlled by the maximum diffusion coefficient "1,A- In this latter scenario, the bound becomes asymptotically tight when the graph structure satis- fies the condition that the nodes connected by the perturbed edge have no common neighbors, and their degrees tend to infinity. We raise a double star graph as an toy example that satisfies the above no common neighbor condition (see Fig. 7
Figure 7: Double Star Graph.
Step 3: Bounding the Privacy Loss via Shift A Absopption and PABL. Next, we consider the noisy diffusion process, where Laplacian noise is introduced during graph propagation. Note that, we focus on injecting noise at the initial step of the diffusion process, although the analysis can be directly extended to include noise injection intermediate steps. For k 2 drawing upon the moise-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 (s) as follows:
= (x + (((1) + 21(2) where E ~ ((d ou (f(()))))))
(20)
where we introduce 2K2) as shifted Laplacian noise and noise scale d3 = a. Therefore, the coupled graph diffusion processes can be summarized as follows:
S
ou (S ()) + ch +5( 5/c- = tn (J + 5k
+EK
Vk 2 1.
(21)
Identical CNT
Identical CNI
Note that our objective is to establish upper bound for D. 1s we claim that for any parameter 7 E
(0, 1, 1....
K-13 1).
K
(a) Da S.t1.k |s<k:
Da, (Sx 18())
(22)
(t21.k)
21(2)
(22)
(b) (a!
-
(2)
(1(2))
sup
(Sk
(7t1:k (sx
(2)
G4 7(2)
Sr11k)
Shift Absorption
PABI
(23)
16

---

where +++1 is noise realization, (a) is by the post- pest-proesssing inequality of Rényi Divergence (Lemma A.3 and (b) from the strong composition rule for Rényi divergence (Lemma A.4).
As demonstrated in Eq. 23 the privacy leakage can be upper bounded by the Rényi divergence across joint Laplacian distributions with shift (shift absorption term) and the divergence across conditional CNIs employing identical transformations Φ% f (PABI term). The parameter т 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. distance tracking method that get rid of the diameter requirement in original PABI analysis. Besides, for each lemma below, we state that considering projection onto the & ball does not affect the conclusions.
important to emphasize that, for the latter, we leverage oc- oasseserstein
(1) Upper bounding shift absorption term:
Lemma B.2 (Absorption of Shift in Laplacian Distribution). Given two coupled graph diffusions mentioned above, for any T 2 0, the shift absorption term can be upper bounded by
K
Pa (l)+kkk
S
Σ k=T+1
ga( Paitt)
(24)
where
distortion Pail max (44)mmxx Ymax) 7 and shifted Laplace function ga(a, =
exp( o- p) + 2a-1 exp( - - p)).
o-1
a-1
20-1
(2) Upper bounding PABI term:
Lemma B.3 (PABI with Laplacian Distribution). Given two coupled graph diffusions mentioned above, for any 2 0, we have
sup (skl GHIKISK (2) 1-i
= (r+1ik) S ( (s,l(s,,) + 9a (ak, K- ".y)
(25)
The lemma demonstrates that the PABI term is controlled by the shifted Rényi divergence step and privacy amplification term that decays exponentially at rate of > In previous analyses of the PABI for the Gaussian mechanism, (27] utilized the diameter of the bounded parameter to further constrain the shift w,. However, we have found that this bound does not satisfactorily achieve a favorable privacy-utility trade-off practice. Subsequently, we develop a oc- Wasserstein distance tracking method to more effectively bound this PABI term, offering a more practical approach.
Lemma B.4 (PABI with oo- Wasserstein Distance Tracking). Given two coupled graph diffusions mentioned above, for any 2 O, we have
Pdiff Vimx)) Wr, D(w-) [|5,) = 0
W Ws ||s, <
(26)
7max
where distortion Pair maxx44mmxx 2mmxx .1..
(1)
By summarizing the above results (Lemma B.2 B.3 and B.4). we conclude the final results:
Da (s [|s/)
(Da (2)
(5 (7+1K) + sup Da (sk S7+1.K = (r+1. 1
(2)
(2)2)
-r-1:K)
So+1x
K
ga (akk, Pam)) + ga K-r w-)
(27)
k=
=(K- T) 9a (a, Pditt) + ga k-= Pditf (1 7
(28)
1 7max
17

---

C Discussion on Personalized Graph Diffusion
As discussed in Sec. in many personalized scenarios, the definition of personalized edge- level privacy shifts to protect edges that are incident to the source node. This adjustment offers additional benefits in distortion analysis (Lemma B.I): no distortion occurs in the first step. According the proof of Lemma B.I, given seed node with the corresponding initial vector and letting (u, v) denote the edge differing on adjacent graphs G and G' where {u, v). we have:
[s]u du
[AAD- )sl'
(29)
dg
since - = [s]. = Thus, when analyzing noisy graph diffusion a personalized scenario, this distinction results in a better bound for Lemma B.2] Further, Eq. (29) demonstrate that we can relax the thresholding over seed node to seek for better privacy-utility trade-offs. Therefore, for uniform noise scheduling, obtain the corresponding results in Theorem 4
6
min rE(0,..,K-1) Ia(a, Pdiff (1 max
7max
K
Pa, + +K - (a Pan 1 1x700
(30)
7max
D Additional Experiments
D.1 Datasets and Experimental Environment
As mentioned in Section this paper includes three benchmark datasets: BlogCatalog, TheMarker, and Flickr. Their details are included in Table 1
Size
Statistics
Dataset
Nodes [V]
Edges |g|
Classes |C]
Avg. Deg.
Density
Blogcatalog
10k
334k
39
64.8
6.3 x 10-3
TheMarker
69.4k
1.6M
NA
47
6.8 x 10-4
Flickr
80k
5.8M
195
146
1.5 x 10-3
Table
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 rumning time for a single trial of each method across all datasets in Fig. 8 As illustrated the figure, all single trial experiments of our method and DP- PPUSHFLOWCAP are completed within minute. In contrast, the edgeflipping mechanism exhibits significantly longer running times, ranging from 16 minutes to over 12 hours the size of the graph increases.
Rumning Time Comparison Across Datesets
11
Our Metlod
Ranning Time (Seecadis)
Cap
ExlgePlipping
24h
14
Bllge stain
Tonttebe Dataset
Figure Running Time for Single Trial of Experiments with a Privacy Budget of e = 0.1.
18

---

D.3 Sensitivity of Ranking Performance to Variations in Threshold Parameter
In this series of experiments, we further investigate the sensitivity of the NDCG ranking performance with respect to the selection of 17. Specifically, we enhance the granularity of the lj values within the existing range from 1 x 10 to x 10 by selecting 20 equidistant points for each dataset within this interval. The NDCG ranking performance depicted in Fig. 9 The left column represents the transition curve of our method, the middle column denotes the performance of DP- HP-PUSHFLLWWAL and the right column illustrates the performance gap between the two methods. For each privacy budget e, we highlight the optimal 1) corresponding to the best performance (yellow for our method, cyan for DP DP-PUSHFLOKKE PUSHFLOCAAP) As demonstrated
right column, when varies from 10-10 to 1 x 10- our method consistently outperforms OP-PUSHFLOWCAN up superior stability of hyperparameter selection for our method in terms of ranking performance.
10-6. This indicates
Our NDCG ClogCgg
Pushflow NDCG BlogCatelog
Performance Gap NDCG BlogCatelog
Privacy Budget e
Privacy Budget 5
8.0 Lu 0.3 6.6 6.2
Privary Budget
Threshold
16-33
36-8
Threshold
Threshald
Our- NDC- TheMarker
Pushflow NDCG TheMarker
Performance Cap NDCG TheMarker
0.2 1e Lo Lid 6.5 6.7 1.00
67
Privacy Budget e
Privacy Rudget
Privacy Rudget
aue 66 ni
1010 1s6 .26
106 les
1C4
Threshold 160
Thresbold n
Threshold
Our Bur-NNt RDCGN Flickr
Pushflow NDCG Flickr
Performance Gap NDCG Flickr
1in A. 56 573 E00
3 3.3 120 079 100
6. Privacy Budgett
Privacy Budget
Privacy Budgets
3.6 110
0.5 0.44 0.46
1x33
Ice
3e5
104
Threshold
Thresbald m
Threshold
7)
Figure 9: Transition Curves of Thresholding Parameter Relative to Privacy Budget 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 I and the Composition Theorem. Following the experimental settings outlined in Sec. 4.2 we perform experiments on the BlogCatalog dataset, utilizing PPR diffusion
with parameter 3 0.8 and total of K 100 diffusion steps.
Noise Distributions: Laplace versus Gaussian. We investigate the effectiveness of injecting Laplace noise 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. (Left). Within strong privacy regime where ranges from 0.1 1 to 1, the performance gap
19

---

between the two noise types is approximately 0.05. This finding supports the superiority of Laplace noise injection for graph diffusion processes & space and of practical importance.
Noise Comparision Lapiace va, Gaussino
Noise Calibration: Ours Composition
10a
DP Privacy Budget (c)
Parameter settings:
B- 0.8, f 10-), K-1
NDCG
0.50
Paeseneerr srtting:: d.08, K
0.45
0.50
Onne laplans
Ours
Composttion Thoorom
1010=
Epsilon (+)
Noise
(o)
Figure 10: Left:: Ranking performance with Laplace and Gaussian noise injection. Right: Comparison of noise scales between method (Theorem and the composition theorem under the DP metric.
Theorem I versus Composition Theorem. As we discussed in Section 3.2 one can naively adopt the DP composition theorem 43 44
establish the privacy guarantee for the same noisy graph diffusion. However, is a general approach and does not take the contraction properties of graph diffusion into account, which leads a worse privacy bound in our case. We examine the calibrated noise scales a under edge-level DP, converted from RDP. Figure I0 (Right) compares noise scales derived from our Theorem [T (Red Line) against those from the standard RDP composition theorem (Blue Line). Our method achieves noise scale that is 10 times smaller than that required by the composition theorem.
E
RDP to DP Conversion
First, we present the standard results on converting RDP to DP:
Proposition E.1 (Conversion from RDP DP (44). If M an (a, ERDP) mechanism, then
also satisfies (EDP, d)diifferettial privacy, where EDp ERDP log for any d (0,
To determine the DP guarantees of the three mechanisms, first calculate the RDP for each mecha-
nism. Specifically, we use Theorem 4 for our method, sensitivity analysis Theorem 4.3 from [20] with the dimensional Laplace mechanism under Rényi divergence (Eq. (46)) for DP-PUSHFLOWCAP
and Proposition 5 from [44] for EdgeFlipping. For all three mechanisms, the expression ERDP + log 1
a-I
convex in a. By setting #odges then search for the optimal minimize this expression
and obtain EDp.
F Proof of Lemmas
F.1 Proof of Lemma B.1
Given any E R", without loss of generality, assume that the edge sets of two graphs satisfy E' U (1,2), i.c., we remove edge (1,2) from graph G, resulting in graph G'. Furthermore,
let .iii) denote the neighbors of node i, and define the following index sets: A = (2))
B = ==(())
== An B, A' == A'C, and B' = B'C. Additionally, we can rearrange the
node indices in G such that A'
[3.
A' + 2). B'
[1A'1+ 3...., |A' + |B' 2). and
C = (IA + B + 3, [A'
+ BB [C| 2). We adopt the shorthand notation f; = [x)]]
|B'
and Af. [x] ; [x)) We first consider the case where d,, d2 2 2, and define m,
de (di -) m2 = dI Am == -4 Amg - Since degree-based thresholding
function f is symmetric, WLOG, we can assume is non-negative, i.e., (x) min(max(x 0),
d). We have the following
(f)x)(x)
=|00(=)) (((())))))))(((()))))))))))))))) (x(((x)) + 6' (f
(31)
= =I/,(PP - (2) + (TAPP' (fxx) f
(32)
20

---

-I ff(x + (TI.A
+ ((fx)
(1
(33)
0
0
f1
0
f2
7i,k 7,1k
d1
0n1
an
0
0
L
d1
d2
A f
f2
A'D'-''''11 )2.4)
(34)
A f
f2 fi d2 di
=1hm, :
m
m. m2 ".... M2, my + m2."" :. .m + m2 0,.............. 0,
|4 Times
BB Times
C| Times
+ 10,0, Am1, .... Am1. Am2 Ame. Am1 Amg
Am + Amg] T + +2,2k [Afi. 1f,'0,..,00
[A Times
B' Times
Times
(35)
<hiol
-0 -(1
f2
1)
+ + 1all.AA') 1A
1
+
Afi
+ +haal
|B'|-K
1
)/2
+
A
d2
di
di
di
d2
d2
d2
1
1
Afi
1
1
A
+ +ma -C1.
11
+
+
f +
+ +1222
((Afi
d1
d1
--1-
d1 1
d2
d2
d2
(36)
(0) maxl
ff
+
f2g
+ ha,i -1471
|d, - fil
+ Imn -18'|
Id2 fzl
d1
d2
di (dl - 1)
d2(d2 1)
di Afi f1
d2 f2
+ +1m.0l- -C1
+ +122,ll (Afi + Af2)
(37)
di (d) 1)
d2(d2= 1)
(6)
shm,ll
(
f1
+
f2 d2
) + |m,a1l
|d - fal
+ +mm,dl
d2 - fzl + 1722l (AS + Af2)
d1
d2
(38)
(c)
(
fi
+
f2z
+ |7,b
fi - di
+ mmnll
fz -d2 + 122 (AA + Af2
(39)
dz
di
d2
2
(d, - -
+ h12.1 moxll-ff
(fs - f/)
(40)
dj
max max(4/7,,): 20mal + h22l)) 17 S / 2mma))
(41)
where (a) follows from the non-negativity of the function f. and (b) is derived from |4' Ad'n = d1 - and BB' ncl d2 1. Equality is obtained when C = 0, i.e., when there
common neighbors
between nodes 1 and 2. (c) is obtained from Result and (d) originates from Result 2.
Result 1. Consistent with the above notations, we have ʃ3 d, 2 0 for j E (1,2).
Results 2. Consistent with the above notations, we have h1, (1) (4م²) + 12, 17) s
d2
max(2) m1,,, fan.ll/h... hi,e) + h2)))) for j E [1,
Proof of Result 1. From the above definitions, we have Sj [x)]] = min(max(2 0), 77 d3) and
f3 dd = d - (dg - 1)ʃ, where v, is the j-th entry of x. Now, consider the following cases:
When 2, < 0, we have f; d, 00
When 2, E (0, (d, - 1)n) it follows that f, - -d = ddnn - (dg - 1)mb = ne, 2 0.
When 2, E ((dy - 1)77, d,w)), we obtain f, - d A5; = (d, 1))dg - xz)r² 2 0.
When 2, > dz. f, - d, O.
In conclusion, based on the above cases, the result is proven.
Proof of Result 2. We consider different cases:
21

---

When 2 s 0, lm, الاا + l2,x fz) 0.
d;
When 2 E (0, (dg - 1)ni]. we have
Imllf [dg 2)/1, 122 - 13) 2/,,ll/bb
dl = 2/ (dj - 1)m
(42)
dj
dj
When 2j E ((dj 1),, dyn), we obtain
mmllfff (d, - + 122, (fg f7) dj
(43)
-myal1 (dj-1))
1)dj - (dj 2)0rg) ) 12uullzy (d,- 1))
(44)
dj
Smax( w/d 1)m (hi.l h2ex))n) S max(2 h1,1 h2.
(45)
dz
Note that, based on the derivations in (b) and (d), we conclude that the bound is asymptotically tight, with the worst-case scenario occurring when the nodes connected by the perturbed edge have no common neighbors, and their degrees increase infinity.
Additionally, when d1 = or d2 = 1, it can be directly shown that the distortion is upper bounded by max (ex(""mmn Tmmx: 2mmxx 1). Note that if we further incorporate Fuclidean projection onto & ball, we can regard PB (x) as a single input without altering the overall bound.
(1)
F.2 Proof of Lemma B.2
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 shift h R Ml, for two Laplacian distributions L(0, σ) and C(h, σ). if [[b]] S p.
Pa(C(O,o)) o)) S Inf a
expl
p) + 2a expl
a m))
(46)
a 2a
σ
Lemma Proof. With the above result, we can upper bound the Rényi divergence over joint noise distributions. For 7 2 0,
K
(2) (a( (o(S++1:k) lik ((
Da(E (2) 1
2 = Sr+1k-1 (1(2) (1)2)
2(2) ( = Sr+14-1)
sup
k= S
(47)
(o) (,(C(O,ou)) ow))
&
Σ
9o (ak, Paitt)
(48)
where (a) arises from strong composition rule for Rényi divergence (Lemma A.4, (b) is from the
definition of <(2) ((2) with shift h; (Øx f)(x) (0% (x), and (c) is derived by combining the results that the & norm of the shift is upper bounded by ||ba|| < Pair = mmax(4-mm, mmxx
(Lemma B.1 and the above Laplace bound under Rényi divergence (Eq. (46) with go (a, P)
exp( 1-11 p) + a-1
2 exp(- exp(-))am)).
Summarizing the above, we prove the lemma. Note that further considering a projection operator does not affect the distortion, established in Lemma B.I and thus leaves the bound derived here unchanged.
Proof of Result. Now consider Laplacian distribution, for h E R Vl, let h, denote the i-th entry of the vector, we have
M
(0)
Σ
1 In(
a
exp(
hhl)) + a
exp(- 2 xxp(-(1h1]) (h+l))
(49)
2a
2a
im
22

---

where (a) is from the additivity of Rényi divergence [60] and the Rényi divergence over one- dimensional Laplacian noise [61] By considering the worst case h, we can reformulate the problem
as:
I
maximize h
1=1 2a 11-1 exp( a -
In
a
- + a a-
2a exp(--2
(50)
s.t. ||||| p
(51)
For the above optimization problem, let A1 = 2n-1: 22 a-1 A3 2a and X
Define f(h;) -ي In(A exp(>2 hi) + λ exp(-1s h.). Consider the gradient term
(Da(C(O,, o) (l),
(P.(C(O,o)]lC(hnn) ()) 0f(hs) d1de exp(A2h4) - exp A exp(A2hhs + as exp((-1a1)
(52)
ah4
0h,
Further for Hessian matrix V=D,(C(0,0)I(((b..)
(CD, A1da A1 exp( exp(b>ah))))))) A exp((22h;) + A exp((>xxhi) >
(53)
th
8DD (C(O, = f.
(54)
Th.h,
From the eigenvalue criterion for positive definiteness, (C0,,,(( σ)) > 0, i.e. D,, (CC(O,,))l((h, o)) is convex function. As the feasible convex, maximum is obtained on the boundary of feasible set. Thus, the problem can be further formulated as:
V
maximize Σ
In(
2a exp(
σ [h,1)
a-1
exp( exp(-
a (hil)) -1al)) s.t. | = p (55)
2a
Next, we use the adjustment method to solve the above objective methods. First, we define hpi) - f(h+) and we fix h3...., We aim to optimize:
maximize L(h b2 hy...., b1.b2
(56)
with respect to h and h2, considering the constraints | p. This is equivalent to
2
[V]
maximize b1.
L(h1, h2,...,,,ppp hppp), s.t. hn + h2 =
h4-
(57)
Define 6 = p -y hy. Since c3 fixed, and h2 c3 - h1, the objective function become
univariate function, by calculating the derivative
OL
(Aarad + AcddAs)(oxp(A2h) + >a(hi cs)) exp()2(cs - h1) \ah1))
(58)
0h (Λ1 exp()2h1 + λS exp( -1a11))1))A exp(A2 h1)) + X3
- h1)))
OL < 0 for hı < - and OL The derivative AL reaches O when h1 S. Furthermore, ahv
> 0 for
Shy hy > T Thus, the maximum value of the function is attained at the endpoints.
0h1
maximize L(h, h2 he....., hyp) max [Mes, O, ha ... MM) L(O, ca, hy Avvi hy,
(59)
As the function is symmetric, two endpoints attain the same value, i.e. L(c3, O, ha....,.yy)) L(O, cs, hlv)). Now, we aim to maximize the objective function by each time adjustment two variables and fixed the rest variables unchanged:
maximize L(hi, h2 hy....,, hy byy.....yy
L(hi, f2 . hy.
maximize
ha...., hp))
(60)
hi tet
maximize maximize L(h, ba .g...., by) hi hiz
(61)
hy tho
23

---

maximize L(p - c3. Cs 03.,0........ hy..... mln I maximize L(p ct, 0,,0,0..... hpp) KI1
(62)
1 In( S... S T(p, 0) a
2a exp( p) a
exp( p)
(63)
2a
where (a) is from Eq. (59). and for each incquality, we adjust the values of h1 and h2 to maximized the objective function while keep the rest variables fixed. From the above reasoning, maximized the Rényi divergence over two Laplacians with shift.
F.3 Proof Lemma B.3
To prove the upper bound of sup (sks ( S7-1:K Gr+i.k / 2(22)
(2)
Sr+1:k),
mainly leverage the definition of shifted Rényi divergence (Def. A.I) with two properties under noise convolution and contraction mapping (Lemma A.T Lemma A.2p. Specifically, recall that
(a p) su D. +l({)
where & ~ C(O, σ), define ÿp Øb f. for any G711KK define
WK- 0.
D. Da(Sk 157 S5+1:k 1
| (+1kk)
ST+1KK
(64)
Diux ( 15+1:K = + s ST+1:K S+HKk)
(2)
(112)
(65)
(o)
S
((
= GHIx=1llx((k)((HH 202
= G+IIK-1) + R. (K)
a
(66)
(b) K tak
< Dr
Tru
1 (SK 11 S = fr+1: 212)
(2)
Sr+1:K-1 1r+1:k11) + Ra Ralok, (67)
to K
wx
DIwK- (SK-1 (2(2)
( = S 11 = (++1:-11) + Ra ax)
(68)
S...
(69)
K Σ
< ((w (Sr+1 (2) Cr+ +15
202) +
Ra
(70)
k=T+2
K
D (s+ (s]||s,))
+
Σ
Ralok.
(71)
km741
where (a) is from Lemma A.I and (b) derived from Lemma A.2 as (pk is -ontractve
(composition of two contractions). Further, we have
- Tmax Wip a
W--2 2 Ymux W++1 a 2 W+
a 8,42
(72)
K-r-1
K w.
WK
mma ak-k
k=0
By setting ar+1 ..., ak-1 have aκ V K-Tw, Wy. Therefore, we have
(2) Da(sk 1 G++1x
(1 11s
(T+1KK D(w)) (|=,) + Ra (O m K-Tw,)
(73)
From the result in the proof of Lemma B.2 Ra , the above, obtain
K- [w = ga Vmxx Tw7). Summarizing
(s(
(2) S++1:K | 1 (++1k)) S ((==) (s, ga 7 w,)
KKTw,)
(74)
Further, we point out that incorporating the projection operator, i.e., yFk th o ʃ Ps. does not affect the contractiveness of the mapping. Indeed, projecting vector onto the -ball via Euclidean projection yields a nonexpansive operator under the l norm (62] and thus this extension does not alter the bound.
24

---

F.4 Proof of Lemma B.4
To prove this lemma, we consider tracking the oc- Wesseessttin distance of the coupled iterates. Given 2 k.11 and O K. for 2 1, recall that for any k(k 2 1),
(x,((s):
ox (f(s==)))
( + 4x kk)((s) 8/ = (f
Ex + ((2) (75)
For any step k=k 2 1), let jal and vi denote the distribution of sy and s/ respectively. Further, define i and ig denote the distribution of S = (EI:k. fi.)) and S = (C (1x),, respectively. For step 1, we have
(i) inf ess sup ||s| s (LET(n))1) (51.)()=
(76)
inf ssssup ([)o)) + +1 + +5( - (s)(s) -1 -/10) (S
(77)
ssssup (
| (S(S)) - (I' Pain
(78)
where (a) is from selecting a coupling #* such that r.v.s S1 and S are identical.
Next, for any т, following the above procedure, define #g I' ps) such that Sn. Sy are identical,
we have
W (KT,
inf esssup ||8 - s/,112
(79)
v, E.(T( (s.,6)
inf ((r,
esssup (()
(fr + x + -
0%, (f(((()) - 2 1|2
-00
(80)
< ess sus (,
||0, (f+((()))) + ((1) + ( Φ (5(1))))) (24) -
(81)
esssup (S, )
((+ - (f
(82)
Following the analysis in Lemma B.I by induction,
CSS sup
(f+ - -f(
(83)
(S, ) 1
( (f+ - (f- 1)l + (1-((f($;--)))) -s
CSS sup (S, 188 1
(84)
088 sup 1S.-1.8 St 1
Timxx ||8t-1 8 + Pan
(8:5)
....
(86)
058 sup 7 ||8ı s/ll1 Paint (1 + Tmax + =m=2)
(87)
(c) T-- (1 Mmax) Pain Pain
(1 Yiaax
(88)
Tmax
Tmax
Pdiff (1
(89)
Ymax
where (a) is from Lemma B.1 (b) from induction, and (c) arises from Eq. 778
Therefore,
Woo (Mr, 22) < Paift (1 m
(90)
1 -max
Further, when we set w, (1-)
1-7mm we have
D(u=)
inf I.: (F))
Da(u(llu)) =
(91)
where the equality is achieved by selecting μl, Vy.
25

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All main claims substantiated both theoretically (Sections Appendices A
and B) and empirically (Section 4 Appendix D
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
26

---

Answer: [Yes]
Justification: The complete proofs are presented in Appendix B with proof sketch outlined
in Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have uploaded our code in supplementary file. All information to reproduce the main experimental results discussed in Section 4 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
27

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have uploaded our code in the supplementary file with instructions (README.md)) to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/ htaalees//ooeeSSmmimiiionoffeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/ccpppbllcgggudeeeeeeeeeeee Coaee///ddeSebmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental details are all included in Section 4 and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have included 95% confidence interval for our main experiments in Section 4 (Fig. 4 Fig. 5)
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have detailed the compute workers and reported the running time each
algorithm in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics /t
Answer: [Yes]
Justification:
The research presented in this paper adheres the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have discussed societal impacts in Section 5
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve the development or release of models, data, or technologies that carry high risk of misuse, such as pretrained language models, image generators, or scraped datasets. Consequently, discussions on specific safeguards for such contexts are not applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: As detailed Section 4 and Appendix our manuscript, we have metic- ulously cited all open-source benchmark datasets and baseline methods utilized in our research. Each asset is attributed to its original source. Please note that the benchmark datasets in this paper do not include licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
30

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have included well-documented new assets in submission, which provided an anonymized zip file. These assets are accompanied by comprehensive docu- mentation covering all relevant details such the training procedures, licensing information, and any limitations of the assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
31

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "RdyDovSNvW", "reviewer": "Reviewer_ApdU", "summary": "Graph diffusion iteratively propagates signals through the graph, that are subsequently used for real-world applications like personalized page rank. This paper develops edge-level Differentially Private (DP) guarantees for personalized PageRank using Laplace noise addition. Unlike traditional perturbation-based DP algorithms, the Laplace noise addition is done during the diffusion phase and not added directly to the output. This allows the algorithm to achieve better utility-privacy tradeoffs compared to existing approaches. \n\nThe authors identify the graph diffusion process as a composition of contraction maps and aim to extend the Privacy Amplification by Iteration (PABI), guarantees to the graph setting. To this end, the authors introduce degree-based thresholding of signals to bound distance between coupled diffusions over adjacent graphs. The authors prove the DP guarantees for the general setting of delayed noise injection where, noise is injected into the signals starting from diffusion iteration step “m”. They first bound the L1 norm between the two signals for all < m-th iterations. The Renyi Divergence (RD) between the final signal iterates are then upper bounded by the sum of shift absorption term and a PABI term using the properties of RD and the previous bound. The shift absorption term is finally bounded by the strong composition rule of RD and bounding the shift “h_k” per iteration. The PABI term is bounded by the infinite Wasserstein distance between the coupled iterates using the identity mapping.\n\nThe authors empirically demonstrate the utility gains (NDCG, RECALL) of the algorithm on BlogCatalog, Flickr and TheMarker datasets with respect to two baselines: DP-PUSHFLOWCAP and Edge-Flipping.", "questions": "1. Since Theorem B.1. holds for any “m”, have you observed the utility privacy tradeoffs for different “m” values? Specifically are there any advantages to performing delayed noise injection instead of starting at m=0?\n\n2. Graph prediction tasks are usually performed over node embeddings. These embeddings are typically generated by graph convolution operators which perform an operation similar to graph diffusion followed by a non-linearity. Is it possible to extend the DP guarantees to node embeddings in such settings? Such a guarantee can possibly extend the results in this paper to more general graph prediction tasks (other than PBR).\n\n3. In the paper titled “GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation” which was referenced in this paper, the authors have conducted a “Resilience Against Privacy Attacks” study in their experimental results to emphasize the resilience of their model against node membership inference attacks. Is it possible to perform similar experiments in this work?", "limitations": "Limitations are addressed.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The algorithm performs Laplace noise injection during the signal diffusion phase, as opposed to output perturbation, resulting in better privacy utility tradeoffs.\n\n2. Develops theoretical guarantees in epsilon-RDP based on tractable hyperparameters.\n\n3. The method guarantees the RD Privacy budget remains bounded w.r.t the number of iterations.", "weaknesses": "1. Edge differential privacy is quite weak. I think the authors should try node differential privacy or atleast some stronger notion of privacy. Just with Edge DP, the privacy guarantee is quite weak.\n\n2. The iterative privacy framework is quite well known since Thakurta et al.'s work. PageRank is well known iterative algorithm. In that sense, the contribution of the paper is limited. I was expecting to see some graph specific insights from either experiments or theory, which I did not find.\n\n3. Since the algorithm is quite generic, can one extend it to learning or inference of a graph neural network?\n\nThe key weaknesses therefore are lack of novelty and impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are deeply grateful to Reviewer ApdU for the comprehensive feedback. Here, we will address these questions.\n\n>Edge DP is weak; consider node DP or stronger privacy notions. (W1)\n\nWe sincerely appreciate your suggestion to explore node-level differential privacy as a potential extension of our work, a direction we agree could indeed enrich the scope of our research, as noted in the \"Societal Impact and Limitations\" section. However, we respectfully emphasize that edge DP still holds significant value within the private graph learning community, as recognized by both Reviewer y6QA and Reviewer sGeR. Furthermore, the previous work [1] most relevant to this work also focuses exclusively on edge DP for personalized Pagerank, underscoring its significance and practical applications. Our study specifically addresses edge DP within the context of graph diffusion.\n\n[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.\n\n>Iterative privacy framework and PageRank are well-known; lacks graph-specific insights. (W2)\n\nWe respectfully disagree with the assessment. Two things being well-known does not mean building a connection between them is well known, let alone the algorithm having to be designed specifically by taking into account the features from both sides. \nFirst and foremost, our main contribution is the first one to introduce Privacy Amplification by Iteration analysis [1] within the graph analysis and graph learning community, to the best of our knowledge, while prior research has predominantly concentrated on optimization [1,2] and sampling [3]. Regarding the work by Thakurta et al., we did not find a work first-authored by Dr. Thakurta and closely related to the iterative privacy framework. We guess Reviewer ApdU might be referring to [1]. However, the applications of PABI to graph diffusion scenarios are not standard and require many specific designs to incorporate graph properties:\n\n(1) The degree-dependent thresholding function design in our work is motivated to achieve better control over edge perturbation. This design definitely involves graph-specific design.\n\n(2) Since graph diffusions propagate in $\\ell_1$ space, we are the first to explore the use of Laplace noise instead of Gaussian noise,  while Laplace noise has seldom been considered in previous PABI analyses. The superiority of our approach is demonstrated in Appendix Figure 9 (Left). This further involves graph-specific consideration.\n\n(3) Most importantly, we propose a novel $\\infty$-Wasserstein distance tracking method, which improves upon previous PABI analyses and significantly tightens our privacy bound (as demonstrated in Figures 3 and 6), thereby making our algorithm actually practical. Additionally, this $\\infty$-Wasserstein distance tracking method is generalizable to other metric spaces and may be of interest for addressing other related problems.\n\n[1] Feldman et al. Privacy amplification by iteration.\n\n[2] Altschuler et al. On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization.\n\n[3] Altschuler et al. Faster high-accuracy log-concave sampling via algorithmic warm starts.\n\n>Can the algorithm be extended to GNN learning/inference? (W3)\n\nYes, our algorithm may be extended to some graph neural networks, such as the private version of SGC [1], where the gradient information does not need to be back propagated through the graph structure. During the training phase, the algorithm can be used to propagate features and generate private node embeddings, which can then be utilized to train a classifier. In the inference phase, applicable to both transductive and inductive settings, these features can be propagated, and the trained classifier can be employed for inference. However, for standard message passing NNs where the nonlinearity requires to backpropagate gradients across graph structures, we cannot use our framework because the backpropagation may leak private information. Note that some recent DP-GNN works such as [2] indeed adopt the framework without gradient  backpropagating over graphs. \n\n[1] Wu et al. Simplifying graph convolutional networks.\n\n[2] Sajadmanesh et al. GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation.\n\n>Utility-privacy trade-offs for different “m” values (Q1)\n\nWe thank the reviewer for this insightful question. When adjusting “$m$” from $0$ to larger values, our algorithm transitions from noisy to noiseless graph diffusion with output perturbation. Our experiments show that noisy iterations generally outperform output perturbation in utility. Slightly delaying noise injection “$m$” leads to minor performance variations (gains or losses) depending on the dataset and privacy requirements. While practitioners can explore different “$m$” values to optimize privacy-utility trade-offs, our results suggest that $m=0$ is already an effective choice for noise injection.\n\n>Can DP guarantees be extended to node embeddings in graph prediction tasks? (Q2)\n\nYes, it is possible to directly extend our analysis to node embeddings with DP guarantees as long as the non-linear graph convolution operators satisfy certain constraints, such as Lipschitzness, and do not involve learnable parameters that require backpropagation through the graph diffusion.\n\n>Can similar privacy tests, like in the GAP paper, be conducted? (Q3)\n\nIn GAP paper, node-level MIA were employed to assess privacy leakage from learnable weights in GNNs under node DP, in scenarios where strong adversaries exploit overfitting to classify members based on GNN confidence. However, our algorithm does not involve a learning model (no learnable weights or data features) while only generating/output graph diffusion vectors, making it improper to be directly tested in GAP paper’s settings. We greatly value the Reviewer’s suggestion on privacy auditing for our algorithm and agree that exploring effective MIA is a promising direction for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ciTb0zTtHE", "reviewer": "Reviewer_sGeR", "summary": "The paper presents a new differentially private personalized PageRank (PPR) algorithm. The paper extends and theoretically analyzes the privacy ampliﬁcation by iterations (PABI) technique applied to a graph diffusion setting. Rigorous theoretical results demonstrate the privacy guarantees achieved by the approach. An experimental evaluation shows that the proposed approach achieves better results than known algorithms", "questions": "- When computing Recall@R and NDCG@R, do you use as a ground truth the rankings computed by the non-private PPR algorithm, like in [20]? \n- Would it be possible to show some theoretical results on how the quality of the diffusion vectors degrades by enhancing the privacy parameters, for some intuitive notion of \"quality\"?", "limitations": "I am not really happy with the discussion of limitations. The required noise to achieve privacy guarantees, as defined in (3), appears to be substantial. Also, as evident from Figure 5, the recall scores are considerably worse compared to the baselines. I want to emphasize that this is not meant as a criticism of the proposed algorithm, it clearly improves upon previous work. But the price that one has to pay for obtaining diffusion vectors with privacy guarantees is a limitation that needs to be acknowledged.", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The considered problem is important as diffusion vectors might be used to reveal the edges in the graph.\n- The proposed technique appears to be interesting.\n- The theoretical results and proof techniques are non-trivial and require in-depth subject knowledge.", "weaknesses": "The paper is extremely difficult to read. I admit I am no expert in the area but, for example, I didn't have a problem following Epasto et al. [20]. The paper is overloaded with advanced mathematical terms and concepts that are never properly defined. Maybe terms like Banach space, the diameter of a convex bounded set, contraction maps, Lipschitz continuous graph diffusions, essential supremum, etc are standard terms for a mathematical paper but, after all, NeurIPS is not a mathematical venue.  Even the $\\infty$-Wasserstein distance is only defined in the appendix. \nThe paper would become much more accessible if the authors provided some intuition above the approach. For example, a paragraph can be devoted to Figure 1, a vanilla version of the main result simplifying some of the terms can be presented, pseudocode of the approach can be added to the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank Reviewer sGeR for appreciating our contributions to the algorithm and corresponding theoretical results. Here, we are to respond to the questions and weaknesses proposed by Reviewer sGeR.\n\n>The paper is difficult to read; consider simplifying terms, and including pseudocode. (W1)\n\nWe sincerely thank Reviewer sGeR for the valuable feedback. To improve the accessibility of the paper, we will make the following adjustments in our revised version: (1) We remove some abstract notations, such as Banach space, and replaced them with specific terms, like the Euclidean space $R^{|\\mathcal{V}|}$. (2) We plan to include definitions, such as Lipschitz continuity, the $\\infty$-Wasserstein distance, in the main text. We will also expand the discussion around Figure 1 and provide additional explanations for our main results in Equation 5, if space allows. (3) We include the pseudocode for our private graph diffusion algorithm along with the corresponding privacy accounting method in the appendix.\n\n>Is non-private PPR used as ground truth for Recall@R and NDCG@R, like in [20]? (Q1)\n\nYes, in our experiments, we use the rankings computed by the non-private PPR algorithm as the ground truth, consistent with the baseline approach described in [20].\n\n\n>Possible to measure utility degradation with increased privacy? (Q2)\n\nWe appreciate Reviewer sGeR's insightful question. In the privacy literature, algorithms are typically developed to meet specific privacy requirements and are often validated empirically, as seen in works like [1]. Specifically, while addressing worst-case scenarios under privacy constraints is crucial, necessitating theoretical proofs, the utility of these methods is generally assessed through empirical evaluation. That being said, we acknowledge that in some cases, worst-case utility can also be significant. While our current work emphasizes empirical evaluation, we recognize the importance of exploring the theoretical relationship between privacy parameters and the quality degradation of noisy diffusion vectors—such as in terms of approximation error [2,3]. This exploration is planned as a direction for our future research, which could enhance understanding of how increased privacy impacts the quality of diffusion vectors and ensure robustness in more challenging scenarios.\n\n[1] Abadi et al. Deep learning with differential privacy.\n\n[2] Andersen et al. Using pagerank to locally partition a graph.\n\n[3] Hou et al. Massively parallel algorithms for personalized pagerank.\n\n>Discussion of limitations.(L1)\n\nThanks Reviewer sGeR for pointing this out. We fully acknowledge that privacy is not without cost, and this phenomenon is commonly referred to as privacy-utility trade-offs. Our experiments (Fig. 4 & 5) demonstrate these trade-offs, where enhancing privacy budget $\\epsilon$ results in some degradation of utility. Following your suggestion, we will further emphasize this point in the \"Limitations\" section of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8u3Yl05Lso", "reviewer": "Reviewer_dwyJ", "summary": "The paper titled \"Differentially Private Graph Diffusion with Applications in Personalized PageRanks\" proposes a novel graph diffusion framework that ensures edge-level differential privacy (DP) by injecting Laplace noise into the diffusion process. This framework leverages Privacy Amplification by Iteration (PABI) and introduces a new method for tracking privacy leakage using the ∞-Wasserstein distance. The proposed approach is evaluated in the context of Personalized PageRank (PPR) computation and demonstrates superior performance under stringent privacy conditions compared to existing methods.", "questions": "Generalizability: Can the proposed framework be easily adapted to other types of graph diffusion processes beyond Personalized PageRank? If so, what modifications would be necessary?\n\nScalability: How does the proposed method scale with increasing graph size and complexity? Are there any optimizations or approximations that could improve scalability?\n\nParameter Tuning: How sensitive is the performance of the proposed method to the choice of the noise scale σ and the degree-based thresholding parameter? Are there guidelines for selecting these parameters in practice?", "limitations": "See above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel method for achieving edge-level differential privacy in graph diffusion processes by incorporating Laplace noise and utilizing Privacy Amplification by Iteration (PABI). This approach is innovative and adds to the existing body of knowledge on privacy-preserving graph algorithms.\n\nThe authors provide a thorough theoretical analysis of the privacy guarantees of their method, including a novel ∞-Wasserstein distance tracking method to tighten privacy leakage bounds. This rigorous analysis enhances the credibility and potential impact of the work.\n\nThe application of the proposed framework to Personalized PageRank (PPR) is highly relevant, as PPR is widely used in various real-world applications such as recommendation systems, community detection, and targeted marketing.\n\n The paper includes extensive experiments on real-world datasets (BlogCatalog, Flickr, TheMarker) demonstrating that the proposed method achieves better privacy-utility trade-offs compared to baseline methods, particularly under stringent privacy settings.", "weaknesses": "Complexity of Implementation: The proposed method involves complex theoretical constructs such as PABI and ∞-Wasserstein distance tracking, which may pose challenges for implementation and adoption in practical applications. \n\nSpecific Focus on PPR: While the application to Personalized PageRank is well-justified, the paper's focus on a single type of graph diffusion might limit its generalizability. \n\nScalability Concerns: The scalability of the proposed method, particularly for very large graphs, is not thoroughly addressed. Additional experiments or discussions on the computational efficiency and scalability of the approach would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank Reviewer dwyJ for appreciating the novelty of our method and the corresponding theoretical analysis, and acknowledging the practical importance of the problem we studied. Here, we are to respond to the questions and weaknesses proposed by Reviewer dwyJ.\n\n>Complexity of Implementation. (W1)\n\nWe appreciate the reviewer’s question. Our framework comprises two main components: noisy graph diffusion algorithm and noise calibration. The noisy graph diffusion is straightforward and efficient to implement, involving only thresholding and noise injection after each diffusion step. The noise calibration is derived from our theoretical results (Theorem 1 & 4), which is computed before our graph diffusion algorithm. The efficiency of this part is further discussed in the text following Equation 6. For a given noisy graph diffusion algorithm (with a predefined thresholding function), our noise calibration method only requires the privacy budget to determine the appropriate noise scale, which the algorithm then outputs directly. To facilitate practical use, we will include the pseudocode for both components in the appendix. Additionally, we have released the code for noise calibration, enabling practitioners to apply it directly for effective noise calibration.\n\n>Generalizability to other graph diffusions? (W2 & Q1)\n\nWe thank Reviewer dwyJ for the insightful question. Yes, our framework (Theorem 1) includes broader graph diffusion processes, such as Global PageRanks [1] and Generalized PageRanks [2], with Heat Kernel diffusions [3] as a special case. Additionally, when viewing graph diffusion as a graph operator, our theoretical results can also be applied to graph convolution operators with non-linear transformations, provided these transformations satisfy certain Lipschitz continuity properties and do not require learnable parameters that necessitate backpropagation through the graph diffusion [4]. This approach further paves the way for obtaining edge-level private node embeddings for graph learning scenarios.\n\n[1] Brin et al. The anatomy of a large-scale hypertextual web search engine.\n\n[2] Li et al. Optimizing generalized pagerank methods for seed-expansion community detection.\n\n[3] Chung Fan. The heat kernel as the pagerank of a graph.\n\n[4] Sajadmanesh et al. GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation.\n\n>The scalability of the proposed method. (Q2)\n\nWe appreciate Reviewer dwyJ for raising this important question. In our paper, the largest graph dataset we consider is Flickr, with around 80k nodes and 6 million edges. For comparison, the largest dataset in previous research, Blogcatalog, contains around 10k nodes and 334k edges. We discuss the runtime in Appendix D.2 and Figure 7, where our method demonstrates comparable performance to the most efficient DP-PUSHFLOWCAP [1] method, completing a single trial on the Flickr dataset in under a minute. Specifically, on datasets with nodes ranging from 10k to 80k and edges from 334k to 6 million, our algorithm's runtime increases from 24s to 59s.\n\nOur algorithm consists of two main parts: noise calibration and noisy graph diffusion. Given a specific privacy budget and the thresholding parameter $\\eta$, we first calibrate the noise scale according to Theorem 1 using bisection search (pseudocode will be included in the appendix in the revised version). We then perform graph diffusion followed by a fixed thresholding and noise injection at each step with a complexity of $O$(\\# nodes), which is usually much smaller than $O$(\\# edges). However, we acknowledge that exploring further techniques to enhance scalability could be an interesting direction for future work.\n\n[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.\n\n>Sensitivity of parameters. (Q3)\n\nWe thank Reviewer dwyJ for highlighting this point. In our framework, the degree-based thresholding parameter $\\eta$ is the only parameter that can be tuned, while the noise scale is determined by the privacy budget (illustrated in Theorem 1). In practice, once the privacy budget $\\epsilon$ is set, the noise scale is determined by our theorems for the noisy graph diffusion process. Regarding the degree-based thresholding parameter $\\eta$, we have illustrated its performance sensitivity in Appendix D.3, Figure 8. The results show that our framework is robust to the choice of $\\eta$, with performance remaining stable when $\\eta$ is selected within the range of $10^{-10}$ to $10^{-6}$, consistent with the recommendations in [1]. For practical purposes, we suggest selecting $\\eta$ within this interval.\n\n[1] Epasto et al. Differentially private graph learning via sensitivity-bounded personalized pagerank.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7cOtsKAjbt", "reviewer": "Reviewer_y6QA", "summary": "The authors study the important problem graph learning methods (graph diffusion) with differential privacy. There is limited work in this important problem space (one exception being some work on PPR with DP). The authors present a non-trivial use of the PABI framework which uses Contractive Noisy Iterations to prove differential privacy for a process that adds noise iteratively and applies a contractive function. This is a novel and interesting result that might have impact on a variety of learning problems beyond DP.\nThe authors prove formally privacy guarantees of the method. Then the perform an empirical analysis on real data of moderate size and show that their method exceeds all existing baselines (prior DP PPR paper and trivial edge flipping baseline). \n\nThis paper addresses an important problem with novel and practical ideas showing improvements both theoretically and practically.", "questions": "No question", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Important problem: graph learning with privacy\nNovel algorithmic method that appears to be general enough to have impact on multiple graph problems.\nTheoretical guarantees for privacy\nGood evidence of improving empirically over all prior baselines", "weaknesses": "The paper lacks theoretical lower bounds showing the method is tight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our gratitude to Reviewer y6QA for appreciating our theoretical and practical contributions and supporting the acceptance of this paper. Here, we are to respond to the weaknesses proposed by Reviewer y6QA.\n\n>The paper lacks theoretical lower bounds showing the method is tight. (W1)\n\nThe Reviewer y6QA raises an insightful point. We agree that establishing a privacy lower bound is essential for evaluating the tightness of our framework and identifying areas for improvement. The original PABI analysis on noisy SGD [1] provides an order-tight lower bound by constructing a dataset with zero loss and an adjacent dataset with a bias introduced by a differing data sample. The parameter update processes in these adjacent datasets are thus characterized by a symmetric random process and a biased random process. The distinction between these processes is determined by test positivity [1], as one is symmetric and the other is biased. We believe a similar approach could be applied to our graph diffusion analysis, and we plan to explore this in future work.\n\n[1] Altschuler et al. On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the valuable feedback and insightful comments from all our reviewers. All reviewers recognize the significance of the problem we are addressing. Our work has contributed novel theoretical insights coupled with comprehensive empirical evaluations, which were particularly appreciated by Reviewer y6QA, Reviewer dwyJ, and Reviewer sGeR. Some questions remain regarding the generalization of our framework to other types of diffusions and its potential extension to graph neural networks, as well as the sensitivity of the thresholding parameter $\eta$, and the scalability of our algorithm. We are eager to provide further clarifications on these points in the detailed responses to each reviewer below.

Meta-review: While the reviews of the paper varied a lot in their scores, I think the contribution towards the improvement of amplification by iteration in terms of reducing the dependence on diameter is significant. However, I will request the authors to carefully address the concerns regarding the notion of privacy (e.g., edge differential privacy), and other associated concerns regarding the motivation of the problem, in a future version of the paper.
Decision: Accept (poster)