Network embedding aims to preserve topological structures of a network using low-dimensional vectors and has shown to be effective for driving a myriad of graph mining tasks (e.g., link prediction or classification) free of the stressful feature extraction procedure. Many methods have been proposed to integrate node content and/or label information, with nodes sharing similar content/labels being close to each other in the learned latent space. To date, existing methods either consider networked instances with a single label or consider a set of labels as a whole for node representation learning. Therefore, they cannot handle network of instances containing multiple labels (i.e. multi-labels), which are ubiquitous in describing complex concepts of instances. In this article, we formulate a new multi-label network embedding (MLNE) problem to learn feature representation for networked multi-label instances. We argue that the key to MLNE learning is to aggregate node topology structures, node content, and multi-label correlations. We propose a two-layer network embedding framework to couple information for effective learning. To capture higher order label correlations, we use labels to form a high-level label-label network over a low-level node-node network, in which the label network interacts with the node network through multi-labeling relations. The low-level node-node network can be enhanced by latent label-specific features from high-level label network with well-captured high-order correlations between labels. To enable the multi-label informed network embedding, we force both node and label representations being optimized under the same low-dimensional latent space by a unified training objective. Experiments on real-world data sets demonstrate that MLNE achieves better performance compared with methods with or without considering label information.