Adversarial Attacks on Locally Private Graph Neural Networks

1. Problem Statement

Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data but are highly vulnerable to adversarial attacks. When GNNs are applied to sensitive domains (e.g., finance, social networks), Local Differential Privacy (LDP) is often employed to protect user data by injecting noise at the source (client-side) before aggregation.

The paper addresses a critical research gap: How do adversarial attacks behave against LDP-protected GNNs (LPGNNs)? Specifically, the authors investigate whether the noise introduced by LDP mechanisms (which protects privacy) inadvertently creates new vulnerabilities, hinders existing attacks, or can be exploited by adversaries to break privacy guarantees. The core question is whether the trade-off between privacy and utility in LPGNNs compromises the system's robustness against malicious perturbations.

2. Methodology

The authors propose a framework to evaluate LPGNNs (specifically the model proposed by Sajadmanesh and Gatica-Pere [23]) against four distinct types of adversarial attacks. The LPGNN framework utilizes:

• Multi-Bit Mechanism: For private feature collection.
• KProp Layer: For denoising via K-hop aggregation.
• Randomized Response: For label perturbation.
• DROP: For robust training with noisy labels.

The study evaluates the following attack vectors:

A. Classical Attacks (Targeting Utility/Accuracy)

1. Node Injection Attack:
   • Mechanism: The adversary injects malicious nodes connected to high-degree nodes in the graph.
   • Setting: Black-box (attacker knows graph structure but not node features/labels).
   • Goal: Disrupt the aggregation process to mislead the GNN's predictions.
2. Label-Flipping Attack:
   • Mechanism: The adversary flips the labels of compromised nodes (typically high-degree nodes) before the LDP process begins.
   • Setting: White-box (attacker knows node labels but not features).
   • Goal: Corrupt the training signal to degrade model accuracy.

B. Privacy-Breaking Attacks (Targeting Confidentiality)

3. Inference Attack:
   • Mechanism: The attacker (compromising the server) attempts to reconstruct original node features from the noisy, aggregated data sent by clients.
   • Strategy: Leveraging the assumption that neighbors have similar features, the attacker aggregates noisy values to estimate the original mean.
4. Poisoning Attack (Theoretical & Empirical):
   • Mechanism: The adversary injects a specific "poison" value ($p$) into the feature vectors of targeted nodes before the LDP encoding occurs.
   • Mathematical Basis: The attack targets the Multi-Bit Encoder algorithm. By injecting a specific poison $p = \frac{\alpha - \beta}{e^{\epsilon/m} - 1}$, the attacker manipulates the probability of the Bernoulli trial in the encoder.
   • Goal: To force the encoder to output a deterministic value (e.g., always 0 or 1) for specific original inputs, effectively bypassing the privacy guarantee and allowing the server to infer the exact original feature value.

3. Key Contributions

• First Comprehensive Study: This is the first work to systematically analyze the interplay between LDP and adversarial robustness in GNNs.
• Novel Poisoning Attack: The authors propose and mathematically prove a Data Poisoning Attack that breaks the $\epsilon$-LDP guarantee. By injecting a calculated poison, the attacker can deterministically infer private feature values, rendering the privacy mechanism ineffective for those specific nodes.
• Empirical Evaluation: Extensive experiments were conducted on four benchmark datasets (Cora, PubMed, Facebook, LastFM) using three GNN architectures (GCN, GAT, SAGE).
• Defense Analysis: The paper analyzes the impact of privacy budgets ($\epsilon$) and perturbation step sizes on attack success, providing insights for future defense mechanisms.

4. Experimental Results

A. Classical Attacks (Utility)

• Node Injection: Surprisingly, this attack was ineffective. Even with up to 50% node injection, the model accuracy did not degrade significantly.
  • Reason: The LDP noise already obscures the graph structure. Randomly injected nodes (black-box) add noise that is often indistinguishable from the LDP noise, failing to create a coherent adversarial signal.
• Label Flipping: This attack was highly successful. Accuracy degraded linearly as the percentage of flipped labels increased.
  • Reason: LDP protects the transmission of labels, but if the labels are corrupted before the LDP process (at the source), the noise injection cannot correct the fundamental error in the ground truth.

B. Privacy-Breaking Attacks (Confidentiality)

• Standard Inference Attack: Failed. The attempt to reconstruct features via mean aggregation of noisy neighbors resulted in very low cosine similarity and high mean feature difference.
  • Reason: The Multi-Bit mechanism expands the output domain significantly (e.g., from $[0,1]$ to $[-178.5, 179.5]$), making simple aggregation ineffective for reconstruction.
• Poisoning Attack: Highly Successful.
  • The attack successfully breached the LDP guarantee.
  • Success Rates:
    • Cora (Binary features): 100% inference accuracy.
    • PubMed: 99.82% success rate.
    • Facebook: 97.44% success rate.
    • LastFM: 100% success rate.
  • The attack proved that if an adversary can inject a specific pre-computed poison, the LDP mechanism's randomness can be neutralized, allowing perfect reconstruction of private data.

5. Significance and Implications

• Privacy vs. Security Paradox: The paper highlights a critical vulnerability: while LDP protects against passive inference, it is vulnerable to active poisoning if the attacker can manipulate the input before the privacy mechanism is applied.
• Limitations of Current LPGNNs: Existing LPGNN frameworks (like the one by Sajadmanesh et al.) are robust against structural attacks (node injection) but fragile against label corruption and specific poisoning strategies that exploit the mathematical properties of the encoder.
• Future Directions: The authors suggest that future defenses must focus on:
  1. Validating input data before the LDP process to prevent poisoning.
  2. Developing robust aggregation methods that are resistant to targeted poisoning.
  3. Modeling the interaction between attackers and defenders in LPGNNs as a game-theoretic problem.

In conclusion, the paper demonstrates that LDP is not a silver bullet for GNN security. While it effectively thwarts simple inference attacks, it introduces new vectors for sophisticated poisoning attacks that can completely compromise both the privacy and utility of the system.