PrivGNN: High-Performance Secure Inference for Cryptographic Graph Neural Networks

Fuyi Wang, Zekai Chen, Mingyuan Fan, Jianying Zhou, Lei Pan, Leo Yu Zhang

Abstract

PrivGNN is a novel secure two-party computation (2PC) framework optimized for privacy-preserving inference on Graph Neural Networks (GNNs). By integrating additive and function secret sharing within an offline-online paradigm, PrivGNN significantly mitigates the communication and computational overhead typically associated with non-linear operations in secure computation. Experimental results demonstrate that PrivGNN achieves up to 4.7x faster online inference compared to state-of-the-art methods while maintaining high accuracy across various graph and image datasets.

Introduction

Graph Neural Networks (GNNs) have become essential for analyzing graph-structured data, ranging from molecular structures in drug discovery to social network connections. However, the sensitivity of this data often prevents organizations from leveraging cloud-based Machine Learning as a Service (MLaaS). Existing Secure Inference (SI) protocols, primarily designed for Convolutional Neural Networks (CNNs), struggle with GNNs due to structural leakage and the high computational cost of non-linear activations. PrivGNN addresses these challenges, delivering secure cloud-based graph inference up to 4.7x faster than existing methods with negligible accuracy loss.

Challenges in Secure GNN Inference

Applying standard cryptographic primitives to GNNs presents two major hurdles:

  1. Structural Leakage: Many existing methods fail to fully protect the relational structure of the graph, potentially leaking metadata such as the maximum node degree.
  2. Computational Bottlenecks: GNNs rely heavily on non-linear activation functions. Implementing these via Homomorphic Encryption or Garbled Circuits is computationally intensive and requires significant communication rounds, making them unscalable for large-scale graphs.

The PrivGNN Framework

PrivGNN operates on a client-server model under a semi-honest assumption, where parties follow the protocol but may attempt to learn private information. The framework utilizes an offline-online paradigm to push heavy cryptographic computations to a data-independent offline phase, ensuring a fast online phase.

Overview of the PrivGNN secure inference protocol between a client and a server.

Key Technical Innovations

  • Hybrid Secret Sharing: PrivGNN combines Additive Secret Sharing (AddSS) for linear operations with Function Secret Sharing (FuncSS) for non-linear operations.
  • Secure Matrix Multiplication (SMatMul): This protocol is optimized to reduce auxiliary randomness, streamlining the offline generation of Beaver triples.
  • Secure DReLU (SDReLU): A novel protocol for ReLU and MaxPool layers that uses FuncSS to evaluate comparisons (e.g., $x > 0$) in a single round of online communication, bypassing the overhead of Garbled Circuits.
  • Secure Piecewise Polynomials (SPiePol): To handle Sigmoid and Tanh activations, PrivGNN approximates these functions using 12-piece quadratic polynomials, which are evaluated securely via SDReLU indicators.

Experimental Evaluation

The authors benchmarked PrivGNN using standard image datasets (MNIST, CIFAR-10/100) for CNN architectures and the QM9 dataset (134,000 organic molecules) for Message Passing Neural Networks (MPNNs).

Key Results

  • Performance Gains: PrivGNN achieves 1.5x to 1.7x speedups for linear layers and 2x to 15x speedups for non-linear layers compared to state-of-the-art solutions like Delphi and CrypTFlow2. Overall, online secure predictions are 1.3x to 4.7x faster.
  • High Accuracy: Secure approximations have minimal impact. On the QM9 task, PrivGNN achieved 96.42% accuracy compared to 97.93% in plaintext. On MNIST, the accuracy drop was only 0.02%.
  • Reduced Communication: The online communication cost for the SQuaPol protocol is 2x to 4x lower than competing frameworks.

Limitations and Future Work

While PrivGNN offers significant online speedups, it involves a minor accuracy trade-off due to fixed-point arithmetic truncation and polynomial approximations. Additionally, the offline phase remains communication-intensive. Future research may focus on further optimizing the offline phase, extending the framework to handle malicious adversaries, and scaling to even larger, more complex graph datasets.

Summary updated

BibTeX
@inproceedings{wang2025privgnn,
  author = {Fuyi Wang and Zekai Chen and Mingyuan Fan and Jianying Zhou and Lei Pan and Leo Yu Zhang},
  title = {{PrivGNN: High-Performance Secure Inference for Cryptographic Graph Neural Networks}},
  booktitle = {FC},
  year = {2025},
  doi = {10.1007/978-3-032-07035-7\_21},
}
Figure