Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networks

• URL: http://arxiv.org/abs/2605.26243v1
• Date: Mon, 25 May 2026 18:10:20 GMT
• Title: Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networks
• Abstract summary: Graph neural networks (GNNs) achieve strong performance on relational data, but real-world graphs are often distributed across organizations that cannot share raw data due to privacy and policy constraints.<n>We propose CE-FedGNN, a communication-efficient and privacy-preserving federated GNN framework for learning over such coupled graphs.<n> Experiments on synthetic interbank anti-money laundering benchmarks and citation networks demonstrate that CE-FedGNN achieves strong performance while significantly reducing communication and maintaining robustness under privacy-preserving noise.
• Score: 18.008132027250777
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) achieve strong performance on relational data, but real-world graphs are often distributed across organizations that cannot share raw data due to privacy and policy constraints. Existing federated GNN methods either ignore cross-client links, leading to degraded accuracy, or require frequent embedding exchanges, incurring substantial communication and privacy costs. We propose CE-FedGNN, a communication-efficient and privacy-preserving federated GNN framework for learning over such coupled graphs. Our approach avoids sharing raw data or per-round embeddings by infrequently exchanging aggregated node representations. To handle cross-client dependency and staleness, we introduce a moving-average estimator that continuously tracks node representations and enables their stable reuse across rounds. To provide formal privacy guarantees for the released representations, we adopt the metric differential privacy (metric-DP) framework, which measures privacy with respect to distances in the learned embedding space rather than worst-case input perturbations. This yields meaningful guarantees at noise levels where standard differential privacy becomes overly conservative. We establish convergence to a stationary point at a rate of $O(1/\sqrt{T})$ with $O(T^{3/4})$ communication complexity. In addition, we derive $(\varepsilon,δ)$-metric-DP guarantees via Rényi differential privacy composition under a public-cohort threat model. Experiments on synthetic interbank anti-money laundering benchmarks and citation networks demonstrate that CE-FedGNN achieves strong performance while significantly reducing communication and maintaining robustness under privacy-preserving noise.

Related papers

• Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions [89.52532304099522]
  Federated Learning (FL) enables clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy.<n> gradients and model updates can still leak sensitive information, while malicious servers may mount adversarial attacks such as Byzantine manipulation.<n>These vulnerabilities highlight the need to address differential privacy (DP) and Byzantine robustness within a unified framework.<n>We propose Byz-Clip21-SGD2M, a new algorithm that integrates robust aggregation with double momentum and carefully designed clipping.
  arXiv  Detail & Related papers  (2026-03-24T17:39:09Z)
• A Secure and Private Distributed Bayesian Federated Learning Design [56.92336577799572]
  Distributed Federated Learning (DFL) enables decentralized model training across large-scale systems without a central parameter server.<n>DFL faces three critical challenges: privacy leakage from honest-but-curious neighbors, slow convergence due to the lack of central coordination, and vulnerability to Byzantine adversaries aiming to degrade model accuracy.<n>We propose a novel DFL framework that integrates Byzantine robustness, privacy preservation, and convergence acceleration.
  arXiv  Detail & Related papers  (2026-02-23T16:12:02Z)
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation [79.64626707978418]
  We propose using link local differential privacy over decentralized nodes to train graph neural networks. Our approach spends the privacy budget separately on links and degrees of the graph for the server to better denoise the graph topology. Our approach outperforms existing methods in terms of accuracy under varying privacy budgets.
  arXiv  Detail & Related papers  (2023-09-06T17:53:31Z)
• Differentially Private Graph Neural Network with Importance-Grained Noise Adaption [6.319864669924721]
  Graph Neural Networks (GNNs) with differential privacy have been proposed to preserve graph privacy when nodes represent personal and sensitive information. 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-grained privacy-preserving GNN algorithm with privacy guarantees based on adaptive differential privacy to safeguard node information.
  arXiv  Detail & Related papers  (2023-08-09T13:18:41Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Heterogeneous Randomized Response for Differential Privacy in Graph Neural Networks [18.4005860362025]
  Graph neural networks (GNNs) are susceptible to privacy inference attacks (PIAs) We propose a novel mechanism to protect nodes' features and edges against PIAs under differential privacy (DP) guarantees. We derive significantly better randomization probabilities and tighter error bounds at both levels of nodes' features and edges.
  arXiv  Detail & Related papers  (2022-11-10T18:52:46Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging [20.39986955578245]
  We introduce pairwise network differential privacy, a relaxation of Local Differential Privacy (LDP) We derive a differentially private decentralized optimization algorithm that alternates between local gradient descent steps and gossip averaging. Our results show that our algorithms amplify privacy guarantees as a function of the distance between nodes in the graph.
  arXiv  Detail & Related papers  (2022-06-10T13:32:35Z)
• GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation [19.247325210343035]
  Graph Neural Networks (GNNs) are powerful models designed for graph data that learn node representation. Recent studies have shown that GNNs can raise significant privacy concerns when graph data contain sensitive information. We propose GAP, a novel differentially private GNN that safeguards privacy of nodes and edges.
  arXiv  Detail & Related papers  (2022-03-02T08:58:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.