Methods, systems, and computer program products for constraints-based refactoring of monolith applications through attributed graph embeddings are provided herein. A computer-implemented method includes performing an analysis of source code of a monolith application to identify structural features and behavioral features; generating a graph structure representing the monolith application based on the identified structural features and the identified behavioral features, wherein the graph structure comprises: a plurality of nodes, each node corresponding to one of a plurality of software modules of the monolith application, and a plurality of edges between the plurality nodes, each edge representing a relationship of the corresponding nodes; automatically identifying constraints associated with the plurality of nodes in the graph structure based on the analysis of the source code; clustering the nodes using a convolutional neural network based the constraints; and outputting candidate microservices corresponding to respective ones of the clusters for refactoring the monolith application.