  Graph neural networks (GNNs) are susceptible to privacy inference attacks
(PIAs), given their ability to learn joint representation from features and
edges among nodes in graph data. To prevent privacy leakages in GNNs, we
propose a novel heterogeneous randomized response (HeteroRR) mechanism to
protect nodes' features and edges against PIAs under differential privacy (DP)
guarantees without an undue cost of data and model utility in training GNNs.
Our idea is to balance the importance and sensitivity of nodes' features and
edges in redistributing the privacy budgets since some features and edges are
more sensitive or important to the model utility than others. As a result, we
derive significantly better randomization probabilities and tighter error
bounds at both levels of nodes' features and edges departing from existing
approaches, thus enabling us to maintain high data utility for training GNNs.
An extensive theoretical and empirical analysis using benchmark datasets shows
that HeteroRR significantly outperforms various baselines in terms of model
utility under rigorous privacy protection for both nodes' features and edges.
That enables us to defend PIAs in DP-preserving GNNs effectively.
