  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 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
$\textit{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 an
approach that can effectively take advantage of the sparsity of matrix
operations in GCN inference to significantly reduce the computational overhead.
Specifically, we propose a novel AMA data formatting method and associated
spatial convolution methods, which can exploit the complex graph structure and
perform efficient matrix-matrix multiplication in HE computation and thus
greatly reduce the HE operations. 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 module 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 $\textit{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 by 77.4\% with a small accuracy
loss of 1-1.5$\%$.
