VIRGOS: Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917922730934272 |
|---|---|
| author | Zheng, Yu Zhang, Qizhi Li, Lichun Zhou, Kai Yin, Shan |
| author_facet | Zheng, Yu Zhang, Qizhi Li, Lichun Zhou, Kai Yin, Shan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VIRGOS: Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition Zheng, Yu Zhang, Qizhi Li, Lichun Zhou, Kai Yin, Shan Cryptography and Security 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. |
| title | VIRGOS: Secure Graph Convolutional Network on Vertically Split Data from Sparse Matrix Decomposition |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2502.09808 |