  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.
