Penguin: Parallel-Packed Homomorphic Encryption for Fast Graph Convolutional Network Inference
Authors: Ran Ran
Nuo Xu
Tao Liu
Wei Wang
Gang Quan
Wujie Wen
Venue: NeurIPS 2023 poster (2023)
Keywords: Cryptographic inference
Graph Convolutional Network
Parallel Packing

Abstract: The marriage of Graph Convolutional Network (GCN) and Homomorphic Encryption (HE) enables the inference of graph data on the cloud with significantly enhanced client data privacy. However, the tremendous computation and memory overhead associated with HE operations challenges the practicality of HE-based GCN inference. GCN inference involves a sequence of expensive matrix-matrix multiplications, and we observe that directly applying the state-of-the-art HE-based secure matrix-matrix multiplication solutions to accelerate HE-GCN inference is far less efficient as it does not exploit the unique aggregation mechanism of two-dimension graph node-features in GCN layer computation. 
As a result, in this paper, we propose a novel HE-based ciphertext packing technique, i.e., Penguin, that can take advantage of the unique computation pattern during the HE-GCN inference to significantly reduce the computation and memory overhead associated with HE operations.
Specifically, Penguin employs (i) an effective two-dimension parallel packing technique for feature ciphertext with optimal graph node partitioning and graph feature interleaving, and (ii) an interleaved assembly technique that can effectively make use of the blank slots to merge ciphertexts after feature reduction and significantly reduce the costly rotation operation.
We provide theoretical analysis and experimental validation to demonstrate the speedup achieved by Penguin in accelerating GCN inference using popular GCN models and datasets. Our results show that Penguin can achieve up to $\sim10\times$ speedup and around $\sim79$% reduction in computational memory overhead, significantly outperforming state-of-the-art solutions. To the best of our knowledge, this is the first work that can ensure the protection of both graph structure and features when accelerating HE-GCN inference on encrypted data. Our code is publicly available at https://github.com/ranran0523/Penguin.

Penguin: Parallel-Packed Homomorphic Eneryption for Fast Graph Convolutional Network Inference
Ran Ran
Nuo Xu Lehigh University mux2190lehigh.ed
Tao Liu Lawrence Technological University tliu38ltu. edu
North Carolina State University rran@ncsu.edu
Wei Wang Anonym, Inc. wei mei@@nnnymco.co com
Gang Quan
Wujie Wen
Florida International University
North Carolina State University wwen20ncsu, edu
gaquan iunuuuuuuuuuuuuuuuuuuuu
Abstract
The marriage of Graph Convolutional Network (GCN) and Homomorphic En- cryption (HE) enables the inference of graph data the cloud with significantly enhanced client data privacy. However, the tremendous computation and memory overhead associated with HE operations challenges the practicality of HE-based GCN inference. GCN inference involves a sequence of expensive matrix-matrix multiplications, and observe that directly applying the state-of-the-art HE-based secure matrix- matrix multiplication solutions to accelerate HE-GCN inference is far less efficient as does not exploit the unique aggregation mechanism of two-dimension graph mode-features in GCN layer computation. As result, in this paper, we propose novel HE-based ciphertext packing technique, i.e., Penguin, that can take advantage of the unique computation pattern during the HE-GCN inference to significantly reduce the computation and memory overhead associated with HE operations. Specifically, Penguin employs (i) an effective two-dimension parallel packing technique for feature ciphertext with optimal graph node parti- tioning and graph feature interleaving, and (ii) an interleaved assembly technique that can effectively make use of blank slots to merge ciphertexts after feature reduction and thus significantly reduce costly rotation operations. We perform detailed theoretical analysis to support our arguments. In the meantime, our ex- perimental results also show that Penguin achieve up 10x speedup and around ~ 79% reduction in computational memory overhead, significantly out- performing state-of-the-an solutions. To the best of knowledge, this is the first work that can ensure the protection of both graph structure and features when accelerating HE-GCN inference encrypted data. Our code is publicly available at
com httm///anann023/Peeete
Introduction
Graph Convolution Neural Networks (GCNs) have recently demonstrated phenomenal performance for many privacy-sensitive applications such as social networks (34], cross-domain recommendation
systems (35), and personal healthcare [T8). A popular solution for clients seeking to leverage these advanced GCN models is utilize floud-based inference services. However, clients often hesitate to share their graph data with the public cloud due to concerns about sensitive information, such as graph structure and node features that reveal personal social relationships and medical records. To address this privacy concern, one viable approach is to adopt the Homomorphic Encryption (HE) scheme 6 7]. By performing the entire inference computation the cloud using encrypted data,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Latency (s)
RotationCMMutt Non-Linear Linear
Node-atte Feature wisc Node-Feahwoe Fede--iadure-jffit
CMult 6.44
Rotation
6.2
Reletive Ratio
0.76
Add
0.318
96 70%
PMult
0.297
0.21
Latency(ms)
Linear
Tom!
Latency
Memory
Latency
Latency
(a)
(b)
(c)
Figure 1: (a) Latency comparison of different HE operations under same encryption parameter and hardware environment; (b) Latency breakdown of linear/nonlinear HE operations in typical GCN layer computation. (Detailed settings in Sec. 4.1). (c) Single optimization and wasted ciphertext slots have negative effect memory utilization and computation latency.
the privacy of client data is significantly enhanced. This enables while ensuring that sensitive information remains confidential.
GCN inferences
While the idea of embedding HE into GCN inference on graph data seems appealing, it faces several significant challenges: Firstly, similar to HE-based CNN inference on non-graph data (such as for using convolutional neural networks (CNN) [10 privacy would come at the cost of the tremendously escalated computational overhead associated
4 8 23
2 19 [26] 17 I4). the enhanced
with HE operations (e.g., ciphertext (ct) rotations/mulliplicati
additions), which could be orders
of magnitude higher than the counterparts in the non-encrypted computation [TO] 29 [6]. Secondly,
existing solutions focusing on alleviating computation overhead of HE-based CNN inference may not be applicable or optimal to GCNs due to computing pattern differences between the CNN and GCN (11] For example, a GCN layer's computation is dominated by the special consecutive matrix multiplications (A x- W) for 2-dimensional feature-node aggregation-feature aggregation via multiplying high dimensional feature matrix X with weight matrix W, followed by graph node aggregation with A, while a CNN layer's s computation is bottlenecked by multi-channel 2D convolutions. Thirdly, simply treating the above critical matrix operations in HE-based GCN inference as a traditional encrypted matrix-matrix multiplication (MM) problem for speedup is sub-optimal because: state-of-the-art (SOTA) HE-based MM acceleration often requires the matrix to satisfy some special properties, e.g. square matrix with size 64 x 64 [15], while GCN matrices like feature matrix X typically irregular depending on applications (i.e. 2708 x 1433 in Cora dataset (32): 2) SOTA solutions focus on a one-time MM without considering the consecutive MMs incurred by the two-dimensional feature-node aggregation, as well as the further processing of MMs' result in the next GCN layer. This leads to inefficient ciphertext space utilization and unnecessary HE operations, which further translates into prolonged HE-GCN inference, we shall show in Sec. 4.2
To better understand the computation cost of HE operations that dominate the HE-GCN inference latency, we profile the latency of different HE operations using one GCN layer with 32 hidden units and the Cora dataset with 2708 graph nodes and 1433 (32) input (output) features per node. All HE operations are defined in Sec. 2 For generality, we assume both feature matrix and adjacency matrix are encrypted, which is a typical case in inductive learning (e.g. dynamic graph structure in link prediction) [22]. Without loss of generality, the same indexed features from different nodes for
packed as a ciphertext (feature-wis wise packing) and the encrypted matrices are diagonal-encodde MMs (detailed settings in Sec. 4.1. As Figure (a) shows, first, the latency of ciphertext rotation and ciphertext multiplication (CMult) can be much higher than other operations like plaintext (pt) multiplication (PMult) or Addition, c.g. 20 Rotation v.s. PMult. Furthermore, about > 99% latency comes from the linear operations (mainly HE rotation and CMult due to the consecutive MMs), instead of the nonlinear operations (ReLU replaced by square function) due to feature reduction in GCN (from 1433 input features to 32 output features). Meanwhile, for linear latency, Rotation and CMult dominate the latency (e.g. > 96% of total) as the size of the adjacency matrix could be quite large (Cora: 2708 22788) in the GCN problem. Last, we profile the latencies of different ciphertext packing formats under the same evaluation setup as (b) in Figure (c). From the profiling result in Figure (c), either the node-wise packing format (e.g. ciphertext contains one node's 1433 features) or the Teature-ve casture-wise packing format (e.g. I ciphertext contains the same indexed features from 2707 nodes) could not effectively perform the HE-GCN inference. With

---

packing format (e.g. 1 ciphertext packs 32 features and 128 nodes) by our proposed two-Dimension Paraklee-Packing (see Sec. (.2). the ciphertext size is fully exploited, and the total HE operation count reaches minimum, leading to significantly reduced latency and memory cost. These results indicate that the key to accelerating the HE--based GCN inference is to significantly reduce the rotation and CMult operations with a GCN-dedicated ciphertext packing format.
To this end, we propose Penguin, a novel HE ciphertext packing framework dedicated to accelerating GCN inference with the consideration of encrypting both graph structure and features simul- taneously (both adjacency matrix A and input feature matrix X). The driving vision of Penguin is: feature ciphertext packing for efficient HE-based GCN inference needs to be designed in manner that aware of the unique GCN computation both the left-side graph node aggregation AX and right-side feature aggregation (XW), ), instead of optimization in one direction (either AX or XW). In this way, the whole ciphertext space can be efficiently utilized with minimized slot waste, enabling the significant reduction of ciphertext number (memory overhead) as well as the expensive HE rotation and CMult operations under the single instruction multiple data (SIMD) architecture. Our major contributions are three-fold: 1) We propose efficient two-dimension parallel packing technique for ciphertext via optimal graph node partition and feature interleaving. By performing the feature-level aggregation first and formulating the HE computation overhead as a constrained optimization problem, we analytically obtain the best feature- partition that can maximize the usage of ciphertext space and minimize the costly HE operations. Experimental results are well consistent with theoretical analysis. 2) We propose an interleaved assembling (IA) technique to efficiently merge ciphertexts with blank slots incurred by feature dimension reduction in the feature aggregation stage. This extra-level optimization further significantly reduces the number of ciphertexts and associated HE operations. 3) We comprehensively evaluate our proposed Penguin for TKKSSbased GCN inference using Cora-based graph node classification, Citeseer- prediction, and Pubmed-based link prediction. Results show that our method achieves by up to about 10x inference speedup and 79% memory overhead reduction, significantly outperforming the state-of-the-ar solutions. To the best of our knowledge, this is the first work focusing on accelerating the HE-bau based private graph convolutional neural network inference on encrypted graph data, of which both the sensitive graph features and graph structure are protected.
link
2 Preliminary
CKKS Homomorphic Encryption Scheme. Homomorphic Encryption (HE) allows computations on enerypted data. HE has different categories according to the different computation types they support. The Leveled HE (LHE) schemes support a limited number of additions or multiplications while Fully HE (FHE) allows arbitrary number of computations using bootstrapping procedure that can effectively refresh the ciphertext and obtain a new ciphertext that encrypts the same value but has lower noise (9. In this work, we focus on reducing the number of bottlenecked operations in CKKS-one of the promising LHEs, without considering the costly bootstrapping.
CKKS 66 is an LHE scheme and its security is based on the hardness of ring learning with errors (RLWE) problem. CKKS allows arithmetic operations on encrypted data over fixed exeetpointt numbers with predefined precision, which makes it ideal candidate for performing machine learning tasks where most of the computations are approximate. The supported homomorphic operations include ciphertext addition Add ~ (ct, + ct2), ciphertext multiplication CMult ~ (cta x ctz), plaintext multiplication PMult ~ (ct x pt), ciphertext Rotation ~ p(ct, The rotation is to apply Galois automorphisms of the cyclotomic extension to the plaintext polynomials in encrypted form resulting in cyclic shift of the slot vector. Among these four operations, Rotation and CMull are substantially slower ( 20x slower) than siphertext-plainter addition and multiplication shown in our runtime performance of CKKS in Figure T due to the expensive key-switching operation 23
Graph Convolution Neural Network. To extract the hidden graph features H, the 2-dimensional neature-node aggregation of a typical GCN layer can be often abstracted as [21]:
H ==o(p, 1 A,,, A,Ø,->xx)
(1)
Where X E RNF is the input feature matrix. W, E RFX represents weight parameters to transform the input features from an input dimension F to output dimension F' ( (feature level aggregation). Dj. Ag is the adjacency matrix with self-loop. The XW term is implemented by
3

---

Fualur-Aggragtiion XW -y==
Node-Aggragation AX
Fuu
45
Σ
plat),
14.
021
021
402
F15
Fai
PL
P31
1544
534
PM
PM
944
Figure 2: Peature-Optimizer Packing Ciphertext Computation Flow.
fully-connected (FC) layer (node level aggregation) and then multiplied with the normalized adjaceney matrix 13 A, Finally, a non-linear activation function (e.g. ReLUU is applied to get one GCN layer's output feature matrix H. Throughout this work, we refer A as the normalized adjacency matrix since normalization could be absorbed in a pre-processing step.
Threat Model. We adopt a threat model setting consistent with prior works [0
19
client uploads private and sensitive data the cloud for obtaining the online machine learning model prediction results. The cloud server is semi monesth (e.g. honest but curious). To ensure data privacy, the client encrypts their own data by HE and decrypts this inference result by their private key. In this work, we focus encrypting both graph node features X and the normalized adjacency matrix A. The clients run the decoder of GAE [22 their end because this step does not involve trained model parameters on the cloud server.
3 Method
Overview. The GCN inference A X W can be separated into the two-dimension (A X on the nodes and X W on the features) aggregation on feature matrix X. When we perform HE matrix multiplication on the encrypted feature matrix (ciphertexts), is inevitable that we need to perform HE rotation on the same ciphertext. Unfortunately. the rotation operation not only incurs high latency but also generates huge number of ciphertext copies that consume large amount of memory space. In this section, we propose holistic solution set to systematically address these issues.
In order to effectively reduce the number of ciphertexts involved in HE computation, our design is built upon the fcature-wise packing since multiplying W often leads to a lower feature dimension. However, for non-densely packed ciphertexts, feature-wise packing is further subject the data alignment issue, resulting in extra rotations. To overcome this challenge, we propose the two- dimension purallel-packingg In addition, considering that the layer-wise feature number reduction would result in many wasted slots, we further propose the interleaved assembling to efficiently merge such ciphertexts.
3.1 Motivation of Feature-Oriented Ciphertext Packing
The major inference computation in GCN can be illustrated as A X W, where NNN the normalized adjacency matrix used for node-wise aggregation, X E R. is the input feature matrix, and W E RF x F' is the weight matrix used for feature wise aggregation. Apparently, we can choose A. X or W as the first step, which will not change the final product. However, considering that matrix X is encrypted ciphertexts with fewer dimensions will reduce the required HE operations and copies of the ciphertexts. For example, if F < F, first perform X W to produce intermediate product with fewer dimensions, i.e., RNN F" This will reduce the computational overhead and latency in the next step A X. On the contrary, F < F", we first perform A X.
ciphertexts, the order of computation will affect the efficiency since
We explore two ciphertext packing design options that could lead to minimized computational overhead single-dimension aggregation (either graph node or feature). One the feature-wise packing, where one ciphertext only packs one feature data from different nodes. The number of ciphertexts is proportional to feature number. The other is the node wise packing, where the number of ciphertexts is equal to the number of graph nodes. However, in this case, the number of graph

---

Hs
H
Ha
Fo
Pu
H6
Aa
Au
Figure (a) The Iwo-Dimension Parallel-Packing (b) The Interleaved Assembling.
nodes (or ciphertexts) does not change during inference, this inevitably results in too many wasted empty slots in the ciphertexts and thus would yield more HE rotations. As the example in Figure shows, we assume the ciphertext packing size is 8, adjacency matrix A E p4x4, weight matrix W E R and feature matrix X R2x44 The 4 feature-wise packing ciphertexts can be reduced to 1 ciphertext after feature aggregation, which only needs 4 Siphertext-multiliicaal
(CMult) in the next adjacency matrix multiplication. using the node-wise packing, we still need 16 CMult in the next step. Therefore, we choose feature-wise packing in our design.
3.2 Two-Dimension Parallel-Packing
Optimization Problem Formulation Following the definition in the previous section, assume that the ciphertext has M available slots for packing data and consider the following general case: M >> N and M F. As shown in Figure [ after the feature-wise packing, the same features of different data from feature matrix X are encoded into the same ciphertext X = [ct1... ct and then multiplied with weights Waj to get matrix X' XW . p'p in the same feature-wise packing format (see Eq. 22)
at - -
di
2 W.y. FEF
(2)
For node-wise aggregation, we need perform diagonal-encoded matrix multiplication 11] on ciphertexts F' individually. However, due to M N, we need to generate the corresponding ciphertext copies with each data aligned by rotating each ciphertext twice and scaling with the mask vector then summing (see Eq. 3).
dy = plct i) @ ms: + p(dl, -NN - i)) @ mV- i2!
(3)
After that, we multiply them with the corresponding diagonal-encoder vector d, of adjacency matrix and sum up them to get the node-wise aggregation result of A X' (see Eq.
Σ (ctt)) 60 du, ctos = =d
(4)
In this process, we can find that data alignment issue for non-densely packed ciphertexts leads to extra rotations. We propose the two-dimension parallel-packing solve it. Our idea is leverage the matrix partition to fully pack data in all slots and amortize the HE computation cost.
Figure 3 a) shows our basic idea. We partition (a power two number) graph nodes into small block to fully utilize the size of the ciphertext and encode the feature matrix X. In each ciphertext, we actually pack n nodes corresponding to f different features together in an interleaved way. For feature-wist aggregation, we adopt the baby-step algorithm 199 [5| to get the different output features with good alignment. As shown in Figure 3 (a), the number of rotations 2(f 1) used here for each ciphertext depends on the number of different features f = M/n (we assume the output feature
F' > f). Then, we continue rotate each ciphertext for 1 times and perform the diagonal encoded matrix multiplication
112 for A X. The total complexity of rotation is:
(n 1) (N- F' /M) + (2(f 1)) (N/n (F'/F)
(5)
Since M = n ff the total complexity is further equal to (N F MM) ((n 1) + 2( 1))
(6)
5

---

According to Cauchy-Schhae Schhar-- inequality:
O(n + 2f) 2 02 02./V = 0 vM)
7
Where = 2f, the total complexity of rotation reaches a minimum. Hence minimizing the number of rotations can be modeled as an optimization problem:
M = n **
argmin (m1 1) + 2( - s1)
f = 2t, KEN
(8)
M > N, N,M
Supporting Large Graph Eq. 8 assumes that the number of graph nodes should be smaller than
that of ciphertext slots (M N). however, for scaled graph networks, it is possible that M < N.
For example, the PubMed [32 contains 19717 nodes, which is far more than the 4096 ciphertext
slots. To address this, our method can be scalable to such cases by splitting large graph into several sub-graphs. Assuming we use feature-wise encoding and it requires 5 cts (each with 4096 slots) to pack 1 feature. Accordingly, each feature will have 4 cts with fully packed 4096 nodes and I ct with partially packed 3333 nodes. To solve the problem under the constraint M < N, we split N as:
N x M R
where x = N mod M, R = N % M. Eq. 9 leads to one Rx sub-block matrix and x of M x F sub- block matrices. For the R x F matrix, we refer to Eq. to optimize the Rolation as N = R < M. For other M x sub-block matrices with N = M, we change the assumption from N < M to N = M. Then, again with our proposed Wio-Dimension Parallel-Packe ct, the total complexity of rotations becomes:
(M . /M) ((n 1) + 2(f - 1)) = F' (n 2f - 3)
(10)
The corner case f= is different from that in the discussion of optimization problem formulation. Because ct here is fully packed for n = M and does not have the data alignment issue. For n M, F' the total complexity of Rotation becomes:
F² (M
(11)
Except for this corner case n f- the total complexity reaches a minimum when n 2 We compare the previously proved minimum with the corner case n M, = here, and get the difference of rotations complexity as follows:
F' ((M 1)
1) - (2vM - -3)) = (M - 2VM 4) = F (V 2)2
(12)
In general, since M is always holds. Thus, when considering a M x F matrix, the proposed Two-Dimension Parallel-Packin can still reach the minimum
> 2 to guarantee security level 17 28), the above inequality 12
2
3.3 Interleaved Assembling
In GCN inference, the reduction in feature size may result in wasted slots in two-dimension parallel- packing. As the example shown in FigureBjb, we optimally encode 32 different features into one ciphertext at the beginning. After the feature extraction layer with 16 hidden units, the previous dense encoded ciphertext will have half of the slots turn to blank. These blank slots in ciphertext bring higher memory overhead, especially given that the adjacency matrix A is also encrypted, resulting in more CMult operations thus computational overhead. We propose interleaved assembling to solve this issue. Figure b)b shows our idea. We rotate the 2t2 that contains node 5-8's features by I slot and then add it with ct1 that contains node 1-4's features. After that, we have new ciphertext ct' that contains 8 nodes with 1 feature. Meanwhile, we multiply the two mask vectors with the ciphertexts for aubssquare matrix A1 (for node 1-4) and Ags (for node 5-8) and get an interleaved assembled ciphertext contains matrix An and A22. Then, by rotating ciphertext et' 3 times and performing element-wise multiplication with new diagonal-encoded ciphertexts of the matrix An and Azz, we could get the results- ciphereett ct' of node 1-4 with the matrix A₁ and node 5-8 with the matrix Aza simultaneously. In this way, the complexity of HE operations including both rotation and ciphertext multiplication can be reduced by half. After that, we repeat the steps to perform multiplication on ct' and ciphertext that contains A2I and A to get the ct2y Based on the formula ct" = cl's + p(el/g. 1), we get the final result ciphertext cl" that multiples matrix (A11, A12, A21, A22). By leveraging such an interleaved assembling, could achieve / times reduction of the total computational complexity, where I' is the number of features on the current ciphertext, and f is the number of features on the ciphertext before feature reduction.

---

Evaluation
the extreme cases when only the 4.1 Experiment Setup
Datasets. We adopt the Cora 32]. Citeseer || and Pubmed [32 scientific publication datasets for graph learning. The Cora, Citeseer, and Pubmed contain 2708, 3327, and 19717 publication nodes divided into 7, 6, and classes respectively. And each node consists of 1433, 3703, and 500 unique word features, respectively. To test the link prediction task 22 90% of edges are removed and all node features retained on all datasets.
Models. We train Graph Auto-Encoder (GAE) models with 2 hidden layers and activation layers on 3 different datasets, i.e., Cora, Citeseer, and Pubmed. The three models follow the same GAE architecture
[22]. and are implemented using the DGL library [33]. Table [ lists the model architecture and pertinent encryption parameters for encrypting both adjacency matrix A and feature matrix X. We use 2.² the non-linear function [TO] to replace the ReI.U activation and apply the ADAM optimizer to train the model for 200 epochs using learning rate of 0.01. The accuracy of each model (AUC in Link Prediction) is maintained at the original level.
Encryption parameters. For all tasks, we apply scaling factor A = 2000 to ensure the accuracy of the enerypted inference using CKKS. Each rescale consumes 30 bits of ciphertext modulus Q, and there are 6 times rescale and corresponding levels across the whole network. Thus, we set Q = 218, and the polynomial degree N 2 to guarantee a 128-bit bit security level. Additionally, the scale factor of mask plaintext used in comparison with E2DM [5] & uSCORE [3] is set to 215
Baseline designs. To better evaluate the proposed approach, develop several baselines, including:
Penguin-family. We implement several Penguin baselines by applying only our proposed two- dimension parallel- parallel-packing technique (see Sec. 3.2). nodes when optimizing the packing format. Table lists the numbers of features/nodes selected. Here Penguin ff n) denotes that f features and n nodes are used in the corresponding baseline design. Note that, the baseline designs with f feature-wise or mode packing method is used.
3.2.. We set up different pairs of features and
Penguin+IA. We develop two Penguin+IA baselines by further applying the proposed Interleaved Assembling (IA) technique (see Sec. 3.3 to the Penguin-faid famill.
We also implement a set of state-of-the-art secure matrix matrix multiplication solutions, which include Gazelle [17], HElayers M. E2DM [15] and uSCORE [13. To ensure fair comparison, we do not apply the activation pruning technique for multiplicative level reduction across all
implementations 28 as this technique orthogonal our proposed solutions.
Measurements. We use inference latency as our main performance metric, which averaged over 20 simulations. Besides, we record the Homomorphic Operation Count (HOC), including the number of rotations (Rotation), the number of ciphertext multiplications (CMulr), etc. We also calibrate the numbers of ciphertexts and memory usage. A lower number of these metrics indicates better performance.
Environment. We conduct all experiments on machine equipped with Threadripper 3975WX CPU using the single thread setting the inference latency and train these GAE models with 2 Nvidia 3090 GPUs We use Microsoft SEAL version 3.7.2 31 to implement the RNS-variant of CKKS 5 scheme.
Table 1: Model and encryption parameters.
# I Layers
Accuracy
Encryption Parameters
Mult Level
Security Level
Dataset
Hiddenl
Hidden2
Activation
(AUC)
N
Q
P
Cora Citeseer
0,974
32
16
0.747
8192
218
30
128-bit
PubMed
0.858

---

Table 2: Ablation study of Two-Dimension Parallel-Packing and Interleaved Assembling.
Dataset
Packing-Format Format
Rot
CMult
HOC
Others
of Cipheriexts
Memory (GB)
Latency (8)
Speedup (x)
Penguin([433.1)
1048K
74K
282K
2708-2708-2708
2.38
7018.31
Penguin( (. 2708)
260K
130K
223K
1433-32-16
1.82
2475.78
2.83
Penguin((6,256)
9.7K
9.3K
157k
990-22-11
0.49
678.
10.35
Corn
Penguin(32,128)
8.3K
124K
188K
990-22-22
0.65
871.15
8.06
Penguin(64 64)
1650.28
Penguin(32,128H4
6.9K
9.3K
157K
990-22-11
0.49
660.67
10.62
Ponguin(64.64)+4A
10.3K
9.3K
220k
989-22-11
693.13
Pengumi(7003.1
1521K
1110K
3852K
3327-3327-332
2.92
9240,10
Penguin 3327)
Penguin; 16,256)
110K
130K
324K
3016-26-13
1.40
950.30
9.72
Cieeseer
Penguin(
9.8K
173K
367K
3016-26-26
1225.05
7.54
Penguin((64.64 644
16.3K
346K
734K
3016-52-52
2,51
2429 47
3,80
Penguin(3221188)
7.4K
324K
3016-26-13
Ponguin(64.64)41.
12K
130K
387K
3016-26-13
1.39
982.08
9.41
Penguint 19717.1)
5974K
817K
12687K
0917-19717-19771
Penguin (1, 500)
1106K
4732K
4897K
1600-660-0
17.3
37727 58
1.18
PuhMed
Penguin(16,25)
69K
4673K
4837K
2496-156-78
3.76
30906 28663
1.44
Penguin(32, 128)
59K
615IK
6314K
2480-155-155
11.6
40474,
1.10
Penguin(64, (44)
117K
1222IK
12547K
2472.309-309
42.9
80424.70
0,55
Penguin(32, 128)+AA
49K
4633K
4794K
2480 155-78
3.76
30522.43
1.46
Penguin(64..64)+4
73K
4633K
4954K
2472-155-78
3.75
30701.59
1.45
4.2 Evaluation Results
4.2.1
Two-Dimension Parallel-Packing
Table presents our evaluation results of the proposed two-dimension parallel-packing and interleaved assembling approach. We find that the packing format Penguin(J, 1) performs the worst on the three datasets due to having the largest number of HOCs and no slot packing optimization. This results in significant latency and memory overhcad. In particular, since PubMed contains more encrypted features (number of cts), the same design performs worse on PubMed than on the other two datasets. We use this Penguin( (f
as the baseline to compare the speed of other approaches.
Our results clearly show that our proposed two-dimension porallel-packing method can significantly reduce the HOCs (especially the number of rotations) and the number of ciphertexts. For example, on Cora dataset, our Penguin(16, 256), Penguin(S 128), and Penguin(64) 64) designs can reduce the number of rotations from 1048K to 9.7K, 8.3K, and 13.5K, respectively, thus reducing memory usage by ~ 79%, ~ 76%, and 47%, and reaching ~ 10.35x, 8.06x, and ~ 4.25x speed up, respectively.
In particular, the results we observed are well consistent with the theoretical analysis. For example, with MM
n 4096, 2f, we have the theoretical minimum smin /2048 45 (see Section 3.2 We can observe that the baseline Penguin 128) with f 32, n = 128 is very close the theoretical minimum and achieves the best results among the three designs. Meanwhile, other HOCs besides Rotation may increase under the optimal packing and affect the overall latency. For example, Penguin(322 128) yields more ciphertext multiplication (CMult) than Penguin( 256) due to wasted slots from feature reduction, which can be further optimized using the proposed Interleaved Assembling method.
Moreover, as our discussion of large graph in Section 3.2 indicates, all designs exhibit significantly worse performance the PubMed dataset compared the other two datasets. This is because the number of nodes in PubMed is significantly larger than the size of ciphertext (19717 >> 4096), which means that needs be multiplied with large 19717 19717 adjacency matrix. Therefore, the number of CMult > number of Rot. However, our proposed packing technique can still improve the performance in such cases.
4.2.2 Interleaved Assembling
Table 2 also reports the evaluation results of incorporating the two-dimensional parallel packing
and interleaved assembly methods. For example, in Cora, the number rotations, the number of CMult, and the number of other HOCs in the Penguin 128) + 7 design are further reduced parallel-packing only Penguin 128).
by 1.4K, 114.7K, and 31K, respectively, compared This makes Penguin (32, 128) + LA the best design on all datasets, i.c., with the minimum memory

---

Table 3: Compare with the state-of sere--of-hehaarr
Dataset
Method
Security Level
Latency (8)
Amortized Latency
Speedup (x)
Gazelle 17
128-bit
3832.36
1.42
Cora
E2DM(64) 15
98-bit
3150.74
1.16
1.22
HElayers 1
128-bit
2102.47
0.78
1.82
USCORE(32.128))
98-bit
1727.12
0.64
2.22
Penguin(32,118))-1
128-hit
660.57
5.92
Gazelle [i7]
128-hit
4727.94
1.42
Citeseer
E2DM((4) [5
98-bit
4561.15
1.37
1.04
HElayers [
128-bit
3044.58
0.92
1.54
USCORE(32.128) [k]
98-bit
2377.50
0.72
1.97
Penguin(32,1285++1A
128-bit
928.10
0.28
5.07
Gazelle [7]
128-bit
158655.54
Puhmed
E2DM((64) L51
98-bit
154530.49
7.84
1.03
HElayers 1
128-bit
103283.56
5.24
1.54
uSCORE((3,128) 133
98-bit
78843.49
4.00
2.01
Peng
128-bit
30522.43
1.55
5.19
usage of 0.49GB, 1.39GB, and 3.76GB and a 10.62x, 9.96x, and 1.46x speedup on dataset Cora, Citeseer, and PubMed, respectively. These results illustrate that proposed interleaved assembly can effectively reduce the wasted empty slots and save the number of ciphertexts selected in the computation, thus significantly improving the efficiency based on the SIMD.
4.2.3 Compare with State-of-the-art Solutions
In our evaluation, we conduct comparative analysis of our best-designed model, Penguin(32,, (32, 128) IA with several state-of-the-art (SOTA) solutions, including Gazelle [17), HElayers [1] E2DM [[S and uSCORE [3. All these SOTA solutions can speed up HE-GCN inference with optimized matrix-matrix multiplication. The results are summarized in Table
is worth noting that our approach uses encryption parameters which offer 128-bit security level. This security level is higher than that of the other two SOTA solutions, which can only guarantee 98-bit security level and require more multiplicative levels mask the plaintexts. For a fair comparison, we measure the amortized latency-the time required for link predictions of single node. As reported in Table 3 our method achieves an amortized latency 0.24s on Cora, which is 5.92x. 4.83x, 3.25x and 2.67% x faster than that of Gazelle, E2DM, HElayers and uSCORE, respectively. The similar improvement can observed across the Citeseer and PubMed.
The superiority of our method over other SOTA solutions can be attributed to two key factors:
The first reason is that all prior approaches primarily designed solve the single matrix-matrix multiplication problem instead of two-way matrix multiplications GCN inference. In GCN inference, the computation pattern mainly consists of two computational components-the common FC layer for graph feature aggregation (X W) and the adjacency matrix multiplication for graph node aggregation (A X). These two components represent distinct and orthogonal computation patterns for the input feature map. Consequently, optimizing only one of these directions leads to sub-optimal performance. In contrast, proposed "Penguin" which incorporates two-way parallel encoding and an optimized sub-block matrix size, offers superior performance with theoretical guarantees.
The second compelling factor contributing to the excellence of our approach is the adaptability to address the issue wasted slots ciphertext, a capability notably absent in prior methods. In studies such as [15] [3), traditional matrix- matrix-muliplication methods establish sub-block matrix partitions based on square or rectangular sub-block matrices determined by the input weight matrix size. However, these conventional methods face challenges in effectively managing the problem of wasted slots that arise after feature aggregation in Graph Convolutional Network (GCN) inference. As confirmed in Table 3] our two-way parallel packing method substantially improves HE-GCN inference by leveraging the Interleaved Assembling technique that can effectively minimize the wasted slots. This, in turn, leads to extra memory space and HOC reduction.
Putting these together, our method clearly demonstrates its advantage over SOTA solutions in accelerating HE-GCN inference.

---

5 Related Work
CryptoNets [T0] is the first work that demonstrates the feasibility of building privacy-preserye machine learning (PPML) by HE. However, the long inference latency and the inflexible packing format make it hard to be applied to large-scale models and datasets. Another following work named SHE [25], translates the nonlinear ReLU and Max Pooling operations as Boolean operations to support the TFHE-based M PPML without modifying the pretrained models. There also exist many multi-party computation (MPC) solutions that combine the two- party computation protocols [36]
with HE frameworks to achieve the low inference latency [30 26 24 27 However, they suffer from high communication overhead incurred by data transfer between multiple parties. Recent studies such as LoLaa 4 CHET ( and HEAR (0) leverage the eiphertext packing technique to place multiple data in the same ciphertext so that HE operations can be conducted efficiently via single instruction multiple data (SIMD) for accelerating HE-based CNN inference. These approaches are often not applicable between the GCN and CNN. CryptoGCN (28) is the first attempt to build HE-based PPML for GCNs. It packs the ciphertexts from individual node relieve the adjacency matrix multiplication overhead. However, they assume the adjacency matrix as plaintext, which is not applicable to dynamic graph settings which require protecting both graph structure and features like our work.
optimal to GCN inference due to the very different computation patterns
Cheetah 14 aims to eliminate the need of costly rotation in HE-matrix multiplication. The basic idea is to replace the dot-sum operation with two polynomials multiplications. However, it requires communication between the client and server to perform ciphertext decryption and re-encryption after each layer computation, c.g. after a convolutional layer. In contrast, approach operates within a "HE without-client-add" setting. Here, the server only requires the client to encrypt and send data to the server once, after which the server can perform the whole computation of inference and only send the final encrypted result back to the client. It does not require the frequent communication between client and server like [14]. Therefore, our work focuses on HE computation optimization. In our view, our solution and [4]'s ' MPC+HE setting represent two distinct directions to realize PPML. Each approach is tailored for different private inference scenarios. Hence, conducting direct comparison between our method and the approach in [14) could be challenging since they are designed for different purposes and provide distinct advantages.
Gazelle 17 is a hybrid matrix multiplication algorithm based on mixture of naive implementation and diagonal encoding method [12. It is designed to handle the general matrix multiplication that occurs in FC layers, where the output dimension is smaller than the input dimension. Additionally, E2DM 13 and uSCORE [13 address encrypted matrix-matrix multiplication optimization by breaking down the problem into small square matrix multiplications and facilitating consecutive matrix multiplications. HElayess (. on the other hand, leverages a tiles tensor-basee matrix- multiplication technique for multiplying two square matrices and consumes less multiplicative depth compared to (15). While these general solutions have proven effective in various contexts, their efficiency is limited when applied to accelerate Homomorphic Encryption-base Graph Convolutional Network (HE-GCN) inference, as detailed in Section 4.2.
6 Conclusion
In this paper, we propose a two-dimension parallel packing technique for feature ciphertext by optimizing the feature matrix partition size and further propose an interleaved assembling technique to merge ciphertexts that have wasted slots from feature reduction in rKKS-based secure GCN inference. These techniques can better save ciphertext memory and effectively reduce the number of homomorphic operations required. Experimental results based on the GAEs for link prediction and 3 popular graph datasets show that our solution can speed up the latency of the secure GCN inference by 10x and reduce the memory requirement by more than 79%, greatly outperforming the state-of-the-arr solutions.
7
Acknowledgment
We thank all anonymous reviewers for their constructive comments and suggestions on this work. This work is partially supported by the National Science Foundation (NSF) under Grants No. CNS- 2348733 and CNS- 2349538.
10

---

References
[1] Ehud Aharoni, Allon Adir, Moran Baruch, Nir Drucker, Gilad Ezov, Ariel Farkash, Lev Greenberg, Ramy Masalha, Guy Moshkowich, Dov Murik, et al. Helayers: A tile tensors framework for large neural networks on encrypted data. Proceedings on Privacy Enhancing Technologies, 1(1):325-342, 2023.
[2] Fabian Boemer, Anamaria Costache, Rosario Cammarota, and Casimir Wierzynski. ngraph-he2: high-throughpu framework for neural network inference on encrypted data. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 45-56, 2019.
[3] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transuctions on Computation Theory (TOCT), 6(3):1 36, 2014.
[4] Alon Brutzkus, Ran Baald-BBcchrch, and Oren Elisha. Low latency privacy preserving inference.
In International Conference on Machine Learning, pages 812 821. PMLR, 2019.
[5] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full ms variant of approximate homomorphic encryption. In International Conference Selected Areas in Cryptography, pages 347-368. Springer, 2018.
[6] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409-437, Springer, 2017.
[7] Ilriaa Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Thee: fast fully homomorphic encryption over the torus. Journal of Cryptology. 33(1):34-91, 2020.
[8] Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. Chet: an optimizing compiler for fully- hollomhhomooopiic neural- network inferencing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 142-156 156, 2019.
[9] Craig Gentry. A fully homomorphic encryption scheme. Stanford university, 2009.
[10] Ran BichadBachhrac, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMLR, 2016.
[11] Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[12] Shai Halevi and Victor Shoup. Algorithms in helib. In Annual Cryptology Conference, pages 554-50 571. Springer, 2014.
[13] Zhicong Huang, Cheng Hong, Wen-jie Lu, Chenkai Weng, and Hunter Qu More efficient secure matrix multiplication for unbalanced recommender systems. IEEE Transactions on Dependable and Secure Computing, 2021.
[14] Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding. Cheetah: Lean and fast secure two-party deep neural network inference. IACR Cryptol. ePrint Arch., 2022:207, 2022.
[15] Xiaoqian Jiang, Miran Kim, Kristin Lauter, and Yongsoo Song. Secure outsourced matrix computation and application to neural networks. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 1209-1222, 2018.
[16] Wonkyung Jung, Eojin Lee, Sangpyo Kim, Jongmin Kim, Namhoon Kim, Keewoo Lee, Chohong Min, Jung Hee Cheon, and Jung Ho Ahn. Accelerating fully homomorphic en- cryption through architecture-centric analysis and optimization. IEEE Access, 9:98772-98789, 2021.
11

---

[17] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. {GAZELLE); A low latency framework for secure neural network inference. 27th USENIX Security Symposium (USENIX Security 18), pages 1651-1669, 2018.
[18] Oussema Keskes and Rita Noumeir. Vision-based fall detection using st-gen. IEEE Access, 9:28224-28236, 2021.
[19] Miran Kim, Xiaoqian Jiang, Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Hear: Human action recognition via neural networks on homomorphically encrypted data. preprint arXiv:210..0114, 2021.
[20] Miran Kim, Xiaoqian Jiang. Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Secure human action recognition by encrypted neural network inference. Nature communications, 13(1):1-13, 2022.
[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXi:: 2016.
[22] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.073000 2016.
[23] Eunsang Lee, Joon- Woo Lee, Junghyun Lee, Young-Sik Kim, Yongjune Kim, Jong-Scon No, and Woosuk Choi. Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In International Conference on Machine Learning, pages 12403-12444 12422. PMLR, 2022.
[24] Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pages 1199-31,2220 2017.
[25] Qian Lou and Lei Jiang. She: A fast and accurate deep neural network for encrypted data. Advances in Neural Information Processing Systems, 32, 2019.
[26] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Symposium (USENIX Security 20), pages 2505-2522, 2020.
[27] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable
machine learning. In 2017 IEEE symposium security and privacy (SP), pages 19-38. IEEE, 2017.
[28] Ran Ran, Wei Wang, Quan Gang, Jieming Yin, Nuo Xu, and Wujie Wen. CryptoGCN: Fast and scalable homomorphically encrypted graph convolutional network inference. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[29] Ronald L. Rivest Len Adleman, Michael I. Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169-180, 1978.
[30] Bita Darvish Rouhani, M Sadegh Riazi, and Farinaz Koushanfar. Deepsecure: Scalable provably- secure deep learning. In Proceedings of the 55th annual design automation conference, pages 1-6, 2018.
[31] Microsoft SEAL (release 3.7), https://gituub.cc///ccccoofof//s September 2021.
Microsoft Research, Redmond, WA.
[32] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getvor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-5) 93, 2008.
[33] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. preprint arXiv: 19090013,, 2019.
12

---

[34] Le Wu, Peijie Sun, Richang Hong, Yanjie Fu, Xiting Wang, and Meng Wang. Socialgen: An efficient graph convolutional network based model for social recommendation. arXiv preprint 10l.:/81100211 2018.
[35] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: a survey, ACM Computing Surveys (CSUR), 2020.
[36] Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), pages 162-167. IEEE, 1986.
13


Reviews:
[{"review_id": "XBDIiJAWKF", "reviewer": "Reviewer_RE11", "summary": "The paper proposes a framework for optimizing latency in secure inference of GNNs. The authors propose a CKKS based packing scheme that is tailored for the structure of operations applied in Graph Convolution Networks. This appears to be the first work that considers both adjacency matrix and the feature matrix as private.", "questions": "None", "limitations": "I could not find any discussion on limitations by the authors even though they claim it in the submission form.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The optimizations for parallel packing introduced in this work are well motivated and justified with experimental data.\n2. The technique provides a significant latency improvement over existing matrix multiplication techniques empirically.\n3. I found the overall in-depth analysis of GCN computation and utilizing it for optimizing packing and reducing wasted operations with interleaved assembling to be well designed.", "weaknesses": "1. I wonder if a fair evaluation would include cryptoGCNs with encrypted adjacency matrix.\n2. The latency is extremely high for practical purposes, however, there isn't much work in this specific problem therefore it is difficult to understand the difficulty of the task.\n3. How does this technique compare with SecGNN[1]? (Ignoring the training aspect)\n\nReferences -\n1. Wang, Songlei, Yifeng Zheng, and Xiaohua Jia. \"SecGNN: Privacy-preserving graph neural network training and inference as a cloud service.\" IEEE Transactions on Services Computing (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Response to Weakness 1-if a fair evaluation would include CryptoGCN:**\n\nThanks for your comments. Our experiments have included a fair comparison with CryptoGCN. For CryptoGCN, the key idea is to use Adjacency Matrix Aware (AMA) ciphertext encoding technique, followed by the patterned sparse matrix partitioning to take advantage of the sparsity of unencrypted adjacency matrix A, so as to reduce the costly HE operations in GCN. \nWhile deploying AMA encoding technique is still applicable when both graph node features and structure are encrypted, we would like to emphasize that the patterned sparse matrix partitioning technique is not applicable since here the adjacency matrix A is encrypted and the sparsity cannot be exploited. Therefore, to make our work comparable with CryptoGCN under the same setting (both encrypted features and adjacency matrix), in our experiments, we implemented CrytoGCN’s AMA encoding format as the node-wise format which encodes the features from the same node into one ciphertext (See Table 2,  Cora-Penguin(1433,1), Citeseer-Penguin(3703,1), and PubMed-Penguin(19717,1)). As Table 2 shows, the performance of our method (Penguin 32,128) is much better than those with the AMA encoding from CryptoGCN. The reason is twofold: 1) encrypted adjacency matrix does not offer the public sparsity information that can be exploited by CryptoGCN; 2) two-dimensional optimization (feature-node AXW) instead of CryptoGCN’s AMA encoding focusing on one-direction optimization (adjacency matrix multiplication AX) only.\n\n**2. Response to Weakness 2-concern about the difficulty about our research problem:**\n\nHomomorphic Encryption (HE) is a promising technology to realize the PPML inference. Also the well-known challenge of HE is the large computation and memory (thus latency) overhead especially facing machine learning.This leads to the prolonged inference latency which greatly hinders its practicality at the current stage, as illustrated in many prior HE-based PPML for Deep CNN models, e.g. ResNet-20 [4,5]. Compared with HE-based CNNs, HE-based GCN is an emerging area that has been far less explored so far. To the best of our knowledge, the SOTA work for HE-based GCN inference-CryptoGCN requires an inference latency 4273.89s for 25✖25 adjacency matrix due to the unique and expensive matrix-matrix multiplications in the encryption domain. Compared with CryptoGCN, our work involves much larger adjacency matrices (e.g. 19717✖19717), of which the computation and latency overhead is expected to be much higher. While our work has not yet reached the latency requirement of practical applications, it represents an early attempt along this challenging direction. We believe there is room for further performance improvement from the aspects of algorithm and hardware. For example, with the advancement of dedicated HE hardware accelerators [2,3], the HE operations latencies could be further reduced.\n\n**3. Response to Weakness 3-comparison with SecGNN:**\n\nSecGNN is based on a technique called additive secret-sharing in a three-servers setting where the overhead mainly stems from the communication between different servers, as it involves the interaction among servers. However, for our HE without-client-aid setting (no communication between server and client during inference), the overhead is mainly from the HE operations (e.g. rotation and ciphertext-ciphertext multiplication) for completing the required computations on the server. These two methods represent two directions for achieving PPML under different application scenarios or settings, of which the former is bottlenecked by communication while the latter is bottlenecked by computation. Therefore, we believe it is difficult to directly compare them.\n\nReference:\n\n[1] Lee, Eunsang, et al. \"Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Samardzic, Nikola, et al. \"F1: A fast and programmable accelerator for fully homomorphic encryption.\" MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture. 2021.\n\n[3] Kim, Sangpyo, et al. \"Bts: An accelerator for bootstrappable fully homomorphic encryption.\" Proceedings of the 49th Annual International Symposium on Computer Architecture. 2022.\n\n[4] Lee, Eunsang, et al. \"Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions.\" International Conference on Machine Learning. PMLR, 2022.\n\n[5] Ran, Ran, et al. \"SpENCNN: Orchestrating Encoding and Sparsity for Fast Homomorphically Encrypted Neural Network Inference.\" International Conference on Machine Learning. PMLR, 2023.\n"}, {"review_id": "9U917oRcxp", "reviewer": "Reviewer_pXg9", "summary": "This paper proposed an efficient data-packing method for cryptographically-secure inference on GCN, where the feature matrix and adjacency matrix are encrypted using homomorphic encryption (HE). The problem statement is interesting as the GCNs typically exhibit a significant sparsity level, increasing the number of rotations and, consequently, causing an increase in the HE latency.\n\n\n\n", "questions": "Can we employ the rotation-free HE implementation [1] for faster private inference on GCNs? How does the sparsity in GCN impact the solution proposed for making HE rotation free [1]?  \n\n\n\n\n1.  Huang et al., \"Cheetah: Lean and fast secure two-party deep neural network inference,\" USENIX Security 2022.", "limitations": "Not addressed in the paper. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The proposed solution is *novel* for dealing with rotation inefficiency in HE, which stems from the high degree of sparsity in GCN. \n\n\n2. The presentation of the proposed solution is excellent, and the paper provides clear and detailed information about the experimental methodology, including the specific parameters of HE. ", "weaknesses": "\n**Comparison with SOTA data packing method**\nTable 3 in the paper does not compare the proposed solution and the state-of-the-art HE-packing method [1]. It is worth noting that the HELayer [1] incorporates a packing optimizer that selects the most efficient packing method to optimize latency and memory usage in HE convolution operations. Conducting a study on the suitability of the HELayer packing for graph convolution and their comparison with the proposed solution can provide valuable insights.\n\n**Lack of experiments for showing the impact of sparsity on the efficacy of the proposed packing method**\nAn experimental study and discussion on the impact of sparsity on the effectiveness of existing/state-of-the-art HE packing methods versus the proposed methods in GCNs would provide valuable insights. \n\n\n**CryptoGCN + Penguin** \nIncluding an experimental analysis in the paper would have been beneficial to understand how the proposed approach in CryptoGCN (NeurIPS'22) for reducing the multiplicative depth can further enhance the efficiency of the proposed HE packing method.\n\n\n1. Aharoni et al., \"HElayers: A tile tensors framework for large neural networks on encrypted data, \" PoPETs 2023. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Response to Weakness 1-Comparison with SOTA data packing method:**\n\nThanks for your constructive comments. We have conducted the experiments and reported the comparison results with HElayers in Table 1 below.  As Table 1 shows, our solution–Penguin beats HElayers consistently across the datasets because:  1) Principally, HElayers [2] focuses on the computation of a fully-connected layer which is a one-direction (single) matrix multiplication. However, GCN inference has different bottlenecked computation patterns, e.g. two-way matrix multiplication (AXW) in each layer. Our proposed method targets an optimization problem for a two-way matrix-matrix multiplication (adjacency matrix multiplication and fully-connected layer weight matrix multiplication) and comes up with the best matrix blocking size with theoretical guarantee. 2) In HElayers, their matrix-multiplication method has the same computation complexity as E2DM [3] (in section 8.1 of [2]) and also requires a series of fixed square sub-blocks matrices to replace the original matrix multiplication. Thus,  similar to E2DM (a benchmark we compared in Table 3 in our paper), the proposed matrix-multiplication method in [2] cannot handle the problem of the wasted slots. Therefore, as expected in Table 1, our two-way parallel packing can achieve much better HE-GCN inference than that of HElayers. We will incorporate such discussions in the experiments based on the reviewer’s advice.\n\n**Table 1**\n|  | Cora | Citeseer | PubMed |\n|---|---|---|---|\n| HElayers | 2102.47s| 3044.58s| 103283.56s|\n| Penguin(32,128)+IA| 660.67s| 928.1s| 30522.43s|\n\n\n**2. Response to Weakness 2-Lack of experiments for showing the impact of sparsity on the efficacy of the proposed packing method**\n\nWe appreciate your question regarding the impact of sparsity on the efficacy of the packing method. However,  we would like to clarify that in this work, we assume the adjacency matrices (A) are encrypted and the actual element value in the matrix could not be seen by the server. In other words, both adjacency matrix A and feature matrix X are encrypted, which is different from that of CryptoGCN-adjacency matrix A is a plaintext matrix whose sparsity can be exploited along with ciphertext packing for speedup. Thus, we can not leverage the sparsity of the adjacency matrix to skip redundant HE operations like CryptoGCN does. \n\n**3. Response to Weakness 3-CryptoGCN + Penguin**\n\nThanks for your suggestion. Actually we have tried to reduce the activation layers of our evaluated GNN models for multiplicative depth reduction and the corresponding accuracy and latency results are reported in Table 2 and 3 below respectively. As Table 2 shows, the accuracy drops when pruning 2 activations, especially for the Citeseer dataset. If we prune two activation layers, the saved two levels would reduce the requirement of encryption parameter ciphertext modulus Q from 218 to 158. However, this could not allow us to change the polynomial degree from 8192 to 4096 like CryptoGCN  because we still have to use N=8192 to maintain at least 128 bits security level for current Q [1]. As Table 3 illustrates, it can still achieve latency reduction but the improvement is not as significant as that of CryptoGCN despite the more prominent accuracy drop.\n\n**Table 2**\n|  | Cora | Citeseer | PubMed |\n|---|---|---|---|\n| No activation pruning | 0.974 | 0.747 | 0.858 |\n| With 2 activations pruned| 0.958 | 0.659 | 0.855 |\n\n\n**Table 3**\n|  | Cora | Citeseer | PubMed |\n|---|---|---|---|\n| Q=218 | 660.67s| 928.1s| 30522.43s|\n| Q=188 | 453.56s | 642.4s| 20855.38s|\n| Q=158 | 353.07s| 501.51s| 16215.66s|\n\n**4. Response to Question 1-Rotation-free approaches**\n\nThanks for your interesting question. The rotation-free implementation by [1] is in a MPC+HE setting. It needs the client to do decryption and re-encryption for completing the computation process to achieve the rotation-free. In this way, the computation latency on the server can be low. However, this method comes at the cost of communication between server and client (one-layer computation with one-time communication). Also, the client needs to frequently decrypt and then re-encrypt the intermediate results sent by the server. In our work, we assume a HE without-client-aid setting and do not require the client to interact with the server during the inference. The setting and application scenario are different from that of MPC + HE. In our setting, the HE computation at the server, instead of communication, becomes the bottleneck. Therefore, we think the two approaches represent different directions to achieve the privacy-preserving machine learning applicable to different scenarios, and both solutions have pros and cons. In our view, it would be interesting to explore such a rotation-free solution for private GCN inference in future work.\n\nIn regard to the sparsity’s impact on rotation-free solution, our understanding is that if the assumption for the adjacency matrix is in non-encrypted status, we think it is still possible to use sparsity skip some operations, like two polynomial multiplications. However, in our work here, we would like to clarify that we cannot leverage the sparsity to skip HE operations as the adjacency matrix is encrypted.\n\nReference:\n\n[1] Laine, Kim. \"Simple encrypted arithmetic library 2.3. 1.\" Microsoft Research https://www. microsoft. com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1. pdf (2017).\n\n[2] Aharoni et al., \"HElayers: A tile tensors framework for large neural networks on encrypted data, \" PoPETs 2023.\n\n[3] Jiang, Xiaoqian, et al. \"Secure outsourced matrix computation and application to neural networks.\" Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018.\n\n"}, {"review_id": "bymetHaHz1", "reviewer": "Reviewer_MKSk", "summary": "The paper introduces Penguin, a novel HE-based ciphertext packing technique for accelerating GCN inference on encrypted graph data while ensuring data privacy. By exploiting the unique computation pattern of GCN layers, Penguin reduces computation and memory overhead associated with HE operations. The technique achieves significant speedup and reduction in computational memory overhead compared to state-of-the-art solutions. This work is the first to address the protection of both graph structure and features in accelerating HE-GCN inference on encrypted data.", "questions": "-", "limitations": "The paper could benefit from further discussion on the limitations and potential future directions of the proposed technique.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Introduces Penguin, a novel HE-based ciphertext packing technique for accelerating GCN inference on encrypted graph data.\nExploits the computation pattern of GCN layers to reduce computation and memory overhead associated with HE operations.\nProvides theoretical analysis and experimental validation to demonstrate the speedup achieved by Penguin.\nAchieves significant speedup and reduction in computational memory overhead compared to state-of-the-art solutions.\nAddresses the protection of both graph structure and features in HE-GCN inference on encrypted data.", "weaknesses": "It would be beneficial to provide more detailed comparisons with existing approaches to highlight the advantages of Penguin.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Weakness- More comparisons with other existing works:**\n\nThanks for your comments. In addition to the baselines E2DM[3], uSCORE[4], We have conducted additional experiments and reported the results comparisons with other existing relevant approaches (e.g. Gazelle [1] and HElayers [2]) in the following Table. In particular, HElayers [2] , a state-of-the-art HE Packing method suggested by Reviewer pXg9, Gazelle [1] is another work aiming to address the single matrix-multiplication problem in the general FC layer, suggested by Reviewer idN7. As Table 1 shows, our Penguin still achieves the best latency performance because it takes advantage of the unique computation pattern during the HE-GCN inference to significantly reduce the computation and memory overhead associated with HE operations. Following is the table showing the comparison results:\n\n**Table 1**\n|  | Cora | Citeseer | PubMed |\n|---|---|---|---|\n| Gazelle| 3832.36s| 4727.94s| 158655.54s|\n| HElayers | 2102.47s| 3044.58s| 103283.56s|\n| Penguin(32,128)+IA| 660.67s| 928.1s| 30522.43s|\n\n\n\nReferences:\n\n[1]Juvekar, Chiraag,Vinod Vaikuntanathan, and Anantha Chandrakasan. \"{GAZELLE}: A low latency framework for secure neural network inference.\" 27th USENIX Security Symposium (USENIX Security 18). 2018.\n\n[2]Aharoni et al., \"HElayers: A tile tensors framework for large neural networks on encrypted data, \" PoPETs 2023.\n\n[3] Jiang, Xiaoqian, et al. \"Secure outsourced matrix computation and application to neural networks.\" Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018.\n\n[4] Huang, Zhicong, et al. \"More efficient secure matrix multiplication for unbalanced recommender systems.\" IEEE Transactions on Dependable and Secure Computing (2021).\n"}, {"review_id": "J7lRV8gloe", "reviewer": "Reviewer_idN7", "summary": "To alleviate the dramatic computation and memory overhead in HE-based GCN inference, this paper proposes a new HE-based ciphertext packing technique named Penguin. Penguin focuses on a sequence of matrix-matrix multiplications which is the bottleneck during private GCN inference. Thus, it employs an effective two-dimension parallel packing technique and an interleaved assembly technique to reduce the number of HE rotations while make use of the blank slots in polynomials. This paper also provides theoretical analysis and experimental validation to demonstrate the speedup achieved by Penguin in accelerating private GCN inference. Results show that Penguin can achieve up to ∼ 10× speedup and around ∼ 79% reduction in computational memory overhead, outperforming SOTA solutions.", "questions": "1. How does the proposed method compare to the coefficient encoding-based method like Cheetah?\n\n2. How about the comparison with stronger baselines like CryptoGCN that optimizes HE for GCN?\n\n3. In Table 2, Penguin(32,128)+IA significantly reduces the number of CMults over 10 times, but the latency only reduces 20% compared to Penguin(32,128). Why is this situation happening? ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Reasonable motivation. This paper first analyzes the latency breakdown in private GCN inference and finds that the bottleneck is a sequence of matrix-matrix multiplications $A\\cdot X\\cdot W$ due to a great deal of Rotations and CMults. Additionally, the inefficient packing method is the deeper reason. Therefore, this paper proposes several packing techniques to solve this issue.\n\n2. Direct and effective method. Based on the node-wise and feature-wise packing, this paper proposes Two-Dimension Parallel-Packing which selects tiling size to minimize the number of rotations. What's more, when feature size is reduced in aggregation, Interleaved Assembling can be used to make a denser packing. Experiments demonstrate the effectiveness of the two methods.\n\n3. Well written. The writing quality of the paper is excellent, with logical coherence.\n", "weaknesses": "1. Missing comparison with several highly related works. The node-wise and feature-wise packing methods described in Sec 3 are actually common in SIMD-based HE methods. Thus, I think this paper needs to have a comparison with SIMD-based work like Gazelle [1].\n\n[1] Juvekar, Chiraag, Vinod Vaikuntanathan, and Anantha Chandrakasan. \"{GAZELLE}: A low latency framework for secure neural network inference.\" 27th USENIX Security Symposium (USENIX Security 18). 2018.\n\n[2] Reagen, Brandon, et al. \"Cheetah: Optimizing and accelerating homomorphic encryption for private inference.\" 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 2021.\n\n[3] Hao, Meng, et al. \"Iron: Private inference on transformers.\" Advances in Neural Information Processing Systems 35 (2022): 15718-15731.\n\n2. There exists another type of method named coefficient encoding which has extremely high performance in matrix-matrix and matrix-vector multiplication[2,3]. So the SOTA methods claimed by the author are questionable.\n\n3. The baseline of the paper is not very strong. How does the proposed method compare to CryptoGCN and other works that directly optimize HE for GCN instead of CNN?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Response to Weakness 1-Missing Comparison:**\n\nThanks for your constructive feedback. We have conducted additional experiments and reported the comparison results with Gazelle [1] in Table 1 below. As Table 1 shows, our proposed solution outperforms that of Gazelle across all three datasets. The reason is as follows:  the proposed hybrid approach in Gazelle[1] is mainly designed to solve the single matrix-multiplication problem in the general FC layer (input feature > output feature). However, GCN inference contains two parts of computation-one is FC layer (XW) and the other is adjacency matrix multiplication (AX) that is a square matrix (fixed size). When computing with an adjacency matrix, the proposed method in [1] would not optimize its packing but instead just adopt the diagonal wise-encoding method from [2]. Thus, our proposed Penguin-two-way parallel-encoding with optimized sub-block matrix size could perform better here.\n\n**Table 1**\n|  | Cora | Citeseer | PubMed |\n|---|---|---|---|\n| Gazelle| 3832.36s| 4727.94s| 158655.54s|\n| Penguin(32,128)+IA| 660.67s| 928.1s| 30522.43s|\n\n**2. Response to Weakness 2 and Question 1-Why CKKS not coefficient encoding method [3]:**\n\nThanks for your constructive comments regarding coefficient-encoding work. There are several differences between our solution and the referred coefficient encoding work. First, \nour work has a different threat model setting compared to [3]. The coefficient encoding rotation-free HE in [3] requires clients assistance for private inference, where our work assumes the client doesn’t have much computation capability and would not participate in the inference computation process. The method used in [3] is BFV, in which it requires the client to do the decryption for the extracted LWE ciphertext, re-encryption for intermediate results and then send the new ciphertexts to the server, then the server can perform the next layer’s computation. As a result, communication is the bottleneck in their proposed method [3]. However, in our CKKS HE without-client-aid setting, the server side only requires the client to encrypt and send data to the server once, and the server can perform the computation one time and only send the final encrypted result to the client. It does not require the frequent communication between client and server like [3]. Therefore, HE computation, instead of communication, becomes the bottleneck. In our view, our HE without-client-aid setting and [3]’s MPC+HE setting represent two orthogonal directions to realize PPML, and they are suitable for different private inference scenarios. Our paper aims at reducing the server’s computation overhead under the HE without-client-aid setting. It is very difficult to directly compare these two approaches, as both have pros and cons under different assumptions. In the future, it would be interesting to explore the coefficient encoding method for HE-based GCN inference. We will include such discussion in the related work based on the reviewer’s further suggestions.\n\n**3. Response to Weakness 3 and Question 2-Comparison with CryptoGCN:**\n\nThanks for your comments. Our experiments have included a fair comparison with CryptoGCN. For CryptoGCN, the key idea is to use Adjacency Matrix Aware (AMA) ciphertext encoding technique, followed by the patterned sparse matrix partitioning to take advantage of the sparsity of unencrypted adjacency matrix A, so as to reduce the costly HE operations in GCN. \nWhile deploying AMA encoding technique is still applicable when both graph node features and structure are encrypted, we would like to emphasize that the patterned sparse matrix partitioning technique is not applicable since here the adjacency matrix A is encrypted and the sparsity cannot be exploited. Therefore, to make our work comparable with CryptoGCN under the same setting (both encrypted features and adjacency matrix), in our experiments, we implemented CrytoGCN’s AMA encoding format as the node-wise format which encodes the features from the same node into one ciphertext (See Table 2 in our paper,  Cora-Penguin(1433,1), Citeseer-Penguin(3703,1), and PubMed-Penguin(19717,1)). As Table 2 shows, the performance of our method (Penguin 32,128) is much better than those with the AMA encoding from CryptoGCN. The reason is twofold: 1) encrypted adjacency matrix does not offer the public sparsity information that can be exploited by CryptoGCN; 2) two-dimensional optimization (feature-node AXW) instead of CryptoGCN’s AMA encoding focusing on one-direction optimization (adjacency matrix multiplication AX) only.\n\n\n**4. Response to Question 3-concern about the weird data**\n\nThanks for your careful review. It is 93K instead of 9.3K. Sorry about the typo. We will fix this part in future revision of our manuscript.\n\nReference:\n\n[1]  Juvekar, Chiraag, Vinod Vaikuntanathan, and Anantha Chandrakasan. \"{GAZELLE}: A low latency framework for secure neural network inference.\" 27th USENIX Security Symposium (USENIX Security 18). 2018.\n\n[2] Halevi, Shai, and Victor Shoup. \"Algorithms in helib.\" Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34. Springer Berlin Heidelberg, 2014.\n\n[3] Huang, Zhicong, et al. \"Cheetah: Lean and fast secure {two-party} deep neural network inference.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.\n"}]

Author rebuttal:

Meta-review: The paper proposes an efficient HE-based GCN inference method, by exploiting the unique computation patterns of GCN layers.

Reviewers recognize the importance of the problem as well as the technical contributions. The authors addressed most of the concerns raised by the reviewers. They have also added additional experiments of comparison with the SOTA data packing method. The reviewers unanimously recommended accept after the rebuttal (6, 6, 5, 7). 

Please add the clarifications and additional experiments in the final version.
Decision: Accept (poster)