A method for protecting sensitive data from being exposed in graph embedding vectors. In some embodiments, a method may include generating first graph embedding vectors from an original graph and generating a proxy graph from the first graph embedding vectors. The proxy graph may include a plurality of proxy nodes and proxy edges connecting the proxy nodes. The proxy nodes may include one or more attributes of the original nodes that are included in the first graph embedding vectors. Second graph embedding vectors may then be generated by encoding the proxy graph and a reconstructed graph may be generated from the second graph embedding vectors. Finally, the reconstructed graph may be compared to the original graph and if a threshold level of similarity is met, a security action may be performed to protect sensitive data from being exposed.