LiSA: Leveraging Link Recommender to Attack Graph Neural Networks via Subgraph Injection (Extended Abstract)

1 Introduction

In recent years, Graph Neural Networks (GNNs) have shown remarkable proficiency in modeling graph-structured data. GNNs primarily operate on a message-passing mechanism. This process of iterative information aggregation enables GNNs to effectively update node representations while incorporating the structural properties. However, the powerful message-passing mechanism of GNNs also brings its share of challenges and limitations. Malicious attackers can intentionally perturb the graph structure and features. Such deliberately tampered information can propagate among nodes, leading to a degraded performance of GNNs [Dai et al., 2022; Dai et al., 2018; Z¨ugner et al., 2018; Z¨ugner and G¨unnemann, 2019; Chen et al., 2018; Wang et al., 2020; Chang et al.,

∗This paper is an extended abstract of the work that received the Best Paper Award at PAKDD 2025 [Zhang et al., 2025].

†Corresponding author.

2019]. Among various attack methods, manipulation attacks [Z¨ugner et al., 2018] have been demonstrated to be particularly effective. These attacks involve adding or deleting edges, or modifying node features in the original graph, all within a constrained budget.

Nonetheless, adversaries frequently encounter practical hurdles when attempting to manipulate these data, as it usually requires direct access to the backend data, a task that is not easily achievable. On the other hand, node injection attacks (NIAs) [Sun et al., 2020; Tao et al., 2021; Zou et al., 2021] present a more feasible approach. Such attacks degrade classification performance by introducing malicious nodes linked to target nodes, spreading harmful attributes. Within citation networks, adversaries may craft counterfeit papers and insert references to target papers, ultimately causing them to be misclassified. This kind of emerging attack method have demonstrated high success rates and are increasingly seen as a more practical method in real-world scenarios. Injecting fake nodes is often more feasible than modifying data on existing nodes, making these techniques particularly insidious.

There is no doubt about the practicality and effectiveness of NIAs. Nevertheless, current research often focuses on ideal conditions, which implies that adversaries can freely establish connections between target nodes and injected fake nodes. However, this assumption does not universally hold across various applications. Especially in applications where security is critical, like social networks, fake users who connect with the target user can subtly alter the ground truth label of the target user, leading to targeted advertising. However, it is not certain that target users will approve connection request with fake accounts. Thus, evaluating these attack models under the assumption of cost-free linking can be misleading, potentially leading to an overestimation of the attack outcomes. These concerns highlighted above have motivated us to focus on enhancing the likelihood of adversaries successfully linking fake nodes to the target nodes. Given the prevalence of link recommendation algorithms within GNN-based applications, we explore the potential to exploit these link recommenders to facilitate malicious link formation. The proposed subgraph injection attack (SIA) scenario is shown in Fig. 1. Our method does not manually add edges between target victim nodes and the aggressor fake nodes. Instead, it deceives the link recommender of GNN into actively initiating links formation. Once these links are established, the classification performance on the target victim nodes suffers a considerable decline, ultimately enabling a successful attack. This novel approach to adversarial attacks is crucial for real-world applications yet remains largely unexplored. Moreover, the uncertain feasibility of attacking multiple GNN models simultaneously poses a significant challenge in solving this problem.

In this work, we investigate a unique SIA scenario, which injects an isolated subgraph to deceive both the link recommender and the node classifier simultaneously. Specifically, it aims to mislead the link recommender into creating adversarial links from targeted victim nodes to the subgraph, thereby undermining the accuracy of node classification. Our contributions in this study are outlined as follows: 1) We explore a novel attack scenario utilizing the link recommender to compromise the node classification accuracy within a GNN. 2) We introduce Link Recommender-Subgraph Injection Attack (LiSA), a pioneering framework crafted to effectively generate subgraphs by employing a dual surrogate model and bilevel optimization. 3) Through rigorous experimentation on diverse real-world datasets, we validate the effectiveness and applicability of our proposed methodologies.

2 RelatedWorks

Adversarial attacks on GNNs aim to exploit model vulnerabilities and are generally categorized into evasion, poisoning, and backdoor attacks. Evasion attacks manipulate graph structure or node features during the test phase to induce incorrect predictions without modifying the trained model [Z¨ugner et al., 2018; Zou et al., 2021; Xu et al., 2019]. Poisoning attacks instead occur during training, where adversarial edges or nodes are injected into the dataset to distort the learning process and degrade model reliability [Dai et al., 2018; Sun et al., 2020]. Backdoor attacks embed hidden triggers into the model during training, causing the GNN to produce incorrect outputs when the trigger appears while behaving normally otherwise [Xi et al., 2020; Zhang et al., 2021; Dai et al., 2023]. However, these methods often struggle to demonstrate their effectiveness in realistic scenarios. In practice, attackers typically cannot directly modify the original graph, and injected nodes often fail to establish connections with target victims, significantly reducing attack success rate (ASR). To address this limitation, we propose leveraging link recommenders to facilitate link generation between injected nodes and target victims, increasing the likelihood of forming connections and improving the practicality and effectiveness of graph adversarial attacks.

3 Preliminaries

3.1 Notations

We define the original graph as Go = (Ao, Fo), with adjacency matrix Ao ∈ RNo×No and feature matrix Fo ∈ RNo×D . The target victim nodes, vt ∈ V , are selected for the attack. An isolated subgraph, denoted as Gs = (As, Fs), is injected, forming the poisoned graph Gp = (Ap, Fp):

where Ap ∈ R(No+Ns)×(No+Ns) and Fp ∈ R(No+Ns)×D is the adjacency matrix and features of the poisoned graph.

3.2 Threat Model and ProblemFormulation

Attacker's Goal. The objective of the adversary is to deceive both the link recommender, conceptualized as a form of link prediction model, and the node classifier simultaneously in a GNN system. This is achieved through the strategic injection of a deliberately crafted subraph, which will mislead the link prediction model to form connections with the target nodes, thereby influencing classification accuracy thereafter.

Attacker's Knowledge and Capability. Attackers lack specific knowledge regarding the GNN models employed, including the particular type of link prediction and node classification model utilized within the system. Nevertheless, attackers possess access to the original attributed graph as well as a restricted set of training and validation labels. Attackers are capable of introducing an isolated subgraph to the original graph. However, any alteration to the original graph or establishment of connections between the original graph and the subgraph is strictly prohibited. Additionally, the features and node degrees of the subgraph must closely resemble those of the original graph to maintain inconspicuousness.

Problem. We assume the presence of a link recommender fϕ in the GNN, utilizing a subset of edges from core users in the original graph to suggest connections. This results in an updated graph Gr, with:

The SIA strategically generates adversarial edges between the target victim nodes and the isolated subgraph, updating the adjacency matrix to:

Here, Al ∈ RNs×No represents the edges generated via link recommender, and the rank of Al increases from zero, which indicates that some adversarial edges have been generated successfully. Finally, the node classification model fθ provides predictions based on the updated graph:

where ˆ yvt is the predicted class on target victim nodes. The ultimate objective of SIA is to compromise classification accuracy, making ˆ yvt diverge from the ground truth labels.

4 Methodology

In this section, we investigate an optimization-based approach for generating subgraphs. In the SIA scenario, achieving dual adversarial goals within the SIA scenario presents significant technical challenges. Intuitively, generating links is more likely when there is a close resemblance in the node representations between the target victim nodes and the nodes of the aggressor subgraph, whereas a greater disparity in these representations increases the chances of the victim nodes being misclassified. As a result, a more deliberate subgraph optimization technique is essential to balance two conflicting objectives and identify the optimal subgraph for SIA. To this end, we introduce the LiSA framework, as depicted in Fig. 2.

4.1 LiSA Framework

The LiSA framework is designed to challenge the performance of two GNN models through a strategic deployment of dual-surrogate models for bi-level optimization in a blackbox attack context. We select the GAE [Kipf and Welling, 2016] and GCN [Kipf and Welling, 2017] as the surrogate models for link prediction and node classification, aiming to refine the adjacency matrix and feature attributes of the subgraph to meet two critical optimization goals concurrently: i) the generation of adversarial edges between the original graph and the subgraph via the link recommender, and ii) negatively affect node classification performance on target victim nodes once they are connected to the subgraph. To navigate these objectives, the attack loss function of LiSA includes two terms, balanced by a factor α, to regulate the contribution of each model:

The loss related to link prediction, Llink atk , is defined as a reconstruction loss with Q negative sampling, aiming to mislead the link predictor into establishing adversarial links aij between the original graph and the subgraph:

For the node classification, the attack loss, Lcls atk , seeks to reduce the chance of the target nodes being correctly classified by employing a cross-entropy loss with the attack label yatk:

Notably, the approach begins by pretraining a node classifier using a limited label set, subsequently swapping the top-2 output classes to define the attack labels [Mopuri et al., 2020]. This approach circumvents the use of GradMax, which complicates the task of balancing the two objectives. The continuously increasing adversarial loss for classification, Lcls atk , usually fails to maintain balance between these two loss terms. By giving precedence to the second-highest output class for the attack, we foster a more stable training environment. The comprehensive training strategy is outlined as follows:

The method involves the simultaneous bi-level optimization of the two surrogate models, with optimizing space limited to the subgraph.

4.2 Subgraph Training

The training procedure for the subgraph involves a two-tiered process with inner and outer iterations. In the inner iterations, we simultaneously train surrogate models for link prediction and node classification to optimize model parameters, while the outer iterations optimize the subgraph by alternately updating its adjacency matrix and node features. The inherent complexity of graph-structured data means that changes to the edges can significantly impact node representation. This alternating update methodology is necessary because it helps the training to achieve convergence.

Feature Optimization. The optimization process for refining the features within the subgraph employs a conventional approach that utilizes the principles of gradient descent through backpropagation. The goal is to adjust the node features in a manner that directly contributes to the two adversarial objectives. Each iteration of feature optimization is guided by the following rule:

Here, lr stands for the learning rate, and the gradient of the attack loss with respect to the subgraph features, ∇Fs Latk, directs the update, ensuring that each adjustment supports the two adversarial goals. Adjusting the balance factor α in the attack loss is crucial for aligning the feature updates with the dual aims of the attack.

Structure Optimization. Optimizing the structure of the subgraph presents a more complex challenge compared to feature adjustments. Upon the initialization of subgraph, the total number of edges within it is fixed. To maintain this constant edge count during each iteration of structure optimization, we ensure that for every edge removed, a corresponding edge is added. This process is designed to preserve the integrity of the subgraph structure while aligning with our adversarial objectives. The approach to directing structural updates involves calculating a combined gradient of the adjacency matrix at the outset of each optimization cycle:

In this formula, ∇Ap Llink atk denotes the gradient of attack loss by the link prediction model with respect to the subgraph adjacency matrix Ap before link recommender intervention, while ∇ ˆ ALcls atk represents the gradient of attack loss by the node classification model with respect to the post-update adjacency matrix ˆ A modified by the link recommender. The parameter β acts as a balancing factor in the optimization of the structure. The structural update process involves ranking the combined gradient ∇str, then strategically adding and removing edges based on this ranking. Specifically, we add edges in locations where they are currently absent, prioritizing those with the lowest combined gradient values. Simultaneously, we remove edges from areas with the highest combined gradient values.

5 Experiments

To evaluate the effectiveness of our attack method, we conduct experiments on Cora and PubMed, two citation network datasets, and FacebookPagePage (PagePage), which represents a social network graph. We validate the proposed LiSA framework using GAE and VGAE [Kipf and Welling, 2016] as link recommenders, and GCN [Kipf and Welling, 2017] and SGC [Wu et al., 2019] as node classifiers. We assume that the target user establishes links with the nodes having the top three linking scores in the poisoned graph. To assess the feasibility of our methods, we randomly select 1,000 nodes from each original graph as target victim nodes. We then generate subgraphs and execute attacks on these nodes individually. This approach allows us to compute both the link success rate (LSR) and the overall ASR. The LSR is defined as the proportion where at least one adversarial edge is generated between the target node and subgraph, while the ASR refers to the misclassfication rate on these victim nodes. For the link recommender, we use 85% of the edges for training, with half serving as positive edge labels with negative sampling for both subgraph optimization and attack verification. For node classification, 5% of the nodes are randomly chosen for training labels. These labels are utilized in subgraph optimization and the pretraining of a node classifier to identify the second highest output class as the attack label. To maintain a consistent basis for comparison across different datasets, we employ a subgraph comprising five nodes for each target victim node attack. However, we tailor hyperparameters such as the number of subgraph edges nE, the balance parameters α and β, ensuring optimal performance and adaptability to the specific characteristics of each dataset.

The attack results obtained using the LiSA framework are presented in Table 1. For reference, we also report the misclassification rates on the original clean graphs to evaluate the impact of the proposed attacks. The results show that the subgraphs generated by LiSA successfully establish links between the injected subgraphs and target nodes, leading to a significant degradation in node classification accuracy. For instance, LiSA achieves over 77% LSR and 66% ASR on PubMed, resulting in more than a 45% decrease in classification performance compared with the clean model. These results demonstrate the effectiveness and efficiency of the LiSA framework and highlight the need to develop defenses against such attacks in real-world scenarios. For more detailed experiment results qualitative analysis, please refer to the original LiSA paper published in PAKDD 2025 [Zhang et al., 2025].

6 Conclusions

This study presents a new attack scenario, along with a novel attack framework that utilizes link recommender to compromise the node classification accuracy of GNNs through subgraph injection. Unlike conventional attacks that require direct manipulation of the original graph or the addition of links to artificially created nodes, LiSA executes an attack indirectly by injecting an isolated subgraph, thereby enhancing practicality in real-world scenarios. Our experiments across various real-world datasets demonstrate the effectiveness of LiSA, illustrating significant degradation in GNN performance.

Acknowledgments

This material is based upon work supported by, or in part by, the National Natural Science Foundation of China (NSFC) under Grant No. 62506316, and the Guangdong Provincial Program under Grant No. 2025DO3JOO15. This research is also supported in part by JST CREST JPMJCR23M4 and JPMJCR21D2, JST Next-generation Edge AI Semiconductor JPMJES2515, JST SPRING JPMJSP2123, JSPS Kakenhi 23H00467, 24K02940, Futaba Foundation, Asahi Glass Foundation, and Telecommunications Advancement Foundation.