  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.
