Gromov-Wasserstein Discrepancy with Local Differential Privacy for Distributed Structural Graphs

1 Introduction

A lot of applications in machine learning are extensively using either pairwise matrices or kernels to perform the task of prediction or regression. Examples like the RBF kernel and covariance matrices are commonly used in support vector machine classification in the Euclidean space. However, applications in the non-Euclidean domains, presented in graphs, such as social network [Fan et al., 2019], recommendation systems [Wu et al., 2020], fraud detection [Li et al., 2020] and biochemical data [Coley et al., 2019] involve the study the of relations among the featured objects. To measure the graph similarities, a variety of graph kernels [Vishwanathan et al., 2010] are proposed but mainly focus on the topological information. Graph neural networks (GNNs, e.g., [Hamilton et al., 2017]) are one of the state-of-the-art models to learn node embedding. However, it requires additional readout layers to match the dimension for graph sizes, and it lacks the trackable way to capture the isometric issue on graphs. Recently, Gromov-Wasserstein (GW) distance [M´emoli, 2011; Peyr´e et al., 2016] provides a geometry-based metric to measure the optimal transportation from one structural object to another. GW operates on the metric-measure spaces, i.e., a Borel probability measure on the set with its compact metric space. In other words, it operates on distances between pairs of points calculated within each domain and measures how the distance is compared to those in the other domain. Specifically, all-pair shortest path (APSP) is one of the common geodesic measures applied. Thus, it requires calculating the transportation between two domains by their intradistance, turning the distance problem from a linear optimization to a quadratic one. And it extends both topological and features information (known as FGW [Titouan et al., 2019]) so that the similarity problem cooperates with the node features nicely. One of the key advantages of applying GW distance is the capability of handling the isometric properties between structures. Thus, GW is highly related to graph matching problem, encoding structural information to compare graphs, and has long history been successfully adopted in image recognition [Peyr´e et al., 2016], bio-domain adoption [Demetci et al., 2020], and point-cloud data alignment [M´emoli and Sapiro, 2006].

∗Corresponding author

All previous works have assumed that all structured data are always available and accessible, which is often not true in reality. Structured data in many applications either contain sensitive and private information (such as payment transactions and social connections) or distribute across different clients commonly [Liao et al., 2021]. On one hand, data owners are limited to sharing the original data due to the privacy regulations that are enforced globally, such as GDPR [Regulation, 2018] and CCPA [Bukaty, 2019]. On the other hand, in many applications, one has to deal with very large datasets that cannot be processed at once. Thus, a nested partitions of the input which are parameterized by a scale parameter is arising from the metric structure of the input data.

1.1 ProblemFormulation

In this paper, we work on the problem of GW distance between distributed graphs while having privacy constraints. Two key assumptions are placed in the underlying such scenarios: 1) each graph holds its topological information, nodes with feature and labels locally; 2) server cannot access raw data globally while having to distinguish from graph to graph (anomaly detection, clustering, recommendation, etc). Accordingly, two main issues need to be addressed: first, to train the global model across different graphs while preserving the privacy of local data; second, to compare graphs even in the case of permutation invariant and size variant. In order to overcome the two issues, we take federated learning schema as our primary framework, along with a geometrybased metric named Gromov-Wasserstein discrepancy [Peyr´e et al., 2016] on the server-side to learn similarity / dissimilarity across graphs. Gromov-Wasserstein distance [M´emoli, 2011] provides a metric to measure the optimal transportation from one structural object to another.

The proposed framework is illustrated in Figure 1. To summarize: 1) the synchronized vertical federated learning first updates local parameters W from the private structural data G(A,X) to learn the local graph embedding H; 2) then, instead of pulling the raw graph data from the client, the proposed framework takes the local graph embedding learned from the FL model, and local differential privacy (LDP) is applied explicitly, where we extend the multi-bit encoder from vector space to matrix scenario, protecting the sensitive information; 3) after getting the encoded graph embeddings, the framework calculates similarity metrics (GW distance) on the server and serves the downstream tasks, such as clustering, classification, and matching problems.

Overall, we highlight our core contributions as

• Beyond the conventional federated learning, we design the guaranteed ε-LDP on graph embeddings to explicitly protect the graph information. It is worth mentioning that LDP on topology is not applicable because of the vulnerability of GNN, and perturbation on either the node or edge leads to a non-smoothing function.
• Besides, we adopt the Gromov-Wasserstein discrepancy to be the learnable structural metric on the server, cooperating the LDP encoded graph embeddings from the client-side.
• Interestingly, we observe that the LDP on graph embeddings not only protects privacy but also helps to escape
• saddle points in GW optimization. We interpret that this is largely due to the non-convexity of GW discrepancy.
• Having the GW discrepancy with noised input, we empirically evaluate the performance of graph classification and clustering problem.

To the best of our knowledge, this is the first work to learn the structural metric with local differential privacy under the distributed setting. And the framework is flexible to learn the node embedding and can be combined with a variety of GNNs for a broad range of different tasks, including graph classification, clustering, etc.

1.2 Notation

We take capital and lower letter in bold to represent matrix and vector, respectively. A graph G(A, X) has adjacency matrix A as structural information and node feature X as feature information. Besides, V, E are the node sets and edge sets from the graph, respectively. H is the retrieved node representation, each row of the matrix represents a single node on the graph. An upper script i means the i-th graph, while a lower script i means i-th row of the matrix.

2 RelatedWork

The ultimate goal of our proposed method is to protect the privacy of structured data while building the GW distance for similarities between graphs. Naturally, Federated Learning (FL) [McMahan et al., 2017; Smith et al., 2017] is an emerging collaborative learning framework that can train multiple clients locally while maintaining a global model on the server. Distinguished from the shared parameter server [Li et al., 2014], one of the significant fruits of federated learning is privacy protection, where each client holds its raw data locally, only shared parameter/gradient will be exchanged with the server. Specifically, in the vertical FL setting, a model is shared among all the clients, and the client trains the model locally with its labels, while the server learns the global models by aggregating the local client models.

Recently, a set of different methods are proposed to build a GNN model with a federated setting. With the task of graph classification, [He et al., 2021] design a federated learning system and benchmark for graph neural networks. The framework is built based on FedML [He et al., 2020] research library, enabling to run a variety of GNN models effectively with non-IID graph dataset, which is a similar approach in the image domain. Interestingly, FL-AGCNS [Wang et al., 2021] propose to take advantage of federated learning to accelerate in the task of neural architecture search of graph convolutional network. Specifically, they take federated SuperNet optimization to select random GCN architecture and take federated evolutionary optimization to perform evaluation suing GCN SuperNet.

However, all the work above trains a shared model with the task of supervised/semi-supervised learning, but do not address the issue of unlabelled graphs on clients. What's more, none of the work above discusses the graph differential privacy while learning the model. Unlike our proposed framework, a recent work of locally private graph neural network [Sajadmanesh and Gatica-Perez, 2020] build the feature and label differential private on the clients at once while leaving the whole training process on the server-side instead.

Another approach to protecting privacy is differential privacy. More specifically, with distributed graphs, we mainly focus on the local differential privacy of each graph. Given a graph G(A,X), the purpose of applying LDP is to protect the private information from topology A and node feature X. A naive approach would be directly adding LDP noise to A and X. However, we argue that such an approach has its limitations. For the topological LDP, assume we add random perturbation to the topology of the graph, i.e., add or delete edges on a graph. However, works like Nettack proposed in [Z¨ugner et al., 2018], found that even a small perturbation could lead to the misclassification of the nodes in the graph. Moreover, random perturbation could result in the same graph but is permutation invariant to the original graph, i.e., A′ = Π(A), where A′ is the perturbed graph [Niu et al., 2020]. For the feature LDP, adding LDP on feature is a valid approach in the work [Sajadmanesh and Gatica-Perez, 2020], but it lacks protection for the structural information. Moreover, the study in graph diffusion Wasserstein distance [Barbe et al., 2020] suggests that a noisy feature will let the fused GW depend mostly on the structure. Therefore, adding small random perturbation to either the topology or the feature is not a guaranteed approach to protect privacy in the federated learning setting.

2.1 Gromov-Wasserstein Discrepancy

Graph neural networks rely on training on structured data for various graph-related tasks. However, a common limitation is its difficulty in explaining the isomorphism in graph data. Identification of similarities between graphs is an essential problem in graph learning areas. In these areas, the graph isomorphism problem is known as the exact graph matching [Xu et al., 2019b], which is not solvable in polynomial time. Two graphs are considered isomorphic if there is a mapping between the nodes of the graphs that preserves their adjacencies. The graph isomorphism testing is used in a wide range of applications, such as the identification of chemical compound, the generation of molecular graphs in chemical dataset [Titouan et al., 2019], and the electronic design automation (EDA) with placement and routing operations [Chan et al., 2000]. Graph Isomorphism Network (GIN) [Xu et al., 2019c] is recently proposed to implement Weisfeiler-Lehman (WL) graph isomorphism test [Shervashidze et al., 2011]. However, such kind of approach only deals with graphs of the same size, and hard to distinguish the difference between graphs with arbitrary sizes.

Recently, the optimal transport (OT) associated with their Gromov-Wasserstein (GW) discrepancy [Peyr´e et al., 2016], which extends the Gromov-Wasserstein distance [M´emoli, 2011], has emerged as an effective transportation distance between structured data, alleviating the incomparability issue between different structures by aligning the intra-relational geometries. GW distance is isometric, meaning the unchanged similarity under rotation, translation, and permutation. Formally, [Peyr´e et al., 2016] define the GromovWasserstein discrepancy between two measured similarity matrices (C, p) ∈ Rn×n × ∑n and (D, q) ∈ Rm×m × ∑m as follows

where C and D are matrices representing either similarities or distances between nodes within the graph. ℓ(·) is the loss function either in Euclidean norm or KL-divergence [Peyr´e et al., 2016]. p ∈ R+n : ∑i pi = 1 is the simplex of histograms with n bins, and T is the coupling between the two spaces on which the similarity matrices are defined. Specifically,

Here, we denote the domain E := {T ∈ Rn×m,T1 = p,T⊤1 = q} and N := Rn×m + . Furthermore, we can rewrite the problem in KoopmansBeckmann form [Koopmans and Beckmann, 1957]:

Note that the GW distance is non-convex and highly related to the quadratic assignment problem (QAP), which is NP-hard. Moreover, given the similarity matrices C and D, we optimize with the quadratic trace form in (3) over the domain of E ∩ N. The GW discrepancy problem can be solved iteratively by conditional gradient method [Peyr´e et al., 2016] and the proximal point algorithm [Xu et al., 2019a].

In the next section, we will address the details of our proposed ε-LDP on graph embeddings and cooperate them under GW metrics.

3 Framework

To highlight our framework, it encodes node representation from the client while building the structural metric on the server-side. To build the node representation, we train the model in the task of node classification, by using the node labels locally. A conventional federated learning framework is well suited in this setting. To the simplification, we take FedAvg [McMahan et al., 2017] as the aggregation algorithm without further notice. Besides, we apply a multi-bit encoder to the node representation as LDP before transmit the graph information to the server. With the protected node representation, server calculates the geometric metric GW accordingly.

3.1 ε-LDP withMulti-bit Encoder on Graph Embedding

Inspired by the locally differential privacy on features, we adopt the multi-bit encoder from [Sajadmanesh and GaticaPerez, 2020], while their approach send the encoded feature and label directly to server and train a single model on the server-side. Differentiated from feature encoding, we take the encoder on the node representation, leveraging the privacy on both topology and feature learned from GNN. Algorithm 1 describes the LDP on node embedding in more details. We extend the one-bit encoder on a vector space to the multi-bit encoder in 2-D dimension while preserving the guaranteed privacy. Intuitively, the encoder first uniformly sample the m out of the dimension of n × h without replacement. Then for each row-wise dimension, we take the Bernoulli distribution to decide the mapped encoding after the mask. For

Algorithm 1 LDPG(·, ε): Multi-Bit Encoder

• Input: Node embedding H ∈ [α, β]n×h , ε Output: Encoded embedding H∗ 1: Let S be a set of m values sampled uniformly from [n] × [h] 2: for i in n do 3: for j in h do 4: sij = 1 if Sij = 1 else sij = 0 5: tij ∼ Bernoulli ( 1 eε/(mn)+1 + Hij-α β-α · eε/(mn)-1 eε/(mn)+1 ) 6: H∗ij = sij(2tij -1) 7: end for 8: end for

each hidden feature dimension, the probability encoding is determined by the number of nodes in the graph (n) and the sampled mask (m). This is just one-pass encoding with the complexity of O(mn).

Theorem 1 The multi-bit encoder presented in Algorithm 1 satisfies ε-local differential privacy for each graph representation.

Theorem 1 provides the theoretically guaranteed privacy protection on hidden representation.

3.2 Constructing GWDistance

Besides the work of building the global model, we also explicitly enforce the server to construct a pairwise similarity matrix C ∈ Rn×n . More specifically, CH∗(i) ∈ Rn(i)×n(i) represents intra-distance of the encoded node embedding from i-th client, namely H∗(i) ∈ Rn(i)×h , where n(i) is the number of node in i-th graph and h is the hidden dimension. Therefore, we can explicitly formulate the distance matrix between node u and v in C as

where d(·, ·) is the distance function applied. Due to its Euclidean space over the reals of H∗ , we can simply take the Euclidean distance between node embeddings to build the intra-distance. Of course, it can be easily extended to other distance metrics, such as Cosine similarity and correlation. Note that, after taking the distance introduced from hidden representation, the CH is a metric space induced from the original graph (without ε-LDP encoding). Even though the unbalanced probability measure over nodes are also applicable [Titouan et al., 2019], we will take p as a uniform distribution among the nodes, i.e., pu = 1 |V| , ∀u ∈ V. Also, as H is the graph representation after federated learning, the embedding itself encodes both structural (A) and feature (X) information, which is different from the conventional calculating C where only geodesic distance is applied commonly.

Additionally, the framework requires the optimization of Gromov-Wasserstein discrepancy on the server, and the εLDP encoded graph embedding can be retrieved only once after a stable global model from FL learning is obtained. However, considering the unexpected drop-off of clients, the graph embedding can be retrieved periodically if necessary. Therefore, compared with the vanilla FL setting, sending the encoded graph embedding H∗ will not introduce overhead in communication.

4 Experiments

Dataset. We will perform two tasks, one with graph classification under federated learning via GW, where we take the benchmark datasets from TUDataset [Morris et al., 2020]. Another task is to take the graph clustering with subgraph generated from the single big graph, where we take the citation benchmark dataset from Planetoid [Yang et al., 2016].

Graph classification. Regarding the task of graph classification under a centralized setting, we adopt an SVM using the indefinite kernel matrix e-γFGW as a distance between graphs [Titouan et al., 2019], where the training, validation, and testing sets are split in the ratio of 7 : 2 : 1. For all methods using SVM, we cross validate the parameter C ∈ {10-7 , 10-6 , · · · , 107} and γ ∈ 2-10 , 2-9 , · · · , 210 . For the decentralized setting, we split the graphs into 10 clients from the Dirichlet distribution [Wang et al., 2020], and each client has 20% and 10% for validation and testing, respectively. We report the classification accuracy in Table 1. Both PROTEINS and MUTAG has node features, where we adopt the FGW as the base metric. While IMDB-B has no features on nodes, we only take the GW (topology only) as the base metric. SPK [Borgwardt and Kriegel, 2005] is the shortest path kernel method on raw data. GCN indicates a two-layer graph convolutional layer with hidden dimension of 16, followed by an average pooling method. GIN represent a five graph isomorphic layers with hidden dimension of 64, followed by a two linear perception layers.

Comparing the results from raw data (metric based on A,X), we can see the kernel based SVM on GW discrepancy performs better than the base GCN and SPK model. For the FL setting, we defined the shared model with GCN and GIN. H is the graph embedding without privacy protection, and H∗ is ε-LDP graph embedding. Without the further notice, we take the optimal m∗ =max(1,min(d, ⌊ ε 2.18 ⌋)) from [Sajadmanesh and Gatica-Perez, 2020], where d is the number of classes from nodes. We extract the node embedding after the softmax layer, and leave α = 0, β = 1. The default value is ε = 1 |V| which varies from each graph. Intuitively, this basically means the cumulative privacy budget will be normalized on the number of nodes n.

To see the effectiveness of FL, GCN model under FL perform a bit worse than SVM on raw data. However, FL under GIN (a strong model) improves almost 10% when compared with vanilla SVM with raw data. What's more, to check how LDP works (using the H∗ graph embedding) in the classification tasks, we can find that the ε-LDP didn't hurt the overall performance.

Graph clustering. Our framework fits unsupervised learning with federated learning. And it is quite common to see that labels for each node are trivial, but not for the subgraphs (communities). Regarding the data with a single graph, we split the big graph into small subgraphs by taking multihop neighbors for simplification. Moreover, for such kind of dataset, we might not have the ground-truth label of the split subgraph. Therefore, we take the label of the central node as its pseudo-label. Note that we will see the overlap of nodes in different clients, which is a typical scenario in various applications, such Internet-of-Things (IoT) devices, community connections, and recommendation systems. A shared 2-layer GCN model with node classification task is deployed in the federated setting, where each client builds the node embedding. We retrieve the node embedding after a fixed number of 200 rounds of updating the shared model.

Figure 2 shows the t-SNE plot of KMeans clustering of 500 1-hop subgraphs from citeseer dataset with different ε. KMeans under GW distance is different from Euclidean distance, the centroid of each cluster is represented by a metric matrix. To simplify, we fix the dimension of the centroid by the average number of nodes within the cluster. Note that ε = 0 means no LDP introduced to the graph embedding and we assume the number of clusters is equal to the number of labels from nodes. Intuitively, data in the citation network has the label for each paper, and the induced subgraph is the citations referred for the central node. To show the impact of GW distance in clustering, we compare the first and second plots in Figure 2. It shows that even without the LDP encoder, the KMeans clustering with GW distance performs better than the naive labeling from central node. The property of GW distance makes it a better similarity metrics, especially with a pre-learned graph embeddings. To see the impact of LDP in clustering, compared with the raw graph embedding, the encoded H∗ with small ε won't hurt too much in the clusters. However, a larger privacy strength (ε = 1) introduces more deviates of unlabelled subgraphs. This is consistent with the observation in classification problem as well. Additional results with 2-hop subgraphs and other datasets are provided in Appendix. In the next subsection, we will have a close look at privacy strength ε in the GW distance calculation.

4.1 Privacy Analysis for LDP on Embedding

Knowing that the ε is a key factor in privacy protection and downstream tasks, we invest the impact of privacy budget ε in LDP under classification. Following the Figure 3, in order to eliminate the influence of hyperparameter in GNN models, we report the accuracy using KNN based on GWH∗ by cross-validating on ε on MUTAG dataset. As we can see on both settings of k = 5, 10, the model is relative stable with just a small perturbation, i.e., ε < 1, and with the increased privacy protection strength, a larger ε will hurt the overall performance. More interestingly, introducing the ε-LDP not only helps to protect the privacy, but also potentially helps the performance in downstream tasks with a proper ε.

Furthermore, we look into details of changes in similarity metric GW distance with respect to the ε. For the task of clustering, we extract five subgraphs (check Appendix for the subgraph structures) from Citeseer dataset, and shows the results of GW discrepancy when LDP is applied with different ε in Figure 4. We consider two privacy budgets ε = 0.1, 1 to be compared. GWH represents the distance without LDP, i.e., ε = 0, with the baseline statistics of GW discrepancy to be 2.38±2.22. GWH∗ represents the distance under encoded LDP with three different privacy budget ε = 1 |V| , 0.1, 1, and 2.42±2.33, 2.43±2.35, 3.25±3.09 are the distances statistics, respectively. It can be seen from Figure 4 that, with a proper privacy budget, we can see little difference on pairwise distance based on GW. In other words, from the perspective of applications, applying LDP on node embedding has little impact on the clustering / classification tasks. It is also true from the algorithmic view that GW distance is quantitatively stable [M´emoli, 2011] in the sense of the structure invariant. Moreover, in the distributed training, graphs are completely in non-i.i.d. distribution, suggesting that the ε can vary from client to client. Therefore, we have our default ε set to be 1/ |V|, which also matches our design of algorithm 1, sampling based on number of nodes.

4.2 Rationale behind GWwith ε-LDP Encoder

We step further to reason why the LDP on H won't sacrifice the GW distance. Due to the non-convexity of GW discrepancy, which involves a quadratic problem, the absolute error in distance from different pairs cannot have a guaranteed boundary to tell the closeness between them. Despite the challenge of finding the exact the global minima, an effective way is to escape saddle points in the non-convex manifold, which prevents the optimal solution to be stuck at the local minima.

Among many of the works targeting the escape saddle points, perturb gradient descent (PGD) [Jin et al., 2017] is one of practical simple method to solve the problem. The meta-algorithm is described as

where ξt ∼ B(ε) is a small perturbation on the input space within a small ball. Noting that, the H∗ = H+ O(ε) and Cu,v = d(H∗u ,H∗v ) = d(Hu,Hv) +O(ε), when d is a Euclidean distance function. Interestingly, we can take the LDP as small perturbation on the node embedding, which is ultimately the noisy input to the GW optimization problem.

Since it is very challenging to characterize the impact of noise in optimization, we empirically check the average output of GW with the increasing ε. Figure 5 indicates the average GW discrepancy calculated by increasing the privacy budget ε on the dataset Citeseer. We fix the initial point and other hyperparameters (threshold, max iter and etc.) in optimization, the only differences are ε. The solid blue curve indicates the average GW discrepancy (optimal function value) and the dashed orange line indicate the baseline without any perturbations. Although the increase of the privacy budget ε eventually leads to a higher mean and variance of GW discrepancy which is expected, a slight perturbation from LDP (when ε is small) helps to get a lower GW discrepancy

(smaller optimal function value from blue curve), especially when the graph is more complicated (2-hop neighbors).

The empirical result matches with our understanding of non-convex optimization with perturbed method. However, a rigorous analysis of relation between LDP and non-convex still remains unclear, especially in the connection between privacy budget and the constrained perturbation domain. We leave this problem for our future work.

5 Conclusion

In this paper, we propose a novel framework to protect the distributed structural graphs by introducing the local differential privacy to graph embeddings and handle the permutation invariant issue by taking the Gromov-Wasserstein distance for further downstream tasks. With the guaranteed ε-LDP encoding on graph embedding, our experiments show that the privacy budget not only helps in the distributed privacy protection learning, but also won't hurt the performance of the downstream tasks due to the nonconvexity of GW distance. Considering the flexibility of the framework, an interesting extension is to see the performance on large heterogeneous graphs, where the subgraphs represent small communities in social networks, fraud actions in transactions networks, and browsing logs in recommendation systems.

Acknowledgements

The research is supported by Samsung Research America internship program. We thank our colleagues Tianwei Xing, Wenjun Jiang from Samsung Research America for their valuable discussion and feedbacks.