OblivSage: Oblivious Graph Sampling for Privacy-Preserving GNN

Graph Neural Networks (GNNs) are highly effective for analysing interconnected data, yet collaboratively training them across distributed silos introduces severe privacy risks. While Multi-Party Computation (MPC) can secure this process, existing frameworks enforce full-graph aggregation. This triggers a ‘neighbour explosion’, generating prohibitive computational and communication bottlenecks that render secure training infeasible for large-scale graphs. To address this, we propose OblivSage, a novel framework leveraging Function Secret Sharing (FSS) to enable dynamic, oblivious subgraph sampling. OblivSage allows distributed parties to agree on and execute secure sampling, choosing between minimal shared-degree ( \(d_{min}\) ) and k-hop aggregation, without leaking the sampling access patterns or the underlying graph topology to the computing servers. Evaluations on standard benchmarks demonstrate that OblivSage achieves up to a \(14.3\times \) speedup and a \(1024\times \) reduction in communication overhead compared to state-of-the-art secure baselines, while incurring negligible loss in model accuracy.