<p>Quantum Variational Graph Auto-Encoders (QVGAE) represent an integration of graph-based machine learning and quantum computing. In this work, we propose a first-of-its-kind quantum implementation of Variational Graph Auto-Encoders (VGAE). This approach employs a Quantum Encoder Circuit (QEC) as an encoder and an inner product decoder to process graph data. The QEC circuit is a quantum extension of the classical Graph Neural Network (GNN) framework, inspired by Quantum Graph Neural Network (QGNN), which embeds each graph node into Hilbert space via quantum operations and entanglement to enable message passing instead of traditionally updating vector embeddings. The limitation on the number of qubits and shots creates a bottleneck for quantum machine learning in handling real-world large graph data. To mitigate this, we proposed a graph processing approach involving graph clustering algorithms for partitioning the nodes of a graph into clusters and learning the representation of coalesced graphs using QGNNs. Experimental results show that our model outperforms baseline models in terms of AUC and AP scores; it performs 4.37% and 3.56% higher on Cora respectively, and 1.10% and 0.86% higher on Citeseer, when compared with the baseline VGAE on link prediction tasks. Experiments further reveal that QVGAE outperforms QGNN, respectively by 4.4% and 3.6% with respect to accuracy and AUC, thereby validating the effectiveness of variational inference in the quantum framework. All the experiments described in this research attempt were conducted using the SV1 quantum simulator available through the Amazon Braket environment.</p>