Traffic volumes are an essential input to many highway planning and design models; however, collecting this data for all the roads in a network is not practical nor cost-effective. Accordingly, transportation agencies must find ways to leverage limited ground truth count data to obtain reasonable estimates at scale on all the network segments. One of the challenges that complicate this estimation is the complex spatial dependency of the links’ traffic state in a transportation network. A graph-based model is proposed to estimate networkwide traffic volumes to address this challenge. This model aims to consider the graph structure of the network to extract its spatial correlations while estimating link volumes. In the first step, a proof-of-concept methodology is presented to indicate how adding the simple spatial correlation between the links in the Euclidian space improves the performance of a state-of-the-art volume estimation model. This methodology is applied to the New Hampshire road network to estimate statewide hourly traffic volumes. In the next step, a Graph Neural Network model is introduced to consider the complex interdependency of the road network in a non-Euclidean domain. This model is called Fine-tuned Spatio-Temporal Graph Neural Network (FSTGCN) and applied to various Maryland State networks to estimate 15-minute traffic volumes. The results illustrate significant improvement over the existing state-of-the-art models used for networkwide traffic volume estimation, namely ANN and XGBoost.