{'fraction_non_alphanumeric': 0.04602114964258286, 'fraction_numerical': 0.009304661192178177, 'mean_word_length': 4.304763397054215, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Privacy Preserving Link Prediction with Latent Geometric Network Models

Link prediction is an important task in social network analysis, with a wide variety of applications ranging from graph search to recommendation. The usual paradigm is to propose to each node a ranked list of nodes that are currently non-neighbors, as the most likely candidates for future linkage. Owing to increasing concerns about privacy, users (nodes) may prefer to keep some or all their connections private. Most link prediction heuristics, such as common neighbor, Jaccard coefficient, and Adamic-Adar, can leak private link information in making predictions. We present D P L P , a generic framework to protect differential privacy for these popular heuristics under the ranking objective. Under a recently-introduced latent node embedding model, we also analyze the trade-off between privacy and link prediction utility. Extensive experiments with eight diverse real-life graphs and several link prediction heuristics show that D P L P can trade off between privacy and predictive performance more effectively than several alternatives.


Introduction
Link prediction (LP) [20,22,25] is the task of predicting future relations (edges) that can emerge between nodes in a social network, given historical views of it. Predicting new collaborators for researchers, new Twitter followers, new Facebook friends and new LinkedIn connections, are examples of LP tasks. Link predictions are usually presented to each node u as a ranking of the most promising non-neighbors v of u at the time of prediction.
With increasing concerns about privacy [35,37,42], social media platforms are enabling users to mark some of their data (usually demographic attributes) as private to other users and the Internet at large. However, homophily and other network effects may leak attributes. Someone having skydiver or smoker friends may end up paying large insurance premiums, even if they do not subject themselves to those risks. A potential remedy is for users to mark some part of their ego network as private as well. However, the social media hosting platform itself continues to enjoy full access to the network and all attributes, and exploits them for LP. As we shall see, many popular LP algorithms leak neighbor information, because they take advantage of rampant triad completion: when node u links to v, very often there exists a node w such that edges (u, w) and (w, v) already exist. Therefore, recommending v to u may breach the privacy of v and w.
In this paper, we develop DPLP, a simple-to-implement wrapper around most popular LP algorithms and show that it can protect privacy in the more general sense motivated above. For our analysis we use differential privacy (DP) [13], the standard yardstick for protecting private information. We perturb the scores from an LP module using a (non-Laplacian) distribution and sample top predictions using by sampling a distribution parameterized by the perturbed scores. Similar paradigms have been used [26], but with utility functions that would choose a single node (rather than a ranking), had privacy concerns been absent.
There is usually a trade-off between prediction quality and privacy. If the utility without privacy concerns is a deterministic function of the current graph, the relative loss of utility for a given level of privacy can be analyzed [26] for per-node definitions of utility. We analyze prediction quality under two additional challenges. First, we consider top-K ranking quality. Second, we model utility that is not directly observable, but latent in the generative process that creates the graph.
Sarkar et al. [33] showed that popular (non-DP) LP heuristics wield predictive power, when latent node embeddings in a geometric space [17] are modeled as causative forces driving edge creation. More specifically, nodes u, v are represented as points in a high dimensional space, and the edge (u, v) is likely to emerge according to a suitable distribution that depends on the distance between the node embeddings. The latent node embeddings are not known to LP algorithms, so even the best LP algorithm may have a positive risk to (ranking) utility. DP requirements will generally result in an increase in that risk, which we analyze. As a result, we get a complete characterization of the trade-off between privacy requirement and risk to utility, with reference to a latent generative process.
Related work: In the absence of a graph generative model as a reference, absolute prediction quality cannot be quantified. Machanavajjhala et al. [26] define utility as the best single-node score s v * attained by a non-DP LP heuristic, such as the best common-neighbor score. To protect privacy, the deterministic maximum utility choice is replaced by a sample drawn from all nodes V according to a distribution {p v } over non-neighbors. The expected sample utility is ( v s v p v )/s v * . Thus, they do not consider the top-K ranking scenario. They also assume a constant fraction of total utility is concentrated in a small number of candidate nodes, which naturally yields steep trade-offs between privacy and utility. When the popular Laplace perturbation is used in this relative utility setting [14], |V| random numbers are needed to draw a single recommendation. If the level of privacy is held constant, as |V| → ∞, Laplacian perturbation will continue to lose (relative) utility. In contrast, we introduce K random numbers to draw K samples, and our (absolute) loss of ranking accuracy goes to zero as |V| → ∞.
Other complementary aspects of privacy in social networks have also been addressed [10,11,32]. When the social media platform itself cannot be trusted, Samanthula et al. [32] provide an encryption and security architecture, together with anonymous message-passing protocols for friend recommendation. Chen et al. [10] characterize node attribute and link information in terms of rareness. Disclosure of attributes has benefits and risks, which are balanced using a knapsack formulation.

Summary of contributions:
We initiate a study of differential privacy in LP algorithms that present a ranked list of top-K recommended nodes to a query node u. We present and establish the privacy guarantee of DPLP, a generic template to convert a non-DP LP algorithm into a DP version. In contrast with Laplacian or Gaussian mechanisms that use O(|V|) random numbers, DPLP uses O(K) random numbers. Consequently, it results in a smaller loss of ranking accuracy, while maintaining the same level of privacy. In a marked departure from earlier work [26], we also analyze the absolute loss of ranking quality attributable to privacy requirements, in a graph generative framework where nodes have latent embeddings and links depend on the distance between these embeddings. Experiments over eight data sets and several popular LP algorithms show the efficacy of DPLP, compared to DP obtained through Laplacian, Gaussian and Exponential perturbations. Our code and data have been uploaded in [1].

Preliminaries
We model a snapshot of the social network as an undirected graph G = (V, E) with vertices V and edges E. Neighbors of node u are denoted as the set N (u) and non-neighbors denoted as N (u). After observing this snapshot, an LP algorithm will present to each node u a ranking of nodes in N (u), perhaps truncated to the first/top-K positions. The expectation is that user u has strong reason to link to the top nodes in the list. Throughout, we denote {1, . . . , N } as [N ] and the 0/1 indicator for event B as B . point x u sampled uniformly randomly from within a D-dimensional hypersphere having unit volume. Nodes u and v get connected if the distance d uv = ||x u − x v || 2 between them is less than r [9]. Therefore, Here, Ω(r) is the volume of the r-radius hypersphere. The usual evaluation protocol of an LP algorithm is that a graph, thus created, gets some fraction of edges and non-edges 'hidden' (see Section 5 and Appendix E) from an LP algorithm A, which has to predict their existence or non-existence. A has no access to the latent node embeddings or r. In our work we are interested in the quality of ranking, for each node u, nodes v that are not currently neighbors of u, that are most likely to be(come) neighbors.
Ranking loss: Given u, an LP method M ranks the top-K nodes v that u is most likely to link to. If the latent node embeddings were known to M, it would pick non-neighbors v ∈ N (u) by increasing d uv . However, M cannot observe distances in the latent space. Popular LP methods assign scores s M (u, v) by observing G. These scores provide M's ranking on current non-neighbors v of node u. This ranking will generally differ from the 'perfect' ranking induced in the latent space, leading to a ranking loss.
Differential privacy: We design and analyze privacy protection in LP algorithms in the framework of differential privacy (DP) [13]. In our context, a randomized computation M runs on a graph G, returning an ordered list of K recommended nodes for a query node u. Let us call this (random) output M(u; G). If the graph is changed to G , the random output becomes M(u; G ). M provides -differential privacy if, for any possible output list L, log Pr(M(u;G)=L) Pr(M(u;G )=L) ≤ |G ⊕ G |, where the multiplier of measures the extent of perturbation, usually a single edge. For a more formal background of differential privacy, see Dwork and Roth [13], applications to link prediction [26], or Appendix A.

Link prediction algorithms with privacy protection
In this section, we present a generic differentially private (DP) framework for link prediction. Such a framework DP implements an algorithm A on a given LP protocol A with a scoring function s A (u, ·). To that aim, we first define a sensitivity function of a score s A (u, v) implemented by an LP protocol A. Then we leverage this sensitivity function to develop a generalized paradigm for DP LP algorithms, called DPLP. Finally, we instantiate DPLP to specific privacy-preserving methods for the popular LP methods: common neighbors (CN), Jaccard coefficient (JC) and Adamic-Adar (AA).
Graph sensitivity: Given a query node u, a DPLP algorithm A which operates over an original LP algorithm A, should not be likely to produce a substantially different set nodes for a graph G as compared to G , where G and G differs by only one edge. To establish the DP property, we need to show that the likelihood of predicting a candidate is not very sensitive to (small) perturbations to G. To that end, we first define the sensitivity of a positive scoring function s A (u, ·) : N (u) → R + .
Definition 1 (Sensitivity of s A ). Let G = (V, E) and G = (V, E ) be two graphs with the same node set V. E differs from E by at most one edge, i.e., max(|E \ E |, |E \ E|) = 1. Then the sensitivity ∆ A of an LP algorithm A is defined as the maximum absolute difference between the scores s A (u, v) in G and G across all pairs of nodes (u, v) and all set of such possible graphs G and G, i.e., Note that G and G differ only by an edge, but not a node. This is because adding or removing an isolated node does not affect reasonable LP algorithms.
Examples: For common neighbors, ∆ CN = 1, because an additional edge (v, y) increases s CN (u, v) = |N (u)∩N (v)| by one for y ∈ N (u) and v ∈ N (u). For Jaccard coefficient, too, it is easy to check that ∆ JC ≤ 1, since a single-edge perturbation can increase the number of common neighbors only by 1. DPLP, a privacy-protecting LP framework: Since the traditional deterministic scoring protocols are sensitive to perturbation in G, they can lead to privacy leakage. In response, we present a generic DP framework for LP. Instead of selecting nodes deterministically, we sample them based on a simple categorical distribution which depends on the corresponding scores (s A ) and suitable privacy parameter σ to control the noise injected into the sampler, and thus, leakage. Algorithm 1 summarizes the generic template.
Recommends top K nodes that u may link to.
Input: Node u, non-neighbors v ∈ N (u), LP algorithm A, estimate of ∆A, allowed privacy leakage level p Output: K predicted nodes to which u might link.
Main loop for predicting 1 st to K th neighbor 4: Set probability of sampling k th neighbor 5: w ∼ Multinomial(α α α) Sample the neighbor 6: Elaborating, to sample the k th node recommended to a query node u, we draw a potential neighbor v with a probability proportional to (s A (u, v) + ∆ A + 1) σ , among all non-neighbors who are not selected until step k − 1. The parameter p controls the privacy leakage. If p → ∞, then σ → ∞, and the candidate node with maximum score gets selected, and the algorithm reduces to the original deterministic protocol A that may violate the privacy of the nodes. On the other hand, if p , σ → 0, then every node has an equal chance of getting selected, which preserves privacy but has low predictive utility.
Applied in the utility setting of Machanavajjhala et al. [26], the popular Laplacian or Gaussian perturbation protocol [14] would generate |V| random numbers, perturb the raw scores, and choose one node with maximum perturbed score. In contrast, in each of K iterations, DPLP first generates α α α without using any randomness, and then samples Multinomial(α α α) once in each of K recommendations. Thus, DPLP uses O(K) random numbers and provides privacy at a smaller loss of ranking accuracy. Note that, since any monotone function of a score is also a suitable score, the exponential protocol [13] can also be used in Algorithm 1 to guarantee privacy. However, depending on the form of the monotone function, ranking utility may vary. In Section 5, we show that exponential perturbation achieves worse ranking quality in practice.
Analysis of the privacy of DPLP: Among our key results is that the template proposed in Algorithm 1 offers a DP guarantee for any positive scoring function s A , provided ∆ A is bounded. The proof of the following formal claim is given in supplementary material (Section B.1).
Theorem 2. Given any LP algorithm A with bounded sensitivity on the scoring function s A , the corresponding DP algorithm A given by DPLP (Algorithm 1) is p = 2Kσ log(1 + ∆ A ) differentially private.
As sensitivity ∆ A increases, p increases as well, thereby inflicting more violation of privacy. Such an observation intuitively supports the basic notion of privacy leakage -for a highly sensitive scoring protocol, a small perturbation in the graph produces a substantially different set of recommendations.
While the above result holds for any generic LP algorithm, DPLP may give stronger guarantees for specific algorithms. In particular, the presence of such stronger bounds also depends on the number of nodes affected due to one single addition or deletion of edge in the graph. For example, given a node u, adding or deleting one edge can change the common neighbor score s CN (u, v) for at most one possible node v, when it connects v to a neighbor of u. On the other hand, in case of Adamic-Adar, addition of one edge can change the scores for many nodes. In the following, we formally state the privacy guarantee for common neighbors and Jaccard coefficient. The proof is given in supplementary material (Section B.2). Lemma 3. Given the conditions of Theorem 2, if s A (u, v) is computed either using common neighbors or Jaccard coefficient, then Algorithm 1 is p /2 differentially private.
4 Quality of privacy-protecting link prediction under the latent space model Privacy can always be trivially protected by ignoring private data, but that leads to poor prediction. E.g., Algorithm 1 can provide extreme privacy by driving p → 0, but such a protocol will select each node uniformly, which has no predictive value. Most proposals for privacy protection provide empirical analysis of variation of prediction quality against some DP guarantee parameter [2,21,34]. However, a formal guarantee would reveal more insights and help to draw the possible boundaries of the underlying proposal. In this context, the relative loss of prediction qualityloss suffered in terms of an observable quantity e.g. a scoring function-may be easier to analyze [26]. However, preservation of absolute prediction quality-utility in terms of the true latent generative process-is harder to prove, because, even in the non-DP case, absolute quality is rarely analyzed. A notable exception is the latent space model of Sarkar et al. [33], reviewed in Section 2. We leverage their paradigm in two ways: we will first work with ranking losses over K > 1 neighbors, and then establish ranking quality in the face of privacy protection.
Relating ranking loss to absolute prediction error: In general, any LP algorithm 1 M provides two maps: π M u : gives the rank of v ∈ N (u) and u M i represents the node at rank i recommended to node u by algorithm M. Any score based LP algorithm M provides ranking π M u by sorting scores s M (u, v) in decreasing order. On the other hand, a sampling based LP protocol (e.g. the proposed DP algorithm A) sequentially samples u M i . Furthermore, we denote π * u as the perfect ranking over v ∈ N (u) induced by (increasing) latent distances d uv , and therefore we have u * i = (π * u ) −1 (i). Any ranking π M u may suffer some deviation from the 'ideal' permutation π * u of non-neighbors N (u). This may happen because M can build only imperfect estimates of latent distances after observing G, and because it has to protect privacy. Therefore, we define a loss function incurred by the ranking protocol M, which measures such a deviation from the hidden perfect order π * u of non-neighbors up to rank K. In the context of the latent model [33] . .] as the sequence of latent distances from u to other nodes, as ordered by algorithm M. Because M is generally imperfect, d M u need not be monotone increasing. Following Negahban et al. [29], we define The above nonsmooth ranking loss can be bounded by a function of the following surrogate loss. The proof is given in Appendix C.1.
Quality of ranking in the face of DPLP: Here, we consider a DPLP algorithm A that calls an underlying LP algorithm A as a subroutine, and explore A = CN, JC, AA. Like other privacy preserving algorithms, DPLP also introduces some randomness into the original LP protocol, and therefore, any DPLP algorithm A may reduce the predictive quality of A. Controlling the level of randomness ( p ) in A allows DPLP to effectively tradeoff between privacy and the fidelity to the predictions made by A. A nontrivial p results in some loss of predictive quality. To formally investigate the loss, we first quantify the loss in scores suffered by A, compared to the top-K nodes selected by s A : Here, we do not take absolute difference because the first term cannot be smaller than the second. The expectation is over randomness introduced by an ( p differentially private) algorithm A. Using the loss of scores, we next bound the loss of ranking quality induced by a DPLP algorithm A over several LP algorithms A.
Theorem 5. Define = 2 log(2/δ) |V| + 7 log(2/δ) 3(|V|−1) and recall that Ω(r) is the volume of radius-r, D-dimensional hyper- 1 We denote M as A if it is a non DP algorithm; and as A if it is a DP algorithm induced by A.
sphere for the latent space random graph model. With probability 1 − 4K 2 δ, we have Note that the expectation is only taken only over the differentially private algorithm, but not randomness of the data, and this randomness of the data induces the high probability. Proof idea: To prove these inequalities, for each LP heuristic, we first bound the deviation of the common volumes shared by u and the recommended nodes u A i from those shared by u and the optimal nodes u * i . Then we use such a deviation to bound RANKINGLOSS(d u ; d A u ). The proof is formally given in supplementary material (Appendix C.2). To investigate the behavior of ranking loss with variation of p and |V|, we first estimate γ u (A, p ) (For proof see Appendix C.3).
is the largest score of a node, which is strictly less than the score of node u A i .
Privacy-utility trade-off: Note that if p increases, the amount of privacy given by DPLP decreases, and therefore we can measure 1/ p as a measure of privacy. Then, from Lemma 6, we observe the following lemma.
Lemma 7. If s max = max v∈N (u) s A (u, v), PRIV := 1/ p then we have: The proof mostly leverages Lemma 6. It is given in supplementary material (Appendix C.4). The above relation reveals that if sensitivity increases, the maximum attainable privacy for maintaining a given utility decreases. Moreover, if the privacy is kept constant, then a high sensitivity helps to increase the utility (γ u (A, p ) goes low). Since a high sensitivity allows the underlying algorithm A to exploit rich signals, it provides better prediction.

Experiments
In this section, we use eight real world datasets to show that DPLP can trade off privacy and the predictive accuracy more effectively than three standard baselines [13,26,28].
Datasets: We use eight datasets 2 (USAir [7], C.Elegans [39], Yeast [38], Facebook [19], NS [30], PB [3], Power [39] and Ecoli [41]). These datasets are graphs with diverse sizes and structural properties. Appendix E.1 contains further details and statistics about them. Owing to space constraints, in this section, we present the results only for the first five datasets. Appendix E contains the results on the others.
Evaluation protocol and metrics: For each of these datasets, we only consider predicting neighbors on the set of query nodes Q each containing at least one triangle, and we leave the others out. Such a pre-selection protocol is standard to LP literature [5,12], which allows for a fair evaluation specifically for triad based LP heuristics. Then, following [12], for each query node q, in the fully-disclosed graph, the set of V\{q} is partitioned into neighbors N (q)  Table 1: Comparison of performance in terms of expected Mean Average Precision (MAP) between various differential private algorithms e.g. DPLP, Laplace, Gaussian and Exponential for 15% held-out set with p = 0.1 and K = 10.
The expectation is computed using MC approximation with n = 10 runs of randomization. Error analysis is given in Appendix. The first (last) five rows indicate performance of triad-based LP heuristics (graph embedding techniques). DPLP outperforms Laplacian, Gaussian and Exponential mechanisms across almost all the datasets. and non-neighbors N (q). Then we sample 85% of |N (q)| neighbors and 85% of N (q) non-neighbors and present the resulting graph G sampled to an LP protocol M (M = A for a usual non-private LP and M = A for a differentially private LP). Then, for each query node q, we ask M to provide a top-K (K = 10) list of potential neighbors (good items in the context of information retrieval [27]) from the held-out graph-consisting of 15% secret neighbors and non-neighbors, then compute average precision value AP (q) and finally provide mean average precision (MAP) i.e. 1 |Q| q∈Q AP (q) to measure the predictive power of M. In contrast to some previous works [5,40], we avoid AUC as an accuracy metric due to two pitfalls: (i) some differentially private mechanisms (like DPLP and Exponential) randomly sample nodes, where the sequence of sampled nodes is not likely to comply with relative order of scores; and (ii) AUC strongly relies on the number of neighbor vs. non-neighbor pairs in the top-K-ranked list, and is somewhat immune to class imbalance. As a result, AUC is usually large and undiscerning for any reasonable LP protocol over a sparse graph [12,27].
Candidates for traditional LP protocols A: We consider two classes of base LP algorithms A: (i) algorithms based on the triad-completion principle, i.e. the ones we analyzed (CN, JC, AA), and (ii) algorithms based on fitting node embeddings, i.e. Node2Vec [16], Struct2Vec [31] and PRUNE [18], which are beyond the scope of the current theoretical analysis. In addition, we also report results on two another LP protocols: Cumulative Random Walk (CRW) [24] and LINE [36] in Appendix E.3.

DPLP and baselines (A):
We consider DPLP and three additional perturbation mechanisms that maintain differential privacy to compare with DPLP: (i) Laplacian, (ii) Gaussian, and (iii) Exponential perturbation. To evaluate a differentially private algorithm A on the above LP protocols, we first fix the level of privacy leakage p and apply A to various base LP algorithms and then we run n = 10 trials and finally report E A [MAP]. The exact choice of p differs across experiments.
Results: Table 1 compares the expected MAP estimates at a given privacy leakage p = 0.1, for various data sets and base LP algorithms for top-K (K = 10) predictions. At the very outset, DPLP almost always outperforms Laplacian, Gaussian and Exponential mechanisms. This is because, Laplacian and Gaussian mechanisms use O(|V|) random numbers thereby injecting more randomness than DPLP and Exponential protocols which generate O(K) random numbers. While the substantially better performance of DPLP than the baselines over CN, AA and JC corroborate our theoretical analysis, we note that such an improvement is not so significant in case of the other three base LP algorithms involving deep graph embedding techniques. The formal theoretical analysis of this observation is beyond the scope of the paper. We believe that these embedding methods already use many sources of randomness-from initialization to negative samples, which make them immune to an additional random perturbation. In fact, it is surprising to see that the overall MAP values of the node embedding methods were generally worse than simple LP protocols, however, this is also noted by others [40].  i.e. CN, AA and JC, we observe that as we allow more privacy leakage, MAP increases for all methods. For LP protocols based on node embeddings, the performances remain stable. The overall MAP values of node embedding methods are worse than simple triad-based protocols, which is also noted in [40]. Figure 1 fixes A = DPLP and K = 10, varies the privacy level p , and compares expected MAP using base methods CN, JC and AA on various data sets. AA is generally the best. There is an increasing trend of MAP with increasing p (reducing privacy), which is expected. Figure 2 shows a different slice of the data. We fix the dataset to Yeast and K = 10. Each chart is for a base method, and shows MAP vs. privacy for various perturbation protocols A. For traditional deterministic methods CN, AA and JC, the upward trend continues. Curiously, for the node embedding approaches, such trends, if any, are very weak. As mentioned before, LP methods that depend on node embeddings invest large amounts of randomness even without privacy requirements. Another important issue to consider for node embedding methods is that node embeddings include private information. Decisions made by comparing these embeddings may leak information.

Conclusion
In this paper, we have presented DPLP, a perturbation protocol to turn non-DP LP heuristics into DP versions, in a top-K node ranking setting. After establishing DP guarantees when DPLP is applied to three popular LP heuristics, we analyzed the loss of predictive quality of DPLP in a latent distance graph generative framework. We also characterized the trade-off between privacy and absolute predictive quality in this framework. In contrast to popular Laplace or Gaussian mechanisms which use O(|V|) random numbers, we inject O(K) random numbers, which allows for a more accurate link prediction with the same amount of privacy leakage. Extensive experiments showed that DPLP is superior to popular Laplacian, Gaussian and exponential perturbation protocols. Our work opens up several interesting directions for future work. In particular, we can investigate DPLP or similarly effective protocols, when applied to recent LP algorithms such as supervised random walks [5] and graph-based deep networks [40]. Collusion between querying nodes, graph steganography [6], and repeated data exposure over time entail privacy breach risks that are not modeled in our framework. Bhagat et al. [8] use LP on a current graph snapshot to guide how future exposure should be curtailed. Further analysis along these lines may be of interest.

Supplementary Material
Appendix A Formal notion on differential privacy Here, we formally state the definition of differential privacy [13,14].
Definition 8. An algorithm M is ( p , δ p ) differentially private if for any two datasets D, D differing in exactly one data point, and for all measurable sets O ⊆ Range(M), the following holds: Equivalently, a randomized algorithm M is said to be p differentially private ( In case of a graph G(V, E), we say that a randomized algorithm M that takes a graph G as an input, is p , if G and G differ in an edge and Eq. 7 holds true.

Appendix B Proofs of technical results in Section 3
Here, we first restate and prove the main result for privacy guarantee. Proof. Here u, A are fixed throughout and will be omitted when convenient. We need to prove that: where G u and G u differ in one edge but N (u) is the same in both. The reason is that, N (u) also specifies the output space (support of the recommendation). By definition, the addition or deletion of one edge changes the score s A (u, v|G) by at most ∆ A (G). I.e., Over the K iterations of Algorithm 1, let R 0 = ∅, R 1 , . . . , R K be the recommended node sets, where As A, G and u are fixed, we will shorthand s A (u, v|G) as ψ v for the rest of the proof. Recall that Next, we will upper and lower bound each of the terms and likewise For an upper bound on the second ratio, Inequality (1) is because ∆ uw ≤ ∆ A . Inequality (2) is due to Chebyshev's sum inequality (Fact 10), where we have Similarly, we obtain a lower bound on the second ratio as: From the above steps, B.2 Privacy guarantees of Algorithm 1 for common neighbors and Jaccard coeffcient Lemma 3. Given the conditions of Theorem 2, Algorithm 1 is p /2 differentially private for s CN and s JC .
Proof. We only argue for the common neighbors case. The argument for Jaccard coefficient is similar. Assume that an edge (v, y) ∈ E is present in E , with v ∈ N (u). Such an edge affects |N (u) ∩ N (v)| only if y ∈ N (u). Even then, it can change s CN (u, v) by one. Hence ∆ A = 1. To lighten the notation, we denote ψ v = s CN (u, v). As before, we seek to bound r k = log Note that, the value of ψ v only changes for the pair (u, v). For all other pairs, it remain the same. Thus, From item (1) in Fact 9, we have (2) (n + ∆ A + 1) σ (n + 2∆ A + 1) σ < (n + ∆ A + 1) σ (n + 2∆ A + 1) σ × k + (n + 2∆ A + 1) σ k + (n + ∆ A + 1) σ < 1. Fact 10 (Chebyshev sum inequality). If x w and y w are decreasing and increasing sequences respectively, then |R| w∈R x w y w < w∈R x w w∈R y w .
Appendix C Proof of technical results in Section 4 C.1 Proof of Proposition 4 Proof. Let the nodes ordered by decreasing s M u be u M 1 , . . . , u M K , . . .. We are not concerned with positions after K. Let the latent distances from u to these nodes be j , but this may not happen, in which case we assess a loss of (d uu M i − d uu M j ) 2 , following Negahban et al. [29]. This can be summed up as In such a case, C.2 Proof of Theorem 5 We apply Lemma 11 to prove these theorems. Recall that r is the threshold distance for an edge between two nodes in the latent space model and γ u (A, p ) is given as follows: Theorem 5. Define = 2 log(2/δ) |V| + 7 log(2/δ) 3(|V|−1) . With probability 1 − 4K 2 δ, we have Proof. Here, we show only the case of common neighbors. Others follow using the same method. We first define Note that E A ( γ u (A, p )) = γ u (A, p ). We first fix one realization of A for A = CN. Lemma 14). Now, given K N , 2rt Since f (x) = x 2/KD is a concave function in x for D ≥ 2, we apply Jensen inequality to have which immediately leads to the desired result.
C.3 Expected error in score due to Algorithm 1 is the largest score of a node, which is strictly less than the score of node u A i . Proof.

Appendix D Auxiliary Lemmas
In this section, we first provide a set of key auxiliary lemmas that will be used to derive several results in the paper. We first denote Further, let ω r (u, v) = ω r (v, u) be the common volume between D-dimensional hyperspheres centered around u and v.
Proof of (iii): Note that: 2Ω(r)−A(u,v) . We observe that: Inequality (2a) is due to decreasing nature of ω −1 r (.) (Proposition 13 (i)) and inequality (2b) is obtained by adding additional positive terms. Hence, Proof. (i) We have from [33] dA −1 u (y) We differentiate again and have Lemma 12 can be used to prove the corresponding bounds for different LR heuristics.
Proof. We only prove the case for (i), rests follow same methods. We define = + γ u (CN, p )/(2K|V|) From Lemma 11, we have which is less than 2rK − ω −1 r (2K ) with probability 1 − 2Kδ from Lemma 11, (i) Now, We aim to approximate the above quantity by for some suitable dimension A, which says that Inequality 4 is due to concavity of logarithmic function. Now, The quantity achieves maximum at → 0 when A ≥ KD. Then, All the other hyperparemeters are set as default in the corresponding software. The experiments are carried out using a Debian-9 OS with 4-core Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz machine having 8GB RAM. Except for embedding computations which are done using the codes available in respective github repositories, we wrote the rest of the codes-starting from sampling training graphs, score calculation to implementation of differentially private algorithms-in MATLAB R2017b.

E.3 Additional results
Here we present results for all differentially private algorithms on several LP protocols across all the datasets.