Abstract: Graph Convolutional Neural Networks (GCNs) have gained widespread popularity in various fields like personal healthcare and financial systems, due to their remarkable performance. Despite the growing demand for cloud-based GCN services, privacy concerns over sensitive graph data remain significant. Homomorphic Encryption (HE) facilitates Privacy-Preserving Machine Learning (PPML) by allowing computations to be performed on encrypted data. However, HE introduces substantial computational overhead, particularly for GCN operations that require rotations and multiplications in matrix products. The sparsity of GCNs offers significant performance potential, but their irregularity introduces additional operations that reduce practical gains. In this paper, we propose FicGCN, a HE-based framework specifically designed to harness the sparse characteristics of GCNs and strike a globally optimal balance between aggregation and combination operations. FicGCN employs a latency-aware packing scheme, a Sparse Intra-Ciphertext Aggregation (SpIntra-CA) method to minimize rotation overhead, and a region-based data reordering driven by local adjacency structure. We evaluated FicGCN on several popular datasets, and the results show that FicGCN achieved the best performance across all tested datasets, with up to a $4.10\times$ improvement over the latest design.

Lay Summary:

Graph AI is transforming fields like healthcare and finance by analyzing complex relationships in data, but cloud-based services raise serious privacy concerns for sensitive information. While encryption protects data, it often makes AI computations painfully slow - especially for advanced models like Graph Convolutional Networks (GCNs) that need to process intricate connections. Our solution, FicGCN, breaks this bottleneck by cleverly optimizing how encrypted graph data gets processed. By reorganizing data more efficiently and eliminating unnecessary cryptographic operations, FicGCN achieves something remarkable: it runs privacy-preserving GCNs up to 4.1 times faster than current methods while maintaining complete security. This breakthrough means hospitals can safely analyze patient records in the cloud, financial institutions can detect fraud without exposing sensitive transactions, and various industries can finally harness powerful graph AI without compromising privacy. The technology represents a crucial step toward making privacy-preserving artificial intelligence practical for real-world applications that affect millions of people.