Joint Client and Cross-Client Edge Selection for Cost-Efficient Federated Learning of Graph Convolutional Networks

Graph-structured data applications promote the development of Graph Neural Networks (GNN) in recent years. Due to privacy concerns, collecting graph data stored in massive client devices for centralized graph learning is prohibitive. It is natural to integrate federated learning (FL) in graph learning to address this issue, which enables clients to collaborate on training a shared model without uploading their data. This generates an emerging paradigm of federated graph learning (FGL). However, due to various costs incurred by FGL training, the collaboration between the server and clients is still a challenging issue in FGL, which remains largely unexplored in existing studies. To bridge this gap, we propose a cost-efficient collaboration framework for FGL of graph convolutional networks on semi-supervised node classification tasks, i.e., Joint Client and Cross-Client Edge Selection (JC3ES) for the server. Specifically, we first characterize how varies graph structure affect the final convergence performance of the FGL model. We then reveal the fundamental supermodular property in client selection. Based on this, we further devise an approximately optimal algorithm for the server and theoretically derive the performance gap between the proposed algorithm and the optimal solution. Extensive numerical evaluations show that our proposed algorithm achieves outstanding performance in cost-efficient collaboration for FGL on popular graph datasets.