Title: Multi-Vector Embedding on Networks with Taxonomies. Abstract: Networks serve as efficient tools to describe close relationships among nodes. Taxonomies consist of labels organized into hierarchical structures and are often employed to describe rich attributes of the network nodes. Existing methods that co-embed nodes and labels in a low-dimensional space all encounter an obstacle called under-fitting, which occurs when the vector of a node is obliged to fit all its labels and neighbor nodes. In this paper, we propose HIerarchical Multi-vector Embedding (HIME), which allows multiple vectors of a node to fit different sets of its labels in a Poincare ball, where the label hierarchy is well preserved. Experiments show that HIME has comprehensive advantages over existing network embedding methods in preserving both node-node and node-label relationships. 