  Graph neural networks (GNN) have been widely deployed in real-world networked
applications and systems due to their capability to handle graph-structured
data. However, the growing awareness of data privacy severely challenges the
traditional centralized model training paradigm, where a server holds all the
graph information. Federated learning is an emerging collaborative computing
paradigm that allows model training without data centralization. Existing
federated GNN studies mainly focus on systems where clients hold distinctive
graphs or sub-graphs. The practical node-level federated situation, where each
client is only aware of its direct neighbors, has yet to be studied. In this
paper, we propose the first federated GNN framework called Lumos that supports
supervised and unsupervised learning with feature and degree protection on
node-level federated graphs. We first design a tree constructor to improve the
representation capability given the limited structural information. We further
present a Monte Carlo Markov Chain-based algorithm to mitigate the workload
imbalance caused by degree heterogeneity with theoretically-guaranteed
performance. Based on the constructed tree for each client, a decentralized
tree-based GNN trainer is proposed to support versatile training. Extensive
experiments demonstrate that Lumos outperforms the baseline with significantly
higher accuracy and greatly reduced communication cost and training time.
