Vast amount of data generated from networks of sensors, wearables, and theInternet of Things (IoT) devices underscores the need for advanced modelingtechniques that leverage the spatio-temporal structure of decentralized datadue to the need for edge computation and licensing (data access) issues. Whilefederated learning (FL) has emerged as a framework for model training withoutrequiring direct data sharing and exchange, effectively modeling the complexspatio-temporal dependencies to improve forecasting capabilities still remainsan open problem. On the other hand, state-of-the-art spatio-temporalforecasting models assume unfettered access to the data, neglecting constraintson data sharing. To bridge this gap, we propose a federated spatio-temporalmodel -- Cross-Node Federated Graph Neural Network (CNFGNN) -- which explicitlyencodes the underlying graph structure using graph neural network (GNN)-basedarchitecture under the constraint of cross-node federated learning, whichrequires that data in a network of nodes is generated locally on each node andremains decentralized. CNFGNN operates by disentangling the temporal dynamicsmodeling on devices and spatial dynamics on the server, utilizing alternatingoptimization to reduce the communication cost, facilitating computations on theedge devices. Experiments on the traffic flow forecasting task show that CNFGNNachieves the best forecasting performance in both transductive and inductivelearning settings with no extra computation cost on edge devices, whileincurring modest communication cost.