Title: Learning Privacy-Preserving Graph Embeddings Against Sensitive Attributes Inference. Abstract: We focus on preserving the privacy of some sensitive attributes associated with certain private nodes on a graph when releasing graph data. Notably, deleting the sensitive attributes from the graph data cannot resist adversarial attacks because an adversary can still leverage the graph structure information and the non-sensitive node features to predict the sensitive attributes. We propose a framework to learn graph embeddings insensitive to the changes of certain specified sensitive attributes while maximally preserving the graph structure information and non-sensitive node features for downstream tasks. The key ingredient of our framework is a novel conditional variational graph autoencoder (CVGAE), which captures the relationship between the learned embeddings and the sensitive attributes. This allows us to quantify the privacy loss that can be used for penalizing privacy leakage when learning graph embeddings without adversarial training.