A Novel Unsupervised Structural Attack and Defense for Graph Classification

Graph Neural Networks (GNNs) have proven highly effective for graph classification across diverse fields such as social networks, bioinformatics, and finance, due to their capability to learn complex graph structures. However, despite their success, GNNs remain vulnerable to adversarial attacks that can significantly degrade their classification accuracy. Existing adversarial attack strategies primarily rely on label information to guide the attacks, which limits their applicability in scenarios where such information is scarce or unavailable. This paper introduces an innovative unsupervised attack method for graph classification, which operates without relying on label information, thereby enhancing its applicability in a broad range of scenarios. Specifically, our method first leverages a graph contrastive learning loss to learn high-quality graph embeddings by comparing different stochastic augmented views of the graphs. To effectively perturb the graphs, we then introduce an implicit estimator that measures the impact of various modifications on graph structures. The proposed strategy identifies and flips edges with the top-K highest scores, determined by the estimator, to maximize the degradation of the model’s performance. In addition, to defend against such attack, we propose a lightweight regularization-based defense mechanism that is specifically tailored to mitigate the structural perturbations introduced by our attack strategy. It enhances model robustness by enforcing embedding consistency and edge-level smoothness during training. We conduct experiments on six public TU graph classification datasets: NCI1, NCI109, Mutagenicity, ENZYMES, COLLAB, and DBLP_v1, to evaluate the effectiveness of our attack and defense strategies. Under an attack budget of 3, the maximum reduction in model accuracy reaches 6.67% on the Graph Convolutional Network (GCN) and 11.67% on the Graph Attention Network (GAT) across different datasets, indicating that our unsupervised method induces degradation comparable to state-of-the-art supervised attacks. Meanwhile, our defense achieves the highest accuracy recovery of 3.89% (GCN) and 5.00% (GAT), demonstrating improved robustness against structural perturbations.