Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel perturbation constraint (named TDAP) for adversarial attack on discrete-time dynamic graph. Importantly, TDAP can preserve the average rate of structure and embedding changes. As TDAP constraint has not been studied before for dynamic graph, authors propose a theoretically grounded approach named TD-PGD for easily extending TDAP to find attacks in a more practical online setting.
Experiments are conducted on dynamic link prediction and node classification tasks to show the effectiveness of TD-PGD. 

strength_and_weaknesses: Strength:
1. The paper is well written and easy to follow. 
2. Theoretical proofs are given.

The author proposed TD-PGD as an attack approach on dynamic graph models. I have the following questions that are mainly related to the proposed constraints.

1. Limiting the impact of attack perturbations on the change rate of structures and embeddings sounds reasonable, but it would be conditional. Nowadays, spatial- and spectral-based anomaly detection techniques on graphs are developing rapidly. The attack constraint on dynamic graphs is fundamental to this task, thus the authors should give a rigorous proof about why and when anomaly detection algorithms fail in the face of the proposed constraints.
2. The proof is not rigorous. First, although the bound is proven, there is no limit to the constants $\alpha$ and $\beta$, which might seriously affect the average change preservation. Second, the change of a matrix is directional, it is unreasonable to just consider the norm of average changes. To my knowledge, spectral anomaly detection methods can effectively capture the anomaly caused by the change directions.
3. The proof is inconsistent with the target. It is not clear how the proven bound echoes the word ‘preserves’. A small enough $\overline{dA’}$ instead limits the dynamics of dynamic graphs, which increases risk being detected. I think at least the following formula should be proved:  $\vert \overline{dA’}-\overline{dA} \vert \leq \phi$, where $\phi$ is the bound to make the perturbed structure change rate preserved. ‘Implications’ are intuitively sound, but theoretical proof might be flawed.
4. The authors are suggested to empirically demonstrate that anomaly detection is insensitive to the proposed attack method. If the attack itself is easily detected, the performance drop may be ineffective.

clarity,_quality,_novelty_and_reproducibility: The method and the research problem are not surprising. Writting is good. Novelty is limited.
summary_of_the_review: The paper is well written in terms of grammar and writing style. Theoretical proofs are not mathematically rigorous and are inconsistent with the constraint targets. Necessary assumptions are not made clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a novel adversarial attack strategy for discrete-time graph neural networks (GNNs). The objective is to perturb the sequence of graphs to decrease accuracy on prediction tasks such as dynamic link prediction and node classification. To preserve temporal dynamics of the graph to avoid detection, the authors propose the temporal dynamics-aware perturbation (TDAP) constraint. They then propose a projected gradient descent algorithm to identify effective perturbations that satisfy the TDAP constraint. They demonstrate strong empirical performance when attacking three different discrete-time GNNs.

strength_and_weaknesses: Strengths:
- Proposed TDAP constraint and projected gradient descent relaxation to find near-optimal attacks are principled and technically sound.
- Proposed Temporal Dynamics-aware Projected Gradient Descent (TD-PGD) attack method is much more effective than greedy and other baseline attacks subject to the same TDAP constraint.
- There does not appear to be much prior research on attacks for dynamic GNNs, so novelty is high.

Weaknesses:
- Some empirical results regarding the proposed Embedding Variability (EV) seem highly implausible, if not impossible.
- Attack performance for online version of TD-PGD is inexplicably poor in several experiments. More investigation should be conducted as to why this is happening, beyond just a conjecture.

Questions:
1. What is the meaning of the notation $\mathbf{S}_t \leq \varepsilon_t$ in line 4 of Algorithms 1 and 3? On one side of the inequality, you have a matrix, and on the other side, you have a scalar. Is there supposed to be $\ell_1$ norm around $\mathbf{S}_t$?
2. Also for line 4 in Algorithms 1 and 3, why randomized rounding using Bernoulli($\mathbf{s}_t^{(N)}$) rather than just directly rounding? Can you guarantee that the discretized $\mathbf{S}_t$ satisfies the TDAP constraint, and not just the continuous $\mathbf{s}_t$?
3. How is a standard deviation of 6.37 for the EV of EvolveGCN possible when the mean is 0.81, and EV must be greater than 0 according to Equation (7)? Similarly, I see error bars going into the negatives in Figure 6.

Typos and minor issues:
- Some minor inconsistencies in notation in Algorithm 1: I believe the vectors $\mathbf{a^{(i)}}$ and $\mathbf{s^{(i)}}$ should also have subscript $t$, and $s_t^{(N)}$ should actually be a vector $\mathbf{s}_t^{(N)}$.
- Abstract and Section 5.1: "upto" -> "up to"

clarity,_quality,_novelty_and_reproducibility: - Clarity: Medium. The paper is mostly well written, but some important points are unclear (see my questions above), and there are some notation issues.
- Quality: Medium. There are potentially some technical issues with some experiment results, but the proposed TDAP constraint and TD-PGD methods seem mostly sound.
- Novelty: High. There is both high methodological and empirical novelty in this paper. The TDAP constraint and TD-PGD attack method constitutes the methodological novelty, while the results on attack vulnerability for the three different GNNs constitutes the empirical novelty that may be useful beyond this paper.
- Reproducibility: Medium. Lots of details on experiment setup are provided in the appendix, along with code. I skimmed through some of the code but did not run it. Some of the results seem implausible, so I don't know how reproducible they would be.

summary_of_the_review: The authors present a novel and technically sound approach to attack dynamic GNNs. I have some technical concerns regarding empirical results that prevent me from more strongly recommending acceptance. I should note also that my expertise is in building models for dynamic networks and not attacking them, so my knowledge of research on adversarial learning is lower.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a new constraint on generating perturbations on discrete dynamic graphs and a white-box attack methods on dynamic graphs. Several experiments have been conducted to verify the effectiveness of the proposed method.
strength_and_weaknesses: Strength:
* The paper focuses on a new perspective of dynamic graph attack
* The draft is organized well and easy to follow
* The technical details are presented clearly

Weakness:
* The experiments results need more analysis and to be better presented; some experiment design needs to be better justified
* The motivation of proposing the new constraint need to be highlighted
clarity,_quality,_novelty_and_reproducibility: The technical details are presented clearly. However the experiment section needs to be strengthed
summary_of_the_review: My major concern is on the evaluation section:

- It would be better if the authors can include more state-of-the-methods on dynamic graph modeling in the evaluation (e.g., ROLAND) in addition to the current methods (e.g., DySAT, etc.) and discuss whether the proposed attacking method apply to them or not
- The relative drop figure can be misleading (e.g., Fig. 1) as the y-axis scales are not aligned. I suggest the authors to plot the absolute values instead
- Some design choices need to be better justified: e.g., why only selecting top degree nodes to evaluate the classification tasks
- I suggest the authors to conduct more analysis instead of just presenting the results: e.g., DySAT seems suffering less from the proposed attack methods. What is the potential reason for this robustness compared w/ other mechanisms? Any specific mechanisms can be further designed to attack this category of modeling algorithms?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper aims at modeling adversarial attacks which can perturb the input graph sequence on discrete-time dynamic graph models meanwhile preserving the temporal dynamics of the graph.Then they propose a constraint named Temporal Dynamics-Aware Perturbation (TDAP) to make imperceptible perturbations in discrete-time. Through the proof provided, the perturbations under TDAP constraint preserve changes from the structural and embedding perspectives.
strength_and_weaknesses: \+ It is a less studied problem that generates attacks on the time-evolving graphs.

\+ Theoretical proofs and extensive experiments are given. 

\- The layout of this article is somewhat hard to follow.
clarity,_quality,_novelty_and_reproducibility: Writing can be improved in some parts of the paper.
summary_of_the_review: 1. The meaning of proposed metric embedding variability (EV) is similar to the TDAP constraint. So the value of EV should be small intuitively under TDAP constraint. It is better to provide the explanation and comparison to other existed metrics. 

2. Table 2 only reports the EV metric for TD-PGD, I would like to see more attack methods in the results. And the proposed method seems cannot achieve the best results in appendix H.4, whiy.

3. Some baselines should be considered, e.g., TGA (Chen et al., 2021b).
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper studies adversarial attacks on time-evolving graphs. The paper introduces the Temporal Dynamics-Aware Perturbation (TDAP) constraint, which allows for small perturbations of graphs analogous with other adversarial settings, while still preserving the graph evolution. This constraint appears to be combinatorial, and the paper suggests greedy and projected gradient descent with rounding approaches. Numerical studies are shown to show the effect of the perturbations.

strength_and_weaknesses: Strengths


Weaknesses

* The paper and, in particular, the numerical studies do not provide much motivation as to why we need to study adversarial attacks in this setting.
* The theory. Proposition 1 does not appear to be a true proposition but a condition. Are the Theorems really important? How good is the PGD approach at soolving the optimization problem in equation (2) in any specific setting?
clarity,_quality,_novelty_and_reproducibility: * Low quality, low novelty.
* Clarity and reproducibility are fine.

summary_of_the_review: * This seems to be an extension of adversarial perturbations to a setting where it is unclear the study is necessary.
* Even if the problem were important, the theory seems weak and should be revised in its content and/or presentation.
* Strangely, a new proposal for a defense mechanism is missing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors study the robustness of graph learning techniques, specifically in the setting of time evolving graphs. For this, the paper proposes an adversarial attack approach (here: projected gradient descent under a specific budget constraint taking adjacent snapshots into account) showcasing the methods (non)robustness. The work has received mixed scores, with different opinions about its novelty, motivation in general, presentation, and experimental execution. Due to one strongly diverging score, the paper has been checked in detail again.

Regarding the motivation: Overall, I feel that the motivation is good and showcasing limitations of temporal methods is important.

Regarding the novelty: It has to be noted that attacks to temporal graphs have been studied before. Likewise have versions of PGD been studied for (graph) attacks multiple times. Thus, I feel that the technical novelty is indeed not the strongest. Moreover, at the end, the proposed constraint it still a usual budget constraint but just uses some "data-dependent" threshold. 

Regarding experiments: Given that the constraint is still some budget constraint, I was wondering why the authors do not compare against a standard PGD attack (e.g. as shown in Table 1 first row). While not designed for dynamic data, one could still use PGD on every snapshot individually. At the moment, the only real competitor is TGA. The other baselines are, not surprisingly, not very strong.

Regarding presentation: I found the overall presentation to be fine. However, I don't really see the benefit of the presented theorems (partially because the statements are a bit obvious).

Given these points, I encourage the authors to revise the paper and resubmit at a future venue.
justification_for_why_not_higher_score: Based on the description above, there are various points the authors can improve.
Decision: Reject