title: GraphFederator: Federated Visual Analysis for Multi-party Graphs
authors: Dongming Han Wei Chen Rusheng Pan Yijing Liu Jiehui Zhou Ying Xu Tianye Zhang Changjie Fan Jianrong Tao Xiaolong Zhang
text: 
  
  
  
  Blind information reconciliation with polar codes for quantum key distribution
      A.K. Fedorov
      December 30, 2023
  ==============================================================================
  
  
  
  
  
  
  § INTRODUCTION
   
  Visual analysis of multi-party graphs plays an important role in helping us understand real-world complex data  <cit.>, such as ego-network analysis in social media <cit.>, disease diagnosis in healthcare <cit.>, and anomaly detection in public security <cit.>. Various features or models extracted from multi-party graphs can be integrated to support a comprehensive understanding of the entire graph data.
  Using the integrated information, we can conduct more comprehensive investigations.
  For instance, by combining knowledge graphs of patients and diseases from multiple hospitals, doctors can gain a deeper understanding of diseases and develop best treatment plans.
  
  One main bottleneck of exploiting multi-party graphs is data accessibility. Early studies on graph visual analysis assume that the graph data is freely accessible. Currently, however, more and more graph data are distributed (e.g., on servers in different organizations). To analyze such data, we need to combine multi-party graphs and examine them as an entirety. Considering of privacy and security, raw data in distributed clients may be prohibited from accessing. This leads to two challenges for visual analysis of multi-party graphs. The first is the federation of multi-party graphs.
  Because raw data should be kept locally, creating a joint representation of data in all clients must resort to privacy-preserving feature extraction techniques. This situation is even exaggerated by the fact that features of different graphs may be different. A uniformed joint representation that is capable of characterizing the essential features of each graph is needed.
  The second challenge is that the federated analysis based on joint representations is difficult. Designing a generalized framework for federating various and complex analysis tasks remains a huge challenge.
  
  Visual analysis of multi-party graphs based on the joint representations requires new approaches. Conventional graph analysis, which is performed in a centralized model, or only uses limited accessible graph data, cannot be applied to multi-party graph analysis.
  Existing solutions for distributed graph analysis <cit.> mainly focus on the partitions of data and analysis tasks for the purposes of performance improvement, and are incapable of supporting multi-party graph analysis either.
  
  One way to support privacy-preserving decentralized graph analysis is to build a decentralized federation of both data features and the analysis. We propose , a novel federation approach that constructs joint representations of multi-party graphs, and supports privacy-preserving visual analysis of graphs.
  Inspired by federated learning, we reformulate the analysis of multi-party graphs into a decentralization process. The new federation framework consists of a shared module that is responsible for joint modeling and analysis, and a set of local modules that run on respective graph data.
  Specifically, we propose a federated representation model
  that is iteratively learned from the encrypted characteristics of multi-party graphs in local modules.
  We design multiple visualization views for joint visualization, exploration, and analysis of multi-party graphs.
  The contributions of this paper include:
  
      
    * a federated graph representation model to represent and extract distinctive features from multi-party graphs; and
  
    * a federated visual analysis approach to support privacy-preserving graphs analysis.
  
  
  The rest of this paper is organized as follows. Related work is discussed in Section 2.
  Section 3 introduces the problem formulation.
  Section 4 explains our design goals and the overview of our approach.
  Our federated graph representation model is introduced in Section 5.
  Section 6 presents the visual interface.
  The evaluation is discussed in Section 7.
  
  
  Discussions and the conclusion are given in Section 9 and Section 10, respectively.
  
  
  
  § RELATED WORK
   
  
  
   §.§ Visual Analysis of Graph Data
  
  
  A graph analysis task is usually defined as the analysis of entities or associated properties <cit.>. Here, entities denote nodes, links, paths, and networks, while the properties include structures and derived features.
  
  Graph analysis tasks <cit.> can be classified into four groups: topology-based tasks, attribute-based tasks, browsing tasks, and overview tasks. Complex tasks can be decomposed into a set of basic tasks. Alternatively, tasks can be represented as a combination of two fundamental tasks <cit.>: analyzing topology for given attributes, and analyzing attributes for a given topological structure. These two tasks are supported with respect to topological structures, including nodes, edges, clusters, node neighbors, paths, and substructures.
  
  A recent study <cit.> proposes a multi-level typology to facilitate specific task classifications. Likewise, 29 group-level graph visualization tasks <cit.> are classified into four groups: group only tasks, group-node tasks, group-link tasks, and group-network tasks. From the viewpoint of graph-based sensemaking, four categories of graph visualization tasks <cit.> are introduced: visualization and exploration; global, local, and hybrid views; subgraph mining and interaction. Without loss of generality, this paper follows their notations and design specified tasks. A typical graph analysis system named Network Repository <cit.> provides users with the ability to explore, visualize, and compare data along many different dimensions interactively and in real-time. By combining global network statistics, local node-level network statistics, and features, users can easily discover key insights into the data.
  
  
  
   §.§ Distributed Analysis and Federated Learning
  
  
  Machine learning is benefited from the ability to train increasingly sophisticated models with the unprecedented growth of data collection <cit.>. To overcome the problem of high computational cost for analyzing large-scale data, parallel or distributed computing has become popular <cit.>. Similarly, decentralized machine learning approaches can be reformulated from centralized versions. There are two basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling <cit.>.
  
  Much effort is paid to improve communication efficiency. For instance, minimizing the number of rounds of communication works well for cases where data is unevenly distributed over an extremely large number of nodes <cit.>. A new framework is proposed to manage asynchronous data communications between clients and servers with flexible consistency, elastic scalability, and fault tolerance <cit.>.
  
  To protect the privacy data during the process of communication, a Homomorphic Encryption (HE) scheme <cit.> is designed to preserve structures of the original message space. HE can be leveraged to privacy-preserving training or prediction of linear regression, linear classifiers, decision trees, matrix factorization, and neural networks. To address the problem of non-linear activation functions, a HE-based neural network scheme <cit.> is proposed with an interactive protocol between the data owner and the model owner. The calculated transformation of the data owner is swapped in an encrypted form with the result from the model.
  
  
  As a pioneering work on privacy-preserving computing, secure multi-party computation (MPC) <cit.> guarantees that clients can only get the final cumulative model weight. Recently, federated learning emerged as a new privacy-protection scheme to construct a global machine learning model with distributed multiple clients <cit.>.
  To improve the training efficiency while protecting the privacy of multiple parties, local training data is kept from the central server.
  It is trained in a decentralized manner on multiple remote clients without transferring raw data. By integrating parameters from clients, the server can compose a global model.
  For large-scale graph data, distributed processing is needed. A distributed implementation of the Dijkstra algorithm <cit.> can handle various graph problems like the depth first search in an undirected graph. TUX^2 <cit.> is a distributed engine that supports the layout and computation of graphs with billions of edges and outperforms other state-of-the-art graph engines by using a series of graph-based optimizations.
  
  To our best knowledge, research on using federated learning for graph analysis is rare. A distributed learning algorithm on graph generalizes the previous work on federated learning <cit.> and provides a fully decentralized framework with localized data of individual nodes kept from one another. The entire learning process over nodes does not use a central server and hence is a peer-to-peer method. A distributed graph neural network is constructed by following the scheme of federated learning <cit.>. The algorithm uses a similarity matrix to capture the high-distance structure of nodes precisely in graph neural network.
  
  
  
  
  
  
  
  
  
  
  
  
  
  § PROBLEM FORMULATION
  
  For the reason of data privacy, directly analyzing graphs in multiple clients is difficult.
  Our solution is to extract joint representations from multi-party graphs and use joint representations for analysis.
  However, existing federated learning frameworks are inapplicable for multi-party graphs, because the data characteristics and analysis tasks of multi-party graphs are quite diverse.
  Designing a model that extracts joint representations with privacy-persevering is a nontrivial issue.
  
  Given K parties, we define G_k as a graph in the k-th party, where G_k=(V_k,E_k) and V_k, E_k represent the node set and edge set, respectively.
  Each graph G_k owns the identical attributes A_k=a_1, a_2,..,a_J, where J denotes the dimension of attributes.
  Each node v has a public ID.
  Nodes from different graphs may have the same public ID.
  Our goal is to construct a federated graph representation model that generates the joint representations R of nodes V_k∈ G_k.
  Sensitive information should be kept locally: attributes of each node, such as age, year and salary; links among nodes; and personal privacy information, like name, e-mail, and address.
  
  
  
  
  § APPROACH OVERVIEW
  
  
  
  
   §.§ Design Goals
   
  We work closely with five domain experts. Two of them are professors whose research focus is on federated learning and privacy analysis, respectively. The other three include one professor and two Ph.D. students. Their research interests are all related to graph representation learning.
  We also consulted two experts of an online game publisher and provider. Both of them have experience in federated learning and graph analysis research.
  Through discussions with these experts, we identify the following design goals:
  
  
  
    G Global representation learning model for multi-party graphs data.
  Considering that the data distribution can be distinctive for different parties, a globalized criterion is needed to ensure all computations are secured and generating satisfying results.
  
  
    R Representations learning for each party graph.
  The main goal of multi-party graphs representation learning is to derive the localized graph representation of each party. In particular, localized representations should be:
  [ R1
      ]
  
    * Privacy-preserving:
  Parties are not allowed to share or transmit their raw data, which should be kept locally to avoid the leakage of sensitive information.
  
  
    * High-quality:
  Local representations learned by our decentralized scheme should achieve comparable performance with the ones learned in a centralized manner.
  
  
    * Information-diverse:
  Learned local representations are comprehensive and can enlighten insights about graphs from various aspects. Such representations should be extracted on the basis of rich and diverse characteristics of a graph, such as the structure information, the side information (node attributes), and graph embedding results.
  
  
  
    CCustomizations support.
  Analysis tasks vary with different users, and thus a flexible scheme is needed. Users should be allowed to customize analysis methods and control relevant parameters of different steps upon their preferences.
  
  
  
  
  
   §.§ Approach Overview
  
  Our general approach is shown in <ref>. The central component of our approach is a server that runs a global federated graph representation model (FGRM). The server communicates with individual clients, each of which owns its local graph data and runs its local . And with the user interface to provide data for various views.
  
  is designed to extract multiple graph representations (G). It runs in a server-client mode,
  and contains two components: graph representation and federated computing.
  
  The graph representation of each local graph is computed based on three components (R2, R3): the embedding component, the structure component, and the attribute component.
  The federated computing is used to federate graph representations from multi-party graphs.
  
  The federated computing (R1, C) includes three parts: federated initiation, client-side update, and server-side update.
  In the federated initiation, the server distributes , predefined encryption schemes, and related rules to multiple remote clients.
  The client-side module updates with the local graph and sends extracted graph representations to the server.
  The server-side module collects and handles these representations.
  Next, the server sends back the representations to each client.
  The update process is iterated until the specified number of rounds is reached.
  Finally, the server receives federated graph representations from multi-party graphs.
  
  We design and implement a visual interface to visualize different federated graph representations.
  Users configure and build by custom schemes in the server view for extracting federated representations from multi-party graphs (C).
  The embedding view, the attribute view, and the structure view display the federated embedding representation, the federated attribute representation, and the federated structure representation, respectively.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § FEDERATED GRAPH REPRESENTATION MODEL
  
  
  
  
   §.§ Graph Representation
  
  supports the construction of three different types of graph representations: graph embedding, node attribute, and structure information. These representations depict graph information from different aspects, making suitable for various visual analysis tasks.
  For the purpose of simplicity, the federated graph representations are denoted as R=(W_emb, W_att, W_struc). Here, the federated embedding representation is denoted as W_emb. The federated atrribute representation is denoted as W_att = (W_att_1, W_att_2,..., W_att_P), and P denotes the dimension of attributes. The federated structure representation is denoted as W_struc.
  
  
  
  
    §.§.§ The Embedding Component
  
  The embedding component is used to construct a graph embedding representation of a graph. This representation converts the node set into low dimensional vectors in a canonical space <cit.>.
  
  
  
  Input:
  The input includes a graph G=(V,E) with attributes A, an embedding model, and corresponding parameters.
  
  Extraction:
  For a graph G, its embeddings are generated from a graph embedding model.
  Some models only use the topology to extracted representations, while some require node features.
  For embedding learning models that require topology and features as the input, the final representation is extracted directly by the model with G and A.
  For those models that only require topology as the input, basic embedding vectors are extracted by the model with G.
  Then, features of nodes are extracted by following these steps.
  First, one-hot vectors are extracted to represent categorical attributes and text attributes.
  Then, normalized vectors are extracted to represent the numerical attributes.
  Feature vectors are then concatenated by these two vectors.
  Thereafter, feature vectors are reduced to the same number of dimensions as basic embedding vectors.
  The embedding representation is concatenated by reduced feature vectors and basic embedding vectors, yielding a high dimensional vector for each node.
  
  Output:
  A set of vectors of nodes is generated.
  
  
  
    §.§.§ The Structure Component
  
  The structure component is used to construct the connection relationships of a graph.
  The raw connection relationships are sensitive.
  Therefore, the structures are restructured from the embeddings of the graph.
  
  Input:
  The input includes a graph G=(V,E) with A, an embedding method, and corresponding parameters.
  
  Extraction:
  The embedding can be extracted by the embedding component or by specified embedding models.
  Then, the distance matrix is calculated by node embeddings.
  The edges among nodes are extracted by the user-specified reconstruction method with the distance matrix.
  
  The reconstruction is controlled by predefined parameters to avoid privacy disclosure.
  Here, different embedding methods can be used to support different analysis tasks.
  Some methods are strong in link prediction and graph reconstruction, while some are good at node clustering.
  This component and embedding component can use different embedding methods for specified analysis tasks.
  
  Output:
  Reconstructed graph structures are output.
  
  
  
  
  
    §.§.§ The Attribute Component
  
  The attribute component is used to construct the attribute distribution of a graph. Attribute distributions are extracted to avoid privacy disclosure.
  
  
  Input:
  The input includes a graph G=(V, E) with attributes A, the bin size of the attribute distribution and filter condition.
  
  Extraction:
  For numeric attributes, the bin size of the distribution is specified by users.
  For categorical attributes, the bin size of the distribution is the dimensions of attributes.
  Those data types that are less meaningful for counting (e.g., name) are not used.
  Moreover, the topology attributes can also be extracted. These attributes are important to the analysis of the nodes of a graph, such as identifying the social influence in the social media network.
  To avoid privacy exposure, the extraction only constructs topology distributions rather than topology values.
  The distribution of the topology attribute of one node characterizes the node.
  The supported topology metrics include:
  (1) Degree, (2) Betweenness, (3) Eigenvector, (4) PageRank, (5) Clustering Coefficient, (6) Average Nearest Neighbors Degree (KNN).
  This component will filter out specific nodes according to the filter conditions, and count the attribute distribution of these nodes (e.g., extracting the attribute distribution of players whose age is between 10 and 30).
  
  Output:
  The attribute distribution of each node is extracted.
  
  Note that other graph representation components can also be designed for specified graph visual analysis tasks.
  
  
  
   §.§ Federated Computation
  
  Federated computation is used to federate graphs and generate joint representations.
  The process contains three steps: federated initialization, server-side update, and client-side update.
  
  
  
    §.§.§ Federated Initialization
  
  Federated initialization sets the configuration of the federation model: encryption schemes, rules for computing feature vectors, and the distribution of the model.
  
  Encryption:
  We provide different encryption schemes to protect the transmission of data, although the transmitted data contains no sensitive information.
  Sometimes, the data owner still has concerns about data privacy, so our model employs encrypted federated average and encrypted model training <cit.>.
  Specifically, our model is implemented with the federated functions of TensorFlow (e.g., federated_mean and federated_max).
  TensorFlow uses homomorphic encryption <cit.> to secure the transmission process.
  
  Attributes of nodes can be used to specify an individual's identity uniquely. A traditional way of protecting privacy is to transfer only attribute distributions of nodes. Unfortunately, the identity can be re-identified by exploiting the side information or schematic meaning of data <cit.>. Thus, employs multiple attribute distribution protection models to improve results:
  (1) syntactic anonymization
  models: k-anonymity <cit.> and l-diversity <cit.> <cit.>.
  (2) differential privacy models: Laplace mechanism <cit.> and exponential mechanism <cit.>.
  
  Computing feature vectors:
  The server counts fields of categorical attributes from all clients,
  and sets the corresponding one-hot vector for each field.
  Then, the server counts the maximum and minimum values of each numerical attribute and formulate the normalization standard of each attribute.
  Finally, each client calculates feature vectors of each node based on computing rules.
  
  The distribution of :
  The server distributes our and relevant settings to each client.
  The weights of the model (the hidden layer) are the embedding results of the graph.
  The weights compose an N × M matrix, where the row number N is the number of different nodes of all graphs, and the column number M is the dimensions of the vector of a node.
  M can be configured by users.
  A row presents the embedding representation of a node.
  Models in both clients and the server have the same weight.
  However, the nodes of local graphs are different.
  To find the embedding of the row corresponding to each node, the server unifies the row index of each node of all clients.
  It should be noted that the node counts of graphs in clients are different.
  The model makes statistics of the number of graph nodes from all clients and the server, and then sets the index of the row of the matrix corresponding to each node.
  
  
  
    §.§.§ Client-side Update
  
  Client-side update runs on each client.
  For the embedding component and the structure component, the server distributes a graph representation model and the initial weights of the model to each client in the federated initiation.
  Each client executes the model with an initial weight.
  Then, each client learns the graph representation from the learning model with the local graph per round,
  and calculates the gradients that encode the differences between weight pairs between two weights.
  Thereafter, each client sends gradients to the server.
  This process does not transmit the raw data, but only transfers the gradients of the learning model.
  
  Each client calculates W_att by a user-specified attribute distribution protection model.
  Then, W_att is encrypted and transmitted to the server by means of TensorFlow.
  Note that, secure aggregation protocols and homomorphic encryption algorithms <cit.> are supported by TensorFlow.
  
  
  
  
  
  
  
  
    §.§.§ Server-side Update
  
  The server randomly generates the weights of the embedding learning model and distributes the model with weights to each client.
  The server collects gradients of models from clients to fulfill federated average per round.
  Then the server computes the weighted average of gradients according to the node number of each client.
  Next, new weights are computed based on weights and averaged gradients, and are sent back to each client.
  The server executes the weights updating process iteratively until the specified number of rounds is reached.
  The weights of the model, W_emb, are learned from graphs in clients.
  This transmission process does not transmit raw data.
  
  The federated structure representations W_struc is generated based on W_emb with link prediction and graph restructuration algorithms. For instance, the distance matrix of nodes is calculated.
  Edges can be generated by calculating the nearest |E| node pairs.
  The federated attribute representation W_att is calculated by means of TensorFlow.
  
  
  
  
  
  
  
  
  
  § VISUAL INTERFACE
  
  <ref> shows the interface of our system. It consists of five views:
  a server view (<ref> (A)) that provides configuration (<ref> (A1)), data selection (<ref> (A2)) and model monitoring (<ref> (A3));
  a client view (<ref> (B)) that shows the information and the process state of clients;
  an embedding view (<ref> (C)) that shows federated embedding representations;
  a structure view (<ref> (D)) that shows federated structure representations: and an attribute view (<ref> (E)) that visualizes federated attribute representations.
  
  
  
   §.§ The Server View
  
  Within the server view (<ref> (A)),
  users can configure graph learning models, multiple parameters and encryption schemes (<ref> (A1)), and monitor the running process of (<ref> (A3)).
  The loss and the accuracy of are shown in a line chart (<ref> (A3)).
  Users can choose the federated graph representation anytime in a training process and visualize them in other views (<ref> (F1)).
  Through these visual graphs, users can explore the training representation, verify the accuracy of the representation, and evaluate the models and parameters.
  
  
  
  
   §.§ The Client View
  
  In the client view (<ref> (B)), users can observe the general information, the running state, and the training process of each client.
  Users can select a client to examine its process state and visualize its federated graph representations in other views.
  
  
  
  
  
   §.§ The Embedding View
  
  The embedding view contains (<ref> (C)) multiple visualization components associated with federated graph embedding representations.
  Following visual graphs are supported: the projection view (<ref> (C1)), the clustering view (<ref> (C2)), and the anomaly view ((<ref> (C3))).
  
  Projection view:
  This view shows the distance of nodes of multi-party graphs in high-dimensional embedding space.
  Each point in the view represents a node (<ref> (C1)).
  The node color encodes clustering information or anomaly information.
  Interactive actions such as panning, zooming, and lasso-based selection are supported.
  Users can select nodes to study attribute distributions in the attribute view and their reconstructed structures in the structure view.
  
  Cluster view:
  This view uses a table to visualize the clustering result of nodes from multi-client graphs according to federated embedding representations(<ref> (C2)).
  Users can select nodes from one of the clusters for visualizing their attribute distributions and reconstructed structures in other views (<ref> (D2) (E2)).
  
  Anomaly view:
  This view lists the anomaly detection results of multi-party graphs based on federated embedding representations (<ref> (C3)).
  When users select some nodes, their attribute distributions and reconstructed structures are shown in other views.
  
  Control panel:
  With the control panel, users can configure parameters or methods in each view (in the top right corner).
  In the projection view, different projection methods including MDS <cit.>, and t-SNE <cit.> can be chosen.
  In the cluster view, different node clustering algorithms and corresponding parameters, including K-Means <cit.> and DBSCAN <cit.> can be set.
  In the anomaly view, One-Class SVM <cit.> or IsolationForest <cit.> can be used for nodes' anomaly detection.
  
  
  
  
  
   §.§ The Structure View
  
  The structure view (<ref> (D)) depicts reconstructed structures of selected nodes from other views.
  To make structure exploration clear and avoiding heavy overlapping, this view hides nodes without any edge.
  Different layout methods in the view can be chosen.
  
  
  
  
  
   §.§ The Attribute View
  
  In the attribute view (<ref> (E)), multiple histograms are used to visualize the attribute distribution of multi-party graphs.
  Users can interact with bins of histograms (<ref> (F3)) to specify attribute distributions in the corresponding attribute interval.
  The y-axis in each histogram can be either linear or logarithmic.
  
  
  
  
  
  
  
  
  
  § EVALUATION
  
  In implementing , the front-end client was developed with the React framework and D3.js. Our in-house graph visualization engine is employed with rich user interactions, and flexible customizations.
  TensorFlow is used to compute the federated average of the attribute component. Pytorch is used to execute the graph embedding learning model.
  
  
  Datasets.
  DBLP Dataset:
  This is a paper citation graph dataset.
  Each node represents a paper, and an edge represents the citation relationship between two papers, which has 5 attributes.
  Papers and their citation graphs in four areas are extracted to form a graph: AI, System, Theory, and Interdisciplinary. The total number of papers in each area are 64,232, 62,020, 14,430, and 62,708, respectively.
  
  NetEase-Game-Player Dataset (NEGP):
  This is a game player transaction graph dataset provided by NetEase Co.[http://game.163.com] It is collected in five servers of a massively multi-player online role playing game.
  In each graph, a node represents a player, and an edge represents a transaction between two players.
  
  
  Each player has 36 attributes related to the player's role information and account status, such as role_level, role_class and create_date.
  
  
  
  
  
   §.§ Experiments
  
  
  We conducted several experiments to evaluate our approach.
  Experiments were conducted in a PC with a single Intel (R) Xeon (R) Gold 5218 CPU (a basic frequency of 2.3GHz and 16 cores), 128GB internal memory, and single RTX 2080TI GPU.
  
  
  
    §.§.§ Federated Embedding Representation
  
  Considering that the federated scheme may have a lower quality of embedding representations, the performance and computing cost with our approach and its centralized counterpart were tested on two datasets DBLP <cit.> and NEGP.
  
  Configurations.
  We ran three configurations to evaluate the performance of different models: embedding learning in a single client (ELSC), centralized embedding learning (CEL), and our federated embedding component (FEC).
  
  Data processing.
  DBLP Dataset <cit.>:
  The citation graphs of years 2014-2018 were used in our experiments with CEL and FEC, each of which located in a client.
  The abstract of each paper was encoded as a fix-length vector based on word frequency count.
  For ELSC, the embedding generated from the graph of the year 2016, which is the largest graph among them, was used to generate the performance baseline (ELSC).
  The sub-filed information was employed as the ground truth to evaluate embedding representations with three configurations.
  
  NEGP Dataset:
  The game player transaction graphs from five servers were evaluated with CEL and FEC.
  The graph from game server 1 was used to derive ELSC.
  
  Players were classified into two categories: high and low levels of in-game consumption.
  
  The consumption information was used as the ground truth to evaluate embedding representations with three configurations.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Settings.
  
  Two popular embedding learning methods were employed: DeepWalk <cit.>, an unsupervised approach for learning node representation without utilizing attribute vectors; and GAT <cit.>, one of the most popular neural graph architectures of graphs, which captures both the structure and the feature of each node.
  The random walk step of DeepWalk was firstly applied to generate samples by setting the number of walk times to be 80, and the length of walks to be 40. DeepWalk learned node representations by using the skip-gram model. We set the dimension of representation and the length of the sliding window to be 128 and 10, respectively. The GAT model was configured as follows: the number of layers was 3; the intermediate dimension of representations was 256; three heads were used in GAT. To train GAT, we employed the stochastic gradient descent (SGD) algorithm. The learning rate and the coefficient of L2 regularization were set to be 0.001 and 0.0001, respectively. DeepWalk and GAT of all clients were updated with 300 rounds.
  
  We tested three configurations on the DBLP and NEGP datasets.
  GAT has high computational complexity and memory consumption.
  The CEL was not conducted on GAT.
  All evaluations were derived by a 5-fold cross-validation.
  
  Results.
  The accuracy and time consumption are shown in <ref>.
  The accuracy of FEC has a similar performance with that of CEL, and the accuracy of FEC or CEL is better than that of SCEL. The time consumption of FEC is more than that of SCEL, and less than that of CEL.
  Line charts of the loss of our approach are shown in  <ref>.
  Projections of test dataset embeddings extracted by our approach are shown in <ref> by using t-SNE.
  In the first half of the training process, the embedding already has good adequate performance. Users can early terminate the training by observing the visualization of the results in real-time.
  
  
  
  
  
  
  
  
  
    §.§.§ Federated Attribute Representation
  
  We tested the computing cost of the federated average in the attribute component.
  For the attribute protection model, the time consumption is very short.
  The federated average supported by TensorFlow was used to encrypt attributes distributions of all clients.
  The time consuming of the encrypt could not be ignored.
  
  Settings.
  The computing cost of three aspects was collected: the number of clients (1-30), the number of attributes (1-30), and the node number in each client (1-50,000).
  We evaluated one aspect while fixing the other two.
  Each evaluation was repeated for five times.
  
  Results.
  The influence of each variable on the computing cost is reported in <ref>. The computing cost of the extaraction of federated attribute representations shows a linear complexity over the number of clients and attributes (<ref> (A) (B)) but has little relevance with the node number in each client (<ref> (C)).
  
  
  
  
  
  
    §.§.§ Federated Structure Representation
  
  We evaluated the performance of federated structure representation by link prediction evaluation metrics: the Area Under Curve (AUC) score and Precision <cit.>. Deepwalk was selected because it precisely captures the linkages among nodes from the node sequence generated by random walk. Supervised models such as GAT seek to minimize difference among intra-class nodes, and may lead to a result that node embeddings of same category are concentrative in space, which is problematic for linkage reconstruction.
  
  Setting.
  We used training representations of the entire dataset to test the performance.
  We selected 10,000,000 edge pairs to test AUC score and set L of Precision as 1000.
  
  Results.
  Given G=(V,E) and W_emb, the distance matrix of nodes is calculated, and the time complexity is O(|V|^2).
  Edges can be generated by calculating the nearest |E| node pairs. Its time complexity is O(|V|^2log(|E|)) by using the heap sorting technique.
  The total time complexity O(|V|^2 +|V|^2log(|E|)).
  Results are show in <ref>.
  AUC score is high on two datasets.
  Precision is not satisfactory on the NEGP dataset, probably because the dataset has a high data complicacy.
  
  
  
  
  
  
  
  
  
   §.§ Case Study
  
  
  
  
    §.§.§ Case 1: NetEase-Game-Player Dataset
  
  We invited an expert to use our to analyze the game data. He works in NetEase and is skilled at game data analysis. We introduced our system and showed how it works. Then, he used to analyze and explore NEGP datasets freely. His interest was in verifying the validity of the learned model and anomalous trades with .
  He took graphs from four different game servers as the input data (clients) of in the server view (<ref> (A2)).
  Then, he configured to build federated graph representations (<ref> (A1)).
  The general information of the graph from each client is shown in the client view (<ref> (B)).
  The running status and the progress of are shown in the monitoring view (<ref> (A3)).
  The monitor information indicates that the model runs well.
  
  With the obtained representations of all components after 300 rounds of training, the expert saw clear clusters of the embedding in the projection view (<ref> (C1)).
  The structure view showed clear and diverse structures.
  He concluded that performed well.
  He studied the distributions of the main attributes of players (<ref> (a1-5)) and found that the distributions of several attributes are interesting.
  
  While most Role_total_score (players' scores) are low, and a small number of players have scores distributed in the highest interval.
  This result indicates that a small number of players' game progress leads to the vast majority.
  The distribution of Role_equip_score (players' equipment score) and  the distribution of Degree (the number of trades of a player) are generally in a relatively low range (<ref> (a2) (a5)), and imply that most players have low equipment scores and trading records.
  These distributions helped the expert better understand the upgrading speed of the game, the consumption preferences of the players, and the preferences of players in different activities.
  
  He selected 20,526 detected anomalous players (<ref> (F2)) to study anomalies in in-game trading behavior from the anomaly view.
  He found that many anomalous players had no trading record in the structure view (<ref> (D1)), and many players' accounts were banned (<ref> (E1)) in the attribute view. Apparently, these players behaved differently from the rest of all players (<ref> (a1)).
  It should be noted that the status of being banned is one of the most important attributes for game analysis because it indicates that a player may have an illegal plugin or other behaviors that violate game fairness policies <cit.>.
  He selected banned players from the corresponding histogram (<ref> (F3)), and the structure view showed trades among 1,122 players who were banned and detected as anomalies (<ref> (D2)).
  There are 462 trades among 465 players.
  It indicates that some banned players knew each other and may belong to a studio that controls the accounts of many plugin players. In addition, these players may accumulate their virtual wealth in the game onto a specific player's account.
  He selected three structures (<ref> (D2)) because he believed that the selected structures were typical anomalous trading patterns based on his domain knowledge.
  The short and intensive trading chain is the unique characteristic of anomalous trades.
  
  
  
  The Degree distribution showed that some banned players made many trades (<ref> (E2)).
  
  Interestingly, he found that kjjf (cumulative score of an activity) distributions were distributed in the lowest interval (<ref> (E2)), compared with those of all players (<ref> (a4)).
  He gave two possible explanations. The first one is that banned players were banned earlier, and they had no chance to accumulate scores. The second is that some plugin players seek to make money or upgrade the level.
  They made no contribution to kjjf, which is an indicator of entertainment activities.
  
  The three structures with 66 players and 168 trades (<ref> (C)) were also presented to the expert. 113 trades are anomalous trades. The expert was surprised that our system achieved a high detection rate of anomalous trades.
  Raw graph data of each game server was used to learn embeddings and detect anomalous trades. We found that trades among these players are very intensive (<ref> (D)-(G)).
  We recorded structures of each step analysis in this case study.
  These results were presented to the expert.
  Using to detect anomalous trades from four game servers, yields detection rate of 50.90% (<ref> (A)).
  However, when a single game server data is employed, the detection rate are much lower (<ref> (D)-(G)).
  This indicates that federated graph representations extracted from multi-party graphs can capture more underlying insights.
  
  In this case study, the expert achieved a detection rate of 67.26% (<ref> (C)).
  empowers him to improve the detection rate of anomalous trades and discover anomaly trading patterns.
  
  
  
  
  
  
  
  
    §.§.§ Case 2: DBLP Dataset
  
  We invited a professor to use our to analyze the DBLP dataset.
  His research area is soical network analysis.
  He wanted to analyze the clustering result of the paper citation data.
  
  He chose data from 2014 to 2018 and configured the embedding component with DeepWalk.
  He selected the training results of the last round and observed federated graph representations in other views.
  He modulated different parameters of the K-Means algorithm from 3 to 6 and selected 5 (<ref> (B)).
  Then, he selected different clusters.
  By observing the attribute view (<ref> (C)), he found differences of attributes: Ref_num (the number of references), N_citation (the number of citations), and Average_neighbor_degree, the distributions of which are shown in <ref> (C1).
  Clusters (a) and (d) have similar distributions with distributions of the entire set of papers.
  He inferred that most papers belong to these two clusters, so they have similar distributions.
  However, the distributions of three clusters (b) (c) and (d) lie in the lower interval.
  This indicates that those papers falling into these clusters are rarely cited.
  He inferred that these papers were published recently.
  The distributions in clusters (c) and (e) lie in the lowest interval.
  Clusters (c) and (e) have fewer papers than other clusters.
  The Ref_num and N_citation distributions indicate that the numbers of citations and references of papers in these two clusters are small.
  The Average_neighbor_degree implies that the number of citations and references of cited papers and reference papers is also small.
  He concluded that papers in two clusters are not attractive.
  
  We used raw data of each year from 2014-2016 to learn embeddings(<ref> (A2)-(A4)).
  <ref> (A1) shows the projection of federated embedding representations of years 2014-2016.
  The color encodes ground truth labels.
  We found that papers with the green label are separated in 2014 and 2015, but clustered together in 2016.
  Papers in red circles (<ref> (A1)-(A4)) are clustered in terms of both data representations.
  It is regarded as a cluster, even though they have different labels.
  It indicates that federated graph representations extracted from multi-party graphs can capture more features and information, and help find clusters with unique features.
  
  
  
  
   §.§ Expert Reviews
  
  
  
  
  We interviewed the expert involved in our first case study (<ref>). The expert thought that the findings could help to improve strategies of the anomalous player detection.
  He also believed that the clustering result of players of different clients might be used to stimulate more strategies for studying players of different clusters with unique features.
  The professor in the second case study (<ref>) suggested that our system supports the extraction and visualizations of keywords or abstracts of papers. He hoped that analysts should be able to control privacy standards and analyze more data or dimensions; otherwise, some interesting insights would be missed.
  
  To evaluate the effectiveness of our approach, we also conducted one-on-one interviews with five additional domain experts from NetEase Co.
  They are all skilled at game data analysis, graph analysis, and federated learning.
  With a live, hands-on demonstration for approximately 10 minutes, we showed them case studies. We discussed the feasibility of and findings and solicited feedback from them.
  They all confirmed that our approach could help them analyze features and information of players without touching raw data, and empowers them to explore multiple aspects and features of graphs.
  They liked our intuitive user interface for visual analysis of large-scale graphs. One expert commented on our system by saying: “...The system can help me validate training results of the federated model by the visual interface and help accomplish various analysis tasks of multiple graphs.
  ”
  Another expert claimed: “...When I want to analyze graphs which are distributed in multiple clients, the accessibility of graphs limits me. can solve these problems and give wonderful visualizations of features from graphs.”
  
  
  
  
  
  
  
  § DISCUSSIONS
  
  
  Privacy.
  In the computing of federated representations, the server computes the weighted average of gradients of each client model and sends weights to each client.
  By jointly averaging gradients, the model can be trained by using multi-party graphs without switching raw data.
  The federated average algorithm computes the attribute representations from each client graph with the encryption of TensorFlow. The encrypted algorithm prevents transmission data from being intercepted. Although the transmitted data contains no sensitive information, it is still possible that privacy-related data can be inferred from non-sensitive information.
  At the same time, to prevent the identification of individuals from attribute distributions, our model employs multiple strategies like syntactic anonymization models and differential privacy models.
  Structure representations are reconstructed by embedding representations, and reconstructed parameters could be used to adjust accuracy.
  In fact, a small difference between raw structures and reconstructed structures can protect privacy <cit.>.
  In the fields of secure multiple computing and homomorphic encryption, there are various strategies to handle different privacy and security issues. Our approach is fully compatible with them and supports interactive configurations.
  
  Expansibility.
  Our approach can accomplish various graph visual analysis tasks. Three components are employed for constructing different types of graph representations: embedding representation, attribute representation, and structure representation. Users can freely configure strategies, methods, and parameters of each component.
  As shown in case studies, users accomplished different analysis tasks for multi-party graphs, including anomaly detection, clustering, and comparison.
  Experts highly rated our approach in gaining and identifying patterns.
  Our approach also supports to design new components for constructing distinctive graph representations. Various visualization styles for different graph representations can also be employed to fulfill a variety of complex tasks.
  
  
  Scalability.
  Our approach constructs federated graph representations from multi-party graphs with reasonable scalability.
  is compatible with different models and encrypt strategies for different tasks and requirements.
  We conducted multiple experiments to measure the performance of the federated graph representation (<ref>).
  The efficiency of in terms of data size depends on the selected model. For the embedding component, GAT can only handle a moderate-sized data due to the use of matrix, and DeepWalk can support large-sized data because it uses the skip-gram technique.
  The other two components also support extracting representations from large-scale graphs.
  Our in-house visualization engine is amenable for visualizing large-scaled graphs with rich user interactions.
  
  
  Performance.
  Our model indeed extracted high-quality federated graph representations from multi-party graphs. Federated representations improve the efficiency of anomaly detection and clustering results compared with using the representation extracted from single data.
  with rich interactions empowers experts to accelerate the process of detecting anomalous trades and comparing clusters of papers.
  There are three conclusions drawn from experiments.
  
  
    * Compared with the centralized counterpart, our approach can generate results with a similar quality, and achieve a better running performance.
  
    * The graph can be reconstructed well with federated structure representations in terms of AUC score and precision, and the reconstructed structures keep differences to prevent privacy leaks.
  
    * The federated attribute representation can be constructed with relatively low computing costs.
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  This paper presents , a federation approach that constructs joint representations of multi-party graphs, and supports privacy-preserving visual analysis of multi-party graphs.
  In the future, we plan to explore various encryption strategies. We alsp plan to extend our approach to other graph data. Currently, we assume that multi-party graphs have identical attributes. We will improve to support heterogeneous graphs.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  abbrv-doi
  
  
  
  
  
  
  
  
  