  Graph Neural Networks (GNNs) with differential privacy have been proposed to
preserve graph privacy when nodes represent personal and sensitive information.
However, the existing methods ignore that nodes with different importance may
yield diverse privacy demands, which may lead to over-protect some nodes and
decrease model utility. In this paper, we study the problem of
importance-grained privacy, where nodes contain personal data that need to be
kept private but are critical for training a GNN. We propose NAP-GNN, a
node-importance-grained privacy-preserving GNN algorithm with privacy
guarantees based on adaptive differential privacy to safeguard node
information. First, we propose a Topology-based Node Importance Estimation
(TNIE) method to infer unknown node importance with neighborhood and centrality
awareness. Second, an adaptive private aggregation method is proposed to
perturb neighborhood aggregation from node-importance-grain. Third, we propose
to privately train a graph learning algorithm on perturbed aggregations in
adaptive residual connection mode over multi-layers convolution for node-wise
tasks. Theoretically analysis shows that NAP-GNN satisfies privacy guarantees.
Empirical experiments over real-world graph datasets show that NAP-GNN achieves
a better trade-off between privacy and accuracy.
