# Black-Box Attacks against Signed Graph Analysis via Balance Poisoning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2023.

## Built on by (most cited first, 3 of 3)

- [Adversarial Robustness of Link Sign Prediction in Signed Graphs](https://mlsanity.com/paper/2401.10590/) (2024)
- [SFR-GNN: Simple and Fast Robust GNNs against Structural Attacks](https://mlsanity.com/paper/2408.16537/) (2024)
- [Toward Robust Signed Graph Learning through Joint Input-Target Denoising](https://mlsanity.com/paper/2510.22513/) (2025)

## Abstract (arXiv)

Signed graphs are well-suited for modeling social networks as they capture both positive and negative relationships. Signed graph neural networks (SGNNs) are commonly employed to predict link signs (i.e., positive and negative) in such graphs due to their ability to handle the unique structure of signed graphs. However, real-world signed graphs are vulnerable to malicious attacks by manipulating edge relationships, and existing adversarial graph attack methods do not consider the specific structure of signed graphs. SGNNs often incorporate balance theory to effectively model the positive and negative links. Surprisingly, we find that the balance theory that they rely on can ironically be exploited as a black-box attack. In this paper, we propose a novel black-box attack called balance-attack that aims to decrease the balance degree of the signed graphs. We present an efficient heuristic algorithm to solve this NP-hard optimization problem. We conduct extensive experiments on five popular SGNN models and four real-world datasets to demonstrate the effectiveness and wide applicability of our proposed attack method. By addressing these challenges, our research contributes to a better understanding of the limitations and resilience of robust models when facing attacks on SGNNs. This work contributes to enhancing the security and reliability of signed graph analysis in social network modeling. Our PyTorch implementation of the attack is publicly available on GitHub: https://github.com/JialongZhou666/Balance-Attack.git.