FedGCD: Federated Learning Algorithm with GNN-based Community Detection for Heterogeneous Data

English

Overview

This paper introduces FedGCD, a federated learning algorithm that utilizes Graph Neural Network (GNN)-based community detection to address the non-IID problem in distributed clients. By detecting clusters of clients with similar data distributions, the algorithm enables adaptive model aggregation and reduces the bias introduced by statistical heterogeneity.

Citation:
Shin, W., & Shin, J. (2023). FedGCD: Federated Learning Algorithm with GNN-based Community Detection for Heterogeneous Data.
Journal of Internet Computing and Services (JICS), 24(6), 1–11.

Motivation

Federated learning suffers from data heterogeneity across clients, where different users have distinct data distributions. FedGCD proposes a community-aware structure that groups similar clients together and performs community-level aggregation using GNN-based connectivity. This approach helps reduce client drift and improves convergence compared to conventional methods such as FedAvg and FedProx.

Algorithmic Framework

1. Graph Construction

Each client is represented as a node, and the similarity between clients is encoded as an edge weight. Let \( G(V, E) \) denote the client graph where:

\[V = \{a_1, a_2, \dots, a_K\}, \quad E = \{e_{i,j} \mid \text{similarity}(a_i, a_j) > \tau\}\]

The similarity threshold \( \tau \) controls edge sparsity and determines how clients are connected based on local update similarity or feature-space proximity.

2. Community Detection via GNN

FedGCD employs a Multi-NMF (M-NMF) and GNN-based embedding for community detection. The membership strength of client \( i \) to community \( j \) is given by:

\[s_{i,j} = \frac{1}{|D_i|} \sum_{x \in D_i} 1(x \in c_j)\]

These scores define overlapping community memberships used during aggregation.

3. Community-Level Aggregation

After communities are formed, local models are trained per community. Each client's contribution to the global model is adjusted based on its membership score:

\[w_i = \sum_{j=1}^{C} \frac{s_{i,j} \, w_j}{\sum_{k=1}^{C} s_{i,k}}\]

This ensures that clients participating in multiple communities are proportionally weighted across those models.

4. Optimal Community Selection (AIC)

The number of optimal communities \( k^* \) is selected using the Akaike Information Criterion (AIC):

\[AIC(k) = 2k - 2\log(L(k))\]

where \( L(k) \) is the likelihood of the data given \( k \) clusters.

Schematic Diagram

The following schematic illustrates the FedGCD architecture, showing the process from client graph construction to GNN-based community detection and global aggregation.

FedGCD Framework Diagram

Figure 1. Overview of the FedGCD algorithm with GNN-based community detection.

Pseudocode

The pseudocode below summarizes the major steps of the FedGCD algorithm, including graph construction, GNN training for community detection, and adaptive aggregation.

FedGCD Algorithm Pseudocode

Algorithm 1. Pseudocode for FedGCD federated learning framework.

Experimental Setup

  • Dataset: FEMNIST (handwritten character dataset)
  • Number of Clients: 100
  • Training Rounds: 300
  • Local Epochs: 5
  • Metrics: Accuracy, F1-Score, Convergence Rate
  • Baselines: FedProx, FedVar, FedAvg

Results

Setting FedProx FedVar FedGCD (Proposed)
Non-IID (0.7) 91.0% 90.8% 91.3%
Semi-IID (0.5) 89.5% 90.1% 93.1%
IID (0.2) 86.0% 85.8% 86.2%

FedGCD consistently achieves higher performance than FedProx and FedVar, especially in non-IID and semi-IID environments. The community-based structure allows for better convergence and generalization across heterogeneous clients.

Conclusion

FedGCD demonstrates that leveraging graph structure learning and community-aware aggregation can effectively address client heterogeneity in federated learning. The algorithm provides an interpretable framework where GNNs model inter-client relationships, achieving superior accuracy and stability across different heterogeneity levels.

한국어

연구 요약

본 논문은 비독립·비동일 분포(Non-IID) 환경에서의 연합학습 성능 저하 문제를 해결하기 위해, 그래프 신경망(GNN)을 이용한 커뮤니티 탐지 기반 연합학습(FedGCD) 알고리즘을 제안한다. 클라이언트 간 데이터 유사도를 그래프로 표현하고, GNN을 활용하여 통계적 특성이 유사한 클라이언트들을 커뮤니티로 군집화한다. 각 커뮤니티 모델은 독립적으로 학습되며, 멤버십 가중치를 반영하여 전역 모델을 집계한다. FEMNIST 데이터셋을 이용한 실험 결과, FedGCD는 FedProx 및 FedVar 대비 Non-IID 환경에서 최대 2.1%의 정확도 향상을 달성하고, 데이터 이질성이 심한 환경에서도 높은 안정성과 수렴 속도를 보였다.

Updated: