  The convergence speed of machine learning models trained with Federated
Learning is significantly affected by heterogeneous data partitions, even more
so in a fully decentralized setting without a central server. In this paper, we
show that the impact of label distribution skew, an important type of data
heterogeneity, can be significantly reduced by carefully designing the
underlying communication topology. We present D-Cliques, a novel topology that
reduces gradient bias by grouping nodes in sparsely interconnected cliques such
that the label distribution in a clique is representative of the global label
distribution. We also show how to adapt the updates of decentralized SGD to
obtain unbiased gradients and implement an effective momentum with D-Cliques.
Our extensive empirical evaluation on MNIST and CIFAR10 demonstrates that our
approach provides similar convergence speed as a fully-connected topology,
which provides the best convergence in a data heterogeneous setting, with a
significant reduction in the number of edges and messages. In a 1000-node
topology, D-Cliques require 98% less edges and 96% less total messages, with
further possible gains using a small-world topology across cliques.
