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

• DOI: 10.48550/arxiv.2502.09808
• Publication Date: 2025-02-13
• Authors: Yu Zheng; Q. Y. Zhang; Lichun Li; Kai Zhou; Shan Yin
• Keywords: Matrix (chemical analysis); Dense graph

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 in GCN--a core operation training/inference--poses performance bottleneck secure GCNs. Consider GCN with $|V|$ nodes and $|E|$ edges; it incurs $O(|V|^2)$ communication overhead. Modeling bipartite graphs leveraging the monotonicity non-zero entry locations, we propose co-design harmonizing multi-party computation (MPC) sparsity. Our decomposition transforms an arbitrary into product structured matrices. Specialized MPC protocols oblivious permutation selection multiplication are then tailored, enabling our ($(SM)^2$) protocol, optimized these Together, techniques take $O(|E|)$ constant rounds. Supported by $(SM)^2$, present Virgos, 2-party framework that communication-efficient memory-friendly on standard vertically-partitioned datasets. Performance Virgos has been empirically validated across diverse network conditions.