SPG: Ensuring Structural Privacy in Secure Graph Learning

The growing adoption of Graph Neural Networks (GNNs) in Machine Learning as a Service (MLaaS) has introduced critical privacy challenges, as both graph features and structural information are exposed to untrusted environments. To mitigate these risks, recent efforts have focused on integrating secure computation into GNNs. However, existing privacy-preserving GNN frameworks often incur substantial computational and communication overhead, and remain susceptible to model-based inference attacks even when built on secure multi-party computation (MPC). While differential privacy (DP) offers an alternative defense, it typically results in significant utility degradation, underscoring a fundamental trade-off between privacy, utility, and efficiency.