The generation of novel structured data, such as graphs, with desired properties is a critical task in fields like drug discovery and material design. Graph Variational Autoencoders (GraphVAEs) offer a promising solution; however, their performance is often limited by suboptimal graph reconstruction. To address this limitation, we propose a novel framework that uses an efficient primal-dual graph matching algorithm to significantly enhance the reconstruction capabilities of GraphVAEs. By accurately aligning generated graphs with their original input graphs, our method enables the generation of valid structured data. We evaluate our approach on a benchmark molecular dataset, demonstrating its performance compared to existing graph-based generative models. Our experiments show a significant reduction in reconstruction loss and substantial improvement in training efficiency. Beyond molecular generation, the underlying metric labeling problem addressed by our graph matching algorithm has far-reaching implications for various domains, including semi-supervised learning, point cloud semantic segmentation, and the prediction of individual relations in social networks, image, and video processing. This work underscores the critical role of effective graph matching in advancing GraphVAE performance and paves the way for new possibilities in molecular generation and beyond.