Federated Learning coordinates many mobile devices to train an artificial intelligence model while preserving data privacy collaboratively. Mobile devices are usually equipped with totally different hardware configurations, leading to various training capabilities. At the same time, the distribution of the local training data is highly heterogeneous across different clients. Randomly selecting the clients to participate in the training process results in poor model performance and low system efficiency.

In this paper, we propose GraphCS, a graph-based client selection framework for heterogeneity in Federated Learning. GraphCS first measures the distribution coupling across the clients via the model gradients. After that, it divides the clients into different groups according to the diversity of the local datasets. At the same time, it well estimates the runtime training capability of each client by jointly considering the hardware configuration and resource contention caused by the concurrently running apps. With the distribution coupling information and runtime training capability, GraphCS selects the best clients in order to well balance the model accuracy and overall training progress. We evaluate the performance of GraphCS with mobile devices with different hardware configurations on various datasets. The experiment results show that our approach improves model accuracy up to 45.69%. Meanwhile, it reduces communication and computation overhead 87.35% and 89.48% at best, respectively. Furthermore, GraphCS accelerates the overall training process up to 35×.