  While federated learning has shown strong results in optimizing a machine
learning model without direct access to the original data, its performance may
be hindered by intermittent client availability which slows down the
convergence and biases the final learned model. There are significant
challenges to achieve both stable and bias-free training under arbitrary client
availability. To address these challenges, we propose a framework named
Federated Graph-based Sampling (FedGS), to stabilize the global model update
and mitigate the long-term bias given arbitrary client availability
simultaneously. First, we model the data correlations of clients with a
Data-Distribution-Dependency Graph (3DG) that helps keep the sampled clients
data apart from each other, which is theoretically shown to improve the
approximation to the optimal model update. Second, constrained by the
far-distance in data distribution of the sampled clients, we further minimize
the variance of the numbers of times that the clients are sampled, to mitigate
long-term bias. To validate the effectiveness of FedGS, we conduct experiments
on three datasets under a comprehensive set of seven client availability modes.
Our experimental results confirm FedGS's advantage in both enabling a fair
client-sampling scheme and improving the model performance under arbitrary
client availability. Our code is available at
\url{https://github.com/WwZzz/FedGS}.
