Federated Graph Classification over Non-IID Graphs
Authors: Han Xie
Jing Ma
Li Xiong
Carl Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: federated learning
graph classification
non-iid graphs
structure heterogeneity
feature heterogeneity

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.

Federated Graph Classification over Non-IID Graphs
Han Xie, Jing Ma, Li Xiong, Carl Yang"
Department of Computer Science, Emory University {han. xiee jing ma, lxiong, y.callyag))emmory... edu
Abstract
Federated learning has emerged an important paradigm for training machine learning models in different domains. For graph-level tasks such as graph classifi- cation, graphs can also be regarded collected and stored in separate local systems. Similar to other domains, multiple local systems, each holding small set of graphs, may benefit from collaboratively training a powerful graph mining model, such as the popular graph neural net- works (GNNs). To provide more motivation towards such endeavors, real-world graphs from different domains to confirm that they indeed share certain graph properties that statistically significant compared with random graphs. However, we also find that different sets of graphs, even from the same domain or dataset, non-IID regarding both graph structures and node features. To handle this, we propose graph clustered federated learning (GCFL) framework that dynamically finds clusters of local systems based 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.
special type of data samples, which can be
analyze
Introduction
Federated learning (FL) as distributed learning paradigm that trains centralized models on decentral- ized data has attracted much attention recently [28] 533 25 T8 [7]. FL allows local systems to benefit from each other while keeping their own data private. Especially. for local systems with scarce train- ing data or lack of diverse distributions, FL provides them with the potentiality 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 personalized FL.
optimization process 25 18
clustered FL
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 graph kernels 44
45 and graph neural networks 4x 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.
36
21 [ 49
46
47
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Since the key idea of FL is the sharing of underlying common information, as 2 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 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 II we analyze four typical datasets from different domains, i.c., PTC_ MR (molecular structures), ENZYMES (protein structures), (social communities), and MSRC_ 29R (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 Erdōs-Rény model ?
[CC ). 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
Table 1: Data analysis on important graph properties shared among real-world graphs across different domains. For example, large Kurtosis values [2) indicate long-tail distribution of node degrees, which is observed in ENZYMES, AMDB-BINARY, and MSRC_ 21; similar average shortest path lengths are observed in PTC_MPP ENZYMES, and MSRC_ 21, although their actual graph sizes are rather different; large CC are observed in ENZYMES, IMDB-BINARY, and MSRC_ 21 and large LC are observed in almost all graphs.
Property
kurtosis of degres distribution
avg.
shortest path longth
largest composeent (LC, %)
clustering coefficient (CC)
real random
p-valac
real
random
p-valae
real
random
p-value
real
random
p-valuc
PIC. MR (molecules)
2,1535
2.4424
0,9999
3,36
2.42
~D
100
82.68
~00
0:0095
0.1201
0
ENZYMES (proicins)
3.0106
28224
0.0027
4.44
98.24
97.69
0.2054
0.4516
0.1425
IMDE-BINARY (social)
8.9362
2.2791
1,48
1.54
100
99.93
0.0023
0.9471
D.5187
0
AIRR__1 (superpize))
3.6959
2.9714
0
4.09
2.81
~
100
99.13
~
0.5147
0.0655
0
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 feature heterogeneity measure in different scenarios (c.f. Section 4.T). We refer to the graphs possibly with significant heterogeneity in our cross-dataset FL setting as non-IlI graphs, which concerns both structure non-IID and feature non-IID, where naive FL algorithms like FedAvg [28] can fail and even backfire (c.f. Section 6.2). Morcover, the heterogeneity varies from case to case, 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 4% 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 (..1.on............ which could be caused by the complicated interactions among clients regarding both structure and feature hetero- geneity, making the local gradients towards divergent directions. In the vanilla GCFL framework, the server calculates matrix for clustering only based on the last transmitted gradients, which ignores the client's 'ss multi-round behaviors. Therefore, we further propose an improved version of GCFL with gradient-series- serettt-eeiee--bb-eeee 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 pooss-dataset/eeoos-doooe FL for graph classification, where our GCFL+ framework can effectively and consistently outperform other straightforward baselines.
2

---

2 Related works
Federated Learning Federated learning (FL.) has gained increasing attention as 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 be an unbiased estimation of the full gradients, thus hurting the convergence of FL. In fact, multiple experiments [53] 25 [8] have shown that the convergence will be slow and unstable, and the accuracy will degrade with FedAvg proposed different data sharing strategies to tackle the data heterogeneity problem by sharing the local device data or server- side proxy data, which still requires certain public common data, whereas other studies explored
when data at each client are statistically heterogeneous (non-lID). [33 15 12
the convergence guarantee under the non-Ill 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 E. 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 1 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 graph. x studied the cross-domain heterogeneity problem in FL. by leveraging Graph Convolutional Networks (GCNs) to model the interaction between domains.
22 studied spatio-temporal data modeling in the FL setting by leveraging 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:
154 40 focused the privacy issue of federated GNNs; B7 incorporated model-agnostic meta- learning (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; 33 proposed computationally efficient way of GCN architecture search with FL; I 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.
[6
3
Preliminaries
3.1 Graph Neural Networks (GNNs)
42 provides a taxonomy that categorizes Graph Neural Networks (GNNs) into recurrent GNNs, convolutional GNNs, graph autoencoders, and 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 h2 E R. or a graph embedding hGg E da 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
GNNs. In general, given the structure
((+1) obb)) agg (( E NoJ)), VI [4],
(1)
where 1 is the representation of node at the 1th layer, and 1 (0) = is the node feature. N,, is neighbors of node v. agg(-) is an aggregation function that can vary for different GNN variants, and represents an activation function.
For graph-level representation hG, it can be pooled from the representations of all nodes, as
hg readout (hoj V}),
(2)
3

---

where readout(.) can be implemented as mean pooling, sum pooling, etc, which essentially aggregates the embeddings of all nodes on the graph into single embedding vector to achieve tasks like graph classification and regression.
3.2 The FedAvg algorithm
McMahan al. 2S 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 each client. Specifically, given clients in total, at each communication round f, the server first samples a partition of clients (8)) For each client S in { it trains the model downloaded from the server locally with its own data distribution Dj for Elocal epochs. The client S, then transmits its updated parameters w(()) to the server, and the server will aggregate these updates by
(4) Di w
(1+11)
(3)
where |D; is the size of data samples in client S; 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((++1) remote clients, and the (t. + 1) round clients use (t-(1) start their local training for another Frocal epochs.
The GCFL framework
4.1 Non-IID structures and features across clients
From Table 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 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) |E to generate representation for each graph, and compute the Jensen-Shannon distance between the AWES of each pair of graphs; for feature heterogeneity, pairs of linked nodes in each graph, and compute the Jensen-Shannon divergence between the feature similarity distributions of each pair of graphs.
calculate the empirical distribution of feature similarity between all
As we can observe in Table 2 both graph structures and features demonstrate different levels of heterogeneity within single dataset, single domain, and across different domains. We refer to graphs with such structure and feature heterogeneity as non-lll) graphs. Intuitively, directly applying naïve FL algorithms like FedAvg on clients with non-lllD graphs 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?
4.2 Problem formulation
Motivated by our real graph data analysis in Tables I and we propose 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 KK and consider a clustered FI. setting with one central server and set of local clients (S,, , S.). Different from the traditional FL setting, the server can dynamically cluster the

---

Table 2: Summary of the average heterogeneity of features and structures for some datasets. In general, the structure heterogeneity increases from the settings of one dataset to across-dataset, and to across-domain, However, the feature heterogeneity is more case-by-case, and the high variances indicate that graphs could have large feature divergence even within the same dataset. Additionally, it not necessarily true that one dataset itself should be more homogeneous (e.g., AMDB-BINARE
cox2 (molecules)
COX2 (molccules)
COX2 (melecules)
dataset
IMDE-BINARY (social)
cox2 (molecules)
FIC_MR (molccules)
ENZYMES (proteins)
IMDU-HINAKY (social)
ayg. struc. hetero.
0.4406 (1000397))
0.3246 (=00445))
0.3689 (110.0540)
0,5082 (1000399)
0.6079 (=0.0331)
avg. feat. hetero.
0.1785 (#0. 1226)
0.0427 (=003114)
0.1837 (=0.)065)
0,1912 1000))00)
0.1642 (=0.)
clients into set of clusters (C1, C2....) . and maintain m cluster- wise models. In our GCFL setting, each local client S; owns a set of graphs G; = {G1, G2,... .J. where each G3 = (V,, X, U2) E 9; is graph data sample with a set of nodes Vj. set of edges Ej, node features j,, and a graph class label V/- The task on each local client & is graph classification that predicts the class label "y hi (G₃) for each graph Gj E Gs, where hj is the collaboratively learned optimal graph mining model for cluster Cg to which S belongs. Our goal is to minimize the loss function F(O+)= == ec, [[(0, Gi)]. for all clusters (Cx). The function (0RR, e 9,) is local loss function for client S which belongs to cluster Cs. In the meantime, we also aim to maintain a dynamic cluster assignment IS,)) + [C*} based on the FL process.
4.3 Technical design
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 ( [A0:)== in order to maximize the collaboration among more homogeneous clients and eliminate the harm from heterogeneous clients. According to [3) 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 the stationary point. Here, we first introduce dyyer--arameed E as criterion to decide whether to stop the general FL based on whether a stationary point is approached, that is,
99 g
Smean = ||
Σ TE[m]
A0
< E1
(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 82 to split the clusters when
8maz m| 82 > O.
(5)
The GCFL framework follows top-down bi- birpartiti mechanism. At each communication round t, the server receives m sets of gradients ( [A6,,) 1. (A.t.)..... {Ae,,.. }} from clients in clusters (C1, C2,..., C..)- For cluster Ct., if 6k 6 and 6%: 6mea satisfy the Eqs. 4 and the server will calculate a cluster- cosine similarity matrix og2, 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 355 is then applied to the constructed graph, which bi bi-partitions the graph and divides the cluster Cj + {CA1. ]. The clustering mechanism based on Eqs. 1 aadd 5 cann automatically and dynamically determine the number of clusters along the FL, while the two cypee-parrmeters E and E2 can be easily set through some simple experiments on the validation sets following (3)
For client 34 in cluster C₁, it tries to find i..: that is close the real solution 0% arg ming,e02 (Bp, 9:). At a communication round t, the client S transmits its gradient to the server
A0l. -hh 0
(6)
5

---

Since the server maintains the cluster assignments, it can aggregate the gradients cluster-wise by
0 = 0 +
A0k
xE(mk]
4.4 Theoretical analysis
We investigate the problem of graph FL with multi-domain data distribution, and use the gradient- based FL paradigm [27] to facilitate the model training. We theoretically analyze that the gradient- based FL algorithm clusters, along with the task difference between data from different domains. We study two general problems in order prove that the gradients can reflect the feature, structure, and task information.
GNNs
in principle reduce the structure and feature heterogeneity in
Definition 4.1 Let function f : X - y which maps from the metric space (X. d) to (V.d".. the function f considered have 8 distortion if Vu, X. jd(uu, v) S d' (f(().((v)) S d(u,v) v).
(Bourgain theorem () Given n-point metric space (X,d) and embedding function f as defined above, Vu, E X, there exist an embedding mapped from (X, d) to R with the distortion of the embedding being (loggn).
Theorem 4.1
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, solve Problem with the GNN of Simple Graph Convolutions (SGC) the following two propositions.
41 through
Proposition 4.1 Given graph G with fixed structure represented by the normalized graph Laplacian C= DD 2, feature represented with X, and an SGC f(C softmax [L X with weights θ trained graph G. If we have another graph G' with different structure L', the weight difference ||0' - -0122 is bounded with the structure difference.
Proposition 4.2 Given graph G with fixed structure represented by the normalized graph Laplacian C= AĐ-3, 2, feature represented with X, and SGC J[C, X) softmar L X with weights θ trained on graph G. If we have another graph G' with different feature X', the weight difference | 0 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 struetures/feattres, 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 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, also study the following problem, which allows our GCFL framework to be further extended to cross-task task graph-level federated learning in the future.
Problem 2. The communicated gradients in GCFL can also capture the task heterogeneily.
Proposition 4.3 Given a graph G with structure represented by the normalized graph Laplacian f - AD-1, 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 found in Appendix B
GCFL+: improved GCFL based on observation sequences of gradients
5.1 Fluctuation of gradient norms
When observing the norm of gradients for each communication round in GCFL,, as shown Figure U notice that: I) the norm of gradients continuously fluctuates; 2) different clients can have divergent

---

Norm of Gradients
INBBAUUTII
Norm of Gradients
INDBAUUTII
10
10
BZR
BZR
COX2
COX2
ADS
5
ADS
PROTEING
PROTENS
115
120
115
120
Communication Round GCFL
Communication Round (b) GCFL+
Figure 1: Norm of gradients versus communication round with six clients across datasets. Clients with datasets colored the same are split to the same cluster.
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 setting again. In vanilla GCFL framework, the server calculates 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-poin could omit important client behaviors and be misled by noises. For example, in Figure (a), GCFL performs clustering at round 119 based on the gradients at that round, which does not elfectively find graphs with lower heterogeneity.
5.2 Technical design
Motivated by these observations, propose improved version of GCFL, named GCFL+, which conducts clustering by taking series of gradient norms into consideration. the GCFL+ framework, the server maintains multi-variant time-series matrix Q E (R(,,)), where n the number of clients and d is the length of a gradient series being tracked. At each communication round I, the server updates Q by adding in the norm of gradients || to Q :) E Ted and remove the out-of-date one. GCFL+ uses the same clustering criteria GCFL (Eqs. and 5). If the clustering criteria satisfied, the server will calculate a distance matrix 3 in which each cell is the pair-wise distance of two series of gradients. Here, we use technique called dynamic time warping (DTW) 3| to measure the similarity between two data sequences. For a cluster Cx, the server calculates its distance matrix as
Ba(p, g) = dist :), (la.))). p,g idx(():)),
where (s.)( is the indices of all clients (S:} in cluster Ce. With the distance matrix B, the server can perform bi-partitioning for clusters who meet the clustering criteria. As a result, in Figure (b). GCFL+ performs clustering round 1 118 based the gradient sequence of length 10, which captures the longer-range behaviors of clients and effectively more homogeneous clusters.
6 Experiments
6.1 Experimental settings
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, NCT1), three protein datasets (ENZYMES, DD, PROTEINS), and three social network datasets (COLLAB, AMDB-BINARY. IMDB- MULTI), each with 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.c., singie-dataset) is to randomly distribute graphs from a single dataset to number of clients, with each client holding distinct set of about 100 graphs, among which 10% are held out for testing. 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-BINARE from three domains and distribute them to 30, 10. 10 clients, respectively. 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 MOLECULEES and distribute them into 10 clients, MIX where we add three datasets from the social domain into BIOCHEM and distribute them into 13 clients.
7

---

Baselines We use self- 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 FI. 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 [3 design, which represents the state-of-the-art GNN for graph-level tasks. We fix the GIN architecture and hlyerr-prameee 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 batch size of 1 128, and an Adam [20] optimizer with learning rate 0.001 and weight decay 5e The ja for FedProx is set to 0.01, For all FL methods, the local epoch E is set to The two important hyper-parameeters E and 22 as clustering criteria vary in different groups of data, which are set through offline training for about 50 rounds following [3] We run all experiments for five random repetitions on server with 8 24GB NVIDIA TITAN RTX GPUs.
6.2 Experimental results
Federated graph classification within single datasets Conceptually, clients in this setting are more homogeneous. As can be seen from the results in Table []] 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 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 the total 10 clients, GCFL and GCFL+ achieve 7.29% and 7.81% average performance gains compared to self welf-tzee trriin. 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 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 GCFL+, they can achieve more comparable performance as self-traid 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 Mand 2 clients 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 D 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 -rain. In all three data groups, our GCFL+ framework can improve twice many 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-IIDDess. 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 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 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 E and E2 The hyper- paeeer-rramterr E is a stopping criterion for check- ing whether a general FL on the current set of clients is near the stationary point. Theoretically, Eι 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 52 will make the clients more likely to be clustered. When 1 and Eq 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 E2 is set too large,
We do not have global model as baseline as datasets from various domains and their tasks are divergent.
8

---

Table 3: Performance on the single-daraset-mulliiiieenn setting. We present the average accuracy and
minimum gain over self-train on all clients, well as the ratio of clients which get improved.
Dataset (# chents)
NCHI (30)
PROTEINS (10)
IMDB BINARY (10)
Accuracy
average
min gain
ralio
average
min gain
ralio
average
min gain
rabio
self -triin
0.6568(200053)
0.7213(40.0088
0.765+K:0.055)
FedAvg
0.647((20.076)
-0.1333
14/30
0.7490:+0.024)
-0.0615
6/10
0.7596(20.044
-0,0800
5/10
FedProx
(.6037)=000722)
-0.2400
16/30
0.7556(40.036)
-0.0923
7/10
0.7746(+0.0488
-0.0600
6/10
GCFL. GCFL+
0.7326((00.052)
-0.0462
26/30
0.7739(+0.043)
-0.0545
0.8256(+0.059)
0.0182
0.7022(=0.053)
-0.1143
28/30
0.7776(H0.037)
-0.0154
9/10
0.829%(=0.052)
0.0167
10/10
Table 4: Performance on the mult--datast-multtccienn setting. Metrics are the same as Table
Dataset (f domains)
MOLECULES (1)
BIOCHEM
MIX
Accuracy
avcrage
min gain
ratio
average
min gain
ratio
average
min gain
ratio
8elf telf-tzain
0.7543(+0.017)
0.7129(=00016)
0.7001(20.054)
FedAvg
0.7524(+0.026)
-0.0132
3/7
0.6944(=0.027)
-0.1467
4/10
0.6886(+0.023)
-0.1233
5/13
FedProx
0.7668(10.088
0.0054
5/7
0.7053(
0.1000
5/10
0.6897(
00.1677
5/13
GCFL
0.7.61(100016)
0.0010
0.7072(10.019)
0.0700
7/10
1.7059(100011)
0.1400
GCFL+
0.7745(+00.20)
0,0010
7/7
0.7312(=00051)
-0.0300
8/10
0.7121(200021)
+0,0233
10/13
the performance will be similar as applying a basic FL algorithm directly (i.e. with single cluster). When 22 is set too small, more clusters with smaller sizes even single clients will be generated. We provide additional experimental results regarding the performance of GCFL and GCFL+ w.r.t. varying E and E2 in Figure As shown in the subfigures, some points that represent varying #2 overlap for each 1 which indicates that varying E2 in certain range w.r.t. the fixed ε leads to similar performance. Looking a E2. within certain range of E1, 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 E1 and Sq in reasonable ranges.
6.3 Structure and feature analysis in clusters
We conduct an in-depth analysis explore the clustering results of GCFL and GCFL+ As be in Figure 3] after being clustered by GCFL and GCFL+, the overall structure and feature heterogeneity of clients' graphs within clusters reduced significantly compared to the original values, especially
for the multiple dataset setting (Figure and 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 3e and 3d both structure and feature heterogeneity decrease significantly, which intuitive since datasets across domains usually tend to have higher heterogeneityy as discussed in 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 NCII, 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-dee dynamic clustering along the process of FL.
62
0.78
62
0.2
0,2
Accuracy
0.77
0.25
0.3
0.3
0.76
0.35
0.4
0.76
0.45
0.45
0.5
0.75
0.74
0.05
0.06
0.07
0.08
0.09
0.10
0.05
0.06
0.07
0.08
0.09
0.10
(a)
GCFL
(b) GCFL+
Figure 2: Performance of GCFL and GCFL+ on MOLECULES w.r. varying E and 82.

---

heterogensily
0.4
GCFL+ heleergehhell
0.4
GCFL heterogeneil
0.4
GCFL+ helerogenelly
0.4
GCFL
0.2
0.2
0.2
4
cluster
cluster
cluster
cluster
(a) oneDS: PROTEINS
(b) oneDS: PROTEINS
(c) multiDS: MIX
(d) multiDS: MIX
Figure 3: Structure (blue) and feature (red) heterogeneity within clusters found by GCFL and GCFL+
Dashed lines denote the heterogeneity over all clients before clustering.
1.4
1.4
Teclag
fecdag
GCEL
88 1.0
3.0
1.0
0.6
0.6
0.6
0.4
0.4
20
40
60
20
40
60
100
Communication Round
Communication Round
Communication
(a) oneDS: PROTEINS
(b) multiDS: MOLECULES
(c) multiDS: MIX
Figure 4: Average with standard deviation of the training curves of all clients.
6.4 Convergence analysis
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 shows the training curves on two settings, which illustrates that GCFL and GCFL+ achieves similar convergence rate 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.
6.5 More results in Appendix
In Table 4 averaged the accuracy all clients for presentation simplicity. To understand the detailed performance by clients and clusters, we present different Violin plots in Appendix [
Besides, also show more results regarding various settings (overlapping clients, real vs. synthetic node features, standardized gradient-sequence matrix in GCFL+, etc) in Appendix D
7 Conclusion
In this work, we propose novel setting of cross-dataset and cross-domain federated graph classifica- tion. The techniques (GCFL and GCFL+) we develop allow multiple data owners holding structure and feature non-IID graphs 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 data privacy. although it is intuitive to preserve the privacy clients by introducing an encryption mechanism (c.g. applying orthonormal transformations), and prevent from adversarial scenarios by clustering Due to its evident motivations and proofs on the effective FL in a new setting, we believe this work serve stepping stone for many interesting future studies.
the malicious clients.
Acknowledgments and Disclosure of Funding
The work partially supported by National Science Foundation (NSF) under CNS-2124104, CNS- 2125530, CNS- 1952199, and IIS-1838200 National Institute of Health (NIH) under R0I GM1 18609 and UIITRR003378 and the internal funding and GPU servers provided by the Computer Science Department of Emory University.
10

---

References
[1] Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52 (1):46-52, 1985.
[2] Christopher Briggs, Zhong Fan, and Peter Andras. Federated learning with hierarchical cluster- ing of local updates to improve training non-iid data. In IJNN, 2020.
[3] Debora Caldarola, Massimiliano Mancini, Fabio Galasso, Marco Ciccone, Emanuele Rodolà, and Barbara Caputo. Cluster-driven graph federated learning over multiple domains. CVPRW,
2021.
[4] Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. Federated meta-learning with fast convergence and efficient communication. arXiv preprini arXiv: Ie02.08877 2018.
[5] Mingyang Chen, Wen Zhang, Zonggang Yuan, Yantao Jia, and Huajun Chen. Fede: Embedding knowledge graphs in federated setting. arXiv preprint arXiv:2010. 12882, 2020.
[6] Canh T. Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In NeurIPS, 2021.
[7] Paul Erdös and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae, 6:290-297, 1959.
[8] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. In NeurIPS, 2020.
[9] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In NeurlPS, 2020.
[10] Edgar Gilbert. Random graphs. Annals of Mathematical Statistics., 30 (4):1141-1144, 1959.
[11] Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, Peilin Zhao, Junzhou Huang, Murali Annavaram, and Salman Avestimehr. Fedgraphnn: A federated learning system and benchmark for graph neural networks. arXiv preprini arXiv:2104.00 104.01400. 2021.
[12] Li Huang, Yifeng Yin, Zeng Fu, Shifa Zhang, Hao Deng, and Dianbo Liu. Loadaboost: Loss- based adaboost federated machine learning on medical data. PLoS ONE, 15(4)002230706 2020.
[13] Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang. Jiangehuan Liu, Jian Pei, and Yong Zhang. Personalized cross-silo silo federated learning on non-iid data. In AAAI, 2021.
[14] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In ICML, 2018.
[15] Eunjeong Jeong, Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong- Kim. Communication-effiiieee on-device machine learning: Federated distillation and augmen- tation under non-iid iid private data. In NIPSW, 2018.
[16] Meng Jiang, Taeho Jung, Ryan Karl, and Tong Zhao. Federated dynamic gnn with secure aggregation. arXiv preprint 2XXx:20009.03551. 2020.
[17] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and Trendy in Machine Learning, 14 (1), 2019.
[18] Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In ICML., 2019.
[19] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In AISTATS, 2020.
[20] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR. 2017.
[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[22] Anusha Lalitha, Osman Cihan Kiline, Tara Javidi, and Farinaz Koushanfar. Peer-to-peer federated learning on graphs. arXiv preprint arXiv:1901.11173, 2019.
11

---

[23] Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In ECML-PKDD, 2005.
[24] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. ICML,, 2021.
[25] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in hetcrogeneous networks. In Proceedings of Machine Learning and Systems, 2020.
[26] Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Vari- ance reduced local sgd with lower communication complexity. arXiv preprint 1rXiv:/912.12844. 2019.
[27] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- effficiiet learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, 2017.
[28] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. coamuuicaation-effcieee learning of deep networks from decentralized data. In AISTATS, 2017.
[29] Chuizheng Meng, Sirisha Rambhatla, and Yan Liu. Cross-node federated graph neural network for spatio-temporal data modeling. KDD, 2021.
[30] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICMLW, 2020.
[31] Niels Lundtorp Olsen, Bo Markussen, and Lars Lau Rakêt. Simultancous inference for mis- aligned multivariate functional data. Journal of the Royal Statistical Society Series C, 67 15):1147-1176, 2017.
[32] Karl Pearson. Das fchlergesetz und seine verallgemeinerunngen durch fechner und pearson. rejoinder [the error law and its generalizations by fechner and pearson. a rejoinder]. Biometrika, 4 (1-2):169-212, 1905.
[33] Felix Sattler, Klaus-Robert Müller, and Wojeiech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. TNNLS, pages 1-13, 2020.
[34] Nino Shervashidze and Karsten M. Borgwardt. Fast subtree kernels on graphs. In NIPS, 2009.
[35] Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4), 1997.
[36] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. JMLR, 11:1201-1242, 2010.
[37] Binghui Wang, Ang Li, Hai Li, and Yiran Chen. Graphfl: A federated learning framework for sumi-super node classification graphs. arXiv preprint arXi::2012.04187 2020.
[38] Chunnan Wang, Bozhou Chen, Geng Li, and Hongzhi Wang. Fl-agens: Federated learning framework for automatic graph convolutional network search. In ICML, 2021.
[39] Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, (7(6): 2012200522211 2019.
[40] Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for 2021.
recommendation. arXiv preprint 1422002.....4255..
[41] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[42] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE TNNLS, 32(1):4-24, 2021.
[43] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[44] Pinar Yanardag and V.N.N. Vishwanathan. Deep graph kernels. In KDD, 2015.
12

---

[45] Carl Yang, Mengxiong Liu, Vincent W Zheng, and Jiawei Han. Node, motif and subgraph: Leveraging network functional blocks through structural convolution. In ASONAM, 2018.
[46] Carl Yang. Yuxin Xiao, Yu Zhang. Yizhou Sun, and Jiawei Han. Heterogeneous network representation learning: A unified framework with survey and benchmark. In TKDE, 2020.
[47] Carl Yang. Jieyu Zhang, and Jiawei Han. Co-embedding network nodes and hierarchical labels with taxonomy based generative adversarial nets. In ICDM, 2020.
[48] Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In NIPS, 2019.
[49] Rex Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, 2018.
[50] Jiaxuan You. Rex Ying. and Jure Leskovee. Position-awan graph neural networks. In ICML, pages 7134-7143, 2019.
[51] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI, 2019.
[52] Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. In NewrIPS, 2021.
[53] Yue Zhao, Meng Li. Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806.0053: 2018.
[54] Jun Zhou, Chaochao Chen, Longfei Zheng, Huiwen Wu, Jia Wu, Xiaolin Zheng, Bingzhe Wu, Ziqi Liu, and Li Wang. Vertically federated graph neural network for privacy-preservie node classification. arXiv preprint arXiv:2005. 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Mainly see Sections 4-6
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [N/A] See
Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4.4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.? [Yes] See Section 6.1 and the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6.1
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] For example see Tables 3 and 4
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6.1
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Wherever we mention them for the first time
(b) Did you mention the license of the assets? [N/A] They are public
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We include our models and code in the supplemental material
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zbL4mRXhJBH", "reviewer": "Reviewer_RhpX", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Some minor concerns are as follows:\n\nQ1: It looks like the objective of GCFL is closer to personalized federated learning instead of standard federated learning. Can the authors clarify on this?\n\nQ2: Although simplicity is good, the overall technical novelty is somewhat limited. For example, how is the proposed framework different from recent works such as FedCG (Cluster-driven Graph Federated Learning over Multiple Domains), in CVPR’21 workshop?\n\nQ3: The columns in tables 3&4 can use more explanations, such as the min gain and ratio columns. As they appear now, it requires more thinking to exactly appreciate how they show the advantages of the proposed methods.\n\nQ4: How do hyper-parameters like \\epsilon_1 and \\epsilon_2 influence the performance of the framework?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "JLFcczs0JVY", "reviewer": "Reviewer_eL7Z", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper does not try to sell a bunch of fancy or complicated architectures. Instead, it tells a real scientific story, where every major step including the problem setting, usage of GNN, utilization of clustered FL (and the small improvement) are well motivated and justified through real data analysis and observations. This has been taken for granted in recent works especially related to graph federated learning. In terms of weaknesses, I find certain low-level technical details to be confusing, such as why agglomerative clustering is used for splitting the clusters? Is it following the design of existing clustered FL ?  Is it really ideal?\n\nOverall, this paper is well-organized and easy to follow. It provides enough information even for non-expert readers.\n\nThis paper properly justifies the need of graph classification with federated learning and demonstrates its benefit in different settings (one-dataset, cross-dataset, cross-domain). An easy-to-implement framework composed of GNN and clustered FL is proposed and shown to be effective. Though there exist some issues such as model efficiency, privacy, etc. that should be further studied, this work can serve as a good starting point for research on graph federated learning.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "A_AegsimizI", "reviewer": "Reviewer_S61D", "summary": "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. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Summary \n\nThe 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. \n\nPros\n\nThe authors recognize an important problem in the non-iidness that occurs in graph datasets within the same domain and naturally across domains. The paper is mostly well written and easy to follow, although a few sections could benefit from clear phrasing. \n\nCons\n\nThe main concern with the paper are a lack of technical novelty, an unconvincing motivation, and inadequate experimental evaluation. Detailed comments are given below.\n\n\nDetailed comments:\nIt's unclear what the comparison of random graphs to real world graphs is meant to illustrate beyond the fact that real world graphs illustrate certain common properties across domains. This is a fairly well understood phenomenon and it seemed there was not much insight with this data in the introduction.\n \nThe motivation for clustering is entirely dependent on a robust metric of homogeneity. On the one hand, statistical structural properties (as shown in Table 1) might be similar between graphs on different clients. But how much do these statistical properties matter? What is the correlation between the expressivity of a GNN trained on different graphs and the statistical similarity between those graphs? \n\n\nGCFL\n\"From Table 1 we notice that real-world graphs tend to share certain general properties across different graphs, datasets and even domains..\". This is probably a bit strong claim to be made from the Table 1. The information presented in Table 1 is inadequate to make this claim. At the very least more datasets need to be investigated.  Table 1 in itself doesn't seem like a strong enough motivation for clustering. \n\n Graph Clustered Federated Learning needs to be motivated with a real world use case that satisfies these properties. Where do real world scenarios with different clients containing heterogeneous features in their graphs / nodes show up? Why would an IMDB-BINARY type dataset ever be split between clients that cannot share data with each other? Or when would a client working on molecular data ever collaborate with a social media company working on social networks? Recent work https://arxiv.org/abs/2104.07145 motivated federated graph learning in the context of molecular graphs, but the features that are used in such a setting are often atom properties which would be fairly homogenous between graphs and clients. So the motivation needs to be better.\n\nThe technical novelty is limited. Section 4.3 seems more like an application of CFL than a novel approach to clustered federated learning. Moreover, the approach seems general and doesn't seem specific to exploiting any GNN related specifics. \n\nGCFL+\nObservations on gradient norm and why GCFL cannot adjust itself makes sense, still a general phenomenon in FL.\nUsing DTW is simple and neat, but experimentally, improvement seems not significant. Have you ever tried different window lengths ? \n\nExperiments\nIn the single dataset to number of clients setting, how is the dataset partitioned in a non-iid fashion between clients? \n\nThe baselines are not strong enough. What is the motivation for the self-train baseline? \n\nHow does GCFL compare to just CFL being applied?\n\nThe claim that GCFL can help clients that are training on disparate graphs (different domains) collaborate needs to be better justified. Maybe I misunderstood, but it seems that  the authors are suggesting that the semantic information in the graphs on each client is  irrelevant? I am not sure if a client training on social network data can collaborate with a client training on some other  GCN models. Hence, collaboration across domains may not be that trivial, in my view. The experimentsalsection needs to be reinforced with  more combinations of datasets from different domains to convince readers  that such a non-intuitive result holds true in practice. \n\nProofs\nWhy is the model used for analysis SGC but the model used in experiments GIN? I understand that it is for the sake of simplicity, but the models are quite different. Do the proofs hold up if the model being analyzed was GIN? Some intuition on this, even if not a full proof would definitely clear things up. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No comments here to adress.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was a fruitful discussion about this paper.
Overall, I feel that the paper contains enough interesting and novel ideas for a publication. 
Decision: Accept (Poster)