Graph representations based on embedding methods allow for easier analysis of the network structure and can be used for a variety of tasks, such as link prediction and node classification. These methods have been shown to be effective in a variety of settings and have become an important tool in the field of graph learning. These methods are easy to implement, and their predictions yield interpretable results. However, most graph embedding methods rely solely on graph structural information and do not consider node/edge attributes, limiting their applicability. In this paper, we propose graph-theoretic designs to incorporate node and edge attributes within the topology, enabling graph-embedding methods to seamlessly work on attributed graphs. To find ideal representation for a given attributed graph, we propose augmenting special subgraph structures within original network. We discuss the potential challenges of the proposed approach and prove some of its theoretical limitations. We test the efficacy of our approach by comparing state-of-the-art graph classification models on 15 standard bioinformatics datasets. We observe an encouraging improvement of up to 5% in classification accuracy on the augmented graphs compared to the results on the original graphs.