Vehicle Edge Computing (VEC) has emerged as an efficacious paradigm that supports real-time, computation-intensive vehicular applications. However, due to the highly dynamic nature of computing node topology, existing scheduling algorithms need to more effectively apprehend the characteristics of fine-grained task topologies and network topologies. Moreover, they require significant communication overhead and training costs, making them inadequate for fine-grained task scheduling in vehicular networks. In response, our research explores fine-grained task scheduling issues within VEC scenarios, proposing a scheduling algorithm based on Graph Neural Networks and Federated Learning (FL-GNN). This algorithm maintains a global scheduling model that periodically aggregates local scheduling models deployed on Roadside Units (RSUs) and high-performance vehicles. Furthermore, to enhance the model’s ability to perceive topology and expedite the convergence rate, we incorporate a graph neural network layer in each local model to preprocess the raw state of the VEC environment. Lastly, we construct a simulation platform and implement multiple competitive solutions, demonstrating the superiority of the FL-GNN algorithm in aspects such as reducing the average task delay, balancing the load, and improving the task scheduling success rate.