Novel FDP mechanisms for releasing bipartite graph data on fixed and infinite intervals

Abstract

As data collection increases, more and more sensitive data is being used to publish query results. This creates a significant risk of privacy disclosure. As a mathematically provable privacy theory, differential privacy (DP) provides a tool to resist background knowledge attacks. Fuzzy differential privacy (FDP) generalizes differential privacy by employing smaller sensitivity and supporting multiple similarity measures. Thus the output error can be reduced under FDP. Existing FDP mechanisms employ sliding window strategy, which perturb the true query value to an interval with this value as the midpoint to maintain similarity of outputs from neighboring datasets. It is still possible for an attacker to infer some sensitive information based on the difference between the left and right endpoints of the output range. To address this issue, this article present two solutions: fixed interval perturbation and infinite interval perturbation. These strategies perturb the true query values of two neighboring datasets to the same interval and provide fuzzy differential privacy protection for the dataset. We apply the proposed method to the privacy-preserving problem of bipartite graph subgraph counting and verify the effectiveness by experiments.

Keywords

Fuzzy differential privacy privacy protection subgraph counting bicliques

1 Introduction

Due to the development of the Internet, the dramatic growth in the number of various terminals, including smartphones, has made it necessary for various companies and organizations, as well as governments, to collect and analyze huge amounts of data. In this process, privacy protection regarding personal information has become a big issue. How to protect private data and prevent the leakage of sensitive data information has become the focus of research in the field of data security.

Fig. 1

From left to right, perturbation strategies of outputs are bounded interval (sliding window), fixed interval and infinite interval.

Existing privacy protection technologies mainly include k-anonymous [35], l-diversity [24], t-closeness [22], ε-differential privacy (DP) [9] and (S, s)-fuzzy differential privacy (FDP) [18]. K-anonymity is usually achieved by masking or generalizing some fields in a data table. It cannot prevent attribute disclosure when there is little diversity. L-diversity is a privacy criterion which can defend against homogeneity attacks and some degree of background knowledge attacks. However, it requires that there exists at least l well-represented values for each sensitive attribute which restricts its use. T-closeness improves this shortcoming by defining that the distance between the two distributions should be no more than a threshold t. Differential privacy is a privacy protection mechanism, which defines privacy by adding random noise to the query results when sharing data and prevents attacks based on background knowledge. As differential privacy has strong mathematical guarantees, it attracts increasing attention [3 , 37]. The application fields of DP include recommender systems, location-based systems and social networks [21 , 42]. Many scholars have summarized its research progress [10–13 , 44].

However, in differential privacy, the sensitivities of many queries are set very large for defending against differential attacks 1 In this case, the output errors will increase with increasing query sensitivities and the noise can even completely mask the true query value. As a generalization of DP, fuzzy differential privacy [18] is proposed to acquire a more flexible trade-off between the accuracy of outputs and the privacy-preserving level of data by employing smaller sensitivities and multiple similarity measures.

1.1 Motivation

The authors in paper [18] supply triangular FDP mechanisms and curved triangular FDP mechanisms which perturb outputs on bounded sliding intervals (i.e., intervals with different midpoints D, D′ and the same radius), see Fig. 1(a). Our concerns focus on getting a more privacy-protective and comprehensive model in the FDP framework. However, bounded sliding FDP model has a weakness that can be attacked. Precisely, for neighboring data sets D and D′, if the output obtained by the attacker is located in the part of the red dot, it can be inferred that the result originates from D. If the output obtained by the attacker is located in the part of the blue dot, it can be inferred that the result originates from D′. It means that existing fuzzy differential privacy mechanisms have weaknesses in the protection of values near the endpoints of the interval. This motivates us to design more secure FDP mechanisms to output results on the same interval.

Fig. 2

Diagram of FDP mechanism on fixed and infinite interval.

1.2 Contributions

There are two feasible solutions, one for the same finite interval, named fixed interval, and one for an infinite interval. They are shown in Fig. 1(b) and Fig. 1(c), respectively. In this article, we propose novel FDP mechanisms supporting perturbations on fixed intervals and infinite intervals, which are illustrated in Fig. 1. We prove that the mechanisms and the corresponding fuzzy similarity measure are compatible, thus satisfying the conditions of FDP. The proposed FDP mechanisms are used to solve private subgraph counting problem in bipartite graphs and the effectiveness of the method is verified on real-world datasets.

1.3 Related work

Privacy-preserving data releasing has received increasing interest in various social network application fields. The authors in papers [5, 17] present automorphically equivalent and k-automorphism framework for privacy preserving network publication defending against multiple attacks (such as 1-neighbor-graph attack, degree attack). To address the privacy protection issues in bipartite graphs, the authors in papers [7, 8] present bipartite anonymity method based on classic anonymity techniques. The authors in paper [43] protect privacy by generalizing the original graph to super-nodes and super-edges. The authors in paper [36] use weighted bipartite graphs to model high-dimensional sparse data and achieve privacy preservation by clustering node attributes. The authors in paper [6] present a privacy-preserving bipartite graph matching framework for multimedia analysis and retrieval. The authors in paper [14] give a privacy-preserving solution for the bipartite ranking problem by employing homomorphic encryption and secure multi-party computation. The authors in paper [29] investigate privacy-preserving wireless communication methods using bipartite matching. The authors in paper [31] present the privacy preserving method of 2-party queries on bipartite graphs using private set intersection. Fundamental privacy limits are studied for bipartite networks under active attacks in [33]. The authors in paper [45] present differential privacy mechanisms for multi-agent systems with bipartite consensus over signed digraph. Differential privacy preservation for the subgraph counting (e.g. biclique counting) problem in bipartite graphs has not been investigated to date.

2 Preliminaries

Fuzzy set theory is a generalization of classical set theory. In classical set theory, elements either belong to a set or they do not. In fuzzy set theory, the degree to which an element belongs to a set takes values between 0 and 1. Since its establishment in 1965, fuzzy set theory [40] has a wide range of applications in management science, artificial intelligence, cybernetics, decision theory, and data analysis. In this section, we introduce several basic concepts in fuzzy sets, fuzzy differential privacy in order to facilitate a clear exposition of the proposed approach. In addition, some basic definitions of the subgraph counting problem in graph data query are presented for studying the privacy protection of bipartite graphs.

2.1 Fuzzy sets

Definition 2.1. [Fuzzy set [40]] Let X be a set and m : X → [0, 1] be a membership function. A fuzzy set $\tilde{A}$ is a pair (X, m). X is called the universe of discourse and m (x) , (x ∈ X) , is called the grade of membership of x in $\tilde{A} = (X, m)$ . $m = μ_{\tilde{A}} (x)$ is called the membership function of the fuzzy set $\tilde{A}$ .

All fuzzy sets on X is denoted by F (X). The equality and containment relationships of two fuzzy sets $\tilde{A}, \tilde{B} \in F (X)$ , are defined as: $\begin{matrix} \tilde{A} = \tilde{B} & \Leftrightarrow μ_{\tilde{A}} (x) = μ_{\tilde{B}} (x), \forall x \in X; \\ \tilde{A} \subset \tilde{B} & \Leftrightarrow μ_{\tilde{A}} (x) \leq μ_{\tilde{B}} (x), \forall x \in X . \end{matrix}$ The fuzzy similarity measure can be used to measure the degree of similarity between two fuzzy sets. There are various definitions of fuzzy similarity measures, and the following one is used in this article.

Definition 2.2. [Fuzzy similarity measure [30]] The function S : F (X) × F (X) → [0, 1] is a fuzzy similarity measure if it satisfies the following conditions:

1. $\forall \tilde{A}, \tilde{B} \in F (X), S (\tilde{B}, \tilde{A}) = S (\tilde{A}, \tilde{B})$ ;

2. $\forall \tilde{A}, \tilde{B} \in F (X), 0 \leq S (\tilde{A}, \tilde{B}) \leq 1$ ;

3. $S (\tilde{A}, \tilde{B}) = 1$ if and only if $\tilde{A} = \tilde{B}$ ;

4. $\forall \tilde{A}, \tilde{B}, \tilde{C} \in F (X), if \tilde{A} \subset \tilde{B} \subset \tilde{C}, thenS (\tilde{A}, \tilde{C}) \leq min (S (\tilde{A}, \tilde{B}), S (\tilde{B}, \tilde{C}))$ ;

5. For two nonempty fuzzy sets $\tilde{A}, \tilde{B} \in F (X)$ , if $S (\tilde{A}, \tilde{B}) = 0$ , then $min (μ_{\tilde{A}} (x), μ_{\tilde{B}} (x)) = 0, \forall x \in X$ .

2.2 Differential privacy

Dwork et al. [9] demonstrate that it is impossible to absolutely prevent the leakage of privacy, mainly due to the usefulness requirement. As long as data needs to be used, it will inevitably lead to information leakage.

Therefore, the remaining possibility is how to limit relative privacy leakage as much as possible, and this is where "difference" comes in: any query result should not be able to be used to infer, to a certain extent, whether an individual’s data is included in the dataset D. This is reflected in the definition of "neighboring datasets". A pair of neighboring datasets is one in which two datasets (D, D′) differ by only one record, denoted by d (D, D′)) =1. A differential attack is a type of attack that infers information about the original dataset by analyzing the query values corresponding to neighboring datasets. Differential privacy is a privacy-preserving approach to resist differential attacks defined as the degree to which neighboring datasets are indistinguishable. This methodology works by applying certain perturbations to the query results so that the output results corresponding to adjacent data sets are similar.

2.3 Fuzzy differential privacy

Fuzzy differential privacy (FDP) [18] maintains the similarity of the corresponding outputs of neighboring datasets by outputting the query results to fuzzy sets. FDP uses the degree of similarity of fuzzy sets to indicate the degree to which the query results are perturbed and also the level that the model protects privacy.

Definition 2.3. [Fuzzy Differential Privacy [18]] Let $D$ denote a class of data. $D \in D$ is a given data set. All possible outputs of a query function f comprise the universe of discourse X, $f : D \to X$ . A fuzzy mapping $\tilde{f} : D \to F (X)$ outputs fuzzy sets $\tilde{f} (D)$ in F (X). S : F (X) × F (X) → [0, 1] is a fuzzy similarity measure. The fuzzy algorithm $\tilde{f}$ is (S, s₀)- fuzzy differentially private on D, if for any pair of subset neighboring data sets $(D_{0}, D_{0}^{'})$ , we have

$S (\tilde{f} (D_{0}), \tilde{f} (D_{0}^{'})) \geq s_{0}, (0 \leq s_{0} \leq 1),$

and s₀ is called similarity level. Note: A pair of subset neighboring data sets refers to a pair of neighboring data sets that at least one of the two $(D_{0}, D_{0}^{'})$ is included in D.

Definition 2.4. [Compatibility Principle [18]] Let $D$ denote a class of data. $D \in D$ is a given data set. All possible outputs of a query function f comprises the universe of discourse X, $f : D \to X$ . A fuzzy mapping $\tilde{f} : D \to F (X)$ outputs fuzzy sets $\tilde{f} (D)$ in F (X). S : F (X) × F (X) → [0, 1] is a fuzzy similarity measure. The fuzzy algorithm $\tilde{f}$ and fuzzy similarity measure S are compatible on D, if for all D₀ ⊂ D, : $S (\tilde{f} (D), \tilde{f} (D^{'})) \leq S (\tilde{f} (D_{0}), \tilde{f} (D_{0}^{'})),$ (1) in which d (D, D′) =1 and $d (D_{0}, D_{0}^{'}) = 1$ .

Definition 2.5. [Semi-global Sensitivity [18]] D is a data set. The semi-global sensitivity of f on D is defined as: $\begin{matrix} {SGS}_{f} (D) = max_{D_{0} \subset D} | f (D_{0}) - f (D_{0}^{'}) | \end{matrix}$ where $(D_{0}, D_{0}^{'})$ is a pair of neighboring data sets.

Definition 2.6. [Local Sensitivity [27]] Let f be a function that maps a graph G to a real number (f : g ↦ r, g ⊂ G, r ∈ R). The local sensitivity of f, denoted by LS_f (G), is defined as ${LS}_{f} (G) = max_{G^{'} : d (G, G^{'}) = 1} | f (G) - f (G^{'}) |$ (2) where G,G′ are neighboring.

Definition 2.7. [Monotone incremental query [18]] $D$ is a class of data sets. A query $f : D \to R$ is monotonically increasing, provided that $\forall D_{1}, D_{2} \in D, D_{1} \subset D_{2}$ : f (D₁) ≤ f (D₂). $f : D \to R$ is also called a monotone incremental query.

Definition 2.8. [Conjugate neighboring data sets [18]] $D$ is a class of data sets. $\forall D_{1}, D_{2} \in D, D_{1}^{'} : d (D_{1}, D_{1}^{'}) \leq 1, D_{2}^{'} : d (D_{2}, D_{2}^{'}) \leq 1$ . $D_{1}^{'}, D_{2}^{'}$ are conjugate neighboring data sets of D₁, D₂, if $D_{1} Δ D_{1}^{'} = D_{2} Δ D_{2}^{'}$ , in which Δ represents the symmetry difference of two sets, e.g. AΔB = {x| (x ∈ A) XOR (x ∈ B)}. It means that $D_{1}^{'}, D_{2}^{'}$ are generated by editing (adding or deleting) the same element.

Proposition 2.9. [ [18]] If $D_{1}, D_{2} \in D : D_{1} \subset D_{2}$ , for each $D_{1}^{'} : d (D_{1}, D_{1}^{'}) \leq 1$ , there exists $D_{2}^{'} : d (D_{2}, D_{2}^{'}) \leq 1$ , s.t. $D_{1}^{'}, D_{2}^{'}$ are conjugate neighboring data sets of D₁, D₂.

Definition 2.10. [Difference-incremental query [18]] $D$ is a class of data sets. A monotone incremental query $f : D \to R$ is differentially increasing, provided that $\forall D_{1}, D_{2} \in D : D_{1} \subset D_{2}$ , $| f (D_{1}) - f (D_{1}^{'}) | \leq | f (D_{2}) - f (D_{2}^{'}) |,$ in which $D_{1}^{'}, D_{2}^{'}$ are conjugate neighboring data sets of D₁, D₂. $f : D \to R$ is also called a difference-incremental query.

Lemma 2.11. [ [18]] Suppose that $D$ is a class of data sets and $f : D \to R$ is a difference-incremental query. $\forall D_{1}, D_{2} \in D : D_{1} \subset D_{2}$ , we have ${LS}_{f} (D_{1}) \leq {LS}_{f} (D_{2}) .$

Proposition 2.12. [ [18]] $D$ is a class of data sets. Let $f : D \to R$ be a monotone incremental query. We have ${LS}_{f} (D) = {SGS}_{f} (D), \forall D \in D .$

Fig. 3

Examples of (2, 2)-biclique and (2, 3)-biclique.

2.4 Subgraph counting in bipartite graph

This section introduces an important type of query for graph data (also called network data)-subgraph counting. Subgraph counting is a basic statistical method in data querying, data mining and social networking, which refers to counting subgraphs with a given type in the input graph. Suppose the given graph dataset is G = (V, E) and g = (V₀, E₀) is a subgraph of G. The subgraph counting query f_g (G) returns the number of all subgraphs in graph G that are isomorphic to g 2 In the case where the subgraph structure g is determined without ambiguity, f_g (G) is also often abbreviated to f (G).

Bipartite graphs are a special type of graph whose vertices can be partitioned into two disjoint and independent sets such that each edge connects two vertices from different sets. They are commonly used to model the relationship between two different types of objects and are widely used in various fields, such as social networks and economics [2, 15].

Let G = (U, V, E) denote a bipartite graph which can be divided into two disjoint vertex sets U, V and that edges in E connect one vertex in U with one vertex in V, i.e., E = {(u, v) |u ∈ U, v ∈ V, U ∩ V = ∅}, where ∩ denotes the intersection of two sets and ∅ denotes the empty set. A biclique, which is also called a complete bipartite subgraph, is a special kind of bipartite graph where every vertex in U is connected to every vertex in V. We use (a, b)-biclique to denote bicliques with |U| = a, |V| = b, where | · | denotes the cardinality of a set. In Fig. 1(left part), we show a (2, 2)-biclique, also called a butterfly (rectangle), in which U = {u₁, u₂} , V = {v₁, v₂} and E = {(u₁, v₁) , (u₁, v₂) , (u₂, v₁) , (u₂, v₂)}. We also show a (2, 3)-biclique in the right part of Fig. 1.

Example 2.13. Let f₂₂ (G) denote the (2, 2)-biclique counting on a bipartite graph G, as shown in Fig. 1.2 and f₂₃ (G) denote the (2, 3)-biclique counting. We have f₂₂ (G) =7 and f₂₃ (G) =2.

Fig. 4

Examples of (2, 2)-biclique and (2, 3)-biclique counting.

3 FDP on fixed and infinite intervals

Due to existing fuzzy differential privacy mechanisms have weaknesses in the protection of values near the endpoints of the interval. We design FDP mechanisms to output results on fixed intervals and infinite intervals.

3.1 FDP on fixed intervals

Existing FDP mechanisms are designed for bounded sliding intervals which are compatible with fuzzy similarity measures. In many practical applications, query results have a relatively small fixed range such as querying the average age of specific populations in demographic data. In this case, outputs on sliding window will bring security weaknesses near interval endpoints, as shown in the left part of Fig. 1. However, existing FDP mechanisms with fuzzy similarity measures can not be directly used on fixed interval, due to compatibility. To solve this problem, we design a new fuzzy similarity measure S^★ and construct fuzzy mapping ${\tilde{f}}_{γ}$ , which is compatible to S^★.

Suppose that the fixed output range is [a, b]. The fuzzy mapping ${\tilde{f}}_{γ}, (γ > 0)$ is defined as follows.

$\forall D \subset D$ , $μ_{{\tilde{f}}_{γ} (D)} (x) = {\begin{matrix} \frac{exp (- \frac{1}{γ} (f (D) - x)) - 1}{1 - exp (- \frac{1}{γ} (f (D) - a))} + 1, \\ a \leq x \leq f (D), \\ ∥ \frac{exp (- \frac{1}{γ} (x - f (D))) - 1}{1 - exp (- \frac{1}{γ} (b - f (D)))} + 1, \\ f (D) < x \leq b . \end{matrix}$

The following fuzzy similarity measure S^★ is designed for the collection of fuzzy sets which produced by the fuzzy mapping ${\tilde{f}}_{γ}, (γ > 0)$ .

Theorem 3.1.S^★ is fuzzy similarity measure on set $\tilde{f} (D) = {{\tilde{f}}_{γ} (D) | D \subset D, γ > 0}$ .

∀γ₁, γ₂ > 0, and $D_{1}, D_{2} \subset D$ ,

$\begin{matrix} S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) \\ = exp (- (\frac{1}{b - a} | γ_{1} - γ_{2} | + \frac{2 | f (D_{1}) - f (D_{2}) |}{(γ_{1} + γ_{2}) (b - a)})) \end{matrix}$

Proof. $\forall {\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2}), {\tilde{f}}_{γ_{3}} (D_{3}) \in \tilde{f} (D) :$

(1) $S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) = S^{★} ({\tilde{f}}_{γ_{2}} (D_{2}), {\tilde{f}}_{γ_{1}} (D_{1}))$ ;

(2) $0 \leq S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) \leq 1$ ;

(3) If $S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) = 1$ , then we have γ₁ = γ₂, ${\tilde{f}}_{γ_{1}} (D_{1}) = {\tilde{f}}_{γ_{1}} (D_{2})$ . Hence, $μ_{{\tilde{f}}_{γ_{1}} (D_{1})} (x) = μ_{{\tilde{f}}_{γ_{2}} (D_{2})} (x)$ and ${\tilde{f}}_{γ_{1}} (D_{1}) = {\tilde{f}}_{γ_{2}} (D_{2})$ ;

(4) If ${\tilde{f}}_{γ_{1}} (D_{1}) \subset {\tilde{f}}_{γ_{2}} (D_{2}) \subset {\tilde{f}}_{γ_{3}} (D_{3})$ , then f₁ (D₁) = f₂ (D₂) = f₃ (D₃) and γ₁ ≤ γ₂ ≤ γ₃. We have $\begin{matrix} S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) \\ = exp (- \frac{γ_{2} - γ_{1}}{b - a}) \\ \geq exp (- \frac{γ_{3} - γ_{1}}{b - a}) \\ = S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{3}} (D_{3})) . \end{matrix}$

(5) $S^{★} ({\tilde{f}}_{γ_{1}} (D_{1}), {\tilde{f}}_{γ_{2}} (D_{2})) > 0$ always holds.

According to Definition 2.2, S^★ is a fuzzy similarity measure on set $\tilde{f} (D) = {{\tilde{f}}_{γ} (D) | D \subset D, γ > 0}$ .□

Note: If we use the same γ in outputting fuzzy sets, the similarity degree increases with distance |f (D₁) - f (D₂) | decreasing (see Fig. 3) and increases with γ increasing (see Fig. 4). These facts fit human intuition.

Fig. 5

An example of |f (D₁) - f (D₂) | < |f (D₁) - f (D₃) | and $S^{★} (\tilde{f} (D_{1}), \tilde{f} (D_{2})) > S^{★} (\tilde{f} (D_{1}), \tilde{f} (D_{3}))$ .

Fig. 6

An example of γ₁ < γ₂ and $S^{★} (\tilde{f_{γ_{1}}} (D_{1}), \tilde{f_{γ_{1}}} (D_{2})) < S^{★} (\tilde{f_{γ_{2}}} (D_{1}), \tilde{f_{γ_{2}}} (D_{2}))$ .

Theorem 3.2. D is a data set. The fuzzy algorithm ${\tilde{f}}_{γ}$ and fuzzy similarity measure S^★ are compatible on D.

Proof.

For ∀D₀ ⊂ D, $| f (D_{0}) - f (D_{0}^{'}) | \leq | f (D) - f (D^{'}) |$ , $\begin{matrix} S^{★} ({\tilde{f}}_{γ} (D_{0}), {\tilde{f}}_{γ} (D_{0}^{'})) \\ = & exp (- \frac{| f (D_{0}) - f (D_{0}^{'}) |}{γ (b - a)}) \\ \geq & exp (- \frac{| f (D) - f (D^{'}) |}{γ (b - a)}) \\ = & S^{★} ({\tilde{f}}_{γ} (D_{0}), {\tilde{f}}_{γ} (D_{0}^{'})) . \end{matrix}$ Thus, ${\tilde{f}}_{γ}$ and fuzzy similarity measure S^★ are compatible on D.□

Theorem 3.3.D is a data set. Let $f : D \to R$ be a query. The fuzzy algorithm ${\tilde{f}}_{γ}$ is (S^★, s₀)- fuzzy differentially private (0 < s₀ < 1), provided that $γ \geq \frac{{SGS}_{f} (D)}{- ln s_{0} (b - a)}$ .

Proof.

For any pair of neighboring data set $(D_{0}, D_{0}^{'})$ , (D₀ ⊂ D), we have $\begin{matrix} S^{★} (\tilde{f_{γ}} (D_{0}), \tilde{f_{γ}} (D_{0}^{'})) \\ = exp (- \frac{| f (D_{0}) - f (D_{0}^{'}) |}{γ (b - a)}) \\ \geq exp (\frac{| f (D_{0}) - f (D_{0}^{'}) |}{{SGS}_{f} (D)} ln s_{0}) . \end{matrix}$

Note that SGS_f (D) is the semi-global sensitivity. By Definition 2.5, we have ${SGS}_{f} (D) \geq | f (D_{0}^{'}) - f (D_{0}) |, (\forall D_{0} \subset D) .$ Hence, $S^{★} (\tilde{f_{γ}} (D_{0}), \tilde{f_{γ}} (D_{0}^{'})) \geq s_{0} .$ That means $\tilde{f_{γ}}$ is (S^★, s₀)-FDP.□

Note: We can also construct other mechanisms to be compatible with S^★ according to $\tilde{f}$ in previous sections. Due to space limitations, it’s not described here.

3.2 FDP on infinite intervals

FDP protects privacy by designing membership functions of fuzzy outputs according to fuzzy similarity measures and a user specified similarity level s₀. In this section, we present a variety of mechanisms which support various types of perturbation intervals and strategies under S, as a typical example (See Definition 2.4). In line with DP framework, we fist design mechanisms on infinite intervals.

Definition 3.4. [Fuzzy similarity measure [28]] Suppose that $\tilde{A}$ and $\tilde{B}$ are two fuzzy sets. The fuzzy similarity measure S is defined as: $S (\tilde{A}, \tilde{B}) = 1 - max_{x_{i}} (| μ_{\tilde{A}} (x_{i}) - μ_{\tilde{B}} (x_{i}) |) .$ Theorem 3.5. [Power mechanism] $D$ is a class of data sets. Suppose that $D \in D$ is the current data set to protect. Let $f : D \to R$ be a query. The fuzzy algorithm $\tilde{f_{1}} : D \to F (R)$ is defined as: $\forall D_{0} \in D$ , $\begin{matrix} μ_{\tilde{f_{1}} (D_{0})} (x) \\ = (\frac{| x - f (D_{0}) |}{γ} + 1)^{- η}, (- \infty < x < + \infty), \end{matrix}$ in which η > 1 is a specified parameter. For any 0 < s₀ < 1, $\tilde{f}$ is (S, s₀)-FDP, provided that, $γ \geq \frac{{SGS}_{f} (D)}{s_{0}^{- \frac{1}{η}} - 1} .$

Proof. Suppose that D₁ ⊂ D. For any pair of neighboring data set $(D_{1}, D_{1}^{'})$ , we have $\begin{matrix} S (\tilde{f_{1}} (D_{1}), \tilde{f_{1}} (D_{1}^{'})) \\ = 1 - max_{x} | μ_{\tilde{f_{1}} (D_{1})} (x) - μ_{\tilde{f_{1}} (D_{1}^{'})} (x) | \\ = 1 - max_{x} | (\frac{| x - f (D_{1}) |}{γ} + 1)^{- η} \\ - (\frac{| x - f (D_{1}^{'}) |}{γ} + 1)^{- η} | \\ = 1 - (1 - (\frac{| f (D_{1}^{'}) - f (D_{1}) |}{γ} + 1)^{- η}) \\ = (\frac{| f (D_{1}^{'}) - f (D_{1}) |}{γ} + 1)^{- η} \\ \geq (\frac{| f (D_{1}^{'}) - f (D_{1}) |}{{SGS}_{f} (D_{1})} (s_{0}^{- \frac{1}{η}} - 1) + 1)^{- η} \\ \geq s_{0} . \end{matrix}$ We prove the following inequality:

$S_{1} (\tilde{f_{1}} (D_{1}), \tilde{f_{1}} (D_{1}^{'})) \geq s_{0} .$ (3)

That means $\tilde{f}$ is (S₁, s₀)-FDP.□

In a similar way, we can prove the following theorems.

Theorem 3.6. [Linear exponential mechanism] D is a data set. Let $f : D \to R$ be a query. The fuzzy algorithm $\tilde{f_{2}} : D \to F (R)$ is defined as: $\forall D_{0} \in D$ , $\begin{matrix} μ_{\tilde{f_{2}} (D_{0})} (x) \\ = exp (- | \frac{x - f (D_{0})}{γ} |), (- \infty < x < + \infty) . \end{matrix}$ For any 0 < s₀ < 1, $\tilde{f}$ is (S₁, s₀)-FDP, provided that, $γ \geq \frac{{SGS}_{f} (D)}{- ln s_{0}} .$

Theorem 3.7. [Quadratic exponential mechanism] D is a data set. Let $f : D \to R$ be a query. The fuzzy algorithm $\tilde{f_{3}} : D \to F (R)$ is defined as: $\forall D_{0} \in D$ , $\begin{matrix} μ_{\tilde{f_{3}} (D_{0})} (x) \\ = exp (- (\frac{x - f (D_{0})}{γ})^{2}), (- \infty < x < + \infty) . \end{matrix}$ For any 0 < s₀ < 1, $\tilde{f}$ is (S₁, s₀)-FDP, provided that, $γ \geq \frac{{SGS}_{f} (D)}{\sqrt{- ln s_{0}}} .$

Theorem 3.8. [Superlinear exponential mechanism] D is a data set. Let $f : D \to R$ be a query. The fuzzy algorithm $\tilde{f_{4}} : D \to F (R)$ is defined as: $\forall D_{0} \in D$ , $\begin{matrix} μ_{\tilde{f_{4}} (D_{0})} (x) \\ = exp (- | \frac{x - f (D_{0})}{γ} |^{1 + η}), (- \infty < x < + \infty), \end{matrix}$ in which 0 < η < 1 is a specified parameter. For any 0 < s₀ < 1, $\tilde{f}$ is (S₁, s₀)-FDP, provided that, $γ \geq \frac{{SGS}_{f} (D)}{(- ln s_{0})^{\frac{1}{1 + η}}} .$

Theorem 3.9. [Sublinear exponential mechanism] D is a data set. Let $f : D \to R$ be a query. The fuzzy algorithm $\tilde{f_{5}} : D \to F (R)$ is defined as: $\forall D_{0} \in D$ , $\begin{matrix} μ_{\tilde{f_{5}} (D_{0})} (x) = & exp (- | \frac{x - f (D_{0})}{γ} |^{1 - η}), \\ (- \infty < x < + \infty), \end{matrix}$ in which 0 < η < 1 is a specified parameter. For any 0 < s₀ < 1, $\tilde{f}$ is (S₁, s₀)-FDP, provided that, $γ \geq \frac{{SGS}_{f} (D)}{(- ln s_{0})^{\frac{1}{1 - η}}} .$

Fig. 7

Membership functions of various fuzzy mapping corresponding to f (D) and f (D′) on infinite intervals. η = 3 in ${\tilde{f}}_{1}$ and η = 0.5 in ${\tilde{f}}_{4}$ , ${\tilde{f}}_{5}$ .

4 FDP subgraph counting in bipartitle graph

4.1 Several preliminary theorems

Subgraph counting query is a fundamental statistic in data mining and social networks, which refers to counting the number of subgraphs with given shape in an input graph. In this section, we investigate subgraph counting under FDP and prove that the semi-global sensitivity of the query f on a graph dataset G equals to its local sensitivity, SGS_f (G) = LS (G). It means that the FDP subgraph counting problem can be calculated easily with local sensitivity.

Theorem 4.1. Let f be a subgraph counting query on a given graph G = (V, E). f is differentially increasing for edge privacy 3

Proof. Let F (G) be the set of subgraphs of specified type, F (G) = {g₁, g₂, ⋯ , g_|F(G)|}, in which |F (G) | represents the cardinality of set F (G). The subgraph counting query f is denoted as f (G) = |F (G) |.

Obviously, f is monotonically increasing. ∀G₀, G : G⁰ ⊂ G, we need to prove |f (G⁰) - f ((G⁰) ′) | ≤ |f (G) - f (G′) |, in which (G⁰) ′ and G′ are conjugate neighboring data sets of G⁰, G. The proof process is divided into two steps.

First, we assume that G⁰, G differ at one edge. Without loss of generality, let G⁰ = (V, E - {e₀}), which is denoted by G - {e₀}, (similarly hereinafter). G_i represents the neighboring data set of G by deleting one edge and G_λ represents the neighboring data set of G by adding one edge, respectively.

∀e_i ∈ E, G_i = G - {e_i}, $Δ f_{i} (G) = | f (G) - f (G_{i}) | = | F (G) - F (G_{i}) | .$ $F (G) - F (G_{i}) = {g_{1}^{i}, g_{2}^{i}, \dots, g_{Δ f_{i} (G)}^{i}} .$

∀e_λ ∈ E^c (complement of edge set E), G_λ = G + {e_λ}, $Δ f_{λ} (G) = | f (G_{λ}) - f (G) | = | F (G_{λ}) - F (G) |$ . $F (G_{λ}) - F (G) = {g_{1}^{λ}, g_{2}^{λ}, \dots, g_{Δ f_{λ} (G)}^{λ}} .$ We have conclusion (1),(2) and (3).

(1) For G_i = G - {e_i}, we have Δf_i (G⁰) ≤ Δf_i (G), (∀e_i ∈ E - {e₀});

By reduction to absurdity, we assume that the conclusion (1) is not valid. ∃e_{i
₀} ∈ E (e_{i
₀} ≠ e₀) : Δf_{i
₀} (G⁰) > Δf_{i
₀} (G). That is, $\begin{matrix} | F (G^{0}) - F (G_{i_{0}}^{0}) | = f (G^{0}) - f (G_{i_{0}}^{0}) \\ > & f (G) - f (G_{i_{0}}) = | F (G) - F (G_{i_{0}}) | . \end{matrix}$ Hence, there is at least one subgraph g : $g \in F (G^{0}) - F (G_{i_{0}}^{0}), g \notin F (G) - F (G_{i_{0}}) .$ That means,

(a). $g \in F (G^{0}), g \notin F (G_{i_{0}}^{0}), g \notin F (G)$ or

(b). $g \in F (G^{0}), g \notin F (G_{i_{0}}^{0}), g \in F (G_{i_{0}})$ .

From (a), we have g ∈ F (G⁰) , g ∉ F (G). That is contrary with F (G⁰) ⊂ F (G).

From (b),

$g \in F (G^{0}), g \notin F (G_{i_{0}}^{0}) \Rightarrow e_{i_{0}} \in g$ .

g ∈ F (G_{i
₀}) ⇒ e_{i
₀} ∉ g.

This is contradictory.

Thus, (1) holds.

(2) Δf_λ (G⁰) ≤ Δf_λ (G), (∀e_λ ∈ E^c).

When f (G⁰) = f (G), we have $Δ f_{λ} (G^{0}) \leq Δ f_{λ} (G) \Leftrightarrow f (G_{λ}^{0}) \leq f (G_{λ})$ , (∀e_λ ∈ E^c).

When f (G⁰) ≠ f (G), we assume that the conclusion (2) is not valid. ∃e_λ₀ ∈ E^c : Δf_λ₀ (G⁰) > Δf_λ₀ (G). That is $\begin{matrix} | F (G_{λ_{0}}^{0}) - F (G^{0}) | = f (G_{λ_{0}}^{0}) - f (G^{0}) \\ > & f (G_{λ_{0}}) - f (G) = | F (G_{λ_{0}}) - F (G) | . \end{matrix}$ Hence, there is at least one subgraph g : $g \in F (G_{λ_{0}}^{0}) - F (G^{0}), g \notin F (G_{λ_{0}}) - F (G) .$ That means,

(a). $g \in F (G_{λ_{0}}^{0}), g \notin F (G^{0}), g \notin F (G_{λ_{0}})$ or

(b). $g \in F (G_{λ_{0}}^{0}), g \notin F (G^{0}), g \in F (G)$ .

From (a), we have $g \in F (G_{λ_{0}}^{0}), g \notin F (G_{λ_{0}})$ . That is contrary with $F (G_{λ_{0}}^{0}) \subset F (G_{λ_{0}})$ .

From (b),

$g \in F (G_{λ_{0}}^{0}), g \notin F (G^{0}), g \in F (G) \Rightarrow e_{λ_{0}} \in g, g \subset G \Rightarrow e_{λ_{0}} \in E$ .

That is contrary with e_λ₀ ∈ E^c.

Thus, (2) holds.

(3) For G_i = G - {e_i}, we have Δf_i (G⁰) = Δf_i (G), (e_i = e₀).

By the definition of conjugate neighboring data sets G_i and $G_{i}^{0}$ , we have $G_{i}^{0} = G_{i} \cup {e_{i}} = G$ , G_i = G - {e_i} = G - {e₀} = G₀.

$\begin{matrix} Δ f_{i} (G^{0}) = & | f (G^{0}) - f (G_{i}^{0}) | \\ = & | f (G^{0}) - f (G) | \\ = & | f (G_{i}) - f (G) | = Δ f_{i} (G) \end{matrix}$

Thus, (3) holds.

By (1), (2) and (3), we have

$| f (G^{0}) - f ((G^{0})^{'}) | \leq | f (G) - f (G^{'}) |,$ in which (G⁰) ′ and G′ are conjugate neighboring data sets of G⁰ and G.

Table 1
Datasets properties with counting bicliques

datasets |U| |V| |E| Maxdegree | ⋈ | (2, 3)-bicliques (3, 3)-bicliques

Frwikinews 26,546 1,408 68,703 10,988 43,535,318 44,024,580,080 354,421,935,906

Picsut 99,157 17,122 449,503 10,466 519,071,489 14,723,260,205 307,814,525,336

Wikiquote 116,363 21,607 238,714 16,711 108,810,979 51,318,990,467 638,403,925,825

datasets	\|U\|	\|V\|	\|E\|	Maxdegree	\| ⋈ \|	(2, 3)-bicliques	(3, 3)-bicliques
Frwikinews	26,546	1,408	68,703	10,988	43,535,318	44,024,580,080	354,421,935,906
Picsut	99,157	17,122	449,503	10,466	519,071,489	14,723,260,205	307,814,525,336
Wikiquote	116,363	21,607	238,714	16,711	108,810,979	51,318,990,467	638,403,925,825

Second, ∀G₁, G₂ ⊂ G : G₁ ⊂ G₂, without loss of generality, we assume that G₂ = G₁ ∪ {e₁, e₂, ⋯ , e_k} , k ≥ 1.

$\begin{matrix} | f (G_{1}) - f (G_{1}^{'}) | \\ \leq & | f (G_{1} \cup {e_{1}}) - f ((G_{1} \cup {e_{1}})^{'}) | \\ \leq & \dots \\ \leq & | f (G_{1} \cup {e_{1}, \dots, e_{k}}) - f ((G_{1} \cup {e_{1}, \dots, e_{k}})^{'}) | \\ = & | f (G_{2}) - f (G_{2}^{'}) | . \end{matrix}$

Thus, the subgraph counting query f is differentially increasing.□

Note: In a quite similar way, we can prove that the conclusion in the above theorem still holds under node privacy. However, whether all monotone incremental queries are difference incremental queries is still an open question.

Corollary 4.2.Let f be a subgraph counting query on a given graph G = (V, E). We have ${LS}_{f} (G) = {SGS}_{f} (G) .$

Proof. According to Theorem 4.1, f is differentially increasing. By Proposition 2.12, LS_f (G) = SGS_f (G).□

Recall that, we need to calculate semi-global sensitivities for queries which are not differentially increasing. Theorem 4.1 and Corollary 4.2 indicate that we can directly employ FDP mechanismswith local sensitivities of subgraph counting.

4.2 Algorithms

We present the schematic diagrams (Fig. 1) illustrating the operation process of FDP mechanisms in the Introduction section.

5 Experimental evaluation

In this section, we first introduce our experiment settings, including the datasets and the baselines. Then, we report the results of experiments which are conducted on the platform of Matlab R2012a. We use a machine which is equipped with an Intel(R) Core(TM) i5-4590 3.30 GHz processor and a 8GB RAM.

5.1 Experimental settings

Datasets: From the Koblenz Network Collection (KONECT) [20] which contains hundreds of network datasets of various types, we choose six datasets of bipartite networks as follows: 1) Frwikinews [1] is a bipartite edit network of the French Wikipedia. The nodes are users and pages, connected by edit events. 2) Picsut [25] is a bipartite picture tagging network. Left nodes represent users and right nodes represent tags. Each edge connects a user and a tag he has used. 3) Wikiquote [38] is a bipartite edit network of the English Wikipedia. Each edge represents an edit. We summarize some important statistics of these datasets in Table 2. As a preparatory work, we list a number of parameters to demonstrate the size of the datasets. The FDP mechanisms add noise to the counting results of (2,2)-bicliques and (2,3)-bicliques to protect privacy.

Baselines: As aforementioned, some existing works focus on differentially private subgraph counting in unipartite graphs [19, 27]. However, they are suffered from various drawbacks. For example, smooth method [19, 27] which employs a smooth upper bound of the local sensitivity and adds Cauchy noise to the query values is faced with the difficulty of computing smooth sensitivity of k_Δ and k-cliques. NoisyLS [19] only applies for k_Δ. The time complexity of Recursive [4] is super-quadratic to the number of cliques and only works when counting results is small. Ladder framework is the only effective and efficient algorithm for k-clique counting [41]. Furthermore, since unipartite and bipartite graphs have different structures, all the above methods can not be directly applied for differentially private biclique counting in bipartite graphs before being reformed. In this paper, we present fixed and infinite intervals FDP frameworks for (a, b)-biclique counting in bipartite graphs.

Table 2
Experimental parameters

Random Number N 50 100 200 300 400 500

Privacy Budget ε 0.05 0.1 0.2 0.4 0.8 1.6

Similarity level s ₀ 0.9512 0.9048 0.8187 0.6703 0.4493 0.2019

Random Number	N	50	100	200	300	400	500
Privacy Budget	ε	0.05	0.1	0.2	0.4	0.8	1.6
Similarity level	s ₀	0.9512	0.9048	0.8187	0.6703	0.4493	0.2019

Fig. 8

(2, 2)-biclique counting.

Fig. 9

(2, 3)-biclique counting.

To evaluate the performance of our algorithms, we compare them with two competitors, Laplace mechanism and ladder frameworks in DP. Laplace mechanism adds Laplace noise (GS/ε, DP) to the exact value of subgraph counts. Ladder frameworks are reformed from paper [41]. Besides, we employ a relative error curve adding Laplace noise (LS/ε, not DP) as a reference lower bound. We measure the accuracy of the algorithms by the median relative error, median |output₁ - f (G) |/f (G) , |output₂ - f (G) |/f (G) , ⋯ , |output_N - f (G) |/f (G) ), in which f (G) represents the true value of biclique counting and N represents the execute times of our random algorithm. We set N = [50, 100, 200, 300, 400, 500]. The conversion formula of the similarity level s₀ is ε = - ln s₀. The specific parameters are included in Table 3.

5.2 Evaluation results

Experimental results of (2, 2)-biclique counting are shown in Fig. 7. As can be seen, FDP achieves good accuracy on f_⋈ over all three datasets. When the privacy budget is relatively large, e.g. ε = 1.6 = - ln s₀, the median relative error is always less than 1% 0. The median relative errors increase with the decreasing of the privacy budget ε as well as the similarity level s₀. When the privacy budget is relatively small, e.g. ε = 0.05 = - ln s₀, the median relative error is still smaller than 0.1 in most datasets and the median relative error of FDP is nearly one magnitude smaller than ladder in Frwikinews, Picsut and Wikiquote.

Fig. 10

(3, 3)-biclique counting.

Experimental results of (2, 3)-biclique counting are shown in Fig. 8. As can be seen, on the whole, FDP achieves good accuracy on f_2⋈3 over all datasets when the privacy budget is not too small (say ε ≥ 0.2).

When the privacy budget is relatively small, e.g. ε = 0.05 = - ln s₀, the error of FDP is one magnitude smaller than ladder for most datasets.

Experimental results of (3, 3)-biclique counting are shown in Fig. 9. It can be observed that the excellent performance of the algorithm (2, 3)-biclique counting is handed down.

From Figs. 7, 8 and 9, we can observe that the accuracy of FDP is several orders of magnitude higher than Laplace. FDP is more accurate than ladder on f_⋈ and f_2⋈3, especially for datasets which have large differences between degrees of vertices. With ε getting smaller, FDP shows greater advantage than ladder.

6 Conclusions

In this article, in order to enhance the privacy of output results building on previous work, we put forward two types of novel FDP mechanisms. One is for bounded intervals, named fixed intervals FDP mechanisms, with stronger consistency in output results. The other one is for unbounded intervals, named infinite intervals FDP mechanisms, with a wider range of perturbations. In addition, we obtain an essential property of subgraph counting query, SGS = LS. It means that the calculating of semi-global sensitivities of a query can be simplified by calculating local sensitivities. Our experiments on subgraph counting verify the validity of these novel FDP mechanisms and show the magnitude of the error for different levels of privacy protection. It can be seen that the error in the output results remains low at higher levels of privacy protection.

FDP is a competitive model for privacy protection. Different types of queries can make the privacy protection mechanism different in nature. To accommodate the characteristics of different types of data sets, our ongoing studies will focus on investigating more FDP mechanisms in a variety of scenarios and exploring more types of queries such as histogram query.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 61976168, Grant 61972309, and Grant 61902299, in part by S&T Program of Hebei under Grant 20310102D, in part by XD-Inspur DB Innovation Lab grant, in part by Key Scientific Research Program of Shaanxi Provincial Department of Education under Grant 20JY014,, in part by China Postdoctoral Science Foundation under Grant 2019TQ0239 and Grant 2019 M663636, and in part by scientific research project of Chaohu University (XLY-202105).

Broadly speaking, differential attacks are the study of how differences in information input(i.e. neighboring data sets which differ at one record) can affect the resultant difference at the output.

The isomorphism between a pair of graphs g1 and g2 means that there is an isomorphic mapping between them. Isomorphic subgraphs, in some order, have the same adjacency matrix.

Edge privacy refer to the differential privacy with a pair of neighboring datasets which differ at one edge.

References

Wikinews (fr) network dataset – KONECT, April 2017.

Taher Alzahrani , Kathy Horadam

, Serdar Boztas Community detection in bipartite networks using random walks, In Complex Networks V, pages 157–165. Springer, 2014.

Luca Bonomi , Li Xiong Mining frequent patterns with differential privacy, Proceedings of the VLDB Endowment 6(12) (2013), 1422–1427.

Shixi Chen , Shuigeng Zhou Recursive mechanism: towards node differential privacy and unrestricted joins, In Proceedings of the 2013 ACMSIGMOD International Conference on Management of Data, pages 653–664. ACM, 2013.

James Cheng , Ada Wai-chee Fu , Jia Liu Kisomorphism: privacy preserving network publication against structural attacks, In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 459–470, 2010.

Wei-Ta Chu , Feng-Chi Chang A privacy-preserving bipartite graph matching framework for multimedia analysis and retrieval, In Proceedings of the 5th ACM on International Conference on Multimedia Retrieval, pages 243–250, 2015.

Graham Cormode , Divesh Srivastava , Ting Yu , Qing Zhang Anonymizing bipartite graph data using safe groupings, the VLDB Journal 19(1) (2010), 115–139.

Kai Dong , Tao Gu , Xian-Ping Tao , Jian Lv Complete bipartite anonymity for location privacy, Journal of Computer Science and Technology 29(6) (2014), 1094–1110.

Cynthia Dwork

Differential privacy, In Proceedings of the 33rd International Conference on Automata, Languages and Programming –Volume Part II, ICALP’06, pages 1–12, Berlin, Heidelberg, 2006. Springer-Verlag.

10.

Cynthia Dwork

Differential privacy: A survey of results, In International Conference on Theory and Applications of Models of Computation, pages 1–19. Springer, 2008.

11.

Cynthia Dwork Differential privacy in newsettings, In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 174–183. SIAM, 2010.

12.

Cynthia Dwork

A firm foundation for private data analysis, Communications of the ACM 54(1) (2011), 86–95.

13.

Cynthia Dwork , Aaron Roth et al. The algorithmic foundations of differential privacy,in Theoretical Computer Science, Foundations and Trends® 9(3–4) (2014), 211–407.

14.

Noushin Salek Faramarzi , Erman Ayday , Altay Guvenir

A privacy-preserving solution for the bipartite ranking problem, In 2016 15th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 375–380. IEEE, 2016.

15.

Maximiliano Fernandez , Javier Galeano , Cesar Hidalgo Bipartite networks provide new insights on international trade markets, Networks & Heterogeneous Media 7(3) (2012), 399–413.

16.

Arik Friedman , Assaf Schuster Data mining with differential privacy, In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 493–502. ACM, 2010.

17.

Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Chao Li Resisting structural re-identification in anonymized social networks, The VLDB Journal 19(6) (2010), 797–823.

18.

Yongchao Hou , Xiaofang Xia , Hui Li , Jiangtao Cui , Abbas Mardani Fuzzy differential privacy theory and its applications in subgraph counting, IEEE Transactions on Fuzzy Systems, pages 1–1, 2022.

19.

Vishesh Karwa , Sofya Raskhodnikova , Adam Smith , Grigory Yaroslavtsev Private analysis of graph structure, ACM Transactions on Database Systems (TODS) 39(3) (2014), 22.

20.

Jérôme Kunegis Konect: the koblenz network collection, In Proceedings of the 22nd International Conference onWorld Wide Web, pages 1343–1350. ACM, 2013.

21.

Laeuchli

, Ramĺłrez-Cruz

, Trujillo-Rasua

Analysis of centrality measures under differential privacy models, Applied Mathematics and Computation 412(4) (2022), 126546.

22.

Ninghui Li , Tiancheng Li , Suresh Venkatasubramanian t-closeness: Privacy beyond k-anonymity and l-diversity, In 2007 IEEE 23rd international conference on data engineer-ing, pages 106–115. IEEE, 2007.

23.

Ninghui Li , Wahbeh Qardaji , Dong Su , Jianneng Cao Privbasis: frequent itemset mining with differential privacy, Proceedings of the VLDB Endowment 5(11) (2012), 1340–1351.

24.

Ashwin Machanavajjhala , Daniel Kifer , Johannes Gehrke , Muthuramakrishnan Venkitasubramaniam l-diversity: Privacy beyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDD) 1(1) (2007), 1–52.

25.

Nicolas Neubauer , Klaus Obermayer Analysis of the Visualize.us folksonomy, Unpublished, 2010.

26.

Bo Ning , Yunhao Sun , Xiaoyu Tao , Guanyu Li Differential privacy protection on weighted graph in wireless networks, Ad Hoc Networks 110 (2021), 102–303.

27.

Kobbi Nissim , Sofya Raskhodnikova , Adam Smith Smooth sensitivity and sampling in private data analysis, In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75–84. ACM, 2007.

28.

Costas Pappis

, Nikos Karacapilidis

A comparative assessment of measures of similarity of fuzzy values, Fuzzy Sets and Systems 56(2) (1993), 171–174.

29.

Meikang Qiu , Keke Gai , Zenggang Xiong Privacy-preserving wireless communications using bipartite matching in social big data, Future Generation Computer Systems 87 (2018), 772–781.

30.

Swapan Raha , Abul Hossain , Sujata Ghosh Similarity based approximate reasoning: fuzzy control, Journal of Applied Logic 6(1) (2008), 47–71.

31.

Sara Ramezanian , Tommi Meskanen , Valtteri Niemi Privacy preserving 2-party queries on bipartite graphs with private set intersection, In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, pages 1867–1870, 2019.

32.

Anand Sarwate

, Kamalika Chaudhuri Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data, IEEE signal processing magazine 30(5) (2013), 86–94.

33.

Mahshad Shariatb , Farhad Shirani , Elza Erkip Fun-damental privacy limits in bipartite networks under active attacks, arXiv preprint arXiv:2106.04766, 2021.

34.

Entong Shen , Ting Yu Mining frequent graph patterns with differential privacy, In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 545–553. ACM, 2013.

35.

Latanya Sweeney

k-anonymity: A model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(05) (2002), 557–570.

36.

Li-e Wang , Xianxian Li A clustering-based bipartite graph privacy-preserving approach for sharing high-dimensional data, International Journal of Software Engineering and Knowledge Engineering 24(07) (2014), 1091–1111.

37.

Ning Wang , Xiaokui Xiao , Yin Yang , Zhenjie Zhang , Yu Gu , Ge Yu Privsuper: A superset-first approach to frequent itemset mining under differential privacy, In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 809–820. IEEE, 2017.

38.

Wikimedia Foundation, Wikimedia downloads, January 2010.

39.

, Kashima

, Ming

Modular control under privacy protection: Fundamental trade-offs, Automatica 127(4) (2021), 109–518.

40.

Lotfi Zadeh

Fuzzy sets, Information and control 8(3) (1965), 338–353.

41.

Jun Zhang , Graham Cormode , Cecilia Procopiuc

, Divesh Srivastava , Xiaokui Xiao Private release of graph statistics using ladder functions, In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 731–745. ACM, 2015.

42.

Zhang

, Li

, Wang

, Guo

, Pan

Data-driven caching with users’ content preference privacy in information-centric networks, IEEE Transactions on Wireless Communications PP(99) (2021), 1–1.

43.

Jian Zhou , Jiwu Jing , Ji Xiang , Lei Wang Privacy pre-serving social network publication on bipartite graphs, In IFIP International Workshop on Information Security The-ory and Practice, pages 58–70. Springer, 2012.

44.

Tianqing Zhu , Gang Li , Wanlei Zhou , Yu Philip

Differentially private data publishing and analysis: a survey, IEEE Transactions on Knowledge and Data Engineering 29(8) (2017), 1619–1638.

45.

Zhiqiang Zuo , Ran Tian , Qiaoni Han , Yijing Wang , Wentao Zhang Differential privacy for bipartite consensus over signed digraph, Neurocomputing 468 (2022), 11–21.

Novel FDP mechanisms for releasing bipartite graph data on fixed and infinite intervals

Abstract

Keywords

1 Introduction

1.3 Related work

2 Preliminaries

2.1 Fuzzy sets

2.2 Differential privacy

2.3 Fuzzy differential privacy

3.1 FDP on fixed intervals

4.1 Several preliminary theorems

5 Experimental evaluation

5.1 Experimental settings

Table 2 Experimental parameters Random Number N 50 100 200 300 400 500 Privacy Budget ε 0.05 0.1 0.2 0.4 0.8 1.6 Similarity level s 0 0.9512 0.9048 0.8187 0.6703 0.4493 0.2019

Footnotes

Acknowledgments

References

Table 2
Experimental parameters

Random Number N 50 100 200 300 400 500

Privacy Budget ε 0.05 0.1 0.2 0.4 0.8 1.6

Similarity level s ₀ 0.9512 0.9048 0.8187 0.6703 0.4493 0.2019