FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Authors: Zhaoxuan Kan
Husheng Han
shangyi shi
Tenghui Hua
Hang Lu
Xiaowei Li
Jianan Mu
Xing Hu
Venue: ICML 2025 poster (2025)
Keywords: Homomorphic Encryption；Graph Convolutional Network；Reordering；Sparse Intra-ciphertext Aggregation
Primary area: deep_learning->graph_neural_networks
TL;DR: In terms of HE GCN, we propose latency-aware packing， sparsity-aware intra-ciphertext rotation and conflict-aware reordering  to exploit the non-structural sparsity and achieve up to 4.1x speedup.

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\times$ improvement over the latest design.

FicGCN:
Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Zhaoxuan Kan 123
Husheng Han 12
Shangyi Shi 12 Tenghui Hua"
Hang Lu 13
Xiaowei Li Jianan Mu
Xing Hu 134
Abstract
1. Introduction
Graph-based machine learning has gained significant promi- nence across numerous domains, with Graph Convolutional Neural Networks (GCNs) (Kipf & 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 sys- tems (Wu al., 2022), and drug discovery (Bongini et al., 2021). As the demand for dloud-base GCN services contin- ues grow, privacy concerns surrounding sensitive graph data have become especially critical, given that graph data typically include large amounts of confidential information.
Graph Convolutional Neural Networks (GCNs) have gained widespread popularity in various fields like personal healthcare and financial sys- tems, due to their remarkable performance. De- spite the growing demand for cloud-based GCN services, privacy concerns over sensitive graph data remain significant. Homomorphic Encryp- tion (HE) facilitates Privacy-Presenve Machine Learning (PPML) by allowing computations to be performed on encrypted data. However, HE intro- duces substantial computational overhead, partic- ularly for GCN operations that require rotations and multiplications in matrix products. The spar- sity of GCNs offers significant performance po- tential, but their irregularity introduces additional operations that reduce practical gains. In this pa- per, we propose FicGCN, a HE-based framework specifically designed to harness the sparse char- acteristics of GCNs and strike a globally optimal balance between aggregation and combination operations. FicGCN employs latency-aware packing scheme, a Sparse Intra-Ciphertext Ag- gregation (SpIntra-CA) method to minimize rota- tion overhead, and a region-basse based data reordering driven by local adjacency structure. We evalu- ated FicGCN on several popular datasets, and the results show that FicGCN achieved the best per- formance across all tested datasets, with up to 4.10x improvement over the latest design.
Machine Learning (PPML) using Ho- momorphic Encryption (HE) offers a promising solution to alleviate these concerns by allowing clients 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 safe- guarding user privacy. Specifically, in a privacy-presevving GCN cloud service, the server holds the well-trained weight matrices W and adjacency matrix which are all plain- texts. The client sends the encrypted data to the server (Ran et al., 2022) thus preventing data leakage the server. Al- though this framework successfully protects sensitive graph embeddings, it also introduces substantial overhead.
When a Lean-Kii--Kii-SS (CKKS) (Cheon et al., 2017) scheme is employed, the computational overhead increases lot, often resulting 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.
State Key Lab of Processors, Institute of Computing Technol- ogy, Chinese Academy of Sciences, Beijing, China UUniversity of Chinese Academy of Sciences, Beijing, China "Zhongguancun Laboratory, Beijing, China 'Shanghai Innovation Center for Pro- cessor Technologies, Shanghai, China. Correspondence to: Jianan Mu <mujianan ict.ac.en.>.
For HE-GCN computation, the bottleneck in computation speed still lies in performing the aggregation and combina- tion operations, specifically the plaintext-ciphertex matrix multiplication A where A and W are plaintexts and X
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
However, the contradiction between irregular sparsity and SIMD makes it challenging to balance ciphertext utiliza- tion and minimize the number of rotations. When using packed ciphertexts, rotation is required for each node's 's spe- cific aggregation needs, leading to significant computational overhead.
A(Sparsity)
WDDnsityy)
Sparse Matrix Mult
Dense Matrix Mult
In this paper, we propose FicGCN, TKKS-based frame- work designed exploit the irregular sparsity of GCNs. To resolve the mismatch between the aggregation and combina- tion operations, we devise a latency-aware packing scheme that strikes a globally optimal balance for overall perfor- mance. For the irregular sparsity of within aggregation, we employ a two-pronged strategy: first, a Sparse Intra- Ciphertext Aggregation (SpIntra-CA) technique that lever- ages HE's operational properties to minimize total rotation overhead; second, region- region-based based data reordering based on the structural local adjacency of A. We implement and eval- uate these designs, and our experimental results show that FicGCN achieves up to 4.10x improvement on different datasets compared to the latest work. Our contributions can be summarized as follows:
Inconsistency in computation patterns.
Agyregation
(b) Irregularity in neighbor aggregation patterns.
Figure 1. The contradiction between the computing characteristics of GCN and CKKS.
is ciphertext, which includes 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 manicenny-matrixxo aware data packing and multiplication method proposed (Ran et al., 2022), which reduces the rotation overhead in the X' 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' 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 com- putations while adhering to the SIMD calculation pattern of HE, ultimately reducing the computational overhead.
We propose an optimal layer-wise aggregation schedul- ing strategy based on the data dimensions, model struc- ture, and the latency of different HE operations. This enables efficient inference for data of various scales.
We propose 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 perfor- mance across all tested datasets, with up to a 4.10x improvement over the latest design.
Addressing this challenge is difficuul, GCN's irregular operational patterns stand in stark contrast to HE's SIMD- based data processing. We analyze the conflicts as follows: Inconsistency in computation patterns. As shown in Figure ((a), in AXW, the left multiplication of X by A is calculating sparse weighted aggregation between a partial 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 mul- tiplication 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 necessi- tates rotating the corresponding nodes and summing them.
2. Preliminary
2.1. CKKS Homomorphic Encryption Scheme
CKKS (Cheon et al., 2017), as a popular HE scheme, has been widely employed in confidential neural network in- ference since its ability for floating point numbers encryp- tion and computing using a scaling factor A. In CKKS, ciphertext
R2 can be decrypted by computing c sk mod Q = m + e, where R2 = Zx|XX/X + is the residue cyclotomic polynomial ring and sk refers to secret keys held by the client, is small error that provides security. The modulus is Q I qi. where L is the mul- tiplication level of the ciphertext. Each time homomorphic multiplication is performed, L decreases by one, making the next homomorphic operation faster. A ciphertext has N/2 slots to accommodate N/2 complex numbers and it supports homomorphic addition, multiplication and rotation:
2

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Order Optinizing
Higghn
Clisat
Selecion
Decrypt
PC
Duide & Conguer
Pi Add Propection to
Nowal
Aciiaatnn
Roals of Last Laysrs
Iaten-CA
Siroeal Connectid Hegion Detretion
Intelaneel
Search for Conflice
Misteniacion
Rost Proporticn bag
(c) Packing Methed
Fasture
Sclettinn
Splatra-CA
Adjanny Matii
Park Endeaon opteitol
Figure Workflow FicGCN. (a) Three main steps of HE-specific reordering algorithm: Detect, Arrange Scarch. (b) The computational complexity comparison between Inter-CA and SpIntra- CAntra-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.)
Dec(c1 2 C2) mi C m2 De & C2) = my @ m2:
sensitive data, such as clients' fingerprint information, med- ical data, and financial transaction records (Choi al., 2024; Yan al., 2018; Matsunaga al., 2019). Early cloud computing
Dec(m m @ C1) = m @ m1 Rot Enc(Uo, UN k) Enc(Uk, ... u.y 11 00 ...y 1k-
mainly integrated with CNN. Cryp- toNets (Gilad-Bachracd et al., 2016) is the first introduce HE into cloud computation. Due to the time overhead gap of 10 x between plaintext and ciphertext, existing work such as HEMET (Lou Jiang, 2021) made a trade-off between model parameters and encryption parameters to utilize mobile networks. (Lee al.. 2022) also observed the parallelism between CNN channels and leveraged this to effectively combine with the SIMD property of CKKS but still cost 6351 seconds when predicting on 50 images in CIFAR-100.
2.2. Graph Convolution Network and GraphSage
GCN contains multiple linear layers (consecutive matrix multiplications, GCNConv) and nonlinear layers. In GCN- Conv, there are two stages, Aggregation and Combination, corresponding to the left and right multiplications involving the feature matrix X. The layer-wise forward propagation can be expressed follows (Kipf& & Welling, 2016):
x GCNNCoo(XX)) o(x'''))
where Á is normalized adjacency matrix, W is the weight matrix for feature dimension transformation in 1 layer, a()) denotes the non-linear activation function.
The most distinguishing feature GCN compared to other types of networks is inherent sparsity. The plaintext in- ference has direct access the feature vectors of the nodes, which enables fully exploiting their sparsity based ad- jacency information, thereby simplifying the computation. (Jia et al., 2020)also identified common aggregation patterns and reused them, further enhancing cache performance and reducing computational overhead. Multi-Party secure Com- putation (MPC) methods (Reagen et al., 2021; Hao et al., 2022: Zeng al., 2023a;b; Wu al., 2024) are also in- troduced in confidential GCN to simulate the property of arbitrary node access in plaintext (Srinivasan et al., 2019; Reagen et al., 2021; Hao et al., 2022), but face significant communication overhead and rely on client computation.
GraphSage (Hamilton et al., 2017) is popular GCN scheme that introduces neighbor sampling in Aggregation, allowing each node's 's update depend only on features from subset of neighboring nodes. This significantly reduces the computational complexity while maintaining inference accuracy. The forward propagation chosen in this paper is:
x!+1 O(MEAN((X) u E (w)))hbo(())) W
2.3. Related Work
GCN inference under HE an effective method com- monly used in cloud computing scenarios to protect privacy-
Recent works tend to optimize the performance but fail
3

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
to fully utilize the sparsity. Gazelle (Juvekar al., 2018) was the first to apply diagonal encoding in the optimiza- tion of HE matrix multiplication, enhancing computational efficiency. Peinguin (Ran et al., 2024) adopted this idea by leveraging block-wise packing of X at the first layer, thereby achieving a trade-off when computing AX and XW. However, it had no utilization of the graph sparsity. CryptoGCN (Ran et al., 2022) made full use of the sparsity of A but it achieved suboptimal efficiency for requiring re- dundant computations to obtain the multiple ciphertexts for aggregation in the next layer.
2018) achieve 128-bit security- any successful attack would require at least 2 basic operations. Therefore the above theoretical foundations and configuration ensure the overall security of the inference process in FicGCN.
3. Method
3.1. Overview
In this work, we propose FicGCN from the following three aspects as shown in Figure 2: 1) The latency-aware methods for packing to efficiently utilize ciphertext slots. 2) The novel SpIntra-CA algorithm, which utilizes graph sparsity to reduce the aggregation overhead. 3) The Node Order Optimizing (NOO) algorithm further enhances the efficiency of SpIntra-CA with aggregation-friene node arrangement.
Besides, recent works like LinGCN, THE-X and HETAL (Lee et al., 2023; Peng et al., 2024; Ao & Boddeti, 2024; Jha et al., 2021; Ran et al., 2023; Chen et al., 2022) have observed that the nonlinear layers or feature maps not equally important, and have proposed algorithms to prune them. Meanwhile, prior works like FedMI.-HE (Jin et al., 2023) and BatchCrypt (Zhang et al., 2020) enable clients to strategically compromise certain node features' se- curity via Selective Encryption and reduce inference latency via parameter quantization. Corresponding technologies above are orthogonal and can be compatible with our work.
3.2. Latency-Aware Packing
Since decryption is not possible during the entire inference process, the initial packing strategy is crucial. The packing scheme determines both the utilization of ciphertext slots and the order of nodes within the ciphertext.
Our primary packing principle is designed to be Combination-ffiendly since the Combination stage does not exhibit sparsity, which thus is suitable and efficient for SIMD computation. Let M denote the number of ciphertext slots, N the number of nodes, F and F the feature dimen- sions before and after the layer computation, and n the number of sampled neighbors. That is, given feature ma- trix X E R NxF we perform the packing on column-wise basis as the blue ciphertexts in Figure ((a).
2.4. Threat Model
The threat model of this paper is similar to CryptoGCN. 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 honest but curious server and holds the secret keys thus preventing data leakage to the server. After calculating on encrypted data, the server sends the encrypted outcomes back to the client. The client can then decrypt them and get the results.
However, due to the varying dimensions of A and X across different graphs, column- based packing may not always guarantee efficient utilization of ciphertext slots. When the column vector is of small dimension, the packing scheme that assigns one ciphertext per column results in a waste of slots and an excessive number of ciphertexts, leading to significantly high Homomorphic Operation Counts (HOCs).
2.5. Security Analysis
The homomorphic encryption scheme employed in this study-CKKS derives its security from a well-established hard problem in lattice- cryptography: Learning With Errors (LWE). Specifically, in the CKKS decryption form sk mod Q = + e, the noise term e, which is inten- tionally added and accumulates throughout the computation process, ensures that the plaintext cannot be recovered in polynomial time without access to the secret key. Since e is typically much smaller than the encrypted message m, it has a negligible impact on the accuracy of the final output. As discussed in (Cheon et al., 2017), fundamental homomor- phic operations such as addition, multiplication, and rotation are all designed to preserve computational security. Further- more, according to the threat model outlined in Section 2.4, the client does not disclose the secret key to the server or any third party. All homomorphic operations used in FicGCN are covered by the security analysis in (Cheon et al., 2017). In the setup stage, we select HE parameters(Cheon et al.,
To address the issue, we model the impact of I (column num- ber in one ciphertext) on latency and compute the latency- optimal packing parameters, as shown in Figure 2(b). We can deduce that (The detailed derivations of the following two cases are provided in the appendix):
1) When M > N * F': The objective function can be ap- proximated as
F * n. F(; =2 11 1 20 log(t)]
We can optimize the value of for this function and deter- mine the packing strategy (shown in Appendix Section B).
4

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
2) When M < N F¹: It can be deduced that:
Table
Ablation Study for AOO
F +
N
F
Model
Rot
PMult
Add
Latency(s)
P Add#
Inter-CA
0
189K
206K
70.08
w/o AOO
7.04
61+3.1K
61+3.1K
47.65=3.76
This is an approximation that is independent of t, meaning that the total latency only depends on the number of Rot. Therefore, the optimal solution is t 1.
w/ AOO
5.74
65-44.0K
65444.0K
40.39-11.11
the lowest bit. Let the i-th rotation step be bit 2 for nodej, no rotation is performed (retained in the current slot) when bit: is equal to O. In ideal scenario (where all bili = 1), the i-th rotation would be effective for all nodes, improving the rotation efficiency significantly and allowing us to obtain the neighbor ciphertext in at most log(M) ro- tations. Meanwhile, we also check whether each node has reached its target position; if it has, is removed from the current ciphertext and added the result ciphertext.
3.3. Sparse Intra-ciphertext Aggregation
In this section, we introduce the innovative Sparse Intra- ciphertext Aggregation algorithm, which effectivelyy exploits the graph sparsity and improves the performance.
The existing HE+GCN aggregation method does not utilize the sparsity of GCN and thus is efficient (Ran et al., 2024). They construct N ciphertexts, each containing duplicate nodes node,, and perform aggregation using the adjacency matrix A. However, due to the sparsity of A, this method introduces significant redundant computation and storage.
All of the removal and position-selecting operations men- tioned above can be accomplished by multiplying the ci- phertext with a "Mask" plaintext polynomial composed of 0 and 1. Our SpIntra-CA can be iteratively represented as follows:
Observing that GCN exhibits significant sparsity, aggre- gation only performs with neighboring nodes. Thus, by constructing n "neighboring ciphertext", where each node position holds its neighboring node, we can achieve parallel aggregation across all nodes and eliminate the redundant computation.
{ct} t {ef) & Maska @ Rot((ct), 2m--) @ Maska
3.3.1. REDUCING COMPUTATIONAL COMPLEXITY
However, Due to the irregular connectivity in GCN, neigh- boring nodes of each node are randomly arranged in the ci- phertext, making it difficult to efficiently obtain the "neigh- bor ciphertexts". The naive method (Ru et al., 2021) as shown in Figure 3(a), performs node-by-node extraction, but results in an (NN) rotation complexity, where each rota- tion is only effective for one node, leading to low efficiency.
As shown in Figure 3(d), SpIntra-CA experiences slot con- flicts when multiple nodes attempt to occupy the same slot. This results in additional ciphertexts to resolve these con- flicts and more extra rotation overhead. Therefore, measures must be implemented to either reduce conflicts or minimize the shifting range of each node within the ciphertext.
Worst Case Analysis: In the worst case, each node traverses at most log(N) slots and collides at all of them, leading to at most log(N) extra ciphertexts and log"(N) Rots at all. Further, considering the number of ciphertexts (sampled neighbors), the total number of rotations is (n (n=1))=lo'² (NV). In practice, conflicts occur less frequently than assumed. The results Section 4 will demonstrate that, even when using the SpIntra-CA algorithm without reordering, the Rot number often much lower than the worst-case scenario.
Inspired by the ciphertext internal-sum method, which rotates each slot total M- - steps (where M 1 = 20 2' +... + ()ng(M)-1 -1), this method executes rotations sequentially (i.e., 20, 21, 22..) and performs a reduce to achieve summation. This method allows each rotation to be effective for all slots, ultimately requiring only log(M) rota- tions, significantly reducing needed rotations. The process can be represented by the following expression:
et + ct + Rot(ct, ) mm = 1,,
Optimizations: To improve the efficiency of SpIntra-CA, we have proposed the following optimizations:
Based on this, we propose the SpIntra-CA method as shown in Figure 3 efficiently generate neighbor ciphertexts and achieve efficient aggregation. First, given the ciphertext, we calculate the rotation length required for each node based on A, to construct the target "neighbor ciphertext" to be ag- gregated. Due to the irregular arrangement of sibling nodes in GCN, the rotation length varies for each node. Second, we perform bit decomposition of the rotation lengths for all nodes, executing rotations for all nodes sequentially from
Aggregation Order Optimization (A00): As shown in Figure 4(a), observing the cyclic shift property of ciphertext rotation, we have optimized the shift order of each node to find the shortest shift distance. This can reduce the bits of each node's 's shift step of SpIntra-CA, thereby reducing the Rot number.
Ciphertext Processing Order Optimization (CPOO): As shown in Figure 3(b), both the conflict
5

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
(a) Prior Work
Prior Work:
(b) SpIntra-CA
(c) NOO
Mask Rot())
SpIntra-CA:
NOO: Rots
4 Rots
Rots
Mask
N2
N
N
(2((2") & Mask
Rot(2 & Mash
N
2
Mask & Rotey)
Rot ) Maok
Target
Order
Target
Target
(d) СРОО
wi CPOO: Rut(6)
(e) Adjacency Matrix
Prior Work: Rots
w/o CPOO: :5 Rots
N1
w/ CPOO :4 Rots
0
1 0
Rot(2')
Ron(2*) Mask
0
For (a), (8). (c)
Maal
1
Ng
001
1
07
110
N
R
N2
N
0
0
110
1
1
0
071
X7
N
Conflict
0
0
0
0
110
Mark
N
N
For (d) A
1
0
0
0
101
N
N
Rut(2')
Rot(22) & Mask
N2
1
1
0
Inirial Order
Target Order
0
0
0
1
N
Keep the Original Position
Retain in Position of the Rotated Ciphertext
Remove from the Current Ciphertext and Add Ciphertext
N+
Before Rotation
Figure toy example of SpIntra-CA. (a) Aggregation in prior work node by node. (b) The process SpIntra- CA. (c) The NOO effect. (d) Conflicts arise when multiple nodes occupy the same slot, and removals occur when a node reaches its aggregation target position. Also CPOO may help merge some common Rots in sparse ciphertexts
Suboptimal Optimall
rotation counts and increase the node number per Rot. For example, we merge Rot(2) and Rot(4) into Rot(6) Figure 3(d). Meanwhile there exists oppurtunity to merge sparse ciphertexts into denser one, which another part of CPOO.
Step Longth-3MM4
Step Length=M/2
Ualization of slots
M/4
Node Order Optimization (NOO): The order of nodes within the ciphertext also crucial as illustrated Figure 3(c). This will be elaborated in detail in Section 3.4.
M/2
Index Ciphertexts
(b)The relationship index additional ciphortexts Spinbra-CA
AOO selects
aggrogation path
3.3.2. SELECTING AGGREGATION MODE
Figure Aggregation ciphertext processing order problem in SpIntra-CA
In FicGCN, two Aggregation modes are available: SpIntra- CA and Inter-CA. For each layer, the optimal mode is se- lected based complexity analysis. From Table 2, can deduce that the computational complexity of Inter-CA primarily arises from multiple inter-ciphertext calculations to obtain different node arrangements, which is mainly de- termined by F. In contrast, SpIntra- single ciphertext generate others, and is mainly influenced
and removal in SpIntra-CA lead to more sparse ciphertext, which decreases the efficiency of SIMD. Observing that no conflicts occur continuous multiple rotations on sparse ciphertext, we propose to merge them into one large-step rotation reduce the
Canntr--CAaa CA involves rotating a
6

---

the same as the existing works (Ran et al., 2022; 2024), in- cluding Cora, Citeseer, Corafull and NTU-cross- crooss-ww--w. The former three are relatively large-scate graphs, comprising 2708, 3327, and 19793 nodes with feature dimensions of FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Inter-Region Node Arrangement
Table 2. The comparison of HOC for different Aggregation modes. 'r" indicates that HOC for this mode cannot be theoretically ana- lyzed.
(a) Non- -nterleeee
(b) Interleave
Noa Intert
Inter:
Complexity
Aggrepation Pattern:
Operation
Latency
SpIntra-CA
Inter-CA
Nyt Nyth
PMult
Low
N
Fan
Add
Low
N
Rot
High
O(n log (N))
[log(t)
(c) Confllet-I cast Intra-Region Node Arrangement
Bil Nock
J-h Nak:
6ik Node
No hede
Least Coefiic
by N.
Based on this, the scheduling principle for layer-wise Ag- gregation mode can be derived as follows:
Node with Higlesi Degiee in Its Region
Leal Creflic
We always choose Inter-CA for the first layer, as the multiple inter-ciphertext computations can be eliminated by offline user encryptions from the client, which can be ignored.
First Layer:
Figure 5. Node order optimization (NOO). Interlcaved region ar- rangement (h) requires fewer rotations than the region-by-region arrangement (a). Greedy node arrangement for least conflicts within each region (c)
we enqueued sibling nodes instead of neighboring nodes in each iteration. We also use a threshold TH to limit the node number within a region. 2) Aggregation-efficinn inter-region node arrangement: Aggregation occurs be- tween sibling nodes, primarily within the same region. We propose interleaved arrangement of nodes between re- gions where each region can be regarded as a subring of the ciphertext, preserving the rotation pattern as illustrated in Figure 5(b). This inherent consistency further facilitates parallel computation across regions. 3) Conflict-least intra- region node arrangement. Within each region, we employ greedy strategy to sequentially determine node positions by selecting the (k + 1)-th node that minimizes the total number of conflicts with the already fixed k nodes, as shown in Figure 5(c). Thanks to the interleave arrangement, the search within each region can be conducted independently without interfering with one another.
Other Layers: For other layers, considering that Rot is often more than 20x slower than Pmult and Add (Lee et al., 2022), we follow the latency-aware formula (Ta- ble 2) to select Aggregation mode. In SpIntra-CA, we introduce factor E [0, 1] to quantify the effect of the optimization (like AOO) and the actual Rot number in practice (that is often less than the worst-case scenario). The final formula is as follows:
Inter-CA:
FA
Agg = arg min
SpIntra-CA: 10en log2 (N)
SpIntra-CA is preferred when F dominates the latency.
3.4. Node Order Optimization
As analyzed in Section 3.3.1, the efficiency of SpIntra-CA is limited by the maximum rotation range and the conflict number. The large rotation range results in a longer rotation step, leading more rotations; Excessive confticts may lead to more extra eiphertexts and rotations. From Section 3.3, we can observe that the rotation step is closely tied to the relative distance between the nodes to be aggregated in the ciphertext, which aligns seamlessly with the regional charac- teristics observed in the graph. Moreover, the arrangement of nodes within a region plays crucial role determining the frequency of conflicts.
Existing work also designed reordering algorithms, which are designed to enhance cache hit rates for plaintext comput- ing (Geng et al., 2021; Wei et al., 2016; Arai et al., 2). It fails to achieve optimal performance because it is not designed to accommodate the ring structure of CKKS ci- phertexts and cannot effectively reduce conflicts within a region. The NOO Algorithm is shown in Appendix.
4. Evaluation
4.1. Experiment Setup
Based on the observations above, FicGCN proposes node order optimizations (NOO) for HE+GCN to reduce HOCs and enhance efficiency, which includes the following three stages: 1) BFS-based Region Partition. We sequentially obtain all regions and find the nodes for each region with Breadth- Feartt--Firtttt Search (BFS). The only adjustment is that
Datasets. We conduct experiments the four datasets

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
1433, 3703, and 8710, respectively. Notably, the Corafull dataset exceeds the complexity of all prior inferred datasets in HE-GCN. The last one is a small-scale dataset designed for human action recogmition, comprising 25 nodes with 3-dimensional features. However, due to its inclusion of 256 frames with a temporally dense computation pattern, the computational latency under HE remains high.
Table 3. Compare with SOTA solutions. ("E" represents Inter-
CA. "A" represents Spintra- CA, and "Hybrid" denotes a mixed computation of the two methods.)
Dataset
Method
Aggregation Siot Utilization
Latency
Speed up
Gazelle
35%
1535,27s
Penguin
Hybrid
100%
128.82s
11.9x
Cora
CryptoGCN
E-E
66%
131,06s
11.7x
FicGCN+NOO
E-A
100%
64.12s
21.6x
Gazelle
81%
2897.25 25x
Models. Graph Auto-Encoder (GAE) models with 2 lay- ers and 2 non-linean activation functionssapproximaal x²) are trained on three large-scale datasets, using Adam optimizer with mini-batch size of 64, momentum of 0.9, and the learning rate of 0.01 for 200 epochs. The feature dimensions of the 2 layers are set to 32 and 16, respectively. We employ number of sampled neighbors that is approxi- mately equal the average number of neighbors per node in the original dataset. We also set TH- = 1024 for Cora and Citeseer; TH- = 4096 for Corafull. For NTU-cross- View, we train using the identical STGCN-3-64 model (Ran et al., 2022) and hyper-parameters following CryptoGCN.
Penguin
Hybrid
100%
142.90%
20.3
by
Citeseer
CryptoGCN
E-E
90%
150.42s
19,3%
FicGUN+NOO
100%
79.98s
36.2x
Gazelle
72%
Corafull
Penguin
Hybrid
100%
35565s
30x
CryptoGiCN
E-E
83%
31735s
>30x
FicGCN+NOO
E-A
100%
7733s
> >100%
NTU
CryptoGCN
E-E-E
78%
1731.08s
FieGCN
E-E-A
100%
1373.82s
1.26x
formance bottlenecks under these conditions, limiting their overall efficiency. We outperform state-of- the-art (SOTA) methods primarily due to two factors:(I), Our SpIntra-CA overcomes the trade-off between sparsity and SIMD pack- ing, significantly reducing redundant computations. While Penguin uses efficient packing but not sparsity, and Cryp- toGCN adopts both sparsity and SIMD but suffers low slot utilization, our approach is more holistic.
HE parameters & Environment. For the datasets with large and small scales described above, we respectively adopt the HE parameter configurations from Penguin (Ran et al., 2024) and CryptoGCN (Ran al., 2022). For large- scale datasets, we set: A = 230, : = 212 Q 218. For small-scale datasets, we set: A = 233, M = -11;;
(2). We de- vise specialized reordering algorithm for SpIntra-CA and CKKS's cyclic shift, which trades minimal plaintext over- head for a significant reduction in homomorphic latency.
680. We conduct all experiments on a machine equipped with Intel(R) Core(TM) 17-9750H CPU using the single thread setting to test the inference latency and use Microsoft SEAL version 3.7.2 (t implement the CKKS scheme.
4.2.2. ABLATION STUDY
Ablation study for AOO. We first conduct an ablation study for AOO. As illustrated in Figure 4(a), we determine the op- timal aggregation order for each node to minimize the shift range within the ciphertext. Clearly, AOO is independent of the dataset, thus, without loss of generality, we analyze this only using the Cora dataset as an example. We report the mean and standard deviation of results from 10 different samples.
4.2. Evaluation Results
1.2.1. COMPARE WITH SOTA SOLUTIONS
We conduct an end-to-end latency comparison analysis with SOTA methods including Gazelle, Penguin, and Cryp- toGCN. For fair comparison, when using Penguin, we perform aggregation with the plaintext adjacency matrix A. As shown in Table 3, our FicGCN achieves speedups of 21.6x, 34.2x, >> 120x over Gazelle across Cora, Cite- seer, and Corafull, respectively. The results in Table 3 also show that on the NTU dataset (25 points), we achieve a 1.26x speedup over the fastest design, CryptoGCN. On the Cora (2708 points) and Citeseer (3327 points) datasets, we achieve 2.01x and 1.78x speedups, respectively, compared to the fastest design, Penguin. Furthermore, on the Corafull dataset (19793 points), our method outperforms the fastest design CryptoGCN, by a factor of 4.
Table shows that incorporating AOO results in an 18.5% rotation reduction and achieves speedup of 1.18x. AOO may introduce minor side effects since multiple nodes may occupy the same optimized initial position, which may incur slightly more conflicts in SpIntra-CA, but still leads to the above performance gains.
Ablation Study for CPOO. As shown in Figure 6(b), CPOO that merging and postponing the process of sparser ciphertexts enhances computational efficiency by 15%, prun- ing 14%-46% Rots, which is attributed to allowing single rotation to satisfy the requirements of more nodes with a relatively low conflict rate. Figure 6(a) illustrates the ra- tio of inference latency under different ciphertext sparsity thresholds to that without CPOO across four datasets, which demonstrates that the optimal threshold should be selected
This comparison highlights that our method delivers stronger performance on larger graphs. Specifically, SpIntra- CA enables arbitrary reordering within the ciphertext, effec- tively addressing the inefficiency that arises when M- < N. In contrast, existing approaches such as Penguin face per-
8

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Optimized Range
Table 5. Overhead analysis of Node Order Optimization (NOO) on
130
Sunun P (%)
large-scale datasets
Datasct
[V(G)
E[G)
daug
Tyao (8)
The (8)
86%
77%
82%
Cora
2.7K
5.4K
4.01
2.00
64.12
3.2%
Citeseer
54%
Citeseer
3.3K
4.7K
2.85
5.33
79.98
6.7%
ml
NTU
Prused Rateton
Rotzzan
Corafull
19.8K
127K
12.82
27.91
7733
0.36%
Ciphertexts Number in Current Stage
Utilization Threshald
(a)
Cora
Chssee
(b)
Corstal
NTU
Pokce
1.63M
30.62M
18.80
181.20
~ 10"
~ 0.002%
w. crep
20-
Claacer choo
Citsseer wta CPSO
4.3. NOO Overhead Analysis
MIUI wi ciPd
As shown in the results of Table 3, the advantages of FicGCN become more pronounced on large-scale graph datasets. The datasets used in current mainstream studies and in the evaluation of homomorphic inference in FicGCN all contain fewer than 100K nodes. Consequently, as the dataset size increases, the overhead of pre-processing NOO may potentially surpass online inference latency and be- come the primary performance bottleneck for FieGCN. To investigate this, we selected Pokec, large-scale dataset with over million nodes, measure the time overhead of NOO and compare it with the online inference latency. The results are presented in Table 4, which includes:
+ MIU whah CINDO
10-
10 12
16
Rotation Stage in SpIntra-CA (c)
Figure 6. The effectiveness of CPOO. (a) The relationship between latency and utilization thresholds across four datasets. (b) The ratio of Rots pruned by CPOO of 4 datasets. (c) Stage-wise ciphertext number w/ and w/o CPOO
Graph Statistics: Node count (VV())), edge count (F(G)), and average degree (davg))
Table 4. Ablation Study for NOO (NOR: Namber of Regions)
Accuracy (Backbone)
Dataset
Model
Rot
PMult
Add
Latency(s)
NOR
Time Overhead: NOO preprocessing time (Txoo) and online stage HE computation latency (ThE).
w/o NOO
125K
117K
94.68
0.792
Cora
w/ Rabbit
2.85K
109K
103K
80.05
(0.815)
w/ NOO
1.93K
97K
95K
69.28
Efficiency Ratio: p == TNoo/THE
w/o NOO
7.03K
151K
139K
117.87
0.692
Citeseer
w/ Rabbit
3.60K
140K
131K
97.21
8
(0.727)
w/ NOO
2.35K
123K
120K
86.14
As shown in Table 5, NOO exhibits low time overhead on smaller datasets. For large-scale graphs like Pokec, NOO's overhead remains negligible relative FicGCN's online phase, ensuring NOO does not bottleneck FieGCN's perfor- mance.
w/o NOO
46.3K
20.0M
22.8M
12003
0.648
Corafull
w/ Rabbit
38.3K
16.5M
17.5M
10011
14
(0.695)
w/ NOO
36.7K
14.7M
16.9M
9075
w/o NOO
10.66K
233K
257K
1562.03
0.749
NTU
Rabbit
10.66K
1562.03
(0.825)
w/ NOO
9.97K
218K
241K
1463.80
5. Conclusion
within 0.2~0.3. Figure 6(c) further illustrates the effective- ness of CPOO across different datasets.
In this paper, we explore the performance potential of spar- sity in HE+GCN. Based on the sparsity of node connection, we propose FicGCN with optimal layer-wise column- based packing method and a sparse intra-ciphertet aggre- gation method to reduce the computation redundancy and boost the performance. We also propose a region-basee data reordering method to further improve the aggregation effi- ciency. The results show an up to Ix speedup compared to SOTA works and demonstrate its superiority on large graphs, promoting the practical deployment of HE GCN.
Ablation Study for NOO performs greedy search for the node with the fewest current conflicts in SpIntra- CA. resulting in optimization performance that surpasses existing cache hit rate improvement methods such as Rab- bit (Arai et al., 2016). Table presents the ablation experi- ments of NOO on datasets. Our proposed NOO reduces Rot number by 66.4%, 66.6%, 20.7% and 6.5% compared with direct SpIntra-CA respectively. The relatively lower improvement in NTU-cross- dataset is attributed to its smaller node number (25) and simpler connectivity struc- tures, in which cases we suggest not using NOO to save offline time. Among the 3 optimization methods, NOO demonstrates the most significant effect.
Acknowledgments
This work is partially supported by Strategic Priority Re- search Program of the Chinese Academy of Sciences, (Grant

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
X0B66600000,, XDB0660301, XDB0660302), the NSF of China(under Grants U22A2028, 62222214, 62341411, 62102398, 62102399, 62302478, 62302482, 62302483, 62302480, 62302481, 62172387), CAS Project for Young Scientists in Basic Research(YSBRR-O) and Youth Innova- tion Promotion Association CAS.
ence for privacy-preserving fingerprint authentication. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 38, pp. 21976-21985, 2024.
Geng, T., Wu, C.. Zhang, Y., Tan, C., Xie, C., You, H., Herbordt, M., Lin, Y., and Li, A. I-gen: A graph convolu- tional network accelerator with runtime locality enhance- ment through islandization. In MICRO-54: 54th annual IEEE/ACM international symposium on microarchitec- ture, pp. 1051-1063, 2021. 2021.
Impact Statement
Our paper enhances the computing efficiency of Homo- morphic Encryption (HE) GCNs while ensuring data pri- vacy through robust security guarantees of HE, With the widespread use of GCN systems and growing privacy con- cerns, our paper facilitates the practical application of GCNs in security and privacy-critical scenarios. We believe our work positively impacts society.
Balad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Nachrig, M., and Wernsing, J. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pp. 201-210. PMLR, 2016.
Halevi, S. and Shoup, V. Algorithms in helib. In Advances in Cryptology-CRPPPO 2014: 34th Annual Cryptology Conference. Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part 34, pp. 554-571 Springer, 2014.
References
Ao, W. and Boddeti, V. N. {AutoFHE}: Automated adap- tion of {CNNs} for efficient evaluation over (FHE). In 33rd USENIX Security Symposium (USENIX Security 24), pp. 2173-2190, 2024.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Arai, J., Shiokawa, H., Yamamuro, T., Onizuka, M., and Iwamura, S. Rabbit order: Just-in-time parallel reorder- ing for fast graph analysis. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS),
Hao, M., Li, H., Chen, H., Xing, P., Xu, G., and Zhang,
T. Iron: Private inference on transformers. Advances in neural information processing systems, 35:15718-15731, 2022.
pp. 21. IEEE, 2016.
Bongini, P., Bianchini, M., and Scarselli, Molecular gen- erative graph neural networks for drug discovery, Neuro- computing, 450:242-252. 2021.
Jha, N. K., Ghodsi, Z., Garg. S., and Reagen, B. Deepre- duce: Relu reduction for fast private inference. In Interna- tional Conference on Machine Learning, pp. 4839-4849. PMLR, 2021.
Chen, T., Bao, H., Huang, S., Dong, L., Jiao, B., Jiang, D., Zhou, H., Li, J., and Wei, F. The-x: Privacy- preserving transformer inference with homomorphic cryption. arXiv preprint 2:XX::2206.002/111 16, 2022.
Jia, Z., Lin, S., Ying, R., You, J., Leskovec, J., and Aiken, A. Redundancy- computation for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 997-1005, 2020.
Cheon, J. H., Kim, A., Kim, M., and Song. Y. Homomor- phic encryption for arithmetic of approximate numbers. In Advances in CryptolggyASIAACRYP) 2017: 23rd In- ternational Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part 1 23, pp. 409-437. Springer, 2017.
Jin, W., Yao, Y., Han, S., Gu, J., Joe-Wong, C., Ravi, S., Avestimehr, S., and He, C. Fedml-he: An efficient hwwpmmorppii-enccrpiio--aaaae
privacy-preservingg fed- erated learning system. arXiv preprint arXiv:2303.10837, 2023.
Cheon, J. H. Han, K., Kim, A., Kim, M., and Song, Y. Bootstrapping for approximate homomorphic encryption. In Advances in Cryptology Annual International Conference on the Theory and Ap- plications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3. 2018 Proceedings, Part 37, pp. 360- 384. Springer, 2018
2018: 37th
Juvekar, C., Vaikuntanathan, V., and Chandrakasan, A. (GAZELLE): A low latency framework for secure neural network inference. In 27th USENIX security symposium (USENIX security 18), pp. 1651-1669, 2018.
Kipf. T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint hewp:6609009000 2016.
Choi, H., Woo, S. S., and Kim, H. Blind-touch: Homomor- phic eneryption-base based distributed neural network infer-
10

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Lee, E., Lee, J.-W., Lee, J., Kim, Y.-S., Kim, Y., No, J.-S., and Choi, W. Low-complexity deep convolutional neural networks on fully homomorphic encryption using multi- plexed parallel convolutions. In International Conference on Machine Learning, pp. 22403-12422, PMLR, 2022.
SEAL. Microsoft (relesee 3.7). https: htap::://ggthb///// com/Mi croso /SEAL, September 2021. Microsoft Research, Redmond, WA.
Si, C., Jing, Y., Wang, W., Wang. L.,, and Tan, T. Skeleton- based action recognition with spatial reasoning and tem- poral stack learning. In Proceedings of the European conference computer vision (ECCV), pp. 103-118, 2018.
Lee, S., Lee, G., Kim, J. W., Shin, J., and Lee, M.-K. Hetal: transfer learning with homo- morphic encryption. In International Conference on Ma- chine Learning, pp. 19010-19035. PMLR, 2023.
efficient
Srinivasan, W. Z., Akshayaram, P., and Ada, R. Delphi: A cryptographic inference service for neural networks. In Proc. 29th USENIX secur. symp, volume 3, 2019.
Lou, Q. and Jiang. L. Hemet: homomorphic iineeyrrpiieeeerrpptionn friendly privacy-preserving mobile neural network archi- tecture. In International conference machine learning. pp. 7102-7110 10. PMLR, 2021.
Wei, H., Yu, J. X., Lu, C.,, and Lin, Speedup graph processing by graph ordering. In Proceedings of the 2016 International Conference on Management of Data, pp. 1813-1828, 2016.
Matsunaga, D.. Suzumura, T., and Takahashi, T. Ex- ploring graph neural networks for stock market pre- dictions with rolling window analysis. arXiv preprint arXiv: (eti::990..1000 2019.
Wu, H., Fang. W. Zheng, Ma, J., Tan, J., Wang, Y., and Wang, L. Ditto: Quantization aware secure inference of transformers upon mpc. arXiv preprint arX5v2240.005525, 2024.
Peng, H., Ran, R., Luo, Y., Zhao, J., Huang. S., Thorat, K., Geng, T., Wang, C., Xu, X., Wen, W., et al. Lingen: Structural linearized graph convolutional network for ho- momorphically encrypted inference. Advances in Neural Information Processing Systems, 36, 2024.
Wu, S., Sun, F., Zhang, W. Xic, X., and Cui, B. Graph neural networks in recommender systems: a survey, ACM Computing Surveys, 55(5):1-37, 2022.
Ran, R., Wang. W., Gang, Q. Yin, J., Xu, N., and Wen, W. Cryptogen: Fast and scalable homomorphically encrypted graph convolutional network inference. Advances in Neural information processing systems, 35:37676-37689, 2022.
Yan, S., Xiong, Y., and Lin, D. Spatial temporal graph convolutional networks for skeleton-basee action recogni- tion. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
Zeng, W., Li, M., Xiong, W., Tong, T., Lu, W.-j., Tan, J.. Wang. R., and Huang, R. Mpevit: Searching for accurate and efficient mpe-friendly vision transformer with het- erogeneous attention. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5052- 5063, 2023a.
Ran, R., Luo, X., Wang, W., Liu, T., Quan, G., Xu, X., Ding, C., and Wen, W. Spenenn: orchestrating encoding and sparsity for fast homomorphically encrypted neural net- work inference. In International Conference Machine Learning, pp. 28718 8-7788. PMLR, 2023.
Zeng, W., Li, M., Yang, H., Lu, W-j.. Wang, R., and Huang, Copriv: network<protocol co-optimization for communicaiion-efiiienn private inference. Advances in Neural Information Processing Systems, 36:78906- 78925, 2023b.
Ran, R., Xu, N., Liu, T., Wang, W., Quan, G., and Wen, W. Penguin: perallel-packed homomorphic encryption for fast graph convolutional network inference. Advances in Neural Information Processing Systems, 36, 2024.
Reagen, B., Choi, W.-S., Ko, Y., Lee, T., Lee, H.-H. S., Wei, G.-Y,, and Brooks, D. Cheetah: Optimizing and accelerating homomorphic encryption for private infer- ence. In 2021 IEEE International Symposium High- Performance Computer Architecture (HPCA), pp. 26-39. IEEE, 2021.
Zhang, C., Li, S., Xia, J., Wang, W., Yan, F., and Liu, Y. [BatchCrypt]: Efficient homomorphic encryption for {Cross-Sile Silo) federated learning. In 2020 USENIX annual technical conference (USENIX ATC 20), pp. 493-506, 2020.
Ru, S., Zhang, B., Jie, Y., Zhang, C., Wei, L.,, and Gu, C. Graph neural networks for privacy-preserve recommen- dation with secure hardware. In 2021 international con- ference on networking and network applications (NaNA), pp. 395 400. IEFE, 2021.

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
A. HE Operation Overhead Analysis
As mentioned the main text, the basic overhead of different types HE operations varies. Generally, L(Rot) so L(CMult) L(PMult) > L(Add). 'L' represents latency. The two aggregation modes primarily used in this paper (Intra-CA and Inter-CA) rely on different fundamental operations. By analyzing the differing HOCs for each mode, is evident that each method has its strengths and weaknesses depending the dimension of the feature matrix, the size of the model, and the HE parameters configuration.
Since CKKS is a leveled homomorphic encryption (LHE) scheme, it divides the bits of each coefficient in the ciphertext polynomial into multiple groups, with each group corresponding to a multiplication level. After performing a multiplication cost for
on the ciphertext, re-scaling operation necessary to reduce the bit length of the coefficients, lowering subsequent HE operations. The core idea behind an optimal inference framework is prioritize the cheaper operations, such Add, PMult, and delay the more expensive ones. This is reflected FicGCN's design, where the first layer primarily uses the Inter-CA based PMult and Add, while the SpIntra-CA. is placed in later layers.
Figure 7(a) illustrates the HE operation individual cost at different levels for ciphertexts under the HE parameter configuration used for large graph inference in this paper. It shows that the overhead of Rot and CMult is often over 20x greater than that PMult and Add. Figure 7(b) breaks down the time overhead of HE operations under different methods. inference dominated by SpIntra-CA, the delay caused by Rot exceeds %.. Therefore, the methods proposed this paper, such as AOO, CPOO, and NOO, which reduce the overhead of Rot to enhance computational efficiency, have been shown be effective. Since under plaintext A, the computational overhead of the non-linear layer represented by CMult is negligible, there is no need prune the non-linear layer done in prior work (Lee al., 2023; Peng al., 2024; Ao & Boddeti, 2024; Jha et al., 2021; Ran et al., 2023).
5.142
Add
CNult
4.20 380
Latency (ms)
2,423
1.989
0.304
0.21%
Level3
Level2
Levell
HE Operation
(a)
51.8
PMult
CMult
Rot
Relative Ration(% (%)
38.2
33.7
29.1
29.4
24
7.9
4.5
CryptoGCN
Penguin
FicGCN
HE+GCN Framework
(b)
Figure 7. (a) Statistics of single operation overhead for the four basic HE operations different levels of ciphertext. Bb)akkoo of time overhead for the basic HE operations under different inference frameworks.
12

---

FicGCN:
Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
B. Latency-Aware Objective Function
Section 3.2 presents two macro scheduling strategies for FieGCN-packing method and layer-wise aggregation mode decisions. The commonality of these two strategies is that they estimate the latency by evaluating the HOC under different methods, which is then used as the objective function to derive the optimal solution and strategy for the current state. This section provides detailed derivation of how the two objective functions obtained.
Table 6. Experiments Sctup
Average Degree (Sampled Neighbors)
HE Parameters
Dataset
Model
Feature Dimension
Security Level
M
Q
GCN GraphSage
4.01
Cora
1433-32-16
4096
30
218
128-bit
4.00
GCN GraphSage 3703-32-16
2.85
Citeseer
4096
30
218
128-bit
3.00
GCN
12.82
Corafull
GraphSage 8710-32-16
4096
30
218
128-bit
13.00
GCN
2.00-4.00
NTU
3-64-128-128
8192
60
680
80-bit
GraphSage
4.00
B.1. Packing Method
As shown in Figure (()), to minimize the dense computation overhead the Combination step, we propose column-based packing strategy. Specifically, pack the data from columns of X into the same ciphertext polynomial in column-major order. When t = each ciphertext stores single feature dimension for all nodes, eliminating the need for expensive rotation operations during the Combination phase. However, since the dimensions of X vary, 1 may not guarantee maximum ciphertext slot utilization, potentially resulting in more ciphertexts and additional overhead. Therefore, we must balance ciphertext utilization with the extra rotation overhead, aiming to find the optimal value t by using the first-layer Inter-CA latency estimation as the objective function.
We divide the problem into two categories based on whether the eiphertext size can fully pack all the elements of the next layer's feature matrix, i.e. by comparing the sizes of M and N F..
M N F' :In this case, it is possible to pack particular column from Figure 1(a) within the same ciphertext, so the number of PMult and Add is [ where [-] denotes ceiling. Since there are multiple feature dimensions within the ciphertext, considering the intra-ciphertext summation, this will incur an additional rotation overhead of log(t) times. (Halevi & Shoup, 2014) Here we consider L(CMult) = L(Rot) = 20L(PM)l)) = (Add), thus we can derive the objective function as:
F n
[[: (n)= =
+ 20 log(()]
Figure 7(a) shows example objective function, the optimal can be searched within a cheap pre- pre-processing overhead. M < N F': In this case, we are unable to fully pack complete column from Figure ((a) into single ciphertext; we can only pack several rows. Since we pack & columns from X each time, a single ciphertext will contain M
+
rows as shown in
the figure. Consider that the matrix in Figure 1(a) contains N + F' rows, we can get N=F single ciphertext. Therefore, the number of PMult and Add can be calculated as:
rows in the figure within
_F *
N F
uPltt) N Wum(AAd)
This is an approximation that is independent of t, meaning that the total latency only depends on the number of Rot. Therefore, the optimal solution is 1.
13

---

FicGCN:
Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
B.2. Selecting Aggregation Mode
From Table I, it be seen that the dominant HE operations in Inter-CA and SpIntra-CA differ. Inter-CA primarily involves different orderings of repeated ciphertext-level additions and multiplications, the time overhead can be estimated as: 21 E 1. On the other hand, SpIntra-CA is mainly composed of single-order ciphertext, from which new permutation of ciphertext is generated every log" (N) rotations. As result, smaller time overhead can be chosen for each layer, and the aggregation mode for each layer can be determined before starting the inference.
Agg = arg min {
Inter-CA: 2 Fen ? 10cn log (N)
SpIntra-CA:
At the same time, since the final output and the node order in the client's packed ciphertext can be arbitrary, the NOO results on the SpIntra-CA CA results be propagated back to the client layer by layer to complete the optimal order packing since there is no restriction for both the order of the input and output in FicGCN, as shown in Figure 7(b).
Optimized
((tF.n)
Order Back Propagation
Cloud
Client
Arbitrary Order
Inter- Ciphertext
Intra- Ciphertext
Packing
Output
Aggregation
Aggregation
Arbitrary Order
X
NOO
(b)
Figure 8. (a) An example objective function (b) The principal of node order back propagation which influences the initial packing order from the client.
C. Supplementary Experiments
C.1. Experiments Setup
All experimental settings are mentioned in Section 4.1. 1. Here, this information is summarized in Table 5. When sampling, the number of neighbors we sample is approximately equal to the average degree of nodes the graph.
C.2. Ablation Study for Packing
We pack columns from into a ciphertext and use the delay estimate of the first-layer Inter-CL. MArr-CA as the objective function to find the optimal t value, balancing the utilization of ciphertext slots and the extra Rot overhead induced. However, whether this approach remains effective for subsequent layers, particularly for those using SpIntra-C., Cantra-CA, nontrivial question.
14

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Table 7. Ablation Study for Packing
DataSet
Optimized
Packing Method
Ciphertesi Number
Inter Latency
Spiutra CA Latency
Overall Latency
Speedup with Optimized
1433-32-16
37.95s
8.07s
Cora
2
2
717-16-8
20.36s
15,87s
36.23s
1.27x
359-8-4
14.88s
27.01s
41.89s
1
1
3703 3703-32-16
77.00s
5.98s
82.98x
Citeseer
2
t
1852-16-8
40.29s
17.47s
57.76s
1.44x
1 4
926 8-4
21.69%
39.05%
60.74s
For Inter-CA, since the ciphertexts involved in the computation are repeatedly generated, the overall computational cost is almost proportional to the number of ciphertexts. Therefore, reducing the number of ciphertexts, or in other words, increasing the packing density, can reduce the latency. However, for SpIntra-CA, the situation more complicated. As the slots utilization increases, the sparsity of ciphertexts decreases significantly, resulting in a higher probability of conflicts during computation, which actually increases the latency. Furthermore, since these confticts are closely related to the "Graph Coloring Problem", which is NPC, the exact relationship between conflict occurrences and ciphertext sparsity is hard to be theoretically derived.
Therefore, we conduct experiments to verify the effectiveness of the proposed latency-aware packing optimization method. Table 6 shows the latency variation of different parts of the model under different packing strategies. Each data point is the average of 20 different random samples, and only the Cora and Citeseer datasets, with moderate dimensions, were selected for the experiment. Furthermore, 1024 nodes were randomly sampled from each dataset for the experiments.
From the table, we can observe that for both datasets, when is doubled, it leads to halving of the number of ciphertexts, along with small increase in the Rot overhead. As result, the Inter-CA delay approximately becomes half of the original value. However, the delay for SpIntra-CA does not exhibit a clear pattern as ciphertexts become more densely packed. Therefore, when considering both, the optimal computation efficiency is typically achieved at the point that minimizes the overhead for the first layer. Thus, the proposed packing strategy not only minimizes the Inter-CA overhead in the first layer but also ensures minimal delay even when different modes of SpIntra- are considered for subsequent layers.
C.3. NOO Effect
The principle behind our proposed NOO that enhances the computational performance of homomorphic inference mainly involves two key aspects:
GCN sibling node computation mode: By grouping nodes with computational relationships into the same region and mapping this relationship to the ciphertext's ordering, we ensure that nodes that need to be computed are placed closer together. This effectively reduces the displacement distance of all nodes within the ciphertext.
Heuristic search with greedy strategy: By searching for the state with the fewest conflicts, the entire aggregation process sees significant reduction in the number of conflicts.
Algorithm 1 aligns with the 3 stages illustrated in Figure 2(a). Lines 1-11 describe the detection of strongly connected regions using BFS-based approach. In each iteration, the sibling nodes of the current node are enqueued, and a threshold TH is employed to control the maximum number of nodes per region. Subsequently, line 12 interleaves the nodes of these regions within the vector. These two steps also facilitate the partitioning of the problem into sub- uub-problems, ensuring the search space is partitioned from the entire graph into multiple regions and thereby achieving the divide-and and--uquer strategy. Finally, lines 13-27 employ a greedy search strategy to traverse the node within each region individually, placing each node position that minimizes the total number of conflicts in the current state. Here, Congo' (pl n. i) indicates whether conflict occurs at the j - th position during the rot th rotation when node is placed the i th position under the current node ordering. Moreover, the arrangement between these regions remains unaffected due to the SIMD rotational characteristics on the ring, thus the process of merging these sub-problems incurs no additional overhead.
As shown in Table 7, our NOO outperforms plaintext reordering algorithms for the following reasons: 1) Most plaintext reordering algorithms place neighboring nodes closer together, but this doesn't 't directly align with the sibling computation patterns in GCN 2) Plaintext reordering algorithms are often designed to optimize cache hits in linear structures, while NOO focuses on the ring structure of CKKS ciphertext. 3) Leveraging the computational features of CKKS, a cnn-cquerr
15

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
Table 8. Ablation Study for NOO
Dataset
Add
Latencyls)
(Backbone)
NOR
Distriburion Ciphertest Number
Cora
w/ Rabbit
2,85K
109K
L17K 103K
$0.05
0.792 (0.815)
6
3-7-8-7-6-5-1-3-1
w/ NOO
1.73K
91K
89K
64.12
2:5:5:5-4:3-2
Cltsseer
w/o NOO
w/ Rabbit
7,03K
3.60K
140K
151K
131K
139K
117.87
97.21
(0.727)
0.692
8
6-12-12-12-221111100000000.22
3-9-9-8-772.7-3--222
NOO
2-7-6-1---:--2-2---
Corafull
w/o NOO
Rabbit
46.3K
20.0M
22.8M
10011
12003
0.648
69:11-13-13-1--11----777
w/ NOO
32.1K
12.7M
14,9M
7733
(0.695)
4-11-11-8-10.7-766553
NTU
w/ Rabbit
w/o NOO
10.66K
10.66K
233K
233K
257K
257K
1562,03
1562.03
0.749
2
4-3-3-1
4-3-3-1
w/ NOO
9,97K
214K
236K
1373.82
(0.825)
3-3-2-1
algorithm can naturally be designed to parallelize the processing of all partitioned regions, thereby reducing the number of conflicts.
NOO consists of three steps: Detection, Interleave Arrangement, and Search. The effects of each step will be presented one by one.
Table 9. Ablation Study for Packing
Dataset
Naive Lat
Lat w/ Detection
Lat w/ Search
Lat w/ Rabbit
Lat w/ NOO
Cora
94.68s
76.73s
88.22s
80.05s
64.12s
Citeseer
117.87s
95.01s
108.96s
97.21s
79.98s
Corafull 12003s
10805s
11426s
10011s
7733s
NTU
1562.03
1481.13s
1413.45s
1562.03s
1373.82s
Detection & Search Effect As shown in Table 8, for medium-sized datasets like Cora and Citeseer, our Detection outperforms graph partitioning algorithms on plaintext, as prioritizing the grouping of sibling nodes into the same region better aligns with the computational structure of GCN. Additionally, Detection alone more effective than Search alone, generally reducing latency by up to 13%. This suggests that, for these datasets, the disordered connectivity in randomly arranged ciphertexts is the primary factor limiting HE computation. However, for larger datasets like Corafull, where connectivity is more complex. the sibling-firse first detection strategy results in certain connected regions being inadequately explored, making Detection 8.0% slower than Rabbit. In such cases, Search is more effective, indicating that the key limiting factor for computational efficiency in large graphs is the higher probability of conflicts. For small-scale datasets like NTU, both Detection and Rabbit have little impact, with efficiency gains coming mainly from reducing conflicts.
Regardless of the dataset, the efficiency improvement from using the complete NOO is always greater than the sum of the improvements from Detection and Search alone. This is because only when both are used together can partitioned regions reduce the search space and enable parallel computation between regions (divide and conquer), resulting in higher computational efficiency.
Interleave Arrangement Effect We aim to arrange the nodes belonging to different regions in the ciphertext in an alternating pattern like ABCABCABC... as shown in Figure 2(a). However, in practice, we often encounter situations where the number of nodes in different regions is unequal, and the total number of nodes is slightly smaller than M. Therefore, we follow these principles for arrangement: 1) Placing the nodes of all in an interleaved manner. 2) When the nodes of particular region are exhausted, prioritize filling the position of that region with blank slots. 3) If blank slots are also exhausted, begin alternately arranging the remaining regions. The final arrangement results for the four datasets are shown in Figure 8. We use gray to represent blank slots. As can be seen, each dataset ultimately faces a situation where the nodes of certain regions are exhausted, which breaks the efficient parallel rotation pattern established earlier. However, the proportion of nodes with this arrangement is quite low, so we can first complete the aggregation of most nodes and then handle this small portion of nodes at the end. This has little impact on the overall computational efficiency.
16

---

FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
1291
2400
104
400
270
Cora NOR=6
Citeseer NOR-8
Corafull NOR=4+3+344
NTU
Figure 9, Interleave Arrangement Effect of 4 Datasets
Algorithm Node Order Optimization for SpIntra-CA
Input: Graph: G (V, M: Slot number; TH: Maximum number of nodes in region; A: Adjacency matrix after neighbor- sampling; Sittiiitigg modified breadth-first search enqueues sibling nodes at iteration. Output: pl Res: A plaintext vector which contains an optimized order of nodes
I: t 0; Plain + []; Vrea V;; m +
2: while V is not empty do
Neur + Node with the highest degree in Veur
Numnode t- 0; Rear +-D
5: BFSSabiing.tnill -nnil..-niAA... (A, Neur)
while Nummnode TTH BF Sebbinngg do
7: Nour + B (popl)
8: Rour & Reuu U Neur N Nummode+ + =
9: end while
10: R.push((Rcur):
V Reer
end while
12: Plain + Interleane. InterreeneeAraangement (rrangement(R)
13: pl
Zeroslike(PP)) (Plain)
14: for 1 [R] do
15: Nar +- Node with the highest degree in Rr
16: pl Plain" [[] <- N
17:
for E Sübling([Nae and is not visited do
18:
kmin +00; index +- 0; |llaire for i Lo do
20:
Kn Eド Elog(t)
C n,
21:
if pt'ees is available and hn kmin then index <- i; kmnn kn.
22:
23:
end 24: end for
25: pfkke (index)) Neur Neur
26: end for
27:
end for
28:
Return peR
17


Reviews:
[{"review_id": "5cwMaLY9Ot", "reviewer": "Reviewer_B6Z3", "summary": "The paper presents FicGCN, a method aimed at enhancing the efficiency of homomorphic encryption in irregular Graph Convolutional Networks (GCNs). It introduces a **latency-aware packing method** that optimizes the arrangement of ciphertext slots, balancing computational overhead and utilization. The **Sparse Intra-Ciphertext Aggregation (SpIntra-CA)** method is proposed to minimize redundant computations during aggregation, leveraging the sparsity of graphs for parallel processing of neighboring nodes. Additionally, the **Node Order Optimization (NOO)** technique is introduced, which rearranges nodes to reduce rotation overhead and conflicts during ciphertext processing. The paper also includes a **region-based data reordering method** that improves aggregation efficiency by organizing data based on local adjacency structures. Experimental results demonstrate that FicGCN achieves up to a **4.1x speedup** compared to state-of-the-art methods, particularly benefiting larger datasets. Overall, the study emphasizes the importance of optimizing homomorphic encryption operations to enhance computational efficiency while maintaining data privacy in GCN applications.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Time complexity of Node Order Optimization (NOO) on large-scale datasets**\n\nThanks for your constructive comments. We have extended the application of NOO to large-scale datasets  Pokec (1.6M nodes). The following table summarizes the experimental results across datasets, including:\n- **Graph Statistics**: Node count ($|V(G)|$), edge count ($|E(G)|$), and average degree ($d_{avg}$).\n- Time Overhead: NOO preprocessing time ($T_{NOO}$) and online stage FHE computation latency ($T_{FHE}$).\n- Efficiency Ratio: $\\rho=T_{NOO}/T_{FHE}$\n \n\n| Dataset      | $\\|V(G)\\|$ | $\\|E(G)\\|$     | $d_{avg}$ |  $T_{NOO}$ (s)     | $T_{FHE}$ (s) | $\\rho$      |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n| Cora      | 2.7K       | 5.4K      | 4.01       | 2.00      | 64.12    | 3.2%       |\n|Citeseer     | 3.3K       |  4.7K      | 2.85       | 5.33       | 79.98      | 6.7%       |\n| Corafull      | 19.8K       |  127K     | 12.82       | 27.91      | 7733      | 0.36%       |\n|Pokec      | 1.63M       |  30.62M      | 18.80      | 181.20       | $\\sim 10^7$     | $\\sim 0.002$%      |\n\n\nAs shown in this table, NOO exhibits low time overhead on smaller datasets. For large-scale graphs like Pokec,  NOO's overhead remains negligible relative to FicGCN's online phase. Notably, on large graphs, the client-side encryption time alone eclipses NOO's latency, ensuring NOO does not bottleneck FicGCN's performance.", "claims_and_evidence": "Yes, all claims are clear and with enough proof.", "methods_and_evaluation_criteria": "The Node Order Optimization (NOO) technique improves computational efficiency during encrypted data processing by determining the optimal aggregation order for each node. This minimizes the shift range within the ciphertext, which is crucial for reducing rotation overhead during aggregation operations. By arranging nodes in an aggregation-friendly manner, NOO enhances the efficiency of the Sparse Intra-Ciphertext Aggregation (SpIntra-CA) method, leading to a significant reduction in the number of required rotations and overall computational complexity. This optimization allows for more effective utilization of ciphertext slots, ultimately improving the speed and efficiency of the graph convolutional network operations. With the provided benchmarks, i think this work handles the sparsity of graph in HE domain very well.", "theoretical_claims": "I have checked correctness of proof. No issues found by me.", "experimental_designs_or_analyses": "I have checked the experiments, all looks good and enough to support the techniques.", "relation_to_broader_scientific_literature": "see above.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "I have only one concern about the scalability to very large model. As graph model might be applied to dataset with over 100k nodes, e.g. reddit, applying node detection here might has very large cost on graph traverse.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aT0FJBMAJk", "reviewer": "Reviewer_DHPE", "summary": "The paper proposes FicGCN, a framework designed to accelerate private Graph Convolutional Network inference, with three key innovations. First, an optimal layer-wise aggregation scheduling strategy is presented to accelerate inference for data of various scales. Second, Sparse Intra-Ciphertext Aggregation (SpIntra-CA) is introduced to leverage GCN sparsity to minimize the overhead associated with rotations in ciphertexts during aggregation operations. Third,  Node Order Optimization (NOO) is proposed to minimize conflicts and improve computation efficiency by reordering nodes based on the adjacency structure. FicGCN is evaluated on several popular datasets, and the results show that FicGCN achieved the best performance across all tested datasets, with up to a 4.10× improvement over the latest design.\n\n## update after rebuttal\nBased on the authors’ rebuttal, I have revised my original score from 2 to 3 since the rebuttal resolved my major concerns on the motivation of the NOO technique.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Justification for the need to reorder nodes(Q1)**\n\nThanks for your comments. Negotiating and determining the optimal packing method based on NOO prior to private inference indeed constitutes a key contribution of our work.  We discussed it in Section 3.2.1 and Figure 8(b).\nHowever, only packing is insufficient due to the leak of utilization of sparsity of A in online inference(Table 4,6), we thus introduce three techniques and put them together to support efficient FHE-GCN inference:\n- Latency-aware packing: Optimizes packing for XW to enable dense SIMD computations.\n- SpIntra-CA: A novel approach leverages irregular sparsity patterns during AX, enabling arbitrary desire node order and supporting parallel and non-redundant node aggregation.\n- NOO: A reordering algorithm that groups nodes to enhance SpIntra-CA's computational efficiency while preserving XW performance.\n\nTo illustrate, in Figure 8(b) both parties iteratively determine the node packing order, starting from the final layer and back-propagating to the client's input based on NOO and SpIntra-CA. This reverse derivation is then integrated with our latency-aware strategy to derive the optimal packing method, achieving simultaneous optimization of both AX and XW computation.\n\n**2. Proof of upper bound rotation counts in SpIntra-CA (Q2)**\n\nDue to space constraints, we present the key proof arguments and the complete formal proof with notation tables is at https://anonymous.4open.science/r/FicGCN-D208. In our paper, n denotes the sampled neighbor counts.\n\nThe rotation counts of each stage in SpIntra-CA can be calculated as $\\sum\\_{k=0}^{i-1}Con_{k,j+\\sum\\_{p=0}^{k-1}2^p} \\cdot \\frac{1}{2^k}\\leq \\sum\\_{k=0}^{i-1}2^k \\cdot \\frac{1}{2^k}$, is less than $log(N)$. Thus the total counts is $O(log^2(N))$  rather than $O(N)$. This can be formally proved by the Lemma 1 and Conflict Bound Analysis. \n\n**Analysis:** 1) $Con_{i,j}$, the number of conflicts in the $i^{th}$ rotation stage at the $j^{th}$ slot, is the summation of all conflicts during the prior stages in the corresponding slots which can be rotated to $j^{th}$. \n2) $PR(ct[m]\\rightarrow ct[q])$, the the probability of rotating an element in $m^{th}$ slot to $q^{th}$. The case \"$ct[j+\\sum^{k-1}\\_{p=0}2^p]\\rightarrow ct[j]$\" means that the rotation step($rs$) bits of an element in $ct[j+\\sum^{k-1}\\_{p=0}2^p]$ should be all ``1'' among the corresponding k contiguous bits.\n\n\n**Lemma 1:** Given any bit distribution($Pr[bit_p=1]=\\frac{1}{2}-\\epsilon$),  $ PR(ct[j+\\sum\\_{p=0}^{k-1}2^p]\\rightarrow ct[j])\\le \\frac{1}{2^k}$\n\n**Proof:**\nBased on **Analysis** 2), we have $PR(ct[j+\\sum\\_{p=0}^{k-1}2^p]\\rightarrow ct[j])\\le \\frac{1}{2^k}$ when $\\epsilon>0$. When $\\epsilon\\le0$, by replacing cyclic left shifts with cyclic right shifts, the $rs$ bits become the complement of the original:\n$$PR(ct[j+\\sum^{k-1}\\_{p=0}2^p]\\rightarrow ct[j])=(\\frac{1}{2}+\\epsilon)^k \\leq \\frac{1}{2^k}$$ So we have $ PR(ct[j+\\sum\\_{p=0}^{k-1}2^p]\\rightarrow ct[j])< \\frac{1}{2^k}$ when $\\epsilon\\neq 0$\n\n**Conflict Upper Bound Analysis:** $Con_{i,j} \\leq log(N)$ under the worst case(uniform distribution).\n\n**Proof:**  According to **Analysis** 1), $$Con_{i,j}=\\sum\\_{k=0}^{i-1}Con_{k,j+\\sum\\_{p=0}^{k-1}2^p} \\cdot PR(ct[j+\\sum\\_{p=0}^{k-1}2^p]\\rightarrow ct[j]) $$\nAccording to Lemma 1, it is $$\\sum\\_{k=0}^{i-1}Con_{k,j+\\sum\\_{p=0}^{k-1}2^p} \\cdot \\frac{1}{2^k}\\leq \\sum\\_{k=0}^{i-1}2^k \\cdot \\frac{1}{2^k}=i \\leq log(N)$$\nThus, the number of conflicts per stage is bounded by log(N). Given that SpIntra-CA comprises log(N) stages, it yields a total conflict counts of less than $log^2(N)$ between an aggregation of two nodes.\n\n**3. Crypto primitives in FicGCN (Q3)**\n\nWe use only FHE in FicGCN framework, with no other crypto primitives such as MPC.\n\n**4. Impact of masking on multiplicative depth**\n\nIn  CKKS, the consumption of multiplicative depth primarily stems from ciphertext rescaling operations. However, the masking procedures described in our work do not require such rescaling and introduce no additional burden on the multiplicative depth budget.\n\nDuring CKKS, each floating-point message $m$ is first scaled by a precision parameter $\\Delta$ and quantized to an integer before encryption:\n$c=Enc(\\Delta \\cdot m)\\ $.\nConsequently, when multiplying two ciphertexts with identical initial scales ($\\Delta$), the resulting ciphertext's scale becomes $\\Delta^2$:\n$$c_1*c_2=Enc(\\Delta\\cdot m_1)*Enc(\\Delta\\cdot m_2)=Enc(\\Delta^2\\cdot(m_1\\*m_2)) $$\n\nCKKS employs rescaling operations to restore the ciphertext's scale to $\\Delta$. However during Masking, we multiply the ciphertexts by plaintexts encoding integer 0/1 with the scale=1:\n$$ Enc(\\Delta \\cdot m) * Encode(1 \\cdot mask) = Enc(\\Delta \\cdot (m*mask))$$\nTherefore the scale of ciphertexts remains invariant. Also, the results of Masking  bit-length remains constant because we multiply them by 0/1. Thus the multiplicative depth will not be consumed during Masking.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "No. I have one question on the method proposed in this paper. It seems this paper mainly focuses on optimizing the node’s order so that the adjacent row in the feature map would represent neighbor nodes in the graph, which could then benefit the aggregation process. However, since the graph topology (the adjacency matrix A) is a public input to both parties, they can first negotiate and determine the optimal packing method before private inference. Moreover, Ciphertext-Plaintext computation in the combination process (XW part) would not change the node order. So I think the need to reorder the node’s packing during runtime requires further justification. (Q1)", "theoretical_claims": "Yes. I have one question on the correctness of CPOO’s theoretical overhead (Page 5). The original paper claims the worst case requires (n-1)logN^2 rotations, but once a conflict happens, the number of rotations will double as this will split the original ciphertext into two ciphertexts, and result in like 2^logN = N ciphertext instead of logN^2.Therefore, detailed proof for this worst-case scenario is needed. Moreover, I do not find the meaning of n, and I suggest the author make a table to better illustrate the meaning of the notations. (Q2)", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper mainly focuses on private GCN inference, which is meaningful for Graph relevent tasks including recommendation system, knowledge graphs and can be further extended.", "essential_references_not_discussed": "No, essential references are all discussed.", "other_strengths_and_weaknesses": "Strengths:\n+ Only aggregating a subset of the neighbor node is an effective way to exploit the sparsity.\n\nWeaknesses:\n- More details are required to better clarify this paper, especially questions proposed in the comments.", "other_comments_or_suggestions": "- On section 3.3, paragraph 2, line 2, I suppose the author wants to express “and thus is inefficient” instead of “and thus is efficient”.", "questions_for_authors": "Besides the questions (Q1 and Q2) described above, I have the following questions to the author:\n\n- Q3: What are the crypto primitives used in the framework? Is it HE/MPC or FHE?\n- Q4: In the proposed method, frequent masking is required and this will result in increased multiplication depth. How does this influence the computation efficiency of HE? Could you provide a theoretic estimation of the multiplication depth required?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OFFEfLm8u4", "reviewer": "Reviewer_JDUB", "summary": "This paper proposes FicGCN, a framework for efficient privacy-preserving inference of Graph Convolutional Networks (GCNs) using Homomorphic Encryption, by using (1) a latency-aware packing scheme that optimally balances aggregation and combination operations based on data dimensions and model structure; (2) a Sparse Intra-Ciphertext Aggregation method that minimizes rotation overhead in aggregation operations by leveraging graph sparsity; (3) a region-based node reordering technique that reduces computational overhead by optimizing the local adjacency structure.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Security proof of FicGCN**\n\nThanks for your comments. FicGCN fully adopts CryptoGCN's[3] threat model and privacy assumptions which has been rigorously proved. We utilize the CKKS scheme, whose security is guaranteed by the hardness of the RLWE problem[1], ensuring polynomial-time indistinguishability. During inference, we employ only CKKS-supported secure homomorphic operations (PMult,CMult,Rot), and the ciphertext packings. Since CKKS inherently supports arbitrary message vector ordering in its plaintext polynomial encoding[2] and homomorphic operations, FicGCN preserves CKKS's original security guarantees.\nIn the setup stage, we select homomorphic encryption parameters[2] to achieve 128-bit security—meaning any successful attack would require at least $2^{128}$ basic operations.\n\n**2. Analysis of the impact of supplementary references on FicGCN**\n\nThe techniques from the referenced works are orthogonal to our research and do not directly contribute to it. However, they can be easily integrated with our approach in their intended applications to enhance overall end-to-end performance.\n\nTo illustrate, FedML-HE enables clients to strategically compromise certain node features' security via Selective Encryption, converting partial computations from ciphertext to plaintext for reduced latency. THE-X primarily optimizes nonlinear layers through polynomial approximation—an objective orthogonal to FicGCN's linear-layer optimizations. Similarly, BatchCrypt's quantization uniformly accelerates all layers, constituting another independent optimization dimension. While all 3 studies offer potential improvements for GCN inference, their techniques operate on distinct axes from our approach. We therefore incorporate them as valuable references while emphasizing FicGCN's unique contributions.\n\n\n**3. Key management in FicGCN**\n\nIn FicGCN, we exclusively employ FHE to execute encrypted inference for ensuring data security. This framework requires three distinct keys: the public key (pk), private key (sk), and evaluation key (evk).\n\n- Pk: Used for data encryption/decryption and enabling homomorphic operations, thus being publicly shared between both parties.\n- Sk:  Also involved in encryption/decryption, is strictly client-exclusive to prevent server-side privacy breaches. All decryption occurs solely on the client side to eliminate man-in-the-middle risks.\n- Evk: Generated by the client and disclosed to the server, facilitates server-side HE computations (e.g. Rotation, CMult).\n\n**4. Analysis of collusion threat model in FicGCN**\n\nFicGCN's application scenario involves strictly one client and one server following the common FHE assumption[3], where the client possesses all node features and refuses to disclose any data to the server. This fundamentally contradicts the prerequisite for collusion models defined in [4]—which require at least three participating parties capable of covert coordination to violate protocol security. Under our key management framework, **FHE inherently eliminates collusion threats** because:\n\n(1) Only two non-cooperating parties exist\n\n(2) Even if a server supports multiple colluding clients, they cannot obtain honest clients' private keys\n\n(3) Security reduces solely to RLWE hardness\n\n\n\nReference:\n\n[1] Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC '05)\n\n[2] Cheon, J.H., Kim, A., Kim, M., Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. In: Takagi, T., Peyrin, T. (eds) Advances in Cryptology – ASIACRYPT 2017.\n\n[3] Ran Ran, Nuo Xu, Wei Wang, Gang Quan, Jieming Yin, and Wujie Wen. 2022. CryptoGCN: fast and scalable homomorphically encrypted graph convolutional network inference. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS '22).\n\n[4] Goldreich, O. (2004). Foundations of Cryptography II. Cambridge University Press.", "claims_and_evidence": "The key claims appear to be well-supported by (1) detailed theoretical analysis and derivations of the optimization methods; (2) extensive experimental results across multiple datasets showing consistent improvements. However, a formal privacy analysis is missing for security properties claimed.", "methods_and_evaluation_criteria": "Same as above.", "theoretical_claims": "Detailed theoretical analysis and derivations of the optimization methods, but a formal privacy analysis is missing for security properties claimed.", "experimental_designs_or_analyses": "Experimental design seems to be sufficient. The analyses are generally valid, though they could benefit from additional privacy analysis, either from empirical attack simulation or statistical analysis like privacy sensitivity calculation.", "relation_to_broader_scientific_literature": "This work proposes a specific optimization when introducing HE into GCN for privacy-preserving ML. However, there still lacks some key related work that would raises concerns about the novelty and improvement claim in this paper. Some missing related work are listed below.", "essential_references_not_discussed": "1. Zhang, Chengliang, et al. \"{BatchCrypt}: Efficient homomorphic encryption for {Cross-Silo} federated learning.\" 2020 USENIX annual technical conference (USENIX ATC 20). 2020.\n2. Chen, Tianyu, et al. \"The-x: Privacy-preserving transformer inference with homomorphic encryption.\" arXiv preprint arXiv:2206.00216 (2022).\n3.. Jin, Weizhao, et al. \"FedML-HE: An efficient homomorphic-encryption-based privacy-preserving federated learning system.\" arXiv preprint arXiv:2303.10837 (2023).", "other_strengths_and_weaknesses": "Some technical details in appendix could be better integrated into main text to have a better flow for explanation of the proposed idea.", "other_comments_or_suggestions": "I would love to see a formal rigorous security proof. For example, use UC-Security to provide privacy analysis.", "questions_for_authors": "1. How can the missing related work listed above further help justify the claims in the paper? Can any techniques in these papers be used to augment this work? For example, non-linear approximation and selective encryption?\n2. How does the key management work in this work?\n3. How does the system handle a client-server collusion threat model?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a homomorphic encryption based framework for GNNs that exploits sparsity. This includes in particular a scheme for sparsity-aware aggregation, a latency-aware packing method that optimizes combination operations, and a node-order optimization. The empirical evaluation shows an up to 4x speedup over existing methods.
The reviewers appreciated the contributions, especially the efficiency gains due to exploiting the sparsity of graphs. One reviewer asked for a security proof, please include the argumentation in the paper, as well as relation to the additional related works.
Decision: Accept (poster)