  In the era of a data-driven society with the ubiquity of Internet of Things
(IoT) devices storing large amounts of data localized at different places,
distributed learning has gained a lot of traction, however, assuming
independent and identically distributed data (iid) across the devices. While
relaxing this assumption that anyway does not hold in reality due to the
heterogeneous nature of devices, federated learning (FL) has emerged as a
privacy-preserving solution to train a collaborative model over non-iid data
distributed across a massive number of devices. However, the appearance of
malicious devices (attackers), who intend to corrupt the FL model, is
inevitable due to unrestricted participation. In this work, we aim to identify
such attackers and mitigate their impact on the model, essentially under a
setting of bidirectional label flipping attacks with collusion. We propose two
graph theoretic algorithms, based on Minimum Spanning Tree and k-Densest graph,
by leveraging correlations between local models. Our FL model can nullify the
influence of attackers even when they are up to 70% of all the clients whereas
prior works could not afford more than 50% of clients as attackers. The
effectiveness of our algorithms is ascertained through experiments on two
benchmark datasets, namely MNIST and Fashion-MNIST, with overwhelming
attackers. We establish the superiority of our algorithms over the existing
ones using accuracy, attack success rate, and early detection round.
