Graph neural networks have been widely used for a variety of learning tasks. Link prediction is a relatively under-studied graph learning task, with current state-of-the-art models based on one- or two-layer shallow graph auto-encoder (GAE) architectures. In this paper, we overcome the limitation of current methods for link prediction of non-Euclidean network data, which can only use shallow GAEs and variational GAEs. Our proposed methods innovatively incorporate standard auto-encoders (AEs) into the architectures of GAEs to capitalize on the intimate coupling of node and edge information in complex network data. Empirically, extensive experiments on various datasets demonstrate the competitive performance of our proposed approach. Theoretically, we prove that our deep extensions can inclusively express multiple polynomial filters with different orders. The codes of this paper are available at https://github.com/xinxingwu-uk/DGAE.