CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
Authors: Ran Ran
Wei Wang
Quan Gang
Jieming Yin
Nuo Xu
Wujie Wen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Cryptographic inference
ST-GCN
Ciphertext data formatting

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

CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
Ran Ran Lehigh University rar4180lehigh.ce edu
Nuo Xu Lehigh University nux2196lehigh. edu
Wei Wang Microsoft wewang30mi www.:mm.iioooooooooooooooooo.
Gang Quan
Jieming Yin Nanjing University of Posts and Telccommunications jieming yinênj edt. edu.
Wujie Wen Lehigh University
Florida International University gaquan0f iu. edu
suw2196lehigh. edu
Abstract
Recently cloud-based graph convolutional network (GCN) has demonstrated great success and potential in many privacy-sensitiv applications such as personal health- and financial systems. Despite its high inference accuracy and performance the cloud, maintaining data privacy in GCN inference, which is of paramount im- portance these practical applications, remains largely unexplored. In this paper, we take an initial attempt towards this and develop CryptoGCN-a homomorphic encryption (HE) based GCN inference framework. key to the success of our approach is to reduce the tremendous computational overhead for HE operations, which can be orders of magnitude higher than counterparts in the plaintext space. To this end, we develop solution that can effectively take advantage of the spar- sity of matrix operations in GCN inference to significantly reduce the encrypted computational overhead. Specifically, we propose novel Adjacency Matrix- Aware (AMA) data formatting method along with the AMA assisted patterned sparse matrix partitioning, exploit the complex graph structure and perform efficient matrix-matrix multiplication HE computation. In this way, the number of HE operations can be significantly reduced. We also develop a co-optimization framework that can explore the trade-offs among the accuracy, security level, and computational overhead by judicious pruning and polynomial approximation of activation modules GCNs. Based on the NTU-XVIEW skeleton joint dataset, i.c., the largest dataset evaluated homomorphically by far imental results demonstrate that CryptoGCN outperforms state-of-the-art solutions in terms of the latency and number of homomorphic operations, i.e., achieving much as a 3.10x speedup on latency and reduces the total Homomorphic Operation Count (HOC) by 77.4% with a small accuracy loss of 1-1.5%. Our code is publicly available at https:: /ttp///gtttttttt www.tttu..oooaaaaaeeeeeeeeoeeaae
aware of, exper-
Introduction
Graph Convolutional Neural Networks 23 (GCNs) have recently emerged in machine learning and demonstrated superior performance in various privacy-sensitive applications such as human action recognition [35] 38), financial recommendation system [37), and autonomous driving (25). While it has been increasingly popular to deploy machine learning services the cloud, the cloud environment raises critical concerns for GCN-based privacy-sensinee services, since graph data usually contain considerable amount of sensitive information.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Recently, Homomorphic Encryption (HE) based private-preserving preserving machine learning (PPML) has emerged to be an effective way to protect the privacy of clients. Using HE, a client can encrypt the data and send it to the cloud. The cloud server directly operates on the encrypted data and sends the encrypted results back to the client, which can then be decrypted and used. As the data are encrypted throughout the entire process when it is out of the client's control, data privacy is greatly enhanced. The challenge, however, is to deal with the tremendously increased computational cost associated with the HE operations (e.g., rotations, multiplications, additions), which is orders of magnitude higher than that in the plaintext space 13 31 20)..
There exists flurry of work that aims to alleviate the computation overhead of HE-based PPML [ [ [3] 22 27]. However, these solutions are all focused on the traditional Convolutional Neural Network (CNN) models and are ineffective for GCNs because of major difference of computation pattern between GCN and CNN. That is, each graph convolution layer in the deep GCN model would involve unique adjacency matrix multiplication operation to incorporate the graphic information during the convolution. This additional matrix multiplication in GCN can significantly increase the required HE operations. As our profiling result in Fig. [a demonsttrss,, for a typical 64-channel-GCN layer with matrix size 25 x 25, the matrix multiplication can lead to a nearly 49 x increase in terms of homomorphic operation count (HOC) in the worst case. How to deal with the significantly increased HE operations in the GCN inferencing process presents a primary challenge. Furthermore, current HE frameworks, such as the Cheon Kii---i---i--i-- Kim-Song (CKKS) scheme (7] used by this work, are normally built on the so-called Leveled HE (LHE) 2 scheme, which has a limit on the maximum number of concatenated homomorphic multiplication operations. The extra multiplication operations in GCNs increase the multiplication depths of the total computation eircuit, leading to the requirement of larger encryption parameters (e.g. increased polynomial degree and primes) maintain the same security levels. As shown in Fig. [cl the choice of parameters for HE schemes not only affects the security level of the encryption but also has profound impacts on the latency of HE operations. How to judiciously choose the HE parameter to optimize the security, computational cost, and latency is also critical for effective and efficient GCN inferencing.
One intuitive approach to dealing with the adjacency matrix multiplication operation at each graph convolution layer is to employ the state-of-the-ee art encrypted matrix multiplication methods (e.g. [8] 19). However, these solutions can be problematic for deep GCN models because of increasing the total multiplication depths, e.g. by 3 8 and 6 [19], which leads
higher polynomial degree for encryption to maintain at least the same security level. From the comparison in Fig. [b] with no optimization, these results would be inferior to the method in [4]] which we used in our paper as the baseline results for comparison. Instead, we take advantage of the sparsity in the adjacency matrix, which is very common, especially for applications based on class of popular GCNs-Spatial- Temporal GCN (ST-GCN), and can dramatically reduce the number of HE operations.
In this paper, we have made the following contributions. First, we develop approach that can effectively take advantage of the sparsity of matrix operations in GCN inferencing that can signif- icantly reduce the computational overhead. As shown above, for GCN inferencing, the required matrix-matrix multiplication can lead to significantly increased HE operations. In the meantime, the matrix operation for GCN inferencing exhibits strong sparsity features, which can be exploited to reduce the computational overhead. To this end, we develop a novel GCN data formatting method, i.e., Adjacency Matrix A Aware (AMA) data formatting method support the associated multi-channel multi-batch convolution and matrix-matrix multiplications, which can exploit the single instruction multiple data (SIMD) structures in HE computation and thus greatly reduce the HE operations. Second, we also study how to better manage the HE computation numbers and levels for GCN infer- encing by judiciously pruning and approximation of the activation module in GCN and settings of HE parameters. We develop co-optimization framework that can help to explore the tradeoffs among security level, inference accuracy, and inference latency. Third, we conduct extensive experiments based on the NTU-XVIEW 34] skeleton joint [o 15 4. dataset. Our experimental results show that the AMA data formatting achieves latency speedup of up to 3.10x, and the Activation Pruning achieves as much as 2.29x x speedup for latency. To our best knowledge, this is the first work that builds the basba PPML pipeline for GCN-based models with HOC decrease by as much as 77. 77.44% compared to previous benchmarks.
2

---

wio Mutiplication Mabris Multification
security
ring
ring size- 32768
7552.969
3.0
20w1
5015.35
2.5
2.26
2.51
2.52
Homomorphh
1002
Latercce
Latency Rotatiie
2.0
4000
1.5
10c1:
2065.46
1.0
1000
2000
1863.95
0.5
0.0
PHut
Add
PHul
CHutt
HE aperotian
Matrix Nuttiplicarion Mecholls
HE operation
(a)
(b)
(c)
Figure 1: Motivation examples: (a) the number of HE operations increased at log scale (by 49x in total) due to involving an adjacent matrix-based matrix multiplication in a typical 64-channel GCN layer (detailed setting in Sec. 4 (b) Comparison with the state-of-the-an HE matrix multi- plication methods applied in the 64-STGCN-3 model (see Table 2 A 8 B
. C 14, D-Ours; (c) The latency of HE operations on a single ciphertext increased by up 2.52x (32K v.s. 16K, normalized to 16K) due to enlarging the polynomial degree. PMulr, Add, CMult and Rot represent multiplication, ciphertext addition, ciphertext-ciphereex multiplication and rota- tion, respectively (see Sec. P
19
Background and Related Work
Sempoal--emporal Graph Convolution Network. In this work, we focus class of popular Sea--ppaall--emmopee Graph Convolution Network (ST-GCN) [38]. ST-GCN mainly consists of two types of graph convolutions Spatial convolution and Temporal convolution, which aim to extract Spatial and Temporal information from the input graph data, respectively. The Spatial convolution can be expressed by Equation
H D6 3
XW,
Where indicates different sets of graph connections separated by a graph node partition strategy to better extract the Spatial information. is the input graph data. W, E RC represents set of filter parameters transform the input tensor features from C.n input channels to Cout output channels. Dj is the degree matrix. A, is the adjacency matrix with self-loop. The XW, term implemented by 2D-convolution with kernel size 1, then multiplied with the normalized
adjacency matrix D D, and finally the resulted data are summed up as output feature H. The Temporal convolution convolution operation performed on the same graph node data from different time slices.
CKKS Leveled Homomorphic Encryption Scheme. The Chhoo--Kim-Kim-S5 (CKKS) scheme 77.. which based on the hardness of ring learning with errors (RLWE) problem, is a leveled homomorphic encryption scheme that allows arithmetic operations encrypted data fixed-point numbers. CKKS provides configurable precision by taking the encryption noise [24] as natural error introduced the approximation computations and through dropping the least signifi- cant bits of computations via the rescaling of ciphertext. The supported homomorphic operations include the ciphertext addition Add(ct,, ct2), ciphertext multiplication CMult(ct,, ctz), scalar mul- tiplication PMulr(ct, pr), rotation Rot(ct, k) and rescaling Rescale(ct). The scalar multiplication to multiply a ciphertext with plaintext. The rotation to apply Galois automorphisms of the cyclotomic extension to the plaintext polynomials in encrypted form resulting in cyclic shift of the slot vector. For instance, (et, k) transforms an encryption (No, ..., UN/2-1) into an encryption of (uk,..., UN/2-1, 20 .... 1)-
Compared with unencrypted computations, CKKS introduces significant runtime and memory over- head. The use of packing, also referred to as batching, allows to pack of multiple data values into ciphertext so the encrypted computations can be done a Single Instruction Multiple Data (SIMD) manner. We use this property improve the amortized overhead in this paper.
The security level of the CKKS scheme is measured bits. With 128, will take around 2 128 operations to break the encryption. Throughout this paper, assume that N is the cyclotomic

---

polynomial degree. CKKS is leveled HE and the level of ciphertext (1) is defined as the number of successive multiplications that can be performed to the ciphertext without bootstrapping. The level is decreased by one through the rescaling operation after each homomorphic multiplication. If the level becomes zero, bootstrapping is needed to make this zero-level ciphertext a higher-level ciphertext to enable further homomorphic operations. In our work, we optimize the GCN network to have lower depth and select proper parameters to avoid the costly bootstrapping procedure.
Related Work. CryptoNets [3] is the first work that demonstrates the feasibility of building PPML by HE. CryproNets evaluates a 5-layer neural network with MNIST dataset and achieves 59000 image inferences within one hour. However, the long inference latency makes it hard to be applied to large-scale models and datasets. A recent work named SHE 19. translates the nonlinear ReLU and Max Pooling operations as Boolean operations to realize the TFHE- based PPML, and achieves the state-of-te the-art inference accuracy. However, SHE also incurs a high inference latency, where making prediction on CIFAR-10 10 image costs 2258 seconds. There also exist many MPC solutions which combine the two-party computation protocols (39 with HE frameworks to achieve the low inference
26 (3). However, they suffer from high communication overhead incurred by data transfer. For example, DeepSecure [32 needs to exchange 722GB of data between the client and the server for only 5-layer CNN inference on one MNIST image. Another approach [IO] employs the sparsity location vector to avoid unnecessary computations when performing the secure sparse matrix multiplication. They exploit PIR protocol [ to extract the required non-zero elements from the ciphertexts in their multi-pare computation (MPC) setting, which is not applicable in our HE enviromment since decryption at the inference stage is not possible. Other studies such as LoLa (3), CHET M. and HEAR [22] aim to use the ciphertext packing technique to place multiple values from network nodes in the same ciphertext, so that HE operations can be conducted efficiently via single instruction multiple data (SIMD). However, their data formats for ciphertext are not optimized for GCN-based models, resulting in a large amount of HE operations (multiplication and addition).
latency 32 21
29
16,
Methodology
In this section, we first present the threat model assumption for this work. We then discuss technique details of our proposed CryptoGCN-a CKKS-basce homomorphic encryption framework tailored for fast and scalable GCN inference on encrypted graph tensor. In particular, we focus on two key components to significantly reduce the number of HE operations: 1) adjacency matrix-aware (AMA) data formatting dedicated to simplifying GCN's matrix- matrix multiplications without involving ciphertext rotation; 2) non-lineat Activation Pruning to reduce the multiplicative depth, resulting in trade-offs between security level and inference latency with low accuracy loss.
Threat Model. We assume the cloud-basee machine learning service, of which a well-trained graph convolutional network model with plaintext weights, is hosted in a cloud server. A client can upload private and sensitive data to the cloud for obtaining the online inference service. The cloud server is semi-honest (e.g. honest but curious). To ensure the confidentiality of clients' data against such cloud server, client will encrypt the data by HE and send it to the cloud for performing encrypted inference without decrypting the data accessing the client's 's private key. The client then can decrypt the returned encrypted inference outcome from the cloud using the private key. In this work, we focus on encrypting graph node features, and the normalized adjacency matrix (often sparse and the same for different graph inputs) is assumed as plaintext.
3.1 AMA Data Formatting and Matrix-Matrix Multiplication
Since HE operations can be performed on encrypted vectors by taking advantage of the SIMD architecture for parallel computing, the input tensor should be well placed into "big vector container" by a certain format which we call "data formatting". The state-of-the-ee row-major format [2] concatenates ciphertext row by row and facilitates the dot-produe computation that is essential to convolution or matrix- -based operations. However, as we shall show later, it cannot efficiently support GCNs' matrix-matric multiplication that would occur multiple times in multi-channel GCN layer, because of the extensive ciphertext rotation, addition, and multiplication. The mini-batch inference over multiple GCN layers would further escalate HE overhead and latency for the row- majoo format.

---

Adjacency Matrix-Aware (AMA) Data Formatting. We use the skeleton- action recognition graph tensor data as an example to better illustrate our proposed AMA data formatting: assuming the size of an input graph tensor is B x C. x T x J, where B is the batch size of mini-hatch inference (e.g. = for single input inference), C, T and are the number of input channels, video frames, and joints, respectively. The first step is to permute the tensor as J columns, with each column of size C' x B x T. Then each column is flattened to C' ID vectors, with each vector of size x T. For each of such ID vectors, zeros are padded to make its length equal to the smallest power-of-two integer greater than B x T. The C zero-padded ID vectors are concatenated and then further stacked to plaintext vector via a caannnll-nterleaving manner until the space of a plaintext vector can be fully exploited, e.g. the length reaches half of the polynomial degree N. Finally, we encrypt such a plaintext as a fully-packed ciphertext ctg, k E J. The detailed process is presented in Algorithm I and Fig. aa).
AMA Data Format-Aided hatrix-Matris Multiplication. Once the AMA data formatted ci- phertext is created, the next step would be to apply it to simplify and speed up the matrix-matrix multiplication introduced by adjacency matrix and convolution operations. Recall Equation [ in Section 2 a typical ST-GCN layer's computation involves three consecutive PMult(ct, pt): Spatial convolution (1 X plaintext kernel), matrix-matrix multiplication with normalized adjacency matrix J J in plaintext, and the Temporal convolution along the dimension T (K x 1 plaintext kernel). Considering the property of X Spatial convolutional kernel, we can easily merge this into the adjacency matrix and formulate new plaintext matrix to reduce one multiplicative depth of PMult. Then we can perform the matrix- matrix multiplication based on the new J x J plaintext matrix A. Note that each graph tensor input channel could contain one such matrix.
For row-major formatted ciphertext, as Fig. 2() shows (bottom), even with state-of-the-art diagonal encoding method [1]]. such matrix-matri multiplication would still involve 2./ 1 ciphertext rotations (Rot). Since the final outcome is the sum of each rotated ciphertext (Rot(ct,k)) multiplied by the corresponding diagonal encoded vector (Ptx)) from the plaintext matrix A, it also brings extra PMult and Add. In contrast to the row-major data format, our AMA data format can significantly reduce the amount of these HE operations. As Fig. (2c (top) demonstrates, first, we decompose the J x J plaintext matrix A into a series of patterned sparse matrices A,-each A, contains at most one valid element in each column, and A = >x A,, Am < J. Second, simply multiply the column-wise fully-packed ciphertext (due to the AMA data formatting) with the valid element of the corresponding column in A,, and then sum the intermediate column-wiss ciphertext to obtain final ciphertext:
VI Σ ct
17 ΣΣ PMult(cti, 0i.k)
ot2
(2)
Where aiga represents the single valid element in column A of A,. Since the process does not require any Rot, except the simple column-wise PMull with a single plaintext value and final summation, the HE operations can be greatly decreased compared with the row-major format. To be specific, as the example in Fig. ( shows, the sparse adjacency 4 x 4 matrix A in a GCN consists of 8 non-zero elements (a11, 013, 411, 023, 032, a11, 442, a44) and 8 zeros, while the dense encrypted feature matrix that needs be multiplied with A has numbers from 1 to 16. For AMA format, as shown in the top part of Fig. (i.) due to the sparsity of A, A can be casily decomposed into two submatrices A₁ - A2 whose column only contains a single non-zero value (e.g. 01 in column 1 of A1, a41 in column 1 of A2). Then the output ciphertext can be quickly calculated by simply multiplying constant value in a column of A = 1) with the corresponding polumn-wise packed ciphertext in the dense feature matrix, and then sum such column-wise multiplied results from A₁ and Ag. In this way, the rotation is eliminated. The sparsity of A determines how many submatrices need to be decomposed, and how many PMult are needed. The sparser (e.g. 4n1, 413 become zero) A is, then the less number of (M (x2x) is. Thus our AMA format takes advantage of A's sparsity in practical GCN applications to reduce HOCs. In contrast, the row-major format presented in the bottom part of Fig. ((c). cannot utilize this sparsity for computation overhead reduction due to using a diagonal encoding method to form multiple plaintexts to be multiplied with corresponding rotated ciphertext.
Theoretical Analysis of HE Operation Reduction. We analytically compare the number of HE operations needed for matrix-matrix multiplication between our AMA and row-major data formats. To ensure the evaluation generality, our analysis is conducted by assuming mini-batch inference
5

---

Aoep Siuce
P1a #32 110
Ria
PM
Fis
R4
Aci R42
F4
AMArfrrat
(8)
c1
211 #22 zu 216
15.15
R2
030 Pg: 2a 2g
Poo
Potvenatrr
16
21) FM 9%
10
12
13
Input Data (c))
pda 56s 54
Figure 2: The comparison of data formatting: (a) AMA data format; (b) Row-major format; (c) Matrix-matrix multiplication comparison using AMA and row-majon formatted ciphertext.
typical ST-GCN layer which consists of C' input channels and C output channels with 1 X 1 convolution kernels. The J x J matrix A in Eq. Can be decomposed into J sub-matrices if A is dense in the worst case. For fair comparison. we assume the space of ciphertext-T x J is fully exploited in both methods. As shown in Fig. (a) and (b), a ciphertext in row-major and AMA format contains one channel data of size x J. and multiple-channel multiple-batch data of size B x T x c J/B, N respectively. This results in the same total amount of ciphertext B example matrix matrix multiplication using the two methods are presented in Fig. (c). Since AMA formatting increases processing parallelism in SIMD by packing multiple-channel and multi-batch data into one ciphertext, it involves the rotation of the outcomes of matrix-matra multiplications from different channels and then summing up them to obtain the result for an output channel (Fig. 2 (b)). A ciphertext including data from more channels (a larger C') requires more rotations. To further reduce the rotation overhead, we leverage the multi multi-channel convolutional technique and baby-step strategy from HEAR [22 We also apply them to row-major formatting in evaluation 5 However, the improvement is limited as a row-major formatted ciphertext can only contain single-channer data.
of multi-channel graph tensor input (B C x J)
in both methods. The implementations of an
Table I: Analytical comparison of HE Operation # (AMA v.s. Row-major)
HE Operation
Description
Total
Complexity
Rot
Row-major
B G (2J
O(B-C-2J)
Rot
AMA
B C (J/B
O B)) O(B-C4.2))
PMult
Row-major
C (2J x
PMult
AMA
J X x (BC/J)
O(B-C2.J)
Add
Row-majj
B C (2 BC
O(B C² 22)
Add
AMA
J J x (BCJJ) BC
O(B-C
Table [ reports the detailed breakdown of HE operation numbers for each method (see Appendix A.2 for detailed proof). Overall, AMA data format requires almost half of PMult and Add operations of that of row-major format, since row-major format needs to compute 2. - versions of a ciphertext due to rotations in the matrix-matris multiplication. The number of rotations increases proportionally as the number of channels C that can be included in ciphertext increase for both methods. However, it is much less than that of row-major. The rotation number difference between AMA and row-major format can be further enlarged when only the batch size B increases. This is because the AMA formatted ciphertext contains data from more batches, resulting in the reduction of rotation times (JC'
(JC-BC) (CC-BC BC). In contrast, the rotation amount of the row-major format grows as B increases. This means that our AMA data formatting performs better when the batch size increases. Moreover, since A is often sparse matrix in practical ST-GCNs, the number of decomposed matrices m can be much smaller than for matrix matrix multiplication, indicating better efficiency than Table which is obtained from a dense matrix. We further validate these observations in Section 5
3.2 Activation Pruning
Applying the Leveled Homomorphic Encryption scheme like CKKS for private inference of deep network is challenging because of the limited modulus bits for the encrypted ciphertext. This
We optimize the K x Temporal convolution following the matrix matrix multiplication in similar manner.

---

means that one LHE encrypted ciphertext has limited rescale level. For computation like batch normalization, it could be easily absorbed in the adjacent linear computation like convolution and matrix multiplication 13] since batch normalization 17 is fixed-parameter based linear transformation in inference. However, the nonlinear ReL.U activation computation must. be replaced by polynomial approximate activation (PAA). However, even a simple 2 PAA would consume 2 rescale levels. Given that each GCN layer can contain one or more ReLU activation for accuracy purposes, more rescale levels would be needed for deep GCNs. This increases the polynomial degree to achieve a certain security level, leading to higher computation overhead and inference latency.
Algorithm 1 AMA Formatting for Encryption
Algorithm 2 Activation Pruning
1: Input: X5 = (I1, (I1..2..... .2.....,,.0............... E RC BxT
Input: NN Model with M activation layers
2: Output: cta, fully packed ciphertext
2: Output: Optimized Architecture
3: For from to M
3: For i from 1 to C
4: acc;=Train the Model with in activa- tion layer pruned
4:
U/ = FFatten Dü Pad(c;)= = Padding v/ to nearest power of
5:
5: rankact = [ace,]
SORT rankact from high to low
6: end for
7: For from 1 to M
7: V/2 = -(Pad(vi), Pad(vz).... ..... Pad(vc))
Fine-tune the network Arch, without top i activations in rank AP-performance = (Ace,, Level)
8: Varuu stack copies of Vn to size N/2
9: return cl.- Ennerpp((V fma)
10: return Arch; with best AP AP-performance
To achieve the trade-off between inference latency, security level, and accuracy, we investigated the ofate-of-the-art solution-fine fine-graieed channel-wis PAA for ReLU in SAFENet [28]. which is to replace the ReLU activation in the same layer with different polynomial degrees. However, the method has major limitation when applied to LHE-based private inference. Given ciphertext could contain data from multiple channels in our AMA data formatting, mask vector that chooses different PAAs must be utilized to process a ciphertext. As a result, this would consume extra rescale level and offset the benefit of reduction from the multiplicative level in ReLU. Therefore, we propose to identify and prune ReLU activations based on the fact that removing ReLU activation of some layers in deep networks leads to marginal accuracy loss [8]. For our Leveled HE schemes CKKS, computation overhead from activation is not linearly changed with activation counts different from some existing approaches like CryptoNAS [12] and Delphi [29]. Thus, our target not to prune as many activations possible. Instead, we need to take the total multiplication depth, model accuracy, latency, and security level all into consideration in our optimization process.
We name such technique Activation Pruning (AP). As Algorithm Ssowss, we first replace all the ReLU activations with a 2-degree polynomial activation ax? + bx + C, in which (a, h, e) is updated during the training process, and train this model's accuracy to desired level as the baseline. Second, we rank the activation layers according to the accuracy, search the architecture by increasing the number of pruned activation layers and fine-tune the new model to recover the accuracy. A model can be selected based on the accuracy and number of needed rescale levels to trade off between security level and latency.
Experiment Methodology
HE parameter setting. We have two sets of encryption parameters for the experiments without Activation Pruning and with Activation Pruning. For both settings, we choose the scaling factor A = 233 to maintain the inference accuracy. For each level, it will consume 33 bits of ciphertext modulus Q. For experiments without AP setting, it requires 21 levels for the whole network architecture. Thus, we set Q 740, and the polynomial degree N should be set to 2 to make the security level 2 80 bits. For experiments with the AP setting, the total level is 19 or 17. Therefore, set = 680 or 600 and the polynomial degree N = 2 to achieve least 80- security level.
Dataset. NTU-RGE+D 34 is the current largest dataset with 3D joint annotations for human action recognition task. It contains 56,880 action clips in 60 action classes. The annotations contain the 3D information (X, Y, Z) of 25 joints for each subject in the skeleton sequences. We choose one benchmark NTU-cross-Viee View (NTU-XView) as the dataset for our evaluation because this benchmark
7

---

Table 2: Model Architecture
Model
Layer
ST-GCN
ST-GCN 2
ST-GCN 3
Output featuremap size Channels
(256,25)
(128,25)
(128,25)
64-STGCN-3
64
128
128
Output featuremap size Channels
(256,25)
(128,25)
(128,25)
128-STGCN-3
128
256
256
representative human skeleton joints dataset. It contains 37,920 and 18,960 clips for training and evaluation, respectively. For better evaluation, we use 256 frames from the video clip as our input data. Thus, the input tensor with size of 2 3 256 x 25 contains the 25 skeleton-joint information YX,Y, Z) of 2 persons in a video has 256 frames.
Network Architecture. ST-GCN (38 is the state-of-the-art GCN architecture for human action recognition. It combines the GCN and CNN to better extract the Spatial and Temporal information than the previous models. In our experiment, pooling layer and a cullycconeected layer and study one small net and one large net: 64- STGCN-3 and 128-STGCN- where the first number stands for the channel number of the first ST-GCN layer. Table Jummarzie the network architecture. One ST-GGN layer is composed of one Spatial Cony layer and one Temporal Conv layer. Following the stacked 3 ST-GCN layers are global average pooling layer and a fully-connected layer. We use Stochastic Gradient Descent (SGD) optimizer with mini-batch size of 64, momentum of 0.9, and weight decay of e- 4 to train the model for 200 epochs. The initial learning rate is set to 0.01 with a decay factor 0.1.
use stack of 3 ST-GCN layers with global average
Evaluation Setup. Our experiments are conducted on machine with AMD Ryzen Threadripper PRO 3975WX with a single thread setting. We use Microsoft SEAL version 3.7.2 [33 to implement a variant of CKKS [6] scheme. To perform the Temporal convolution, we leverage the baby-step strategy [2 to optimize the multi-channel convolution. The Global Avg Pooling layer and Fully- Connected layer have small impact the total latency so just apply same implementation with HEAR 22 to compute these two layers.
5 Results and Analysis
5.1 Activation Pruning Ablation Study
We first analyze the effect of our Activation Pruning (AP) technique in our framework through an ablation study. To evaluate the performance, we optimize our neural network architecture by pruning the activation layers. After the algorithm optimization, 2 AP, where the numbers denote how many activation layers have been pruned. Then, we compare the performance of these optimized architectures the model inference accuracy and HE inference latency. The results are shown in Table 3
have two types of variants, i.e., 1 AP and
Despite the architectures having different widths (channel numbers), the original unoptimized archi- tectures (w/o AP) have the best accuracy but also the highest latency. To deal with the multiplicative depth of the unoptimized architectures, rameter to 25, resulting in a tremendous latency increase. By applying AP, the I AP (one activation layer pruned) architecture only has small accuracy loss (1.1-1.5%) while the latency is improved by about 2.3x through saving two levels. This is because reducing two levels allows us to trade off the polynomial degree with a security level decrease and achieve a sweet point. More specifically, we can use 214 as our polynomial degree for the optimized depths with an 80-bit (instead of the original 128-bit) security level. If we try prune one more activation layer (2 AP), the accuracy loss (3.95-4.04%) is larger than the 1 AP variant. Besides, the latency speedup is limited because we can not reduce the polynomial degree further to have at least 80-bit security level.
have to set the polynomial degree in the encryption pa-
5.2 AMA Format Effectiveness
To evaluate the effectiveness of the AMA format method, we compare its performance against the row-major formatting with the same encryption parameter setting. As the AP improves the latency for every HE operation, we evaluate the performance of two data formatting methods on AP-optimized
8

---

Table Ablation study for AP (Model Architec- ture Tradeoff) (AMA format)
Table Ablation study of AMA format with batch size=1
Model
34-STGN
3
Model
64-STGCN.3
128-STGCN-3
75.31%
Row-major
Lateney
2962.46s
9589.59%
w/o AP
Latency
4273.89s
10580.41s
formar
# of
128
256
73.78%
Latency
1863.96s
4850.93s
AMA
(1 AP)
Latency
1863.95s
4850.93s
# of CI
100
200
AP (2 AP)
ACC Latency
70.21% 1856.36s
71.36%
Speedup
1.59
4831.93s
architecture. Then, we compare our AMA format with the row-major format in different batch size settings.
5.2.1 Compare with row-major format
As reported in Table 4 AMA format improves the inference latency by 1.59 for 64-STGCN-3 architectures and 1.97x for 128-STGCN-3 architecture, respectively. Table breakdown of HE operations for 64-STGCN-3. From the table, we observe that the AMA format consumes only 31.3% of PMult and Add, comparing with the row-major format, The theoretical analysis of HOC is presented in Table 8 of Appendix A.
Table Breakdown for HE operations in different layer of 64-STGCN-3
Row-major format
AMA
Layer
Rot
PMult
CMult
Add
Rot
PMult
CMult
Add
Spatial Conv
6.9K
623K
622K
6K
56K
5SK
Temporal Cony
4K
295K
294K
7.7K
230K
230K
GlobalAvgPooling
832
896
FC Activation
60
3.8K
3.8K
240
240
240
1.3K
640
640
1K
500
1K
Here are two reasons for the HOC reduction. First, the AMA format uses fewer ciphertexts than the row-major format. The row-major format does not fully utilize the ciphertext space as the feature map has size of 256 x 25. In row-major format, the feature map is first converted into ID vector with size of 6400; then zero padding is applied to the right end of this vector make the size equal to 8192. Therefore, in the resulting encrypted ciphertext, 1792 slots have been wasted. Our AMA format, on the other hand, fully utilizes the ciphertext space, because 256 is a power-of- of-two number. None of the slots in the ciphertext is wasted. Second, compared to row-major formatting, our AMA format could perform matrix matrix multiplication with fewer HE operations. For the matrix used in proposed network, one row-major format ciphertext should perform 19 multiplications for one output channel. However, one AMA format ciphertext only needs to perform multiplications for one output channel. A similar reason holds for the Add operation.
5.2.2 Different batch size settings
We analyze our data formatting method different batch size settings, As described in Table with the batch size increasing, the latency of the row-major format increases linearly as they do not have any parallelism for a mini-batch setting. However, our AMA format allows processing a mmini-batch of data in the same ciphertext, which improves the parallelism for mini-bater setting. Besides, the number of rotations for multi-channel convolution decreases when the batch size increases and the number of other HE operations increases linearly, resulting in speedup much as 3.1 x for average latency with the batch size growing.
5.3 Computation Complexity Evaluation
Table compares CryptoGCN against the state-of-the-art crivacy-preserve neural network frame- works (i.e., CHET [ and Fast-HEAR (22). Since the previous frameworks and ours are imple- mented in different environments (different CPUs and number of threads). For fair comparison, we evaluate the number of the required homomorphic operations for 64-STGCN-3 on the same dataset. In this way, we climinate the impact of different hardware and software configurations.

---

Table 6: AMA performance with batch size increase
Model
Batch size
Row-major
AMA
Average Latency
Speedup
64 3TGCN-3
1
2965.46 sec
1863,95 6663,9 sec
1863.95 sec
1.59 x
64-STGCN-3
2
5931.92 sec
2704.41
1352.21
2.19 x
64-STGCN-3
11852.84
4390.66
1097.66
2.70 x
64-STGCN-3
8
23703.68 sec
7770.91 sec
971.36 see
3.05 x
64-STGCN-3
16
45179.33 sec
14535.23 see
908.45 see
3.10 x
Table 7: Compare with the previous benchmarks on 64-STGCN-3
HOC
Method
Batch size
Rot
CMult
PMult
Add
Total
CHET
16K
1.28K
1.3
1.29M
2.61M
Fast-HEAR
1
12K
1K
923K
922K
1.86M
CryptoGCN
14K
500
287K
287K
589K
CHET
32K
2.56K
2.6M
2.59M
5.23M
Fast-HEAR
2
24K
2K
1.84M
1.84M
3.7M
CryptoGCN
16K
1K
575K
574K
1.17M
Similar work, CHET and Fast-HEAR utilize the ciphertext packing technique to reduce HE computation complexity. They utilize the row-major format as the data representation for the encrypted feature maps. The main difference between Fast- HEsR and CHET is that Fast-HEAR leverages the non-valid space in ciphertext after down-sampling (avg pooling layer) in the CNN model such that Fast-HEAR could have less Homomorphic operation count (HOC).
Neither CHET nor Fast-HEAR is optimized for GCN-based models and the unique matrix multi- plication mechanism could significantly increase the HOC. When batch size equals 1, compared to CHET and HESA, our AMA formatted ciphertext better utilizes the sparsity of the matrix and significantly reduces the multiplication and addition operations. Specifically, when performing matrix multiplication combined with multi multi-channel convolution, the AMA format avoids performing an inner loop for matrix multiplication and hence reduces the amount of PMult and Add operations by 02.5%-66.22 66.2%. Furthermore, we pack the graph data into ciphertexts to maximize the use of the slots and prune one activation layer from the original architecture, which reduces the number of CMult by 40%-50%. With the batch size increasing, CryptoGCN reduces 77.4% of the total HOC compared to prior work. A more detailed theoretical comparison of HOC between CrytoGCN, CHET and FESR can be found in Table of Appendix A.I
Conclusion
Homomorphic encryption (HE) has become an effective way to build privacy-preserving machine learning thanks to the great advancement of HE schemes. In this paper, we build fast and scalable Leveled HE-based privacy-preserving inference framework optimized for GCN models by leveraging our proposed novel AMA data formatting and model architecture optimization strategy. To the best of our knowledge, this is the first framework supporting private inference for large skeleton joint data with a 40x size of previous work-Fast-HHE.. using deeper networks. Our solution demonstrates encouraging results for enhancing cost-effective manner. In the future, could leverage the multi-threading technique further improve the encrypted inference latency. We would like to extend the encrypted data to both graph node features and adjacency matrices, the matrices may also contain part of sensitive information. By encrypting both graph node features and the associated adjacency matrices, the client's data privacy can be fully guaranteed.
inference on GCN models in
7 Acknowledgement
We would like to thank the anonymous reviewers for their constructive comments and suggestions on this work. This work is partially supported by the National Science Foundation (NSF) under Award CCF-201 1236, and Award CCF-2006748.
10

---

References
[1] Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. Pir with compressed queries and amortized query processing. In 2018 IEEE symposium on security and privacy (SP), pages 962-979, IEEE, 2018.
[2] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1 36, 2014.
[3] Alon Brutzkus, Ran Gilad-Bachrand and Oren Elisha. Low latency privacy preserving inference.
In International Conference on Machine Learning, pages 812 221.. PMLR, 2019.
[4] Zhe Cao, Tomas Simon, Shih-En Wei, and Yaser Sheikh. Realtime multi-person 2d pose estimation using part affinity fields. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 7291-7299, 2017.
[5] Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Jeffrey Hoffsteen, Kristin Lauter, Satya Lokam, Dustin Moody, Travis Morrison, et al. Security of homomorphic encryption. Homomorrphic Encryption. org, Redmond WA, Tech. Rep, 2017.
[6] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full ms variant of approximate homomorphic encryption. In International Conference on Selected Areas in Cryptography, pages 347-368. Springer, 2018
[7] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference the Theory and Application of Cryptology and Information Security, pages 409-437. Springer, 2017.
[8] John Chiang. A novel matrix-encodiig method for seevacy-preserving neural networks (infer- ence). arXiv preprint arXiv:2201.15777 2022.
[9] Naria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Tfhe: fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34-91, 2020.
[10] Jinming Cui, Chaochao Chen, Lingjuan Lyu, Carl Yang, and Wang Li. Exploiting data sparsity in secure ploss-platform social recommendation. Advances in Neural Information Processing Systems, 14:10524-15534 2021.
[11] Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. Chet: an optimizing compiler for fully-homomopphic neural- network inferencing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 142-156, 2019.
[12] Zahra Ghodsi, Akshaj Kumar Veldanda, Brandon Reagen, and Siddharth Garg. Cryptonas: Private inference on relu budget. Advances in Neural Information Processing Systems, 33: 16911-1697,, 2020.
[13] Ran CilladBachhaach, 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.
[14] Shai Halevi and Victor Shoup. Algorithms in helib. In Annual Cryptology Conference, pages 554-571. Springer, 2014.
[15] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-enn. In Proceedings of the IEEE international conference on computer vision, pages 2961-2969, 2017.
[16] 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.
[17] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
[18] Nandan Kumar Jha, Zahra Ghodsi, Siddharth Garg, and Brandon Reagen. Deepreduce: Relu reduction for fast private inference. In International Conference on Machine Learning, pages 4839-4849. PMLR, 2021.
[19] 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 2209-1222, 2018.
11

---

[20] 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 archifecture-centrcc analysis and optimization. IEEE Access, 9:98772-98789, 2021.
[21] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. {GAZELLE]: low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), pages 1651-1669, 2018.
[22] Miran Kim, Xiaoqian Jiang. Kristin Lauter, Elkhan Ismayilzada, and Shayan Shams. Hear: Human action recognition via neural networks on homomorphically encrypted data. arXiv preprint arXiv:2 09164, 2021.
[23] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[24] Kim Laine. Simple encrypted arithmetic library (seal) manual, 2017.
[25] Donsuk Lee, Yiming Gu, Jerrick Hoang, and Micol Marchetti -Bwiekkk Joint interaction and trajectory prediction for autonomous driving using graph neural networks. arXiv preprint arXiv:1912.00882. 2019.
[26] Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC conference computer and communications security, pages 619-631, 2017.
[27] Qian Lou and Lei Jiang. She: A fast and accurate deep neural network for encrypted data. Advances in Neural Information Processing Systems, 32, 2019.
[28] Qian Lou, Yilin Shen, Hongxia Jin, and Lei Jiang. Safenet: A secure, accurate and fast neural network inference. In International Conference on Learning Representations, 2020.
[29] 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.
[30] Payman Mohassel and Yupeng Zhang. Secureml: system for scalable
machine learning. In 2017 IEEE symposium on security and privacy (SP), pages 19-38. IEFE, 2017.
[31] Ronald L Rivest, Len Adleman, Michael L Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of secure computation, 4(1 1819)1199-880 1978.
[32] 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.
[33] Microsoft SEAL (release 3.7),
September 2021.
Microsoft Research, Redmond, WA.
[34] Amir Shahroudy, Jun Liu, Tian-Tsong Ng, and Gang Wang. Ntu rgb+d: A large scale dataset for 3d human activity analysis. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1010-1019, 2016
[35] Chenyang Si, Ya Jing, Wei Wang, Liang Wang, and Tieniu Tan. Skeleton- based action recog- nition with spatial reasoning and temporal stack learning. In Proceedings of the European conference on computer vision (ECCV), pages 103-118, 2018.
[36] Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang. Deep high-resolution representation learning for human pose estimation. In Proceedings of the IEÉE/CVF conference on computer vision and pattern recognition, pages 5693-5703, 2019.
[37] Shiwen Wu, Fei Sun, Wentuo Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: a survey, ACM Computing Surveys (CSUR), 2020.
[38] Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In shirdy- AAAI conference artificial intelligence, 2018.
[39] 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.
12

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section 4
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We clearly present the theoretical analysis and compare our contribution by ablation study in the result part
(b) Did you describe the limitations of your work? [Yes] See section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section 3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See section A.2
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.)? [Yes] See in section
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See in section 4
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] We report the average latency with same random seed setting
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See in section 4
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Yes, we cite all the
creators in the papar
(b) Did you mention the license of the assets? [Yes] SEAL has MIT license. ST-GCN repo has BSD-2-Clause license.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13

---

A Appendix
A.1 HOC breakdown across layers and other methods
We use the following notations: Number of samples N Data size N C T J, Batch size B, Channels on one ciphertext in AMA U = R/2-N-T-B. Number of ciphertexts in AMA N, = J-C/U, Number of ciphertexts in row-major format NN, C N B Output channel O polynomial degree R, Spatial-cony layers Sp. Temporal-com layers Te. Activation layers A, Kernel size K. Valid matrix elements number V. Diagonal decomposition number D, Number of output classes C.. The HOC comparison across layers between AMA format and row-major format is presented in Table The model-level HOC comparison with other SOTA methods listed in Table 9
Table 8: HOC layer breakdown for AMA format
Layer
Type
Rot
PMoli
CMali
Add
S-Coev
J- 1) 10/10/ (V
NV-(V 0-
(V.- -0 -.N00-
T-Cunn
(N,
11-+) (0/0)),
O
(N--O-K-O --a)---------------------- N.)
GAP
AMA
Cyt log(T/2)
C/U-
FC
C/U-C, -C,
C/U-C,
(C/U)-C,
Activation
2.N.
N, 2-N,.A
S-Coev
No.(1 1..(1 11-8
Nr --, +1)
(N-O-- No) (8p +1]
T-Conv
N. (K 1) (Z
N, K-O- (E. 1) 0
(N, K. N.) (L. 1)
GAP
Rom-major
N./N RR22)
N,/N + 1og/2
R/2)
N,/N 2--
N,/N
Table 9: HOC Comparsion with other methods
Methods
CHET
N, (D. 1). (8,
(K (L.
+ N. Rog( +
F-HEAR
N. 1,
(T.
NN R(2) C.
CrypwcccN
J. J-18, +1,+111 -T, T.) (0/0
1)
(N.
(K 1) (L. + 1) CJU tog(1/2) C/U-C.
Methods
PMul
CHET
N, N. (8, 2) 8
33
2
2 N.
F-HEAR
D.
N.JN-C.
CrypaGGN
N. N. 8 N.
12 N.
Method
Add
CHET
(N. N.). 2 IN
4) N.
N./2 (R/( N C. (Rg( N./N
F-HEAR
ON N.). +
N
ClyptoGCN
(Nu-(V/J)-O N.) (M. O.
Method
CMult
CHET
N,-A-2
F-HEAR
N, (AA+))
CryptoGCN
-
A.2 Theoretical Comparison of HOC for Matrix-Matrix Multiplication
We explain the theoretical results in Table by following the same assumption in Section 3.1
Row-major format:
For one ciphertext, represents the data from one channel. order to multiply with a J x J dense matrix, we need to rotate each ciphertext by 2J 2 times. To obtain C' output channel data, all existing BC ciphertexts need to perform 2J - 2 times multiplications, then we get BC resulted ciphertexts by summing up all the ciphertexts. The computation overhead for the three HE operations can be expressed in Equation 3:
Rotation = B C' (2J 2)
PMult = C B C (2J - 22)
(3)
Add = C B C. (2J 2) C
AMA format:
The rotation operation is only used to sum up all the input channel data, because the ciphertext with AMA format contains J/B channel data. For each ciphertext, it needs to rotate (J/B 1) times. To get output channel data, each ciphertext needs to perform times PMull. Then we get BC resulted ciphertexts by summing up all the ciphertexts. The computation overhead for three HE operations can be found in Equation 4
Rotation = B-C -J/B-1) PMult B- G.C.J.C
Add = B- B.C.C.J.--BB.. B-C
14


Reviews:
[{"review_id": "lBjXQUDR17", "reviewer": "Reviewer_YLFb", "summary": "The paper studies private inference of graph convolutional neural networks using leveled homomorphic encryption. The main contributions are, i) a data encoding scheme that is aware of the adjacency matrix of the graph and allows for more efficient spatial convolution that exploits the graph structure to perform matrix-matrix multiplication, and ii) pruning ReLUs to reduce computation overhead.\n\nThe method is evaluated on the NTU-XVIEW skeleton joint dataset and demonstrates lower latency compared to existing baseline methods.\n\n", "questions": "\n- In Fig 2c, is the 4x4 matrix with numbers from 1-16 the adjacency matrix? Why is it dense? \n- Can the computational complexity in Tables 5 and 7 (i.e., rotations, PMult, CMult, etc.) be provided in terms of the number of samples $n$, data dimension $d$, batch-size $b$, etc. instead of just showing the numerical values?\n- The abstract says, \"we develop an approach that can effectively take advantage of the sparsity of matrix operations in GCN inference to significantly reduce the computational overhead\". It is not clear to this reviewer where exactly is the sparsity of $A$ being leveraged.\n- When you compare CryptoGCN with CHET and Fast-HEAR, you report the computation complexity, i.e. the number of homomorphic operations. I am just wondering if CryptoGCN’s operations take the same time as CHET and Fast-HEAR? Although CHET and Fast-HEAR are both using CKKS, do you maintain the same cryptographic parameters? Can the row-major format use a smaller ring size and be efficient as well?\n- This is more of a suggestion. Algorithm 2 is heuristic and not efficient. You train the model with $i$-th activation layer pruned\none by one and sort the performance. Activation pruning is a combination problem. If you only estimate the importance of each ReLU, it is not accurate. Both SafeNet and Delphi use PBT to solve this problem. PBT should be more efficient and can get better solutions than the proposed Activation Prune algorithm.\n\nWill revise the rating of the paper based on the author's rebuttal.", "limitations": "- The paper does not discuss the limitations of the current work nor does it discuss any negative societal impact. I guess since the paper is focused on private inference, there is limited negative societal impact beyond making \"black-box\" GCNs even more \"black-box\" via encryption.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n+ Important and well-motivated problem. \n+ A customized data formatting of GCN over encrypted data under the CKKS scheme. Because CKKS supports SIMD and it is necessary to find a customized way to encode data that is fed into a GCN so that it can better take advantage of SIMD. Previous work majorly focuses on CNNs. There are some presentation issues though as described below.\n+ Experiments show a clear improvement in latency compared to the baselines. \n\n**Weaknesses:**\n- Pruning ReLU is not a new idea. Existing methods such as SafeNet (which searches channel-wise mixed-degree approximation of ReLU including pruning), CryptoNAS (explicitly focuses on removing ReLU layers), and Delphi also shares similar ideas and performs layer-wise pruning.\n- This is more of a presentation issue rather than a fatal flaw. The AMA-based matrix-matrix multiplication shown in Fig 2(c) is not clear to this reviewer. The description in lines 178-180 is not clear in terms of how exactly is this being computed. An algorithm was provided for the AMA data formatting but not for the matrix-matrix multiplication. To summarize, while the AMA data formating is very clear, how it is being used for matrix-matrix multiplication is not clear from the description in the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G0Qu3K_M7Po", "reviewer": "Reviewer_2m5X", "summary": "This work deals with two core techniques to efficiently perform GCN networks on HE with a reduced amount of homomorphic operations. First, since the GCN networks usually use the multiplication with the sparse plaintext matrix, the authors devise AMA data formatting to reduce the homomorphic operations using this sparsity of the matrices. Second, they pruned some activation functions less affecting the performance of the GCN networks, and also proposed a method to find these less-affecting activation functions. With these techniques, the authors successfully reduced the number of homomorphic operations compared to the prior works applied to GCN networks, where these works were not optimized for the GCN networks. ", "questions": "- Will the implementation of this model be open to the public after acceptance?", "limitations": "There is no negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This work deals with the GCN network on HE for the first time. It is desirable to optimize the important networks on HE other than traditional CNN models. \n- The authors observe the sparsity of the matrix in the GCN network and effectively devise the packing method using this sparsity of the matrix. The academic contribution of this technique is good enough.\n- The activation pruning technique is not limited to the GCN network and can be applied to more general frameworks, and this technique can be a useful practical technique for reducing the number of homomorphic operations.\n- The numerical comparison and theoretical analysis are well shown. Even though this work proposed the first GCN network on HE, they compared the proposed model with the prior work applied to GCN networks. Thus, these techniques were well proven to be effective in GCN networks on HE compared to the prior work for traditional CNN networks.\n\nWeaknesses\n- The AMA data formatting is not sufficiently presented. Algorithm 1 is too compact and abstract to be understood exactly, and there is no algorithm for AMA data format-aided matrix-matrix multiplication. Although the authors explain these algorithms in Figure 2, the figures usually play the role of only supplementary material to ease the understanding of the algorithm. I know there is no sufficient margin for this algorithm, but the author should add the specific and detailed pseudocode for these algorithms in Appendix for readers who want to understand the algorithms exactly.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4zuwppfBRy", "reviewer": "Reviewer_RkGQ", "summary": "This work studies the privacy-preserving graph neural networks (GNN) using fully homomorphic encryption. Existing works mainly focus on protecting the data privacy of convolutional neural networks (CNN) using fully homomorphic encryption. This paper tries to explore if fully homomorphic encryption can be used to protect the data privacy pf graph neural networks.  The paper argues that directly applying techniques in privacy-preserving CNN will not work since graph neural network operations brings additional matrix multiplication. To reduce the computational overhead, the paper mainly proposed two techniques including Adjacency Matrix-Aware (AMA) multiplication, and activation pruning techniques. ", "questions": "1. The difference between CNN and GCN is not clear. Although the paper uses figure 1 to highlight that GCN has one more matrix multiplication, the GCN and CNN have the same operators. How to design efficient homomorphic encryption matrix multiplication is not novel. Please try to explain the difference compared to existing works like [2][3][4]. It is important to know why existing techniques in FHE-based CNN or [2][3][4] do not work for the GCN. It is also important to know what is the motivation of the proposed AMA-based matrix multiplication. Is it specific for GCN?\n\n2. The reproduction is not clear to me. It is still not clear why the activation pruning does not significantly hurt the accuracy.", "limitations": "There are some overclaims. For example, the author claims “this is the first work that builds the PPML pipeline for GCN-based models”. As I know, there are multiple existing PPML for GCN based networks, like [1].", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. Graph neural networks are ubiquitous now and protecting the data privacy of input data is strongly needed. \n2. Fully homomorphic encryption (FHE) is a popular method to enable a privacy-preserving computing on cloud. Combining FHE and GNN is a promising direction.\n3. The paper is well-written. \n\nWeakness: \n1. There are some overclaims. For example, the author claims “this is the first work that builds the PPML pipeline for GCN-based models”. As I know, there are multiple existing  PPML for GCN based networks, like [1].\n\n[1] Igamberdiev, T., & Habernal, I. (2021). Privacy-preserving graph convolutional networks for text classification. arXiv preprint arXiv:2102. 09604.\n\n2. The difference between CNN and GCN is not clear. Although the paper uses figure 1 to highlight that GCN has one more matrix multiplication, the GCN and CNN have same operators. How to design efficient homomorphic encryption matrix multiplication is not novel. Please try to explain the difference compared to existing works like [2][3][4]. It is important to know why existing techniques in FHE-based CNN or [2][3][4] do not work for the GCN. It is also important to know what is the motivation of the proposed AMA-based matrix multiplication. Is it specific for GCN?\n\n[2]Chiang, J. (2022). A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference). arXiv preprint arXiv:2201.12577.\n\n[3] Jiang X, Kim M, Lauter K, Song Y. Secure Outsourced Matrix Computation and Application to Neural Networks. Conf Comput Commun Secur. 2018 Oct;2018:1209-1222. doi: 10.1145/3243734.3243837. PMID: 31404438; PMCID: PMC6689419.\n\n[4] Cui, J., Chen, C., Lyu, L., Yang, C., & Li, W. (2021). Exploiting Data Sparsity in Secure Cross-Platform Social Recommendation. Advances in Neural Information Processing Systems, 34, 10524–10534.\n\n\n3. Paper checklist. The reproduction is not clear to me. It is still not clear why the activation pruning does not significantly hurt the accuracy.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept