Federated Graph Classification over Non-IID Graphs
Year: 2021

Abstract:
Federated learning has emerged as an important paradigm for training machine learning models in different domains. For graph-level tasks such as graph classification, graphs can also be regarded as a special type of data samples, which can be collected and stored in separate local systems. Similar to other domains, multiple local systems, each holding a small set of graphs, may benefit from collaboratively training a powerful graph mining model, such as the popular graph neural networks (GNNs). To provide more motivation towards such endeavors, we analyze real-world graphs from different domains to confirm that they indeed share certain graph properties that are statistically significant compared with random graphs. However, we also find that different sets of graphs, even from the same domain or same dataset, are non-IID regarding both graph structures and node features. To handle this, we propose a graph clustered federated learning (GCFL) framework that dynamically finds clusters of local systems based on the gradients of GNNs, and theoretically justify that such clusters can reduce the structure and feature heterogeneity among graphs owned by the local systems. Moreover, we observe the gradients of GNNs to be rather fluctuating in GCFL which impedes high-quality clustering, and design a gradient sequence-based clustering mechanism based on dynamic time warping (GCFL+). Extensive experimental results and in-depth analysis demonstrate the effectiveness of our proposed frameworks.

heading: 1 Introduction
text: Federated learning (FL) as a distributed learning paradigm that trains centralized models on decentralized data has attracted much attention recently [28, 53, 25, 18, 17]. FL allows local systems to benefit from each other while keeping their own data private. Especially, for local systems with scarce training data or lack of diverse distributions, FL provides them with the potentiality to leverage the power of data from others, in order to facilitate the performance on their own local tasks. One important problem FL concerns is data distribution heterogeneity, since the decentralized data, collected by different institutes using different methods and aiming at different tasks, are highly likely to follow non-identical distributions. Prior works approach this problem from different aspects, including optimization process [25, 18], personalized FL [13, 6, 8], clustered FL [9, 15, 2], etc.
As more advanced techniques are developed for learning with graph data, using graphs to model and solve real-world problems becomes more popular. One important scenario of graph learning is graph classification, where models such as graph kernels [44, 34, 36, 45] and graph neural networks [21, 43, 49, 46, 47, 48] are used to predict graph-level labels based on the features and structures of graphs. One real scenario of graph classification is molecular property prediction, which is an important task in cheminformatics and AI medicine. In the area of bioinformatics, graph classification can be used to learn the representation of proteins and classify them into enzymes or non-enzymes. For collaboration networks, sub-networks can be classified regarding the information of research areas, topics, genre, etc. More applicable scenarios include geographic networks, temporal networks, etc.
⇤Corresponding author. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Since the key idea of FL is the sharing of underlying common information, as [23] discusses that real-world graphs preserve many common properties, we become curious about the question, whether real-world graphs from heterogeneous sources (e.g., different datasets or even divergent domains) can provide useful common information among each other? To understand this question, we first conduct preliminary data analysis to explore real-world graph properties, and try to find clues about common patterns shared among graphs across datasets. As shown in Table 1, we analyze four typical datasets from different domains, i.e., PTC_MR (molecular structures), ENZYMES (protein structures), IMDB-BINARY (social communities), and MSRC_21 (superpixel networks). We find them to indeed share certain properties that are statistically significant compared to random graphs with the same numbers of nodes and links (generated with the Erdős–Rényi model [7, 10]). Such observations confirm the claim about common patterns underlying real-world graphs, which can largely influence the graph mining models and motivates us to consider the FL of graph classification across datasets and even domains. More details and discussion about Table 1 can be found in Appendix A.
Although common patterns exist among graph datasets, we can still observe certain heterogeneity. In fact, the detailed graph structure distributions and node feature distributions can both diverge due to various reasons. To demonstrate this, we design and evaluate a structure heterogeneity measure and a feature heterogeneity measure in different scenarios (c.f. Section 4.1). We refer to the graphs possibly with significant heterogeneity in our cross-dataset FL setting as non-IID graphs, which concerns both structure non-IID and feature non-IID, where naïve FL algorithms like FedAvg [28] can fail and even backfire (c.f. Section 6.2). Moreover, as the heterogeneity varies from case to case, a dynamic FL algorithm is needed to keep track of such heterogeneity of non-IID graphs while conducting collaborative model training.
Due to the observations that the graphs in one client can be similar to those in some clients but not the others, we get motivated by [2] and find it intuitive to consider a clustered FL framework, which assigns local clients to multiple clusters with less data heterogeneity. To this end, we propose a novel graph-level clustered FL framework (termed GCFL) through integrating the powerful graph neural networks (GNNs) such as GIN [43] into clustered FL, where the server can dynamically cluster the clients based on the gradients of GNN without additional prior knowledge, while collaboratively training multiple GNNs as necessary for homogeneous clusters of clients. We theoretically analyze that the model parameters of GNN indeed reflect the structures and features of graphs, and thus using the gradients of GNN for clustering in principle can yield clusters with reduced heterogeneity of both structures and features. In addition, we conduct empirical analysis to support the motivation of clustered FL across heterogeneous graph datasets in Appendix A.
Although GCFL can theoretically achieve homogeneous clusters, during its training, we observe that the gradients transmitted at each communication round fluctuate a lot (c.f. Section 5.1), which could be caused by the complicated interactions among clients regarding both structure and feature heterogeneity, making the local gradients towards divergent directions. In the vanilla GCFL framework, the server calculates a matrix for clustering only based on the last transmitted gradients, which ignores the client’s multi-round behaviors. Therefore, we further propose an improved version of GCFL with gradient-series-based clustering (termed GCFL+).
We conduct extensive experiments with various settings to demonstrate the effectiveness of our frameworks. Moreover, we provide in-depth analysis on the capability of them on reducing both structure and feature heterogeneity of clients through clustering. Lastly, we analyze the convergence of our frameworks. The experimental results show surprisingly positive results brought by our novel setting of cross-dataset/cross-domain FL for graph classification, where our GCFL+ framework can effectively and consistently outperform other straightforward baselines.

heading: 2 Related works
text: Federated Learning Federated learning (FL) has gained increasing attention as a training paradigm under the setting where data are distributed at remote devices and models are collaboratively trained under the coordination of a central server. FedAvg was first proposed by [27] which illustrates the general setting of an FL framework. Since the original FedAvg relies on the optimization by SGD, data of non-IID distribution will not guarantee the stochastic gradients to be an unbiased estimation of the full gradients, thus hurting the convergence of FL. In fact, multiple experiments [53, 25, 18] have shown that the convergence will be slow and unstable, and the accuracy will degrade with FedAvg when data at each client are statistically heterogeneous (non-IID). [53, 15, 12] proposed different data sharing strategies to tackle the data heterogeneity problem by sharing the local device data or serverside proxy data, which still requires certain public common data, whereas other studies explored the convergence guarantee under the non-IID setting by assuming bounded gradients [39, 51] or additional noise [19]. There are also works seeking to reduce the variance of the clients [26, 18, 25]. Furthermore, multiple works have been proposed to explore the connection between model-agnostic meta-learning (MAML) and personalized federated learning [8, 4]. They aim to learn a generalizable global model and then fine-tune it on local clients, which may still fail when data on local clients are from divergent domains with high heterogeneity. Some personalized FL works [6, 24] studied the bi-level problem of optimization which decouples the local and global optimization, but having each client maintain its own model can lead to high communication cost among the clients and the server. While personalization in the FL setting can address the client heterogeneity problem to some extent, the clustered FL framework [33] can incorporate personalization at the group level to keep the benefits of personalized FL and reduce the communication cost simultaneously.
Federated Learning on Graphs Although FL has been intensively studied with Euclidean data such as images, there exist few studies about FL for graph data. [22] first introduced FL on graph data, by regarding each client as a node in a graph. [3] studied the cross-domain heterogeneity problem in FL by leveraging Graph Convolutional Networks (GCNs) to model the interaction between domains. [29] studied spatio-temporal data modeling in the FL setting by leveraging a Graph Neural Network (GNN) based model to capture the spatial relationship among clients. [5] proposed a generalized federated knowledge graph embedding framework that can be applied for multiple knowledge graph embedding algorithms. Moreover, there are several works exploring the GNNs under the FL setting: [16, 54, 40] focused on the privacy issue of federated GNNs; [37] incorporated model-agnostic metalearning (MAML) into graph FL, which handled non-IID graph data while also preserving the model generalizability; [52] studied the missing neighbor generation problem in the subgraph FL setting; [38] proposed a computationally efficient way of GCN architecture search with FL; [11] implemented an open FL benchmark system for GNNs. Most existing works consider node classification and link prediction on graphs, which cannot be trivially applied to our graph classification setting.

heading: 3 Preliminaries

heading: 3.1 Graph Neural Networks (GNNs)
text: [42] provides a taxonomy that categorizes Graph Neural Networks (GNNs) into recurrent GNNs, convolutional GNNs, graph autoencoders, and spatial-temporal GNNs. In general, given the structure and feature information of a graph G = (V,E,X), where V , E, X denote nodes, links and node features, GNNs target to learn the representations of graphs, such as a node embedding hv 2 Rdv , or a graph embedding hG 2 RdG . A GNN typically consists of message propagation and neighborhood aggregation, in which each node iteratively gathers the information propagated by its neighbors, and aggregates them with its own information to update its representation. Generally, an L-layer GNN can be formulated as
h (l+1) v = (h (l) v , agg({h(l)u ;u 2 Nv})), 8l 2 [L], (1)
where h(l)v is the representation of node v at the lth layer, and h (0) v = xv is the node feature. Nv is neighbors of node v, agg(·) is an aggregation function that can vary for different GNN variants, and represents an activation function.
For a graph-level representation hG, it can be pooled from the representations of all nodes, as hG = readout({hv; v 2 V }), (2)
where readout(·) can be implemented as mean pooling, sum pooling, etc, which essentially aggregates the embeddings of all nodes on the graph into a single embedding vector to achieve tasks like graph classification and regression.
3.2 The FedAvg algorithm
McMahan et al. [28] proposed an SGD-based aggregating algorithm, FedAvg, based on the fact that SGD is widely used and powerful for optimization. FedAvg is the first basic FL algorithm and is commonly used as the starting point for more advance FL framework design.
The key idea of FedAvg is to aggregate the updated model parameters transmitted from local clients and then re-distribute the averaged parameters back to each client. Specifically, given m clients in total, at each communication round t, the server first samples a partition of clients {Si}(t). For each client Si in {Si}(t), it trains the model downloaded from the server locally with its own data distribution Di for Elocal epochs. The client Si then transmits its updated parameters w(t)i to the server, and the server will aggregate these updates by
w (t+1) =
mX
i=1
|Di| |D| w (t) i , (3)
where |Di| is the size of data samples in client Si and |D| is the total size of samples over all clients. After generating the aggregated parameters (the global model updates), the server broadcasts the new parameters w(t+1) to remote clients, and at the (t+ 1) round clients use w(t+1) to start their local training for another Elocal epochs.
4 The GCFL framework

heading: 4.1 Non-IID structures and features across clients
text: From Table 1 we notice that real-world graphs tend to share certain general properties across different graphs, datasets and even domains, which motivates the graph-level FL framework. However, there still exist differences when the detailed graph structures and node features are being considered. In Table 2, we present the average pair-wise structure heterogeneity and feature heterogeneity among graphs in a single dataset, a single domain, and across different domains. Specifically, for structure heterogeneity, we use the Anonymous Walk Embeddings (AWEs) [14] to generate a representation for each graph, and compute the Jensen-Shannon distance between the AWEs of each pair of graphs; for feature heterogeneity, we calculate the empirical distribution of feature similarity between all pairs of linked nodes in each graph, and compute the Jensen-Shannon divergence between the feature similarity distributions of each pair of graphs.
As we can observe in Table 2, both graph structures and features demonstrate different levels of heterogeneity within a single dataset, a single domain, and across different domains. We refer to graphs with such structure and feature heterogeneity as non-IID graphs. Intuitively, directly applying naïve FL algorithms like FedAvg on clients with non-IID graphs can be ineffective and even backfiring. To be specific, structure heterogeneity makes it difficult for a model to capture the universally important graph structure patterns across different clients, whereas feature heterogeneity makes it hard for a model to learn the universally appropriate message propagation functions across different clients. How can we leverage the shared graph properties among clients while addressing the non-IID structures and features across clients?

heading: 4.2 Problem formulation
text: Motivated by our real graph data analysis in Tables 1 and 2, we propose a novel framework of Graph Clustered Federated Learning (GCFL). The main idea of GCFL is to jointly find clusters of clients with graphs of similar structures and features, and train the graph mining models with FedAvg among clients in the same clusters.
Specifically, we are inspired by the Clustered Federated Learning (CFL) framework on Euclidean data [33] and consider a clustered FL setting with one central server and a set of n local clients {S1, S2, . . . , Sn}. Different from the traditional FL setting, the server can dynamically cluster the
clients into a set of clusters {C1,C2, . . .} and maintain m cluster-wise models. In our GCFL setting, each local client Si owns a set of graphs Gi = {G1, G2, . . .}, where each Gj = (Vj , Ej , Xj , yj) 2 Gi is a graph data sample with a set of nodes Vj , a set of edges Ej , node features Xj , and a graph class label yj . The task on each local client Si is graph classification that predicts the class label ŷj = h⇤k(Gj) for each graph Gj 2 Gi, where h⇤k is the collaboratively learned optimal graph mining model for cluster Ck to which Si belongs. Our goal is to minimize the loss function F (⇥k) := ESi2Ck [f(✓k,i;Gi)], for all clusters {Ck}. The function f(✓k,i;Gi) is a local loss function for client Si which belongs to cluster Ck. In the meantime, we also aim to maintain a dynamic cluster assignment (Si) ! {Ck} based on the FL process.

heading: 4.3 Technical design
text: GNNs are demonstrated to be powerful for learning graph representations and have been wildly used in graph mining. More importantly, the model parameters and their gradients of GNNs can reflect the graph structure and feature information (more details in Section 4.4). Thus, we use GNNs as the graph mining model in our GCFL framework.
Specifically, our GCFL framework can dynamically cluster clients by leveraging their transmitted gradients { ✓i}ni=1, in order to maximize the collaboration among more homogeneous clients and eliminate the harm from heterogeneous clients. According to [33], if the data distribution of clients are highly heterogeneous, the general FL that trains the clients together cannot jointly optimize all their local loss functions. In this case, after some rounds of communication, the general FL will be close to the stationary point, and the norm of clients’ transmitted gradients will not all tend towards zero. Therefore, clustering clients is needed as the general FL approaches to the stationary point. Here, we first introduce a hyper-parameter "1 as a criterion to decide whether to stop the general FL based on whether a stationary point is approached, that is,
mean = k X
i2[n]
|Gi| |G| ✓ik < "1. (4)
In the meantime, if there exist some clients still with large norms of transmitted gradients, it means that clients in the group are highly heterogeneous, and thus clustering is needed to eliminate the negative influence among them. We then introduce the second criterion with a hyper-parameter "2 to split the clusters when
max = max(k ✓ik) > "2 > 0. (5) The GCFL framework follows a top-down bi-partitioning mechanism. At each communication round t, the server receives m sets of gradients {{ ✓i1}, { ✓i2}, . . . , { ✓im}} from clients in clusters {C1,C2, . . . ,Cm}. For a cluster Ck, if kmean and kmax satisfy the Eqs. 4 and 5, the server will calculate a cluster-wise cosine similarity matrix ↵k, and its entries are used as weights for building a full-connected graph with nodes being all clients within the cluster. The Stoer–Wagner minimum cut algorithm [35] is then applied to the constructed graph, which bi-partitions the graph and divides the cluster Ck ! {Ck1,Ck2}. The clustering mechanism based on Eqs. 4 and 5 can automatically and dynamically determine the number of clusters along the FL, while the two hyper-parameters "1 and "2 can be easily set through some simple experiments on the validation sets following [33].
For a client Si in cluster Ck, it tries to find ✓̂k,i that is close to the real solution ✓⇤k,i = argmin✓i2⇥k f(✓k,i;Gi). At a communication round t, the client Sk transmits its gradient to the server
✓tk,i = ✓̂ t k,i ✓t 1k,i . (6)
Since the server maintains the cluster assignments, it can aggregate the gradients cluster-wise by
✓ t+1 k = ✓ t k +
X
i2[nk]
✓tk,i. (7)

heading: 4.4 Theoretical analysis
text: We investigate the problem of graph FL with multi-domain data distribution, and use the gradientbased FL paradigm [27] to facilitate the model training. We theoretically analyze that the gradientbased FL algorithm on GNNs can in principle reduce the structure and feature heterogeneity in clusters, along with the task difference between data from different domains. We study two general problems in order to prove that the gradients can reflect the feature, structure, and task information.
Definition 4.1 Let a function f : X ! Y which maps from the metric space (X , d) to (Y, d0), the function f is considered to have distortion if 8u, v 2 X , 1 d(u, v)  d 0(f(u), f(v))  d(u, v).
Theorem 4.1 (Bourgain theorem [1]) Given an n-point metric space (X , d) and an embedding function f as defined above, 8u, v 2 X , there exist an embedding mapped from (X , d) to Rk with the distortion of the embedding being O(log n).
Problem 1. In GCFL which involves the communication of the gradients between graphs with heterogeneous structures distributed among different clients, the structure and feature difference can
be captured by the GNN gradients.
For simplicity, we solve Problem 1 with the GNN of Simple Graph Convolutions (SGC) [41], through the following two propositions.
Proposition 4.1 Given a graph G with fixed structure represented by the normalized graph Laplacian L = eD 12 eA eD 12 , feature represented with X , and an SGC f(L, X) = softmax(LKX⇥) with weights ⇥ trained on graph G. If we have another graph G0 with different structure L0, the weight difference ||⇥0 ⇥||2 is bounded with the structure difference.
Proposition 4.2 Given a graph G with fixed structure represented by the normalized graph Laplacian L = eD 12 eA eD 12 , feature represented with X , and an SGC f(L, X) = softmax(LKX⇥) with weights ⇥ trained on graph G. If we have another graph G0 with different feature X 0, the weight difference ||⇥0 ⇥||2 is bounded with the feature difference.
We prove proposition 4.1 and 4.2 in Appendix B. We use the Bourgain theorem to bound the difference between embeddings generated with different graph structures/features, and prove that the feature and structure information of a graph is incorporated into the model weights (gradients). By proving that the model weights (gradients) are bounded with the structure/feature difference, we show that the gradients will change with the structure and feature. This further justifies that our proposed gradient based clustering framework GCFL is able to capture the structure and feature information. In addition, we also study the following problem, which allows our GCFL framework to be further extended to cross-task graph-level federated learning in the future.
Problem 2. The communicated gradients in GCFL can also capture the task heterogeneity.
Proposition 4.3 Given a graph G with structure represented by the normalized graph Laplacian L = eD 12 eA eD 12 , and feature represented with X , if trained with different tasks, we will get the Simple SGC with bounded weights.
The proof of proposition 4.3 can be found in Appendix B.
5 GCFL+: improved GCFL based on observation sequences of gradients

heading: 5.1 Fluctuation of gradient norms
text: When observing the norm of gradients for each communication round in GCFL, as shown in Figure 1, we notice that: 1) the norm of gradients continuously fluctuates; 2) different clients can have divergent
scales of gradient norms. The fluctuation of gradient norms and different scales indicate that the updating directions and distances of gradients for clients are diverse, which manifests the structure and feature heterogeneity in our setting again. In our vanilla GCFL framework, the server calculates a cosine similarity matrix based on the last transmitted gradients once the clustering criteria are satisfied. However, with the observation that the norm of gradients fluctuates along the communication round, albeit with the constraints of clustering criteria, GCFL clustering based on gradient-point could omit important client behaviors and be misled by noises. For example, in Figure 1 (a), GCFL performs clustering at round 119 based on the gradients at that round, which does not effectively find graphs with lower heterogeneity.

heading: 5.2 Technical design
text: Motivated by these observations, we propose an improved version of GCFL, named GCFL+, which conducts clustering by taking series of gradient norms into consideration. In the GCFL+ framework, the server maintains a multi-variant time-series matrix Q 2 R{n,d}, where n is the number of clients and d is the length of a gradient series being tracked. At each communication round t, the server updates Q by adding in the norm of gradients k ✓tik to Q(i, :) 2 Rd and remove the out-of-date one. GCFL+ uses the same clustering criteria as GCFL (Eqs. 4 and 5). If the clustering criteria are satisfied, the server will calculate a distance matrix in which each cell is the pair-wise distance of two series of gradients. Here, we use a technique called dynamic time warping (DTW) [31] to measure the similarity between two data sequences. For a cluster Ck, the server calculates its distance matrix as k(p, q) = dist(Q(p, :), Q(q, :)), p, q 2 idx({Si}), (8) where idx({Si}) is the indices of all clients {Si} in cluster Ck. With the distance matrix , the server can perform bi-partitioning for clusters who meet the clustering criteria. As a result, in Figure 1 (b), GCFL+ performs clustering at round 118 based on the gradient sequence of length 10, which captures the longer-range behaviors of clients and effectively more homogeneous clusters.

heading: 6 Experiments

heading: 6.1 Experimental settings
text: Datasets We use a total of 13 graph classification datasets [30] from three domains including seven molecule datasets (MUTAG, BZR, COX2, DHFR, PTC_MR, AIDS, NCI1), three protein datasets (ENZYMES, DD, PROTEINS), and three social network datasets (COLLAB, IMDB-BINARY, IMDBMULTI), each with a set of graphs. Node features are available in some datasets, and graph labels are either binary or multi-class. Details of the datasets are presented in Appendix C.
We design two settings that follow different data partitioning mechanisms, and the example real scenarios of the two settings can be found in Appendix A. The first setting (i.e., single-dataset) is to randomly distribute graphs from a single dataset to a number of clients, with each client holding a distinct set of about 100 graphs, among which 10% are held out for testing. In the second setting (i.e., multi-dataset), we use multiple datasets either from a single domain or multiple domains. Each client holds a graph dataset, among which 10% are held out for testing. In the first setting, we use NCI1, PROTEINS, and IMDB-BINARY from three domains and distribute them to 30, 10, 10 clients, respectively. In the second setting, we create three data groups including MOLECULES which consists of seven datasets from the molecule domain distributed into seven clients, BIOCHEM where we add three datasets from the protein domain into MOLECULES and distribute them into 10 clients, MIX where we add three datasets from the social domain into BIOCHEM and distribute them into 13 clients.
Baselines We use self-train2 as the first baseline to test whether FL can bring improvements to each client through collaborative training. In self-train, each client firstly downloads the same randomly initialized model from the server and then trains locally without any communications. Then we implement two widely used FL baselines FedAvg [27] and FedProx [25], the latter of which can deal with data and system heterogeneity in non-graph FL. For the graph classification model, we use the same GIN [43] design, which represents the state-of-the-art GNN for graph-level tasks. We fix the GIN architecture and hyper-parameters through all baselines in order to control the experiments across different settings.
Parameter settings We use the three-layer GINs with hidden size of 64. We use a batch size of 128, and an Adam [20] optimizer with learning rate 0.001 and weight decay 5e 4. The µ for FedProx is set to 0.01. For all FL methods, the local epoch E is set to 1. The two important hyper-parameters "1 and "2 as clustering criteria vary in different groups of data, which are set through offline training for about 50 rounds following [33]. We run all experiments for five random repetitions on a server with 8 24GB NVIDIA TITAN RTX GPUs.

heading: 6.2 Experimental results
text: Federated graph classification within single datasets Conceptually, clients in this setting are more homogeneous. As can be seen from the results in Table 3, our framework can obviously improve the performance of graph classification over local clients. For the NCI1 dataset distributed on 30 clients, GCFL and GCFL+ achieve 13.27% and 14.75% performance gains over self-train on average, and GCFL and GCFL+ help 10-14 more clients than FedAvg and FedProx who fail to improve about half of clients. For the PROTEINS dataset on the total 10 clients, GCFL and GCFL+ achieve 7.29% and 7.81% average performance gains compared to self-train. For IMDB-BINARY on 10 clients, FedAvg and FedProx fail to help 5/10 and 4/10 clients respectively, while both GCFL and GCFL+ are able to improve all 10 clients. Overall, FedAvg can only help around half of the clients, which demonstrates that FedAvg can be ineffective even for decenrtalized graphs from a single dataset, because of the graph non-IIDness as shown in Table 2. In addition, in all three datasets, the minimum performance gain of clients over self-train using GCFL or GCFL+ is obviously larger than the minimum performance gain using FedAvg and FedProx. It indicates that even when some clients do not improve from self-train by using GCFL or GCFL+, they can achieve more comparable performance as self-train than using FedAvg and FedProx. These experimental results demonstrate that our frameworks are effective on the single-dataset multi-client FL setting.
Federated graph classification across multiple datasets According to our data analysis in Tables 1 and 2, clients in such a setting are more heterogeneous. We conduct experiments with multiple datasets in two settings: single domain (using the data group MOLECULES), and across domains (using the data groups BIOCHEM and MIX). As can be seen from the results in Table 4, our frameworks GCFL and GCFL+ can effectively improve the performance of clients with distinct datasets. The results show 1.7% 2.7% improvements of our frameworks compared to self-train. In all three data groups, our GCFL+ framework can improve twice as many as clients than FedAvg, and it achieves a ratio of 100% in MOLECULES to improve all clients’ performance. The FedAvg failed to improve around 60% clients, which further demonstrates its ineffectiveness facing graph non-IIDness. Additionally, the GCFL+ framework also outperforms GCFL. In MIX, although GCFL can achieve the same ratio of improved clients as GCFL+, the GCFL+ framework has a much larger minimum gain of clients than GCFL. It indicates that by GCFL+ few clients that cannot benefit from others will not be degraded through the collaborating. These results indicate that graphs across datasets or even across domains are able to help each other through proper FL, which is a surprising and interesting start point for further study.
Effects of hyper-parameters "1 and "2 The hyper-parameter "1 is a stopping criterion for checking whether a general FL on the current set of clients is near the stationary point. Theoretically, "1 should be set as small as possible. The hyper-parameter "2 is more dependent on the number of clients and the heterogeneity among them. A smaller "2 will make the clients more likely to be clustered. When "1 and "2 are in the feasible ranges, their small variation can have little effect on the performance because the clustering results would largely remain the same. When "2 is set too large,
2We do not have a global model as baseline as datasets are from various domains and their tasks are divergent.
the performance will be similar as applying a basic FL algorithm directly (i.e. with a single cluster). When "2 is set too small, more clusters with smaller sizes or even single clients will be generated. We provide additional experimental results regarding the performance of GCFL and GCFL+ w.r.t. varying "1 and "2 in Figure 2. As shown in the subfigures, some points that represent varying "2 overlap for each "1, which indicates that varying "2 in a certain range w.r.t. the fixed "1 leads to similar performance. Looking at a "2, within a certain range of "1, we can find the performance often fluctuating within a 0.01 variance. The results show that the performance of GCFL and GCFL+ are not very sensitive to the changes of "1 and "2 in reasonable ranges.

heading: 6.3 Structure and feature analysis in clusters
text: We conduct an in-depth analysis to explore the clustering results of GCFL and GCFL+. As can be seen in Figure 3, after being clustered by GCFL and GCFL+, the overall structure and feature heterogeneity of clients’ graphs within clusters are reduced significantly compared to the original values, especially for the multiple dataset setting (Figure 3c and 3d). For the one dataset setting (Figure 3a and 3b), since features all fall in the same space, pairs of clients tend to have more homogeneous features. Therefore, the feature heterogeneity only gets reduced slightly after clustering. Unlike feature heterogeneity, the structure heterogeneity within clusters decreases significantly. In the setting of multiple datasets, as shown in Figure 3c and 3d, both structure and feature heterogeneity decrease significantly, which is intuitive since datasets across domains usually tend to have higher heterogeneity, as discussed in 4.1. We also look into the clusters and find that datasets from the same domains are more likely to be clustered together, while datasets from different domains also constantly get clustered together and benefit each other. For example, the clustering of GCFL+ corresponding to Figure 3d groups two social networks COLLAB and IMDB-BINARY together with PROTEINS and also several molecules datasets, and there is also a cluster of NCI1, DD, and IMDB-MULTI which are molecules, proteins and social networks, respectively. These analysis manifests that domains of datasets can verify the sanity of clusters to some extent, but one cannot solely rely on such prior knowledge to determine the optimal clusters, which demonstrates the necessity of our frameworks with the ability of performance-driven dynamic clustering along the process of FL.

heading: 6.4 Convergence analysis
text: We visualize the testing loss with respect to the communication round to show the convergence of GCFL and GCFL+ compared with the standard federated learning baselines. Figure 4 shows the training curves on two settings, which illustrates that GCFL and GCFL+ achieves similar convergence rate as FedProx, which is the state-of-the-art FL framework dealing with non-IID Euclidean data. We also notice that both GCFL, GCFL+ and FedProx can converge to a lower loss compared with FedAvg, which corroborates our consideration of the non-IID problem in our setting.

heading: 6.5 More results in Appendix
text: In Table 3 and 4, we averaged the accuracy across all clients for presentation simplicity. To understand the detailed performance by clients and clusters, we present different Violin plots in Appendix D. Besides, we also show more results regarding various settings (overlapping clients, real vs. synthetic node features, standardized gradient-sequence matrix in GCFL+, etc) in Appendix D.

heading: 7 Conclusion
text: In this work, we propose a novel setting of cross-dataset and cross-domain federated graph classification. The techniques (GCFL and GCFL+) we develop allow multiple data owners holding structure and feature non-IID graphs to collaboratively train powerful graph classification neural networks without the need of direct data sharing. As the first trial, we focus on the effectiveness of FL in this setting and have not carefully studied other issues such as data privacy, although it is intuitive to preserve the privacy of clients by introducing an encryption mechanism (e.g. applying orthonormal transformations), and to prevent from adversarial scenarios by clustering out the malicious clients. Due to its evident motivations and proofs on the effective FL in a new setting, we believe this work can serve as a stepping stone for many interesting future studies.
Acknowledgments and Disclosure of Funding
The work is partially supported by National Science Foundation (NSF) under CNS-2124104, CNS2125530, CNS-1952192, and IIS-1838200, National Institute of Health (NIH) under R01GM118609 and UL1TR002378, and the internal funding and GPU servers provided by the Computer Science Department of Emory University.

Review summaries:
This paper advocates a novel setting of cross-dataset and cross-domain federated learning for graph classification, which allows multiple data owners with graphs of non-iid structures and features to collaboratively train powerful graph classifiers without direct data sharing. The proposed techniques are neat yet well-justified. Extensive experiment results show clear performance gains of the proposed GCFL+ over vanilla baselines like FedAvg across different settings. Convergence analyses are also provided.

This paper provides a timely study on the emerging domain of graph federated learning, focusing on the graph classification setting. This is a natural setting close to federated learning over other types of data in terms of data split, yet the authors manage to motivate the need of doing so based on real network data analysis, and figure out the unique challenges of graphs regarding the non-iid nature of both structures and features. This provides a good motivation to the usage of GNNs, which is supported by some theoretical analysis. The existing technique of clustered FL is adopted to the GNNs and slightly improved for better performance. 

The paper proposes a federated graph classification system based on clustered federated learning to solve the non-iid problem in graph structure and node features across clients. The paper also proposes to use dynamic time warping to improve clustering performance. The authors evaluate their system on a couple of different scenarios: (i) a single graph dataset split across multiple clients and (ii) Graph datasets from different domains on each client.