Post-Hoc Robustness Enhancement in Graph Neural Networks with Conditional Random Fields

1. The contribution of this work is quite limited. Although it provides a theoretical framework of CRF for designing GNN architecture, the authors heuristically define the potential functions $\phi_a$ and $\phi_{ab}$ without any theoretical guarantee or intuition from the CRF perspective. These two terms actually follow the robustness criteria of most existing works.

2. The experimental evaluation is not comprehensive:

   • Baselines: The selected baselines are insufficient. How does RobustCRF compare to RUNG [1], ElasticGNN [2], and SoftMedian [3]?
   • Attacks: The main evaluation focuses on feature-based attacks, which are not effective for graph-based models. For structure-based models, the authors only compare the black-box Dice attack, which is not a commonly used attack in this field. The authors should evaluate the model under topology PGD attack, metattack, nettack, or node injection attack.
   • Performance: The models show very limited improvement over other baselines, or even underperform them.

[1] Robust Graph Neural Networks via Unbiased Aggregation

[2] Elastic Graph Neural Networks

[3] Robustness of Graph Neural Networks at Scale

[4] Graph Neural Networks Inspired by Classical Iterative Algorithms

3. The presentation needs further improvement:

   • Notation: The notation is poor and very confusing. The input notation should be consistent. In the paper, $[A,X]$, $[G,X]$, and $\mathcal{G} \times \mathcal{X}$ appear to represent the same thing.
   • Clarity: What do $\tilde{G}$, $\tilde{X}$, and $\tilde{Y}$ mean? Sometimes they denote the perturbed input, other times updated predictions, and occasionally they are used to differentiate two inputs. This makes it difficult for readers to follow the paper.
   • Redundant Information: Sections 4.1 and 4.2 seem redundant. This information is commonly known in the robustness of GNNs but occupies two subsections.
   • Table Placement: Tables are not positioned properly. For example, Tables 1 and 4 should be near the main experiment, and Table 2 (ablation study) should not be placed between the main result tables (Tables 1 and 4).

4. The paper lacks ablation studies to validate the effectiveness of the proposed RobustCRF. For example, the authors should include an ablation study to assess the impact of $\alpha$ in the potential functions, the number of iterations, etc.

I think the weakness lies in insufficient experiments. Some experiments need to be refined or added.

For example, for the structural perturbations. The chosen attack method is old. Could authors consider using some new SOTA attack method?

Besides, it would be better to have all the experiments in Table 8 look like in Table 1. Besides, for the results in Table 4, why are there no results on the methods with RobustCRF? (E.g., GCNSVD w/RobustCRF, and GCNJaccard w/RobustCRF). Is RobustCRF also compatible with them?

1. It is not clear why, in the clean dataset setting, RobustCRF can achieve comparable or even better performance than GCN. Intuitively, RobustCRF should perform worse than the backbone on a clean dataset. Could the authors provide an explanation for this phenomenon?
2. Since RobustCRF introduces new hyperparameters, could the authors provide a hyperparameter analysis?
3. The performance improvement appears marginal, especially under the PGD attack in Table 1. Could the authors provide more explanation on this?

The biggest issue with this paper is that its literature review is outdated. It does not cite any papers (except GCORN) in the field of GNN adversarial robustness published after 2023, resulting in the omission of many recent advancements in evasion attack and defense. For example:

Missing discussion with adaptive attack.

Adversarial robustness studies the generalization in the worst-case scenario. [1] provides a detailed explanation of how existing GNN defenses are highly vulnerable to adaptive evasion attacks and propose a set of perturbed graphs as a bare minimum robustness unit test.

Nicholas Carlini has elaborated extensively on this topic. When designing a defense method, ensuring attack agnosticism and assuming the adversary is aware of the defense are better standards for evaluating the robustness of a method. If a method can be bypassed by a very simple trick, how can we argue that it is adversarially robust?

Authors also mentioned the hope that the method would be robust against unknown future attacks. Therefore, assuming robustness in any situation is necessary, which is why considering adaptive attacks is essential when developing defenses.

Missing comparison with the current state-of-the-art defenses against evasion attacks, adversarial training [2, 3].

The experimental setup of adversarial training is same as that of this paper and shares a similar motivation—encouraging the model to be locally invariant so that it maintains the same output within the range of semantically preserving perturbations. Based on the experimental results presented, the robustness of CRFRobust does not show a significant advantage compared to the baselines used in the paper. Therefore, it is highly likely that adversarial training would perform much better than CRFRobust.

The attacks used in this work are TOO weak.

The structural attack baseline used in this work, DICE, is a heuristic attack based on homophily assumption. However, it serves as a very weak attack in this filed. The authors should consider stronger attack settings, similar to those described in [2] and [3].

References:

[1] Are Defenses for Graph Neural Networks Robust? NeurIPS 2022.

[2] Adversarial Training for Graph Neural Networks, NeurIPS 2023.

[3] Boosting the Adversarial Robustness of Graph Neural Networks: An OOD Perspective, ICLR 2024.