Differentially Private Graph Diffusion with Applications in Personalized PageRanks

Authors: rongzhe  wei
eli  chien
pan  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:41:58

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.

Main paper: 
 introduction: 
 Graph diffusion, characterized by propagating signals across networks, is used in a variety of realworld applications. Variants of graph diffusion such as PageRank [1] and heat kernel diffusion [2] has revolutionized the domains such as web searching [3] , community detection [4] [5] [6] [7] , network analysis [8, 9] and advancements in graph neural networks [10] [11] [12] [13] . Despite their widespread applications, directly releasing diffusion vectors can inadvertently leak sensitive graph information and raise privacy concerns. Hoskins et al. [14] demonstrate that the access to a small subset of random walk-based similarities (e.g., commute times, personalized PageRank scores) could disclose significant portions of network's edges, a phenomenon known as link disclosure [15] . Such attacks, for instance, may enable advertisers to deploy invasive advertising tactics [16] or reveal sensitive transaction information within financial networks [17] . Consequently, it becomes critically important to design graph diffusion algorithms with privacy safeguards. Differential privacy (DP) is recognized as a gold standard used for characterizing the privacy risk of data processing algorithms [18] . However, the inherently interconnected nature of graph-structured data renders the adaptation of DP to graphs non-trivial [19] . Previous studies often conduct the analysis of output sensitivity and adopt output perturbation to keep graph data private, which include the study on differentially private personalized PageRanks (PPRs) [20] , and other relevant graph algorithms such as max flow-min cut [21] , graph sparsification [22] , spectral analysis [23, 24] . However, output perturbation-based approaches often provide a less-than-ideal utility-privacy tradeoff. Numerous studies suggest that incorporating noise during the process, rather than at the output, can potentially enhance utility-privacy tradeoffs [25] .In this work, we introduce a graph diffusion framework that ensures edge-level DP guarantees based on noisy diffusion iterates. Our framework is the first to incorporate privacy amplification by iterations (PABI) technique [26] into graph diffusions. As graph diffusion can be viewed as iterating contraction maps in ℓ 1 space, we adopt per-iterate Laplace noise due to its better performance than the Gaussian mechanism commonly adopted in previous PABI frameworks and provide new analysis dedicated to Laplace noise. We also propose a novel ∞-Wasserstein distance tracking analysis that can tighten the state-of-the-art PABI bound [27] that relies on the space diameter, which makes the bound valid for practical usage. Noticing diffusion from low-degree nodes may introduce high sensitivity, our framework also also proposes a theory-informed degree-based thresholding function at each step diffusion to improve the utility-privacy tradeoff. Lastly, we specialize our framework in the computation of PPR for node ranking tasks. Extensive experiments reveal the advantages of our framework over baselines, especially under stringent privacy requirements.Extensive research has been dedicated to privacy protection within graphs, specifically in the release of graph statistics and structures under DP guarantees [28, 29] . The primary techniques to safeguard graph structures involve the Laplace and exponential mechanisms [30] . Early contributions by Nissim et al. [31] calibrated noise based on the smooth sensitivity of graph queries, expanding beyond output perturbation. Karwa et al. [32] improved the efficiency of privacy-preserving subgraph-counting queries by calibrating Laplace noise according to smooth sensitivity. Different from these methods, Zhang et al. [33] employed the exponential mechanism [34] to enhance privacy protections. Concurrently, Hay et al. [35] developed a constraint-based inference algorithm as a post-processing step to improve the quality of degree sequences derived from output perturbation mechanisms. Further, Kasiviswanathan et al. [36] used a top-down degree projection technique to limit the maximum degree in graphs, thus controlling the sensitivity of degree sequence queries. Additional efforts in privately releasing graph statistics include outlinks [37] , cluster coefficients [38] , graph eigenvectors [39] , and edge weights [40] .In the realm of graph diffusion, the most related work to ours is by Epasto et al. [20] , which focuses on releasing the PPR vector using forward push [41] and Laplace output perturbation. Some studies have shown that injecting noise during the process may offer better privacy-utility trade-offs compared to output perturbation methods [25] and our study compared with [20] provides another use case. Traditionally, the composition theorem [42] is used to track privacy guarantees for iterative algorithms, but it results in a bound that may diverge with the number of iterations. Recently, the technique of PABI [26, 27] was introduced to strengthen the privacy analysis of adding noise during the process, which demonstrates a non-divergent privacy bound for releasing final results if the iterations adopt contraction maps [27] . This substantially tightens the divergent bound given by the naive application of the DP composition theorem [43, 44] . Our framework also benefits from this advantage and we further adapt Altschuler et al.'s analysis [27] to incorporate the Laplace mechanism and provide a tightened space diameter tracking, which makes the bound practically applicable in the graph diffusion 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] . 
preliminaries: 
 Let G = (V, 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 ∈ {0, 1} n×n , where n denotes the total number of nodes, i.e., n = |V|. By establishing an order for the nodes within the graph, we denote d = [d 1 , d 2 , ..., d n ] T as the degree vector. Additionally, let D = diag(d) and e i signifies the i-th standard basis. We denote L(0, σ) and N (0, σ 2 I) as the zero mean Laplace and Gaussian distributions, respectively. We define the set [n] = {1, 2, . . . , n}, and X i:j , i, j ∈ Z + , i ≤ j as joint couple of (X i , X i+1 , . . . , X j ).Graph Diffusion. First, we introduce the concept of Graph Diffusion D, which is commonly characterized by a series of diffusion map ϕ k defined by the random walk matrix P = AD -1 [6, 12, 47] . Formally, We define the graph diffusion D(s) with the initial seed s asD(s) = lim K→∞ s K = lim K→∞ ϕ K • • • • • ϕ 1 (s), where ϕ k (x) = (γ 1,k P + γ 2,k ) x + γ 3,k s. (1) where s ∈ R |V| is a stochastic vector on the graph, and γ 1,k + γ 2,k + γ 3,k = 1. Let γ max = max k |γ 1,k | + |γ 2,k | denote the Lipschitz constant of the graph diffusion mapping, and γ(1) max = max k |γ 1,k | denote the maximum diffusion coefficient. s K is the diffusion vector at time K. The essence of a diffusion process is to model how an initial vector s propagates through the graph over time. Coefficient γ i,k 's control how different resources contribute to the kth step diffusion. When taking γ 1,k = 1 -γ 3,k = β and γ 2,k = 0, Eq. ( 1) is recognized as the PageRank Diffusion [48] with teleport probability 1 -β. 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 [49] .Personalization. Personalized graph diffusions, tailored to individual nodes or localized neighborhoods, play a 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 [51] . These diffusions are defined by setting the graph diffusion vector s as e i for an individual node or s = i∈S e i /|S| for a neighborhood set S. In this paper, we primarily discuss the single-node case while our analysis can be generalized to a set of seed nodes.Privacy Definition. Differential Privacy (DP) [18, 42] is widely recognized as the standard framework for providing formal privacy guarantees for algorithms that process sensitive data. This framework has further been extended under Rényi divergence [44] . Its principles have been applied to safeguard sensitive structures within graph algorithms, an metric noted as Edge-level Rényi Differential Privacy (RDP). Details on the conversion from RDP to DP are elaborated in App. E. Definition 1 (Edge-level RDP [52, 53] ). A randomized graph algorithm A is (α, ϵ)-edge-level RDP if for any adjacent graphs G, G ′ that differs in a single edge, we haveD α (A(G)∥A(G ′ )) ≤ ϵ, where the Rényi Divergence D α (X∥Y ) = 1 α-1 log E x∼ν µ(x) ν(x) α with X ∼ µ, Y ∼ ν.More practical cases find that the seed node (user) of personalized graph diffusion algorithms is already aware of their direct connections within the network, such as one's friend list in social networks, and one's transaction record in financial networks, and therefore protecting the edges directly attached to the seed node becomes unnecessary. Instead, the focus of privacy protection shifts towards obscuring the connections between the remaining nodes. To address this specific need, we follow the previous study [20] and introduce Personalized Edge-level RDP. Definition 2 (Personalized Edge-level RDP [20, 54] ). Consider a graph G and a personalized graph algorithm A. The algorithm A satisfies personalized (α, ϵ)-edge-level RDP if for any node v as the seed node in G, and for any graph G ′ adjacent to G differing by one edge not incident to v, we haveD α (A(G, v)∥A(G ′ , v)) ≤ ϵ. 
methodology: 
 This study centers on a category of γ max < 1 Lipschitz continuous graph diffusions, encompassing prevalent techniques such as PageRank [1] and PPR [55] . It is noted that each diffusion map ϕ k within graph diffusion maintains the total mass of the diffusion vector s k , owing to the condition i∈ [3] γ i,k = 1 and the property of the random walk matrix P being a left stochastic matrix. This observation entails that the diffusion map ϕ k in Eq. ( 1) constitutes a strictly contraction map in the metric space (R |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 diffusion steps can provide improved utility-privacy trade-offs compared to output perturbation alone [25] . This insight serves as a key motivation for employing PABI to establish privacy-preserving graph diffusion.The technique of Privacy Amplification by Iteration (PABI), originally introduced by Feldman et al. [26] for convex risk minimization problems via noisy gradient descent, bounds the privacy loss of an iterative algorithm without releasing the full sequence of iterates. This approach applies to processes generated by Contractive Noisy Iteration (CNI) defined as follows.Definition 3 (Contractive Noisy Iteration (CNI) [26] ). Consider a Banach space (X , ∥ • ∥) with an initial random state X 0 ∈ X , a series of contractions (i.e., c-Lipschitz functions, c ≤ 1) ψ k : X → X , and a sequence of noise random variables {ξ k }. Defining B as a convex bounded set, the Contractive Noisy Iteration CNI(X 0 , {ψ k }, {ξ k }, B) is governed by the update rule:EQUATION)where P B is the projection operator onto B, respecting the norm ∥ • ∥.In the PABI analysis by Feldman et al. [26] , gradient descent is conceptualized as a contractive mapping ψ t in the ℓ 2 space. Leveraging an additive Gaussian noise mechanism after each iteration, i.e., ξ k ∼ N (0, σ 2 I), leads to the observation that the Rényi divergence of identical CNIs with differing initial conditions X 0 and X ′ 0 decays inversely with respect to the total number of iterationsK. Specifically, it is observed that D α (X K ∥X ′ K ) ≤ α∥X0-X ′ 0 ∥2 2Kσ 2. Altschuler et al. [27] further extended this framework with improved bound as follows:EQUATION)The bound in Eq. ( 3) demonstrates that the Rényi divergence between two CNIs can be quantified by the cumulative Rényi divergence over Gaussian noise with a distortion factor ρ (the Distortion Absorption term), complemented by a PABI term. The latter indicates that identical contractive transformations applied to bounded processes reduce privacy leakage in an exponential manner. Note that the bound in Eq. ( 3) is convex with respect to τ , optimized selection of τ leads to non-divergent upper bound ρ(ln(D 2 /ρ) + 1) where ρ = ρ 2 /2 ln(1/c).Note on Parameter Set Diameter D. The privacy bound in Eq. (3) relies on the assumption of bounded diameter D of the parameter set B to upper bound ∞-Wasserstein distance (definition in App. A) 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 ∞-Wasserstein distance tracking method that circumvents the need for the diameter parameter in Lemma 3 (detailed later): A high-level idea is to track the ∞-Wasserstein distance between noisy iterates via constructed couplings instead of using the default set diameter as an upper bound.Note on Noise Random Variables ξ k . The traditional PABI analysis primarily examines gradient descent within the ℓ 2 space employing the Gaussian mechanism. In contrast, in the context of graph diffusions, modifications to Proposition 1 are necessary to accommodate the ℓ 1 norm and the application of Laplace noise. This adaptation to the Laplace mechanism, crucial for the graph diffusion applications, has not been previously addressed in the literature to our knowledge.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 D = {ϕ k } ∞ k=1 , we introduce a noisy graph diffusion D K,σ where K denotes the diffusion steps and σ is the standard deviation of the added noise, constructed by a series of composing noisy graph diffusion mappings ϕ k,σ :D K,σ = ϕ K,σ • ϕ K-1,σ • • • • • ϕ 1,σ , where ϕ k,σ (s k-1 ) = ϕ k (f (s k-1 )) + ξ (1) k + ξ (2) k . (4)where f is a graph-dependent degree-based function set as f (x) = min(max(x, -η • d), η • d) with a threshold parameter η to balance privacy-utility trade-off. Specifically, f clips the values of the diffusion vector according to node degrees. Notably, the thresholding function f allows for negative signals, capturing scenarios where the diffusion coefficient γ 1,k can be negative. Noise variables ξ (1) k and ξ (2) k are independently sampled from a Laplace distribution L(0, σ). 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 ℓ 1 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 a bounded distance between the coupled diffusions over two adjacent graphs, analogous to the role of the general projection operator P B in the standard CNI as defined in Eq. (2) . Such a bounding effect is also crucial for the later analysis of ∞-Wasserstein distance tracking in Lemma 3. Secondly, and more critically, our theoretical analysis reveals that edge perturbation affecting low-degree nodes results in increased distortion at each diffusion step (illustrated in Fig. 1 ). Uniform thresholding coupled with randomness injection for all nodes typically yields suboptimal performance in such cases. Our degree-dependent design naturally controls the distortion per iteration caused by low-degree nodes which helps with reducing the added noise. More detailed distortion analysis on f is shown later in Lemma 2. The threshold parameter η is commonly employed to optimize the privacy-utility trade-off in practical applications [20] . The empirical benefits of f are explored in experiments detailed in Sec. 4.2.Discussion on Dual Noise Injection. Our framework employs a noise-splitting technique, injecting dual Laplace noise at each diffusion step to construct non-divergent privacy bounds, as outlined in Eq. (3) . Theoretical justifications for this design is provided in the proof sketch.Following this, we present our main result on the privacy guarantee of noisy graph diffusion: Theorem 1 (Privacy Guarantees of Noisy Graph Diffusions). Given a graph G, an associate graph diffusion D = {ϕ k } ∞ k=1 , then noisy graph diffusion mechanism D K,σ ensures edge-level (α, ϵ)-RDP with ϵ satisfies:EQUATION)whereg α (σ, ρ) = 1 α-1 ln( α 2α-1 exp( α-1 σ ρ) + α-1 2α-1 exp(-α σ ρ))denotes the Rényi divergence induced by the Laplace mechanism [44] , and ρ diff = max(4γ(1)max , 2γ max ) • η represents the maximum single-step distortion incurred by diffusion on adjacent graphs that involves Lipschitz continuity coefficient γ max , and maximum diffusion coefficient γEQUATION)The privacy bound in Eq. ( 5) consists of two components: the distortion absorption term (the first term on the RHS) and the PABI term (the second term in RHS). Distortion absorption quantifies the cumulative Rényi divergence over Laplace noise with single-step distortion ρ diff , while the PABI term quantifies the exponential decay rate, echoing the result in Eq. (3). However, a key difference lies in our approach; instead of leveraging the projected set diameter D to control the distance between coupled CNIs, our proposed ∞-Wasserstein tracking method yields a more practical term,ρdiff•(1-γ τ max ) 1-γmax. Further details and utility evaluations of this tool are presented in the proof sketch and Sec. 4.2, respectively. The function g α (σ, ρ), which measures Rényi divergence for the Laplace mechanism, increases with distortion ρ 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 ϵ, we calculate the two terms in Eq. ( 5) for each τ . Leveraging the monotonicity of g α (σ, ρ), we employ a binary search to identify the appropriate noise scale σ. The optimal noise scale is then determined by selecting the minimum value across various τ values, achieving this efficiently with linear complexity relative to τ .It is important to note that the maximum single-step distortion ρ diff in Eq. ( 5) is tight and conveys several messages. First, as defined in Eq. ( 1), when the diffusion process is relatively slow (i.e., γ 1,k < γ 2,k ), the distortion remains tight, governed by the Lipschitz constant γ max of the diffusion mapping. In contrast, when the diffusion is relatively fast (i.e., γ 1,k ≥ γ 2,k ), the distortion bound becomes asymptotically tight, depending on graph structures, with worst-case scenarios detailed in App. B.1. In Eq. ( 6), we demonstrate the convergence of the privacy budget with respect to diffusion steps K. This approach differs from the adaptive composition theorem [42] , which analyzes how privacy guarantees degrade when composed mechanisms are applied. Although this method has commonly been employed to protect privacy in graph learning models [52, 53, 56] , it leads to a linear increase in the privacy budget with the number of iterations K under Rényi divergence [44] , potentially resulting in unbounded losses as K grows to infinity. More importantly, even for a small number of diffusion steps, our framework achieves a significantly better privacy budget under practical PPR diffusion settings, as illustrated in Fig. 2 . Further empirical evaluations are detailed in App. D.4.Proof Idea. Similar to Eq. (3), the privacy loss of adjacent graph diffusion processes can be bounded as the sum of distortion absorption term incurred by Laplace noise and a PABI term at intermediate step τ (Step 1 & 2). Subsequently, we explore degree-based thresholding to manage distortion, achieving a superior utility-privacy tradeoff (Step 3), and introduce ∞-Wasserstein distance tracking to further tighten the divergence at τ (Step 4).Step 1: Interpretation of Iterates as Conditional CNI Sequences. Consider the coupled graph diffusionsD = {ϕ k } ∞ k=1 and D ′ = {ϕ ′ k } ∞ k=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:s k = ϕ k (f (s k-1 )) + ξ (1) k Identical CNI +ξ (2) k , s ′ k = ϕ ′ k (f ′ (s ′ k-1 )) + ξ ′(1) k + ξ ′(2) k d = ϕ k (f (s ′ k-1 )) + ξ ′(1) k Identical CNI + ξ′(2) k .where ξEQUATIONk , ξ′(1) k , ξ ′(2) k ∼ L(0, σ), and ξ′(2) k ∼ L ϕ ′ k (f ′ (s ′ k-1 )) -ϕ k (f (s ′ k-1)), σ , andd = denotes equality in distribution. When the distortion ϕ ′ k (f ′ (s ′ k-1 )) -ϕ k (f (s ′ k-1 )) is absorbed by the conditional event of noise variables, i.e., ξ(2) k = ξ(2)k , the coupled diffusion vectors evolve with identical CNIs through the contractive mapping ϕ k • f . Note that the Laplace distribution is essential for fully exploiting ℓ 1 distortion in our analysis.Step 2: Bounding Privacy Loss through Distortion Absorption and PABI. The privacy loss of coupled iterates D α (s K ∥s ′ K ) can be bounded by the distortion from graph diffusion, and PABI:EQUATIONThis inequality arises from leveraging the post-processing and strong composition rules of Rényi divergence. Here, ζ represents a joint noise realization, and the parameter τ is introduced to balance the privacy leakage from the two terms -the divergence between the shifted noise variables accumulated from step τ + 1 to step K (Distortion Absorption), and the divergence across conditional CNIs employing identical transformations ϕ k • f (PABI).Step 3: Bounding Distortion Absorption Lemma 2 (Absorption of Distortion in Laplace Distribution). For any τ ∈ {0, 1, ..., K -1}, we haveEQUATIONEQUATIONHere, ρ quantifies the maximum distortion introduced by a single-step diffusion and is determined by the thresholding function f normalized by node degrees, i.e., [f (s k )]i di .The observation on ρ highlights the importance of a degree-based design for the thresholding function f . Uniform thresholding across all nodes results in distortion proportional to 1 dmin , 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, ρ is tightly bounded byρ diff = max(4γ (1) max , 2γ max ) • η. 10 -5 10 -4 10 -3 10 -2Threshold (η) Setting: Graph Diffusion with γ 1,k = 0.8, γ 2,k = 0, γ 3,k = 0.2.Step 4: Upper Bounding PABI with ∞-Wasserstein distance tracking. To perform tight privacy analysis for the second term in Eq. ( 7), we develop a novel ∞-Wasserstein distance tracking method for coupled CNIs, where we denote the ∞-Wasserstein distance at step τ by w τ . This method discards the original boundedness condition in PABI (Eq. (3) Second Term), which relies on the diameter D.Given two coupled graph diffusions mentioned above, for any τ ∈ {0, 1, ..., K -1}, any noise realization ζ, we have(2)τ +1:K = ζ∥s ′ K | ξ′(2) τ +1:K = ζ) ≤ gα(σ, γ K-τ max wτ ) (9)where the tracked ∞-Wasserstein distance over coupled CNIs is given byw τ = ρdiff•(1-γ τ max ) 1-γmaxand is naturally upper bounded by ρdiff 1-γmax := w.We argue that using w τ (or the upper bound w) instead of the default diameter D is crucial to make the algorithm practically useful. There is no numerical evaluation in the previous study [27] . Numerical comparison between w and the diameter of thresholding function D = η • |V| i=1 d i , using the real-world BlogCatalog dataset (detailed in Sec. 4), is illustrated in Fig. 3 . w achieves orders-ofmagnitude improvement, which is still significant even if D impacts privacy loss via a logarithmic term. Further empirical validations demonstrating significant utility improvements are detailed in Sec. 4.2.By substituting the bounds from Eq. ( 8) and Eq. ( 9) into Eq. ( 7), we establish Theorem 1.In practice, graph diffusions often originate from a single node e i , 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: [ d] i can be set to any positive threshold, i.e., no 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:f (x) = min(max(x, -η • d), η • d), where [ d] j = [d] j for j ̸ = i andEQUATION)where denote indicator function.Note that a 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 a prevalent node proximity metric extensively used in graph mining and network analysis. We may apply our noisy diffusion framework to PPR diffusion. We consider PPR with lazy random walk as follows:EQUATION)where lazy random walk matrix W = 1 2 (P + I) and (1 -β) represents teleport probability with β ∈ (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 4 with ρ diff = 2βη and γ max = β. Note that, since γ j,k > 0 for all j ∈ {1, 2, 3} in PPR scenarios, all signals propagating among nodes should be non-negative. Consequently, the degree-based thresholding function f can be further modified asf (x) = min(max(x, 0), η • d). 
experiments: 
 In this section, we present empirical evaluations to support our theoretical findings. Specifically, we apply the widely-used PPR algorithm (Sec. 3.4) to real-world graphs. We focus on the accuracy of noisy PPR in ranking tasks under personalized edge-level DP due to its practicality as noted in [20] .Benchmark Datasets. We conduct experiments on the following datasets: BlogCatalog [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 mechanism [42] on the adjacency matrix, excluding seed node-connected edges in personalized scenarios. Entries are replaced with values in {0, 1} uniformly at random with probability p (detailed in App. E), or retained otherwise. This method requires O(|V| 2 ) time to generate a private adjacency matrix and increases its edge density, which limits its practicality. Both our approach and DP-PUSHFLOWCAP offer better scalability. A comparison of running times between different approaches is provided in App. D.2. In all experiments, we only report results if a single trial can be completed within 12 hours on an AMD EPYC 7763 64-Core Processor, and thus Edge-Flipping cannot be run on Flickr.Metrics. For utility, we employ two ranking-based metrics: normalized discounted cumulative gain at R (NDCG@R) and Recall@R [59] , where R denotes the cutoff point for the top-ranked items in the list. In our experiments, R is set to 100. For privacy assessments, we utilize the personalized edge-level (ϵ, δ)-DP, with δ set to 1 #edges following [53] . To ensure a fair comparison, both DP-PUSHFLOWCAP and Edge-Flipping are analyzed using RDP. The privacy budgets for all methods are subsequently converted to DP from RDP results, as elaborated in App. E. All results are reported as averages over 100 independent trials, with 95% confidence intervals.In this series of experiments, we aim to assess the ranking performance of our noisy graph diffusion (as delineated in Sec. 3.4) compared with baselines on real-world graphs. We specifically examine privacy budget ϵ ranging from 10 -2 to 1, PPR with parameter β = 0.8. Considering that both our approach and DP-PUSHFLOWCAP employ a thresholding parameter η to balance the privacy-utility trade-off, we select η from a set of seven values spanning orders of magnitude from 10 -10 to 10 -4 , a range empirically determined to be optimal across various datasets for both methods (η = 10 -6 is chosen for DP-PUSHFLOWCAP in [20] ). For each experiment, we randomly choose an initial seed for diffusion and execute PPR for 100 iterations following [20] . We report the average NDCG@100 score and Recall@100 compared to the standard noise-free PPR diffusion (Eq. ( 11)) over 100 independent trials in Fig. 4 and Fig. 5 respectively. Results for NDCG@100. As illustrated in Fig. 4 , our noisy graph diffusion surpasses both baselines across all three datasets, where values below 0.7 are ignored. In a strong privacy regime (ϵ ≤ 0.5), our approach demonstrates significant improvement over DP-PUSHFLOWCAP, which relies on output perturbation. This validates our claim that a noisy process achieves a superior privacy-utility tradeoff in stringent privacy settings.Results for Recall@100. Fig. 5 illustrates the overlap of the top-100 predictions of privacypreserving 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. Additional experiments on the sensitivity of ranking performance over variations in η are deferred to App. D.3, which demonstrate that our approach is significantly more robust on the choice of the hyperparameter η.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 ∞-Wasserstein distance tracking tool. Experiments were conducted on BlogCatalog, utilizing PPR diffusion with parameter β = 0.8, and a total of K = 100 diffusion steps. Additional ablation studies focusing on variations in noise type and comparative analyses of noise scales across different methods are detailed in App. D.4.Tracking. We evaluate the effectiveness of our graph-dependent thresholding function f and ∞-Wasserstein distance tracking. We vary η uniformly across seven discrete values in from 10 -4 to 10 -10 and report the optimal performance for all methods in Fig. 6 . Firstly, we compare the degreebased thresholding functionf (s) = min(max(x, 0), η • d) (Red •) against its graph-independent variant f (s) = min(max(x, 0), η • 1) (Red ×), which uniformly clips over nodes regardless of their degree. As ϵ varies from 0.1 to 3, the degree-based thresholding function consistently outperforms its graph-independent counterpart, with a 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 a diameter η|V| (2η|E|), respectively, which can be utilized in the modification of Theorem 1 for privacy accounting. However, the graph dependent thresholding function f results in a significantly larger diameter, which substantially degrades utility. This underscores the importance of leveraging ∞-Wasserstein tracking.We showcase the benefits of our ∞-Wasserstein distance tracking analysis (Red Lines) on the privacy-utility tradeoff against diameter induced bounds derived from ℓ 1 projection (Green Lines) or thresholding function-induced diameter (Blue Lines). The privacy bound of the ℓ 1 projection is established based on a Laplace modification of Eq. ( 3) with a diameter of 1. As shown in Fig. 6 , methods employing ∞-Wasserstein distance tracking analysis consistently outperform those based on ℓ 1 projection and thresholding-induced diameter. We conclude that our ∞-Wasserstein tracking analysis and the design of graph-dependent thresholding function f markedly enhance the privacyutility tradeoff.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We have uploaded our code in supplementary file. All information to reproduce the main experimental results are discussed in Section 4 and Appendix D. 
conclusion: 
 In summary, we introduce a noisy graph diffusion framework for edge-level privacy protection, utilizing a novel application of PABI in ℓ 1 space. By incorporating a theory-guided design for a graph-dependent thresholding function and employing a new ∞-Wasserstein distance tracking tool, we outperform SOTA methods in ranking performance on benchmark graph datasets.Societal Impact and Limitations. Our work advances the development of DP graph algorithms, offering strong privacy protection when properly implemented. For its limitations, we refer readers to standard textbooks on the subject [42] . The effectiveness of our noisy graph diffusion framework has been demonstrated primarily in the context of PPR diffusion. Extending these results to other types of graph diffusions, such as heat kernel diffusion, is a promising direction for future research. This paper focuses on edge-level privacy protections; exploring extensions to node-level DP protections could further broaden the scope of our research.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 and 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our work does not involve the development or release of models, data, or technologies that carry a 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 a 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 to 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes]Justification: As detailed in Section 4 and Appendix D of our manuscript, we have meticulously 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-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 creators. 
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 our submission, which are provided in an anonymized zip file. These assets are accompanied by comprehensive documentation covering all relevant details such as the training procedures, licensing information, and any limitations of the assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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 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 we expect authors to adhere to 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. 
 
 Appendix: In this section, definitions and lemmas are introduced to facilitate the presentation of proofs. Recall that the contraction mapping denote a self-mapping l-Lipschitz continuous function with l ∈ [0, 1], and the ∞-Wasserstein distance is defined as W ∞ (µ, ν) = inf γ∈Γ(µ,ν) ess sup (x,y)∼γ ∥x-y∥, where Γ(µ, ν) represents the collection of all couplings between µ and ν. Further, define R α (σ, ρ) := sup r:∥r∥≤ρ D α (ξ+r∥ξ), where ξ ∼ L(0, σ), measures the extent to which the Laplacian distribution can absorb shifts of magnitude ρ. For clarity, D α (µ∥ν) and D α (X∥Y ), with X ∼ µ and Y ∼ ν, are used interchangeably when the context is clear. Besides, we denote X i:j , i, j ∈ Z + , i ≤ j as joint couple of (X i , X i+1 , . . . , X j ). We introduce Shifted Rényi Divergence as follows: Definition A.1 (Shifted Rényi Divergence). Let µ and ν be distributions defined over a Banach space (X , ∥ • ∥). For parameter z ≥ 0 and α ≥ 1, the z-shifted Rényi divergence between µ and ν is defined asEQUATION)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 µ, ν, ϱ be probability distributions on R n . For any ρ ≥ 0,EQUATION)Lemma A.2 (Contraction-reduction lemma [27] ). Suppose ψ, ψ ′ are random functions from R n to R n such that (i) each is a strict c-contraction almost surely, and (ii) there exists a coupling of (ψ, ψ ′ ) under which sup x ∥ψ(x) -ψ ′ (x)∥ ≤ ρ almost surely. Then for any probability distributions µ and ν on R n ,EQUATIONFurther, we recall two properties of RDP in our analysis. Lemma A.3 (Post-processing Property of Rényi Divergence). For any Rényi parameter α ≥ 1, any random function f , and any probability measures µ, ν, we haveEQUATIONLemma A.4 (Strong composition for RDP). For any Rényi parameter α ≥ 1, and any two sequences of random variables X 1 , . . . , X k and Y 1 , . . . , Y k ,D α (P X 1:k ∥P Y 1:k ) ≤ k i=1 sup D α (P Xi|Xi-1=xi-1 ∥P Yi|Yi-1=xi-1 ).In this section, we present the main proof for the results in Theorem 1 as detailed in Sec. 3.Proof of Theorem 1. Given a seed s, a total diffusion step K, a noise scale σ, and degree-based thresholding functions f, f ′ , we consider two coupled graph diffusions D K,σ (s), D ′ K,σ (s) which propogate on two joint edge-level adjacent graphs G, G ′ respectively with diffusion mappingEQUATION)EQUATIONEQUATION)where ξ(1)k , ξ ′(1) k , ξ (2) k , ξ ′(2) kare distributed according to the law L(0, σ).Step 1: Distortion of Single-Step Graph Diffusion In each diffusion step, a distortion over the diffusion mappings ϕ k • f is introduced due to the graph adjacency between the graph diffusions D K,σ (s) and D ′ K,σ (s). This distortion, which is crucial for the subsequent analysis, is characterized by the following lemma: EQUATION)where Lipschitz constantγ max = max k |γ 1,k | + |γ 2,k |, and maximum diffusion coefficient γ (1) max = max k |γ 1,k |.We denote this single-step graph diffusion distortion bound as ρ diff , i.e., ρ diff = max(4γ(1) max , 2γ max )•η.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., γ 1,k < γ 2,k , the distortion 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,k . In this latter scenario, the bound becomes asymptotically tight when the graph structure satisfies 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 ). Step 3: Bounding the Privacy Loss via Shift Absorption and PABI. 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 at intermediate steps. For k ≥ 1, drawing upon the noise-splitting approach outlined in [27] , we mitigate the shifts caused by diffusion and thresholding by integrating these factors into the noise distribution. Consequently, we construct conditional CNI sequences with identical diffusion mappings for both processes. Specifically, we reformulate the diffusion process D ′ K,Π (s) as follows:EQUATIONwhere we introduce ξ′(2) k as shifted Laplacian noise and noise scale σ k = σ. Therefore, the coupled graph diffusion processes can be summarized as follows:EQUATIONNote that our objective is to establish an upper bound for D α (s K ∥s ′ K ), we claim that for any parameter τ ∈ {0, 1, ..., K -1},EQUATIONEQUATIONEQUATION)where ζ τ +1:K is a noise realization, (a) is by the post-processing inequality of Rényi Divergence (Lemma A.3), and (b) is from the strong composition rule for Rényi divergence (Lemma A.4).As demonstrated in Eq. 23, the privacy leakage can be upper bounded by the Rényi divergence across joint Laplacian distributions with a shift (shift absorption term) and the divergence across conditional CNIs employing identical transformations ϕ k • 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. It is important to emphasize that, for the latter, we leverage ∞-Wasserstein distance tracking method that get rid of the diameter requirement in original PABI analysis.(1) Upper bounding shift absorption term: Lemma B.2 (Absorption of Shift in Laplacian Distribution). Given two coupled graph diffusions mentioned above, for any τ ≥ 0, the shift absorption term can be upper bounded byEQUATIONEQUATIONwhere distortion ρ diff = max(4γmax , 2γ max ) • η, and shifted Laplace functiong α (σ, ρ) = 1 α-1 ln( α 2α-1 exp( α-1 σ ρ) + α-1 2α-1 exp(-α σ ρ)).(2) Upper bounding PABI term:Lemma B.3 (PABI with Laplacian Distribution). Given two coupled graph diffusions mentioned above, for any τ ≥ 0, we haveEQUATIONThe lemma demonstrates that the PABI term is controlled by the shifted Rényi divergence at step τ and a privacy amplification term that decays exponentially at a rate of γ K-τ max w τ . In previous analyses of the PABI for the Gaussian mechanism, [27] utilized the diameter of the bounded parameter set to further constrain the shift w τ . However, we have found that this bound does not satisfactorily achieve a favorable privacy-utility trade-off in practice. Subsequently, we develop a ∞-Wasserstein distance tracking method to more effectively bound this PABI term, offering a more practical approach.Lemma B.4 (PABI with ∞-Wasserstein Distance Tracking). Given two coupled graph diffusions mentioned above, for any τ ≥ 0, we haveEQUATIONwhere distortion ρ diff = max(4γmax , 2γ max ) • η. By summarizing the above results (Lemma B.2, B.3, and B.4), we conclude the final results:EQUATIONEQUATIONEQUATIONAs discussed in Sec. 3.4, in many personalized scenarios, the definition of personalized edge-level privacy shifts to protect edges that are not incident to the source node. This adjustment offers additional benefits in distortion analysis (Lemma B.1): no distortion occurs in the first step. According to the proof of Lemma B.1, given a seed node s with the corresponding initial vector s, and letting (u, v) denote the edge differing on adjacent graphs G and G ′ where s / ∈ {u, v}, we have:∥(AD -1 -A ′ D ′-1 )s∥ 1 ≤ 2 [s] u d u + [s] v d v = 0 (29) since [s] u = [s] v = 0.Thus, when analyzing noisy graph diffusion in 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, we obtain the corresponding results in Theorem 4:EQUATIONAs mentioned in Section 4, this paper includes three benchmark datasets: BlogCatalog, TheMarker, and Flickr. Their details are included in Table 1 .Nodes 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).We report the running time for a single trial of each method across all datasets in Fig. 8 . As illustrated in the figure, all single trial experiments of our method and DP-PUSHFLOWCAP are completed within 1 minute. In contrast, the edgeflipping mechanism exhibits significantly longer running times, ranging from 16 minutes to over 12 hours as the size of the graph increases. In this series of experiments, we further investigate the sensitivity of the NDCG ranking performance with respect to the selection of η. Specifically, we enhance the granularity of the η values within the existing range from 1 × 10 -10 to 1 × 10 -4 by selecting 20 equidistant points for each dataset within this interval. The NDCG ranking performance is depicted in Fig. 9 . The left column represents the transition curve of our method, the middle column denotes the performance of DP-PUSHFLOWCAP, and the right column illustrates the performance gap between the two methods. For each privacy budget ϵ, we highlight the optimal η corresponding to the best performance (yellow for our method, cyan for DP-PUSHFLOWCAP). As demonstrated in the right column, when η varies from 1 × 10 -10 to 1 × 10 -4 , our method consistently outperforms DP-PUSHFLOWCAP up to 1 × 10 -6 . This indicates the superior stability of hyperparameter selection for our method in terms of ranking performance. In this section, we conduct additional ablation studies to compare the noise distributions, and noise schedules between our Theorem 1 and the Composition Theorem. Following the experimental settings outlined in Sec. 4.2, we perform experiments on the BlogCatalog dataset, utilizing PPR diffusion with a parameter β = 0.8 and a total of K = 100 diffusion steps.Noise Distributions: Laplace versus Gaussian. We investigate the effectiveness of injecting Laplace noise as compared to Gaussian noise within our analysis framework. Recall that standard PABI analysis has primarily focused on the case of Gaussian noise. We report the ranking performance in Fig. 10 (Left). Within a strong privacy regime where ϵ ranges from 0.1 to 1, the performance gap between the two noise types is approximately 0.05. This finding supports the superiority of Laplace noise injection for graph diffusion processes in ℓ 1 space and is of practical importance.Theorem 1 versus Composition Theorem. As we discussed in Section 3.2, one can naively adopt the DP composition theorem [43, 44] to establish the privacy guarantee for the same noisy graph diffusion. However, it is a general approach and does not take the contraction properties of graph diffusion into account, which leads to a worse privacy bound in our case. We examine the calibrated noise scales σ under edge-level DP, converted from RDP. Figure 10 (Right) compares noise scales derived from our Theorem 1 (Red Line) against those from the standard RDP composition theorem (Blue Line). Our method achieves a noise scale that is 10 times smaller than that required by the composition theorem.First, we present the standard results on converting RDP to DP:Proposition E.1 (Conversion from RDP to DP [44] ). If M is an (α, ϵ RDP )-RDP mechanism, then it also satisfies (ϵ DP , δ)-differential privacy, where ϵ DP = ϵ RDP + log 1 δ α-1 for any δ ∈ (0, 1).To determine the DP guarantees of the three mechanisms, we first calculate the RDP for each mechanism. Specifically, we use Theorem 4 for our method, sensitivity analysis in Theorem 4.3 from [20] with the dimensional Laplace mechanism under Rényi divergence (Eq. ( 46)) for DP-PUSHFLOWCAP, and Proposition 5 from [44] for EdgeFlipping. For all three mechanisms, the expression ϵ RDP +log 1 δ α-1is convex in α. By setting δ = 1 #edges , we then search for the optimal α to minimize this expression and obtain ϵ DP . A ′ = {3, . . . , |A ′ | + 2}, B ′ = {|A ′ | + 3, . . . , |A ′ | + |B ′ | + 2}, and C = {|A ′ | + |B ′ | + 3, . . . , |A ′ | + |B ′ | + |C| + 2}. We adopt the shorthand notation f i = [f (x)] i and ∆f i = [f (x)] i -[f ′ (x)] i .We first consider the case where d 1 , d 2 ≥ 2, and define m 1 := -f1 d1(d1-1) , m 2 := -f2 d2(d2-1) , ∆m 1 := ∆f1 d1-1 , ∆m 2 := ∆f2 d2-1 . Since degree-based thresholding function f is symmetric, WLOG, we can assume f is non-negative, i.e., f (x) = min(max(x, 0), η • d). We have the followingEQUATION)EQUATIONEQUATIONEQUATIONEQUATION(d) ≤ max(4|γ 1,k |, 2(|γ 1,k | + |γ 2,k |)) • η ≤ max(4γ (1) max , 2γ max ) • η (41)where (a) follows from the non-negativity of the function f , and (b) is derived from|A ′ ∩C| = d 1 -1 and |B ′ ∩ C| = d 2 -1.Equality is obtained when C = ∅, i.e., when there are no common neighbors between nodes 1 and 2. (c) is obtained from Result 1 and (d) originates from Result 2.Result 1. Consistent with the above notations, we have f j -d j ∆f j ≥ 0 for j ∈ {1, 2}.Results 2. Consistent with the above notations, we have|γ 1,k |(f ′ j - (dj -2)fj dj ) + |γ 2,k |(f j -f ′ j ) ≤ max(2|γ 1,k |, |γ 1,k | + |γ 2,k |)η for j ∈ {1, 2}.Proof of Result 1. From the above definitions, we havef j = [f (x)] j = min(max(x j , 0), η • d j ) and f j -d j ∆f j = d j f ′ j -(d j -1)f j where x j is the j-th entry of x. Now, consider the following cases:• When x j ≤ 0, we have f j -d j ∆f j = 0.• When x j ∈ (0, (d j -1)η], it follows that f j -d j ∆f j = d j ηx j -(d j -1)ηx j = ηx j ≥ 0. • When x j ∈ ((d j -1)η, d j η], we obtain f j -d j ∆f j = (d j -1)(d j -x j )η 2 ≥ 0. • When x j > d j , f j -d j ∆f j = 0.In conclusion, based on the above cases, the result is proven.Proof of Result 2. We consider different cases:EQUATION• When x j ∈ ((d j -1)η, d j η], we obtainEQUATIONEQUATIONEQUATIONNote 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 to infinity.Additionally, when d 1 = 1 or d 2 = 1, it can be directly shown that the distortion is upper bounded by max(γmax , 2γ max ) • η.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.EQUATIONLemma Proof. With the above result, we can upper bound the Rényi divergence over joint noise distributions. For τ ≥ 0,EQUATIONEQUATIONk |ξ(2)EQUATIONEQUATIONwhere (a) arises from strong composition rule for Rényi divergence (Lemma A.4), (b) is from the definition of ξ(2) k , ξ(2) k with shift h k = (ϕ k • f )(x) -(ϕ ′ k • f ′ )(x), and (c) is derived by combining the results that the ℓ 1 norm of the shift is upper bounded byEQUATIONmax , 2γ max ) (Lemma B.1) and the above Laplace bound under Rényi divergence (Eq. ( 46)) with g α (σ, ρ)= 1 α-1 ln( α 2α-1 exp( α-1 σ ρ) + α-1 2α-1 exp(-α σ ρ diff )).Summarizing the above, we prove the lemma.Proof of Result. Now consider Laplacian distribution, for h ∈ R |V| , let h i denote the i-th entry of the vector, we haveD α (L(0, σ)∥L(h, σ)) (a) = |V| i=1 1 α -1 ln( α 2α -1 exp( α -1 σ |h i |) + α -1 2α -1 exp(- α σ |h i |)) (49)where (a) is from the additivity of Rényi divergence [60] and the Rényi divergence over onedimensional Laplacian noise [61] . By considering the worst case h, we can reformulate the problem as:maximize h |V| i=1 1 α -1 ln( α 2α -1 exp( α -1 σ |h i |) + α -1 2α -1 exp(- α σ |h i |)) (50) s.t. ∥h∥ 1 ≤ ρ (51)For the above optimization problem, letEQUATIONFurther for Hessian matrixEQUATIONEQUATION)From the eigenvalue criterion for positive definiteness,∇ 2 D α (L(0, σ)∥L(h, σ)) ≻ 0, i.e. D α (L(0, σ)∥L(h, σ)) is a convex function.As the feasible set is convex, maximum is obtained on the boundary of feasible set. Thus, the problem can be further formulated as:maximize h |V| i=1 1 α -1 ln( α 2α -1 exp( α -1 σ |h i |) + α -1 2α -1 exp(- α σ |h i |)) s.t. ∥h∥ 1 = ρ (55)Next, we use the adjustment method to solve the above objective methods. First, we defineL(h 1 , h 2 , . . . , h |V| ) = |V| i=1 f (h i )and we fix h 3 , . . . , h |V| . We aim to optimize: maximizeEQUATIONwith respect to h 1 and h 2 , considering the constraints ∥h∥ 1 = ρ. This is equivalent to maximize h1,h2EQUATIONDefine c t = ρ -V i=t h i . Since c 3 is fixed, and h 2 = c 3 -h 1 , the objective function become a univariate function, by calculating the derivativeEQUATIONThe derivative ∂L ∂h1 reaches 0 when h 1 = c3 2 . Furthermore, ∂L ∂h1 < 0 for h 1 < c3 2 , and ∂L ∂h1 > 0 for h 1 > c3 2 . Thus, the maximum value of the function is attained at the endpoints. maximizeEQUATIONAs the function is symmetric, two endpoints attain the same value, i.e. L(c 3 , 0, h 3 , . . . , h |V| ) = L(0, c 3 , h 3 , . . . , h |V| ). Now, we aim to maximize the objective function by each time adjustment two variables and fixed the rest variables unchanged:EQUATIONEQUATIONEQUATIONwhere (a) is from Eq. ( 59), and for each inequality, we adjust the values of h 1 and h i to maximized the objective function while keep the rest variables fixed. From the above reasoning, we maximized the Rényi divergence over two Laplacians with shift.To prove the upper bound of sup ζ τ +1:K D α (s K |ξ(2)τ +1:K = ζ τ +1:K ∥s ′ K | ξ′(2) τ +1:K = ζ τ +1:K ),we mainly leverage the definition of shifted Rényi divergence (Def. A.1) with two properties under noise convolution and contraction mapping (Lemma A.1 and Lemma A.2). Specifically, recall that R α (σ, ρ) = sup r:∥r∥≤ρ D α (ξ + r∥ξ) where ξ ∼ L(0, σ), define φ k = ϕ k • f , for any ζ τ +1:K , defineEQUATIONEQUATIONEQUATIONwhere (a) is from Lemma A.1, and (b) is derived from Lemma A.2 as φ k is γ max -contractive (composition of two contractions). Further, we have               w τ +1 = γ max w τ -a τ +1 w τ +2 = γ max w τ +1 -a τ +2 = γ 2 max w τ -γ max a τ +1 -a τ +2 • • • = • • • w K = γ K-τ max w τ - K-τ -1 k=0 γ k max a K-k (72)By setting a τ +1 = 0, ..., a K-1 = 0, we have a K = γ K-τ max w τ . Therefore, we haveD α (s K |ξ (2) τ +1:K = ζ τ +1:K ∥s ′ K | ξ′(2) τ +1:K = ζ τ +1:K ) ≤ D (wτ ) α (s τ ∥s ′ τ ) + R α (σ K , γ K-τ max w τ ) (73) From the result in the proof of Lemma B.2, R α (σ K , γ K-τ max w τ ) = g α (σ K , γ K-τ max w τ ).Summarizing the above, we obtainD α (s K |ξ (2) τ +1:K = ζ τ +1:K ∥s ′ K | ξ′(2) τ +1:K = ζ τ +1:K ) ≤ D (wτ ) α (s τ ∥s ′ τ ) + g α (σ K , γ K-τ max w τ ) (74) F.4 Proof of Lemma B.4.To prove this lemma, we consider tracking the ∞-Wasserstein distance of the coupled iterates. Given D K,Π and D ′ K,Π , for τ ≥ 1, recall that for any k(k ≥ 1),EQUATION)For any step k(k ≥ 1), let µ k and ν k denote the distribution of s k and s ′ k respectively. Further, define μk and νk denote the distribution of S k = (ξ 1:k , ξ1:k ) and S ′ k = (ξ ′ 1:k , ξ′ 1:k ), respectively. For step 1, we haveW ∞ (µ 1 , ν 1 ) = inf π1∈Γ(µ1,ν1) ess sup (s1,s ′ 1 )∼π1 ∥s 1 -s ′ 1 ∥ 1 (76) = inf π1∈Γ(μ1,ν1) ess sup (S1,S ′ 1 )∼π1 ∥ϕ 1 (f (s 0 )) + ξ (1) 1 + ξ (2) 1 -ϕ ′ 1 (f ′ (s 0 )) -ξ ′(1) 1 -ξ ′(2) 1 ∥ 1 (77) (a)≤ ess sup(S1,S ′ 1 )∼π * 1 ∥ϕ 1 (f (s 0 )) -ϕ ′ 1 (f ′ (s 0 ))∥ 1 ≤ ρ diff (78)where (a) is from selecting a coupling π * such that r.v.s S 1 and S ′ 1 are identical. Next, for any τ , following the above procedure, define π * k ∈ Γ(µ k , ν k ) such that S k , S ′ k are identical, we haveEQUATIONFollowing the analysis in Lemma B.1, by induction, ess supEQUATION≤ ess supEQUATION≤ ess supEQUATION) (c) ≤ γ τ -1 max • (1 -γ max ) • ρ diff 1 -γ max + ρ diff • (1 -γ τ -1 max ) 1 -γ max (88) = ρ diff • (1 -γ τ max ) 1 -γ max (89)where (a) is from Lemma B.1, (b) is from induction, and (c) arises from Eq. (78).Therefore,W ∞ (µ τ , ν τ ) ≤ ρ diff • (1 -γ τ max ) 1 -γ max (90)Further, when we setw τ = ρdiff•(1-γ τ max ) 1-γmax, we haveD (wτ ) α (s τ ∥s ′ τ ) = inf µ ′ τ :W∞(µτ ,µ ′ τ )≤wτ D α (µ ′ τ ∥ν τ ) = 0 (91)where the equality is achieved by selecting µ ′ τ = ν τ .Answer: [Yes] Justification: The complete proofs are presented in Appendix B with proof sketch outlined in Section 3.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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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.• 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case 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 to have some path to reproducing or verifying the results. 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

The 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.

The 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.
strength_weakness: strength_weakness: 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.

2. 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.

3. Since the algorithm is quite generic, can one extend it to learning or inference of a graph neural network?

The key weaknesses therefore are lack of novelty and impact.
questions: 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?

2. 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).

3. 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: Limitations are addressed.
paper_summary: paper_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
strength_weakness: strength_weakness: 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. 
The 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.
questions: 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]? 
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Specific 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. 

Scalability 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.
questions: 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?

Scalability: How does the proposed method scale with increasing graph size and complexity? Are there any optimizations or approximations that could improve scalability?

Parameter 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: limitations: See above
paper_summary: paper_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.
The 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). 

This paper addresses an important problem with novel and practical ideas showing improvements both theoretically and practically.
strength_weakness: strength_weakness: The paper lacks theoretical lower bounds showing the method is tight.
questions: questions: No question
limitations: limitations: N/A

Comments: comment: Thanks for the rebuttal.