Real-time traffic speed estimation is an essential component of intelligent transportation system technologies. It is the foundation of modern transportation control and management applications. However, existing traffic speed acquisition systems can only provide real-time speed measurements of a small number of roads with stationary speed sensors and crowdsourcing vehicles. How to utilize these information to provide traffic speed maps for transportation networks is becoming a key problem in intelligent transportation systems. In this work, we present a novel deep learning model called graph convolutional generative autoencoder to fully address the real-time traffic speed estimation problem. The proposed model incorporates the recent development of deep learning techniques to extract the spatial correlation of the transportation network from the input incomplete historical data. To evaluate the proposed speed estimation technique, we conduct comprehensive case studies on a real-world transportation network and vehicular traces. The simulation results demonstrate that the proposed technique can notably outperform existing traffic speed estimation and deep learning techniques. In addition, the impact of dataset properties and control parameters are investigated.