FedGCN: Convergence and Communication Tradeoffs in Federated Training of Graph Convolutional Networks

Distributed methods for training models on large graphs have recently grown in popularity, due to the size of graphs as well as the private nature of graph data like social networks. However, the graph structure means that a single graph cannot be disjointly partitioned into different learning clients, leading to either significant communication overhead between clients or a loss of information available to the training method. We then introduce Federated Graph Convolutional Network (FedGCN), which uses federated learning to train GCN models for semi-supervised node classification on large graphs with optimized convergence rate and communication cost. Compared to prior methods that require communication among clients at each training round, FedGCN preserves the privacy of client data and only needs communication at the initial step, which greatly reduces communication cost and speeds up the convergence. We theoretically analyze the tradeoff between FedGCN's convergence rate and communication cost under different data distributions, and introduce a general framework that can be generally used for the analysis of all edge-completion-based GCN training algorithms. Experimental results demonstrate the effectiveness of our algorithm and validate our theoretical analysis.