Resource allocation of 5G network slices is one of the most important challenges for network operators. It can be formulated using the Virtual Network Embedding (VNE) problem, which was and remains an active field of studies, also known because of its NP-hardness. Owing to its complexity, several heuristics, meta-heuristics and Deep Learning-based solutions have been proposed. However, these solutions are inefficient either due to their slowness or to not taking into account the structure of data which results in an inefficient exploration of the solutions space. To overcome these issues, in this work we unveil the potential of Graph Convolutional Neural (GCN) networks and Deep Reinforcement Learning techniques in solving the VNE problem. The key point of our approach is modeling of the VNE problem as an episodic Markov Decision Process which is solved in a Reinforcement Learning fashion using a GCNbased neural architecture. The simulation results highlight the efficiency of our approach through an increased performance over time, while outperforming state-of-art solutions in terms of the services' acceptance ratio.