  This paper proposes a general spectral analysis framework that thwarts a
security risk in federated Learning caused by groups of malicious Byzantine
attackers or colluders, who conspire to upload vicious model updates to
severely debase global model performances. The proposed framework delineates
the strong consistency and temporal coherence between Byzantine colluders'
model updates from a spectral analysis lens, and, formulates the detection of
Byzantine misbehaviours as a community detection problem in weighted graphs.
The modified normalized graph cut is then utilized to discern attackers from
benign participants. Moreover, the Spectral heuristics is adopted to make the
detection robust against various attacks. The proposed Byzantine colluder
resilient method, i.e., FedCut, is guaranteed to converge with bounded errors.
Extensive experimental results under a variety of settings justify the
superiority of FedCut, which demonstrates extremely robust model performance
(MP) under various attacks. It was shown that FedCut's averaged MP is 2.1% to
16.5% better than that of the state of the art Byzantine-resilient methods. In
terms of the worst-case model performance (MP), FedCut is 17.6% to 69.5% better
than these methods.
