FedCCH: Automatic Personalized Graph Federated Learning for Inter-Client and Intra-Client Heterogeneity

1 Introduction

Federated Learning (FL) enables distributed machine learning while addressing privacy and security concerns by keeping data locally. [McMahan et al., 2017]. However, in FL, clients often exhibit diverse data distributions, thereby contravening the standard assumption of independent and identically distributed (i.i.d) data prevalent in centralized machine learning. This phenomenon, referred to as data heterogeneity, is recognized as a significant factor contributing to the performance degradation of the global model. Therefore, those non-i.i.d phenomenon drive the development of personalized federated learning (PFL) [Tan et al., 2022], which learns customer-specific personalized models with a global model as an integral part of knowledge sharing [Tan et al., 2022; Gauthier et al., 2023]. PFL satisfies the personalized requirements by delivering tailored model parameters to unique model architectures of diverse devices(same as clients in FL), which is called model customization. Model customization becomes imperative for individual devices or users, particularly for cooperative training in cross-client scenarios such as speech recognition [Sim et al., 2019], anomaly detection [Haotian et al., 2022], and image segmentation [Jiang et al., 2022] among different clients. Recently, GFL has emerged as a dominant approach to address the limitation of Graph Neural Networks (GNNs) [Kipf and Welling, 2017; Velickovic et al., 2017; Xu et al., 2018] when facing scattered graph data in the real world with privacy concerns [Fu et al., 2022]. Existing GFL methods are categorized into three types, differentiated by the graph data each client holds. (1) Node-level separation [Chen et al., 2022; Pan et al., 2023] (2) Subgraph-level separation [Zhang et al., 2021; Chen et al., 2021] and (3) Graph-level separation [Tan et al., 2023; Xie et al., 2021]. Similar to traditional FL, GFL also faces the issue of data heterogeneity, and several studies have been conducted to address related challenges [Xie et al., 2021; Gauthier et al., 2023]. However, they still lack specific considerations for graph data. Particularly in graph-level federated learning, there is also a certain degree of heterogeneity among the graphs within each client. Those pose significant challenges to the overall goals of federated learning in various graph-based applications. As shown in Fig. 1, molecular structures can exhibit both ring and tree-like configurations, with substantial differences in their underlying attribute distributions.

∗Corresponding author: Huaming Wu

Additionally, significant domain differences across clients contribute to common forms of heterogeneity. To tackle the challenges caused by the heterogeneity, clustering techniques in personalized federated learning have emerged as a crucial solution. Previous works [Xie et al., 2021; Sattler et al., 2020] have attempted to address these challenges by clustering based on partial graph data or statistical information. However, the former approach compromises user privacy, giving rise to privacy vulnerabilities since sensitive information may be exposed during the clustering stage, while the latter inaccurately represents the data, leading to suboptimal outcomes in federated graph learning. Therefore, enhancing the performance of GFL with heterogeneous issues while ensuring privacy protection presents a significant challenge.

To address the contradiction between privacy and personality widely existed in heterogeneous environments, we propose a novel framework named personalized graph Federated learning with inter-Client and intra-Client Heterogeneity (FedCCH for brevity) for personalized graph federated learning with data privacy in heterogeneous environments. The main contributions can be summarized as follows:

• Joint learning for Intra- and inter-client personalization: We considered the issues of intra-client and interclient heterogeneity present in GFL in heterogeneity environments and proposed a novel personalized Graph Federated Learning approach, which is the first work to jointly learn intra- and inter-client personalization.
• Automatic Personalization Factor for IntraHeterogeneity: To address intra-client data heterogeneity, we propose a novel learnable PF by individually normalizing each graph within a client to achieve an approximate data feature distribution and excluding PF from federated learning. It is worth mentioning that FedCCH does not introduce additional hyper-parameters and can automatically learn personality.
• Hash-based Clustering for Personalization Learning: To address inter-client heterogeneity of graph data which deteriorates GNNs generalization, we innovatively utilize the hash algorithm to generate hash signatures for similarity calculations and clustering to protect client privacy while capturing heterogeneous relationships between clients.
• Effective Performance: We conduct extensive experiments on 15 graph datasets, which include 6 different data combinations to assess the performance of the proposed FedCCH framework. The results surpass multiple FL and GFL algorithms, outperforming other methods by up to 5.04% in average test accuracy on BIO-SN-CV.

2 Preliminaries

2.1 Federated Learning

In FL, each client owns a local private dataset Di drawn from distribution Pi(x, y), i = 1, 2, . . . ,m, where x and y denote the input features and corresponding class labels respectively, and m denotes the number of clients. Usually, clients share a model F(ω; x) with the same architecture and hyperparameters. This model is parameterized by learnable weights ω and input features x. The objective function of FedAvg [McMahan et al., 2017] is:

where ω is the global model's parameters, N is the total number of instances over all clients, F is the shared model, and LS is a general definition of any supervised learning task.

Nonetheless, In the statistical heterogeneity setting in the real world, Pi varies across clients, indicating heterogeneous input/output space for x and y. For example, Pi on different clients can be the data distributions over different subsets of classes. For the i-th client, the training procedure is to minimize the loss as defined below:

Most existing methods cannot well handle the heterogeneous settings above. Thus, the global model's parameter ω cannot be optimized by averaging ω1, ω2, . . . , ωm. In a GFL framework, ωi and Di refer to the parameter set of GNN model and the graph dataset at client i, respectively.

2.2 Graph Neural Networks

Let G = (V, E) be a graph consisting of a set of nodes V and a set of edges E connecting nodes. Each node v ∈ V has a feature vector xv. Based on the graph structure and node features, GNNs can be used to learn the node-level representation vector hv of node v ∈ V and/or the graph-level representation vector hG of graph G. Existing GNNs usually follow the message passing scheme where hv is iteratively updated by aggregating the representations of node v's neighbors. l-th layer in L-layer GNNs can be formulated as:

where h(l) v is the representation vector of node v output by the l-th layer, N(v) is the set of node v's neighbors. Different AGGREGATE and UPDATE strategies are adopted in different GNN variants and sometimes can be integrated together [Kipf andWelling, 2017].

Specifically, for graph classification, the graph representation hG can be further obtained by aggregating all the node representations involved in graph G via various graph-level readout functions, such as summation and mean pooling.

3 RelatedWork

3.1 Federated Learning

FL allows isolated data to collaboratively train a global model with strong generalization ability. FedAvg [McMahan et al., 2017], a classic FL algorithm, performs local training on clients iteratively and averages global parameters on a central server for the next round of client training. Various methods have been proposed to optimize communication cost [Hamer et al., 2020; Wu et al., 2022], data privacy [Wei et al., 2023; Tang et al., 2023], and model accuracy [Wu et al., 2023; Niu and Deng, 2022] in FL. This paper primarily focuses on enhancing model accuracy, which is independent and complementary to other methods concerning communication cost and data privacy. However, the heterogeneity of data distribution can negatively impact the generalization performance of the federated learning global model on each client.

To address this issue, PFL is proposed, which can be divided into data-based PFL and model-based PFL. Data-based PFL aims to reduce heterogeneity among clients by sharing part of the global data [Zhao et al., 2018], but it may pose privacy risks. To mitigate this, model-based PFL was introduced. Model-based PFL can be further categorized into single-model [Li et al., 2020; Karimireddy et al., 2020; Wang et al., 2019; Yue et al., 2021] and multi-model PFL approaches [Dinh et al., 2020; Arivazhagan et al., 2019]. However, the inherent characteristics of graph data introduce additional layers of heterogeneity that exacerbate the challenges in federated learning. This includes the variability in degree distribution across different graphs, the varying levels of sparsity within these graphs, and the diversity in graph feature representations. Such complexities render traditional federated learning methods less effective.

3.2 Graph Federated Learning

The rapid development of FL, along with the benefits of processing graph data using GNNs, has fostered the emergence of GFL, which enables the processing of distributed graph data through FL. Previous work in this area can be classified into three categories:

In node-level graph federated learning, each client possesses an ego graph, which comprises links to other clients, often encapsulating a wealth of information. This approach utilizes the client-composed graphs as the primary objects of learning, aiming to enhance the overall model's capabilities. SFL in [Baek et al., 2023] learns both the global and personalized models simultaneously using client-wise relation graphs and clients' private data to enhance the knowledgesharing process in PFL. Lumos in [Pan et al., 2023] design a novel tree constructor to improve the representation capability given the limited structural information.

In subgraph-level graph federated learning, where the client only holds a part of the complete graph data [Zheng et al., 2021; Chen et al., 2021; Zhang et al., 2021; Zhang et al., 2022; Liu et al., 2021; Baek et al., 2023; Guo et al., 2023]. These works address information loss after splitting subgraphs, either by generating missing nodes [Zhang et al., 2021] or improving federation strategies [Zheng et al., 2021].

This research is mainly oriented toward node classification or link prediction tasks on graphs.

In graph-level graph federated learning, each client holds multiple complete graphs and mainly uses graph classification as the main downstream task [Hu et al., 2022; Xie et al., 2021; Tan et al., 2023]. Existing research mainly focuses on the heterogeneity of graphs between different clients, GCFL in [Xie et al., 2021] performance clustering federated learning based on gradients. FedStar in [Tan et al., 2023] tries to share domain-agnostic structural information to enhance local model performance. However, existing methodologies often overlook the heterogeneity prevalent within client-specific graph data, notably in aspects such as graph degree distribution and feature distribution. This oversight consequently restricts the performance efficacy of Graph Neural Networks (GNNs). Our research is directed towards developing an advanced graph federation architecture. This architecture is meticulously designed to proficiently address both intra-client and inter-client heterogeneity without additional privacy concerns compared to traditional methods.

4 Methodology

4.1 FedCCHOverview

In our federated learning framework, we consider a scenario with m distinct clients, each identified by indices 1, 2, · · · ,m. These clients operate under the oversight of a semi-honest or curious server. Each client possesses a collection of complete graphs, with all graphs from a single client belonging to the same domain. Since graph data in different domains may contain complementary information. Through federated learning, various fields can share their domain expertise, thereby improving the performance of the overall model. For instance, client A, representing a biological company, holds extensive biological graph data, while client B, representing a chemical company, maintains a substantial repository of chemical molecular graphs. The objective is to collaboratively train multiple Graph Neural Network (GNN) models that fulfill the requirements of all participating entities. Finally, the system trains each client's model based on local graph data and performs clustering federated average learning. We can formulate the goal of the system as Eq 2.

4.2 Automatic Personalization Factor

We introduce 'intra-client heterogeneity' as a novel concept, specifically referring to the variability in structural and feature compositions among different graphs within the same client. To address this challenge, we advocate using feature standardization and transformation techniques, such as BatchNorm and LayerNorm.

However, this one-size-fits-all approach may fail to address the unique characteristics of each client's data effectively. Secondly, the necessity of model sharing in a federated environment raises concerns, particularly with regularization layers that encapsulate extensive information, potentially leading to privacy vulnerabilities.

To mitigate these issues, we propose the introduction of personalization factors. This concept is designed to navigate the balance between standardization and customization. By applying these factors, local data undergoes feature normalization tailored to the specific characteristics of each client's dataset. Crucially, while standardizing local data, the personalization factors refrain from sharing any federated data. This approach aims to preserve data privacy while ensuring that the normalization process is more closely aligned with the intrinsic properties of each client's data, thereby enhancing model relevance and effectiveness in a federated learning context.

Inspired by [Cai et al., 2021], considering the particularity of the graph structure, structural information for classification will be lost when removing the norm mean. we have elected to employ it as our preferred standardization method in this study. We perform the GIN layer to obtain the hidden embedding for each graph G in the client i as follows:

where l = 1, . . . , L, k = 1, . . . ,Ki, and Ki is the number of graphs in the i-th client. h(0) i,k is the input graph, ˆh(l) i,k denotes the hidden embedding of the graph in the l-th layer. GIN(·) denotes the GIN layer [Xu et al., 2018] of the model. We denote the element of v-th row and d-th column in h(l) i,k as h(l) i,k,v,d , which is abbreviated as h(l) v,d for the purpose of simplification when computing PF factors. The value of PF factor is computed as follows:

where d = 1, 2, . . . , d(l) represents the index of the embedding of the l-th layer, µd = ∑nv=1 h(l) v,d n , ˆσ2 d =

∑nv=1 (h(l) v,d-α(l) d ·µd )2 n , γ (l) i,d , β(l) i,d are the affine parameters as BatchNorm, hv,d specializes in the d-th parameter of the vth node in the graph, and α(l) i,d is the learnable parameter that plays a crucial role in controlling the retention of information and enhancing the expressive capability of GNNs.

The retention of PF at the local client level, while excluding them from the federated learning's shared parameters, is a strategic approach that caters to the specific needs of individual graph datasets. This methodology permits each set of graph data within a client to adapt to its unique distributional characteristics, significantly enhancing the suitability and efficacy of the model for that particular data. After the PF and ReLU [Glorot et al., 2011], we get the embedding of the l-th layer as follows:

After the transformation of L layers of the neural network, the final representation h(L) i,k is obtained. Next, the embedding is processed by the READOUT function which is summation to obtain the entire graph's representation hk and compared with the ground truth ˆ yi label to calculate the loss and perform gradient descent. The loss function is Cross-Entropy loss as follows:

where R represents the number of graph categories. It is worth noting that parameters such as α(l) i , γ (l) i andβ(l) i are updated after the gradient is backpropagated. The specific process is shown in the upper part of Fig 2.

As a result, local models are capable of achieving faster convergence rates, effectively addressing the challenge of intra-client graph data heterogeneity. The implementation of the PF plays a pivotal role in ensuring that disparate graph datasets within a single client can approximate and learn from their respective distributional representations. Consequently, this leads to an overall improvement in model performance, substantially mitigating the effects of data heterogeneity present within individual clients.

4.3 Hash-based Clustering

In real-world settings, the inherent data heterogeneity among different clients presents a significant challenge to the effectiveness of traditional federated learning methods. To address this, clustering techniques in personalized federated learning have emerged as a key solution. These techniques involve grouping clients based on the similarity in their data distributions, allowing for model training to be tailored to each cluster. This strategy enhances the relevance and suitability of the model to the particular characteristics of the clients within a given group. Implementing clustering in federated learning enhances model performance by tailoring each model to the specific characteristics of its cluster's data, leading to increased accuracy and efficiency. Additionally, it optimizes resource utilization by focusing training and communication on similar clients, conserving computing and communication resources across the network.

While client-side clustering in federated learning presents several advantages, it is not devoid of challenges. Firstly, though this approach can enhance privacy protection, the clustering process often necessitates a degree of data sharing or analysis. This requirement could potentially lead to privacy vulnerabilities, as sensitive information might be exposed during the clustering phase. Secondly, the reliance on indirect features in certain clustering algorithms might not accurately represent the extent of heterogeneity across diverse data distributions. Such algorithms might fail to capture the nuanced differences between datasets, thereby limiting the effectiveness of the clustering. Lastly, the dynamic nature of data in real-world scenarios poses another challenge. Static clustering methods may struggle to adapt to changes in similarity measures over time, leading to outdated or suboptimal groupings.

We adopt aggregation and hash operations to preserve essential client features while ensuring data privacy to tackle this challenge and explore the potential of low-dimensional data representations. Considering the data scale drift among different datasets, we aim to streamline computations and minimize communication costs by achieving a uniform length representation for all clients. To achieve this, we get the final embedding hLi,k of graph k at last round of epochs in the client, and aggregate the all graph's embedding as Ht i = [hLi,1 , . . . , hLi,Ki ], where t represents the number of FL training rounds. Then we compute the unified representation of client i at t-round after aggregation as follows:

where Ti = 1 |Di| 1 T represents the aggregation matrix for mean-pooling and |Di| is the size of graphs of i-th client.

Indeed, hash-based similarity computation has gained popularity in the field of computer vision for achieving faster computation. This approach involves converting two images into a consistent range of pixels and utilizing a hash function to generate a signature that represents the images' similarity. By using this compact representation, image similarity can be efficiently calculated, making it an effective method for largescale image processing tasks. Hash-based image similarity computation has been widely adopted in various computer vision applications, including image retrieval, object detection, and image clustering, due to its computational efficiency and satisfactory performance.

While most algorithms designed for Euclidean data might not adapt to the graph data, we leverage the low-dimensional representation of the data as it reflects valuable information. For our approach, we consider the low-dimensional vector matrix generated by the client as the input, treating it as Euclidean data for the algorithm. In the last round of GNNs training, the resulting embedding is compressed into a matrix with consistent dimensions, which serves as the input for the hash function as follows:

where HASH represents a special mapping function that maps ˆHti to Sti . After the clients send their hash signatures to the server, the server calculates the similarity E t ij between client i and client j based on the corresponding hash signatures. The specific formula is as follows:

where HammingDistance(·) is employed to calculate the dissimilarity between two hash signatures. It involves comparing each bit of the vector to determine if they are the same. If they differ, the Hamming Distance is incremented by one. By summing up the differences in the bits, we obtain the HammingDistance as a measure of dissimilarity.

The similarity between client i and client j is obtained by subtracting the Hamming distance by one and dividing it by the length of the hash signature. Based on the similarity values, a similarity matrix E is formed as follows:

Based on the computed similarity matrix, we employ commonly used clustering methods, such as k-means and Hierarchical Clustering Tree (HCT), for the clustering process. In this paper, we primarily utilize HCT as the clustering method to group the clients into multiple clusters based on their similarity. After determining the clustering result, the client assigned to a specific cluster will engage in synchronous training within that cluster. This involves performing FL specifically within the assigned cluster.

4.4 Model Training Process

FedCCH combines PF with clustering federated learning to enable individual clients to learn knowledge more effectively and achieve better training results in the presence of heterogeneous graph data. Fig. 2 illustrates the overall training pipeline of our proposed method, where each client, regardless of whether they have the same or different domain graph data, employs the same model architecture.

From left to right, for the client i, the model is trained using its local data. Subsequently, the client computes the signature of its data, uploads the signature information along with the model, and retains the PF parameters locally. This process ensures that each client can effectively personalize their training process while still contributing to the overall FL framework. After clustering in the server and dividing into c classes, the model parameters are averaged within the classes, and the averaging step is similar to FedAvg [McMahan et al., 2017], which behaves as follows:

where |Di| refers to the number of graphs in the local dataset of client i and |Dc| refers to the total number of graphs across all clients in the c-th cluster. Then, the server returns wtc to clients in the c-th cluster, and clients update their local model parameters wt+1 i by wtc except for the PF and start local training for the next round. The complete algorithm is shown in the Appendix.

5 Experiments

5.1 Experimental Settings

Datasets We use 15 public graph classification datasets from four different fields, including small molecules (MUTAG, BZR, COX2, DHFR, PTC MR, AIDS, NCI1), bioinformatics (ENZYMES, DD), social network (COLLAB, IMDBBINARY, IMDB-MULTI) and computer vision (Letter-low, Letter-high, Letter-med)[Morris et al., 2020].To thoroughly assess the method's effectiveness on heterogeneous graph data, we segmented the aforementioned graph data into six different combinations as CHEM, BIO-CHEM, MIX, BIOSN-CV, BIO-CV, ALL. Specific information on all graph data can be obtained from the Appendix. In each setting, the client owns the corresponding data set One, by default is randomly divided into three parts: 80% for training, 10% for validation, and 10% for testing.

5.2 Baseline and Experiment Setting

We compare FedCCH with eight baselines. It includes classic federated learning algorithms FedAvg[McMahan et al., 2017], FedProx [Li et al., 2020] and FedBN [Li et al., 2021]. graph federated learning algorithms FedStar [Tan et al., 2023] and GCFL [Xie et al., 2021], and specially modified classic federated learning algorithms FedAvg+PF and FedAvg+PF. The details of these baselines are provided in the Appendix. For model, we primarily utilize a three-layer Graph Isomorphism Network (GIN) as our model. Before the activation function, we incorporate Batch Normalization and Graph Normalization layers. The hidden layer dimension of the GIN is set to 64. For the local training process, we employ 1 epoch and a batch size of 64. The optimization is performed using the Adam optimizer with a weight decay of 5 × 10-5 and a learning rate of 0.001. Regarding the FL settings, we set the number of communication rounds to 200 for all FL methods. We employ the Ahash method for hashing and a hierarchical clustering tree for clustering. To ensure robustness in the experimental results, we conduct 5 experiments with different random seeds and calculate the mean and variance. The experiments are conducted on a system equipped with an Nvidia 3090Ti GPU configuration.

5.3 Experimental Results

Performance on Graph Classification. We show federated graph classification results for all methods under six non-IID settings, including a cross-dataset setting (CHEM) and five cross-domain different settings (BIO-CHEM, BIOCHEM-SN, BIO-SN-CV). We summarize the final average test accuracy and its average gain compared to Local in Table 1. The results show that FedCCH is significantly better than all baselines overall, and the effect is even more obvious after combining the proposed PF.

Among them, traditional FL methods (such as FedAvg and FedProx) cannot surpass Local due to the inevitable performance deterioration in non-IID settings. In particular, FedAvg dropped by 0.96% and 2.09% in BIO-CHEM and ALL respectively, while FedProx dropped by 0.40% and 2.14% in BIO-CHEM and ALL respectively. FedBN, which is designed for personalization, is not suitable for graph data due to its BatchNorm layer and performs poorly in all datasets, losing 4.22% accuracy in the ALL dataset. The two FGL methods (FedStar and GCFL) perform better than Local in most cases. The structure embedding sharing strategy adopted by FedStar aims to share feature-independent structural information, effectively avoiding performance degradation caused by feature heterogeneity and with a 2.64% accuracy increase on BIO-CHEM, but in some datasets such as BIO-CV, the effect is unsatisfactory due to potential heterogeneity in the structure of the data. GCFL uses the nature of gradient information to cluster data information and outperforms Local with a 1.43% accuracy increase on BIO-SN-CV, but due to the limitations of gradient information, most of the effects are not as significant as FedCCH.

ConvergenceAnalysis Fig. 3 illustrates the average test accuracy curves of different FL methods on four datasets, excluding the baseline with regularization technology. It can be observed that across all datasets, FedCCH exhibits faster convergence speed and achieves better average test accuracy. Compared with other baselines, FedCCH saves 100 rounds of training time on average, which is attributed to the fact that the hash clustering method captures more intrinsic similarities between the data, enabling each client to achieve improved performance.

5.4 Ablation Study

Ablation Experiment of HashMechanisms. In our experiment, we removed the hash mechanism and solely utilized cosine similarity, calculated by embedding the data, to represent the similarity between clients and clusters. As depicted in Fig. 4, when compared with the method without the hash mechanism, the performance of FedCCH has not significantly declined. In fact, there is a certain improvement observed in most of the datasets, which indicates that the hash clustering mechanism can contribute to the accuracy performance of the model while reducing the sensitivity of the data.

Ablation Experiment of The PF To investigate the impact of the PF on the overall performance of FL, we conducted experiments on multiple datasets using FedCCH by sharing its layer globally. As depicted in Fig. 4, there is a substantial improvement in performance when retaining the PF locally across different datasets, which suggests that the PF is better suited for local clients to undergo specific training without the need for sharing, resulting in reduced communication costs in FL.

6 Conclusion

In this paper, we define the intra-client heterogeneity and inter-client heterogeneity that exist in graph-level graph federation learning and propose FedCCH to overcome the training challenge caused by these two kinds of heterogeneity. For details, the proposed framework FedCCH improve the training performance by collaboratively training two novel modules: one novel module is hash-based similarity clustering and the other novel module is the learnable PF normalizing, where hash-based similarity clustering can capture inter-client heterogeneity and protect client privacy, while PF normalizing can capture intra-client heterogeneity and bring a faster convergence. Through extensive experiments on 15 graph datasets, the results demonstrate the effectiveness and superiority of the proposed FedCCH. In future work, we will study how to improve the robustness of graph federated systems while handling graph data heterogeneity.

Acknowledgments

This work was supported in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LDT23F01012F01 and LQN25F020016 and by the National Natural Science Foundation of China under Grant Number 62401190, 62372146 and 62071327.