MEMFREEZING: TOWARDS PRACTICAL ADVERSARIAL ATTACKS ON TEMPORAL GRAPH NEURAL NETWORKS

Authors: Yue Dai, Liang Liu, Xulong Tang, Youtao Zhang, Jun Yang
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: Graph Neural Networks, Dynamic Graph, Adversarial Attack, Temporal Graph Neural Network

Abstract:
Temporal graph neural networks (TGNN) have achieved significant momentum in many real-world dynamic graph tasks, making it urgent to study their robustness against adversarial attacks in real-world scenarios.
Existing TGNN adversarial attacks assume that attackers have complete knowledge of the input graphs. However, this is unrealistic in real-world scenarios, where attackers can, at best, access information about existing nodes and edges but not future ones at the time of the attack. However, applying effective attacks with only up-to-attack knowledge is particularly challenging due to the dynamic nature of TGNN input graphs. On the one hand, graph changes after the attacks may diminish the impact of attacks on the affected nodes.
On the other hand, targeting nodes that are unseen at the attack time introduces significant challenges.
To address these challenges, we introduce a novel adversarial attack framework, MemFreezing, to yield long-lasting and spreading adversarial attacks on TGNNs without the necessity to know knowledge about the post-attack changes in the dynamic graphs.
MemFreezing strategically introduces fake nodes or edges to induce nodes' memories into similar and stable states, which we call the `frozen state.' In this state, nodes can no longer sense graph changes or carry information, thereby disrupting predictions.
In subsequent updates, these affected nodes maintain and propagate their frozen state with support from their neighboring nodes. 
The experimental results demonstrate that MemFreezing can persistently decrease the TGNN models' performances in various tasks, delivering more effective attacks under practical setups.

Decision: reject
Reviewer scores: 5, 8, 3, 8

Reviews and discussion:
<thread>
creation date:
1730574025553

thread_type:
official_review

<thread_object>
creator: reviewer_qqgz

<content>
summary:
This work represents MemFreezing, an adversarial attack framework for a Temporal Graph Neural Network(TGNN) that targets the intrinsic node memory mechanism. MemFreezing disables node memory in TGNNs by forcing them into stable states, achieved by a novel cross-freezing mechanism and future simulation. Empirical results have demonstrated that the proposed attack causes a long-lasting frozen state of affected nodes and can spread this impact to current and future neighbour nodes.

strengths:
- The paper proposed novel adversarial attack strategies on TGNNs by focusing on the memory component of TGNN models
- MemFreezing can persist impact on TGNNs performance over timestamps by effectively freezing the memory of the affected node.
- MemFreezing disturbs the prediction of TGNNs not only on affected nodes but also on future nodes of the networks.
- The paper pointed out the impractical strategies of existing adversarial attacks on temporal graphs and introduced more effective adversarial strategies with limit k, MemFreezing, under practical setups
- The effects of MemFreezing are evaluated from different vanilla TGNNs to defence models, from small to large scale datasets.

weaknesses:
- Notation. Consistency in notions could enhance the readability of work. This work uses different notation to indicate nodes (i.e. $node_1$, $u$). In addition, in equation (1), x(t_1) is considered as a set of events at timestamp $t_1$, and the $x(t)$ at line 136 indicates an event. Different notations are needed to differentiate a set of events from a single event to avoid confusion.
- Typos. Line 480 mentions an unclear definition of “one-hot” neighbour. “MemFreezing (1%)” is repeated in Figures 12 and 13.
- This adversarial attack strategy only works with node-memory-based TGNNs, limiting MemFreezing's contribution to evaluating the robustness of other TGNNs, such as EdgeBank[1]. But the authors have acknowledged this issue.

questions:
- What is the time complexity of MemFreezing?
- Empirical experiments have shown that MemFreezing can persistently decrease the TGNN models. However, JODIE[2] and Dyrep[3] use RNN to maintain node memory, while TGN[4] and ROLAND[5] adopt GRU. How does MemFreezing perform on other variants of RNNs, especially LSTM?

[1] Poursafaei, Farimah, et al. "Towards better evaluation for dynamic link prediction." Advances in Neural Information Processing Systems 35 (2022): 32928-32941
[2] Kumar, Srijan, Xikun Zhang, and Jure Leskovec. "Predicting dynamic embedding trajectory in temporal interaction networks." Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019

[3] Trivedi, Rakshit, et al. "Dyrep: Learning representations over dynamic graphs." International conference on learning representations. 2019.

[4] Rossi, Emanuele, et al. "Temporal graph networks for deep learning on dynamic graphs. arXiv 2020." arXiv preprint arXiv:2006.10637.

[5] You, Jiaxuan, Tianyu Du, and Jure Leskovec. "ROLAND: graph learning framework for dynamic graphs." Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2022.

* None of these are our articles.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730695663368

thread_type:
official_review

<thread_object>
creator: reviewer_ykj1

<content>
summary:
This paper makes a new definition on practical adversarial attack against temporal graph neural networks, and proposes an event attack method by injecting nodes and edges. The injected edges and nodes are designed to simulate a fake future neighborhood and further to make the nodes memory unchanged in the future updating steps.

strengths:
1. The paper first explains the motivation of “memory freezing” and shows its effectiveness by a preliminary experiment, which offers an interesting insight on TGNN model robustness. 

2. Extensive experiments are done to validate the effectiveness of the proposed method.

weaknesses:
1. This attack is limited to a white-box attack, which seems to primarily disobey the target of “practical attack”.

2. The definitions on the attack capability seems not reasonable. In a practical situation, it seems the attacker can inject several timestamps instead of a specific timestamp. Besides, in the experiments only the attack budget on the amount of injected nodes is discussed. Since an injected node may occupying multiple injected edges to different nodes, and therefore a budget on edges amount may be also needed.

3. The writing of the paper is confusing. In the section 3-4 the authors use too much verbal description on the attack problem and the proposed method, while too few notations or definition in formal expressions is given, which makes the paper hard to follow.

questions:
I’m not fully convinced by the setting of attacking on a specific timestamp of the temporal graph, instead of attacking several timestamps. In my assumption, even with the limited “current knowledge” when attacking a specific timestamp, the attacker could still attack a few timestamps by taking a “currently optimized” attack in each step. Is there any special reason or assumed scenarios for this setting of limitation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730698144234

thread_type:
official_review

<thread_object>
creator: reviewer_xoun

<content>
summary:
This paper explores the challenge of practical adversarial attacks on TGNNs and introduces a novel framework called MemFreezing. The method creates a so-called “frozen” state in node memories by adding fake nodes or edges, which prevents nodes from sensing the graph changes and thus disrupting model predictions. Experimental results show that MemFreezing effectively reduces the performance of TGNNs across various datasets and models, and outperforms existing attack methods.

strengths:
- The paper is written clearly and technically sounded. 
- The approach that creates a “frozen” state in node memories by adding fake nodes or edges is interesting.
- The experiments are thorough and comprehensive.

weaknesses:
I have some concerns about the hypothesis of the frozen state as below.

questions:
1. The attacks are assumed to be able to propagate through neighboring nodes and consistently distrupt predictions. However, I concern that changes in graph structure and heterogeneity among nodes and edges might limit the propagation effect. I suggest including specific experiments or analyses to evaluate the robustness of the attack propagation under varying graph dynamics or heterogeneity conditions. For example, it would be helpful to test the attack on graphs with different rates of structural change or varying levels of node/edge heterogeneity. This additional analysis could provide a more comprehensive understanding of the attack’s performance in diverse scenarios.

2. The paper proposes develop surrogate future neighbors using current neighbors, but in practice, it is a bit questionable to use this to reflect future graph changes, especially for those irregular or highly random dynamic graphs. I suggest the authors validate their approach on more irregular or random dynamic graphs. For example, they could test their method on synthetic graphs with varying levels of randomness or analyze how well their surrogate neighbors align with actual future neighbors in their datasets over time.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730712925677

thread_type:
official_review

<thread_object>
creator: reviewer_7jhv

<content>
summary:
The paper proposes an adversarial attack, termed MemFreezing, for Temporal Graph Neural Networks (TGNNs). MemFreezing selects pairs of victim nodes and crafts accompanying messages to update the memory of TGNNs s.t. the memory resides in an unrecoverable and update-resistant state. The authors empirically demonstrate that the heuristics underpinning MemFreezing are effective and, as a result, MemFreezing has a long-lasting impact on the attacked TGNN.

strengths:
1. The paper is well-written, and I found it easy to follow the general gist.
1. The authors propose the first attack on TGNN without knowledge of the future data.
1. The authors empirically verify that the TGNN remains effected by the attack for a considerably long time.

weaknesses:
1. The message of the paper strongly depends on the perspective of "practical attacks," without the authors specifying what properties "practicality" entails and why  "practical attacks" are a relevant research topic. Is it the goal of the authors to provide a ready-to-use adversarial attack for real-world adversaries? I hope not. I know that (for reasons unknown to me) it is often advocated that "practicality" is important for adversarial attacks on graph-structured data. While this stance is not necessarily attributed to the work at hand, it still should be discussed prominently (i.e., introduction). Also, the truthfulness of statements like "Attackers can only acquire knowledge up to the attack’s timestamp." depends on the perspective. It is not uncommon to assume an adversary with oracle-like capabilities to study the worst-case performance w.r.t. small meaningless perturbations.
1. Ideally, the authors quantify how the attack compares to an "impractical" attack with perfect knowledge. Although this seems out of scope for a rebuttal. I do not expect experiments up on this.
1. The authors could be more explicit that their attack leverages heuristics like "cross-freeing". Also, statements like "In this state, nodes can no longer sense graph changes or carry information [...]" are overclaiming without the authors providing proof that this was the case.
1. There are many other choices of attack capabilities that are not well discussed and are arguably "impractical" as well. For example, (a) the attacker has perfect knowledge about the model and all data up to $t_0$. (b) MemFreezing chooses the highest-degree nodes and then their highest-degree neighbors. In most graphs, it is very unlikely that a real-world adversary would have access to such node pairs. (c) limiting the message values by the min/max of the features (i.e., [-1, +1]) seems not very realistic/practical either. (d) focusing on inserting all adversarial messages at a single point in time (right before test) is arbitrary and likely to be detected by trivial anomaly detection methods. Results in C6 are not very convincing since FakeNodes appears to be the weakest attack.

I am willing to increase my score if the weaknesses are addressed.

Minor:
1. Using "sample" for a topk procedure was confusing to me (Section 4.3)
1. The procedure of obtaining the "nodes' ideal frozen state" was not clear from the main text.
1. It would be better to apply \text etc. to, e.g., subscripts like "L_{mse}"

questions:
1. Why do the benchmarked attacks compare in their attack capabilities? For example, as far as I understand, inserting new nodes will result in very low-degree nodes, while MemFreezing will attack the nodes with the highest degree.
1. How does MemFreezing compare to TGDIA applied multiple points in time? (C6) 
1. How is "Cross-freezing" achieved if attacking at multiple points in time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732786945221

thread_type:
official_comment

<thread_object>
creator: area_chair_ya2b

<content>
comment:
I would like to encourage the reviewers to engage with the author's replies if they have not already done so. At the very least, please 
acknowledge that you have read the rebuttal.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes an adversarial attack on temporal GNNs. This is apparently the first attack that assumes no knowledge of future data. The method creates a so-called “frozen” state in node memories via perturbations, which prevents memory updates and consequently reduces performance.

The issue of "practicality" was raised and discussed with the reviewers. While indeed not assuming future knowledge does make the attack more "practical" the authors still assume perfect knowledge about the model and all data up to $t_0$. Therefore, it is not clear how to interpret the results from the attack because it test neither worst-case performance nor real-world practical performance. Other choices (e.g. highest-degree nodes) were also questioned. The authors reply addressing these concerns was not fully convincing, and I tend to agree with the assessment of Reviewers 7jhv and YKJ1. 

In the future, I suggest that the authors to rethink the motivation for the attack and provide a stronger justification for the threat model, potentially de-emphasising the importance of whether the attack is practical or not. Going beyond the white-box setting (e.g. with surrogate models) and comparing with attacks that do have future knowledge to quantify how much this knowledge is important would be good steps towards improving the paper.