ComputingComputer ScienceData MiningMachine LearningPrivacy EngineeringData ProtectionDifferential PrivacyGraph-based LearningPrivacy-preserving AnalyticsDifferentially Private Machine LearningGraph Neural NetworksPagerankPrivacyPrivacy-preserving Machine LearningPrivacy-utility Trade-offPrivacy-utility TradeoffUtility-privacy Tradeoff
Graph Neural Networks (GNNs) have achieved great success in learning with graph-structured data. Privacy concerns have also been raised for the trained models which could expose the sensitive information of graphs including both node features and the structure information. In this paper, we aim to achieve node-level differential privacy (DP) for training GNNs so that a node and its edges are protected. Node DP is inherently difficult for GNNs because all direct and multi-hop neighbors participate in the calculation of gradients for each node via layer-wise message passing and there is no bound on how many direct and multi-hop neighbors a node can have, so existing DP methods will result in high privacy cost or poor utility due to high node sensitivity. We propose a D ecoupled GNN with Differentially P rivate A pproximate Personalized PageR ank (DPAR) for training GNNs with an enhanced privacy-utility tradeoff. The key idea is to decouple the feature projection and message passing via a DP PageRank algorithm which learns the structure information and uses the top-K neighbors determined by the PageRank for feature aggregation. By capturing the most important neighbors for each node and avoiding the layer-wise message passing, it bounds the node sensitivity and achieves improved privacy-utility tradeoff compared to layer-wise perturbation based methods. We theoretically analyze the node DP guarantee for the two processes combined together and empirically demonstrate better utilities of DPAR with the same level of node DP compared with state-of-the-art methods.
28
Deep Learning with Differential Privacy
Martı́n Abadi, Andy Chu, Ian Goodfellow et al. · 2016 · 5.9K citations · Full text
Local Graph Partitioning using PageRank Vectors
Reid Andersen, Fan Chung, Kevin Lang · 2006 · 985 citations
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim et al. · SIAM Journal on Computing · 2011 · 900 citations