Recent advances in algorithmic and computational tools have led to an unprecedented growth in data mining over networks. However, partial knowledge of node connectivity (due to privacy concerns or the large number of nodes), as well as incomplete domain knowledge (as in e.g., biological applications), challenge learning tasks over real networks. For robust learning from incomplete data, node embedding over graphs is thus well motivated, and is pursued here by leveraging tensors as multi-dimensional data structures. To this end, a novel tensor-based network representation is advocated, over which node embedding is cast as a structured nonnegative tensor decomposition. The trilinear factorization involved is performed using an alternating least-squares approach. The extracted node embeddings are then utilized to predict the missing links. Performance is assessed via numerical tests on benchmark networks, corroborating the effectiveness and robustness of the proposed technique over incomplete graphs.