Garland: Graph Neural Network-based Federated Recommendation with Malicious Security via Secret-shared Shuffle

Recommendation systems based on graph neural networks (GNNs) have emerged as a promising paradigm due to their ability to capture high-order interactions between users and items. However, in federated scenarios, this advantage is compromised, as each user can access only a first-order subgraph composed of its directly interacted items. To address this issue, most existing solutions introduce a trusted server to assist users in expanding their local subgraphs. However, the server in reality is often untrusted and may deviate from the protocol for its own improper benefit. Furthermore, these solutions primarily focus on the privacy of items while neglecting the privacy of potential relationships between users. To this end, we propose Garland, a GNN-based federated recommendation scheme with malicious security. Garland departs from existing work by ensuring both item and relationship privacy while supporting integrity checks to defend against malicious servers. Specifically, we employ a trending cryptographic primitive of secret-shared shuffle to expand subgraphs in a privacy-preserving and verifiable manner. We also design a pre-shuffle triple-salt encryption mechanism and a post-shuffle user-governed expansion mechanism to reduce communication costs and achieve secure distribution of neighbor information, respectively. Moreover, we develop a secret-shared aggregation mechanism to enable privacy-preserving and verifiable federated training. Theoretical analysis demonstrates the privacy and integrity of Garland. Extensive experimental evaluations on four datasets show that Garland outperforms state-of-the-art solutions.