Virgos : Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition
Yu Zheng, Qizhi Zhang, Lichun Li, Kai Zhou, Shan Yin · 2025
Read Virgos : Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition by Yu Zheng, Qizhi Zhang, Lichun Li, Kai Zhou, Shan Yin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09808.txt.
Introduction
Yu Zheng and co-authors present Virgos, a secure way to run graph neural networks on split data, in this 2025 paper. Graph convolutional networks analyze networks such as social and credit graphs. That data is sensitive and often split vertically between owners. Secure computation of the core matrix step was the bottleneck.
Their trick decomposes a sparse matrix into a product of structured matrices. Custom secure protocols then multiply those pieces efficiently. Communication cost grows with the number of edges, not the square of the node count. Rounds stay constant as the graph grows. Virgos builds a full two party framework on that protocol. Tests on standard split datasets showed strong speed and low memory use.
Catalog record
| CREATOR | Yu Zheng, Qizhi Zhang, Lichun Li, Kai Zhou, Shan Yin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09808
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Virgos : Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition Yu Zheng, Qizhi Zhang, Lichun Li, Kai Zhou, Shan Yin Abstract . 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 | 𝒱 | |\mathcal{V}| nodes and | ℰ | |\mathcal{E}| edges; it incurs a large O ( | 𝒱 | 2 ) O(|\mathcal{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 ( | ℰ | ) O(|\mathcal{E}|) communication in constant rounds. Supported by (SM) 2 , we present Virgos 1 1 1 Vertically-split Inference & Reasoning on GCNs Optimized by Sparsity. , a secure 2 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. DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2025; Woodstock, NY ISBN: 978-1-4503-XXXX-X/18/06 123-A56-BU3 CCS: Security and privacy Cryptography CCS: Computing methodologies Machine learning 1. Introduction Graphs, representing structural data and topology, are widely used across various domains, such as social networks and merchandising transactions. Graph convolutional networks (GCN) ( Kipf and Welling, 2017 ) have significantly enhanced model training on these interconnected nodes. However, these graphs often contain sensitive information that should not be leaked to untrusted parties. For example, companies may analyze sensitive demographic and behavioral data about users for applications ranging from targeted advertising to personalized medicine. Given the data-centric nature and analytical power of GCN training, addressing these privacy concerns is imperative. Secure multi-party computation (MPC) ( Chaum et al., 1987 ; Chen and Cramer, 2006 ; Ciampi et al., 2022 ) is a critical tool for privacy-preserving machine learning, enabling mutually distrustful parties to collaboratively train models with privacy protection over inputs and (intermediate) computations. While research advances ( e.g. , ( Rathee et al., 2020 ; Ng and Chow, 2021 ; Tan et al., 2021 ; Watson et al., 2022 ; Keller and Sun, 2022 ; Mohassel and Rindal, 2018 ; Folkerts et al., 2023 ) ) support secure training on convolutional neural networks (CNNs) efficiently, private GCN training with MPC over graphs remains challenging. Graph convolutional layers in GCNs involve multiplications with a (normalized) adjacency matrix containing |\mathcal{E}| non-zero values in a |\mathcal{V}|\times|\mathcal{V}| matrix for a graph with |\mathcal{V}| nodes and |\mathcal{E}| edges. The graphs are typically sparse but large. One could use the standard Beaver-triple-based protocol to securely perform these sparse matrix multiplications by treating graph convolution as ordinary dense matrix multiplication. However, this approach incurs O(|\mathcal{V}|^{2}) communication and memory costs due to computations on irrelevant nodes. Integrating existing cryptographic advances, the initial effort of SecGNN ( Wang et al., 2023b ; Ran et al., 2023 ) requires heavy communication or computational overhead. Recently, CoGNN ( Zou et al., 2024 ) optimizes the overhead in terms of horizontal data partitioning, proposing a semi-honest secure framework. Research for secure GCN over vertical data remains nascent. Current MPC studies, for GCN or not, have primarily targeted settings where participants own different data samples, i.e. , horizontally partitioned data ( Zou et al., 2024 ) . MPC specialized for scenarios where parties hold different types of features ( Liu et al., 2024 ; Castiglia et al., 2023 ; Wang et al., 2023a ) is rare. This paper studies 2 -party secure GCN training for these vertical partition cases, where one party holds private graph topology ( e.g. , edges) while the other owns private node features. For instance, LinkedIn holds private social relationships between users, while banks own users’ private bank statements. Such real-world graph structures underpin the relevance of our focus. To our knowledge, no prior work tackles secure GCN training in this context, which is crucial for cross-silo collaboration. To realize secure GCN over vertically split data, we tailor MPC protocols for sparse graph convolution, which fundamentally involves sparse (adjacency) matrix multiplication. Recent studies have begun exploring MPC protocols for sparse matrix multiplication (SMM). ROOM ( Schoppmann et al., 2019 ) , a seminal work on SMM, requires foreknowledge of sparsity types: whether the input matrices are row-sparse or column-sparse. Unfortunately, GCN typically trains on graphs with arbitrary sparsity, where nodes have varying degrees and no specific sparsity constraints. Moreover, the adjacency matrix in GCN often contains a self-loop operation represented by adding the identity matrix, which is neither row- nor column-sparse. Araki et al. ( Araki et al., 2021 ) avoid this limitation in their scalable, secure graph analysis work, yet it does not cover vertical partition. To bridge this gap, we propose a secure sparse matrix multiplication protocol, (SM) 2 , achieving accurate, efficient, and secure GCN training over vertical data for the first time. 1.1. New Techniques for Sparse Matrices The cost of evaluating a GCN layer is dominated by SMM in the form of \mathsf{A}\mathsf{X} , where \mathsf{A} is a sparse adjacency matrix of a (directed) graph \mathcal{G} and \mathsf{X} is a dense matrix of node features. For unrelated nodes, which often constitute a substantial portion, the element-wise products 0\cdot x are always zero. Our efficient MPC design avoids unnecessary secure computation over unrelated nodes by focusing on computing non-zero results while concealing the sparse topology. We achieve this by: 1) decomposing the sparse matrix \mathsf{A} into a product of matrices (§ 4 ), including permutation and binary diagonal matrices, that can faithfully represent the original graph topology; 2) devising specialized protocols (§ 5 ) for efficiently multiplying the structured matrices while hiding sparsity topology. 1.1.1. Sparse Matrix Decomposition We decompose adjacency matrix \mathsf{A} of \mathcal{G} into two bipartite graphs: one represented by sparse matrix \mathsf{A}_{\mathsf{out}} , linking the out-degree nodes to edges, the other by sparse matrix \mathsf{A}_{\mathsf{in}} , linking edges to in-degree nodes. We then permute the columns of \mathsf{A}_{\mathsf{out}} and the rows of \mathsf{A}_{\mathsf{in}} so that the permuted matrices \mathsf{A}_{\mathsf{out}}^{\prime} and \mathsf{A}_{\mathsf{in}}^{\prime} have non-zero positions with monotonically non-decreasing row and column indices. A permutation \sigma is used to preserve the edge topology, leading to an initial decomposition of \mathsf{A}=\mathsf{A}_{\mathsf{out}}^{\prime}\sigma\mathsf{A}_{\mathsf{in}}^{\prime} . This is further refined into a sequence of linear transformations , which can be efficiently computed by our MPC protocols for oblivious permutation and oblivious selection-multiplication . Our decomposition approach is not limited to GCNs but also general SMM by treating them as adjacency matrices. 1.1.2. New Protocols for Linear Transformations Oblivious permutation (OP) is a two-party protocol taking a private permutation \sigma and a private vector \mathsf{X} from the two parties, respectively, and generating a secret share \langle\sigma\mathsf{X}\rangle between them. Our OP protocol employs correlated randomnesses generated in an input-independent offline phase to mask \sigma and