Locally Private Graph Neural Networks

Sina Sajadmanesh; Daniel Gatica-Perez

Source-linked AI summary

Locally Private Graph Neural Networks

Sina Sajadmanesh, Daniel Gatica-Perez

arXiv:2006.05535v9Jun 9, 2020cs.LGcs.CRstat.ML

TL;DR

The paper addresses how a central server can train GNNs from sensitive node features and labels without directly collecting them, despite the relational communication challenges of graphs. It proposes LPGNN, combining local differential privacy with KProp denoising and Drop for noisy labels. Across real-world datasets, the method remains robust to injected privacy noise and achieves a useful accuracy-privacy trade-off, while leaving graph-topology privacy for future work.

Problem
GNN training may require sensitive node features and labels, while graph message passing makes privacy-preserving collaboration difficult because connected nodes exchange representations repeatedly.
Method
LPGNN uses LDP mechanisms to privatize node data, KProp to denoise multi-hop aggregates, and Drop to train with perturbed labels across GNN architectures.
Results
LPGNN is robust to injected LDP noise and performs comparably to non-private baselines, with less than 10% accuracy loss on three datasets at 𝜖x = 0.01 and 𝜖y = 1.
Takeaways & Limitations
The framework supports private-feature and private-label GNN learning without requiring clean raw data and maintains a useful accuracy-privacy trade-off.
Takeaways & Limitations
The current method protects node features and labels but leaves graph topology unprotected, while stronger methods for learning with differentially private labels remain future work.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have demonstrated superior performance in learning node representations for various graph inference tasks. However, learning over graph data can raise privacy concerns when nodes represent people or human-related variables that involve sensitive or personal information. While numerous techniques have been proposed for privacy-preserving deep learning over non-relational data, there is less work addressing the privacy issues pertained to applying deep learning algorithms on graphs. In this paper, we study the problem of node data privacy, where graph nodes have potentially sensitive data that is kept private, but they could be beneficial for a central server for training a GNN over the graph. To address this problem, we develop a privacy-preserving, architecture-agnostic GNN learning algorithm with formal privacy guarantees based on Local Differential Privacy (LDP). Specifically, we propose an LDP encoder and an unbiased rectifier, by which the server can communicate with the graph nodes to privately collect their data and approximate the GNN's first layer. To further reduce the effect of the injected noise, we propose to prepend a simple graph convolution layer, called KProp, which is based on the multi-hop aggregation of the nodes' features acting as a denoising mechanism. Finally, we propose a robust training framework, in which we benefit from KProp's denoising capability to increase the accuracy of inference in the presence of noisy labels. Extensive experiments conducted over real-world datasets demonstrate that our method can maintain a satisfying level of accuracy with low privacy loss.

1 INTRODUCTION

GNNs can benefit from sensitive node data, but graph structure and message passing make private-data training difficult. LPGNN addresses this with LDP mechanisms, denoising, and robust learning for noisy labels.

Motivation: GNNs achieve strong results across graph tasks, but graphs involving people may contain private personal information.Examples include social connections, profiles, likes, and comments.
Problem and motivation: The node data privacy problem keeps node features and possibly labels private while exposing graph topology to a central server.The server seeks to use private node data to train a GNN without directly collecting it.
Challenges: Relational message passing makes conventional collaborative learning costly because adjacent nodes exchange representations repeatedly during training.This communication burden is substantially greater than in conventional deep neural networks, where nodes communicate independently with the server.
Contributions: LPGNN provides architecture-agnostic GNN learning with formal LDP guarantees when node features, labels, or both are private.The framework is designed for training over graph data without requiring private values to be directly disclosed.
Contributions: The multi-bit mechanism perturbs node features for low-communication collection, while graph convolution estimates the GNN’s first layer and averages injected noise.For private labels, generalized randomized response is paired with Drop, which uses KProp’s denoising capability without clean raw data.
Results: Experiments on real-world datasets show robustness to LDP noise and a useful accuracy-privacy trade-off with noisy features and labels.The paper also derives formal privacy guarantees and error bounds for the proposed algorithms.

2 PRELIMINARIES

The paper formalizes private node features and labels in a graph whose topology is visible to the server, then reviews GNN message passing and LDP as the technical foundations. LDP privatizes data locally before aggregation, trading utility for privacy through the budget parameter 𝜖.

Problem definition: The graph contains labeled and unlabeled nodes, with feature matrix X and label matrix Y private to nodes while the server observes V and E.The central question is how to train a GNN without letting private data leave the nodes.
Graph Neural Networks: A GNN generates node embeddings by aggregating neighboring representations and applying a trainable nonlinear transformation across stacked graph convolution layers.The initial embedding is each node’s feature vector, and the final layer predicts labels through a softmax output.
Local Differential Privacy: LDP lets data holders perturb private values locally before sending them to an aggregator that estimates the target query from the perturbed outputs.The framework is intended to prevent an untrusted aggregator from inferring an individual’s original value.
Local Differential Privacy: The privacy budget 𝜖 controls the utility-privacy trade-off: smaller 𝜖 strengthens privacy but lowers utility, whereas larger 𝜖 does the opposite.The mechanism must assign similar output probabilities to different private inputs.

3 PROPOSED METHOD

The proposed framework privately collects node features and labels under LDP, then uses KProp and Drop to reduce the effects of feature and label noise during architecture-agnostic GNN training.

3.1 Collection of node features: The multi-bit mechanism privately perturbs multidimensional node features with an encoder and server-side rectifier designed for communication efficiency.The encoder satisfies ε-local differential privacy, while the rectifier produces an unbiased perturbed vector.
3.2 Approximation of graph convolution: KProp prepends a graph convolution layer that expands each node’s aggregation neighborhood to reduce estimation noise, especially for low-degree nodes.Its denoising benefit trades off against possible over-smoothing when the neighborhood expands too far.
3.3 Learning with private labels: Private labels are collected with generalized randomized response, then KProp estimates label frequencies over expanded neighborhoods for label correction.Drop uses these propagated estimates without requiring clean features or labels for training or validation.
3.3 Learning with private labels: Drop avoids fitting propagated labels directly by using a forward-correction loss and a noisy-label accuracy threshold to detect overfitting.The threshold is the expected accuracy upper bound for a perfect classifier predicting randomized-response labels, Acc* = e^ε/(e^ε+c−1).
3 PROPOSED METHOD: The complete training procedure satisfies (ε_x + ε_y)-local differential privacy, and its predictions retain LDP through post-processing.The framework collects perturbed data once and then trains with the stored outputs.

4 EXPERIMENTS

Experiments evaluate LPGNN across real-world graphs, privacy budgets, GNN backbones, perturbation mechanisms, and feature alternatives. Results show robustness to local privacy noise, with KProp and Drop providing larger gains under more severe feature or label noise.

Experimental settings: Experiments use citation and social networks, with node splits of 50/25/25% for training, validation, and testing.Features are perturbed across all splits, while labels are perturbed only for training and validation.
Privacy-utility performance: LPGNN remains within 10% accuracy of non-private baselines on three datasets at feature budget 0.01 and label budget 1.On Cora, GCN and GraphSAGE reach about 80% at feature budget 0.1 and label budget 2, only 6% below the non-private method.
Backbone comparison: GAT has a weaker accuracy-privacy trade-off than GCN and GraphSAGE when feature budget ε_x≤1, but achieves comparable results for ε_x≥1.The paper attributes this sensitivity to GAT's use of node features for attention coefficients at every layer.
LDP mechanisms: The multi-bit mechanism outperforms competing LDP mechanisms by over 8%, 2%, 7%, and 12% on Cora, Pubmed, Facebook, and LastFM at feature budget 0.01.It requires two bits per feature, compared with typically 32 bits per feature for Gaussian outputs.
Feature analysis: Private node features outperform random alternatives because their aggregated values retain information about neighborhoods useful for distinguishing nodes.The comparison includes all-one vectors, degree one-hot encodings, and randomly initialized features.
KProp analysis: At feature budget 0.01, KProp improves accuracy by around 6% and 10% on Facebook and LastFM, versus over 20% on Cora and Pubmed.Lower-degree citation networks benefit more from additional propagation steps, whereas accuracy on higher-degree social networks falls after K_x=4.
KProp analysis: At label budget 0.5, label KProp increases accuracy by over 20% on LastFM, at most 5% on Facebook, and up to 30% on Cora and Pubmed.The gain depends on both graph degree and the number of classes, which affects randomized-response noise.
Noisy-label training: Drop improves LPGNN accuracy over forward correction by over 24%, 31%, 6%, and 25% on Cora, Pubmed, Facebook, and LastFM at label budget 0.5.The advantage shrinks as the label budget increases and labels become less noisy.

5 RELATED WORK

Prior work covers GNNs, LDP, privacy attacks, and privacy-preserving graph models, but existing approaches differ from LPGNN in their target, trust assumptions, or privacy guarantees.

GNN research includes models such as GCN, GAT, GraphSAGE, and GIN for graph representation learning.
LDP supports privacy-preserving data collection without requiring a trusted aggregator.
Privacy attacks on GNNs include link stealing and leakage from graph embeddings trained on sensitive data.
Existing privacy-preserving graph methods target classic embeddings, adversarial defenses, or settings where the server accesses private data.
Federated and split-learning approaches rely on trusted aggregation or address different distributed graph settings than node data privacy.

6 CONCLUSION

The paper concludes that LPGNN combines local privacy mechanisms, KProp, and Drop to train GNNs from private node data while maintaining an appropriate privacy-utility trade-off. It identifies unprotected topology and stronger label-denoising methods as important future directions.

LPGNN privately collects node features with multi-bit encoding and estimates the first GNN convolution layer from noisy features.
KProp reduces estimation error by aggregating features from higher-order neighbors before the backbone GNN.
Drop uses KProp for denoising perturbed labels during training.
Experiments on real-world node-classification datasets maintain an appropriate privacy-utility trade-off.
The current method protects node features and labels but leaves graph topology unprotected.

A.1 Theorem 3.1

Theorem 3.1 establishes the privacy bound for the multi-bit encoder by comparing output probabilities across any two input feature vectors.

The proof compares the multi-bit encoder's output probabilities for arbitrary input features x1 and x2.
For each dimension, the encoder's output probabilities depend on the feature value through the per-dimension privacy budget.
The proof aggregates the per-dimension bound across d dimensions and uses exactly m non-zero output features.

A.2 Proposition 3.2

The appendix proves Proposition 3.2 through Lemma A.1, establishing the expectation and variance properties needed for the multi-bit mechanism's estimator.

Lemma A.1 states the relevant property of Algorithm 1's output for every feature dimension.
The proof derives the estimator's expectation from the lemma's stated relations.
The proof separately derives the variance and combines it with the preceding result.
The final argument applies these results to show E equals x_v,i for every node v and dimension i.

A.3 Proposition 3.3

The proof applies Lemma A.1 to establish the result for Proposition 3.3.

Lemma A.1 is applied as the proof step for Proposition 3.3.

A.4 Proposition 3.4

The proof selects the multi-bit rectifier parameter m by minimizing an upper bound on its variance. The optimization reduces to a convex scalar function, yielding an unconstrained optimum that is then adjusted to the valid integer range.

The optimal m minimizes an upper bound on the rectifier variance because the exact variance depends on private features unknown to the server.
The variance upper bound is maximized at x = (α + β) / 2, which enables reduction to a scalar optimization.
The optimization uses f(z) = z·coth^2(z/2), a convex function with one minimum on (0, ∞).
The unconstrained optimum is z★ ≃ 2.18, giving m★ = ε / 2.18 before enforcing the integer constraint.
The parameter m must be an integer between 1 and d, so the unconstrained solution is adjusted to satisfy those bounds.

A.5 Corollary 3.5

The proof establishes the result by rewriting the aggregation expression and using linearity of expectation together with Proposition 3.2.

The proof considers the target relation for an arbitrary node v.
Linearity of the Aggregate operation allows the expectation to move inside the aggregation.
The final step invokes Proposition 3.2 to complete the argument.

A.6 Proposition 3.6

The proof derives the proposition's bound using the encoder output, the mean aggregator, asymptotic analysis, Bernstein's inequality, and a union bound. It then establishes the algorithm's node-level privacy through composition of its two mechanisms.

The proof derives λ from the multi-bit encoder output and Proposition 3.2 for each node and feature dimension.
The mean aggregator supplies the comparison expression used in the subsequent concentration analysis.
Bernstein's inequality, asymptotic analysis as ε → 0, and the union bound are used to obtain the required probabilistic bound.
Algorithm 3 satisfies (ε_x + ε_y)-LDP per node because its encoder and randomized response are each invoked once, with privacy preserved under composition and post-processing.