Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Authors: Alessandro Epasto
Vahab Mirrokni
Bryan Perozzi
Anton Tsitsulin
Peilin Zhong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential privacy
Graph algorithms
Ranking
Personalized Page Rank

Abstract: Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy is one of the most important recent concerns, existing PPR algorithms are not designed to protect user privacy. PPR is highly sensitive to the input graph edges: the difference of only one edge may cause a big change in the PPR vector, potentially leaking private user data.

In this work, we propose an algorithm which outputs an approximate PPR and has provably bounded sensitivity to input edges. In addition, we prove that our algorithm achieves  similar accuracy to non-private algorithms when the input graph has large degrees. Our sensitivity-bounded PPR directly implies private algorithms for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding. To complement our theoretical analysis, we also empirically verify the practical performances of our algorithms.


Differentially Private Graph Learning via Cansitivity-oounde Personalized PageRank
Alessandro Epasto Google Research aepasto@google. com
Vahab Mirrokni
Google Research
mirrokmi@google.com
Bryan Perozzi Google Research bperozzi@google. com
Anton Tsitsulin Google Research
Peilin Zhong
Google Research
tsitsulin@google.cco
peilinz@google.co com
Abstract
Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy is one of the most important recent concerns, existing PPR algorithms are not designed to protect user privacy. PPR is highly sensitive to the input graph edges: the difference of only one edge may cause a large change the PPR vector, potentially leaking private user data.
In this work, we propose algorithm which outputs approximate PPR and has provably bounded sensitivity to input edges. In addition, we prove that our algorithm achieves similar accuracy to non- non-private algorithms when the input graph has large degrees. Our messitivity-bounde for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding. To complement our theoretical analysis, also empirically verify the practical performances of our algorithms.
PPR directly implics private algorithms
Introduction
Personalized PageRank (PPR) [15], has been a workhorse of graph mining and learning for the past twenty years. Given graph G, and a source node s, the PPR vector of node defines a notion of proximity of the other nodes in the graph to More precisely, the proximity of s to u, is defined by the probability that biased random walk starting in visits node v.
This elegant variation of the celebrated PageRank algorithm [24] has found widespread
in
different application areas of computer science, including web search [7], link prediction [22], network analysis [17, 13), graph clustering [3], natural language processing [27], spam and fake account detection [1, 2]. More recently, PPR has also been used in graph neural networks [21] and
graph representation learning [26] including speed up the computation of graph-based learning
algorithms [5, 6].
Despite the widespread use of PPR, and the extensive algorithmic literature dedicated to its efficient approximation [4, 3, 12, 16], to the best of our knowledge no prior work has attempted to compute PPR vectors in a privacy-pressseee preserving manner.
In this work, we address this limitation by defining the first approximate method for PPR computation
with differential privacy [8]. We focus on a standard notion of differential privacy (DP) for graphs
known as edge-level DP. In this notion, two unweighted, undirected graphs G (V, F) and G' (V. E'), are deemed neighbors if they differ only in the presence of a single edge [23, 10). An algorithm A is then said to be edge-level e-differentially private if the difference in the probability of
observing any particular outcome from the algorithm when run on G vs G" is bounded: Pr[A(G)
S] < e Pr(A(G") E S].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Edge-level DP guarantees strong notion of plausible deniability for the existence of an edge in the graph. This is especially critical in graph- based learning upplications, where nodes correspond to humans, and edges depend on personal relationships, which can be highly private and sensitive. Achieving edge-level DP ensures that an attacker observing the output of the algorithm is information- theoretically bounded in their ability to uncover any specific user pair connection.
On top of this notion, we also explore a popular variation of differential privacy used in personal- ization [18] that follows the concept of joint differential privacy [20]. More precisely we provide Personalized PageRank algorithms that are joint, edge-level neighborhood of the source node s. This means that we can provide the user corresponding to s, with an approximate Personalized PageRank of s that depends on the edges incident but that protects the information on edges of the rest of the graph. This notion is especially relevant in the context of personalization of results in social networks using PPR, where user data can be safely used to provide an output to the user, but must be protected from leaking to others.
cefferrentiallyprrvaat with respect the
1.1 Our results and outline of the paper
Differential privacy forces an algorithm to be insensitive to changes of an edge in the graph. This makes the design of DP PPR algorithms especially challenging single edge removal or addition may result in dramatically different PPR vectors, thus potentially exposing private user data. Our first contribution is to propose an algorithm that approximates the PPR vector with provably bounded sensitivity to edge changes. This technical contribution directly leads to the design of edge-level DP (and joint edge-level DP) algorithms for computing approximate PPR vectors. We believe that this technique may have broader applications in the design of DP graph algorithms.
From theoretical standpoint, we prove that our private algorithms achieve similar accuracy as non-private approximation algorithms when the input graph has a large enough minimum degree (while the privacy guarantee holds for all graphs of any degree). This dependency on the degree is theoretically justified as we show non-trivial approximation requires large enough degrees.
The main ingredient of our DP algorithms is a novel (non-private) censitivity-bounde approximate o 1, the sensitivity of the output of the
PPR algorithm (Algorithm 2). For any input parameter algorithm in the (joint) edge-level DP case is always upper bounded by a. In addition, we show that the algorithm has an ((o) additive error to the ground truth PPR when the minimum degree of the graph is (11/o) in the DP case (resp. Q2 I/o) in the joint-D? DD case). We show that this requirement on the minimum degree for approximation guarantees is almost tight due to hard instances that present in Appendix A. We then use our sensitivity-boundee (resp. joint edge-level DP) algorithm that, for graph of minimum degree least D, has ((1 D) additive error (resp. O(1/D²) error). Then, we focus on applications of differentialll--riiaal including computing graph embeddings. We provide provably edge-level DP and joint edge-level DP graph embedding algorithm in Section 5. Finally, in Section 6, we empirically evaluate the performance of our differentially private PPR rankings, as well that of the embedding methods we design, in several down-stream graph-learning tasks such as node ranking and classification.
algorithm to obtain an edge-level DP
PPR
To the best of our knowledge, our paper presents the first approximation algorithm with thcoretical guarantees for differentially private PPR. This result contributes to the still quite short list of private graph algorithms with provable approximation guarantees that have been developed so far [23, 10, 11, 29).
2 Preliminaries
We consider an undirected and unweighted graph G with node set V = {U1, [U1,v2,." u2,... , en } and edge set E. Let A be the adjacency matrix where A., = 1 indicates an edge between i, and vy. and A = 0 otherwise. Let A be the diagonal matrix where Aç d(w;) denotes the degree of U2- We use 0" to denote an n-dimensional all-zero vector and use e; E R" to denote the one- hot vector where the i-th entry is and other entries are 0. Let [n] denote the set {1, 2, m.). When there is no ambiguity, we sometimes abuse the notation between [n] and V, i.e., using v E [m]] to denote a node or E V denotes an index between and n. For x E R*, we denote ||ك|| Exe(y] |z,| and ||0||00 = maxie(1] [z:]- We use Lap(b) (b > 0) to denote the Laplace distribution with density function f(x) = 26 exp(-Ixl//0 The cumulative distribution function of _ exp(x/b), (-xb)))))
Lap(b) is F(x) = { 1 1
< 0,
We will use the following fact in our analysis.
1
x 2 0.
Fact 2.1. Consider Y drawn from Lap(b). For any d E (0, 1), Pr[[Y| > (ln(1/)) = 6.
2

---

NNote this is slightly weaker than the original definition of joint DP which asks for V subsets S1, S2, Sn of possible outputs of Ai, As.... An, respectively, Pr(A-z,-p(C) S-z.-ol < e Pr[A-z--v(( 1.4...--(( is the tuple of n - outputs of Ar, Az," A., except Ar, Ay, and -_.-p is the 2.1 Personalized PageRank
Personalized PageRank (PPR) takes an input distribution of starting nodes E _", and starts lazy random walk with teleport probability a E (o, 1). Typically, s = e; for some E [n]. which enforces the random walk starting from the source node 24- If there is ambiguity, we abuse the notation to denote with s the source node. The output PPR vector is the stationary distribution of the random walk. Precisely, let W = 2 (I + A A) be the lazy random walk transition matrix.' The PPR vector p(*) is defined recursively as: p()) = a 8 + (1 - a) p(s) W. In many applications, it is good enough to use approximate PPR vectors.
Definition 2.2( (5 (aaproxxie PPR, see e.g., [3]) For & > 0, ε-approximate PPR vector for p(s) is a PPR vector p(s r) where r is a non-negative n- n--imennional vector called residual vector and ||r| S.
We also study the following natural variant of the approximate PPR.
Definition 2.3 ((5, 17) apprrxxxxee PPR). For &. 17 > O, a (5, a)-pprxxxmmate PPR vector for p(s) satisfies ||p p(s r) S b) where is a non-negative n-dimensional vector and ||||] S g.
Note that denotes the error introduced by the residual and denotes the error introduced by the PPR vector itself. Two types of errors are well studied in the literature: for residual error &, see c.g., [3]; for PPR vector error 17, see c.g., [16].
2.2 Differential Privacy
We consider edge-level DP and joint edge-level DP for graph algorithms. Given a graph G. we denote IGG) as the set of all neighboring graphs of G. i.e. VG' (G)G), G' can be obtained from G by either addition or removal of an edge.
Definition 2.4 (Edge-level DP [10] and joint edge-level DP [20]). A randomized graph algorithm A is edge-level e-DP if for any imput graphs G, G' satisfying G' E (G)), and for any subset S of possible outputs of A, it holds Pr[A(G) E S) S e Pr[[((G) E S}. Let V be the set of n nodes (users). For joint edge-level DP we assume that a family of n (personalized) graph algorithmss A = AA,,, An) is run on the graph and the output of A is provided only to user (node) 2r EV. The family A is joint edge-level E-DP, for any z, V and for any two neighboring graphs G,G' that only differ on edge (z, v). any + x, and for any subset S of possible outputs Ag, it always holds Pr(Au(G) E S] $]se (G)) E S).2
for
For E V. let us denote [G) as the set of graphs G' E T(G) satisfying that G' and G differ on an edge that is not incident to s. It is easy to verify that the joint edge-level e-D is equivalent to asking for Vs E V, V subset S of possible outputs of A,, YG, G' (G), (t(A,(G) S] < e Pr.AAA E S]. In the remainder of the paper, we will simply call edge-level D-DP as e-DP and joint lege-level& e eDP as joint c-DP.
In the following, we will briefly review several other related definitions and theorems for DP.
Definition 2.5 (Sensitivity (8). Consider a function f whose input is a graph and whose output is in (I - [(G'))ll Consider a family F of functions f1, J2. In where each takes graph as input and outputs vector in RR.tt The joint sensitivity S is defined as Sf= = G.G [f) - fal
RR The sensitivity Sy is defined as Sj =
Moreover, when this simplifies the presentation, we will refer cDP and sensitivity as non-joint DP and non-joint sensitivity to oppose them to joint DP and joint sensitivity.
Theorem 2.6 (Laplace mechanism [8]. Consider a function f whose input is a graph and whose output is in R2 Suppose f has sensitivity Sy. Then the algorithm A(G)) which outputs f(G) (Yi, Y2 2.................. ... Ys) is DP where Y; are independent Lap(S)/E) /E) random variables. Similarly, consider
'This equivalent to the standard random walk matrix up to change in (see [3]). We the lazy walk for consistency with prior work.
S S=z,-p] where A_,, 2,-v
cartesian product of S1, S2, ... Sr, except S., Sy.
Our definition protects the privacy of each user, however, as we assume that output of A, is available to (node)
E V only.
3

---

family F functions fi, f2. fn joint sensitivity Sp. Then the family of A1, A2, Az. ... A,, is joint E-DP where A, (G) outputs (.) random variables.
+ (Y,,, Y,2.. .uk) and Y.. are independent Lap(S5/E)
Theorem 2.7 (Composition [9]). Consider two algorithms A1 X + A, x - 2. Suppose
.) is E2- for any given E y. Then the algorithm A3 X + Z which is defined as (x(X)= = A2 (A), is (E1 -
(1(+) is E1 and AY,
3 Warm-Up: Push-Flow on Graphs with High Degrees
As warm-up, let us start with standard push-flow algorithm for PPR [3] and provide novel analysis for bounding the sensitivity when each node has degree at least D. The non-private push-flor flow algorithm is described in Algorithm 1.3
Algorithm 1 PUSHFILOW
1: Input: Graph G = (V; E), source node & E V. teleport probability a. precision Ç.
2: Output: Approximate PPR vector for p(s).
3: Initialize (()) < (s) + 0", (()) + es, and R + [ln(1/E//o)
4: ior 1 + R do
5: Let ( + g( Let Letp ,(0 + o".
6: for Each node y E ((1-1)
do
7: Pe + pe 11-11 + a -re (1-1)
Te + re + + (1-0))/2-1 ((-1) (6-1)
8:
For each neighhor u. i.e. (v, E E: r - (00 +11
(1--a) o2)/2/22 2 r0 1/11))
/d(o), + s(t) u fu).
9: end for
10:
end for Outputp(f)
Lemma 3.1. Algorithm I outpuis E-approximate PPR vector in O(FE) (1))//)))))))))) time.
The proof of Lemma 3.1 follows the analysis idea of [3]. For completeness, we put the proof in Appendix B. Next, we prove the sensitivity of Algorithm when every node has degree at least D. Theorem 3.2 (Sensitivity of PUSHFLOW). Consider two graphs G (V, EV, G = (V, E') where G' E T(G). In addition, both G and G' have a minimum degree at least D. Let pf be the output of PUSHFL.OW(G, (G, 8, E) and PUSHFLOW((") 8, 5, respectively. Then G E (G), ip-p'll < 2:(1-a), aD
Otherwise, ||p - p'll1 < 2(1-a)
a.D
Proof. Without loss of generality, suppose G' has one more edge (x,z) than G, i.e., E' E U ((x, Let p(),)(())))))) ((0) be the same as described in Algorithm 1 when running PUSH- FLOW(G, s, E). Similarly, let p(i)) ,'(i) be the vectors plt), (+) described in Algorithm when running PUSHFLOW(G', a. Thus, our goal is to bound (|p(z) (1) It suffices to bound
|| - ( [| + [1) - |(()) Let d(e) denote the degree of e in G and let d' denote the degree of v in G'. Consider [R]. We have:
Ip x0 ||1 (1) , 10 1
Σ v
(n(- 1) +a +a.n((-1)) (1(1)) ((1))))))))
+ Σ
(1-1) (0(
2
VEV
((==1)
Σ
1
2
d(u)
d'(xc)
-EV
ui(a,))EE
u'i(u' W')
<11p
(1 1)
(1-11)
||| +
1 (1
- -(((=)))
(I)
2
1- 2
Σ "EV ui(..))EB
Σ
(--1)
((-1)
+
パ(-1 13
Ty d'
(1-1)
d(u)
d' d'())
d'
(T)
(v)
'The algorithm described in Algorithm is slightly different from the original push-flow flow algorithm of [3]. In each iteration, instead of pushing flow for the node with the largest residual, we push flows for all nodes that were visited. This variant gives better bound of sensitivity.

---

By reordering the terms, part (2) is equal to:
(1-1)
1)
a-a
Σ
d(u).
Fu
2
d(u)
d(u)
(EV((2.))
+ 2
1-a
d(x)
22
(6-1)
13-1)
d(x) +1 + (dlv) d(y)
(1-1)
+
16-1)
rg
1)-1)
d(x)
d(z) +1
d(v) +1
d(y) +
Notice that d(x)).
6
d())
d()+T
Mi 1)
+
a(z)+T - 1r2 (1-1) - 1 1
1)
+ 2 1)
d(2)+T
Similar arguments hold
for y. Thus, part (2) is at most - (1-a)/2 (1| 1) 11 (1- + (r' -1 1) (d'(z) +T0 ((-1) /1
Therefore (1)-(2)5 [1p((-1) -'
+ |||((111) - /k + (r= ((/()11) / /d'(x) - ro (6-1)) / (v))
Since d' (I), d' (y) 2 D. we have: || - -p100 ||| + -,100 S (1 116-11)11 +1|
11 + (1 - a1 (v3 1)-)))
+ +11 - ID.
In Appendix C, we show that riii-1 1)
r ( S (1 a) and if in addition s * z,y.
r ((i11) , (i-1) < (1 a)/-1/D. Thus, if x. have: [l - ( 2 (1 /) Σ (1 -a) < 2-1--a) Otherwise, we have || - 11 S 2 a)/D E/
yf
a.
a)-- - 211-a)
a-D
In Appendix A, we show that the analysis in Theorem 3.2 is tight as the sensitivity of the ground truth PPR in graphs with minimum degree D can be D(1/D) (or (2) for joint sensitivity).
If input graphs were always guaranteed to have minimum degree at least D, we could obtain DP or a joint DP PPR algorithm by applying the Laplace mechanism on the output of Algorithm (see Appendix D). However, in practice the input graphs can have low degree nodes. In this case, the sensitivity of the vanilla push-flow algorithm (Algorithm 1) can be very high. In the next section, we address the question of how to modify the algorithm to ensure low sensitivity for any input graph.
4 Push-Flow with Bounded Sensitivity in General Graphs
In this section, we propose a variant of the floh-flow algorithm of which sensitivity (resp. joint sensitivity) is always bounded by an input parameter a. As a result, we can apply Laplace mechanism (Theorem 2.6) obtain DP PPR (resp. a joint DP PPR) algorithm for all possible general input graphs and thus the added noise is controlled by a. In addition, our new algorithm achieves the same approximation Algorithm when every node in the input graph has relatively high degree.
We explain the intuition of our algorithm as the following. Recall the analysis of the sensitivity of Algorithm/ (the proof of Theorem 3.2). The reason that it may introduce a large sensitivity is
because every node x with residual r/ (f-1) may push rz (f-2) /d'(xr) amount of flow along each of its incident edges. If d'(x:) is small, the sensitivity introduced by an edge incident to x can be very large. Therefore, to control the sensitivity, a natural idea to set threshold for each edge such that the total pushed flow along each edge can never be above the threshold. We present our sensitivity-boume bounded push-flow algorithm in Algorithm 2. For sake of presentation, this algorithm and the following ones have parameter type E {joint, non-joint) indicating whether we are working in the joint DP case or in the non-joint DP case.
Firstly, we show that the joint/non-joint sensitivity of PUSHFLOWCAP(G. s,,,, indeed bounded by a. We will use the following observation.
Observation 4.1. Consider p(6), ()()) f(0) in PUSHFI (OA a, a,.iio, joinoononn-joiinn Then Ye E V, E [R]: (1) (999 Ej f(5). (2) ( min( ()) d(v) To). (3) pb) -9.
Using this observation we show the following lemma on A.59)
Lemma 4.2. Consider 1600 and (() in PUSHFLOWCAP(( G, 8, E, j.joonn/non-joim))) Ve E V E
[R] (0 min (,,10) + -- (1:0 (1-1) + Σ
5 1)
d( d(v): T..)
ai(a,))E
5

---

Algorithm 2 PUSHFL.OWCAP(G. 8, S, type)
I: Input: Graph G (V, E). source node & V. teleport probability a, precision g. sensitivity parameter o
and type E (joint, non-joint) indicating whether joint DP sensitivity or (vanilla) DP sensitivity is required.
2: Output: Approximate PPR vector for p(s).
3: Initialize the set of nodes with positive residual | + {s}, PPR ( + 0", residual v:00) + es, total pushed flow (,) 0", number of rounds R [In(1/[)/o]] and thresholds T E RR such that
1. If rype joint, T. and Vu & s, Ti. (2 (2 a)).
Otherwise, Vu V,Tu t a/(2 - ())
4: for i==1 do
5:
for Each node 5(1-1) do
6:
f6" f- min(rs (ré (1
d(v) T. hi 1
//Compute the flow to push for node e. //pddate the total pushed flow of node e.
7:
h + Ne 1)-11) + f0
8:
p( f- po 1) 3 re
(1-1) !!!
9:
end for
10:
S(1) + S(i-1),
11:
for Each node s(1-1) with f > do
12: (1) <- p.o" +a. f ,t < (1) + (0--)/2.
I/ Do actual flow push 13: For each neighbor u, i.e. (v,4) E E.rr. Eirl - (1++(1a)) /d(o), + sth) u (u}.
(t)
14: end for
15:
end for
16:
Output (8)
Theorem 4.3 (Sensitivity and joint sensitivity of PUSHFLOWCAP).. Consider two graphs G (V. F). G' = (V, F'). Let p.p be the output of PUSHFL.OCAAPiG. 8, S. type) and PUSHFI.OWCAP(C" s, E, o, type) respectively. For type joint and G' (G)),, type
non-joint and G' E [(G), then lpp - p'll1 So.
Proof. Without loss of generality, let G' e I(G) has exactly one more edge (x, than G. i.e. E' E [Zz w)}. Let (()), ( be the same as described in Algorithm 2 when running PUSH- FLOWCAP(G, s, o,, Similarly, let p(((), h/(0) be the vectors ((), described in Al- gorithm 2 when running PUSHFLOWCAP(C s. a. E. type). Let d(v) denote the degree of in G and let d'(v) denote the degree of v in G². To prove the lemma, our goal is to bound
IppR) - (R) According to Observation 4.1, we have (|p(R) [| [| = a [|A(R) - N/(R) [|1- suffices to bound []A( h²(R) ||2. Notice that Vaj, a2 az 01 E R. it easy to verify that min(a1, 02) min( (23 a4)l I |a1 azl + |2 - osl. Consider i E [R]. According to Lemma 4.2,
for every v * x. y. we have:
[h(2 - K0 0 (0) - 10)
+
1 - a
|
1
Σ ))
h d(u)
(t-1)
11 (((-1)
+ +|(d(0) ((d(())-((v())T))
2
d'(x)
1 a
h2 11)
Σ
(1-1)
h
1f
d(us)
d'(u)
where the last step follows from (000) = To
(0)
and d(v) = d'(v). Suppose v E {x, Let v' be the
other node in x, y, i... o' E (x, {o). We have:
1A59 n
((
h((-1) d(u)
1 d'(u) )
(1r(0) ,110 1
a [ [)(
h M1--))+
Σ
+ (d(())
d'(v')
mi(u,)EE g
1-a a
h ((s-2)/
Σ
h h(11))
h 1)
1 h 11
+ To,
2
d(u)
d' d'(
2
d' d'(v')
where the last step follows from |d(v) - d(v')) = 1 and
(0) (0)) Therefore,
()) - 10

---

A
h((
h/ (
+ hy h)
(1-1) 1)
+ + Σ
1- a
+ T2 +T
d(u)
d'(u)
d'(x)
d'(y)
2
u.(u.o)EB
||---0-
- 1/0-101
+ Σ
Au (1-11) 1)
(EVi(
h
AD-1) hy
h((-1)
h
by h(
1
+d(x)-
+ +d(y)
T. Ty.
d(z)
((2)
d(y)
d(y) +1
d' d'(x)
d'(y)
2
Notice that d(x)
A(-1)
<
112 (f-1) - 1/ 11(i-11 1 +
Similarly, d(y)
d(z)
[()++I
A(-1) d(y)
h(--1)
$ [ky
1) 16-1))
A(--))
a Therefore, we have:
a(v)+1
a). [
1)-1)
hy h) d'(x) d'(y)
| - 11 5(1 aa)
T. +Ty
According to Observation 4.1, we have 1 [(x) S T2 and 166 1)
d'(o) S T.. Therefore, ||
11 < (1 - a). -100-1) 11 - (2 - a) (Te + Ty). Since (1 h'00 111 0, we have [[ |/ || (2- (T, T,)/a. Hence, [| p (2 - a)) (I, Ty)) If G' E (G), i.e., 8 z, + Ty = 2 (2-(2-a))- If non-joint sensitivity is considered and G' & r, (G), i...
S 2- (2 aTj We conclude the proof.
The following lemma shows the running time and the approximation guarantee of Algorithm 2. See Appendix F for the proof.
Lemma 4.4. PUSHFL.OWCAP(G. 8, or, E, type) runs in O(IE) log(1/E)/a) time. Furthermore, if the minimum degree of G is at least max (1/(a T.), VI(la Tw) (u # s), the output of PUSHFLOWCAP(G. s, a, &, o, type) is exactly the same as the output of PUSHFLOW(G,s) a, i.e. it is a a É-approximate PPR vector for p(s).
Remark 4.5. According to the choice of and T,, the above lemma shows that if 2 St (1/D2) (resp. 2 S. (1,(D))), the output of PUSHFLOWCAPIC.. 8,0,,,,,, E. type = joint) (resp. for type non-joint) is a É-approximate PPR vector for p()). This is near optimal since we show in Appendix A that the joint sensitivity (resp. non-joint sensifivity) of the ground truth PPR of graph with minimum degree D can be at least Q(1/D²) (resp. ((1/D)).
We apply Laplace mechanism Algorithm 2 and obtain DP joint DP PPR algorithm for general input graphs (see Algorithm 3). We conclude the theoretical guarantees of our algorithm.
Algorithm 3 DPPUSHFLOW s, a,
I: Input: Graph G (V, E), source V, teleport probability o, precision &, sensitivity parameter DP parameter E, and rype E {joint, non-joint) indicating whether joint e-DP or e-DP is required. Output: e-DP approximate PPR vector for p(=).
3: p < PUSHFLOWCCP((C 8, a, E, type).
4: Let Yi, ...... Y.
drawn independently from Lap (2)
5: Output p (Y,, Y2, Yn).
Corollary 4.6 (Joint DP and DP PPR). The family of (personalized) algorithmms (A. == DPPUSHFLOWCAP(G. a, E,E,o, E.jij.) DPPUSUFLOWCAPCC. a,,,,, E,E, jon-jointt is e-DP with respect to G for any addition, if the input graph G has minimum degree at least D, the joint c-DP (resp. c-DP) output (E, Oa,e(a in })) -approximaae PPR with probability at least OZ (1/ (resp. a 2 ())
s E V} is joint s-DP, and V. In
for any 8 E (0,1) when
According to above corollary. we want the sensitivity parameter a to be small as possible since smaller leads to smaller additive emror. On the other hand, too small a may make the approximate PPR obtained by PUSHFLOW CAP (Algortihm 2) deviate from the ground truth PPR. Therefore, if
7

---

graph has minimum degree D, our joint E-DP PPR (resp. E- D- PPR) algorithm provides the best theoretical approximation guarantees when (1/D2 (resp. a = (, This matches the lower bound shown in Appendix A: the ground truth PPR has sensitivity Qt (1/D) and joint sensitivity 2r (1/ ).). Thus, our results are actually theoretically optimal up to constant factors. The implication of Corollary 4.6 is hence tight, and it is impossible to have good theoretical approximation guarantee if a < (1/D) for e-DP or a < oz (1/ for joint e-DP. In the experimental section we show, however, that in practice the algorithm performs well for a vast range of the parameter setting.
Differentially Private Graph Embeddings
As we discussed before. PPR has plenty of applications in graph learning [21, 26, 6]. In this section, to show the potentiality of our algorithms, we focus on recent example of the use of PPR for computing graph embedding. We consider InstantEmbedding [26] (see Algorithm 4) which is one practical PPR-based graph embedding algorithm. The algorithm proceeds computing the PPR vector of and then hashing them to obtain an embedding in R$ for the node s. Using our DP PPR algorithm output as input to InbedinEmbedding leads trivially to a DP embedding algorithm. However, this section, we show better implementation which reduces the amount of noise added using in slightly more sophisticated way our sensitivity bounded PPR algorithm. We think that this technique could be adapted to other uses of PPR.
First we provide a sensitivity bound for the InstantEmbedding algorithm when applying the sensitivity- bounded PPR. As result, we show how to obtain differentially private ImstantEmbedding The proof of the following theorem (the sensitivity bound) can be found in Appendix H.
Algorithm 4 INSTANTEMBEDDINGG2.. k)
1: Input: An approximate PPR vector for p(s), dimension and uniform random hash functions hy V
[k], ltga V + 11,
2: Output: Embedding vector E R²
3: Initialize <- 0².
4: for E V
5:
(hy(() f (hy(s) + hagn (v) max(log(pe-n)) - 0).
6: end for
7: Output
Theorem 5.1 (Sensitivity-bounde InstantEmbeddingg, Consider two neighboring graphs G = (V, G' (V, E') and source node s. Let p.p' be approximate PPR vectors for p(s) with respect to G and G' respectively. Let w, w' be the output of INSTANTEMBEDDINGII. k) and respectively. Let m be the number of non-zero entries of p p/. Then, || w'll S m log (1 ||p p'll _).
INSTANTEMBEDDINGIYY
Non-zero entries of p - p' in the above theorem can be at most n. Thus, || - w'll 1|1 is always at most |p p/ 111 n. If we compute p PUSHFLOWCAP(G: s, &, o). according to Theorem 4.3. the (joint) sensitivity of p is at most a. Then, according to Theorem 5. the (joint) sensitivity of output w of Algorithm 4 (using as approximate ppr p) is at most o n. This allows us to obtain (joint) e- cDPP version of InstantEmbedding by using the Laplace mechanism (Theorem 2.6) to add Lap (o n/e) to each entry of w.
6 Experiments
In this section, we complement our theoretical analysis with an experimental study of our algorithms in terms of the accuracy of the PPR ranking and node classification. In this experimental section we only consider the joint DP setting due to its practicality in personalization applications typical of PPR and its better performance. Hence all private algorithms reported are joint DP.
Hyperparameter settings. Unless otherwise specified, we ran all experiments that use our PUSH- FLOWCAr CAP algorithm (or the non non-private PUSHFLOW algorithm [3]) to obtain PPR rankings consistent to the setting commonly used in the literature of 0.15.4 Moreover, we set & so that the number of iterations R = 100 in all algorithms. We use embedding dimensionality h: = 256. We observe that our algorithm's 's utility not strongly affected by the sensitivity parameter a. For simplicity, we always set = 10-6 as this parameter generalized across different datasets tested. Detailed experiments on the effects of the sensitivity parameter can be found the Appendix.
'The algorithms use the lazy random walk [3]. we set 0.08 match the non- a of 0.15.
8

---

Joint DP PPR
Edge flipping joint DP baseline
Recall @ 100
Recall 100
0.8
0.95
0.8
0.9
0.6
0.6
0.4
0.9
ND
0.8
0.2
0.85
0,2
0.7
0.8
0.6
0
2
4
6
8
10
0
2
6
10
2
4
8
10
0
2
6
10
POS dataset
Blog dataset
Figure 1: PPR approximation on two datasets.
Baselines. To the best of our knowledge, this is the first PPR paper with differential privacy. To compare with relevant joint DP baselines we use the standard randomized response [9] sedge-flippigg baseline applied to the graph. Given the source node s, for each (unordered) pair {u, 2} of nodes (u, v # s) we apply the randomized response mechanism on the corresponding entry in the adjacency matrix: with probability p 2/(1 + (xp() the entry is replaced by uniform at random {0, 1]. otherwise we keep the true entry. This results in a joint c-DP output over which we run the non-private (1),, requires (n time generate DP adjacency matrix, and makes the output matrix dense. This limits the applicability of the baseline mechanism, whereas approach remains scalable for larger graphs.
PPR algorithm [3]. Note that this baseline, for
We also evaluated another simple joint DP baseline: adding Lap (+) noise to all PPR values obtained by the non-private PUSHFLLOW algorithm. We omit these results as they were close to random.
Datasets. We experiment on 2 publicly available datasetsavailable from [14, 28]. Table 1 reports basic statistics about these datasets. POS is a word co-occurrence network built from Wikipedia. BlogCata- log a social network of bloggers from the blogcatalog website.
Table I: Dataset characteristics: number of vertices [V] number of edges EE; number of node labels [C]: average node degree; density defined as | (()()))
Size
Statistics
dataser POS Blogcatalog
[V
[
[4]
Avg. deg.
Density
5k
185k
38.7
8.1 10
10k
334k
39
64.8
6.3 x 10
6.1 PPR Approximation Accuracy
We verify that our algorithms can rank the nodes of real-world graphs a private way. We randomly sample 1000 nodes and compute "ground- truth" PPR values with the standard power iteration algorithm. Then, we run DPPUSHFI.OWC. algorithm in the joint DP setting. Figure presents the results on the datasets studied. We examine the performance of Joint DP PPR from two standard metrics: Recall@1 k and normalized discounted cumulative gain (NDCG) [19]. We select Recall @ 100 and NDCG since the top PPR values are the most important in practical applications of ranking. We observe that the joint DP rankings offer significantly better top-k predictions across datasets and metrics tested than the private baseline.
6.2 Node Classification via Private Embeddings
Joint DP PPR
Last, we examine the performance of our joint DP embedding algorithm. We follow the procedure of [25, 14] and evaluate our embeddings on a node classification task in real-world graphs. We report the results in Figure 2. Here, Joint DP and DP rep- resents our respective implementations of Instant- Embedding; DP Baseline + InstantEmbedding rep- resents the obvious baseline of computing Baseline DP PPR followed by the hashing procedure; Non-DP InstantEmbedding the original non-DP embedding and Random represents uniform random embed- ding. Our joint DP algorithm has significantly better performance than the baseline and has non-trivial Micro-Fl even for small e. In contrast, the base- line does not extract any useful information from the graph in this range for E.
Joint DP Baseline + InstantEmbedding
Random
Non-private InstantEmbedding
25
Micro Fl x100
20
15
10
0.2
0.4
0.6
0.8
Figure 2: Private embeddings introduced in this paper outperform other competitors and achieve much higher performance on tight privacy budget.
TThis calibration of noise needed even in the joint DP setting because of the high sensitivity of PPR.

---

7 Conclusion
In this work, showed that it is possible compute approximate PPR rankings with differential privacy. We believe that the techniques developed for bounding the sensitivity of PPR can find applications in other areas of graph-learning As future work, would like to extend the use of our DP PPR algorithm to more machine learning tasks.
Societal impact and limitations Our work focuses on developing DP algorithms for data analysis. If used correctly, DP provides strong protection, but has limitations (we refer to standard textbooks on the subject [9]). Moreover, while privacy is requirement of a responsible computational system, is not the only one. We encourage reviewing holistically the safety of any application of our work.
References
[1] Lorenzo Alvisi, Allen Clement, Alessandro Epasto, Silvio Lattanzi, and Alessandro Panconesi. Sok: The evolution of sybil defense via social networks. In 2013 IEEE Symposium Security and Privacy, pages 382-396, 2013.
[2] Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Kamal Jain, Vahab S. Mirrokni, and Shang-Hua Teng. Robust pagerank and locally computable spam detection features. In Carlos Castillo, Kumar Chellapilla, and Dennis Fetterly, editors, AIRWeb 2008, Fourth International Workshop on Adversarial Information Retrieval on the Web, Beijing, China. April 22, 2008, ACM International Conference Proceeding Series, pages 69-76, 2008.
[3] Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank locally partition graph. Internet Mathematics, 4(1):35 64, 2007.
[4] Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized pagerank mapre- duce. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages
2011.
[5] Aleksandar Bojehevski, Johannes Klicpera, Bryan Perozzi, Martin Blais, Amol Kapoor, Michal Lukasik, and Stephan Günnemann, Is pagerank all you need for scalable graph neural networks? In ACM KDD, MLG Workshop, 2019.
[6] Aleksandar Bojchevski. Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-2473, 2020.
[7] Junghoo Cho and Uri Schonfeld. Rankmass crawler: crawler with high personalized pagerank coverage guarantee. In Proceedings of the 33rd international conference on Very large data bases, pages 375 7756 2007.
[8] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[9] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-000 2014.
[10] Marek Eliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 560-578. SIAM, 2020.
[11] Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. arXiv preprint arXiv:2 /4756, 2021.
[12] Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3):333-358, 2005.
[13] David F Gleich. Pagerank beyond the web. Siam Review, 57(3):221366,, 2015.
10

---

[14] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks, In KDD, 2016.
[15] Taher H Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE transactions on knowledge and data engineering, 15(4):784-796, 2003.
[16] Guanhao Hou, Xingguang Chen, Sibo Wang, and Zhewei Wei. Massively parallel algorithms for personalized pagerank. Proceedings of the VLDB Endowment, 1 1469):668--1680, 2021.
[17] Gábor Iván and Vince Grolmusz. When the web meets the cell: using personalized pagerank for analyzing protein interaction networks. Bioinformatics, 27(3):405-407, 2011.
[18] Prateek Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. Differen- tially private model personalization. Advances in Neural Information Processing Systems, 34, 2021.
[19] Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain-based based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 2002.
[20] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
[21] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[22] David Liben-Nowell and Jon Kleinberg. The link tink-prediction problem for social networks. Journal of the American society for information science and technology, 18(7):1019-1031, 2007.
[23] Bun Marc, Marek Elias, and Kulkarni Janardhan. Differentially private correlation clustering. In ICML, 2021.
[24] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[25] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD,, 2014.
[26] Stefan Postăvaru, Anton Tsitsulin, Filipe Miguel Gonçalves de Almeida, Yingtao Tian, Silvio Lattanzi, and Bryan Perozzi. Instantembedding: Efficient local node representations. arXiv preprint vrXiv:2010.06992 2020.
[27] Federico Scozzafava, Marco Maru, Fabrizio Brignone, Giovanni Torrisi, and Roberto Nav- igli. Personalized pagerank with syntagmatic information for multilingual word sense disam- biguation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics:
System Demonstrations, pages 37-46, 2020.
[28] Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller, Verse: Versatile graph embeddings from similarity measures. In wwW, 2018
[29] Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In International Conference on Artificial Intelligence and Statistics, pages 1171-1179, PMLR, 2021.
[30] Depeng Xu, Shuhan Yuan, Xintao Wu, and HaiNhat Phan. Dpne: Differentially private network embedding. In Pucific-Asia Conference on Knowledge Discovery and Data Mining, pages 235-246. Springer, 2018
[31] Sen Zhang, Weiwei Ni, and Nan Fu. Differentially private graph publishing with degree distribution preservation. Computers & Security, 106:102285, 2021.


Reviews:
[{"review_id": "mnTfsxI_dki", "reviewer": "Reviewer_SocG", "summary": "This paper studies the Personalized PageRank (PPR) problem (which is a very popular quantity\nused in graphmining) under differential privacy constraints. The first contribution of\nthe paper involves analyzing the sensitivity of a prior algorithm for PPR, Push-Flow,\nin terms of the min-degree of the graph; this could be large if the min-degree is low.\nThe authors design a natural variant, PUSHFLOWCAP, which has a better sensitivity,\nallowing the Laplace mechanism to give privacy bounds. Finally, the authors combine their\nmethod with a recent algorithm for embeddings. The methods are evaluated on real-world datasets.", "questions": "Is the notion of (\\xi, \\eta)-approximate PPR well established? What is the impact of the \\eta\nparameter on the utility of PRR in practice?\n\nThere are a lot of symbols, some of which are defined as they are encountered or after. For instance,\nT_v is not yet defined in Obs 4.1 and Lemma 4.2, making it hard to parse. A table of notation\nmight make the paper more readable.  The statements with join/non-joint, while concise,\nare also harder to read.\n\nSection 6: while the values of hyperparameters \\xi, \\alpha and k might make sense in a non-private\nsetting, it is not clear if those are the best choices for this paper. It would be interesting\nto see how they are impacted under privacy, and it might provide a way to improve the results\nfurther.\n\nSection 6.1: it would be useful to define the metrics.\n\nSection 6.2: for evaluating embeddings, it might be useful to compare with the DPNE method of\n(Xu et al., PAKDD 2018), which gives an algorithm for this problem. Also, how is micro-F1 defined?\nThe results in Figure 2 are not particularly great. Maybe considering larger \\epsilon is helpful", "limitations": "The discussion is limited but seems ok", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "PPR is a very commonly used metric, and differentially private algorithms are not known. So the\npaper is studying an important problem. The main technical idea is quite nice, and pretty natural.\nThe sensitivity analysis of the Push-Flow and PUSHFLOWCAP algorithms is technically\ninteresting, though not particularly involved.\n\nThe statements in the final results are somewhat complicated since the utility analysis\nholds under some conditions. These would become stronger if a lower bound could be shown.\n\nThe experiments section could be strengthened. While there is no private algorithm for PPR,\nrandomized response seems like too weak a baseline.\n\nThe presentation could be improved quite a bit. The authors could simplify the notation and present\nit in a way that the symbols are easier to parse.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "irV9zIqcdL1", "reviewer": "Reviewer_gvyQ", "summary": "This paper focuses on computing approximate Personalized PageRank (PPR) vectors with differential privacy (DP) in graph representation learning. First, the authors analyze the non-private version $\\xi$-approximate PPR push algorithm with sensitivity. Then, the authors develop a variant of the push algorithm with bounded sensitivity called PushFlowCap. By applying Laplace mechanism with PushFlowCap, they also propose an algorithm called DPPushFlowCap to obtain an non-joint or joint $\\epsilon$-DP approximate PPR vector. Finally, based on InstantEmbedding, the authors provide a sensitivity-bounded version for graph embedding.", "questions": "1. Why do the authors specifically choose the Laplace distribution? There are no citations or explanations in Section 2 from line 78 to line 88.", "limitations": "The authors have sufficiently addressed limitations of this work. In Section 7, the authors concern the safety of any application of this work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The theoretical foundation is solid.\n    \n- The algorithms are written clearly.\n\nWeaknesses:\n\n- The idea of this paper is based on an assumption that a GNN with the Personalized PageRank filter is highly sensitive to edge changes on a graph such as a single edge addition or removal. However, according to research works about stability for polynomial spectral graph filters[1,2] which include the Generalized PageRank filter[3,4], a generalization of all PageRank filter variants, polynomial spectral graph filters are robust for edge modifications so long as the endpoint degrees are high. Therefore, the assumption for this work is not entirely valid.\n    \n- The introduction of relations among the $(\\xi,\\eta)$-approximate PPR vector, non-joint and joint DPPPR vector, PushFlowCap algorithm, and DPPushFlowCap algorithm are vague.\n\nReferences:\n1. Kenlay, H., Thanou, D., & Dong, X. (2020). On The Stability of Polynomial Spectral Graph Filters. In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 5350–5354).\n2. Kenlay, H., Thanou, D., & Dong, X. (2021). Interpretable Stability Bounds for Spectral Graph Filters. In Proceedings of the 38th International Conference on Machine Learning (pp. 5388–5397). PMLR.\n3. Baeza-Yates, R., Boldi, P., & Castillo, C. (2006). Generalizing PageRank: Damping Functions for Link-Based Ranking Algorithms. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 308–315). Association for Computing Machinery.\n4. Gleich, D. (2015). PageRank Beyond the Web. SIAM Review, 57(3), 321–363.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bh5ispKosWr", "reviewer": "Reviewer_61St", "summary": "In this paper, the authors propose an algorithm which outputs an approximate PPR and\nhas provably bounded sensitivity to input edges.", "questions": "Why is their no theoretical proofs in the paper?\n\nWhy is comparative analysis lacking from the Experiments?", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nPaper is organized well\n\nPaper topic is interesting\n\nCons:\n\nAlgorithms theoretical bounds are not studied (NP-Complete etc)\n\nExperimental analysis is brief and does not give comparative analysis to SOA algorithms\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9RdaPU74JYY", "reviewer": "Reviewer_MDNv", "summary": "The paper proposes algorithms that compute personalized PageRank (PPR) under edge differential privacy (DP), and extends the algorithms to compute graph embeddings.", "questions": "N/A", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an interesting problem, and is relatively well written. However, there are several major issues with the paper.\n\nFirst, the proposed PPR algorithm is relatively straightforward: it computes the PPR values and then adds noise based on the sensitivity of the values. The sensitivity analysis is mostly based on the triangle inequality and is rather loose. As a consequence, the significance of the algorithm is unclear.\n\nSecond, the proposed algorithm relies on unreasonable parameter settings. In particular, the algorithm set a threshold $\\sigma$, and requires that when each node pushes residues to its neighbors, the total amount of residues pushed along each edge is at most $\\sigma$. As a consequence, if a node $v$ has $d$ edges, then the total amount of residues pushed from $v$ is upper bounded by $d \\cdot \\sigma$. Therefore, if the initial residue of $v$ is $x$, then the approximate PPR for $v$ returned by the algorithm is at most $x - d \\cdot \\sigma$. In the experiments, we have $x = 1$ for each initial node and $\\sigma = 10^{-6}$, and the average degree of each node is only a few dozens. As a result, the approximate PPR for each initial node is almost identical to the initial residue $x = 1$. Apparently, such approximate PPR values are far from the ground truth PPR values. This issue cannot be addressed by using a larger $\\sigma$, because the amount of noise used by the algorithm is linear to $\\sigma$. \n\nThird, the paper presents algorithms for both edge DP and joint edge DP, but the experiments only evaluate the joint edge DP algorithms. As a consequence, it is unclear whether the proposed edge DP algorithms work well or not.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept