LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference
Authors: Hongwu Peng
Ran Ran
Yukui Luo
Jiahui Zhao
Shaoyi Huang
Kiran Thorat
Tong Geng
Chenghong Wang
Xiaolin Xu
Wujie Wen
Caiwen Ding
Venue: NeurIPS 2023 poster (2023)
Keywords: Privacy-Preserving Machine Learning
efficient private inference
machine learning as a service
homomorphic encryption
non-linear pruning
ST-GCN
TL;DR: We propose LinGCN, a framework with structural linearization for addressing graph learning complexity and privacy, outperforms CryptoGCN with 14.2x faster latency at ~75% accuracy.

Abstract: The growth of Graph Convolution Network (GCN) model sizes has revolutionized numerous applications, surpassing human performance in areas such as personal healthcare and financial systems. The  deployment of GCNs in the cloud raises privacy concerns due to potential adversarial attacks on client data. To address security concerns, Privacy-Preserving Machine Learning (PPML) using Homomorphic Encryption (HE) secures sensitive client data. However, it introduces substantial computational overhead in practical applications. To tackle those challenges, we present LinGCN, a framework designed to reduce multiplication depth and optimize the performance of HE based GCN inference. LinGCN is structured around three key elements: (1) A differentiable structural linearization algorithm, complemented by a parameterized discrete indicator function, co-trained with model weights to meet the optimization goal. This strategy promotes fine-grained node-level non-linear location selection, resulting in a model with minimized multiplication depth. (2) A compact node-wise polynomial replacement policy with a second-order trainable activation function, steered towards superior convergence by a two-level distillation approach from an all-ReLU based teacher model. (3) an enhanced HE solution that enables finer-grained operator fusion for node-wise activation functions, further reducing multiplication level consumption in HE-based inference. Our experiments on the NTU-XVIEW skeleton joint dataset reveal that LinGCN excels in latency, accuracy, and scalability for homomorphically encrypted inference, outperforming solutions such as CryptoGCN. Remarkably, LinGCN achieves a 14.2× latency speedup relative to CryptoGCN, while preserving an inference accuracy of ~75\% and notably reducing multiplication depth. Additionally, LinGCN proves scalable for larger models, delivering a substantial 85.78\% accuracy with 6371s latency, a 10.47\% accuracy improvement over CryptoGCN.

LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference
"Honwwu Peng', 'Ran Ran?, Yukui Luo², Jiahui Zhao', Shaoyi Huang', Kiran Thorat',
Tong Geng', Chenghong Wang', Xiaolin Xu², Wujie Wen', Caiwen Ding'
*These authors contributed equally. University of Connecticut, "North Carolina State University,
3 University of Massachusetts Dartmouth, 'University of Rochester, Indiana University Bloomington, Northeasternn University (hongwu. peng, jiahui zhao, shaoyi huang, (rran, wwen2) @ncsu. edu, y yluo20umassd. edu, tgengdur. rochester....... edu cw1660iu. edu, wwwhortheastern. edu, caiwen dingouconn. edu
(aboraa)@uconnn.ee edu, Sawnggduurooohhteer.....
Abstract
The growth of Graph Convolution Network (GCN) model sizes has revolutionized numerous applications, surpassing human performance in areas such as personal healthcare and financial systems. The deployment of GCNs in the cloud raises privacy concerns due to potential adversarial attacks on client data. To address security concerns, Privacy-Preserving Machine Learning (PPML) using Homo- morphic Encryption (HE) secures sensitive client data. However, it introduces substantial computational overhead in practical applications. To tackle those chal- lenges, we present LinGCN, a framework designed to reduce multiplication depth and optimize the performance of HE based GCN inference. LinGCN is structured around three key elements: (1) A differentiable structural linearization algorithm, complemented by parameterized discrete indicator function, co-trained with model weights to meet the optimization goal. This strategy promotes fine-grained node-level non-linear location selection, resulting in a model with minimized mul- tiplication depth. (2) A compact node-wise polynomial replacement policy with a second-order trainable activation function, steered towards superior convergence by a two-level distillation approach from an all-ReLU based teacher model. (3) enhanced HE solution that enables finer- greingr operator fusion for node-wise activation functions, further reducing multiplication level consumption in HE-based inference. Our experiments on the STU-XVIENS skeleton joint dataset reveal that LinGCN excels in latency, accuracy, and scalability for homomorphically encrypted inference, outperforming solutions such as CryptoGCN. Remarkably, LinGCN achieves a 14.2x latency speedup relative to CryptoGCN, while preserving an inference accuracy -55% and notably reducing multiplication depth. Addition- ally, LinGCN proves scalable for larger models, delivering substantial 85.78% accuracy with 6371s latency, a 10.47% accuracy improvement over CryptoGCN. The codes are shared Githut!"
Introduction
Graph learning, deep learning subset, aids real-time decision-maken -making and impacts diverse appli- cations like computer vision [1] traffic forecasting (2], action recognition [3,4, recommendation systems (5), and drug discovery (6. However, the growth of Graph Convolution Network (GCN)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

model sizes 7 g introduces challenges in integrating encryption into graph-based machine learning services. Platforms such as Pinterest's PinSAGE and Alibaba's s AliGraph [TO] operate on extensive user/item data graphs, increasing processing time. Furthermore, deploying GCN-based services in the cloud raises privacy concerns 11 due to potential adversarial attacks on client data, such as
gradient inversion attacks [13 14. Given the sensitive information in graph embeddings, it's crucial to implement lightweight, privacy-foeusee strategies for cloud-based GCN services.
Privacy-Preservinn Machine Learning (PPML) with Homomorphic Encryption (HE) helps protect sensitive graph embeddings, allowing client data encryption before transmission and enabling direct data processing by the cloud server. However, this security comes with substantial computational overhead from HE operations such as rotations, multiplications, and additions. For instance, using the (CKKS) [15]. Leveled HE (LHE) [[6] scheme, the computational overhead
Cheon-Kinn Kim-Kim- escalates significantly (e.g. 3x) with the total number of successive multiplications, which directly related to the layers and non-linear implementations in deep GCNs.
Three research trends have emerged to lessen computational overhead and inference latency for HE inference. First, leveraging the graph sparsity, as in CryptoGCN [12). reduces multiplication level consumption. Second, model quantization, seen in TAPAS 17 and DÎNN [8. binarizes activation and weight to 1 bit, leading to a 3%-6.2% accuracy loss on smaller datasets and limited scalability. Third, nonliear operation level reduction. as in CryptoNet [9] and Lola 20), substitutes low-degree polynomial operators like square for ReLU in CNN-based models. However, these methods struggle with performance due to absent encryption context of graph features, and the latter two are not suitable for GCN-based models.
To bridge the research gap, in this paper, propose LinGCN, an end-to-end policy-guided framework for non-linear reduction and polyno- mial replacement. This framework is designed optimize deep TpepprllTemporal Graph Con- volution Network (STGCN)- -based models for HE-based inference. We conduct extensive ex- periments on the NTU-XVIEW [2I] skeleton dataset and compare our ap- proach with CryptoGCN [12. The pareto fron- tier comparison of accuracy-latency between LinGCN and CryptoGCN [12] demonstrates
85
LinGCN
STGCN-6-255
LinGCN
Accuracy
80
STGCN-3-128
LinGCN w.
75
STGCN-3-255
CrystaGCN w.
70
STGGNN3-112 &
STGCN-3-256
joint 22 2 24
103
104
Latency (s)
Figure 1: Frontier of LinGCN vs. CryptoGCN
12
that LinGCN surpasses CryptoGCN [12] by over 5% accuracy under the same latency budget, and achieves 14.2-fold latency reduction under the same accuracy constraint (-75% accuracy).
Our proposed framework, LinGCN, is principally influenced by two observations: the need to conserve levels in the CKKS scheme and the crucial role of synchronized lincarization. In the CKKS scheme, deeper networks demand a larger polynomial degree, thereby increasing the latency of homomorphically encrypted operators. Non-linear layer pruning can mitigate this by reducing level consumption. However, unstructured non-linear pruning insufficient; structural linearization becomes essential for effective level reduction, underscoring synchronized linearization's 's significance in optimizing CKKS performance. We summarize our contributions as follows:
1. We present differentiable structural linearization algorithm, paired with a parameterized discrete indicator function, which guides the structural polarization process. This method- ology is co-trained with model weights until the optimization objective is attained. Our approach facilitates fine- fine-grained node-level selection of non-linear locations, ultimately yielding a model with reduced multiplication levels.
2. We introduce node-wise polynomial replacement policy utilizing second-order trainable polynomial activation function. This process is further steered by an all-ReLU based teacher model employing two-level distillation approach, thus promoting superior convergence.
3. We have engineered a corresponding HE solution that facilitates finer-grained operator fusion for node-wise activation functions. This development further mitigates multiplication level consumption during our HE-based inference process.

---

2 Background and Related Work
CKKS Homomorphic Eneryption Scheme. The CKKS scheme [15]. based on the ring learning with errors (RLWE) problem, allows arithmetic operations on encrypted fixed-point numbers. It
provides configurable precision via eneryption noise as natural error [25 We denote the cyclotomic polynomial degree as N and the polynomial coefficient modulus as Q, both cryptographic parameters.
ciphertext et encrypts message m with noise e as = m + e (mod Q). The CKKS scheme's security level [26). measured in bits, suggests 2128 operations to break À = 128 encryption. CKKS supports operations including ciphertext addition A cl2), ciphertext multiplication CMuli(cl1 cl2), scalar multiplication PMuli(ct, pt), rotation Rot(ct, k) and rescaling Rescule(cr). Scalar multiplication multiplies a ciphertext with plaintext, and rotation eyclically shifts the slot vector. For example, Rot(ct, k) transforms (vo.... .... UN/2-1) into (Uk,... .... U2/2-11 40, ..... Uk-1)) The level of a ciphertext (L), the number of successive multiplications it can undergo without bootstrapping, is reduced by the Rescale operation after each multiplication. With the level-reduced target network. we do not consider using bootstrapping (27 in this work.
STGCN for Graph Dataset with Timing Sequence. The focus of this study revolves around the STGCN, a highly esteemed category of GCNs proposed by [4. The STGCN model primarily employs two core operators, Spatial graph convolution (GCNConv) and Temporal convolution, designed to extract spatial and temporal information from input graph data, respectively. The Spatial convolution operation, as defined in Equation I1 precisely illustrates the process of extracting spatial information. In Equation| T the variables A, D, X,, W,, and Xi, correspond to the adjacent matrix, degree matrix, input feature, weight parameter, and output feature, respectively [4].
oou = D 1 (A ((++IDD I)D X,W,
Related Work. CryptoNets
Machine Learning (PPML) via Homomorphic Encryption (HE) but suffered from extended inference latency for large models.
19 pioneered
Subsequent studies, like SHE 28 which realizes realize the TFHE-based PPML, and those employing Multi-Pary Computation (MPC) solutions (1) reduced latency but faced high communication overhead and prediction latency. Research like TAPAS 17 and XONN 32 compressed models into binary neural network formats, while studies like CryptoNAS 30,, Sphynx 33 and SafeNet [34]
used Neural Architecture Search (NAS) to find optimal architectures. Delphi [29], J. SNL (35] and
DeepReduce (36) replaced ReLU functions with low order polynomial or linear functions to accelerate MPC-based Private Inference (PI). Nevertheless, these strategies proved suboptimal for homomorphic
encrypted inference. Solutions like LoLa 20), CHET (37). and HEAR [38 sought use ciphertext
packing techniques but were not optimized for GCN-based models.
Threat Model. In line with other studies 12 37 391, we presume semi-honest floud-based machine learning service provider. The tealnerained STGCN model's weight, including adjacency matrices, is encoded as plaintexts in the HEE-nffrence process. Clients encrypt data via HE and upload it to the cloud for privacy-preserving inference service. The server completes encrypted inference without data decryption or accessing the client's 's private key. Finally, clients decrypt the returned encrypted inference results from the cloud using their private keys.
3 LinGCN Framework
3.1 Motivation
We present two pivotal observations that serve as the foundation for our LinGCN.
CKKS Based Encrypted Multiplication. As described in section 2 the message m is scaled by factor A= 2D before encoding, resulting in Am. Any multiplicative operations square the ciphertext's s scale, including inherent noise The Rescale operation reduces this scale back to A by modswitch [15), reducing Q by p bits and lowering the level, as depicted in Figure 2 When Q - go after L multiplications and rescaling, the ciphertext's 's multiplicative level reaches O. At this stage, bootstrapping [12 necessary for further multiplication, unless a higher Q is used to increase the multiplicative level L.
Observation Saving Level is Important in CKKS Scheme. Within a STGCN model, the graph embedding is encrypted with an initial polynomial degree, denoted as N, and coefficient modulus,
3

---

represented by Q. These factors are determined by the network's multiplicative depth. As the multi- plication depth increases, the coefficient modulus must also increase, subsequently leading a higher polynomial degree N. To maintain a security level above a certain threshold (for example, 128-bit) in
the face of deeper multiplicative depths, a larger N necessitated [37 38 12 A larger inherently
results in increased complexity in each homomorphic encryption operation such as Rot and CMult.
These operations are integral to the computation of convolution (Conv) and graph convolution (GCN- Conv). We present a comparative analysis of operator latency with differing polynomial degrees N in Fig- ure Thus, it can be inferred that pruning certain operators conserve levels not only diminishes the latency of the pruned operators but also reduces other operators' latency.
Rensining
Level: L m
modulus bits
Decrewved remaining modillis hit
Mult
GCNCony ...) & RS
Level
Mult (C Cony, GCNCORY ...
ct' (121)
m,m,
Observation Synchronized Linearization Mat- ters. Our study mainly targets reducing multiplica- tion depth in standard STGCN layers, comprising an initial spatial GCNConv operation, two non-linear op- erators, and a temporal convolution. Under the CKKS base HE scheme, each operator's 's imput needs synchro- nized multiplication depths, with any misalignment adjusted to the minimal depth. This is particularly vital for the GCNConv operator, while later node- wise separable operators enable structured non-linear reduction to boost computational efficiency.
Mult
RS by
ce'
Level: /
Mitli
cc-
at"
O.P p
Polynomial degree 32768 Polynomial degrce 16384
CMult
PMult
Add
Figure 2: Top: Rescale decreases the cipher- text level. Bottom: Higher polynomial degree leads to longer HE operator's 's latency.
Unstructured non-linear reduction strate- gies, common in MPC setups like Au- toReP 40). PASNet 41] SNL (35), RR-
Graph input
Net [22 DELPHI 29), and SAFENet [43].
Consumption:
Consumptiont
GCNCory INN
prove suboptimal for homomorphic en- crypted inference. Our example in Fig- 3b) illustrates node-wis unstructured non-linear reduction in an STGCN layer, leading to unsynchronized remaining mul- tiplication depth budgets for nodes after the layer. This approach is ineffective in reducing levels consumption for homomor- phic encrypted inference, emphasizing the necessity for more structured non-linear reduction approach. To address the limitations unstructured non-linear reduction, we propose a structured approach, illustrated in Figure where we apply an equal level of non-linear reduction to each target node, reducing the overall multiplication depth. In contrast to CryptoGCN's layer-wise pruning method [12), our scheme provides nodes with the flexibility to perform non-linear operations preferred positions. This fine-gre graiiedddd structural non-lineat reduction may improve the non-linear reduced structure, potentially augmenting the efficiency and effectiveness of HE inference.
::Cov
IN
L Linear
Non-lincar
mul level
Syne
Synced
Same mul level consumption
Reduced mul level consumption (c)
(a)
(b)
Figure 3: Unstructured vs. structural linearization. Un- structured one doesn't 't lead effective level reduction.
3.2 Learning for Structural Linearization
Problem Formulation. Our methodology is aimed at the node-wise structural dropping of non-linear operators within a given I.-layered STGCN model fw. parameterized by W = (W.)22 This model maps the input Xo E RVXCT to the target Y E Rdd Here, V, C,, and T represent the number of nodes, channels, and frames, respectively. The primary objective of our approach is to eliminate the non-linear operator (designated as G,)) in a structured, node-wise manner. The ultimate aim is to achieve reduced multiplication level while minimizing any resultant drop in model accuracy. This goal serves to optimize the efficiency of bomomorphic encrypted inference for STGCN model.
We introduce an indicator parameter, denoted as h. to mark the node-wise non-linear operator dropping. The following conditions apply: (1) If hi, = O, the non-linear operator o, substituted by the lincar function f(x) (2) If hi, 1, the operator on is utilized. Here, h4 signifies

---

the hey node of the εe non-linear layer. The proposed node-wise non-linear indicator parameter hy. facilitates the expression of the 4sh non-linear layer with partial linearization, as given by XiA = h @ (n(2((11)x)) - (1 hx,x) @ (). Here, 7i-1 denotes the input of the in non-linear layer. Consequently, the issue of structural linearization can be formulated as follows:
2L
argminf = argmin LacolSw (Xo) + p W.A
Σ /
W.A.
(2)
1=1
subject to Vj. k E [1, (h2u. + h2241.5) = (h22, h2
In our formulation, [|b,||0 represents the Lo norm or the count of remaining non non-linear operators. Lace signifies cross-entropy loss, while μi is the Lo norm penalty term in the linearization process. The second term of Eq. 2 challenge due to its non-differentiability stemming from zero norm regularization and additional constraints on the discrete indicator parameter hç. Hence, this issue becomes difficult to handle using traditional gradient- based methods.
Differentiable Structural Linearization. To handle the non-differentiable discrete indicator parame- ter, we introduce trainable auxiliary parameter, h to denote its relative importance. However, the transformation from h to the final indicator h must comply with the structural constraint in Eq 2 ruling out simple threshold checks used in SNL [35]. Structural pruning methods 44 45), useful for weight or neuron pruning, are ill-suited for our problem due to its exponential complexity arising from non-linear selections of 25 nodes, and its distinct nature from weight or neuron pruning.
To tackle this challenge, we propose structural po- larization forward process, detailed in Algorithm The algorithm first ranks the relative importance of two auxiliary parameters (21,() and (2)+))))))) for every Jth node within the 4th STGCN layer, obtaining the higher and lower values and their respective indices. We then sum each ith layer's ' higher auxiliary parameter value into Sh, and lower auxiliary parameter value into 8t- Next, we con- duct a threshold check of 8/ and assign the final polarization output of the indicator value into the corresponding locations of higher value indices, ap- plying the same polarization for lower values. The proposed structural polarization enforces the exact
Algorithm 1 Structural Polarization.
Input: hw: auxiliary parameter
Output: h: final indicator
1: for 8h. 81 = and inda, indy <- 0
to L do
3:
for j = 1 to V do
4:
if [. > hw(2i+1.5) then (2(2)+1.)))
kw inda + (2i, indi + (2i + 1,3)
else
8:
8h + = (u + h inda + (2i +,J), indy +- (2i,
9:
10:
end if
11: end for
constraint given in Eq. 2 where each STGCN
12: hindd, = 81, > 0 and hands = St >
layer maintains a synchronized non-linear count across all nodes. The structural polarization is also capable of capturing the relative importance of the auxiliary parameter within each node and applying the proper polarization every position, all with complexity of only O(V). Each STGCN layer retains the flexibility to choose all positions to conduct the non-linear operation, or just select one position for each node to conduct the non-linear operation, or opt not to perform the non-linear operation at all. This selection is based on the importance of their auxiliary parameters.
13:
end for
Despite its benefits, the structural binarization in Algorithm is discontinuous and non-differentiable. To approximate its gradient, we use coarse gradients (46) via straight through estimation (STE), a good fit for updating he and reflecting the optimization objective in Eq 2 Among various methods such as Linear STE[47]. ReLU and clip ReLU STE [48), we adopt Softplus STE [49] due to its smoothness and recoverability discovered in 49 update hw as follows:
OC aLace (o,, (Z,-1) -Z--)) Ohi, (h
Ōhy
Ōhg, So Softplus(hw(tt.) (3) th
+ Dh
Th ahw(i,k)
0X,
The gradient of the auxiliary parameter, as displayed in Eq. consists of two components: the gradient from the accuracy constraint and the gradient from the linearization ratio constraint. The gradient stemming from the accuracy constraint will be negative if it attempts to counteract the lincarization process, thereby achieving balance with the Lo penalty term μ Σ ||h,]lo. The
5

---

Input
Embedding
Conv2D
GCNCony
Node-wisc balanced non-linear count st-gen layer
Temporal Conv2D
Nodo
Chamnel
Time
Ohr
Loc.
Out Ch
Nondin
Syne mnd dapti Layph
Noa-lar
Time
CH
Lng
Adj
Node
Temperal Conv
Nodo
Conv2D
LBi.
Temporal ConvID
Non-lar
Nodo
Coev2D
Conv
Non-Iar
Cony2D
Lns.
Node
Conv2D
Non-int
Temporal Conv
Lin
(1) Single st-gen layer example with structure pruned non non-lineur operator
1xl Cony2D
GCNCoov
Temporal Conv2D
* -on
Ciphertext
Lor.
Rotate sum
Sepurable ops, of Node
AMA
Rotate
Encoding
sum
(b) Single st-gen layer computation for homomorphieally enerypted inference
Figure 4: Overview of single layer STGCN with non-linear reduction and computation.
entirety of the linearization process is recoverable, which allows for the exploration of a near-optimal balance between accuracy and linearization ratio via the back-propagation process.
3.3 Learnable Polynomial Replacement with Teacher Guidance
CryptoNet 19 and DELPHI 29 suggest using quadratic functions y = x²2 as ReLU replacements for private inference. A second-order polynomial replacement (50) y = x² + x for ReLU was proposed but resulted in decreased performance. CryptoGCN [12] uses layer-wise trainable polynomial function (ax² + bæ + e) for the STGCN model, but it suffers from significant accuracy loss and scalability problems. To tackle these issues, offer two-tiered strategy: node-wise trainable polynomial replacement and distillation technique to facilitate the convergence of replacement.
Node-wise Trainable Polynomial Replacement. In HE setup (see Figure 4.. each node can independently perform non-linear, convolution, and further non-linear operations without increasing the multiplication depth. We suggest using node-wise trainable polynomial function the non- linear function (see Eq. 4). To prevent gradient explosion from quadratic terms, we include a small constant adjust the gradient scale of the wa parameter 4T
nn (z) C Wor wi +
(4)
Improved Convergence Through Distillation. Training a polynomial neural network from scratch often overfits, leading to accuracy loss 50 12]. To counteract this, recommend initially training baseline ReLU model as the teacher, then transferring its knowledge to the polynomial student model to lessen accuracy degradation. The student model's parameters
initialized from the teacher's 's and
polynomial function parameters start at (W2 O, wi 1, 0). To aid knowledge transfer, we use KL-divergence loss (51) and peer-wise normalized feature map difference penalty, The loss function for polynomial replacement is as follows:
L
C. (1- (
&
MSF
X
Xx,
(5)
||x
In the above equation, is employed to balance the significance between the CE loss and the KL divergence loss components, while &p acts as the penalty weight for the peer-wise feature map normalized L2 distance term, analogous to the approach in [52).
3.4 Put it Together
The comprehensive workflow of our proposed LinGCN framework outlined in Algorithm 2 Initially, we construct the student model, Ms. utilizing the parameters of the teacher model, Mr, and subsequently initialize the indicator auxiliary parameter hn for Ms. Following this, Ms undergoes training iterations involving updates for structural lincarization. Upon

---

achieving convergence, the indicator function h is fixed, and the ReLU function in Ms is replaced with polynomial function. Subsequently, we initialize Wpoty and train the final model using a combination of CE loss and the two-level distillation loss as defined in Eq. 5 The resulting model output will feature structurally pruned node-wise polynomial functions, render-
Algorithm 2 LinGCN Framework Workflow.
ing it primed for the final stage of homomorphic encryption-based inference.
Input: Pretrain ReL.U-based model Mr, lin- earization penalty je and optim. OPr. polyno- mial replacement optim. OPp
Further Operator Fusion to Save Level. Figure + shows an example of the single-layer STGCN struc-
Output: Level-reduced polynomial model
Copy Ms from Mr
ture generated by our LinGCN framework. The STGCN utilizes both input nodes information and aggregates them to generate output node features. We adopt the same AMA format [12) for GCNConv computation, as such, we are able to fuse the plaintext weights c W2 of node-wise polynomial function into GCNConv layer and save one multiplication depth budget. Layer operators involve another temporal
2: Initialize hw for Ms
3: for Structural linearization iterations do
4: Calculate L via Eq. and Algorithm
5: Update W and hw through back propaga- tion (Eq. 3 by minimizing & using OP,
6: end for
7: Freeze h... and h
8: Replace ReLU in Mr with polynomial
9: Initialize upoly
convolution layer and non- non-linear/linear layer, we can still fuse the plaintext weights c W2 from the second polynomial function into the convolution operator and save the multiplication depth budget. As such, the dee.U-redeeed example shown in Figure Fooly consumes 3 multiplication level of ciphertext op- posed to the original 4 multiplication depth budget. For the convolution operator, we adopt the same
10: for Polynomial replacement iterations do
11: Calculate Lp via 5
12: Update W through back propagation by minimizing Cp using OPp
13: end for
computation flow from [12 38).
4 Experiment
4.1 Experiment Setting
HE Parameter Setting. We performed experiments with two sets of encryption parameters: one without and one with non-linear reduction. We used a scaling factor A = 2 in both cases to ensure comparable accuracy. This scaling consumes 33 bits from the ciphertext modulus Q per level. Without non-linear reduction, a 3-layer STGCN network needs 14 levels, and a 6-layer network needs 27. For security level of 128-bit bit, we set Q to 509 (932) and the polynomial degree N to (2!62)) for 3 (6) layers STGCN network. In the non-linear reduction case, the total level count ranges from 14 for 3-layer, and 27 to 16 for 6-layer networks. With the reduced models, we can use smaller Q and N while maintaining 128-bit security. Specifically, we set Q to 410 to 344 and N to 214 for the 3-layer network (from 3 non-linear reduced), and Q to 767 to 569 and N 215 for the 6-layer network (starting from 5 non-linear reduced).
Experiment Dataset. The NTU-RGB+D dataset 21 the largest available with 3D joint annotations for human action recognition, is utilized in our study. With 56,880 action clips in 60 classes, each is annotated with (X, Y. Z) coordinates of 25 joints (nodes) per subject. We chose the NTU-cross- View (NTU-XView) benchmark given its representativeness as a human skeleton joint dataset, containing 37,920 training and 18,960 evaluation clips. For a thorough evaluation, 256 frames were used from each clip, resulting in a 2 x 3 x 256 x 25 input tensor for two individuals each with 3 channels.
Baseline Model. Our experiment runs on 8*A100 GPU server, and uses the state-of-the-a STGCN architecture for human action recognition, which combines GCN and CNN. We tested three con- figurations: STGCN-3-122 STGCN-3-256, and STGCN-6-256 where the first number represents the layer count, and the second the last STGCN layer's channel count. These networks contain a stack of three six STGCN layers, followed by a global average pooling layer and a fully-connected layer. They were trained for 80 epochs using SGD, with a mini-batch size of 64, a momentum of 0.9, weight decay of 10 10-4, and dropout 0.5. The initial learning rate (LR) was 0.1, with decay factor of 0.1 at the 10th and 50th epochs. The baseline accuracy of models can also be found in Table
LinGCN Algorithm Setting, In our LinGCN algorithm, we used the baseline model from Table D as the teacher model in Algorithm[2 For structural linearization, we used SGD optimizer with learning rate (LR) 0.01 for both weight and auxiliary parameters. The Lo norm penalty μ was varied from 0.1
7

---

Table 1: All ReLU based model architecture and accuracy
Model
Laser-wise number of channel configuration
Accuracy (%)
STGCN-3-126
1-64-128-128
80.64
STGCN-3-256
3-128-256-255 1464-64-122-128-25566
82.80
STGCN-6-256
84.52
to 10 for desired linearized layers, over 25 epochs, Then, ReLU was replaced with a second-order polynomial in the polynomial replacement iterations. We set scaling factor at 0.01, parameters and yp at 0.2 and 200 respectively. This process took 90 epochs, with SGD optimizer and initial LR of 0.01, decaying by a factor of 0.1 at the 40th and 80th epochs.
Private Inference Setup. Our experiments used an AMD Ryzen Threadripper PRO 3975WX machine, single threaded. The RNS-variant of the CKKS scheme [53] was employed using Microsoft SEAL version 3.7.2 [54]. We adopted the Adjacency Matrix- Aware (AMA) data formatting from CryptoGCN [1] pack input graph data and performed GCNConv layer inference via multiplying with sparse matrices A; split from the adjacency matrix A. The temporal convolution operation
was optimized using the effective convolution algorithm from (38 12 55
The computation for the
global average pooling layer and fully-connecter layer also follows the SOTA
38 12
Table 2: STGCN-3- 3-10 comparison
Table 3: STGCN- --2- comparison
Model
STGCN-3-128
Model
STGCN-3-256
Non- Dinelinear
Test acc
Latency
Non-linear
Test
Latency
Methods
Methods
layers
(%)
(s)
layers
(%)
(s)
LinGCN
77.55
1856.95
LinGCN
6
80.29
4632.05
LinGCN
75.48
1663.13
LinGCN
5
79.07
4166.12
LinGCN
76.33
1458.95
LinGCN
4
78.59
3699.49
LinGCN
74.27
850.22
LinGCN
3
76.41
2428.88
LinGCN
75.16
741.55
LinGCN
2
74.74
2143.46
LinGCN
69.61
642.06
LinGCN
71.98
1873.40
CryptoGCN
74.25
4273.89
CryptoGCN
6
75.31
10580.41
CryptoGCN
73.12
1863.95
CryptoGCN
5
73.78
4850.93
CryptoGCN
70.21
1856.36
CryptoGiNN
4
71.36
4831.93
4.2 Experiment Result and Comparison
LinGCN Outperforms CryptoGCN [12]. The proposed LinGCN algorithm demonstrates superior performance compared to CryptoGCN 12 The STGCN-3-128 and STGCN-3-256 models, which are the basis of this comparison, share the same backbone as those evaluated in CryptoGCN (12). Hence, we have undertaken a comprehensive cross-work comparison between the LinGCN framework and CryptoGCN [12.. The latter employs heuristic algorithm for layer-wise activation layer pruning. which necessitates a sensitivity ranking across all layers. This approach, however, proves to be ineffective, leading to significant accuracy drops as the number of pruned activation layers increases. Comparative results between LinGCN and CryptoGCN [12] are provided in Table and Table 3 In the context LinGCN, the number of non- non-linear layers presented in the table represents the effective non-linear layers post-structural linearization. For the BTGCNN-3-128 and STGCN-3-256 models, LinGCN yielded an accuracy 77.55% and 80.28% respectively for the baseline non-linear layers model, exceeding CryptoGCN [12 by 3.3% and 4.98%. This outcome signifies the superiority of our proposed teacher -uided node-wise polynomial replacement policy over the naive layer-wise polynomial replacement provided in CryptoGCN [12]
Importantly, the LinGCN model for the 6 non-linear layers employs more fine-grained node- wise polynomial function, which is fused into the preceding Conv or GCNConv layers. Thus, the encryption level required lower than that of CryptoGCN [12], resulting in reduced latency. When considering non-linear layer reduction performance, LinGCN experiences only 1.2 to 1.7 % accuracy decline with 2 effective non-linear layer reduction, whereas CryptoGCN 12 displays approximately 4% accuracy degradation when pruned for 2 non-linear layers. Remarkably, LinGCN achieves an accuracy improvement of more than 6% over CryptoGCN [12) for models with non-
linear layers. Even in models with only 2 non-linear layers, LinGCN exhibits exceptional accuracy

---

(75.16% and 74.74%). While this accuracy aligns with the performance of 6 non-linear layer models in CryptoGCN [12], LinGCN significantly outperforms it in terms of private inference latency, providing more than five-fold reduction compared to CryptoGCN [12].
Non-linear Layer Sensitivity. We conduct sensitivity analysis on the STGCN-3-256 model investigate the effect of non-linear layers. The results are displayed in Figure 5 wherein the i layers in the figure represent the remaining ef-
Non-linear nodes
11
layers
20
layers
layers
10
layers
fective non-lineat linear layers in the model, and every 2
layers
1 and 2i exhibit a total number of non-linead
nodes summing up to an integer multiple of 25. During the automatic structural linearization pro- cess, the gradient propagation is orchestrated to strike balance between two goals: (i) preserving the feature structural information at the deeper layers, and (ii) mitigating the over-smoothing effect [56] resulting from the deep linearized GCN layers. Consequently, the middle 4th layer's nonlinearity is most important within the STGCN model.
Non-linear layer Index
Figure 5: STGCN-3 structural linearization
LinGCN is Scalable. Beyond the evaluation of the 3-layer model. we also apply our LinGCN to a 6-layer STGCN-6-255 model, which no prior work evaluated, maintaining the same set- tings to assess the trade-off between accuracy and latency. An intriguing finding is that the teacher-guided full polynomial replacement not only maintains model performance but also sur- passes the accuracy of the teacher baseline by 0.95%, achieving an accuracy 85.47%. This suggests that the STGCN model equipped with a smooth polynomial activation function may enhance model expressivity. Experiments reveal a significant redundancy in the non-linear layers of the STGCN-6 2C66--256 model, accuracy degradation up to the reduction of 8 non-linear layers. When the pruning extends to 10 non-linear layers, the accuracy experiences slight dip of 3.2% compared to the non-reduction one.
Table 4: LinGCN for STGCN-6-256 model.
Model
STGCN-6 --6
Non-linear layers
Test acc
Latency
Methods
(%)
(S)
LinGCN
12
85.47
21171.80
LinGCN
11
86.24
19553.96 9
LinGCN
7
85.08
8186.35
LinGCN
5
83.64
7063.51
LinGCN
4
85.78
6371.39
LinGCN
3
84.28
5944,81
LinGCN
2
82.27
5456.12
LinGCN
75,93
4927.26
it exhibits
Pareto Frontier of LinGCN. Figure Soareecomppe compares the Pareto frontier between LinGCN and Cryp- toGCN 112, showing LinGCN consistently surpassing CryptoGCN by at least 4% in accuracy across all latency ranges. As latency constraints ease (around 6000s), LinGCN's accuracy notably increases, improving by roughly 10% over CryptoGCN. Impressively, LinGCN maintains accuracy of 75.16% while achieving a private inference latency of 742s, making it 14.2 times faster than CryptoGCN.
4.3 Abalation Studies
Non-linear Reduction Replacement Sequence matters. Our LinGCN algorithm employs a sequence of non-linear reduction and polynomial replacement, proving more efficacious in terms of search space convergence compared to the inverse sequence of polynomial replacement followed by non-linear reduction. The reasoning behind this lies in the possibility that the polynomial replacement process may produce a model optimized for a given architecture, hence subsequent changes to the architecture, such as non-linear reduction, could lead to significant accuracy degradation. Keeping all other parameters constant and merely altering the replacement sequence, we present the accuracy evaluation results of STGCN-3-255 model in Figure 6a) As depicted in the figure, the sequence of polynomial replacement followed by non-linear reduction incurs an accuracy degradation exceeding 2% compared to the baseline sequence across all effective non-linear layer ranges.
LinGCN Outperforms Layer-wise Non-linear Reduction. A significant innovation in our LinGCN framework is the structural linearization process. This process allows nodes to determine their preferred positions for -inearitssss within a single STGCN layer, as opposed to enforcing a rigorous constraint to excise the non-linearity across all nodes. This less restrictive approach yields more detailed replacement outcome compared to the layer-wise non-linear reduction. To demonstrate the impact of this method, we kept all other parameters constant for of STGCN-3-256 model, altering

---

Test Accuracy
80
80.0
80.2
80.2
75
80.0
80.0
70
Baseline
75.0
72.5
Laser
Baseline
79.8
ablation
79.8
79.6
ablation
0.2
0.4
0.4
Non-lincar layers
Non-linear layers
n
(a)
(h)
(c)
(d)
Figure 6: Ablation study for (a) Replacement sequence, (b) node- vs, layer-wise linearization.
(c) qf KI. divergence distillation parameter (d) yp: feature map distance distillation parameter.
only the structural linearization to layer-wise linearization, and subsequently evaluated the model's accuracy, as shown in Figure 6b The results indicate that layer-wise linearization results in 1.5% decrease in accuracy compared to structural linearization within the range 2 to effective non-linear layers. This demonstrates the effectiveness of the proposed structural linearization methodology.
Distillation Hyperparameter Study. In prior experiments, kept 7) and (p 0.2 and 200 respec- tively. To assess their influence during distillation, we tested and o across range of values while distilling the STGCN-3-256 model with 6 non-linear layers. We test 1) E [0.1, 0.2, 0.3, 0.4, 0.5] and [100, 200, 300, 400, 500]. Notably, we maintained oo ablations. The study, shown in Figure and Figure [d] confirms that 17 = 0.2 and 1 200 yield optimal accuracy. and larger penalties might lower accuracy due to mismatch with the teacher model. This study thus justifies justifiss our selection of the 7) and ip.
200 and 7) = 0.2 for the respective 17 and
LinGCN Generalize to Other Dataset. With- extended our eval-
loss of generality, uation on Flickr (57) dataset, which rep- resentative node classification dataset widely used in GNN tasks.It consists of 89,250 nodes, 989,006 edges, and 500 feature dimensions. This dataset's 's task involves categorizing images based on descriptions and common online prop- erties. For the security setting, we assume that node features are user-owned and the graph adjacency list public. The Flickr dataset has a larger adjacent list but smaller feature dimension compared to the NTU-XVIEW dataset. We utilize three GCN layers with 256 hidden dimensions. Each GCN layer has similar structure as STGCN backbone architecture and has two lincar and nonlinear layers. We conduct full-batch GCN training to obtain ReLU-base baseline model accuracies of 0.5492/0.5521 for validation/test dataset. We obtain the accuracy/latene, tradcoff detailed in the Table 5 LinGCN framework substantially diminishes the number effective nonlinear layers, which leads to 1.7 times speedup without much accuracy loss.
Table 5: LinGCN for Flickr dataset.
Num. of nonlinear
Accuracy (val/test, %)
Latency
layers in GCN layers
(s)
6
0.5281/0.5275
4290.93
2
0.5247/0.5266
2740.94
0.5269/0.5283
2525.80
5
Discussion and Conclusion
Our LinGCN optimizes HE-based GCN inference by reducing multiplication levels through differentiable structural linearization algorithm and a compact node-wise polynomial replacement policy, both guided by two-level distillation from an all-ReLU teacher model. Additionally, improve HE solutions for GCN private inference, enabling finer operator fusion for node-wise activation functions. LinGCN outperforms CryptoGCN by 5% in accuracy and reducing latency by 14.2 times at -75% accuracy, LinGCN sets a new state-of-the-art performance for private STGCN model inference. In the future, will expand the proposed algorithm on other neural networks.
Acknowledgement
This work was part supported by the NSF Grants CNS-2348733, 2247892, 2247893, OAC-2319962, Semiconductor Research Corporation (SRC) Artificial Intelligence Hardware program, and UConn CACC center. Any opinions, findings and conclusions, or recommendations expressed in this material those of the authors and do not necessarily reflect the views of the funding agencies.
10

---

References
[1] Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in point cloud. In CVPR, pages 1711-1719, 2020.
[2] Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: survey. Expert Systems with Applications, page 117921, 2022.
[3] 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.
[4] Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In Thirty-second AAAI conference artificial intelligence, 2018.
[5] 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.
[6] Pietro Bongini et al. Molecular generative graph neural networks for drug discovery. Neuro- computing, 450:242-252, 2021.
[7] Anuroop Sriram et al. Towards training billion parameter graph neural networks for atomic simulations. ArXiv, (at//2203.09997, 2022.
[8] Daniel Manu et al. Co-exploration of graph neural network and network-on-chip design using automl. In Proceedings of the 2021 on Great Lakes Symposium on VLSI, pages 175-180, 2021.
[9] Rex Ying et al. Graph convolutional neural networks for web-scale recommender systems. KDD '18, 2018
[10] Rong Zhu et al. Aligraph: A comprehensive graph neural network platform. KDD '19, 2019.
[11] Ling Liang, Jilan Lin, Zheng Qu, Ishtiyaque Ahmad, Fengbin Tu, Trinabh Gupta, Yufei Ding, and Yuan Xie. Spg: Structure-private graph database via squeezepir. Proceedings of the VLDB Endowment, 16(7):1615-122,, 2023.
[12] Ran Ran, Wei Wang, Quan Gang, Jieming Yin, Nuo Xu, and Wujie Wen. Cryptogen: Fast and scalable homomorphically encrypted graph convolutional network inference. Advances in Neural Information Processing Systems, 35:37676-37689, 2022.
[13] Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning: Revisited and enhanced. In Applications and Techniques in Infor- mation Security: 8th International Conference, ATIS 2017, Auckland, New Zealand, July 6-7, 2017, Proceedings, pages 100-110. 110. Springer, 2017.
[14] Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
[15] 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 437. Springer, 2017.
[16] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1 36, 2014.
[17] Amartya Sanyal, Matt Kusner, Adria Gascon, and Varun Kanade. Tapas: Tricks to accelerate (encrypted) prediction service. In International Conference on Machine Learning, pages 4490-4499. PMLR, 2018
[18] Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast homomorphic evaluation of deep discretized neural networks. In Advances in Cryptology-CRII CERCyC-CCCTOOOOO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III 38, pages 483-512. Springer, 201 8.
[19] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Cryptonets: Applying neural networks encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMLR, 2016.
[20] Alon Brutzkus, Ran Bachhach, and Oren Elisha. Low latency privacy preserving inference.
In International Conference on Machine Learning, pages 812-821. PMLR, 2019.
11

---

[21] Amir Shahroudy. Jun Liu, Tian-T 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.
[22] Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang. Deep high-resolution representation learning for human pose estimation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5693-5703, 2019.
[23] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. Proceedings of the IEEE international conference on computer vision, pages 2961-2969, 2017.
[24] 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 on computer vision and pattern recognition, pages 7291-7299, 2017.
[25]
Kim Laine. Simple encrypted arithmetic library (seal) manual, 2017.
[26] Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Jeffrey Hoffstein, Kristin Lauter, Satya Lokam, Dustin Moody, Travis Morrison, et al. Security of homomorphic encryption. #oomomorphiccnncrppiii
org, Redmond WA, Tech. Rep, 2017.
[27] Craig Gentry. A fully homomorphic encryption scheme. Stanford university, 2009.
[28]
Ilaria 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.
[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] Zahra Ghodsi, Akshaj Kumar Veldanda, Brandon Reagen, and Siddharth Garg. Cryptonas: Private inference on relu budget. Advances in Neural Information Processing Systems, 33:16961-16971, 2020.
[31] Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-party computation meets machine learning. Advances in Neural Information Processing Systems, $4:4961-4973 2021.
[32] M Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, Kristin Lauter, and Farinaz Koushanfar. { XNOR-basedy oblivious deep neural network inference. In 28th USENIX Security Symposium (USENIX Security 19), pages 1501-1518, 2019.
[33] Minsu Cho, Zahra Ghodsi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Sphynx: Relu-efficient network design for private inference. arXiv preprint arXiv:2106. 1 1175,, 2021.
[34] 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.
[35] Minsu Cho, Ameya Joshi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Selective network linearization for efficient private inference. In International Conference Machine Learning, pages 3947-3961. PMLR, 2022.
[36] 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.
[37] Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. Chet: an optimizing compiler for holmoohomooorphic neural- network inferencing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 142-156, 2019.
[38] 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.
[39] 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:2104.099 2021.
[40] Hongwu Peng, Shaoyi Huang, Tong Zhou, Yukui Luo, Chenghong Wang. Zigeng Wang, Jiahui Zhao, Xi Xie, Ang Li, Tony Geng, et al. Autorep: Automatic relu replacement for fast private network inference. arXiv preprint 2tt::2208.1001.... 2023.
12

---

[41] Hongwu Peng. Shanglin Zhou, Yukui Luo, Nuo Xu, Shijin Duan, Ran Ran, Jiahui Zhao, Chenghong Wang, Tong Geng, Wujie Wen, al. Pasnet: Polynomial architecture search framework for two-party computation-based secure neural network deployment. In 2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1-6. IEEE, 2023.
[42] Hongwu Peng. Shanglin Zhou, Yukui Luo, Nuo Xu, Shijin Duan, Ran Ran, Jiahui Zhao, Shaoyi Huang, Xi Xie, Chenghong Wang, et al. Rrnet: Towards relu-reduced neural network for two-party computation based private inference. arXiv preprint arXiv:2302.02222: 2023.
[43] Qian Lou, Yilin Shen, Hongxia Jin, and Lei Jiang. Safenet: A secure, accurate and fast neural network inference. In International Conference on Learning Representations, 2021.
[44] Mingbao Lin, Yuxin Zhang, Yuchao Li, Bohong Chen, Fei Chao, Mengdi Wang, Shen Li, Yonghong Tian, and Rongrong Ji. Ixn pattern for pruning convolutional neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[45] Tao Zhuang, Zhixuan Zhang, Yuheng Huang, Xiaoyi Zeng. Kai Shuang, and Xiang Li. Neuron- level structured pruning using polarization regularizer. Advances in neural information process- ing systems, 33:9865 9877, 2020.
[46] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. Advances in neural information processing systems, 29, 2016.
[47] Suraj Srinivas, Akshayvarun Subramanya, and R Venkatesh Babu. Training sparse neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition workshops, pages 138-145, 2017.
[48] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding ttraight-through estimator in training activation quantized neural nets. arXiv preprint arXiv: 1903.
(rXiv:1903.005 050622, 2019.
[49] Xia Xiao, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network pruning by regularizing auxiliary parameters. Advances in neural information processing systems, 32, 2019.
[50] Ramy E Ali, Jinhyun So, and A Salman Avestimehr. On polynomial approximations for privacy-preeevving and verifiable relu networks. arXiv preprint 1rXiv:2011.05530 2020.
[51] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprinl arXiv: /503.02531/ 2015.
[52] Sergey Zagoruyko and Nikos Komodakis. Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. In International Conference on Learning Representations, 2017.
[53] 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.
[54] Microsoft SEAL (release 3.7). hittps://githii com/Miccoooof//SAAL. September 2021. Microsoft Research, Redmond, WA.
[55] Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon Seon 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-12422. PMIR, 2022.
[56] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[57] Xiao Huang, Jundong Li. and Xia Hu. Label informed attributed network embedding. In Proceedings of the tenth ACM international conference on web search and data mining, pages 731-739, 2017.
13

---

A Appendix
A.1 HE encoding with AMA format
Prior to encoding imput data into polynomials, it is necessary to map the four-dimensional tensor X E RBxCxIXx to one-dimensional vector in R using the AMA format, proposed in [12]. This transformation allows for more efficient execution of STGCN orward-compptation in the HE domain. Below, we present the definition of the Vec function employed to map tensor X to a vector in N/2
MNN22.) Vec(X) = (Ho..)... Wi.j..... (..j.-..-MN/22.) E RN2
s.t. Vi.j = X(( mod TT%B)))FBB)))) (i
(6)
JEJ
Following the mapping process, the vectors Yj are encoded into polynomials with degree N and subsequently encrypted into ciphertext ctj, as detailed in [53]. In this study, when N is 2 all tensors, including intermediate tensors, can be encrypted and packed into 25 ciphertexts, which corresponds the number of nodes. For cases where N 2 (214) the number of ciphertexts is 50(100). By selecting an appropriate value for N, the encryption and packing processes can be optimized maintain performance and efficiency.
A.2 HE Setting Details
In 6 furnish comprehensive details regarding the HE inference parameters. Specifically, i-STGCN-3 denotes a 3-layer STGCN model with effective non-linear layers, while i-STGCN-6 signifies 6-layer STGCN model with effective non-linear layers. In this context, N represents the polynomial degree, and Q corresponds to the coefficient modulus.
To guarantec computation precision utilizing a one-time rescale operation, assign the scale factor p for both ciphertext and plaintext to 283 This allocation results a reduction the current Q of ciphertext by p bits. This setup ensures that the overall performance and accuracy conform to the desired criteria while capitalizing on the security and resilience advantages conferred by HE.
Table 6: HE parameter settings in detail.
Encryption Parameters
Mult
Model
N
Q
p
go
Level
6-STGCN-3
32768
509
33
47
14
5-STGCN-3
32768
476
33
47
4SSGCN-33
32768
443
33
47
12
3-STGCN-3
16384
410
33
47
11
2-STGCN-3
16384
377
33
47
10
1-STGCN-3
16384
344
33
47
9
12-STGNN-6
65536
932
33
41
27
11-STGNN-6
65536
899
33
41
26
7-STGCN-6
32768
767
33
41
22
5-STGCN-6
32768
701
33
41
20
4-SGCN-66
32768
668
33
41
19
3-STGCN-6
32768
635
33
41
18
2-STGCN-6
32768
602
33
41
17
I-STGCN-6
32768
569
33
41
16
A.3
HE inference on GCNConv and Temporal-Cony Layer
Upon obtaining the AMA-packed ciphertexts clj, the adjacency matrix multiplication A X can be decomposed into series of plaintext multiplications, PMult, in the HE domain. This decomposition accelerates HR-inference without necessitating rotations. Furthermore, the subsequent temporal convolution is performed solely the temporal dimension I,, utilizing 9 kernels.
14

---

Table Comparison of latency breakdown between the non-reduced model with optimized model.
HE Operators
latency (s)
Total Latency
Speedup
Model
Rot
PMult
Add
CMult
(s)
(x)
6-STGCN-3-128
1336.25
378.25
99.65
37.45
1851.60
2-STGCN-3-128
392.21
266.13
68.90
14.31
741.55
2.50
6-STGCN-3-256
2641.09
1508.19
397.17
74.90
4621.36
2-STGCN-3-256
777.68
1062.21
274.96
28.63
2143,47
2.16
12-STGCN-6-255
18955.09
1545.09
396.23
275.39
21171.80
2-STGCN-6-25
4090.08
1006.79
244.19
115.05
5456.12
3,88
771
ct A X
ct
PMult(ct,, (lck)
k=
The AMA-packed ciphertexts allow for natural temporal convolution by single-node ciphertext ctj. facilitating independent computation. This approach results Rel.U-reduucion design through structural pruning of ReLUs.. The primary constraint to consider in this context is ensuring that the level consumption of each ciphertext remains equal prior the GCNConv layer (node aggregation).
A.4 Further Detail of Operator Fusion
During the HE-inference process, employing weight fusion conserves the multiplicative depth, consequently reducing the ciphertext level budget. For instance, batch normalization, defined by an affine transformation a' at + b', and polynomial activation function, defined by (ax: + b)2 + can be readily fused into the corresponding temporal convolution layer wz + 6" with the function a-aaa-a"a)))) a') + ab' + +wb+b" As a result, three consecutive multiplications are consolidated into single multiplication (pre-computing w a aa), thereby reducing the level consumption of ciphertext from 4 to 2 (1 convolution, batch normalization, and polynomial activation).
w(a(a'z a + 6') +6) 1-6)+68 6" (w-a a
Analogous to the polynomial activation and batch normalization of the GCNConv layer. Utilizing AMA-packed ciphertexts, the node aggregation in GCNConv is translated as depicted in Equation 7 where each ciphertext carries out scalar multiplication with the plaintext matrix elements 0i,,k- Consequently, these plaintext matrix elements 0ig.k are fused with the primary conserve the multiplicative level, reducing the total level consumption of the GCNConv layer from 4 to 2 (I x I convolution, adjacency matrix multiplication, batch normalization, and polynomial activation).
layer, the same fusion strategies can be applied to the
convolutional kernels to
A.5
Operator latency breakdown
Table 7 presents comprehensive operator latency breakdown encompassing Rot, PMult, Add, and CMult operations. The designation i-STGCN-3-126 refers to an STGCN-3-128 model with i residual non-linear layers. As indicated in the table, the non-linear reduction contributes to a significant reduction in latency. By leveraging smaller polynomial degree N, the overall latency experiences substantial improvement.
A.6 More Training Details and Insight
In this section, we present the training curves for the STGCN-3-256 model, which employs 6 to I effective second-order polynomial (non-linear) layers. Figures a through Figure 7 depict the training curve progression. During the training process, we utilized mixed-precisio training for the polynomial model, which led occasional instability in iterations, evidenced by spikes in the loss values. Nevertheless, the training process demonstrated rapid recovery following such loss spikes.
As demonstrated in training curve, a smaller number of second-order polynomial (non-linear) layers contribute to more stable training process and facilitate smoother convergence. This finding
15

---

TensorBoard logged statistics
TensorBoard Iagged
TensorBoard logged
voltation sccuacy
0.9
0.9
Tamiin lo22
Toahing lass
Taa Coning loss
0.7
valhop1
vrltep1
valhop1
valitops
veltops
velñops
10000
50000
10000 20000
10000 20000 300n0 40000 sniae
(b)
TensarBoard lagged statistics
TensorBoard Iagged
TensorBoard logged statistics
aocurac
Training los2
Trainingg loss
Trining loss
valhtp1
vai/top3
val/top1
valltpp
veltop:3
velmtop
20000 50000
10000
50000
10000 20000
Itoration
(d)
(f)
Figure 7: Polynomial replacement training curves for (a) 6-STGCN-3-128 (b) 5-STGCN-3-128 (c)
4-STGCN-3-128 (d) 3-STGCN-3-128 (e) 2-STGCN-3-128 (f) I-STGCN-3-128
TensorBoard logged statistics
TensorBoard logged statistics
TensorBeard logged statistics
0.9
Valrsooon sccrary
0.9
0.9
Taininlo2 1022
Taining loss
Taning 1035
tratuloss
0.7
trainfoss
0.7
traitlesss
0.7
0.5
vallopp
valftops
10000 20000 30000 40000
50000
10000 20000 30000 40000 50000
10000 20000 30000 40000 50000
Keration
(b)
(C)
Figure 8: Polynomial replacement training curves for (a) 12-STGCN-6-22 6-256 (b) 6-STGCN-6-256 (c) 2-STGCN-6-256
explains the enhanced performance of the STGCN-6-256 model, which features a reduced number of non-linear layers, as compared to the full-polynomial model baseline.
To substantiate our hypothesis, we plot the polynomial replacement training curve for the STGCN-6- 256 model in Figure The training curves for 12 effective non-linear layers (12-STGCN-6-2566 four effective non-linear layers (4-STGCN-6-256), and two effective non-linear layers (2-STGCN-6-256) presented. As the number of non-linear layers increases, the model achieves greater expressivity; however, the polynomial replacement process becomes increasingly unstable. Consequently, for the STGCN-6-256 model with only 4 non-lineat layers, more stable replacement process facilitates better convergence, ultimately leading to improved accuracy performance.
16


Reviews:
[{"review_id": "IvBOYT2lJf", "reviewer": "Reviewer_iVPr", "summary": "This study presents an approach for enhancing the efficiency of private inference ( using homomorphic encryption (HE)) in Spatiotemporal graph convolutional networks through fine-grained and structured pruning/dropping of non-linearity. The proposed method consists of two main steps. Firstly, ReLUs are eliminated by substituting them with identity/linear operations, reducing the multiplicative depth required for HE operations. Subsequently, the remaining non-linearities are replaced with HE-friendly quadratic activations.", "questions": "1. The sensitivity analysis (Figure 5) shows that ReLUs in the penultimate layers (layer 4) are highly effective, which aligns with similar findings in CNN studies like DeepReDuce (ICML'21) and SENet (ICLR'23). What does it imply about feature learning within CNNs vs GCNs?\n\n\n2. Is the better accuracy of LINGCN over CryptoGCN only due to CryptoGCN's use of two-level Knowledge Distillation? Both these methods use second-degree polynomial activation (instead ReLUs). \n\n3. Does the accuracy mentioned in the paper refer to floating-point accuracy (in plaintext) or fixed-point accuracy (after converting weights/biases and activation to fixed-point for operations in the ciphertext domain)?\n\n\n\n**Note** I am open to increasing the score if most concerns are addressed in the rebuttal.", "limitations": "Limitations are not discussed in the paper. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The idea of optimizing ReLUs with a fine-grained and structured approach is promising. Typically, fine-grained optimizations tend to lack structure, which can reduce the overall benefits of optimization. \n\n2. The paper is well-structured and easy to understand. The proposed method is explained clearly and organized, making it accessible to readers. The authors provide detailed explanations and build a strong foundation for their approach, ensuring it can be easily grasped.", "weaknesses": "\n\n**Limited novelty (compared to CryptoGCN)**: \nCompared to the CryptoGCN paper (NeurIPS'22), this paper demonstrates limited novelty. Both papers propose techniques to reduce the multiplicative depth in STGCN and replace ReLUs with quadratic activations. However, while CryptoGCN employs fine-tuning to recover the accuracy drop, this paper utilizes logit and feature-based distillation to address the accuracy drop resulting from the reduction in non-linearity.\n\nFor a fair comparison, particularly regarding the improvement in accuracy,  an ablation study should be included in the paper to demonstrate the benefits of logit-based knowledge distillation, feature-based knowledge distillation, and the combined usage of both techniques compared to CryptoGCN.\n\n\n**CKKS implementation is used rather than rotation-free HE**\nIn this paper, the authors used the CKKS implementation of Homomorphic Encryption (HE), which incurs a significant total latency due to the rotation operations. The provided Table 2 in the Appendix demonstrates that **approximately 90%** of the total HE latency is consumed by rotation operation in the 12-STGCN-6-256 model. This highlights the inefficiency of the CKKS implementation for private inference, especially when considering the availability of rotation-free HE techniques [1] and their implementation in Microsoft-SEAL.\n\n**Minor corrections**\nAs stated in lines #157 to #161, the optimizations implemented in SNL, DELPHI, and SAFENet are sub-optimal for achieving high efficiency in HE. It is important to note that these optimizations primarily aim to minimize the cost of non-linearity in Multi-Party Computation, under the assumption that intensive HE operations can be carried out offline. \n\n\n\n\n1. Huang et al., \"Cheetah: Lean and fast secure two-party deep neural network inference,\" USENIX Security 2022. \n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for your constructive comments.\n\n\n### Response to limitation 1, novelty: \n\n\nCryptoGCN's approach to employing layer-wise nonlinear pruning and polynomial replacement results in a substantial degradation in accuracy and an insufficient reduction in multiplication depth. Our proposed LinGCN framework is different from CryptoGCN. LinGCN employs: (i) **Differentiable structural linearization**. (ii) Node-wise polynomial activation functions augmented by distillation. (iii) Exploration of nonlinear reduction via polynomial sequences. (iv) Homomorphic Encryption (HE) for enabling finer-grained operator fusion.The LinGCN is designed to significantly reduce multiplication depth and yield much better performance compared to CryptoGCN.\n\n\nThe effects of these strategies have been empirically demonstrated in the ablation study, as illustrated in Figure 6 (Page 9), which encompasses the (a) replacement sequence, (b) node-wise or layer-wise nonlinear reduction, (c) logit-based distillation, and (d) feature-based distillation.\n\n\n\n### Response to limitation 2, encryption scheme: \n\n\nOur research has a different threat model setting in comparison to the setting described in [1]. Specifically, the rotation-free Homomorphic Encryption (HE) described in [1] requires client assistance for private inference, assuming that clients have significant computational capabilities and can actively participate in the encrypted computation process. This method, which leverages the BFV scheme for ciphertext multiplication, requires the client to decrypt the extracted LWE ciphertext, re-encrypt intermediate results, and transmit new ciphertexts to the server for subsequent layer computation. Overall, the framework in [1] introduces computational and network communication bottlenecks from the client side. \n\n\nIn contrast, our methodology is focused on an HE without-client-aid setting, in which the server solely requires the client to encrypt and transmit input data once. Then, the server autonomously conducts the necessary computations.\n\n\nOur HE without-client-aid setting and the MPC+HE setting in [1] represent two orthogonal strategies for implementing Privacy-Preserving Machine Learning (PPML). Each approach caters to distinct private inference scenarios. The primary objective of our LinGCN framework is to alleviate the server's computational burden within the context of an HE without-client-aid setting.\n\n\n[1] Huang et al., \"Cheetah: Lean and fast secure two-party deep neural network inference,\" USENIX Security 2022.\n\n\n### Response to limitation 3, minor corrections:\n\n\nThanks for the suggestion, existing works such as SNL, DELPHI, and SAFENet focus on latency reduction of online inference with MPC-only framework, and those optimizations can not directly benefit the CKKS based HE for offline inference framework. We will clarify it further in the final version. \n\n\n### Response to question 1:\n\nThe results of our experiment indicate that the last layer's nonlinearity is more prone to be linearized, whereas the 4th layer serves as the most vital nonlinear layer. This observation is consistent with works in CNN, as evidenced in studies such as SNL, DeepReDuce, and SENet. Within these models, the importance trend of nonlinearity layers appears to follow a pattern that fluctuates from low to high and then reverts to low across the network layers.\n\nWe further have conducted evaluation on a new graph dataset (i.e., Flickr). Pelase referr to the **Global Response (i)** for more details. We will incorporate those discussions in the final version.\n\n### Response to question 2: \n\nPlease refer to the **Response to limitation 1** and **Global Response (ii)**\n\n### Response to question 3:\n\nThe accuracy mentioned in our paper indicates the floating-point accuracy (in plaintext). We use the 2^33 scaling factor to transform the input into fixed points for encoding & encryption settings, which is the same as SOTA, e.g., CryptoGCN. As mentioned in CryptoGCN, the large scaling factor and  bit width margin makes sure the ciphertext inference has the same accuracy as plaintext. We will include further discussion about plaintext/ciphertext encoding and accuracy in the final version. \n\n"}, {"review_id": "Hq3nwtlqmr", "reviewer": "Reviewer_6Lak", "summary": "LinGCN optimizes HE-based GCN inference by reducing multiplication levels through a differentiable structural linearization algorithm and a compact node-wise polynomial replacement policy, both guided by a two-level distillation from an all-ReLU teacher model. LinGCN also improves HE solutions for GCN private inference, enabling finer operator fusion for node-wise activation functions. ", "questions": "The curves in Figure 1 is confusing. Why the blue curve encompasses a variety of points (red stars, orange dots, and blue dots)? Similarly, the black curve also exhibits this characteristic.\n\n", "limitations": "The paper does not discuss the limitations of the current work nor does it discuss any negative societal impact. Concentrating solely on non-linear operations may not be sufficient for achieving PPML-efficient architectures. This is particularly true in light of emerging lighter cryptographic topologies for non-linear operations, such as those discussed in the following work:\n\nHuang, Zhicong, et al. \"Cheetah: Lean and fast secure {two-party} deep neural network inference.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 Important and well-motivated problem\n\n2 Experiments show a clear improvement in latency and accuracy compared to prior work. ", "weaknesses": "While the concepts of structural linearization and the replacement of ReLU with a polynomial function are not novel in themselves, their application to Graph Convolutional Networks (GCN) is noteworthy. However, it's important to mention that the degree of novelty in this approach is not particularly significant, given the pre-existing knowledge in this field.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for your valuable comments.\n\n\n### Response to weakness: \n\n\nThanks for the important feedback. Our main contribution **structural linearization** for multiplication depth reduction is intrinsically different from existing linearization methods (unstructured linearization, layer-wise linearization) used in CNN works and CryptoGCN. **structural linearization** based multiplication depth reduction especially benefits the CKKS based HE setting. To the best of our knowledge, none of the SOTA CNN works (e.g., SNL, DELPHI) have adopted the **structural linearization** method. The polynomial replacement itself is only one of the contributions in our LinGCN framework. Our major contributions are summarized in **Global Response (ii)**.\n\n### Response to question:\n\n\nThanks for the suggestions. As indicated in the figure legend, blue curve is the pareto frontier of the LinGCN framework. Red stars means STGCN-3-128 model used in LinGCN framework. Orange dots means STGCN-3-256 model used in LinGCN framework, and blue dots means STGCN-6-256 model used in LinGCN framework. The black dots and black curve represent the model performance data points collected from CryptoGCN and its pareto frontier. We will include more descriptions in the legend and make the figure clearer in the final version. \n\n### Response to limitations: \n\n\nCheetah requires the client's assistance while conducting computation because it uses a MPC + HE  based framework. While our work’s setting does not require the client’s assistance because we use CKKS based HE scheme for private inference. The ciphertext multiplication method used in [1] is BFV, in which it requires the client to do the decryption for the extracted LWE ciphertext, re-encryption for intermediate results and send the new ciphertexts to the server, then the server can perform the next layer’s computation. Client computation and communication are the bottleneck in their proposed method [1]. The major latency bottleneck  in our CKKS based HE system is the **multiplication depth** which is associated with the linear and nonlinearity operation, and is not the nonlinearity itself. Hence, structural linearization helps with reducing the ring size while maintaining the same security level, and will make all operator latency to be smaller. The detailed operator latency breakdown with **multiplication depth reduction** can be found in the Appendix Table 2. The table shows the rotation is the major performance bottleneck, not the nonlinearity operator itself. \n\n\n[1] Huang et al., \"Cheetah: Lean and fast secure two-party deep neural network inference,\" USENIX Security 2022.\n\n\n"}, {"review_id": "jSCGhPMoAM", "reviewer": "Reviewer_KG27", "summary": "To improve the efficiency of HE-based PPML for GCN, in this paper, the authors propose LinGCN, an end-to-end framework for non-linear reduction and polynomial replacement. LinGCN features 3 key elements, including 1) a differentiable structural linearization algorithm, 2) a compact node-wise polynomial replacement policy, and 3) finer-grained operator fusion for node-wise activation functions. The authors demonstrate good improvement over the baseline CryptoGCN.", "questions": "1. What can LinGCN achieve better accuracy compared to CryptoGCN? What if similar distillation is leveraged for CryptoGCN as well?\n\n2. How are the proposed linearization method different compared to those used for CNNs, like Selective Network Linearization (SNL), RRNet, etc.\n\n3. How does the proposed method generalize to other datasets or tasks?", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and the motivation is well-explained.\n2. The authors demonstrate both higher accuracy and lower latency compared to the baseline CrypoGCN.\n3. The ablation experiments is comprehensive.", "weaknesses": "1. Only one dataset is shown in the paper. This makes it doubtful for how well the proposed techniques generalize to other datasets, e.g., Cora?\n\n2. Similar techniques have all been proposed by previous method. For example, ReLU linearization and polynomial replacement are widely studied for CNN. The proposed fusion technique is also widely used in plaintext CNN inference. Although the synchronized linearization is unique for GCN, it still makes the proposed method incremental.\n\n3. It is unclear why LinGCN demonstrates better accuracy compared to CryptoGCN. Although KD is helpful, more analysis needs to be provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your insightful review.\n\n### Response to question 1 (Combined response with weakness 3): \n\nPlease refer to **Global Response (ii)** for further detail. \n\n### Response to question 2 (Combined response with weakness 2): \n\nThanks for the valuable insight. To the best of our knowledge, our LinGCN framework is the first attempt to apply fine-grained **structural linearization** in CKKS based HE settings for GCN to significantly reduce the multiplication depth. Although LinGCN shares some similarity between existing CNN works such as SNL and RRNet, the fundamental problem we are trying to solve is different. LinGCN focuses on leveraging **structural linearization** methods to **reduce the multiplication depth** in CKKS based HE setting, and it can benefit all HE based operators (refer to Table 2 in appendix). SNL and RRNet try to partially replace ReLU with linear or polynomial function to reduce the nonlinear operator latency of the private inference under MPC setting. And those methods in CNN works cannot benefit CKKS based HE setting, as discussed in the manuscript from line 157 to line 175. Our LinGCN is the first to significantly advance the benchmark for fine-grained multiplication depth reduction, representing a new baseline to accelerate the HE-based GCN private inference-an emerging field that has been far less explored than that in CNN. We believe our new results and insights would help the community further move forward in this important field.\n\n### Response to question 3 (Combined response with weakness 1): \n\nThe proposed LinGCN is evaluated on NTU-XVIEW skeleton joint dataset, one of the largest graph datasets which has been evaluated in CKKS based HE scheme so far. We also evaluate the performance using three model variants:STGCN-3-128, STGCN-3-256, and STGCN-6-256, where the first number represents the layer count, and the second number represents the last STGCN layer's channel count. \n\nPer reviewer request, we provide an extended evaluation of LinGCN framework on GCN model for **Flickr dataset**. The Flickr dataset consists of 89,250 nodes, 989,006 edges, and 500 feature dimensions. This dataset's task involves categorizing images based on descriptions and common online properties. Please refer to **Global Response (i)** for further details. \n\n"}, {"review_id": "UcNpQrXpNn", "reviewer": "Reviewer_Y6MP", "summary": "The paper propose a novel framework called LinGCN, which reduces the multiplication depth and optimize the performance of Homomorphic Encryption based GCN inference. According to the evaluation results, LinGCN shows promising results in both latency speedup and inference accuracy over existing approaches. ", "questions": "See the weakness part above. ", "limitations": "See the weakness part above. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written, with illustrative figures on the framework and evaluation results.\n* I'm not an expert in privacy-preserving computation, but the evaluation results seem promising to me. The proposed framework not only improves the latency speedup but also the inference accuracy. Behind the stage is their proposed differentiable structural linearization, which reduces the multiplication depth in the HE process. \n", "weaknesses": "* The authors should better provide analytical results on the reduced computational cost and the utility loss. I mean although the intuition and the methodology design is convincing, some analytical statements may further support the empirical results. \n* The authors should also discuss how the security of the HE-based GCN inference process is influenced with the modified designs proposed in the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for your valuable insight. \n\n### Response to weakness 1: \n\nWith a reduced multiplication depth,computational cost and latency will also reduce. Analytically, the Q parameter is reduced with shallower depth, the coefficient of ciphertext polynomial also has a lower bit size, which reduces the data loading time and operators’ computational latency. Further analytical details on computation and latency reduction can be found in **Table 2** in the **appendix**. \n\n### Response to weakness 2: \n\nThe proposed LinGCN framework **does not impact** the security level of CKKS based HE framework. For all experiments with the multiplication depth reduction setting, we guarantee a fixed 128 bits margin for security level. Further details can be found in Table 1 in appendix. Here we provide a brief explanation: \n\nInitially, we have to guarantee a security level of at least 128 bits, which is determined by the encryption parameter N and Q. With one level saved, the budget of Q will also decrease. \n\nFor example, with N=16384, the maximum Q=438 could guarantee a 128 bits security level. For a non-optimized 3-ST-GCN model, it required Q=509 bits to complete the HE inference (N=32768).  With one activation pruned, we save Q by 33 bits. Thus, after we pruned 3 activation layers of this model, Q = 509-33*3=410. Then, we can reduce the N from 32768 to 16384 and still guarantee a 128 bits security level.\n"}]

Author rebuttal:
## Global Response:


We truly appreciate your valuable and constructive comments. We have made a substantial effort to clarify your doubts and enrich our experiments in the rebuttal phase. Below are the responses to two common doubts: 


### (i). New dataset evaluation: 


Without loss of generality，we extended our evaluation on flickr dataset, which is a representative node classification dataset widely used in GNN tasks.It consists of 89,250 nodes, 989,006 edges, and 500 feature dimensions. This dataset's task involves categorizing images based on descriptions and common online properties.


For the security setting, we assume that node features are user-owned and the graph adjacency list is public. The Flickr dataset has a larger adjacent list but smaller feature dimension compared to the NTU-XVIEW dataset. We utilize three GCN layers with 256 hidden dimensions. Each GCN layer has similar structure as STGCN used in our paper. We conduct full-batch GCN training to obtain ReLU-based baseline model accuracies of 0.5492/0.5521 for validation/test dataset.


We obtain the accuracy/latency tradeoff detailed in the following table.


| Num. of nonlinear layers  in GCN layers | Accuracy (val/test, %) | Latency (s) |
|:---------------------------------------:|:----------------------:|:-----------:|
|                    6                    |      0.5281/0.5275     |     4290.93252s     |
|                    2                    |      0.5247/0.5266     |     2740.93779s     |
|                    1                    |      0.5269/0.5283     |     2525.79771s     |


We observe that the proposed LinGCN framework substantially diminishes the number of effective nonlinear layers and thus reduces the multiplication depth, with comparable accuracy. This leads to an expedited private inference within the GCN model (1.7 times speedup). The experiments on the  Flickr dataset substantiate the generalization capability of the LinGCN framework, reinforcing the robustness of our proposed methods.


### (ii) Contributions and ablation study: 


The superior performance of the LinGCN framework over CryptoGCN is not solely attributable to KD. As Figure 6(c)(d) (page 9) in the ablation studies reveal, a two-level KD process contributes to an approximate 1% improvement in accuracy. The LinGCN framework achieves both enhanced accuracy and reduced multiplication depth through a multifaceted approach that includes: (i) **Differentiable structural linearization**. (ii) Node-wise polynomial activation functions, coupled with distillation. (iii) Nonlinear reduction through polynomial sequence exploration. (iv) Extended Homomorphic Encryption (HE) solutions to enable finer-grained operator fusion.


Collectively, these contributions render the LinGCN's performance markedly superior to CryptoGCN. Figure 6 in the Ablation study further elucidates the effects of these factors on the results, showcasing the (a) replacement sequence, (b) node-wise or layer-wise nonlinear reduction, (c) logit-based distillation, and (d) feature-based distillation.


Meta-review: The paper received 4 reviews, and the authors did a solid job in addressing all the reviewer comments and suggestions. This includes running new experiments to analyze performance and run-time. Overall, the general view of the reviewers was quite positive and leaning to accept. They generally commended the authors on proposing a well-founded method and providing a fresh perspective on the subfield of GCNs. The rebuttal seems to have addressed all reviewer concerns.
Decision: Accept (poster)