Random walks are at the heart of many existing network embedding methods. However, such methods have many limitations that arise from the use of traditional random walks, e.g., the embeddings resulting from these methods primarily capture proximity (communities) among the vertices as opposed to structural similarity (roles). In this work, we introduce the Role2Vec framework which uses the flexible notion of attributed random walks, and serves as a basis for generalizing existing methods such as DeepWalk, node2vec, and many others that leverage random walks. Our proposed framework enables these methods to be more widely applicable by learning functions that capture the behavioral roles of the nodes. We show that our proposed framework is effective with an average AUC improvement of 16.55% while requiring on average 853x less space than existing methods.