  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.2x latency speedup relative to CryptoGCN, while preserving
an inference accuracy of 75% and notably reducing multiplication depth.
