Virtual Network Embedding (VNE) is an essential component of network virtualization technology. Prior works on VNE mainly focused on resource efficiency and did not address the scalability as a first-grade objective. Consequently, the ever-increasing demand and size render them less-practical. The few existing designs for mitigating this problem either do not extend to multi-resource settings or do not consider the physical servers and network simultaneously. In this work, we develop GraphViNE, a parallelizable VNE solution based on spatial Graph Neural Networks (GNN) that clusters the servers to guide the embedding process towards an improved runtime and performance. Our experiments using simulations show that the parallelism of GraphViNE reduces its runtime by a factor of 8. Also, GraphViNE improves the revenue-to-cost ratio by about 18%, compared to other simulated algorithms.