PSBR-GNN: Locally Edge-Private Graph Neural Networks via Aggregation-Preserving Graph Reconstruction

Project Basic Information

• Original Author/Maintainer: hhjuser
• Source Platform: GitHub
• Original Title: PSBR-GNN: Locally Edge-Private Graph Neural Networks via Aggregation-Preserving Graph Reconstruction
• Release Time: 2026-06-11
• Project Link: https://github.com/hhjuser/PSBR-GNN

Core Insights

PSBR-GNN is a new GNN method for graph edge privacy protection. It achieves local differential privacy via aggregation-preserving graph reconstruction, significantly reducing model performance loss under strong privacy guarantees. It is applicable to distributed sensitive data scenarios such as federated learning and privacy-preserving recommendation systems.

Graph Neural Networks (GNNs) are widely used in social networks, recommendation systems, bioinformatics, and other fields. However, training requires complete graph structures, and edge information often contains sensitive data (e.g., social relationships, transaction records). Traditional privacy-preserving methods face three major challenges:

1. Trade-off between edge privacy and utility: Direct noise addition severely affects GNN aggregation operations
2. Centralized limitations: Models relying on trusted servers are not suitable for distributed scenarios
3. Structural sensitivity: Topological structures themselves are prone to leaking sensitive relationships

The core insight of PSBR-GNN is to balance privacy and utility by reconstructing an aggregation-equivalent alternative graph structure:

Aggregation-Preserving Graph Reconstruction

1. Edge privacy localization: Nodes process adjacent edges locally without exposing original connections
2. Bipartite graph reconstruction: Convert the original graph into a privacy-protected bipartite graph
3. Aggregation equivalence: Ensure the message-passing aggregation results of the reconstructed graph are similar to those of the original graph

Local Differential Privacy Mechanism

• Nodes apply privacy mechanisms independently
• No trusted third party required
• Attackers cannot infer original edge relationships from privatized outputs

Core Modules

• Privacy perturbation mechanisms (random response/Laplace mechanism)
• Bipartite graph construction and reconstruction algorithms
• GNN layers adapted for private graphs

Baseline Comparison

Supports comparison with standard GNNs, edge-level DP baselines, and other privacy methods

Datasets

Includes Cora/Citeseer/Pubmed citation networks, social networks, and sensitive graph data

PSBR-GNN improves the "utility cliff" problem of private GNNs:

Method Type	Privacy Guarantee	Typical Accuracy Loss	Application Scenario
Unprotected GNN	None	0%	Non-sensitive data
Centralized Edge DP	Medium	15-30%	Trusted server scenarios
Traditional Local Edge DP	Strong	40-60%	Distributed scenarios
PSBR-GNN	Strong	5-15%	Distributed sensitive data

1. Federated Graph Learning: Cross-institution medical collaboration to protect patient relationship graph privacy
2. Privacy-Preserving Recommendation Systems: Social platforms can train recommendation models without exposing friend relationships
3. Financial Risk Control Collaboration: Banks jointly detect money laundering networks without sharing counterparty transaction information

• Large-scale graph efficiency: Reconstruction overhead for graphs with billions of edges may become a bottleneck
• Dynamic graph support: Currently only for static graphs; privacy protection for temporal graphs remains to be solved
• Attack robustness: Need to verify defense capabilities against complex structural attacks (e.g., graph reconstruction attacks)

PSBR-GNN is an important advancement in the field of graph privacy protection, proving that graph structure reconstruction can balance strong privacy and model utility. Value for AI practitioners:

1. Deployable solution: Strict local DP with no need for trusted third parties
2. Open-source implementation: Complete codebase for reproduction and extension
3. Benchmark comparison: Systematic comparisons help understand technical positioning As regulations like GDPR/CCPA tighten, such privacy-preserving technologies will become key components of trustworthy AI.