# Adversarial Signed Graph Learning with Differential Privacy

arXiv: https://arxiv.org/abs/2512.00307 · HTML: https://mlsanity.com/paper/2512.00307/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 29 Nov 2025.

## Builds on (most cited first, 18 of 18)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Differentially Private Optimization on Large Model at Small Cost](https://mlsanity.com/paper/2210.00038/) (2022)
- [Signed Graph Attention Networks](https://mlsanity.com/paper/1906.10958/) (2019)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [SDGNN: Learning Node Representation for Signed Directed Networks](https://mlsanity.com/paper/2101.02390/) (2021)
- [Secure Deep Graph Generation with Link Differential Privacy](https://mlsanity.com/paper/2005.00455/) (2020)
- [Signed Bipartite Graph Neural Networks](https://mlsanity.com/paper/2108.09638/) (2021)
- [DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy](https://mlsanity.com/paper/2210.04442/) (2022)
- [Learning Stance Embeddings from Signed Social Graphs](https://mlsanity.com/paper/2201.11675/) (2022)
- [PrivDPR: Synthetic Graph Publishing with Deep PageRank under Differential Privacy](https://mlsanity.com/paper/2501.02354/) (2025)
- [AdvSGM: Differentially Private Graph Learning via Adversarial Skip-gram Model](https://mlsanity.com/paper/2503.21426/) (2025)

## Abstract (arXiv)

Signed graphs with positive and negative edges can model complex relationships in social networks. Leveraging on balance theory that deduces edge signs from multi-hop node pairs, signed graph learning can generate node embeddings that preserve both structural and sign information. However, training on sensitive signed graphs raises significant privacy concerns, as model parameters may leak private link information. Existing protection methods with differential privacy (DP) typically rely on edge or gradient perturbation for unsigned graph protection. Yet, they are not well-suited for signed graphs, mainly because edge perturbation tends to cascading errors in edge sign inference under balance theory, while gradient perturbation increases sensitivity due to node interdependence and gradient polarity change caused by sign flips, resulting in larger noise injection. In this paper, motivated by the robustness of adversarial learning to noisy interactions, we present ASGL, a privacy-preserving adversarial signed graph learning method that preserves high utility while achieving node-level DP. We first decompose signed graphs into positive and negative subgraphs based on edge signs, and then design a gradient-perturbed adversarial module to approximate the true signed connectivity distribution. In particular, the gradient perturbation helps mitigate cascading errors, while the subgraph separation facilitates sensitivity reduction. Further, we devise a constrained breadth-first search tree strategy that fuses with balance theory to identify the edge signs between generated node pairs. This strategy also enables gradient decoupling, thereby effectively lowering gradient sensitivity. Extensive experiments on real-world datasets show that ASGL achieves favorable privacy-utility trade-offs across multiple downstream tasks.