Exploiting Self-Refining Normal Graph Structures for Robust Defense against Unsupervised Adversarial Attacks

1 Introduction

Graphs are a ubiquitous form of data structure capable of representing a diverse array of entities and their complex relationships [Zhang et al., 2020]. Graphs can mirror various real-world networks, including protein networks [Vlaic et al., 2018], traffic networks [Huang et al., 2022], social networks [Chang et al., 2023], and Textual Networks [Wang et al., 2025]. Graph Neural Networks (GNNs) [Hamilton et al., 2017; Kipf and Welling, 2017] have emerged as a powerful tool for graph representation, attracting significant attention due to their remarkable performance in tasks such as node classification [Yan et al., 2025].

∗Corresponding author

While supervised learning remains prevalent in practical applications, labeling large volumes of graph data can be costly and prone to errors. Consequently, there have been notable advancements in unsupervised algorithms over the years [Veliˇckovi´c et al., 2019; Zhu et al., 2021]. These methods focus on learning an encoder from unlabeled graph data, which can be used to generate representations for downstream tasks.

Despite their advantages in many tasks, unsupervised learning models are generally more vulnerable to adversarial attacks than supervised models due to the absence of labeled data. Supervised models use labeled data to correct predictions and learn more robust representations, whereas unsupervised models lack this mechanism, making them more susceptible to structural perturbations [Xu et al., 2022; Jin et al., 2023]. Adversarial attacks introduce small perturbations to the graph structure, which can significantly alter prediction outcomes [Madry et al., 2018; Z¨ugner et al., 2019; Sun et al., 2022; Zhu et al., 2024; He et al., 2025].

Existing research primarily focuses on defending against evasion attacks by training robust representations to withstand adversarial attacks during the inference phase [Zhuang and Al Hasan, 2022; Feng et al., 2024b]. However, compared to evasion attacks, poisoning attacks are more destructive because they directly alter the model during training, while evasion attacks only degrade performance by modifying the structure around target nodes [Li et al., 2023]. Research on defenses against poisoning attacks remains limited. Common defense strategies often rely on the homophily assumption, which seeks to remove edges between nodes with dissimilar representations [Zhang and Zitnik, 2020; Zhang et al., 2019]. However, due to the presence of perturbed edges, the endpoints of these edges are influenced by the perturbations, causing their representations to become more similar and, consequently, harder to detect. In other words, the large number of normal edges causes the effect of a few perturbed edges to be diluted, resulting in similar similarity distributions for both perturbed and original edges. To illustrate, we design a simple process for detecting adversarial perturbations based on similarity as shown in Figure 1. The adversary aims to maximize disruption by connecting distant nodes, v1 and v2, with a perturbed edge. However, the perturbation causes their representations to become more similar, making it difficult to distinguish between them. To verify this, we examine the similarity distribution of perturbed edges. As shown in Figure 2(a), the similarity distributions of normal and perturbed edges are highly similar, which makes it challenging for similarity-based detection methods to effectively distinguish the perturbed edges.

Currently, several self-supervised methods based on contrastive learning have been developed to detect anomalous structures in graphs, where anomalies are defined as edge connection patterns or the existence of edges that significantly deviate from typical graph structures, such as edges connecting distant nodes or altering the inherent properties of nodes [Peng et al., 2018; Liu et al., 2021; Duan et al., 2023]. Unlike similarity-based detection methods, which are influenced by information propagation, these methods learn anomaly patterns by capturing the normal patterns between a large number of nodes and their neighbors (e.g., the homophily assumption), without being affected by information propagation. Can anomaly detection methods be leveraged to better identify perturbed edges? Figure 2(b) shows the distribution of anomaly edge scores on the Cora dataset computed by CoLA. We find that most normal edges can be reliably trusted; however, some normal edges with higher anomaly scores overlap with perturbed edges, making it difficult to distinguish between them. This raises the following challenge:

How to effectively utilize the trusted normal edges to distinguish those within the overlapping region and accurately identify perturbed edges.

To address this challenge, we first apply anomaly detection techniques to generate a preliminary graph composed of "true" (trusted) edges. In the next step, we employ an information-theoretic measure called Graph Pollution Degree (GPD) to quantitatively assess the purity of the predicted graph. This measure allows us to identify candidate edges that remain perturbed, pinpointing clean subgraphs that are suitable for model training. Through this two-stage process, we iteratively refine the graph and fine-tune the graph representation learning model, ultimately achieving effective representations. In summary, the main contributions of this work are as follows:

• We propose a robust unsupervised graph representation learning framework that leverages a clean graph to iteratively refine the graph structure for effective representation learning.

(a) Representation similarity

• We propose a novel graph refinement process that leverages anomaly detection to identify perturbed edges and utilizes our designed information-theoretic measure, Graph Pollution Degree (GPD), to infer the clean graph by focusing on edges most likely to be "true".
• Extensive experiments on four real-world datasets demonstrate that our model defends against various types of attacks and outperform nine state-of-the-art defense models.

2 Preliminaries

2.1 Graph Representation Learning

We are provided with an attribute graph G = {V,A,X}, where V = {v1, v2, . . . , vn} represents the set of nodes in the graph, A ∈ RN×N denotes the adjacency matrix of the graph G, and X ∈ RN×d is the node feature matrix, where each row xi corresponds to the d-dimensional feature vector of node vi. In the adjacency matrix A, the element Ai,j ∈ {0, 1} indicates whether there is an edge between nodes vi and vj: if an edge exists, the value is 1; otherwise, it is 0. The objective of the graph representation learning task is to train an encoder e : Rd → Rd′ and obtain high-level representations Hi ∈ Rd′ for every node vi.

A lot of studies [Veliˇckovi´c et al., 2019; Sun et al., 2019; Qiu et al., 2020] train a graph encoder to maximize the mutual information between the node representations and the global graph representation in the graph G. Since the marginal distribution is not estimated, optimizing mutual information directly can be challenging, these methods transform the problem into a standard binary cross-entropy loss between positive and negative examples:

where N and M respectively represent the number of positive and negative samples, hi and hj respectively denote the representations of positive G and negative ˜G samples, encoded by the encoder e, s represents graph-level summary vectors, and D(·) represents a discriminator composed of a bilinear scoring function:

where W represents the scoring matrix that needs to be learned in the discriminator, and σ(·) represents the logistic sigmoid function.

2.2 Adversarial Attacks and Defense

Adversarial attacks [Madry et al., 2018; Bojchevski and G¨unnemann, 2019] on graphs may involve alterations to both the graph structure and node attributes, potentially leading to failures in tasks such as node classification, graph classification, and more. Essentially, adversarial attacks can be mathematically expressed as a bi-level attack form:

where φ(G) denotes the space of perturbation, fθ is the surrogate model, and l is the loss associated with the surrogate model, such as cross-entropy or contrastive loss.

Depending on whether the attackers generate adversarial samples during the training or inference phase, attacks can be categorized into poisoning attacks and evasion attacks. In response to poisoning attacks, a substantial body of research has adopted attack detection methods, aiming to proactively identify and eliminate malicious nodes and edges in graph data [Li et al., 2022; Wu et al., 2019; Ding et al., 2019].

Graph-based anomaly detection aims to identify abnormal patterns that deviate from the majority of the data, particularly anomalous structures. Adversarial attacks can be considered a distinct and dangerous scenario of anomalies [Abusnaina et al., 2021; Ma et al., 2021; Wang et al., 2023]. In this paper, we propose a graph refinement method based on the CoLA [Liu et al., 2021] framework, recognized as the state-of-theart in contrastive learning for unsupervised anomaly detection. Our approach predicts the anomaly score of a node by calculating the contrastive instance pair labels between the node vi and its corresponding sub-graph and thus obtains a preliminarily filtered rough graph.

3 Methods

In this section, we introduce a robust representation learning framework composed of two main components: normality analysis and robust representation learning. As illustrated in Figure 3, we initially employ graph anomaly detection methods to ascertain the anomaly scores of each edge, identifying potential adversarial structures. Subsequently, we implement a progressive refinement process that iteratively updates the graph and fine-tunes the model, thereby transforming corrupted representations into effective ones and enabling the learning of robust graph representations.

3.1 Anomaly Studying

We present methods for obtaining a rough graph that contains a significantly lower proportion of perturbed edges. This process involves two main steps: computing anomaly scores for nodes and constructing the rough graph based on these scores.

Anomaly Score Learning

Adversarial attacks often connect two unrelated and distant nodes, resulting in inconsistency between the attributes of a node and its neighbors, which causes these nodes to appear anomalous. Therefore, we compute an anomaly score for each node to identify these anomalies caused by adversarial attacks. Inspired by [Liu et al., 2021], we model the anomaly patterns using contrastive self-supervised learning. Specifically, in each epoch, we randomly select a target node i, and adopt the random walk with restart (RWR) method to sample positive examples associated with i, represented as the positive subgraph G+i . First, we compute the embeddings Hi of the nodes in the subgraph G+i . To achieve this, we aggregate information from each node's local neighborhood to capture both structural and attribute information. For this purpose, we use a Graph Convolutional Network (GCN), as it effectively learns representations by combining features from neighboring nodes. The embeddings H(l) i at layer l are computed as:

where Di represents the degree of node i, and Ai represents the adjacency matrix of the subgraph to which node i belongs. W denotes the learnable parameters, and φ(·) is the ReLU activation function. Then, we apply an average pooling function as the readout function to obtain the overall embedding hgi of the subgraph Gi.

where k represents the k-th node inG+i , andK represents the number of nodes in G+i .

Next, we calculate the representation of node i by mapping it into the same embedding space as the subgraph embedding hgi . Specifically, we use a deep neural network (DNN) to compute the embedding of node i as:

where h(l-1) i is the representation of node i at layaer l-1, and W represents the corresponding learnable parameters. Based on the embeddings of node i and the subgraphG+i , we predict the anomaly score of node i. We adopt a bilinear scoring function defined as:

where W is a learnable weight matrix, and σ(·) is the sigmoid activation function. For positive instance pairs, the score s+i should be close to 1. Learning exclusively from positive instance pairs can result in model collapse [Zhuang et al., 2024]. To address this issue, we introduce the score s-i for negative instance pairs. The negative instance pairs G-i are obtained by randomly selecting positive subgraphs from other nodes. Consequently, s-i should be close to 0 and is defined as:

where j represents any random node other than node i. During the testing phase, the anomaly score of node i is defined by the difference between the scores from the negative and positive instance pairs:

A higher value of si suggests that node i is more likely to be anomalous.

Obtaining Rough Graph

We first develop a method to exclude most of the perturbed edges from the graph. Previous research shows that adversarial attacks often connect distantly located nodes to disrupt the graph's homogeneity, typically resulting in high anomaly scores for the two connected endpoints [Tang et al., 2020; Jin et al., 2023; Li et al., 2023]. Therefore, if the anomaly scores of the endpoints of an edge are high, it suggests a higher probability that the edge has been perturbed. In practice, we rely on the anomaly scores of the endpoints to derive the edge anomaly matrix E∗ i,j , defined as:

We sort the edges according to their anomaly scores in descending order and remove the top-k most anomalous edges to generate the rough graph G. Although this edge removal strategy does not entirely eliminate all perturbed edges, it significantly mitigates the influence of most "false" edges, thereby increasing the proportion of original edges in G.

In addition, averaging the anomaly scores of the endpoints is a straightforward way to handle results across multiple rounds. Theoretically, more statistical methods could be employed, such as using the minimum or maximum values. However, since perturbed edges tend to exhibit different distribution characteristics, we believe that averaging remains an effective solution.

3.2 Effective Representation Learning

Although we obtain a cleaner graph in the previous section, this comes at the cost of discarding many "true" edges that are mistakenly identified as "false", thereby reducing the richness of the graph's structural information. To address this issue, we propose a method in this section to progressively expand the rough graph to include more "true" edges while refining the corrupted representations into effective ones. This method consists of two key components: the establishment of the Graph Pollution Degree (GPD) and the overall framework for obtaining effective representations.

Quantifying Graph Pollution Degree

We propose a method to ascertain whether the edges in a predicted graph have been perturbed by measuring changes in mutual information. Intuitively, the aimof adversarial attacks on graphs is to damage the representations, thereby reducing the performance of downstream tasks. This indicates that representations learned from clean graphs do not adequately reflect graphs containing adversarial edges. Therefore, we propose the Graph Pollution Degree (GPD) as a measure to quantify the level of pollution in the predicted graph.

where G denotes the clean graph and G′ denotes the predicted graph, fθ is an encoder trained on the clean graph G, and I (G, fθ (G)) represents the mutual information between the G and its representation fθ (G). The GPD quantifies the difference in mutual information between the clean graph and the predicted graph, reflecting how much the predicted graph's structure deviates from the clean graph in terms of its learned representations. A lower value of GPD(θ) indicates that the predicted graph under examination contains a higher level of pollution due to perturbed edges.

Depending on the value of GPD, problem (10) can guide two simple sub-problems:

{ G′ contains adversarial edges, if GPD > α G′ can be trusted, otherwise

.

A highly expressive encoder, which undergoes continuous fine-tuning based on clean graphs, fails to capture the interdependencies between polluted graphs and their representations, resulting in GPD > α.

Although some studies [Xu et al., 2022; Jin et al., 2023; Zhu et al., 2020] propose the concept of Representation Vulnerability (RV) to quantify the impact of adversarial attacks on representations and develop corresponding defense strategies, their primary focus is on learning robust representations from clean graphs. In contrast, the goal of GPD is to quantify the level of pollution in the predicted graph and refine the polluted graph into a cleaner one that is more suitable for learning effective representations.

Algorithm 1 Overall Procedure of Algorithm

Input: Attacked graph G∗ = (A∗ ,X), rough graph G, learning rate δ, hyperparameters α Output: Refined model θ, effective representation fθ (G) 1: Calculate model θ according Eq. (1) 2: While not early-stop do 3: Randomly select E′ , and combine it with G to form G′ = (A′ ,X), where E′ ∈ G∗&E′ /∈ G 4: If I (G, fθ (G)) - I (G′ , fθ (G′ )) < α 5: // updating clean graph 6: Let G = G′ 7: // fine-tuning the model 8: θ ← θ - δ∇θI(G; fθ(G)) 9: Else 10: // fine-tuning the model 11: θ ← θ - δ∇θI(G; fθ(G)) 12: End while 13: Calculate effective representation fθ (G) 14: Return θ, fθ (G)

Graph Representation Learning Framework

The overall graph representation learning framework is outlined in Algorithm 1. We begin by randomly initializing the parameters θ for the unsupervised graph contrastive learning method, which employs the DGI (Deep Graph Infomax) approach defined in Eq. (1). Next, we randomly select edges that belong to the polluted graph but not to the clean graph and sequentially add them to the clean graph to generate the predicted graph G′ . We then calculate the difference in mutual information between the clean graph G and its representation fθ(G), and between the predicted graph G′ and its representation fθ(G′ ), denoted as GPD(θ) (step 4). If GPD(θ) is less than the threshold α, the predicted graph G′ is deemed trustworthy and used to fine-tune the model via Eq. (1). Conversely, if GPD(θ) exceeds α, it indicates that G′ contains a significant number of perturbed edges. In this case, we use the cleaner graph G to fine-tune the model, repeating the process until convergence is achieved. The algorithm ultimately returns the refined model and robust representation fθ(G), which can then be used for downstream tasks such as node classification, selecting only the graph G′ with the smallest GPD as the refined graph for each round.

4 Experiments

In this section, we demonstrate that our model can train robust, high-quality representations on graphs under adversarial attacks. We focus on addressing the following research questions. Q1: Can our model learn robust and efficient representations under PGD attacks with varying perturbation rates? Q2: Can our model effectively defend against different types of graph adversarial attacks? Q3: How sensitive is the model to parameter variations? Q4: What is the impact of each component on the overall model performance?

4.1 Experimental Settings

Datasets

We conduct experiments on four widely used benchmark datasets: Cora, Citeseer, Pubmed [Kipf and Welling, 2017; Sen et al., 2008], and Polblogs [Adamic and Glance, 2005]. The first three are citation networks, where nodes represent documents and edges denote citation links between them. Polblogs is a political blog network, in which nodes are blogs and edges indicate hyperlinks. Since Polblogs lacks node features, we use an identity matrix as its attribute matrix following [Xu et al., 2022]. Detailed dataset statistics are provided in Table 1.

Baselines

We compare our methods with nine state-of-the-art defense Graph Neural Networks (GNNs). The baselines are categorized into two main groups: embedding-based methods, including DGI [Veliˇckovi´c et al., 2019], Jaccard [Wu et al., 2019], SVD [Entezari et al., 2020], STABLE [Li et al., 2022], and STRG [Li et al., 2023]; and anomaly detectionbased methods, such as Dominant [Ding et al., 2019], CoLA [Liu et al., 2021], GRADATE [Duan et al., 2023], and GFCN [Mesgaran and Hamza, 2024]. Additionally, we implement three non-targeted structural adversarial attack methods: PGD [Madry et al., 2018], MetaAttack [Z¨ugner and G¨unnemann, 2019], and Random.

Implementation Details

For each dataset, we randomly divided 10% of the nodes for training and 80% for testing, as in [Feng et al., 2024a]. In our work, we set the hyperparameters α = 5e - 4. Regarding the attack setup, the polluted graph is generated using the aforementioned three structural perturbation methods. We set the perturbation ratio δ, which is tuned from {0.05, 0.1, 0.2, 0.3, 0.4}, based on the default parameters. For the parameter design of the baselines, besides using the default parameters, we set a threshold for JACCARD, and STABLE from {0.2, 0.3, 0.4, 0.5, 0.6} and select the best-performing one. For Dominant, CoLA, GRADATE, and GFCN, we delete edges based on node or structural anomaly rankings, ensuring that the number of removed edges corresponds to the number of edges targeted in the attack.

Table 1: Statistics of the experimental data.

4.2 Performances against PGDAttack (Q1)

Table 2 presents the node classification accuracy of our proposed model compared to nine baselines under PGD adversarial attacks. Our method consistently outperforms all baselines across different perturbation ratios, achieving ACC gains of 77.3%, 69.0%, 66.5%, and 87.4% on Cora, Citeseer, PubMed, and Polblogs at a 5% perturbation rate. Compared to similarity-based approaches, our model's advantage lies in its ability to identify more accurate structures from the outset. In contrast to anomaly detection-based methods, we leverage trusted structures to effectively identify the correct structures within untrusted regions. Additionally, as perturbation increases, our model's performance decreases more slowly across all datasets, similar to the STABLE baseline. This resilience is attributed to our approach of initially selecting a rough graph and fine-tuning the model based on refined graph structures, reducing sensitivity to adversarial perturbations.

4.3 Performance against Different Attacks (Q2)

In this section, we evaluate the performance of our model under MetaAttack and random perturbations on the Cora and Citeseer datasets, as shown in Figure 4. Our experiments reveal that adversarial attacks primarily aim to connect distant nodes, resulting in both structural anomalies and mismatches between the polluted graph and its learned representations. By leveraging mutual information, our model effectively mitigates these issues, consistently outperforming baseline methods across different perturbation techniques. Moreover, as the perturbation rate increases, our model's performance declines more gradually than other methods. This resilience can be attributed to the reduced number of perturbed edges, which allows the accurate structures to provide more reliable information and making it easier to identify and exclude false edges.

4.4 Sensitivity Analysis (Q3)

To verify the effectiveness of our framework, we investigate two parameters under a 5% PGD attack on different datasets: the GPD threshold α, the proportion of edges removed in advance, and the number of edge verifications q. First, we vary α to observe changes in classification accuracy. As shown in Figure 5(a), extremely small α values lead to premature termination, while excessively large values can cause severely polluted graphs to be misclassified as clean. Hence, we set α to 5 × 10-4 for a robust balance. Second, increasing the proportion of edges removed in advance generally improves model robustness, indicating that screening out more potentially perturbed edges helps stabilize subsequent refinements. Finally, we examine the effect of q. As shown in Figure 5(b), a higher q yields better refinement, as too few queries risk incomplete structural information. We find that q = 10 sufficiently captures most accurate structures for downstream tasks. Overall, our model remains relatively stable within reasonable parameter ranges, confirming that thresholding polluted edges and adjusting verification times effectively enhance both robustness and representation quality.

4.5 Ablation Study (Q4)

In this section, we provide a detailed analysis of our method's performance under various conditions on the Cora dataset. Specifically, we compare three variants: Ours-similarity (Ours-s), which first learns the representations of the attacked graph using DGI and retains edges with higher similarity; Ours-dominant (Ours-d), which uses autoencoders to compute the anomaly score and selects edges with lower scores; and Ours-none (Ours-n), which randomly selects edges from the polluted graph. Figure 6 shows the results of these variants. We make the following observations: using these methods to obtain the rough graph is less effective than employing the CoLA method. This is likely because CoLA's anomaly detection approach identifies anomaly patterns rather than relying on structural information, making it less influenced by the presence of anomalous edges.

5 RelatedWorks

Numerous studies have demonstrated that graph neural networks (GNNs) are susceptible to attacks, particularly through adversarial perturbations. Nettack [Z¨ugner et al., 2019] is a pioneering study in the domain of graph adversarial attacks, pioneering targeted attacks through subtle changes to the structure and node attributes of graphs. Building on this, Mettack [Z¨ugner and G¨unnemann, 2019] employs a metalearning approach to tackle the bi-level optimization problem in adversarial attacks. This method of perturbation persistently diminishes the representational capacity of graph convolutional networks, enabling maximally effective untargeted attacks on graph neural network learning. PGD [Madry et al., 2018] method uses a projected gradient descent topology attack for dual optimization, effectively applying convex relaxation optimization to enable gradient-based adversarial attacks on discrete graph data. These graph attack algorithms can be directly applied during the graph training phase, leading to extensive research on defending against adversarial perturbations. For defense against different attacks, [Wu et al., 2019] propose using the Jaccard similarity of node representations to remove adversarial edges. [Entezari et al., 2020] propose defending against adversarial attacks by using Singular Value Decomposition (SVD) for low-rank approximation, which retains the high-rank components of the graph and effectively reduces the impact of attacks. [Li et al., 2022] propose removing edges between dissimilar nodes and additionally selecting top-k edges to reduce the impact of residual perturbations. STRG [Li et al., 2023] leverages the local structures of test nodes and pseudo-labels to train a GCN, reducing the distribution shift between the training and test sets, thereby enhancing robustness. Unlike these studies, we recognize the potential impact of perturbed edges on attack detection models. Consequently, we design a method to refine contaminated graphs using clean graphs, enabling more detailed refinement of the contaminated graphs to better defend against adversarial attacks.

6 Conclusion

In this paper, we propose a novel robust representation learning method for unsupervised learning through graph refining. Our framework iteratively refines graphs using cleaner structures, guided by the Graph Pollution Degree (GPD) metric to quantify graph pollution and direct the refinement process. By employing contrastive learning and anomaly detection to identify and exclude perturbed edges, we progressively improve the quality of the learned representations. Extensive experiments demonstrate our model's effectiveness in learning representation, leading to significant improvements in node classification. One limitation of our method is its reliance on the homophily assumption, which may reduce effectiveness on graphs with low homophily. For future work, we aim to adapt our defense technique to effectively handle additional attack types, specifically injection and backdoor attacks, and assess our framework on more complex and varied graph data, such as heterogeneous and multimodal graphs.

Acknowledgments

This work was partly supported by the National Natural Science Foundation of China (Nos. 62272340, 92370111, 62422210, 62276187, 62302333, U22B2036, 62261136549), the Open Research Fund from Guangdong Laboratory of Artificial Intelligence and Digital Economy (SZ) (No. GML-KF-24-16), the Hebei Natural Science Foundation (F2024202047), the Technological Innovation Team of Shaanxi Province (No. 2025RS-CXTD-009), the International Cooperation Project of Shaanxi Province (No. 2025GH-YBXM-017) and the Tencent Foundation and XPLORER PRIZE.