In this paper we deal with complex attributed graphs which can exhibit rich connectivity patterns and whose nodes are often associated with attributes, such as text or images. In order to analyze these graphs, the primary challenge is to find an effective way to represent them by preserving both structural properties and node attribute information. To create low-dimensional and meaningful embedded representations of these complex graphs, we propose a fully unsupervised model based on Deep Learning architectures, called Constrained Attributed Graph Embedding model (CAGE). The main contribution of the proposed model is the definition of a novel two-phase optimization problem that explicitly models node attributes to obtain a higher representation expressiveness while preserving the local and the global structural properties of the graph. We validated our approach on two different benchmark datasets for node classification. Experimental results demonstrate that this novel representation provides significant improvements compared to state of the art approaches, also showing higher robustness with respect to the size of the training data.