Research map / Graph learning / GNN architectures
FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FicGCN, a CKKS homomorphic-encryption framework for GCN inference that exploits graph sparsity via latency-aware packing, Sparse Intra-Ciphertext Aggregation, and region-based node reordering, reporting up to 4.10x speedup over prior designs.
Problem
Homomorphic-encryption GCN inference is slow because rotations and multiplications in aggregation (AX) and combination (XW) are costly, and the irregular sparsity of graph adjacency conflicts with CKKS SIMD packing, so existing designs gain limited speedup from sparsity.
Approach
Combines a latency-aware column packing that picks the number of columns per ciphertext, a Sparse Intra-Ciphertext Aggregation that builds neighbor ciphertexts via bit-decomposed cyclic rotations with masks, and a BFS-based region partition with greedy conflict-minimizing node placement (NOO) to reduce rotations in aggregation.
Key results
- FicGCN+NOO reduces Cora latency to 64.12s, a 21.6x speedup over Gazelle and about 2.01x over Penguin.
- On Corafull (19,793 nodes), FicGCN+NOO runs in 7733s, about 4.1x faster than CryptoGCN.
- NOO reduces Rot count by 66.4% on Cora and 66.6% on Citeseer relative to direct SpIntra-CA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FicGCN+NOO instead of Penguin | HE-GCN inference · Cora | latency: 128.82s -> 64.12s | Helped |
| Use FicGCN+NOO instead of Penguin | HE-GCN inference · Citeseer | latency: 142.90s -> 79.98s | Helped |
| Use FicGCN+NOO instead of CryptoGCN | HE-GCN inference · Corafull | latency: 31735s -> 7733s | Helped |
| Use FicGCN instead of CryptoGCN | HE-GCN inference · NTU | latency: 1731.08s -> 1373.82s | Helped |
| Add Aggregation Order Optimization (AOO) (ablation) | FicGCN on Cora · Cora | latency: 47.65±3.76 -> 40.39±1.61 | Helped |
| Add Ciphertext Processing Order Optimization (CPOO) (ablation) | FicGCN · four datasets | latency: +15% efficiency | Helped |
| Add Node Order Optimization (NOO) instead of no reordering (ablation) | FicGCN · Cora, Citeseer, Corafull, NTU | latency: 94.68 -> 69.28; 117.87 -> 86.14; 12003 -> 9075; 1562.03 -> 1463.80 | Helped |
| Replace NOO with Rabbit reordering (ablation) | FicGCN · Cora, Citeseer, Corafull | latency: 80.05 -> 69.28; 97.21 -> 86.14; 10011 -> 9075 | Hurt |
| Replace NOO with Rabbit reordering (ablation) | FicGCN · NTU | latency: 1562.03 -> 1562.03 | No clear effect |
| Use optimized packing width t=2 rather than t=1 or t=4 (ablation) | FicGCN · Cora | latency: 46.02s -> 36.23s; 41.89s -> 36.23s | Helped |
| Use optimized packing width t=2 rather than t=1 or t=4 (ablation) | FicGCN · Citeseer | latency: 82.98s -> 57.76s; 60.74s -> 57.76s | Helped |
| Use Detection alone instead of the naive node order (ablation) | NOO on Corafull · Corafull | latency: 10011s -> 10805s | Hurt |
Surprising findings
- Plaintext reordering method Rabbit is outperformed by NOO but Detection alone is 8% slower than Rabbit on Corafull.
- Packing optimized for the first layer (Inter-CA) does not necessarily minimize SpIntra-CA latency in later layers.
Limitations
- NOO preprocessing overhead may become a bottleneck on very large graphs (noted on Pokec-scale data).
- NTU dataset with only 25 nodes benefits little from NOO.
- Evaluation uses single-thread CPU and a limited set of datasets.
Experimental setup
Datasets: Cora Citeseer Corafull NTU-cross-View
Benchmarks: Cora Citeseer Corafull NTU-cross-View
Metrics: inference latency (s) speedup rotation count accuracy
Baselines: Gazelle Penguin CryptoGCN Rabbit reordering
Builds on: CryptoGCN Penguin Gazelle GraphSage CKKS
Closest papers by meaning
- CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference (NeurIPS 2022 · similarity 0.93)
- PrivCirNet: Efficient Private Inference via Block Circulant Transformation (NeurIPS 2024 · similarity 0.86)
- Federated Graph Condensation with Information Bottleneck Principles (AAAI 2025 · similarity 0.85)
- Going Deeper into Locally Differentially Private Graph Neural Networks (ICML 2025 · similarity 0.85)
- GRAIN: Exact Graph Reconstruction from Gradients (ICLR 2025 · similarity 0.85)
- DCT-CryptoNets: Scaling Private Inference in the Frequency Domain (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.