# CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference

arXiv: https://arxiv.org/abs/2209.11904 · HTML: https://mlsanity.com/paper/2209.11904/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 24 Sep 2022.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Mask R-CNN](https://mlsanity.com/paper/1703.06870/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Deep High-Resolution Representation Learning for Human Pose Estimation](https://mlsanity.com/paper/1902.09212/) (2019)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Realtime Multi-Person 2D Pose Estimation using Part Affinity Fields](https://mlsanity.com/paper/1611.08050/) (2016)
- [NTU RGB+D: A Large Scale Dataset for 3D Human Activity Analysis](https://mlsanity.com/paper/1604.02808/) (2016)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Gazelle: A Low Latency Framework for Secure Neural Network Inference](https://mlsanity.com/paper/1801.05507/) (2018)
- [Low Latency Privacy Preserving Inference](https://mlsanity.com/paper/1812.10659/) (2018)
- [DeepReDuce: ReLU Reduction for Fast Private Inference](https://mlsanity.com/paper/2103.01396/) (2021)
- [DeepSecure: Scalable Provably-Secure Deep Learning](https://mlsanity.com/paper/1705.08963/) (2017)
- [Skeleton-Based Action Recognition with Spatial Reasoning and Temporal Stack Learning](https://mlsanity.com/paper/1805.02335/) (2018)
- [CryptoNAS: Private Inference on a ReLU Budget](https://mlsanity.com/paper/2006.08733/) (2020)
- [SHE: A Fast and Accurate Deep Neural Network for Encrypted Data](https://mlsanity.com/paper/1906.00148/) (2019)
- [Joint Interaction and Trajectory Prediction for Autonomous Driving using Graph Neural Networks](https://mlsanity.com/paper/1912.07882/) (2019)
- [Exploiting Data Sparsity in Secure Cross-Platform Social Recommendation](https://mlsanity.com/paper/2202.07253/) (2022)
- [HEAAN Demystified: Accelerating Fully Homomorphic Encryption Through Architecture-centric Analysis and Optimization](https://mlsanity.com/paper/2003.04510/) (2020)
- [Volley Revolver: A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)](https://mlsanity.com/paper/2201.12577/) (2022)

## Built on by (most cited first, 10 of 10)

- [LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference](https://mlsanity.com/paper/2309.14331/) (2023)
- [AEGIS: Scaling Long-Sequence Homomorphic Encrypted Transformer Inference via Hybrid Parallelism on Multi-GPU Systems](https://mlsanity.com/paper/2604.03425/) (2026)
- [Privacy-Preserving Graph-Based Machine Learning with Fully Homomorphic Encryption for Collaborative Anti-Money Laundering](https://mlsanity.com/paper/2411.02926/) (2024)
- [DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning](https://mlsanity.com/paper/2507.05649/) (2025)
- [Efficient Privacy-Preserving KAN Inference Using Homomorphic Encryption](https://mlsanity.com/paper/2409.07751/) (2024)
- [Panther: A Cost-Effective Privacy-Preserving Framework for GNN Training and Inference Services in Cloud Environments](https://mlsanity.com/paper/2511.01654/) (2025)
- [PrivGNN: High-Performance Secure Inference for Cryptographic Graph Neural Networks](https://mlsanity.com/paper/2511.02185/) (2025)
- [FEnc2: Unifying Data Packing for Efficient Private Inference via Convolution and Architecture-Aware Fragment Encoding](https://mlsanity.com/paper/2606.16359/) (2026)
- [TGHE: Template-based Graph Homomorphic Encryption for Privacy-Preserving GNN Inference in Edge-Cloud Systems](https://mlsanity.com/paper/2606.26664/) (2026)
- [OptiPrime: Optimizing Private Inference through Protocol-Hardware Co-design](https://mlsanity.com/paper/2609.16898/) (2026)

## Abstract (arXiv)

Recently cloud-based graph convolutional network (GCN) has demonstrated great success and potential in many privacy-sensitive applications such as personal healthcare and financial systems. Despite its high inference accuracy and performance on cloud, maintaining data privacy in GCN inference, which is of paramount importance to these practical applications, remains largely unexplored. In this paper, we take an initial attempt towards this and develop textitCryptoGCN--a homomorphic encryption (HE) based GCN inference framework. A key to the success of our approach is to reduce the tremendous computational overhead for HE operations, which can be orders of magnitude higher than its counterparts in the plaintext space. To this end, we develop an approach that can effectively take advantage of the sparsity of matrix operations in GCN inference to significantly reduce the computational overhead. Specifically, we propose a novel AMA data formatting method and associated spatial convolution methods, which can exploit the complex graph structure and perform efficient matrix-matrix multiplication in HE computation and thus greatly reduce the HE operations. We also develop a co-optimization framework that can explore the trade offs among the accuracy, security level, and computational overhead by judicious pruning and polynomial approximation of activation module in GCNs. Based on the NTU-XVIEW skeleton joint dataset, i.e., the largest dataset evaluated homomorphically by far as we are aware of, our experimental results demonstrate that textitCryptoGCN outperforms state-of-the-art solutions in terms of the latency and number of homomorphic operations, i.e., achieving as much as a 3.10× speedup on latency and reduces the total Homomorphic Operation Count by 77.4% with a small accuracy loss of 1-1.5%.