Thank you for the valuable feedback. We address your concerns and questions below.

[Q.1.] The authors claim that most of existing attacks on GNNs modify the target node’s k-hop neighborhood, but this is not accurate. For instance, most of the cited poisoning attacks focus on global structure attack, where the entire graph structure can be modified.
[A.1.] Although existing poisoning attacks can modify any part of the entire graph structure, the results of their optimization end up exclusively changing the target’s k-hop neighborhood. Furthermore, existing attacks based on meta learning can not scale to large graphs and thus are not practical.

[Q.2.] There exist (restricted) black-box attacks to GNNs, while the authors do not compare and discuss with them
[A.2.] To the best of our knowledge, no existing black-box GNN attacks can be applied to our setting, i.e., long-distance node-injection targeted poisoning. While we do not discount the possibility that potential black box attacks for this setting could be developed, doing so would require significant further research. We will add a discussion about black box attacks to a revised version of our paper.

[Q.3.] There exist many certified defenses against graph structure attacks, but the authors do not test them against the proposed attack.
[A.3.] We did not evaluate certified defenses because we do not know of any existing implementations that can be applied to our setting. Many of the certified defenses for GNNs, such as Wang et. al KDD’21 [1] and Tao et. al WSDM’21 [2], cannot handle node injection attacks. The only work that handles node injection is by Tao et al [3], however, no public implementation is available.

[1] Wang, B., Jia, J., Cao, X., & Gong, N. Z. (2021, August). Certified robustness of graph neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (pp. 1645-1653).
[2] Tao, S., Shen, H., Cao, Q., Hou, L., & Cheng, X. (2021, March). Adversarial immunization for certifiable robustness on graphs. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining (pp. 698-706).
[3] Tao, S., Cao, Q., Shen, H., Wu, Y., Hou, L., & Cheng, X. (2023). Graph adversarial immunization for certifiable robustness. IEEE Transactions on Knowledge and Data Engineering.

Thank you for the detailed review and valuable feedback. We address your comments and questions one by one below.

[W.1.] This trade-off between efficiency and success rate should be discussed better.
[A.1.] We clarify the tradeoff in our answer to your Question.3. Thank you for the suggestion.

[Q.1.] The definition of "long distance" and the specific distance of the injected malicious nodes remain unclear in the current version of the paper.
[A.1.] We define long distance as following, for any attack point $v_a$, the shortest path length from $v_a$ to the target node $v_t$ should be larger than the number of layers used by the victim GNN model. In our experiments, we set $k=3$. We will emphasize the definition more clearly in revision.

[Q.2.] Have you taken into account the influence of robust methods during the poisoning process? If so, what are the results regarding the method's effectiveness when attackers lack knowledge of defense mechanisms.
[A.2.] In the experiments reported in the paper, MetaLDT’s inner training loops and MimicLDT’s surrogate models account for what GNN defenses are used. In the table below, we include results in a setting where MimicLDT’s surrogate model does not account for GNN defenses, and we instead use vanilla GCN as the surrogate model.

We observe that for some defenses (e.g., SAGE, GNNGuard), not knowing about the defenses has little or no impact on poison success rate, but for others (e.g., SVDGCN and SoftMedian) the effects are more noticeable. Table 9 in the paper’s appendix evaluates MetaLDT under a similar scenario, i.e., in a case where its inner-training loop does not account for defenses, and leads to similar conclusions.

[Q.3.] The rationale behind why MimicLDT is more efficient is not clearly articulated. Further elaboration on this aspect would be beneficial. Is it possible to discuss the trade-off between efficiency and effectiveness, such as exploring adjustments to hyperparameters to strike a balance between MimicLDT and MetaLDT?
[A.3.] MimicLDT uses certain design heuristics to restrict the optimization to a much smaller search space than MetaLDT, and is thus more efficient. In particular, MimicLDT does not optimize for which attack points to use nor the graph structure among injected nodes. Furthermore, MimicLDT uses a surrogate optimization goal (trying to use injected nodes to cause an attack point and the target to collide in the embedding space) to determine injected node features. This is in contrast to MetaLDT whose optimization considers the entire space of attack node choices and injected node/graph structures and uses meta-learning (which requires very expensive inner training) to achieve direct end-to-end optimization of the label flipping probability.

In terms of the trade-off between MetaLDT and MimicLDT, we note that MetaLDT always has significantly higher computational cost than MimicLDT in order to achieve any decent poisoning rate, e.g., in Figure 5 of the Appendix, we show that, for Cora and GCN, MetaLDT requires a minimum of 8 inner training rounds and 9670.46s to reach the same poison success rate that MimicLDT can reach in about 43.17 seconds. On the other hand, MetaLDT’s larger search space means that it can often achieve higher poison success rates than MimicLDT can if time is not a concern.

Thank you for the valuable feedback and insightful comments. We address your concerns and questions below.

[W.1.] The motivation of considering nodes that are outside the top-k neighbors of the target victim is unclear. Can we use some threshold to filter out suspicious looking influence nodes for the node under examination? Will this filtering step can be evaded by some adaptive attacks so that short-distance attacks can still survive without sacrificing the effective much?
[A.1.] You made a good point that attackers could try to strengthen their attacks if they knew that GNN explanation tools are being used to detect short distance attacks. In addition to being less conspicuous, we think the bigger advantage of a long distance attack like MimicLDT is that it allows the attacker to choose from a much larger population of potential attack points. In particular, any node whose label is the same as the target poison label can function as an attack point, and there are many more of those at further distance away from the target node.

[W.2.] From the technical perspective, I did not find a significant (inherent) difference from the previously proposed Meta-Attack, as the major the differences are on optimizing a different loss function to encode the targeted attack objective and also to avoid making connections with nodes of top-k neighbors of the target victim during optimization.
[A.2.] Our main contribution is the practical long distance poisoning attack MimicLDT, whose design heuristics are derived from our observations of MetaLDT’s behavior. Compared to existing attacks, MimicLDT can scale to much larger graphs and is easier for the attacker to launch because it is flexible with which attack points to use. We design and evaluate MetaLDT to motivate the heuristics of MimicLDT and to quantify how much MimicLDT gives up in terms of poison effectiveness to its design heuristics.

We also want to clarify that the differences between MetaLDT and Meta-Attack extend beyond changes to the loss function, and require changing the optimization procedure. Specifically, MetaLDT (a) requires the optimization procedure to alternate between optimizing the adjacency matrix and optimizing node features; (b) uses a gradient descent based feature optimizer, rather than one based on meta-scores, thus allowing us to change the feature of all injected nodes in a single feature-optimization iteration (rather than requiring changes to a single node at a time). These changes to the optimization procedure are crucial to making MetaAttack work in our setting.

[Q.1.] What is the value of k to determine if an attack is short-distance or long distance.
[A.1.] $k$ is the number of GNN layers used by the victim model. A long distance attack is one in which injected nodes are further away from the target node than the number of GNN layers.

[Q.2.] There might be some chance to rely on using the gradient alignment technique to design stronger attacks in graph domains.
[A.2.] Thank you very much for pointing out the connection to gradient alignment. We agree that it might be feasible to apply gradient alignment for attacks on GNNs and will investigate this further.

I appreciate the feedback from the authors. However, the concerns still remain. In particular: W1. The argument of many potential attack points for the attacker to choose is not a very well-motivated. Ideally, if the authors can show that a complete pipeline where the short distance nodes are infeasible to achieve attack success empirically (with concrete numbers), then the argument of using nodes outside top-k neighbors are strongly motivated. W2. Thanks for clarifying on the difference to the Meta-Attack details. Q1. Thanks for the clarification. Is there a reason to justify why such a way set the value of $k$ captures the threshold between short and long distance? Providing some explanation in the paper will be helpful.

Thanks for the quick response. For W1, I think this is on a right path to provide better motivation for the problem. However, befriending with the target is a special case of k=1 and I think it might still be fairly easy to connect to the target as $k$-hop neighbors. In the original comment, what I meant by a complete pipeline is to show that, with some detectors (e.g., graph explanation tools) with reported TPR and FPR, indeed can detect the short distance attacks. This way, it will make the paper more convincing. If all state-of-the-art short-distance attacks are detected in such a way, designing long distance attack will be very intriguing.

Thank you very much for the detailed review and valuable feedback. We will address each comment and question below.

[W.1.] The comparison with short-distance attacks is valuable. However, the compared baselines lack more recent node injection attack methods.
[A.1.] We evaluated the efficacy of AFGSM (Wang et al., DMKD’20)[1], a well cited recent node-injection poisoning attack. We used the author’s implementation, but modified it to perform targeted label-flipping poisoning instead of misclassifying the target to be any arbitrary class. The table below shows the Cora results of direct attacks (injected nodes can be direct neighbors of the target node) as well as indirect attacks (injected nodes cannot be direct neighbors but can be k-hop neighbors). The experiments use the same setting as that in our paper (Sec 6, Table 1).

We can see that both the direct and indirect-attacks of AFGSM have a poison success rate ranging from 23–52%, which is lower than what we achieved (55-74% for MimicLDT, 53-96% for MetaLDT). We will add this comparison to a revised version of the paper.

We would also like to note that most recent injection attacks, including, TDGIA(Zou et al., KDD’21), GIA-HAO (Chen et al., ICLR’22), CANA(Tao et al., 2023), G2A2C(Ju et al., AAAI’23), are test-time evasion attacks, so we cannot directly compare against them.

[1] Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, and Qinghua Zheng. 2020. Scalable attack on graph data by injecting vicious nodes. Data Min. Knowl. Discov. 34, 5 (Sep 2020), 1363–1389. https://doi.org/10.1007/s10618-020-00696-7

[W.2.] Some claims lack further empirical or theoretical support. For example, the authors claim that 'there are many more potential attack points beyond the target’s K-hop neighborhood’.
[A.2.] Please refer to our answer to Q.2.

[W.3.] Some minor errors: designe-> design heuristicsc)Finally -> heuristics. c) Finally
[A.3.] Thank you for pointing out the typos. We will fix these.

[Q.1.] Whether the proposed method be generalized to unknown victim models?
[A.1.] Our proposed attack assumes knowledge of the victim model. We do not believe it can be generalized to unknown victim models in theory. However, empirically, the situation is a bit more complex: we ran experiments where the attacker who uses a GCN as the surrogate model either did not know what model was being used (e.g. GAT) or was unaware of what defenses were in use, and measured the efficacy of MimicLDT. We show results in the table below (the rows corresponding to “vanilla GCN”):

Our results show that in many cases (e.g. GAT) using a vanilla GCN based surrogate model can poison as successfully as using a surrogate based on the correct victim model. However, we also see a significant drop in poison success rate in other cases (e.g., SoftMedian, SVDGCN).

[Q.2.] Is there any data analysis supporting the claim that 'there are many more potential attack points beyond the target’s K-hop neighborhood’?
[A.2.] We evaluated this empirically for the Cora dataset. Figure 1 of supplementary material shows the distribution of the distance of potential attack points from a target. We can see that about 95% of the attack points are more than 3-hops away (thus qualifying as long-distance attacks). In Figures 2 and 3, we show the attack points picked by MimicLDT across various datasets and MetaLDT across various models in our experiments are between 4 and 19 hops away.