FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Zhaoxuan Kan, Husheng Han, Shangyi Shi, Tenghui Hua, Hang Lu, Xiaowei Li, Jianan Mu, Xing Hu · 2025
Read FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks by Zhaoxuan Kan, Husheng Han, Shangyi Shi, Tenghui Hua, Hang Lu, Xiaowei Li, Jianan Mu, Xing Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-10399.txt.
Introduction
Zhaoxuan Kan and seven co-authors set out FicGCN in twenty twenty-five. It is a way to run graph convolutional networks on encrypted data. Cloud GCN services raise privacy fears for graphs in health and finance that hold secrets. Homomorphic encryption lets a cloud compute on ciphertext. But its spins and multiplies make graph work painfully slow. The sparsity of a GCN promises speed. Yet its rough shape adds cost back.
FicGCN balances two steps, aggregation and combination, at a global scale. A latency-aware packing scheme trims cost. A sparse within-ciphertext aggregation method trims rotations. Adjacency-driven reordering of the data trims more. On several standard data sets it beat all rivals it was tested on. It beat the newest design by up to about four times. The work pushes private graph learning toward real use.
Catalog record
| CREATOR | Zhaoxuan Kan, Husheng Han, Shangyi Shi, Tenghui Hua, Hang Lu, Xiaowei Li, Jianan Mu, Xing Hu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-10399
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks Zhaoxuan Kan, Husheng Han, Shangyi Shi, Tenghui Hua, Hang Lu, Xiaowei Li, Jianan Mu, Xing Hu Abstract Graph Convolutional Neural Networks (GCNs) have gained widespread popularity in various fields like personal healthcare and financial systems, due to their remarkable performance. Despite the growing demand for cloud-based GCN services, privacy concerns over sensitive graph data remain significant. Homomorphic Encryption (HE) facilitates Privacy-Preserving Machine Learning (PPML) by allowing computations to be performed on encrypted data. However, HE introduces substantial computational overhead, particularly for GCN operations that require rotations and multiplications in matrix products. The sparsity of GCNs offers significant performance potential, but their irregularity introduces additional operations that reduce practical gains. In this paper, we propose FicGCN, a HE-based framework specifically designed to harness the sparse characteristics of GCNs and strike a globally optimal balance between aggregation and combination operations. FicGCN employs a latency-aware packing scheme, a Sparse Intra-Ciphertext Aggregation (SpIntra-CA) method to minimize rotation overhead, and a region-based data reordering driven by local adjacency structure. We evaluated FicGCN on several popular datasets, and the results show that FicGCN achieved the best performance across all tested datasets, with up to a 4.10 × 4.10\times improvement over the latest design. 1 Introduction Graph-based machine learning has gained significant prominence across numerous domains, with Graph Convolutional Neural Networks (GCNs) ( Kipf and Welling, 2016 ) emerging as a key paradigm demonstrating superior performance in various applications, including human action recognition ( Si et al., 2018 ; Yan et al., 2018 ) , financial recommendation systems ( Wu et al., 2022 ) , and drug discovery ( Bongini et al., 2021 ) . As the demand for cloud-based GCN services continues to grow, privacy concerns surrounding sensitive graph data have become especially critical, given that graph data typically include large amounts of confidential information. Privacy-Preserving Machine Learning (PPML) using Homomorphic Encryption (HE) offers a promising solution to alleviate these concerns by allowing clients to encrypt their data before sending it to the cloud server. This setup ensures that the server can perform computation directly on ciphertexts without ever decrypting them, effectively safeguarding user privacy. Specifically, in a privacy-preserving GCN cloud service, the server holds the well-trained weight matrices W and adjacency matrix A which are all plaintexts. The client sends the encrypted data to the server ( Ran et al., 2022 ) thus preventing data leakage to the server. Although this framework successfully protects sensitive graph embeddings, it also introduces substantial overhead. When a Cheon-Kim-Kim-Song (CKKS) ( Cheon et al., 2017 ) scheme is employed, the computational overhead increases a lot, often resulting in performance degradation by a factor of over three orders. Two primary factors contribute to this overhead. First, due to the requirements for security and correctness, homomorphic ciphertexts are much larger than the original data size, and the operation complexity is increased. Second, for batched CKKS ciphertext, moving and accumulating data within a vector, require expensive homomorphic ciphertext rotation operation. This results in high overhead for matrix multiplication on the ciphertext. For HE-GCN computation, the bottleneck in computation speed still lies in performing the aggregation and combination operations, specifically the plaintext-ciphertext matrix multiplication AXW where A and W are plaintexts and X is ciphertext, which includes a large number of rotations and multiplications. Drawing inspiration from the efficiency optimization of plaintext GCN computations, recent work leverages the sparsity of A for optimization. To this end, an adjacency-matrix-aware data packing and multiplication method is proposed ( Ran et al., 2022 ) , which reduces the rotation overhead in the X^{\prime}=AX process by exploiting the irregular sparsity of A . Unluckily, due to the irregular sparsity of A , additional SIMD multiplication operations are introduced when calculating X^{\prime}=AX , which results in limited overall speedup. Therefore, the main bottleneck in improving the computational efficiency of existing designs lies in how to leverage the irregular sparsity of GCN computations while adhering to the SIMD calculation pattern of HE, ultimately reducing the computational overhead. (a) Inconsistency in computation patterns. (b) Irregularity in neighbor aggregation patterns. Figure 1: The contradiction between the computing characteristics of GCN and CKKS. Addressing this challenge is difficult, as GCN’s irregular operational patterns stand in stark contrast to HE’s SIMD-based data processing. We analyze the conflicts as follows: 1. Inconsistency in computation patterns. As shown in Figure 1 (a), in AXW , the left multiplication of X by A is calculating sparse weighted aggregation between a partial set rows of X . The right multiplication of X by W is dense, achieving weighted aggregation between all columns of X . This introduces the conflict: for dense multiplication, fully-packed ciphertexts can improve efficiency, while for sparse multiplication, fully-packed ciphertexts lead to redundant rotations and multiplications. Additionally, The best data packing of X required for left multiplication and right multiplication is also different. 2. Irregularity in neighbor aggregation patterns. As shown in Figure 1 (b), in the calculation of AX , since the adjacency matrix A is sparse and irregular, each node in the graph requires performing different aggregation patterns. In CKKS ciphertexts, these nodes are encrypted into one vector. Therefore, this necessitates rotating the corresponding nodes and summing them. However, the contradiction between irregular sparsity and SIMD makes it challenging to balance ciphertext utilization and minimize the number of rotations. When using packed ciphertexts, rotation is required for each node’s specific aggregation needs, leading to significant computational overhead. In this paper, we propose FicGCN, a CKKS-based framework designed to exploit the irregular sparsity of GCNs. To resolve the mismatch between the aggregation and combination operations, we devise a latency-aware packing scheme that strikes a globally optimal balance for overall performance. For the irregular sparsity of A within aggregation, we employ a two-pronged strategy: first, a Sparse Intra-Ciphertext Aggregation (SpIntra-CA) technique that leverages HE’s operational properties to minimize total rotation overhead; second, a region-based data reordering based on the structural local adjacency of A . We implement and evaluate these designs, and our experimental results show that FicGCN achieves up to 4.10\times improvement on different datasets compared to the latest work. Our contributions can be summarized as follows: • We propose an optimal layer-wise aggregation scheduling strategy based on the data dimensions, model structure, and the latency of different HE operations. This enables efficient inference for data of various scales. • We propose a sparse intra-ciphertext rotation technique and a region-based data reordering to minimize total rotation overhead in aggregation. • We evaluate FicGCN on four popular datasets and the results show that FicGCN achieved the best performance across all tested datasets, with up to a 4.10\times improvement over the latest design. Figure 2: Workflow of FicGCN. (a) Three main steps of the HE-specific reordering algorithm: Detect, Arrange and Search. (b) The computational complexity comparison between Inter-CA and SpIntra-CA, SpIntra-CA encompasses log(N) fundamental rotations along with several additional rotations triggered by conflicts. (The dashed lines represent optional data paths, and the modules shown in detail are those that represent the optimization achieved through our innovative HE graph computation scheduling strategy, while the white modules retain the SOTA structure.) 2 Preliminary 2.1 CKKS Homomorphic Encryption Scheme CKKS ( Cheon et al., 2017 ) ,