Privacy and efficiency guaranteed social subgraph matching

Due to the increasing cost of data storage and computation, more and more graphs (e.g., web graphs, social networks) are outsourced and analyzed in the cloud. However, there is growing concern on the privacy of these outsourced graphs at the hands of untrusted cloud providers. Unfortunately, simple label anonymization cannot protect nodes from being re-identified by adversary who knows the graph structure. To address this issue, existing works adopt the k-automorphism model, which constructs \((k-1)\) symmetric vertices for each vertex. It has two disadvantages. First, it significantly enlarges the graphs, which makes graph mining tasks such as subgraph matching extremely inefficient and sometimes infeasible even in the cloud. Second, it cannot protect the privacy of attributes in each node. In this paper, we propose a new privacy model (k, t)-privacy that combines the k-automorphism model for graph structure with the t-closeness privacy model for node label generalization. Besides a stronger privacy guarantee, the paper also optimizes the matching efficiency by (1) an approximate label generalization algorithm TOGGLE with \((1+\epsilon )\) approximation ratio and (2) a new subgraph matching algorithm PGP on succinct k-automorphic graphs without decomposing the query graph.

1. https://aws.amazon.com/compliance/hipaa-compliance/.

2. https://www.oracle.com/database/graph/.

3. One can argue that differential privacy [11] is more stringent than t-closeness as the former is defined regardless of the underlying dataset or a priori knowledge. However, it is infeasible in subgraph matching where exact matchings are desirable.

4. We will directly use the notation \((v_1,v_2,\ldots v_i,\ldots v_j\ldots v_n)\) to denote the uniform distribution where each value is equally likely. For sorted numerical values \((v_1,v_2,\ldots v_i,\ldots v_j\ldots v_n)\), the ground distance of \(v_i\) and \(v_j\) is \(\frac{|i-j|}{n-1}\) [10].

5. When n is small, we can enumerate all feasible subsets and relax the constraint \(y_{i,j} \in \{0,1\}\) to \(y_{i,j} \in [0,1]\). Then, we apply the Simplex method to solve this linear programming problem. Finally, we employ the Branch-and-Bound method to obtain the integer solution [27].

This work was supported by National Natural Science Foundation of China (Grant Nos: 62072390, U1936205, U1636205, 61572413, 62072125) and the Research Grants Council, Hong Kong SAR, China (Grant Nos: 15238116, 15222118, 15218919, 15203120).

Authors and Affiliations

1. Shanghai Key Lab of Intelligent Information Processing School of Computer Science, Fudan University, Shanghai, China

   Kai Huang & Shuigeng Zhou

2. Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Kowloon, Hong Kong

   Haibo Hu & Qingqing Ye

3. Hong Kong and PolyU Shenzhen Research Institute, Shenzhen, China

   Haibo Hu & Qingqing Ye

4. Department of Computer Science and Technology, Tongji University, Shanghai, China

   Jihong Guan

5. Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Kowloon, Hong Kong

   Xiaofang Zhou

Corresponding author

Correspondence to Kai Huang.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A Proofs

In this section, we present the formal proofs of theorems and lemmas.

1.1 A.1 Proof of Theorem 1

Given a data graph G, the graph outsourcing problem with t-closeness and k-automorphism is to compute an outsourced graph \(G'\), where t-closeness for its labels is required. Since t-closeness is a known NP-Hard problem [56] and can be reduced to our graph outsourcing problem, the graph outsourcing problem with t-closeness and k-automorphism is NP-Hard. In addition, our subgraph matching problem is NP-Hard since it involves subgraph isomorphism testing, which is a classical NP-Hard problem [32, 57, 58]. Overall, both graph outsourcing problem with (k, t)-privacy and subgraph matching problem on outsourced graphs are NP-Hard.

1.2 A.2 Proof of Lemma 1

Let \(l=(l_1,l_2,\ldots ,l_n)\) be ordered labels and \((1/n,1/n,\ldots ,1/n)\) their distribution masses. We define \(\alpha \)-th Alignment Group (denoted by \(g_{\alpha }\)) as m consecutive labels in l, i.e., \(g_{\alpha }\) \(=\) \((l_{(\alpha -1)m+1}\), \(l_{(\alpha -1)m+2}\), \(\ldots \), \(l_{(\alpha -1)m+\beta },\ldots ,l_{\alpha m})\) (Fig. 21). In addition, let feasible column \(y_j\) be ordered labels \((e_1,\ldots ,e_\alpha , \ldots ,e_{n/m})\) with evenly distributed mass \((m/n,m/n,\ldots ,\) m/n). Since labels are ordered, according to [10], the minimal workload of \(EMD(l,y_j)\) can be achieved by satisfying all elements of l sequentially, i.e., sequentially move distribution masses from \(y_j\) to l. In particular, as depicted in Fig. 21, \(e_\alpha \) should transport \(\frac{1}{n}\) distribution mass to each label in \(g_{\alpha }\) \(=\) \((l_{(\alpha -1)m+1}\), \(l_{(\alpha -1)m+2}, \ldots ,l_{(\alpha -1)m+\beta }\),\(\ldots \),\(l_{\alpha m})\). In short, each element \(e_\alpha \) in \(y_j\) should be “aligned” with the \(\alpha \)-th alignment group (i.e., transport distribution mass to elements in \(\alpha \)-th alignment group), and \(e_\alpha \) should transport \(\frac{1}{n}\) distribution mass to each element of \(\alpha \)-th alignment group.

Alignment Group

Full size image

1.3 A.3 Proof of Lemma 2

According to Lemma 1, each element \(e_\alpha \) in \(y_j\) is aligned with \(\alpha \)-th alignment group (i.e., \(g_\alpha \)). In addition, observe that the subscripts of elements in alignment group \(\alpha \) are \((\alpha -1)m+1, (\alpha -1)m+2,\ldots ,(\alpha -1)m+\beta ,\ldots ,(\alpha -1)m+m\), respectively, and the ground distance between \(e_\alpha \) and \(\beta \)-th element in alignment group \(\alpha \) is \(\frac{|i-(\alpha -1)m-\beta |}{n-1}\) where i is the position of \(e_\alpha \) in l. Therefore, we derive that the ground distance between \(e_\alpha \) and \(\alpha \)-th alignment group is

where i is \(e_\alpha 's\) position in l. To estimate its domain, three cases should be considered:

1. (1)

   If \(i \le (\alpha -1)m+1\),

   $$\begin{aligned} \begin{aligned} Dist(e_\alpha ,g_\alpha )&= \frac{1}{n-1} ( (\alpha -1)m^2 + \frac{(1+m)m}{2} - im) \\&= \frac{2n^2\alpha - 2(n^2/m)i - 2n^2 + (n/m+n)n}{2(n-1)(n/m)^2}. \end{aligned} \end{aligned}$$

   \(Dist(e_\alpha ,g_\alpha ) \in [\frac{n^2 - n^2/m}{2(n-1)(n/m)^2}, \frac{2n^3/m - 2n^3/m^2 - n^2 + n^2/m}{2(n-1)(n/m)^2}]\).

2. (2)

   If \((\alpha -1)m+1 \le i \le (\alpha -1)m+m\),

   $$\begin{aligned} \begin{aligned} Dist(e_\alpha ,g_\alpha )&= \frac{1}{n-1}\left( \sum _{\beta _1=1}^{\beta }(\beta -\beta _1)+\sum _{\beta _2=1}^{m-\beta }\beta _2 \right) \\&=\frac{2\beta ^2\alpha - 2(1+m)\beta + m + m^2}{2(n-1)}. \end{aligned} \end{aligned}$$

   If m is odd, \(Dist(e_\alpha ,g_\alpha )\) \(\in \) \([\frac{n^2 - n^2/m^2}{4(n-1)(n/m)^2}\), \(\frac{n^2 - n^2/m}{2(n-1)(n/m)^2}]\), otherwise, \([\frac{n^2}{4(n-1)(n/m)^2},\) \(\frac{n^2 - n^2/m}{2(n-1)(n/m)^2} ]\).

3. (3)

   If \(i \ge (\alpha -1)m+m\),

   $$\begin{aligned} \begin{aligned} Dist(e_\alpha ,g_\alpha )&= \frac{1}{n-1}( im - (\alpha -1)m^2 - \frac{(1+m)m}{2}) \\&= \frac{\frac{2n^2}{mi} - 2(\frac{n}{m})^2n - 2n^2\alpha + 2n^2 -(\frac{n}{m}+n)n}{2(n-1)(n/m)^2}, \end{aligned} \end{aligned}$$

\(Dist(e_\alpha ,g_\alpha )\) \(\in \) \([\frac{n^2 - n^2/m}{2(n-1)(n/m)^2},\) \( \frac{2n^3/m - 2n^3/m^2 - n^2 + n^2/m}{2(n-1)(n/m)^2}]\).

Therefore, for \(\forall i \in [(\alpha -1)m+1, (\alpha -1)m+m ]\), \(Dist(e_\alpha ,g_\alpha ) \in [\frac{n^2 - \frac{n}{m}^2}{4(n-1)\frac{n}{m}^2}\), \(\frac{n^2 - \frac{n^2}{m}}{2(n-1)\frac{n}{m}^2}]\) (if m is odd) or \(Dist(e_\alpha ,g_\alpha ) \in [\frac{n^2}{4(n-1)\frac{n}{m}^2}\), \(\frac{n^2 - \frac{n^2}{m}}{2(n-1)\frac{n}{m}^2}]\) (if m is even).

1.4 A.4 Proof of Theorem 2

Lemma 2 proved that \(\forall i \in [(\alpha -1)m+1, (\alpha -1)m+m ]\), if m is odd, \(Dist(e_\alpha ,g_\alpha ) \in [\frac{n^2 - \frac{n}{m}^2}{4(n-1)\frac{n}{m}^2}\), \(\frac{n^2 - \frac{n^2}{m}}{2(n-1)\frac{n}{m}^2}]\). Otherwise, \(Dist(e_\alpha \), \(g_\alpha ) \in [\frac{n^2}{4(n-1)\frac{n}{m}^2}\), \(\frac{n^2 - \frac{n^2}{m}}{2(n-1)\frac{n}{m}^2}]\). Each element \(e_\alpha \) of \(y_j\) generated by initial solution is selected from the i-th position of l, where \(i \in [(\alpha -1)m+1,(\alpha -1)m+m ]\). In addition, Lemma 1 showed that each element \(e_\alpha \) in \(y_j\) is supposed to transport 1/n distribution mass to each element in \(\alpha -\)th alignment group. Based on those two observations, we derive that \(EMD(l,y_j) \le \sum _{\alpha =1}^{n/m} \frac{n^2 - n^2/m}{2(n-1)(n/m)^2}\times \frac{1}{n}\) \(= \frac{mn^2-n^2}{2(n-1)n^2} = \frac{m-1}{2(n-1)}\). Therefore, when \(t \ge \frac{m-1}{2(n-1)}\), the column \(y_j\) satisfies \(t-\)closeness. Similarly, each column generated in subproblem also satisfies \(t-\)closeness. By the way, we can adopt the similar way to prove that the EMD between l and any other column is bounded by \(\frac{2mn-2n-m^2+m}{2(n-1)m}\).

1.5 A.5 Proof of Lemma 3

Let l=\((l_1,l_2,\ldots ,l_n)\) be n labels ordered by their values, and a the Euler–Mascheroni constant (\(\approx \) \( \frac{1}{ln(n)+0.5772+1/2n}\)), the frequency of l can be represented by \((\frac{a}{1}, \frac{a}{2},\ldots , \frac{a}{n})\), since the frequencies of labels roughly obey the Zipf’s law [3]. When \(t \ge \frac{m-1}{2(n-1)}\), sub-optimal TOGGLE generates the initial partition \(\{y_j|j\in [1,m]\}\) where \(y_{i,j}=1\) if i locates in \(\{j,j+m,\ldots ,j+(n/m-1)m\}\) or \(y_{i,j}=0\), otherwise. Let the sum of label frequencies of \(y_j\) be

the cost of \(y_j\) is obviously \(s^2_j\). Therefore, the total cost of the initial solution is \(s^2_1+s^2_2+\ldots +s^2_m\) where \(s_1+s_2+\ldots +s_m =1\) and \(s_1>\) \(s_2>\) \(\ldots \) \(>s_m\). Due to

we can derive that \(\frac{1}{m} + \frac{(m^2-m+2)a}{m^2+m} \ge s_1>s_2>\ldots >s_m\), and

Therefore, the model cost of initial solution under \(t-\)closeness constraints is at most \( \frac{1}{m} + \frac{(m^2-m+2)a}{m^2+m}\). To estimate the approximate ratio \(R_1\) of our model cost to the exact model cost, we first relax the \(t-\)closeness constraint to find the minimum model cost. Formally, for any \(\{X_i\}\) subjecting to \(\sum _{i=1}^{m}X_i=1\), we need to estimate the lower bound of \(\sum _{i=1}^{m}X_i^2\). According to Cauchy–Schwarz inequality, for \(X_i,Y_i \in {\mathcal {R}}\), \(\big (\sum _{i=1}^{m}X_iY_i\big )^2 \le \big (\sum _{i=1}^{m}X_i^2\big )\big (\sum _{i=1}^{m}Y_i^2\big )\). Let \(Y_i=1\), we derive that \(\frac{1}{m} \le \sum _{i=1}^{m}X_i^2\). Therefore, the minimum model cost, \(s^2_1+s^2_2+\ldots +s^2_m\), is no less than \(\frac{1}{m}\). The approximate ratio \(R_1 \le \frac{ 1/m + (m^2-m+2)a/(m^2+m)}{1/m} \le 1 + \frac{(m^2-m+2)a}{m+1}\). The approximation is good since the approximate ratio is approximately liner to \(m \cdot a\).

1.6 A.6 Proof of Lemma 4

From Lemma 3, we observe that the sum of labels frequencies of \(y_j\) is \(s_j = \frac{a}{j}+ \frac{a}{j+m}+\ldots + \frac{a}{j+(n/m-1)m}\) where \(s_1+s_2+\ldots +s_m =1\) and \(s_1>\) \(s_2>\) \(\ldots \) \(>s_m\). If we denote the first dual solution of the master problem as \(\mu = [s^2_1,s^2_2,\ldots ,s^2_m,0,0,\ldots ,0]\), the objective values of the original subproblem and the reduced problem can be formulated as \(J_2=min(c(y_j)-\mu y_j),~s.t., ~EMD(l,y_j)\le t\) and \( J_{2}' = min(c(y_j)-\mu y_j)\), s.t., QKP Constraints, respectively. Intuitively, we can derive that

Therefore, the approximate ratio of \( J_{2}'\) to \(J_2\) is no less than 4a/m where a is the Euler–Mascheroni constant.

1.7 A.7 Proof of Theorem 3

Let the optimal solution to original problem be opt, and the initial solution \(R_1\times \) opt, if the first reduced cost of the column generation method is \(J_2\), then \(\textsc {opt}= R_1\times \textsc {opt} - \gamma \times J_2\) where \(\gamma \ge 1\) and \(\gamma = (R_1-1)\) opt\(/J_2\). Similarly, if the first reduced cost of the sub-optimal method is \( J_{2}'\), we can derive the objective value \(X = R_1\times \textsc {opt} - \gamma ' \times J_{2}'\).

On the basis of those two lemmas, we can prove that if \( \gamma \le \gamma '\), the approximate ratio is \(\textsc {opt}/X \ge \textsc {opt}/(R_1\times \textsc {opt} - \gamma \times J_{2}') = \textsc {opt}/(R_1\times \textsc {opt} - ((R_1-1)\textsc {opt}/J_2) \times J_{2}') \ge 1/(1+ (m^3-5m^2+6m-8)a/(m^2+m))\). Otherwise, \(\textsc {opt}/X = \textsc {opt}/(R_1\times \textsc {opt} - \gamma ' \times J_{2}')\ge \textsc {opt}/(R_1\times \textsc {opt}) \ge 1/(1 + (m^2-m+2)a/(m+1))\). Therefore, \(\textsc {opt} \le X \le (1+ (m^3-5m^2+6m-8)a/(m^2+m))\textsc {opt}\) or \((1 + (m^2-m+2)a/(m+1))\textsc {opt} \approx (1+0.2m)\textsc {opt}\).

Reprints and permissions