Federated Graph Analytics with Differential Privacy

Like previous works [7, 8, 9, 10, 14], the private information considered in this study is the edge privacy. We assume that the server knows the node information, i.e., $V=\{v_{1},...,v_{n}\}$, which makes sense in some real-world applications. For example, consider that the healthy administration is examining the spread of COVID-19 in a certain region. It collects the disease transmission paths according to the released census in this area.

Differential privacy (DP) [11, 12] has become a de-facto standard for preserving individual privacy, which can be formalized in Definition 1. In our work, we use global sensitivity [11] to achieve the DP, defined as Definition 2. It considers the maximum difference between statistic results on two neighboring graphs.

The Laplace mechanism is one of common techniques to achieve DP. The formal definition is as follows:

Existing locally differentially private models, such as edge local differentially privacy (Definition 4) [7, 9, 8] is a promising model. However, it fails to provide privacy guarantee in federated scenarios. While the same edge may exist in multiple different clients, each client only considers its own edge information. Multiple reports of the same information increase the probability of distinguishing such an edge multiple times, leading to privacy issues. To address this challenge, we introduce edge distributed differential privacy to achieve our privacy objectives. The formal definition is as follows:

Edge DDP guarantees that the server cannot distinguish the presence or absence of any edge based on all reports collected from clients. It also guarantees that the information about which client $C_{i}$ an edge in $E$ belongs to is private, if the edge exists. For example, in Figure 1(c), both the presence of the edge $\langle v_{2},v_{3}\rangle$ in $G$ and the absence of the edge $\langle v_{1},v_{6}\rangle$ in $G$ are private. Furthermore, no party knows that the edge $\langle v_{2},v_{3}\rangle$ belongs to clients $C_{2}$ even if the existence of $\langle v_{2},v_{3}\rangle$ has been disclosed.

Private Set Union (PSU) [21, 22, 23, 24] is a secure multiparty computation cryptographic technique designed for securely computing the union of private sets held by different parties. At its core, neither party reveals anything to the counterparty except for the elements in the union. From a high-level perspective, a typical PSU protocol involves the following steps: (1) Set Encoding: each party privately encodes its set into a cryptographic form suitable for secure computation: $[\![X_{i}]\!]\leftarrow\mathsf{Enc}(X_{i}),i\in[1,m]$. (2) Union Computation: parties engage in computing the union of their encoded sets without revealing the underlying elements: $[\![X]\!]\leftarrow\mathsf{Enc}(X_{1})\cup\mathsf{Enc}(X_{2})...\mathsf{Enc}(X_{m})$. (3) Result Decoding: once the computation is complete, parties decode the computed union from its cryptographic representation to obtain the set union: $X\leftarrow\mathsf{Dec}([\![X]\!])$.

Randomized response (RR) [11] is a common methodology for enhancing local differential privacy. However, it fails to provide $\varepsilon$-Edge DDP, as the same one edge could be reported by different clients multiple times. One edge may exist in multiple subgraphs. In the worst case, an edge is included by all subgraphs $G_{i},i\in[1,m]$. Without loss of generality, assume $G_{i}$ and $G_{i}^{\prime}$ are neighboring graphs and differ in edge $e_{1}$, we have $Pr[\mathcal{M}_{i}(G_{i})\in S_{i}]\leq e^{\epsilon}\cdot Pr[\mathcal{M}_{i}(G_{i}^{\prime})\in S_{i}]$. Then, we have

To address this privacy issue, we could consider the following baseline method. It divides the overall privacy budget into $m$ portions equally. Then each client randomizes each subgraph using the randomized response with $\varepsilon_{l}=\varepsilon/m$. As a result, the baseline can provide $\varepsilon$-Edge DDP, i.e.,

Algorithm 1 shows the details of the baseline approach. It takes as input the subgraph set $G=\{G_{1},...,G_{m}\}$ and privacy budget $\varepsilon$. Each graph $G_{i}$ is represented as a $n\times n$ adjacent matrix $M_{i}$, where each bit $\in\{0,1\}$. If there is an edge between two users, the bit will be set as 1; otherwise, it will be set as 0. After that, each client flips each bit in the upper triangular part of the matrix with the flipping probability $\frac{1}{1+\varepsilon_{l}}$, where $\varepsilon_{l}=\varepsilon/m$. After that, the server collects all noisy edges and aggregates an union as a noisy global graph $G^{\prime}$. Finally, the server computes the targeted graph statistics $f(G)^{\prime}$ based on the noisy global graph $G^{\prime}$. This algorithm is denoted as $\mathsf{Baseline}$.

Discussion. To provide a strong privacy guarantee, too small privacy budget is allocated to each client. Although the baseline approach achieves our privacy goal discussed in Section II, much redundant noise is added into results. For example, for $k$-star counting, $\mathsf{Baseline}$ obtains the expected $l_{2}$ loss errors of $O(\frac{(mn)^{2k-2}}{{\varepsilon}^{2}})$; For triangle counting, it attains the expected $l_{2}$ loss errors of $O(\frac{(mn)^{2}}{{\varepsilon}^{2}})$. Our experiments in Section V further shows that the baseline approach cannot obtain competitive result accuracy under various cases.

To alleviate the limitations of $\mathsf{Baseline}$ method, we propose a federated graph analytic framework, called $\mathsf{FEAT}$, as shown in Figure 2. It supports arbitrary downstream common graph statistics while satisfying $\varepsilon$-Edge DDP.

As discussed in the above section, one edge appears in $m$ clients in the extreme case and then the overall privacy budget $\varepsilon$ should be allocated to $m$ clients, i.e., $\varepsilon_{l}=\varepsilon/m$, which leads to much noise. In $\mathsf{FEAT}$, we leverage the private set union (PSU) technique [21, 22, 23, 24] to achieve $\varepsilon_{l}=\varepsilon$, reducing the noise scale. PSU allows parties to collaboratively compute the union of multiple sets held by different parties without revealing the individual elements of the sets to other parties. It guarantees that an element appears in the final union only once. However, previous PSU protocols cannot be easily applied in our FGA setting. Most of PSU works [21, 22, 24] focus on a two-party setting, which is different from our multi-party scenario. Although the paper [23] proposes a multi-party protocol, it faces the security and efficiency issue. Additionally, this multi-party PSU [23] outputs the true union and is unable to provide the differential privacy guarantee. To this end, we propose a differentially private set union protocol to compute the union of multiple subgraphs while satisfying $\varepsilon$-Edge DDP. The detailed analysis will be presented in Section III-C.

Algorithm 2 presents the overall protocol of $\mathsf{FEAT}$. It involves two kinds of entities: clients and a server. The local clients $C_{i}$, $i\in[m]$, owns a subgraph that is represented as a $n\times n$ adjacent matrix ($n$ is the number of users). It takes as input the set of subgraphs $G=\{G_{1},...,G_{m}\}$, privacy budget $\varepsilon$, and the targeted graph query $Q$. At the beginning, $\mathsf{FEAT}$ recalls a $\mathsf{CollectGraph}()$ function to collect a noisy global graph (step ①). Each client perturbs its subgraph with suitable noise and then encrypts the noisy subgraph. Next, clients communicate with each other to compute the union of subgraphs. All clients collaboratively decrypts the union and outputs a noisy global graph (details in Section III-C). Once obtaining the noisy global graph, it executes the targeted graph statistics (step ②). In this paper, we compute the subgraph counts (i.e., $k$-stars, triangles) to verify the effectiveness of our framework. Considering the estimation bias, the server further calibrates the noisy results to improve the utility (refer to Section III-D for details).

We propose a DPSU protocol based on the state-of-the-art PSU method for computing the global graph under DP.

PSU Protocol. Suppose that each client $C_{i\in[1,m]}$ owns a set $X_{i}\subseteq X=\{x_{1},...,x_{n}\}$. Our goal is to compute the union $X=\bigcup_{i=1}^{m}X_{i}$.

The SOTA multi-party PSU method [23] supports computing the union among multiple clients as follows:

However, the above protocol may face the security issue. It is implemented based on finite field cryptography (FFC) [29] and in fact the prime number $p$ with 512 bits is not secure according to Table 2 in [30]. If this multi-party PSU is implemented in a secure way, the prime number $p$ should be set as 3072 bits. As a result, it is inefficient for the large-scale graph analytics. To improve the tradeoff between security and efficiency, we implement the PSU protocol based on the Elliptic Curve Cryptography (ECC) [31], which is more efficient than finite field cryptography (FFC). In particular, there are three cryptographic libraries for implementing ECC, namely, Libsodium [32], OpenSSL [33], and MCL[34]. As shown in Table II, Libsodium is more suitable for processing large-scale graph data, which motivates us to implement PSU protocol based on Libsodium library.

DPSU Protocol. We then propose a differentially private set union (DPSU) protocol for aggregating a global graph. One challenge is that the output of the PSU protocol does not satisfy DP. The individual privacy could be disclosed via the union of subgraphs. Although some previous works [35, 36, 37, 38] discuss how to calculate the private set union while satisfying DP, their system models differ from ours and can not be used directly. One naive solution is that each client $C_{i}$ perturbs the flag vector $W_{i}$ using the randomized response (RR) mechanism [39] before encrypting. Specifically, each client $C_{i}$ flips each bit in her flag vector $W_{i}$ with probability $p=\frac{1}{1+e^{\varepsilon}}$ in the step Initialization of PSU protocol, where $\varepsilon$ is the privacy budget. Subsequently, the differentially private set union can be computed according to step (2)$\sim$(5) in the above PSU protocol.

Although this natural solution can provide the DP guarantee, it leads to much bias in a noisy graph. In fact, most of real-world graphs tend to be sparse, which means that there are much more 0s than 1s in an adjacent matrix. After the randomly flipping bits, however, the number of 1s is much larger than that of 0s, making the noisy global graph denser than the original one. Additionally, the step Modification further amplifies the denser problem. Even if ‘0’ bit is flipped into ‘1’ bit in one of $m$ subgraphs, the according bit in final union will become ‘1’. In particular, assume that the number of ‘1’ bits in a true global graph is $t$ and the number of ‘0’ bits is $(n^{2}-t)$. After flipping, the number of ‘1’ bits in a noisy global graph becomes $m[(1-p)t+p(n^{2}-t)]$. Take the Facebook graph as an example, which has 4,039 nodes (i.e., $n$) and 88,234 edges (i.e., $t$). Even with a fairly small privacy budget $\varepsilon=0.1$ and the number of clients $m=5$, the expected number of ‘1’ bits will become 3.8$\times 10^{7}$, increasing at least 439 times than before.

To address the above issue, we propose a novel differentially private set union protocol. In particular, ‘0’ bits are perturbed only by the first client and ‘1’ bits are randomized by all clients. The server can then obtain the whole noisy matrix by computing the union of them. Theoretically, our method can reduce the denser problem by a factor of $m$. As a result, the utility loss can be alleviated by at least a factor of $O(m^{2})$. For instance, for $k$-star counting, $\mathsf{FEAT}$ achieves the expected $l_{2}$ loss errors of $O(\frac{n^{2k-2}}{{\varepsilon}^{2}})$; For triangle counting, it attains the expected $l_{2}$ loss errors of $O(\frac{n^{2}}{{\varepsilon}^{2}})$. To further suppress the bias from the randomized response, we calibrate the noisy results during the graph query processing. The details will be discussed in next Section III-D.

Algorithm 3 describes the details of our DPSU-based edge collection method. It takes as input the subgraph set $G$ and the privacy budget $\varepsilon$. Each client $C_{i}$ initializes an edge domain $\mathbb{E}$ according to the node information $V$. In particular, each client $C_{i}$ first constructs a $n\times n$ adjacent matrix $M_{i}$, where $n=|V|$, and then transforms the upper triangular part of $M_{i}$ into a vector $\mathbb{E}$ with the size $N=|\mathbb{E}|=\frac{n(n-1)}{2}$. For example, $\mathbb{E}_{1}=e_{1}=\langle v_{1},v_{2}\rangle$, $\mathbb{E}_{2}=e_{2}=\langle v_{1},v_{3}\rangle$. The server initializes an empty set $E$ for collecting the edge information. Each client $C_{i}$ generates a pair of keys $\langle ps_{i},sk_{i}\rangle$, and all clients jointly generate the public key $pk$. Client $C_{i}$ first initializes a flag vector $Y$ according to the principle in line 5. If $\mathbb{E}_{j}$ exists in $E_{1}$, the according bit will be set as 1; otherwise, it will be set as 0. After, client $C_{1}$ perturbs each bit of $Y$ with the flipping probability $\frac{1}{1+e^{\varepsilon}}$ using the randomized response, and encrypts the noisy $Y^{\prime}$ with the public key $pk$. Then, client $C_{1}$ sends $\mathsf{Enc}(Y^{\prime})$ to the client $C_{2}$. For each client $C_{i}$ from $C_{2}$ to $C_{m}$, $C_{i}$ updates $\mathsf{Enc}(Y^{\prime})$ according to the principle in lines 10 to 15. If $\mathbb{E}_{j}$ is in $E_{i}$, client $C_{i}$ will flip ‘1’ with RR and then replace $\mathsf{Enc}(Y_{j}^{\prime})$ with $\mathsf{Enc}(\mathsf{RR}(1))$. Once the client $C_{m}$ completes updating $\mathsf{Enc}(Y^{\prime})$ and sending it to the server, all clients jointly decrypt $\mathsf{Enc}(Y^{\prime})$ and send decrypted $Y^{\prime}$ to the server. Finally, the server generates and releases $E$ according to $Y^{\prime}$. We call this algorithm by $\mathsf{CollectGraph}$.

Example 3.1. Table III shows how Algorithm 3 works for computing the union of local edge sets while satisfying the DP. Specially, clients $C_{1},C_{2},C_{3}$ owns private edge sets $E_{1}=\{e_{1},e_{2}\},E_{2}=\{e_{2},e_{3}\},E_{3}=\{e_{5}\}$, and node set is $V=\{v_{1},v_{2},v_{3},v_{4}\}$. Thus, $E_{1},E_{2},E_{3}\subseteq\mathbb{E}=\{e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\}$, where $e_{1}=\langle v_{1},v_{2}\rangle$, $e_{2}=\langle v_{1},v_{3}\rangle$, $e_{3}=\langle v_{1},v_{4}\rangle$, $e_{4}=\langle v_{2},v_{3}\rangle$, $e_{5}=\langle v_{2},v_{4}\rangle$, $e_{6}=\langle v_{3},v_{4}\rangle$. The goal is to compute $E=E_{1}\cup E_{2}\cup E_{3}$. Firstly, client $C_{1}$ constructs a flag vector $Y$ according to line 5 in Algorithm 3. Then, $C_{1}$ perturbs each bit of $Y$ and encrypts it to obtain $Y^{\prime}$. Secondly, clients $C_{2}$ and $C_{3}$ update $Y$ based on the principle of lines 10 to 15 in Algorithm 3. Thirdly, all clients jointly decrypt $\mathsf{Enc}(Y^{\prime})$ and send $Y^{\prime}$ to the server. Finally, the server can obtain the edge union $E=\{e_{1},e_{2},e_{4},e_{5}\}$ according to $Y^{\prime}$.

Proof of Theorem 2. Let $G=(V,E)$ and $G^{\prime}=(V,E^{\prime})$ be two neighboring graphs. Let $G_{i}$ and $G_{i}^{\prime}$ ($i\in[1,m]$) be the neighboring graphs of client $C_{i}$ with respect to $G$ and $G^{\prime}$, respectively. Let $\{\mathcal{M}_{i},i\in[1,m]\}$ be a set of randomized mechanisms with any subsets of possible outputs $S_{i}\subseteq range(\mathcal{M}_{i}),i\in[1,m]$. Given the privacy budget $\varepsilon$, we can easily obtain $Pr[\mathcal{M}_{i}(G_{i})\in S_{i}]\leq e^{\varepsilon}Pr[\mathcal{M}_{i}(G_{i}^{\prime})\in S_{i}]$. Due to using the threshold ElGamal encryption, any change of adding or deleting an edge from $m$ clients is only collected by the server once. Thus, we have

Therefore, Algorithm 3 satisfies $\varepsilon$-Edge DDP. Furthermore, by the immunity to post-processing [11], Algorithm 2 provides $\varepsilon$-Edge DDP guarantee. ∎

In this section, we execute two common subgraph counting queries, i.e., $k$-star counting [7, 9, 40] and triangle counting [4, 7, 41], in order to explain how to execute the $\mathsf{Query}$ function of Algorithm 2 and how to calibrate the noisy results.

A $k$-star refers to a subgraph consisting of a central node connecting to $k$ other nodes. To count the number of $k$-stars in a given graph, we iterate through each vertex in the graph and compute $\binom{d_{i}^{\prime}}{k}$, where $d_{i}^{\prime}$ is the noisy degree of node $v_{i}$. The $k$-star counts $S$ of the whole graph is equal to the summation of each node’s $k$-stars, i.e., $S=\sum_{i=1}^{n}\binom{d_{i}^{\prime}}{k}$. However, a direct computation of node degrees from $G^{\prime}$ can lead to significant bias induced by the randomized response in Algorithm 3. To mitigate the bias, we leverage the post-processing property of DP [11], yielding an unbiased estimation $\widetilde{d_{i}}$ of $d_{i}$ as Proposition 1. Hence, we can obtain an unbiased estimation of $k$-stars, i.e., $S=\sum_{i=1}^{n}\binom{\widetilde{d_{i}}}{k}$.

Proof of Proposition 3. The mapping relationship between $d_{i}^{\prime}$ and $\widetilde{d_{i}}$ can be represented as:

Then we can prove Proposition 3. ∎

A triangle in a graph refers to a subgraph consisting of three nodes connected by three edges, forming a closed loop. To count the number of triangles in a graph, one common approach is to iterate each subgraph with three nodes and check if it is a loop. However, simply counting the triangles in a noisy graph $G^{\prime}$ introduces a significant bias. We continue to calibrate the biased triangle counts through the post-processing. Building upon the insights of [7], we categorize triplets in $G_{i}$ into four types based on the number of edges they involve: $t_{0}$, $t_{1}$, $t_{2}$, and $t_{3}$, where $t_{j}$ ($j\in{0,1,2,3}$) represents the count of triplets in $G_{i}$ involving $j$ edges (referred to as $j$-edge; $3$-edges are identical to triangles). Thus, we can compute the unbiased triangle counts $\widetilde{T}$ according to Proposition 2.

Proof of Proposition 2. Let $u_{0},u_{1},u_{2},u_{3}$ be the number of 0-edges, 1-edges, 2-edges, and triangles in $G$, respectively, when we do not flip 1/0 using the randomized response. Let $x=e^{\varepsilon}$. Then we have:

$\bm{A}=\frac{1}{(x+1)^{2}}\begin{bmatrix}x^{3}&3x^{2}&3x&1\\ x^{2}&x^{3}+2x&2x^{2}+1&x\\ x&2x^{2}+1&x^{3}+2x&x^{2}\\ 1&3x&3x^{2}&x^{3}\end{bmatrix}$.

$\bm{A}$ is a transition matrix from a type of subgraph (0-edge, 1-edge, 2-edge, and triangle) in an original graph to a type of subgraph in a noisy graph. Let ($\widetilde{u}_{0},\widetilde{u}_{1},\widetilde{u}_{2}$, $\widetilde{u}_{3}$) be an unbiased estimate of ($u_{0},u_{1},u_{2},u_{3}$). Then we obtain:

Let $\bm{A}_{i,j}^{-1}$ be the $(i,j)$-th element of $\bm{A}^{-1}$. Then we have:

By combining above equations, Proposition 2 is proved. ∎

Algorithm 4 presents the overall protocol of $\mathsf{FEAT}$+. It mainly consists of two phases: global graph collection and local query collection. The global graph collection is used to publish a noisy global graph $G^{\prime}$, which is finished by $\mathsf{FEAT}$ (Algorithm 2). The local query collection consists of three main steps: degree-based partition (Algortihm 5), graph query processing (Section IV-C), and perturbation. To be specific, it takes as input local subgraph set $G=\{G_{1},...,G_{m}\}$, privacy budget $\varepsilon=\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}$, and query sensitivity $\triangle$. $\mathsf{FEAT}$+ first collects a noisy global graph $G^{\prime}$ via $\mathsf{FEAT}$ using $\varepsilon_{1}$. Then, this global graph is published to each client $C_{i}$ for local query collection. Next, $\mathsf{FEAT}$+ recalls a $\mathsf{PartitionNode}$ function with privacy budget $\varepsilon_{2}$, to split the node set $V$ into $m$ disjoint node sets $U$ (Step 1). These node sets are distributed to the respective clients. After that, each client $C_{i}$ computes the targeted query. In our paper, we take $k$-star and triangle counting as examples to explain the rationale behind $\mathsf{Query}$ (Step 2). Since the noisy global graph $G^{\prime}$ is dense, we carefully design calibration techniques to obtain unbiased estimates of $k$-stars or triangles, as presented in Section IV-C. Upon obtaining the query results, each client $C_{i}$ perturbs the local answers using a suitable noise (Step 3). Specifically, each client $C_{i}$ calculates the noisy query $Q_{i}^{\prime}=Q_{i}+\mathsf{Lap}(\frac{\triangle}{\varepsilon_{3}})$ by adding the Laplacian noise to $Q_{i}$, where $\triangle$ is the global sensitivity. Finally, the server computes $Q^{\prime}\leftarrow\sum_{i=1}^{m}Q_{i}^{\prime}$, which is an unbiased estimate of $Q$ and satisfies DP.