Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective

1 Introduction

Graph Neural Networks (GNNs), as a representative approach for processing graph-structured data, have shown promising performance in tasks involving relational information [Jiang et al., 2021; Xing et al., 2024]. GNNs recursively learn feature and topological information through a messagepassing paradigm. Nevertheless, this paradigm also leads to their vulnerability [Dai et al., 2018; Z¨ugner et al., 2018], and many attack methods have been proposed to explore their robustness. Previous studies mainly focus on Graph Modification Attacks (GMA) [Z¨ugner and G¨unnemann, 2019; Z¨ugner et al., 2018], which reduce the performance of GNNs by modifying node features and edge connections in the original graph. However, GMA is difficult to implement in practice because attackers often lack the privileges to alter existing data in a graph. To make graph attacks more practical, researchers have proposed Graph Injection Attacks (GIA) [Ju et al., 2023; Chen et al., 2022; Tao et al., 2021; Zou et al., 2021; Wang et al., 2020; Sun et al., 2020], which reduce the performance of GNNs by injecting malicious nodes.

∗Corresponding author

The settings of GIA can be categorized into white-box and black-box approaches. White-box methods require access to the parameters and architecture of the target model, which is impractical in real-world scenarios. Therefore, we focus on GIA in the black-box setting. Although numerous effective GIA studies have emerged [Chen et al., 2022; Zou et al., 2021; Wang et al., 2020; Sun et al., 2020], this type of attack often disrupts the homophily of the original graph [Li et al., 2023; Chen et al., 2022]. Homophily indicates that neighboring nodes tend to have similar node features or labels, which is a key characteristic of homophilous graphs. Thus, GIA can be effectively defended against by homophily defenders using edge pruning [Zhang and Zitnik, 2020]. To address this problem, the Harmonious Adversarial Objective (HAO) [Chen et al., 2022] enforces GIA to preserve the homophily of the original graph. Nonetheless, according to the no-free-lunch principle, we observe that HAO sacrifices attack performance against undefended models to enhance performance against homophily defenders. Moreover, existing GIA methods mainly rely on surrogate models to generate perturbed graphs. However, different architectures and prior biases pose significant challenges to the generalization ability of the attack method when applied to a new target model. Although recent works [Ju et al., 2023; Wang et al., 2021] attempt to mitigate the dependency on surrogate models by generating perturbed graphs without gradients and using query-based attacks, these methods remain susceptible to homophily-based defenses. These critical flaws raise a significant concern: How can we design a surrogatefree attack method that minimizes damage to attack performance against undefended models while remaining undetectable by homophily defenders?

To address the aforementioned challenges, we propose a

Query-based and Unnoticeable Graph Injection Attack (QUGIA), which is entirely independent of surrogate models. Following existing GIA methods, our approach consists of two main components: feature generation and edge generation. The feature generation component generates the features of the injected nodes, while the edge generation component determines the edges that connect the injected nodes to the original graph nodes. For the feature generation component, we adopt a Bayesian framework to generate the features of the injected nodes, allowing the model to learn from historical Bayesian inference information. We initialize the features of the injected nodes based on those of the victim nodes. Subsequently, we optimize the features of the injected nodes within a fixed perturbation range, K, which implicitly preserves the homophily of the original graph. For the edge generation component, previous work generally generates edges from the perspective of node degree, as nodes with lower degrees are less robust [Li et al., 2023; Zou et al., 2021]. Considering the message-passing paradigm and the homogeneity of the graph, unlike conventional methods, we generate edges from the perspective of the neighbors of the victim nodes. QUGIA avoids the notorious bi-level optimization problem, which involves alternating optimization between edge generation and node generation. Moreover, it implicitly preserves the homogeneity of the graph, making the attack less noticeable. QUGIA provides a novel perspective for the design of GIA attacks. Our contributions are summarized as follows:

• We investigate query-based GIA that are unnoticeable under defenses while effective against undefended models, which were rarely discussed in previous studies.
• We propose a query-based attack framework that is independent of specific model assumptions. Our approach introduces a Bayesian optimization-based method for updating injected node features and an injection strategy based on the victim node's neighbors.
• Extensive experiments on six real-world datasets and six GNN models demonstrate that our attack method outperforms state-of-the-art attackers.

2 Preliminary

2.1 Graph Neural Networks

Consider a graph G = (V, E), where V = {v1, . . . , vn} represents the set of nodes, and E = {e1, . . . , em} represents the set of edges. Let X denote the node feature matrix, with X ∈ Rn×d , where n is the number of nodes and d is the dimensionality of the node features. The feature vector of a node u is denoted by Xu. The adjacency matrix is represented as A ∈ {0, 1}n×n , where Aij = 1 if there exists an edge between nodes i and j, and Aij = 0 otherwise. The set of neighbors of a node v is denoted by N(v). In this paper, we focus on the semi-supervised node classification task. The nodes used during training are denoted as Vtrain. For each node u in Vtrain, there is a corresponding label yu ∈ YL, where YL ⊆ Y and Y = {1, 2, . . . ,C}. YL represents the set of labeled nodes. During the testing phase, the trained GNN

model predicts the labels of the nodes in Vtest = V \ Vtrain based on the subgraph Gtest.

2.2 Graph Adversarial Attacks

During the training phase, the parameters of the GNN model are learned using Gtrain. The objective of the adversarial attack is to construct a perturbed graph G′ that reduces the classification accuracy of the trained GNN model on Vtest during the testing phase. The general formulation of graph adversarial attacks can be expressed as follows:

where θ represents the trained parameters of the GNN model, Latk denotes the loss function for the attack (e.g., -Ltrain), and ∆ constrains the perturbation strength allowed for the attacker.

For GIA, the perturbed adjacency matrix and feature matrix can be expressed as follows:

where AI denotes the adjacency matrix between the original nodes and the injected nodes, OI represents the adjacency matrix among the injected nodes, and VI corresponds to the injected nodes. The constraints for GIA attacks can be summarized as:

where ∆ represents the maximum number of injected nodes, du refers to the degree of the injected node u, and Xu,i denotes the feature value of the injected node u in the i-th dimension. The terms min(X) and max(X) represent the minimum and maximum values of all node features in the original graph after normalization. It is worth noting that discrete features are not normalized in this process.

Following previous works [Chen et al., 2022; Zheng et al., 2021], this paper primarily focuses on an evasion attack scenario where the attacker is not allowed to modify the model's parameters. The attack operates in an inductive learning setting, meaning that test nodes remain entirely unseen during training. Furthermore, the attack is characterized as nontargeted and black-box. Specifically, the attacker aims to reduce the model's accuracy by causing as many misclassifications as possible across the entire test set within a given attack budget, without targeting specific nodes or classes, and without any knowledge of the model's architecture or parameters.

3 ProposedMethod

In this chapter, we provide a detailed introduction to our proposed attack method, QUGIA. Figure 1 illustrates the overall framework of QUGIA, which consists of two core components: node generation and edge generation. Node generation optimizes the features of injected nodes using Bayesian optimization, while edge generation determines the connections of injected nodes based on the neighbors of the victim node.

In each injection step, QUGIA first performs edge generation to establish the connections for the injected nodes, followed by the optimization of their features. As feature optimization is the primary aspect of the injection process, we will first discuss node generation, followed by edge generation.

3.1 Edge Generation

Generating malicious edges is a discrete problem with an extremely large search space due to the numerous possible connections in the graph. Alternating between feature optimization and edge selection leads to the notorious bi-level optimization problem, which is challenging to address within a limited number of queries. Existing works mainly tend to attack low-degree victim nodes because such nodes exhibit lower robustness compared to high-degree nodes [Li et al., 2023; Zou et al., 2021]. Although attacks from the perspective of node degree have been extensively studied, this approach suggests that the topological structure of the graph can be leveraged to simplify the design of attack methods. Unlike existing approaches, our work designs edge generation by considering the neighbors of the victim node, offering a novel perspective for GIA.

Due to the message-passing paradigm in graphs, changes in a node can affect its neighboring nodes. When a new node V ′u is injected to attack victim node Vu, the feature representation of Vu is disrupted, which in turn impacts its neighboring nodes. Therefore, we designed malicious edge generation from the perspective of neighbors, expanding the attack area to Vu ∪ N(u). We only focus on first-order neighbors because the influence between graph nodes diminishes as the distance between them increases. Let pu to denote the firstorder neighbors of node in Vtest, where pu = N1(u) ∩ Vtest. The homophily of the graph implies that neighboring nodes (particularly first-order neighbors) are likely to exhibit similar behaviors. If we can implicitly ensure the similarity between V ′u and Vu, then the newly injected node and N(u) are likely to display a higher degree of homophily. This edge generation method not only simplifies the attack method but also implicitly preserves the homophily of the original graph.

We perform attacks in descending order based on |pu|, where |pu| represents the number of nodes in the set pu. If attacks are performed in ascending order based on |pu|, when |pu| = 0, our attack method degenerates into a single-node attack strategy. When attacking node u, ∀u ∈ Vtest, we connect the malicious new node X′u to k randomly selected nodes from pu, ensuring that X′u is always connected to Xu.

We utilize the Carlini-Wagner (CW) loss function [Xu et al., 2019] for our loss component, which is expressed as follows:

Here, γ represents the confidence score of Latk. A higher γ implies a stronger attack effect but results in a greater distance from the decision boundary. To ensure the attack remains as close to the decision boundary as possible, we set γ = 0.05. Combining Eq. (1) and Eq. (4), the complete attack loss function is:

To maximize the utilization of the injection node edge budget, we record triplet data (src, dst, score), where src ∈ VI , dst ∈ V , and score ∈ [0, 1]. There is no existing connection between src and dst. The score value, computed using Equation 4, represents the distance of the dst node from the decision boundary, with smaller values indicating a higher likelihood of a successful attack. After completing the attack process, if any injection node edge budget remains, the recorded triplets are sorted in ascending order based on their score values, and connections are established by prioritizing the pairs with the lowest scores.

3.2 Node Generation

Since reliance on surrogate models is eliminated, generating the features of injected nodes cannot depend on neural networks and instead becomes a combinatorial optimization problem. The high dimensionality of graph data features significantly expands the search space, particularly for continuous features, where the search space spans the range [min(X),max(X)]. To address this issue, we first reduce the dimensionality of the search space and then perform the search within the simplified space. This process presents two primary challenges: (i) determining the magnitude of feature updates and (ii) selecting the dimensions for feature updates.

The magnitude of feature updates refers to the degree of changes applied to the features during each update. In surrogate-based attacks, attackers can utilize gradients to assign varying update sizes at each step. However, in heuristicbased search, gradients are unavailable, and exhaustive search becomes impractical. To address this issue, we define feature updates as the distance between feature values and their boundary values. By doing so, continuous feature values are replaced with discrete, finite values, allowing perturbations within a significantly reduced search space. Specifically, the features of the injected node are defined as X′u = s ˜ Xu + (1 - s)Xu, where ˜ Xu is defined in Eq. (6), and s indicates whether a specific position in the feature vector is flipped, with s ∈ {0, 1}1×d .

After determining the magnitude of feature updates, we focus on how to select the feature combinations for updates. Specifically, we aim to further reduce the search dimensionality of s. Following the inspiration from BBA [Lee et al., 2022], which first identifies a successful adversarial sample and then searches for unnoticeable perturbations around it, we propose a novel approach from a different perspective. Instead of searching for perturbations around a successful adversarial sample, our goal is to initially identify the most unnoticeable injected node feature X′u init = Xu, followed by searching within its neighboring feature space to find X′u that ensures both a successful attack and unnoticeability. The subsequent challenge is how to define the neighboring feature space. Intuitively, the fewer modifications are made toX′u init , the closer it remains to the original feature space, which aligns with the principles of sparse attacks [Vo et al., 2024; Croce and Hein, 2019; Narodytska and Kasiviswanathan, 2017]. Based on this intuition, we define a relaxed search budget K, where K ∈ Z, representing positive integers {1, 2, 3, . . . }. For each injected node feature X′u , we modify only a fixed number of feature dimensions, thereby further reducing the search space. In search problems, the trade-off between exploration and exploitation is inevitable. To manage this trade-off, we employ a power decay strategy, as described in Eq. (7), where λt represents the exploration rate at iteration t, B denotes the exponential decay speed, and A controls the extent of the initial exploration. Here, A and B are real hyperparameters that can be tuned to balance the trade-off between exploration and exploitation effectively. Larger values of A promote broader initial exploration, while smaller values of B result in faster decay, leading to greater exploitation in later iterations.

It is evident that different features contribute variably to the success of the attack, making it reasonable to treat these features differently. To address this, we employ a Bayesian evolutionary algorithm to learn the influence of features from historical data and approximate their impact using a probabilistic framework. Specifically, we utilize a categorical distribution to simulate the influence of different feature dimensions, as selecting various feature combinations corresponds to multiple draws from a set of possible categories. We use the Dirichlet distribution as the prior for the categorical distribution, as it effectively models the probability distribution over each category or combination of categories. The categorical distribution is parameterized by θ, with its prior defined as: P(θ; α) := Dir(α), where α = [α1, ..., αd] represents the concentration parameters. A uniform distribution is employed with αi = 1. The Bayesian framework is structured into three stages: initialization, sampling, and updating.

Initialization of X′u . We propose a sequential attack method. When attacking a victim node Xu, we initialize the features of the injected node X′u using the features of Xu, i.e., X′u = Xu. We randomly select K positions in s and set them to 1.

Sampling of si. We perform sampling based on θ and s(t-1) , where s(t-1) i denotes the value of the i-th dimension of the perturbation vector s at the (t - 1)-th iteration. Eq. (8) focuses on exploring unknown perturbation combinations, while Eq. (9) focuses on exploiting known perturbation combinations.

The exact solution for the underlying parameter distribution θ is typically unattainable. However, since the Dirichlet distribution is a conjugate prior, we can approximate θ using the expectation of the Dirichlet posterior distribution, which is learned and updated through Bayesian inference over time.

The posterior concentration parameter αposterior i is calculated by adding the observation value s(t) i from the t-th iteration to the prior concentration parameter αprior i . Specifically, s(t) i is defined as: s(t) i = ( q(t) i +0.001 v(t) i +0.001 ), where q(t) i represents the accumulated importance of the i-th dimension feature, as described in Eq. (13), and v(t) i represents the accumulated access count for the feature at position i, as described in Eq. (14). The loss function at the t-th iteration of feature optimization is denoted as: ℓ(t) = Latk(fθ(G′ ))(t) .

Updating of s(t) . We generate a sample s(t) during the t-th feature update, where each s(t) represents a candidate solution. If the new perturbed feature outperforms the perturbed feature from the (t-1)-th iteration, we retain the current sample. Otherwise, we retain the sample s(t-1) from the previous iteration. The corresponding formula is as follows:

3.3 Comprehensive Execution Process of QUGIA

In this subsection, we provide a detailed explanation of the execution process of QUGIA. The complete execution procedure is presented in Algorithm 1. In each injection step, QUGIA first determines the connectivity of the injected node through edge generation (lines 2-3) and then optimizes its features (lines 4-17). After injecting a node, it updates the structural information (line 18) and repeats the process until the node injection budget is exhausted. If any edge injection budget remains, it is allocated through edge generation (line 20).

4 Experiments

4.1 Datasets

We evaluate our approach on six datasets, covering both discrete and continuous features. The discrete datasets include Cora and Citeseer [Yang et al., 2016], while the continuous datasets comprise Pubmed [Sen et al., 2008], the GRBredefined versions of Cora and Citeseer [Zheng et al., 2021], and the arXiv dataset from OGB [Hu et al., 2020]. We adopt a data-splitting strategy similar to those used in prior studies [Chen et al., 2022; Zheng et al., 2021]. Detailed descriptions of the datasets are provided in the Supplementary Material.

4.2 Baseline

The study of node insertion attacks in black-box settings remains relatively unexplored. To provide a comprehensive evaluation, we selected several representative methods as baselines. These include TDGIA [Zou et al., 2021], the state-of-the-art method for node insertion attacks; ATDGIA [Chen et al., 2022], a variant of TDGIA; and AGIA [Chen et al., 2022], which adopts a Gradient-Driven Injection strategy. Additionally, we incorporated HAO [Chen et al., 2022] into TDGIA, ATDGIA, and AGIA to thoroughly assess the unnoticeability of the attacks. Since these methods require

Algorithm 1 QUGIA

Input: Graph G = (A,X), target node set Vt, injection node attack budget ∆n, injection node edge budget ∆e, maximum iterations T, Dirichlet parameters, structural selection score |p|, model-predicted label function f(), node labels Y .

Output: Final adversarial graph G′

• 1: for each i ∈ [0,∆n) do
• 2: Select victim node u based on sorted scores |p|
• 3: Initialize A′u by connecting injected nodes to node u and its neighbors
• 4: while t < T and ∃j ∈ (pu ∪ {u}), f(j) ̸= Yj do
• 5: Initialize feature matrix X′(0) u
• 6: Sample perturbation vector s(t) i according to Equations (8-10)
• 7: X′(t) u ← s(t) ˜Xu + (1 - s(t) )Xu
• 8: Calculate loss ℓt for X′(t) u using Equation (5)
• 9: if ℓt < ℓt-1 then

• 11: Update A′ , X′ with A′u , X′(t) u using (2)
• 12: else

• 14: end if
• 15: Update λt using Equation (7)
• 16: Update Dirichlet parameters according to Equations (11-14)
• 17: end while
• 18: If f(u) ̸= Yu, then for all m ∈ N1(u) ∩ Vt, the score is updated as |pm| = |pm| - 1.
• 19: end for
• 20: Allocate remaining edge budget ∆e
• 21: return G′ = (A′ ,X′ )

gradients from the victim model, we set the surrogate model to have the same architecture as the victim model, with a fixed random seed of 666. Furthermore, we included G2A2C [Ju et al., 2023], a recent query-based attack that leverages reinforcement learning. To ensure a fair comparison, G2A2C was configured to operate under the same maximum number of single-node queries as our proposed method.

4.3 Evaluation Protocol

To ensure a comprehensive comparison, we selected three widely used GNN models without defense mechanisms and three GNN models with defense mechanisms. For models without defenses, we included GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], and APPNP [Gasteiger et al., 2019]. For models with defenses, following prior work [Chen et al., 2022], we selected Guard [Zhang and Zitnik, 2020], EGuard, and RGAT [Chen et al., 2022].

The number of inserted nodes is defined as |VI| = a|V |, where a represents the percentage of the total number of nodes in the clean graph. To evaluate the performance of various attack methods under different attack constraints, we set a to 1%, 3%, and 5%. The maximum degree of the inserted nodes is constrained by the average degree of the corresponding graph dataset.

All attack methods were executed using five different random seeds, and we report both the mean and variance of the results across these five runs. The average performance of the attack methods is summarized in Table 1 and Table 2. In the no-defense setting, we present the average results across GCN, GAT, and APPNP, while in the defense setting, the results are averaged over Guard, EGuard, and RGAT. For additional details, including experimental configurations, comprehensive results, and sensitivity analyses, please refer to the Supplementary Material.

4.4 Performance Comparison

In Table 1 and Table 2, we present the test set classification accuracy of GNN models under various attack methods, with lower values indicating stronger attack performance. The best results are highlighted in bold, while the second-best results are underlined. These experimental results demonstrate that our attack method achieves superior performance on both defended and undefended GNN models. Specifically, our method outperforms AGIA by nearly 5% on average and up to 10% in the best case on undefended models. On defended models, our method performs significantly better on discrete datasets compared to other methods. This indicates that gradient-based approaches struggle with discrete data, as gradients are more suitable for optimizing features in continuous data. Although G2A2C reduces reliance on surrogate models, its focus on single-node attacks hinders the effective allocation of the attack budget across multiple nodes, leading to weaker performance.

Additionally, we found that the performance of gradientbased attack methods drops significantly on defended models when the HAO module is removed. Our method achieves up to a 10% improvement compared to the effective AGIA+HAO attack method on defended models. Interestingly, attack methods with the HAO module generally perform worse on undefended models but better on defended ones. This suggests that the HAO module sacrifices some maliciousness to preserve homophily, making attacks less noticeable. Compared to HAO, our attack method implicitly preserves the homophily of the graph, making it harder to detect using homophily-based defense mechanisms. Furthermore, our attack method maintains excellent performance even on undefended GNN models.

Moreover, we observed that APPNP exhibits surprising robustness to GIA attacks, consistent with findings in previous work [Zhang et al., 2023]. This robustness is likely due to the residual connections in APPNP, which preserve the original feature information. Our experiments show that different models exhibit varying levels of robustness to GIA attacks. Exploring effective GIA attack and defense mechanisms remains an important research direction.

4.5 Homophily Analysis

To further investigate the differences between our method and HAO, we compared our approach with the best baseline under defense models, TDGIA+HAO, on the Cora and GRBCiteseer datasets with α = 0.03 and a fixed seed of 0. Following the discussion in previous work [Chen et al., 2022], we utilize node similarity to analyze the homophily distribution. Node similarity is defined as the similarity between the features of node u and the aggregated features of its neighbors. As illustrated in Figure 2, when TDGIA is applied without HAO, the node similarity of the perturbed graph deviates significantly from the distribution of the original clean graph. However, the addition of HAO effectively reduces this deviation. Furthermore, we observed that HAO is less effective on datasets with discrete features compared to those with continuous features, likely due to its reliance on surrogate model gradients.

Similar to HAO, our method also brings the homophily distribution of the perturbed graph closer to that of the original graph. Our attack method preserves the homophily of both discrete and continuous features. In GRB-Citeseer, we shifted a small number of nodes with a similarity of around 0.9 to approximately 0.7. Experimental results suggest that this shift is less likely to be detected by homophily defenders. Balancing the protection of homogeneity while enhancing the performance of attack methods against undefended models remains a challenge.

4.6 Ablation Analysis

Refer to the Supplementary Material for details on the ablation analysis. Detailed experimental results for Table 1 and Table 2 are also provided in the Supplementary Material.

5 RelatedWork

With the widespread adoption of GNNs, their robustness against adversarial attacks has gained increasing attention. While early studies mainly focused on GMA, constraints such as user permissions have led to a shift toward GIA, which has emerged as a more practical and effective attack approach. NIPA [Sun et al., 2020] achieves its malicious intent by generating a batch of random nodes and injecting them into the existing graph. AFGSM [Wang et al., 2020] employs the fast gradient sign method to inject malicious nodes, enabling attacks on large-scale graphs. G-NIA [Tao et al., 2021] utilizes neural networks to learn and generate new nodes and edges, which are then injected into the original graph to launch attacks. TDGIA [Zou et al., 2021] proposes a method for detecting vulnerable nodes in the graph topology to identify attack targets and introduces a smooth feature generation approach to facilitate attacks. AGIA [Chen et al., 2022] utilizes surrogate model gradients to optimize edge weights and inject node features. HAO [Chen et al., 2022] offers a plugin method to enhance the unnoticeability of attacks, utilizing the homophily ratio of nodes as an unnoticeability constraint to further improve the stealthiness of adversarial attacks. However, the aforementioned methods all rely on surrogate models, and discrepancies between the target model and the surrogate model may lead to degraded attack performance. G2A2C [Ju et al., 2023] formulates the attack process as a Markov Decision Process (MDP) and utilizes reinforcement learning to optimize an injection model based on query-based learning. While G2A2C alleviates dependency on surrogate model gradients, it does not consider the unnoticeability of the attack and still depends on surrogate models.

6 Conclusion

In this work, we propose a neighbor perspective-based attack method that uses a Bayesian framework to generate features for injected nodes, completely eliminating the dependence on surrogate models. Our attack method implicitly preserves the homophily of the original graph, ensuring excellent attack performance under both homophily defenders and undefended models. Extensive Experimental results show that our method outperforms existing state-of-the-art attack methods.