Detecting anomalies in graph-structured data is critical for identifying unusual patterns within complex systems, with applications spanning cybersecurity, fraud detection, and risk assessment. In this work, we present VQ-VGAE, a novel architecture that combines Vector Quantization (VQ) with the Variational Graph Auto-Encoder (VGAE) for unsupervised anomaly detection. By incorporating discrete latent variables, VQ-VGAE offers a new way to model intricate graph anomalies, which are often missed by traditional methods. The framework leverages the expressive power of Graph Convolutional Networks (GCNs) to learn graph structure while integrating the probabilistic approach of Variational Auto-Encoders (VAEs). Extensive experiments on both transactional and business process graph datasets reveal that VQ-VGAE consistently surpasses conventional Graph Auto-Encoder (GAE) and VGAE models, showing marked improvements in AUC-ROC and Average Precision (AP). Beyond performance gains, leveraging a discrete latent space facilitates interpretable anomaly representations, offering deeper insights into the nature of deviations within graphs. This interpretable approach to anomaly detection enhances our ability to understand and manage complex networks across diverse domains.