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.

提出了一种基于自适应差分隐私的节点重要性粒度隐私保护图神经网络算法 NAP-GNN，通过拓扑学方法估计未知节点重要性，并通过自适应私有聚合方法对邻域聚合进行扰动，实现了在多层卷积中进行节点级任务的图学习算法的隐私保障。理论分析和实验证明 NAP-GNN 在隐私和准确性之间取得了更好的平衡。