Distributed Private Aggregation in Graph Neural Networks

Distributed Private Aggregation in Graph Neural Networks

Speakers: Huanhuan Jia, Southeast University & University of Massachusetts Lowell

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=turUb2Yr62g

Overview

This article delves into the groundbreaking work presented by Huanhuan Jia titled "Distributed Private Aggregation in Graph Neural Networks." The talk introduces Distributed Private Aggregation (DPA), a novel methodology for training Graph Neural Networks (GNNs) in a distributed setting while upholding rigorous privacy guarantees. Specifically, DPA is the first GNN aggregation method designed to satisfy node-level Differential Privacy (DP), a robust standard that protects all information associated with a node, including its features, edges, and labels.

The significance of this research cannot be overstated. GNNs have become indispensable tools for analyzing complex graph-structured data across sensitive domains such as social networks, financial systems, and healthcare applications. However, the inherent aggregation process of GNNs, which involves sharing and processing information from neighboring nodes, poses substantial privacy risks when conducted on untrusted servers. Existing privacy-preserving GNN methods either offer weaker privacy guarantees (e.g., edge-level DP) or are confined to centralized environments, rendering them unsuitable for distributed, multi-party scenarios. DPA directly addresses this critical gap, enabling organizations to leverage the power of GNNs on sensitive, distributed data without compromising user privacy.

Huanhuan Jia, representing a collaborative effort between Southeast University and the University of Massachusetts Lowell, demonstrates how DPA, and its implementation DPAGN (DPA Graph Neural Network), achieve an optimal balance between privacy and model utility. By strategically integrating Multi-Party Computation (MPC) protocols with several innovative modifications, the proposed framework overcomes significant challenges related to computational overhead, communication costs, and the efficient management of privacy budgets. This work offers a practical and theoretically sound solution for deploying privacy-preserving GNNs in real-world distributed environments, paving the way for more secure and ethical data analysis.

Background

▶ Watch: Introduction to GNNs and privacy challenges (0:00)

Graph Neural Networks (GNNs) have emerged as powerful machine learning models adept at extracting insights from graph-structured data. In these networks, nodes represent entities (e.g., users, transactions), and edges represent relationships between them (e.g., friendships, financial transfers). The core operation of GNNs is aggregation, where each node iteratively gathers and combines information from its direct neighbors to refine its own representation. This iterative message-passing mechanism allows GNNs to effectively capture complex structural patterns and dependencies within the graph, leading to highly expressive node embeddings.

However, the very nature of this aggregation process introduces significant privacy vulnerabilities. The node attributes (e.g., personal details, transaction amounts) and edge information (e.g., social connections, medical interactions) are often highly sensitive. When GNN training, including the aggregation steps, is performed on untrusted third-party servers, this sensitive data can be exposed, leading to serious privacy breaches. For instance, an adversary could infer private relationships or personal attributes by observing the data flow or intermediate representations during training.

To counter these threats, Differential Privacy (DP) has been adopted as a rigorous mathematical standard for quantifying and enforcing privacy. DP guarantees that the output of a computation is nearly insensitive to the presence or absence of any single individual's data, by introducing controlled noise. In the context of graph data, DP can be applied at two distinct levels:

1. Edge-level DP: Primarily focuses on protecting the privacy of individual edges in the graph. Removing or adding an edge should not significantly alter the model's output.
2. Node-level DP: Offers a much stronger privacy guarantee, as it aims to protect all information associated with a node, encompassing its features, all its incident edges, and its label. This means the model's output should be largely unaffected by the removal or addition of an entire node and all its connected data.

Existing privacy-preserving GNN methods, however, suffer from significant limitations when confronted with the challenge of achieving node-level DP in distributed settings. These methods broadly fall into two categories:

• Local DPGN Methods: These approaches apply local privacy mechanisms to specific types of node information, such as features or edges, before they are sent to a central server. While providing some level of privacy, they often fail to achieve full node-level privacy because different types of private data are accessed repeatedly throughout the GNN training process. This iterative access necessitates repeated noise injection, leading to a substantial accumulation of noise that severely degrades the performance and utility of the GNN model.
• Centralized DPGN Methods: These methods typically employ techniques like Differentially Private Stochastic Gradient Descent (DPSGD) to ensure node-level privacy. However, they are inherently designed for centralized scenarios where a single trusted entity holds all the data. Such methods are fundamentally unsuitable for distributed settings where data owners (users) wish to retain control over their sensitive information and contribute to a shared model without full disclosure to a central server.

Given this landscape, the core problem addressed by Jia's work is how to construct an effective GNN model in a distributed environment, where an untrusted server is responsible for training, while simultaneously satisfying the stringent requirements of node-level Differential Privacy. The scenario assumes a semi-honest model, meaning that all participating users, parties, and the server follow the specified protocol but may still attempt to infer private information from the data they observe. Furthermore, users and parties are assumed to communicate anonymously, a reasonable assumption in decentralized contexts. This challenging problem necessitated a novel approach to GNN aggregation that could balance strong privacy guarantees with practical utility and efficiency.

Key Findings

▶ Watch: Proposing distributed GNN aggregation with node-level DP (3:10)

The central contribution of this research is the proposal of Distributed Private Aggregation (DPA), which represents the first GNN aggregation method capable of ensuring node-level Differential Privacy (DP) in distributed settings. This is a significant breakthrough, as it directly addresses the limitations of prior work that either offered weaker privacy guarantees or were restricted to centralized environments.

Building upon DPA, the talk introduces DPAGN (DPA Graph Neural Network), an end-to-end implementation that serves as the first graph neural network satisfying both edge-level DP and node-level DP in distributed scenarios. Through extensive experimental evaluations on six public real-world datasets, DPAGN consistently demonstrates superior performance compared to existing baselines, including various local DPGN methods, their privacy-enhanced variants, and even centralized DPGN methods. This indicates that DPAGN achieves an optimal balance between preserving privacy and maintaining the utility of the GNN model, even under strict privacy budget conditions.

The ingenuity of DPA and DPAGN lies in a series of six innovative modifications to standard Multi-Party Computation (MPC) protocols and privacy budget management strategies. These modifications are specifically designed to overcome the inherent challenges of high computational and communication overhead in MPC-based GNNs, as well as the detrimental effects of privacy budget over-splitting during iterative training. Key findings include:

• Significant Efficiency Gains: By transforming heavy matrix multiplications into more efficient matrix additions and replacing sparse matrices with compact key-value structures, DPA drastically reduces computation and communication overhead, making MPC-based GNN aggregation practical.
• Robust Edge-Level DP with Dummies: The use of selective MPC and dummy key-value pairs effectively conceals the number of neighbors for each node, ensuring edge-level DP without sacrificing utility.
• Effective Privacy Budget Management: Decoupling the aggregation and training stages allows the privacy budget to be consumed only once for the full L-layer GNN aggregation, rather than iteratively across hundreds of training epochs, thereby preserving model performance.
• Enhanced Utility via Label Calibration: The novel technique of aggregating perturbed labels leverages the graph structure to calibrate noisy labels, mitigating overfitting to noise and significantly boosting model accuracy.
• Comprehensive Privacy Guarantees: DPAGN provides a strong privacy guarantee, satisfying edge-level $\epsilon$-DP and node-level $(\epsilon_E + \epsilon_H + \epsilon_Y)$-$\delta$-DP, where $\epsilon_E$, $\epsilon_H$, and $\epsilon_Y$ represent the privacy budgets allocated to edges, features, and labels, respectively.

In summary, the key findings highlight that DPA and DPAGN not only theoretically address the long-standing challenge of node-level DP in distributed GNNs but also provide a practical, efficient, and high-performing solution that outperforms existing state-of-the-art methods across diverse real-world datasets.

Technical Deep Dive

▶ Watch: Two key challenges: computation and privacy budget (4:55)

The core idea behind Distributed Private Aggregation (DPA) is to employ Multi-Party Computation (MPC) protocols to construct a GNN in distributed settings under Differential Privacy (DP) constraints. The initial conceptual process involves four main steps: each user secretly shares their private data with multiple parties; these parties perform secure computations (multiplications) and inject noise for DP; one party reconstructs the aggregated result; and finally, this result is sent to an untrusted server to train the GNN model. This iterative process, repeated over hundreds of training epochs, faces two significant challenges: substantial computation and communication overhead, and privacy budget over-splitting.

To address these challenges, the researchers propose six key modifications, forming the technical backbone of DPA and DPAGN.

Addressing Challenge 1: Computation and Communication Constraints

GNN aggregation typically involves heavy matrix multiplications, which are notoriously expensive in MPC protocols. The following modifications streamline this process:

1. Modification 1: Matrix Addition Instead of Matrix Multiplication:

In GNNs, each node's representation is updated by aggregating information from its neighbors. This aggregation can be conceptualized as each node sending its representation to its neighbors, and then summing up all received representations. By reframing the aggregation as a simple summation (matrix addition) rather than a complex matrix multiplication for feature passing, the computational burden on MPC protocols is drastically reduced. Addition operations are significantly more efficient and less resource-intensive in MPC than multiplication.

1. Modification 2: Key-Value Structure Instead of Sparse Matrices:

Standard feature passing in GNNs often involves sparse matrices, where most elements are zero, particularly in large graphs. Applying secret sharing to a full sparse matrix means sharing many zero elements, leading to unnecessary computation and communication overhead. This modification proposes replacing the traditional sparse feature passing matrix with a more compact key-value structure. In this structure, each "key" represents the index of a neighbor, and the "value" holds the corresponding node's feature representation. This approach ensures that only non-zero, meaningful values are secret-shared, significantly reducing the data volume transmitted and processed by MPC. For example, a matrix with 25 vectors might be transformed into just six key-value pairs, dramatically cutting down the overhead.

1. Modification 3: Achieving DP Defined on Edges While Dummies:

While the key-value structure is efficient, directly sharing these pairs with untrusted parties could inadvertently reveal the number of neighbors each node has. This information itself can be sensitive, posing a privacy risk. To address this, the researchers employ a selective MPC protocol and introduce dummy key-value pairs. The protocol generates a fixed number of dummy pairs for each node, padding the key-value list to a consistent length. This ensures that an observer cannot infer the true number of neighbors a node has, thereby enforcing edge-level Differential Privacy by obscuring the graph structure information inherent in neighbor counts.

Addressing Challenge 2: Privacy Budget Over-splitting

GNN training typically runs for hundreds of epochs, repeatedly accessing private edge information. If the privacy budget is consumed in each epoch, it must be split hundreds of times, leading to a rapid depletion of the budget and significant degradation of model performance. The following modifications tackle this issue:

1. Modification 4: Separating the Aggregation and Training Stages:

Instead of intertwining aggregation and training, this modification proposes a clear decoupling. The complete L-layer GNN aggregation process is performed once, with its own defined privacy guarantees, separate from the iterative model training. This means the privacy budget for aggregation is consumed only once, rather than being split and consumed across hundreds of training epochs. The aggregated, private node representations are then used for subsequent model training (e.g., via an MLP classifier), preserving a larger effective privacy budget for the overall process and significantly improving model utility.

1. Modification 5: Secret Reconstruction on the User Side:

After the parties perform secure aggregation, directly reconstructing the aggregated results on one of the parties and sending them to the server could still pose a risk. Specifically, if parties were to access intermediate node representations from multiple GNN layers, they might infer aspects of the graph structure. To prevent this, the aggregated results are returned to the respective users for secret reconstruction. This ensures that the sensitive, intermediate aggregated representations are not fully revealed to any single party, enhancing privacy.

1. Modification 6: Aggregate the Perturbed Labels:

A common challenge in DP is that injecting noise into labels can lead to overfitting to the noise, degrading model performance. This modification addresses this by leveraging the inherent graph structure. The premise is that nodes with similar structures are likely to have similar labels. Therefore, instead of directly training on noisy, perturbed labels, the system performs an additional aggregation of these perturbed labels. This process effectively calibrates the noisy labels by incorporating structural context, helping to magnify label errors and significantly enhance the overall model performance.

DPA Function and DPAGN Workflow

These modifications are integrated into the fundamental DPA (Distributed Private Aggregation) function, which is abstracted as three core sub-functions:

• Share Construction (SC) function: Users prepare their private data (features, edges, labels) and convert them into secret shares and key-value pairs, distributing them to multiple parties.
• Secret Aggregation (SA) function: Parties securely aggregate these shares, injecting controlled noise to ensure Differential Privacy, using the optimized matrix addition and key-value structures.
• Secret Reconstruction (SR) function: The aggregated, private results are returned to users for reconstruction, preventing central parties from inferring sensitive information.

Based on DPA, the researchers implement DPAGN (DPA Graph Neural Network). The full workflow consists of five main modules:

1. Initialization: Users perform data preprocessing.
2. Share Construction (SC): Users generate shared key-value pairs from their private data and transmit them to the parties.
3. Secret Aggregation (SA): Parties execute the SA module to aggregate and perturb node representations and labels.
4. Secret Reconstruction (SR): The perturbed aggregates are forwarded to the SR module, where users recover their private aggregated results.
5. Model Training: The final output, processed through multiple layers of aggregation, is passed to an MLP (Multi-Layer Perceptron) for model training.

Privacy Guarantees and Efficiency

DPAGN provides robust privacy guarantees: it satisfies edge-level $\epsilon$-DP and node-level $(\epsilon_E + \epsilon_H + \epsilon_Y)$-$\delta$-DP. Here, $\epsilon_E$, $\epsilon_H$, and $\epsilon_Y$ denote the privacy budgets specifically allocated to edges, features, and labels, respectively. The $\delta$ term accounts for a small probability of privacy failure, as is standard in approximate DP.

In terms of efficiency, DPAGN significantly reduces both communication and offline setup costs compared to an initial, naive MPC-based approach. The primary communication overhead stems from user-to-party aggregation and party-to-party reconstruction. The offline setup involves generating data for sharing. These reductions make DPAGN a more practical and deployable solution for distributed settings.

Demo / Proof of Concept

▶ Watch: Strategies to optimize privacy budget consumption (7:00)

While the talk did not feature a live software demonstration in the traditional sense, the effectiveness and practicality of DPAGN were rigorously validated through extensive experimental evaluations conducted on a variety of real-world datasets. These experiments serve as the crucial proof of concept for the proposed methodology, demonstrating its ability to achieve strong privacy guarantees while maintaining high model utility.

The evaluation involved six public, real-world datasets, whose characteristics were summarized in the presentation (Table 1). These datasets likely represented diverse graph structures and sizes, allowing for a comprehensive assessment of DPAGN's performance across different scenarios.

For comparative analysis, the researchers considered a range of baselines categorized into three groups:

1. Local DPGN methods: Existing approaches that apply local privacy mechanisms.
2. Privacy-enhanced variants: Refinements of local DPGN methods.
3. Centralized DPGN methods: State-of-the-art methods designed for centralized data processing.

A key aspect of the evaluation was to compare the trade-off between utility (model accuracy) and privacy (strength of DP guarantees). The experiments specifically compared DPAGN with these baselines across the six datasets under varying privacy budgets. The results consistently demonstrated that DPAGN achieved superior performance across the board. Crucially, DPAGN maintained high utility while simultaneously providing comprehensive protection for node features, edges, and labels – a capability unmatched by the baselines in a distributed setting.

Further ablation studies were conducted to understand the individual contributions of different privacy components and modifications. For instance, focusing on a setting where only edges were considered private, DPAGN notably outperformed state-of-the-art methods, particularly under conditions of low privacy budgets. This highlights DPAGN's robust performance even when faced with strict privacy constraints.

Finally, experiments were performed to assess DPAGN's performance when transitioning from distributed to centralized settings, comparing it directly against the four centralized baselines. Remarkably, DPAGN achieved comparable or even superior performance in these centralized scenarios. This indicates that the architectural choices and optimizations made for distributed privacy do not inherently penalize performance in centralized contexts, further underscoring the efficiency and effectiveness of the proposed method.

In essence, the experimental results serve as a compelling proof of concept, validating that DPAGN is not merely a theoretical construct but a practical and highly effective solution for achieving robust, node-level differential privacy in distributed GNN training, outperforming existing methods in both privacy and utility.

Defensive Implications

▶ Watch: Overview of DPA GNN's full workflow (9:00)

The work on Distributed Private Aggregation (DPA) and DPAGN carries profound defensive implications for organizations and researchers dealing with sensitive graph-structured data. In an era of increasing data privacy regulations (e.g., GDPR, HIPAA) and growing public concern over data breaches, the ability to train powerful GNN models without compromising individual privacy is paramount. DPAGN provides a robust, state-of-the-art defense mechanism against privacy inference attacks in distributed GNN environments.

Here's how DPAGN strengthens defensive postures:

1. Enabling Secure Distributed GNN Training: For organizations that rely on GNNs but cannot centralize sensitive data due to privacy concerns, regulatory mandates, or data ownership issues, DPAGN offers a viable pathway. It allows multiple data owners (users) to collaboratively train a GNN model on their combined data, with an untrusted server coordinating the process, without any single party or the server gaining full access to raw, sensitive information. This opens up new possibilities for collaborative AI in highly regulated sectors like finance (e.g., fraud detection across banks), healthcare (e.g., disease prediction using federated patient data), and social sciences (e.g., analyzing social networks while protecting individual connections).

1. Stronger Node-Level Privacy Guarantees: DPAGN provides node-level Differential Privacy, which is a significantly stronger guarantee than edge-level or local privacy. This means that the privacy of an entire individual's profile—including their features, all their relationships (edges), and their labels—is protected. Defenders can confidently deploy GNNs knowing that the model's output is nearly independent of any single user's complete data, making it extremely difficult for adversaries to infer sensitive attributes or connections. This level of protection is critical for compliance with stringent privacy laws.

1. Mitigation of Untrusted Server Risks: In many distributed machine learning setups, the central server is assumed to be honest-but-curious or semi-honest. DPAGN is explicitly designed for this semi-honest model, ensuring that even if the server (or any participating party) attempts to infer private information by observing intermediate computations, it cannot succeed beyond the defined DP guarantees. This reduces the attack surface and trust requirements placed on the central orchestrator, a crucial defensive measure in multi-party systems.

1. Practical Efficiency for Real-World Deployment: Previous attempts at MPC-based GNNs often faced prohibitive computational and communication costs. DPAGN's innovative modifications—such as converting matrix multiplication to addition, using key-value structures, and optimizing privacy budget consumption—address these practical hurdles. This means that the defensive benefits of DPAGN are not just theoretical but can be realistically implemented in real-world systems, making privacy-preserving GNNs a tangible option for practitioners.

1. Robustness Against Overfitting to Noise: The technique of aggregating perturbed labels to calibrate noise is a subtle yet powerful defensive mechanism. It ensures that the model, while trained with privacy-preserving noise, does not merely learn the noise itself. This maintains the utility of the GNN, meaning defenders can achieve strong privacy without severely degrading the performance of their analytical tools. A high-utility, privacy-preserving model is more likely to be adopted and provide valuable insights, making the defense both effective and practical.

In essence, DPAGN equips defenders with a powerful tool to build and deploy GNNs in privacy-sensitive domains. It transforms GNNs from a potential privacy liability into a privacy-preserving asset, enabling secure data collaboration and analysis while adhering to the highest standards of individual privacy protection. Organizations should consider integrating such distributed privacy-preserving frameworks into their data governance and machine learning pipelines, especially when dealing with personal, financial, or health-related graph data.

Key Takeaways

• Node-level Differential Privacy is Essential for GNNs: Traditional GNN aggregation exposes sensitive node features, edges, and labels. Node-level DP offers the strongest protection, safeguarding all information related to an individual entity in a graph, superior to edge-level or local privacy.
• Existing Methods Fall Short in Distributed Settings: Current privacy-preserving GNN methods either introduce excessive noise when attempting node-level DP or are confined to centralized environments, making them unsuitable for collaborative, distributed data scenarios.
• DPA is a Novel Solution for Distributed, Node-Level DP: Distributed Private Aggregation (DPA) is the first method designed for GNN aggregation that successfully achieves node-level Differential Privacy in distributed settings, addressing a critical gap in the field.
• Efficiency Gains through MPC Optimizations: DPA leverages Multi-Party Computation (MPC) protocols but significantly optimizes them by replacing computationally heavy matrix multiplications with efficient additions, using compact key-value structures for sparse data, and employing dummy padding with selective MPC for edge-level DP.
• Effective Privacy Budget Management: The framework tackles privacy budget over-splitting by decoupling the L-layer GNN aggregation from iterative training and performing secret reconstruction on the user side. It also enhances utility by aggregating perturbed labels to calibrate noise, preventing overfitting.
• DPAGN Achieves Superior Utility and Strong Privacy: The implementation, DPAGN, demonstrates consistent superior performance on real-world datasets compared to existing baselines, achieving an optimal balance between model utility and robust privacy guarantees (edge-level $\epsilon$-DP and node-level $(\epsilon_E + \epsilon_H + \epsilon_Y)$-$\delta$-DP).

About the Speaker(s)

The presenter for this talk was Huanhuan Jia. This project represents a collaborative research effort between Southeast University and the University of Massachusetts Lowell. Huanhuan Jia's work, as demonstrated in this presentation, focuses on the critical area of privacy-preserving machine learning, specifically addressing the challenges of integrating robust privacy guarantees, such as Differential Privacy, into advanced models like Graph Neural Networks within distributed computing environments. Their research aims to develop practical and efficient solutions that enable the secure analysis of sensitive data while maintaining high model performance.