## 2 Related Work
### Graph Injection Attack  
In the majority of research, adversarial attacks on Graph Neural Networks (GNNs) are executed by modifying node features or edges in the graph, which is known as Graph Modification Attack (GMA). While GMA has shown remarkable efficacy in a multitude of attack scenarios, it is based on the premise that attackers can easily alter the original graph, an assumption that is unrealistic in most situations. To address this concern, researchers have proposed Graph Injection Attack (GIA), which injects adversarial fake nodes into the graph instead of modifying the origin graph.  
In white-box graph injection attacks, the injected fake nodes and fake edges are typically generated based on the gradient values. [PERSON] et al. [18] propose the Node Injection Poisoning Attack (NIPA) method, which makes use of the reinforcement learning method to generate fake nodes and fake edges for poisoning attacks. [PERSON] et al. [13] introduced the Global Attacks via Node Injections (GANI) method, which generates features and selects neighbors for the fake nodes based on the statistical information of features and evolutionary perturbations obtained from a genetic algorithm. [PERSON] et al. [19] propose a Generalizable Node Injection Attack (G-NIA) method that injects only a single node during the test phase to dampen the performance of the target GNN model for evasion attack. [PERSON] et al. [20] found that the flexibility of GIA will lead to great damage to the homophily distribution of the original graph, and suggest using the Harmonious Adversarial Objective (HAO) method to generate undetectable fake nodes.  
In black-box attacks, the information available to the attackers differentiates two types of adversarial strategies: transfer-based attack approaches and query-based attack approaches. In transfer-based attack approaches, the training data and the ground-truth training labels are accessible. Attackers generate fake nodes on a pre-trained surrogate model and enhance the transferability to an attack target model. [PERSON] et al. [21] propose Topological Defective Graph Injection Attack (TDGIA), which is a black box graph injection attack method which leverages the topological vulnerabilities to generate fake edges and optimizes the features of adversarial nodes.  
In query-based attack approaches, the adversary can submit the perturbed graph to the target model. By leveraging the classification confidence provided by the target model, the attacker then optimize the fake nodes. [PERSON] et al. [22] model the graph injection attack as a Markov decision process and propose a Gradient-free Graph Advantage Actor Critic (G\({}^{2}\)A2C) method to generate fake nodes and fake edges in a black box setting. [PERSON] et al. [23] formulate the GIA problem as a graph clustering problem and propose a black-box cluster attack method that measures the similarity between victim nodes using a metric measuring adversarial vulnerability and then optimizes fake nodes through queries.  
This paper primarily focuses on query-based black-box attack. In this attack scenario, the attacker can access a subset of the dataset without ground-truth labels, and is able to obtain the target model's classification confidence through queries.