Graph neural networks or GNNs have in the recent years exhibited great results in node classification, incorporating both the structure and the attributes of graphs to achieve high performance. Many real-world datasets, however, don't always have complete or noiseless structures. Graph structure learning or GSL can help in alleviating this problem, although many algorithms have shallow message propagation schemes, ignoring the deep expressibility that is possible with multi-layer networks. In this work we propose a deep variational structure learning model for semi-supervised node classification called VSLII, which is able to combine the dynamic graph refinement of GSL algorithms with the complexity of deep convolutional methods. The proposed model uses deep message propagation in a modified, deep variational graph autoencoder via the GCNII layer to refine the structure learning and a simple GCNII model for the node classification, outperforming state of the art methods, both in graph and non-graph structured datasets.