VIRGOS: Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition

Securely computing graph convolutional networks (GCNs) is critical for applying their analytical capabilities to privacy-sensitive data like social/credit networks. Multiplying a sparse yet large adjacency matrix of a graph in GCN--a core operation in training/inference--poses a performance bottleneck in secure GCNs. Consider a GCN with $|V|$ nodes and $|E|$ edges; it incurs a large $O(|V|^2)$ communication overhead. Modeling bipartite graphs and leveraging the monotonicity of non-zero entry locations, we propose a co-design harmonizing secure multi-party computation (MPC) with matrix sparsity. Our sparse matrix decomposition transforms an arbitrary sparse matrix into a product of structured matrices. Specialized MPC protocols for oblivious permutation and selection multiplication are then tailored, enabling our secure sparse matrix multiplication ($(SM)^2$) protocol, optimized for secure multiplication of these structured matrices. Together, these techniques take $O(|E|)$ communication in constant rounds. Supported by $(SM)^2$, we present Virgos, a secure 2-party framework that is communication-efficient and memory-friendly on standard vertically-partitioned graph datasets. Performance of Virgos has been empirically validated across diverse network conditions.