Adversarial analysis of signed graphs with balance theory

Abstract

Signed graphs have emerged as effective models for capturing positive and negative relationships in social networks. To analyze such graphs, signed graph neural networks (SGNNs) have been widely employed, leveraging the unique structural characteristics of signed graphs. However, it is surprising to discover that the balance theory, which is commonly integrated into SGNNs to effectively model positive and negative links, can unintentionally serve as a vulnerability, susceptible to exploitation as a black-box attack. In this study, we introduce a novel black-box attack termed balance-attack, specifically designed to diminish the balance degree of signed graphs. To address the associated NP-hard optimization problem, we propose an efficient heuristic algorithm. Furthermore, combating various adversarial attacks on signed graphs has become an urgent concern. We observe that these attacks often result in a reduction of the balance degree in signed graphs. Similar to the restoration of unsigned graphs through structural learning, we propose balance learning techniques to improve the balance degree of compromised graphs. However, we encounter the challenge of "Irreversibility of Balance-related Information", wherein the restored edges may not align with the original targets of the attacks, leading to suboptimal defense effectiveness. To overcome this challenge, we present a robust SGNN framework called Balance Augmented-Signed Graph Contrastive Learning (BA-SGCL), which integrates Graph Contrastive Learning principles with balance augmentation techniques. This approach facilitates the attainment of a high balance degree in the latent space, indirectly addressing the challenge of "Irreversibility of Balance-related Information". We extensively evaluate our proposed balance-attack and robust BA-SGCL on multiple popular SGNN models and real-world datasets. The experimental results validate the effectiveness of balance-attack and the resilience of BA-SGCL. This research significantly contributes to enhancing the security and reliability of signed graph analysis within the context of social network modeling.