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

## Abstract

Abstract Graph Neural Networks (GNNs), which are nowadays the benchmark approach in graph representation learning, have been shown to be vulnerable to adversarial attacks, raising concerns about their real-world applicability. While existing defense techniques primarily concentrate on the training phase of GNNs, involving adjustments to message passing architectures or pre-processing methods, there is a noticeable gap in methods focusing on increasing robustness during inference. In this context, this study introduces RobustCRF, a post-hoc approach aiming to enhance the robustness of GNNs at the inference stage. Our proposed method, founded on statistical relational learning using a Conditional Random Field, is model-agnostic and does not require prior knowledge about the underlying model architecture. We validate the efficacy of this approach across various models, leveraging benchmark node classification datasets. Our code is publicly available at: https://github.com/abbahaddou/RobustCRF .

## 1 Introduction

Deep Neural Networks (DNNs) have demonstrated exceptional performance across various domains, including image recognition, object detection, and speech recognition (Chen et al., ; ; Shim et al., ). The growing interest in handling irregular and unstructured data, particularly in domains like bioinformatics, has pushed some attention toward graph-based representations. Graphs have emerged as the preferred format for representing such irregular data due to their ability to capture interactions between elements, whether individuals in a social network or interactions between atoms. In response to this need, Graph Neural Networks (GNNs) (Kipf & Welling, ; Veličković et al., ; Xu et al., ) have been proposed as an extension of DNNs tailored to graph-based data. GNNs excel at generating meaningful representations for individual nodes by leveraging both the graph’s structural information and its associated features. This approach has demonstrated significant success in addressing challenges such as protein function prediction (Gilmer et al., ), materials modeling (Duval et al., ), time-varying data reconstruction Castro-Correa et al. (), and recommendation systems (Wu et al., ).

Alongside their achievements, these deep learning-based approaches have exhibited vulnerability to various data alterations, including noisy, incomplete, or out-of-distribution examples (Günnemann, ). While such alterations may naturally occur in data collection, adversaries can deliberately craft and introduce them, resulting in adversarial attacks. These attacks manifest as imperceptible modifications to the input that can deceive and disrupt the classifier. In these attacks, the adversary’s objective is to introduce subtle noise in the features or manipulate some edges in the graph structure to alter the initial prediction made by the input graph. Depending on the attacker’s goals and level of knowledge, different attack settings can be considered. For instance, poisoning attacks (Zügner & Günnemann, ) involve manipulating the training data to introduce malicious points, while evasion attacks (Dai et al., ) focus on attacking the model during the inference phase without further model adaptation.

Given the susceptibility of GNNs to adversarial attacks, their practical utility is constrained. Therefore, it becomes imperative to study and enhance their robustness. Various defense strategies have been proposed to mitigate this vulnerability, including pre-processing the input graph (Entezari et al., ; Wu et al., ), edge pruning (Zhang & Zitnik, ), and adapting the message passing scheme (Zhu et al., ; Liu et al., ; Abbahaddou et al., ). Most of these defense methods operate by modifying the underlying model architecture or the training procedure, i.e., focusing on the training side of GNNs and, therefore, limiting their applicability. This limitation is especially pertinent when dealing with pre-trained models, which have become the standard for real-world applications. Additionally, modifying the model architecture during training poses the risk of degrading accuracy on clean, non-attacked graphs, and usually, these modifications are not adapted for all possible architectures.

In light of these challenges, our work introduces a post-hoc defense mechanism, denoted as RobustCRF, aimed at bolstering the robustness of GNNs during the inference phase using statistical relational learning. RobustCRF is model-agnostic, requiring no prior knowledge of the underlying model, and is adaptable to various architectural designs, providing flexibility and applicability across diverse domains. Central to our approach is the assumption that neighboring points in the input manifold, accounting for graph isomorphism, should yield similar predictions in the output manifold.
Based on our robustness assumption, we employ a Conditional Random Field (CRF) (Lafferty et al., ) to adapt and edit the model’s output to preserve the similarity relationship between the input and output manifold.

While the proposed approach is applicable to a wide range of tasks and models, including those in the computer vision domain, our primary focus revolves around Graph Neural Networks (GNNs). We start by introducing our CRF-based post-hoc robustness enhancement model. Recognizing the potential complexity associated with this task and aiming to deliver a robustness technique that remains computationally affordable, we study a sampling strategy for both the discrete space of the graph structure and the continuous space of node features. We finally proceed with an empirical analysis to assess the effectiveness of our proposed technique across various models, conducting also a comprehensive examination of the parameters involved. In summary, our contributions can be outlined as follows: (1) model-agnostic robustness enhancement: we present RobustCRF, a post-hoc approach designed to enhance the robustness of underlying GNNs, without any assumptions about the model’s architecture. This feature underscores its versatility, enabling its application across diverse models; (2) theoretical underpinnings and complexity reduction: we conduct a comprehensive theoretical analysis of our proposed approach and enhance our general architecture through the incorporation of sampling techniques, thereby mitigating the complexity associated with the underlying model.

## 2 Related Work

Attacking GNNs. A multitude of both poisoning and evasion adversarial attacks targeting GNNs models has surged lately (Günnemann, ; Zügner et al., ). Namely, gradient-based techniques (Xu et al., ), such as Proximal Gradient Descent (PGD), have been employed to tackle the adversarial aim, which is framed as an optimization task aiming to find the nearest adversary to the input point while fulfilling the adversarial objective. Building upon this foundation, Mettack (Zügner & Günnemann, ) extends the approach by formulating the problem as a bi-level optimization task and harnessing meta-gradients for its solution. In a different perspective, Nettack (Zügner et al., ) introduces a targeted poisoning attack strategy, encompassing both structural and node feature perturbations, employing a greedy optimization algorithm to minimize an attack loss with respect to a surrogate model. Diverging from these classical search problems, Dai et al. () approach the adversarial search task through the lens of Reinforcement Learning techniques.

Defending GNNs. Different defense strategies have been proposed to counter the previously presented attacks on GNNs. GNN-SVD (Entezari et al., ) employs low-rank approximation of the adjacency matrix to filter out noise, while similar pre-processing techniques are used by GNN-Jaccard (Wu et al., ) to identify potential edge manipulations. Additionally, methods like edge pruning (Zhang & Zitnik, ) and transfer learning (Tang et al., ) have been used to mitigate the impact of poisoning attacks.
Notably, most research efforts have predominantly focused on addressing structural perturbations, with relatively fewer strategies developed to counter attacks targeting node features. For instance, in (Seddik et al., ), the inclusion of a node feature kernel within message passing was proposed to reinforce GCNs. RobustGCN (Zhu et al., ) uses Gaussian distributions as hidden node representations in each convolutional layer, effectively mitigating the influence of both structural and feature-based adversarial attacks. Finally, in GCORN (Abbahaddou et al., ), an adaptation of the message passing scheme has been proposed by using orthonormal weights to counter the effect of node feature-based adversarial attacks.

The majority of the previously discussed methods intervene during the model’s training phase, necessitating modifications to the underlying architecture. However, this strategy exhibits certain limitations; it may not be universally applicable across diverse architectural designs, and it can potentially result in a loss of accuracy when applied to the clean graph. Furthermore, these methods may not be suitable for scenarios where users prefer to employ pre-trained models, as they necessitate model retraining.
Consequently, the need for proposing and crafting post-hoc robustness enhancements becomes increasingly apparent. Unfortunately, the existing methods in this domain remain quite limited. Addressing this gap in the literature, our work aims to contribute to this essential area. One commonly employed post-hoc approach is randomized smoothing (Bojchevski et al., ; Carmon et al., ), which involves injecting noise into the inputs at various stages and subsequently utilizing majority voting to determine the final prediction. Note that randomized smoothing has actually been initially borrowed from the optimization community (Duchi et al., ). Despite its popularity, randomized smoothing exhibits several limitations, including suffering from the shrinking phenomenon where decision regions shrink or drift as the variance of the smoothing distribution increases (Mohapatra et al., ). Other works also identified that the smoothed classifier is more-constant than the original model, i.e., it forces the classification to remain invariant over a large input space, resulting a huge drop of the accuracy (Anderson & Sojoudi, ; Krishnan et al., ; Wang et al., ).

## 3 Preliminaries

Before continuing with our contribution, we begin by introducing notation and some fundamental concepts.

### 3.1 Graph Neural Networks

Let $G=(V,E)$ be a graph where $V$ is the set of vertices and $E$ is the set of edges.
We will denote by $n=|V|$ and $m=|E|$ the number of vertices and number of edges, respectively.
Let $\mathcal{N}(v)$ denote the set of neighbors of a node $v\in V$, i.e.,  $\mathcal{N}(v)=\{u\colon(v,u)\in E\}$.
The degree of a node is equal to its number of neighbors, i.e., equal to $|\mathcal{N}(v)|$ for a node $v\in V$.
A graph is commonly represented by its adjacency matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ where the $(i,j)$-th element of this matrix is equal to the weight of the edge between the $i$-th and $j$-th node of the graph and a weight of 0 0 in case the edge does not exist.
In some settings, the nodes of a graph might be annotated with feature vectors.
We use $\mathbf{X}\in\mathbb{R}^{n\times K}$ to denote the node features where $K$ is the feature dimensionality.

A GNN model consists of a series of neighborhood aggregation layers which use the graph structure and the nodes’ feature vectors from the previous layer to generate new representations for the nodes.
Specifically, GNNs update nodes’ feature vectors by aggregating local neighborhood information.
Suppose we have a GNN model that contains $T$ neighborhood aggregation layers.
Let also $\mathbf{h}_{v}^{(0)}$ denote the initial feature vector of node $v$, i.e., the row of matrix $\mathbf{X}$ that corresponds to node $v$.
At each iteration ($t>0$), the hidden state $\mathbf{h}_{v}^{(t)}$ of a node $v$ is updated as follows:

$$ $\displaystyle\mathbf{a}_{v}^{(t)}=\texttt{AGGREGATE}^{(t)}\Big{(}\big{\{} \mathbf{h}_{u}^{(t-1)}\colon u\in\mathcal{N}(v)\big{\}}\Big{)},$ $\displaystyle\mathbf{h}_{v}^{(t)}=\texttt{COMBINE}^{(t)}\Big{(}\mathbf{h}_{v}^ {(t-1)},\mathbf{a}_{v}^{(t)}\Big{)},$ $$

where $\texttt{AGGREGATE}(\cdot)$ is a permutation invariant function that maps the feature vectors of the neighbors of a node $v$ to an aggregated vector.
This aggregated vector is passed along with the previous representation of $v$, i.e., $\mathbf{h}_{v}^{(t-1)}$, to the $\texttt{COMBINE}(\cdot)$ function which combines those two vectors and produces the new representation of $v$. After $T$ iterations of neighborhood aggregation, to produce a graph-level representation, GNNs apply a permutation invariant readout function, e.g., the sum operator, to nodes feature as follows:

$$ $\mathbf{h}_{G}=\texttt{READOUT}\Big{(}\big{\{}\mathbf{h}_{v}^{(T)}\colon v\in V \big{\}}\Big{)}.$ (1) $$

### 3.2 Conditioned Random Fields

A probabilistic graphical model (PGM) is a graph framework that compactly models the joint probability distributions $P$ and dependence relations over a set of random variables $\tilde{Y}=\{\tilde{Y}_{1},\ldots,\tilde{Y}_{m}\}$ represented in a graph. The two most common classes of PGMs are Bayesian networks (BNs) and Markov Random Fields (MRFs) (Heckerman, ; Clifford, ). The core of the BN representation is a directed acyclic graph (DAG). As the name suggests, DAG can be represented by a graph with no loopy structure where its vertices serve as random variables and directed edges serve as dependency relationships between them. The direction of the edges determines the influence of one random variable on another. Similarly, MRFs are also used to describe dependencies between random variables in a graph. However, MRFs use undirected instead of directed edges and permit cycles. An important assumption of MRFs is the Markov property, i.e., for each pair of nodes $(a,b)$ such as $e_{ab}\notin E^{\text{{MRF}}}$, the node $a$ is independent of the node $b$ conditioned on $v$’s neighbors:

$$ $\forall a\in V^{\text{{MRF}}},~{}~{}\tilde{Y}_{a}\perp\tilde{Y}_{V\setminus \mathcal{N}(a)}|\mathcal{N}(a).$ $$

An important special case of MRFs arises when they are applied to model a conditional probability distribution $P(\tilde{Y}|Y,V^{\text{{MRF}}},E^{\text{{MRF}}})$, where $Y=\{Y_{1},\ldots,Y_{m}\}$ are additional observed node features. These types of graphs are called Conditioned Random Fields (CRFs) (Sutton et al., ; Wallach et al., ). Formally, a CRF is Markov network over random variables $\mathcal{Y}$ and observation $\mathcal{X}$, the conditional distribution is defined as follows:

$$ $P(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}})=\frac{1}{Z(Y,V^{\text{{CRF}}} ,E^{\text{{CRF}}})}\exp\left\{-\sum_{a\in V^{\text{{CRF}}}}\phi_{a}(\tilde{Y}_ {a})-\sum_{(a,b)\in E^{\text{{CRF}}}}\phi_{ab}(\tilde{Y}_{a},\tilde{Y}_{b}) \right\},$ $$

where $Z(\mathcal{X},E)$ is the partition function, and $\phi_{v}(Y_{v},X,E)$ and $\phi_{vu}(Y_{v},Y_{u},X,E)$ are potential functions contributed by each node $v$ and each edge $(u,v)$ and usually defined as simple linear functions or learned by simple regression on the features (e.g., logistic regression).

## 4 RobustCRF: A CRF-based Robustness Enhancement Model

Figure: Figure 1: Illustration of RobustCRF. We use input graphs manifold to generate the structure of the CRF, i.e., $V^{\text{{CRF}}},E^{\text{{CRF}}}$. We use the GNN’s predictions to generate the observables $\left\{Y_{a}~{}~{}~{}|~{}~{}a\in V^{\text{{CRF}}}\right\}$, we then run the CRF inference to generate the new GNN’s predictions $\{\tilde{Y}_{a}~{}~{}~{}|~{}~{}a\in V^{\text{{CRF}}}\}$.
Refer to caption: x1.png

### 4.1 Adversarial Attacks

Let us consider our graph space ($\mathcal{G},\lVert\cdot\rVert_{\mathcal{G}}$), feature space ($\mathcal{X}$, $\lVert\cdot\rVert_{\mathcal{X}}$), and the label space ($\mathcal{Y},\lVert\cdot\rVert_{\mathcal{Y}}$) to be measurable spaces. Given a GNN $f:(\mathcal{G},\mathcal{X})\rightarrow\mathcal{Y}$, as introduced in Section 3.1, an input data point $G\in\mathcal{G}$ and its corresponding prediction $y\in\mathcal{Y}$ where $f(G)=y$, the goal of an adversarial attack is to produce a perturbed graph $\tilde{G}$ slightly different from the original graph with its predicted class being different from the predicted class of $G$. This could be formulated as finding a $\tilde{G}$ with $f(\tilde{G})=\tilde{y}\neq y$ subject to $d(G,\tilde{G})<\epsilon$, with $d$ being some distance function between the original and perturbed graphs. This could be a distance taking into account both the graph structure, in terms of the adjacency matrix, and the corresponding node features, defined as,

$$ $d_{\alpha,\beta}([A,X],[\tilde{A},\tilde{X}])=\min_{P\in\Pi}\{\alpha\lVert A-P \tilde{A}P^{\top}\rVert_{2}+\beta\lVert X-P\tilde{X}\rVert_{2}\},$ $$

The distance $d_{\alpha,\beta}$ has already been used in the literature (Abbahaddou et al., ). This distance is advantageous because it incorporates both the graph structure and the node features. The matrix $P$ corresponds to a permutation matrix used to order nodes from different graphs. By using Optimal Transport, we find the minimum distance over the set of permutation matrices, which corresponds to the optimal matching between nodes in the two graphs.

### 4.2 Motivation

There are different theoretical definitions of robustness (Cheng et al., ; Weng et al., ), but they all rely on one assumption: if two inputs are adjacent in the input space, their predictions should be adjacent in the output space. For example, most existing approaches measure the robustness of a neural network via the Attack Success Rate (ASR), the percentage of attack attempts that produce successful adversarial examples, which implies that close input data should be predicted similarly (Wu et al., ; Goodfellow et al., ). Additionally, there are also works that use the neural networks distortion as a robustness metric (Cheng et al., ; Weng et al., ; Carlini & Wagner, ). Intuitively, large distortion implies potentially poor adversarial robustness since a small perturbation applied to these inputs will lead to significant changes in the output. Consequently, most robustness metrics measure the extent to which the network’s output is changed when perturbing the input data, indicating the network’s vulnerability to adversarial attacks, which is directly equivalent to our assumption. To respect this assumption, we construct a CRF, where the node set $V^{\text{{CRF}}}$ represents the set of possible GNN inputs $\mathcal{G}\times\mathcal{X}$, while the CRF edge set $E^{\text{{CRF}}}$ represents the set of pair inputs $([G,X],[\tilde{G},\tilde{X}])$ such that $[\tilde{G},\tilde{X}]$ belongs to the ball $\mathcal{B}$ of radius $r>0$ surrounding $[G,X]$, as follows:

$$ $\mathcal{B}\left(\left[G,X\right],r\right)=\left\{\left[\tilde{G},\tilde{X} \right]:d^{\alpha,\beta}([G,X],[\tilde{G},\tilde{X}])\leq r\right\}.$ $$

Our method examines how the model performs more generally within a defined neighborhood, instead of considering the model’s behavior only under individual adversarial attacks. This perspective leans towards a concept of average robustness, expanding on the conventional worst-case based adversarial robustness that is often emphasized in adversarial studies (Abbahaddou et al., ). A similar average robustness concept was studied and showed to be appropriate for computer vision (Rice et al., ).

### 4.3 Modeling the Robustness Constraint in a CRF

Let $Y_{a}$ be the output prediction of the trained GNN $f$ on the input $a=[G,X]\in V^{\text{{CRF}}}$. The main goal of using a CRF is to update the predictions $Y=\{Y_{a}|a\in V^{\text{{CRF}}}\}$ into new predictions $\tilde{Y}=\{\tilde{Y}_{a}|a\in V^{CRF}\}$ that respect the robustness assumption. To do so, we model the relation between the two predictions $Y$ and $\tilde{Y}$ using a CRF, maximizing the following conditional probability:

$$ $P(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}})=\frac{1}{Z}\exp\bigg{\{}-\sum _{a\in V^{\text{{CRF}}}}\phi_{a}(\tilde{Y}_{a},Y_{a})-\sum_{b\text{ s.t. }(a,b )\in E^{\text{{CRF}}}}\phi_{ab}(\tilde{Y}_{a},\tilde{Y}_{b})\bigg{\}},$ (2) $$

where $Z$ is the partition function, $\phi_{a}(\tilde{Y}_{a},Y_{a})$ and $\phi_{ab}(\tilde{Y}_{a},\tilde{Y}_{b})$ are potential functions contributed by each CRF node $a$ and each CRF edge $(a,b)$ and usually defined as simple linear functions or learned by simple regression on the features (e.g., logistic regression). The potential functions $\phi_{a}$ and $\phi_{ab}$ can be either fixed or trainable to optimize a specific objective. In this paper, we define the potential functions as follows:

$$ $\centering\left\{\begin{array}[]{ll}\phi_{a}(\tilde{Y}_{a},Y_{a})=\sigma\lVert \tilde{Y}_{a}-Y_{a}\rVert_{2}^{2},\\ \phi_{ab}(\tilde{Y}_{a},\tilde{Y}_{b})=(1-\sigma)g_{ab}\lVert\tilde{Y}_{a}- \tilde{Y}_{b}\rVert_{2}^{2},\end{array}\right.\@add@centering$ $$

where $g_{ab}$ denotes the similarity between two inputs $a=[G,X]$ and $b=[\tilde{G},\tilde{X}]$.
Representing GNN inputs in the CRF can be seen as a constraint problem to enhance the robustness: Finding a new prediction $\tilde{Y}_{a}$ that meets the demands of the
robustness objective, and at the same time stays as close as possible to the original prediction of the GNN, $Y_{a}=f(a)$ where $a=[G,X]$ is a GNN input. The parameter $\sigma$ is used to adjust the importance of the two potential functions. In Figure 1, we illustrate the main idea of the proposed RobustCRF model.

Now that we have defined the CRF and its potential functions, generating the new prediction $\{\tilde{Y}_{p}|p\in V^{\text{{CRF}}}\}$ is intractable for two reasons. First, the partition function $Z$ is usually intractable. Second, the CRF distribution $P$ represents a potentially infinite collection of CRF edges $E^{\text{{CRF}}}$. We need, therefore, to derive a tractable algorithm to generate the smoothed prediction $\tilde{Y}$. In what follows, we show how to overcome these two challenges.

### 4.4 Mean Field Approximation

We aim to derive the most likely $\tilde{Y}$ from the initial distribution $P$ defined in Eq. 2, as:

$$ $\tilde{Y}^{*}=\operatorname*{arg\,max}P(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{ {CRF}}}).$ (3) $$

Since the inference is intractable, we used a Variational Inference method where we propose a family of densities $\mathcal{D}$ and find a member $Q^{*}\in\mathcal{D}$ which is close to the posterior $P(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}})$. Thus, we approximate the initial task in Equation 3 with a new objective:

$$ $\centering\left\{\begin{array}[]{ll}\tilde{Y}^{*}=\operatorname*{arg\,max}_{ \tilde{Y}}Q^{*}(\tilde{Y}),\\ Q^{*}=\operatorname*{arg\,min}_{Q\in\mathcal{D}}\mathcal{KL}\left(Q|P\right). \end{array}\right.\@add@centering$ (4) $$

The goal is to find the distribution $Q^{*}$ within the family $\mathcal{D}$, which is the closest to the initial distribution $P$. In this work, we used the mean-field approximation (Blei et al., ) that enforces full independence among all latent variables. Mean field approximation is a powerful technique for simplifying complex probabilistic models, widely used in various fields of machine learning and statistics (Andrews & Baguley, ; Blei et al., ). Thus, the variational distribution over the latent variables factorizes as:

$$ $\forall Q\in\mathcal{D},~{}~{}Q(\tilde{Y})=\prod_{a\in V^{\text{{CRF}}}}Q_{a}( \tilde{Y}_{a}).$ (5) $$

The exact formula of the optimal surrogate distribution $Q$ can be obtained using Lemma 4.1. We will use Coordinate Ascent Inference (CAI), iteratively optimizing each variational distribution and holding the others fixed.

###### Lemma 4.1 .

By solving the system of Eq. 4, we can get the optimal distribution $Q^{*}$ as follows:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}Q_{a}(\tilde{Y}_{a})\propto\exp\left\{ \mathbb{E}_{-a}\left[\log P\left(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}} \right)\right]\right\}.$ (6) $$

The proof of Lemma 4.1 is provided in Appendix B. CAI algorithm iteratively updates each $Q_{a}(\tilde{Y}_{a})$. The ELBO converges to a local minimum. Using Equations 2 and 6, we get the optimal surrogate distribution as follows:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}Q(\tilde{Y}_{a})\propto\exp\Bigg{\{}\sigma \lVert\tilde{Y}_{a}-Y_{a}\rVert_{2}^{2}+(1-\sigma)\sum_{b\text{ s.t. }(a,b)\in E ^{\text{{CRF}}}}g_{ab}\lVert\tilde{Y}_{a}-\tilde{Y}_{b}\rVert_{2}^{2}\Bigg{\}}.$ (7) $$

Thus, for each GNN input $a\in V^{\text{{CRF}}}$, $Q_{a}(\tilde{Y}_{a})$ is a Gaussian distribution that reaches the highest probability at its expectation:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}\operatorname*{arg\,max}Q_{a}=\frac{\sigma Y _{a}+(1-\sigma)\sum_{b\text{ s.t. }(a,b)\in E^{\text{{CRF}}}}g_{ab}\tilde{Y}_{ b}}{\sigma+(1-\sigma)\sum_{b\text{ s.t. }(a,b)\in E^{\text{{CRF}}}}g_{ab}}.$ (8) $$

Using the CAI algorithm, we can thus utilize the following update rule:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}\tilde{Y}_{a}^{k+1}=\frac{\sigma Y_{a}+(1- \sigma)\sum_{b\text{ s.t. }(a,b)\in E^{\text{{CRF}}}}g_{ab}\tilde{Y}_{b}^{k}}{ \sigma+(1-\sigma)\sum_{b\text{ s.t. }(a,b)\in E^{\text{{CRF}}}}g_{ab}}.$ (9) $$

###### Lemma 4.1 .

### 4.5 Reducing the Size of the CRF

The number of possible inputs is usually very large for discrete data and infinite for continuous data. This could make the inference intractable due to the potential large size of $E^{\text{{CRF}}}$. Therefore, instead of considering all the possible CRF neighbors of an input $a$, i.e., all inputs $b\in V^{\text{{CRF}}}$ such that $d^{\alpha,\beta}(a,b)\leq r$, we can consider only a subset of $L$ neighbors by randomly sampling from the CRF neighbors of $p$. The update rule in Eq. 9 becomes:

$$ $\tilde{Y}_{a}^{k+1}=\frac{\sigma Y_{a}+(1-\sigma)\sum_{b\in\mathcal{U}^{L}(a)} g_{ab}\tilde{Y}_{b}^{k}}{\sigma+(1-\sigma)\sum_{b\in\mathcal{U}^{L}(a)}g_{ab}},$ (10) $$

where $\mathcal{U}^{L}(a)$ denotes a set of $L$ randomly sampled CRF neighbors of a graph $[G,X]$. Below, we elaborate on how to uniformly sample a neighbor graph $b$ surrounding $a$ in the structural distances, i.e., $(\alpha,\beta)=(1,0)$.

Let $\mathbb{A}=\{0,1\}^{n^{2}}$ be the adjacency matrix space, where $n$ is the number of nodes. $\mathbb{A}$ is a finite-dimensional compact normed vector space, so all the norms are equivalent. Thus, all the induced $\{L^{p}\}_{p}$ distances are equivalent. Without loss of generality, we can consider the $L^{1}$ loss, which exactly corresponds to the Hamming distance:

$$ $d^{1}([G,X],[\tilde{G},\tilde{X}])=\sum_{i\leq j}|\mathbf{A}^{i,j}-\tilde{ \mathbf{A}}^{i,j}|,$ $$

where $\mathbf{A},\tilde{\mathbf{A}}$ corresponds to the adjacency matrix of the graphs $G,\tilde{G}$ respectively.
Since we consider undirected graphs, the Hamming distance takes only discrete values in $\{0,\ldots,\frac{n(n+1)}{2}\}$. In Lemma 4.2, we provide a lower bound for the size of CRF neighbors $\mathcal{N}^{\text{{CRF}}}(a)=\{b\in V^{\text{{CRF}}}|(a,b)\in E^{\text{{CRF}}}\}$ for any GNN input $a\in V^{\text{{CRF}}}$. In Appendix A, we present the proof of Lemma 4.2 and we empirically analyze the asymptotic behavior of this lower bound, motivating thus the need for sampling strategies to reduce the size of the CRF.

###### Lemma 4.2 .

For any integer $r$ in $\{0,\ldots,\frac{n(n+1)}{2}\}$, the number of CRF neighboors $\left|\mathcal{N}^{\text{{CRF}}}(a)\right|$ for any $a\in V^{\text{{CRF}}}$, i.e., the set of graphs $[\tilde{G},\tilde{X}]$ with a Hamming distance smaller or equal than $r$, have the following lower bound:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}\frac{1}{\sqrt{4n(n+1)\epsilon(1-\epsilon) }}.2^{H(\epsilon)n(n+1)/2}\leq\left|\mathcal{N}^{\text{{CRF}}}(a)\right|,$ (11) $$

where $0\leq\epsilon=\frac{2r}{n(n+1)}\leq 1$ and $H(\cdot)$ is the binary entropy function:

$$ $H(\epsilon)=-\epsilon\log_{2}(\epsilon)-(1-\epsilon)\log_{2}(1-\epsilon).$ $$

To sample from $\mathcal{B}\left(\left[G,X\right],r\right)$, we use a Stratified Sampling strategy. First, we sample a distance value $d$ from $\{0,1,\ldots,n^{2}\}$. To do so, we partition $\mathcal{B}\left(\left[G,X\right],r\right)$ with respect to their distance to the original adjacency matrix $A$ :

$$ $\left\{\begin{array}[]{l}S_{d}\left(A\right)=\{A\in\mathbb{A}|d^{1}(A,\tilde{A })=d\},\\ \mathcal{B}([G,X],r)=\bigcup_{d\leq r}S_{d},\\ \forall d\neq d^{\prime},S_{d}\cap S_{d^{\prime}}=\varnothing.\end{array}\right.$ $$

To each distance value $d$, we assign the portion of graphs covered by $S_{d}\left(A\right)$ in $\mathbb{A}$ as:

$$ $\forall d\in\{0,\ldots,r\},p(d)=\binom{r}{d}\frac{1}{R}~{}~{}~{}~{}~{}~{}~{}~{ }\text{where}~{}~{}~{}~{}~{}~{}~{}~{}R=\sum_{d=0}^{r}\binom{r}{d}=2^{r}.$ $$

Second, we uniformly select $d$ positions in the adjacency matrix to be modified and change the element of the $d$ positions by changing the value $A^{i,j}$ to $1-A^{i,j}$. To uniformly sample neighbor graphs when dealing with features-based distances for graphs, we used the sampling strategy of Abbahaddou et al. ().

Our RobustCRF is an attack-independent and model-agnostic robustness approach based on uniform sampling without requiring any training. Therefore, it can be used to enhance GNNs’ robustness against unknown attack distributions. In Section 5, we will experimentally validate this theoretical insight for the node classification task and demonstrate that RobustCRF has a good trade-off between robustness and clean accuracy, i.e., the model’s initial performance on clean un-attacked dataset. Moreover, the approach of our work and these baselines are fundamentally different, since our RobustCRF is post-hoc, we can also use the baselines in combination with our proposed RoustCRF approach to draw even more robust predictions. We report the results of this experiment in Table 2.

###### Remark 4.3 .

If we set the value of $\sigma$ to 0 0, the number of iterations to $1$, and all the similarity coefficients to $1$, this scheme corresponds to the standard randomized smoothing with the uniform distribution. In this setting, we do not take into account the original classification task, which causes a huge drop in the clean accuracy. Therefore, RobustCRF is a generalization of the randomized smoothing that gives a better trade-off between accuracy and robustness.

###### Lemma 4.2 .

###### Remark 4.3 .

## 5 Experimental Setup

In this section, we shift from theoretical exploration to practical validation by evaluating the effectiveness of RobustCRF on real-world benchmark datasets. We begin by detailing the experimental setup employed, followed by a thorough presentation and analysis of the results. Our primary experimental objective is to assess how well the proposed method enhances the robustness of a trained GNN.

### 5.1 Experimental Setup

**Table 1: Attacked classification accuracy ($\pm$ standard deviation) of the GCN, the baselines and the proposed RobustCRF on different benchmark node classification datasets after the features based attack application. ① test accuracy on the original features, ② test accuracy on the perturbed features.**
|  | Attack | Model | Cora | CiteSeer | PubMed | CS | Texas |
| --- | --- | --- | --- | --- | --- | --- | --- |
| ① | Clean | GCN | 80.66 (0.41) | 70.37 (0.53) | 78.16 (0.67) | 89.15 (2.06) | 51.35 (18.53) |
| RGCN | 77.64 (0.52) | 69.88 (0.47) | 75.58 (0.65) | 92.05 (0.72) | 51.62 (13.91) |  |  |
| GCORN | 77.83 (2.33) | 71.68 (1.54) | 76.03 (1.29) | 88.94 (1.86) | 59.73 (4.90) |  |  |
| NoisyGCN | 81.04 (0.74) | 70.36 (0.79) | 78.13 (0.53) | 91.47 (0.92) | 48.91 (20.02) |  |  |
|  | RobustCRF | 80.63 (0.38) | 70.30 (0.43) | 78.20 (0.24) | 88.16 (3.41) | 61.08 (5.01) |  |
| ② | Random<br>($\psi=0.5$) | GCN | 77.88 (0.90) | 66.65 (1.00) | 73.60 (0.75) | 88.92 (2.04) | 46.49 (15.75) |
| RGCN | 67.61 (0.80) | 59.76 (1.01) | 61.93 (1.18) | 90.74 (1.08) | 43.51 (10.22) |  |  |
| GCORN | 76.28 (1.96) | 67.82 (2.18) | 72.35 (1.43) | 88.31 (2.10) | 60.00 (4.95) |  |  |
| NoisyGCN | 78.59 (1.09) | 66.83 (0.98) | 73.60 (0.58) | 91.04 (0.85) | 48.91 (19.29) |  |  |
| RobustCRF | 78.28 (0.68) | 68.23 (0.57) | 74.37 (0.47) | 88.30 (3.25) | 57.30 (4.32) |  |  |
| PGD | GCN | 76.38 (0.72) | 67.57 (0.77) | 74.86 (0.65) | 86.90 (1.91) | 52.97 (19.19) |  |
| RGCN | 68.45 (0.97) | 64.63 (0.82) | 73.35 (0.81) | 90.76 (0.68) | 60.81 (10.27) |  |  |
| GCORN | 73.32 (2.19) | 69.05 (2.50) | 74.49 (1.13) | 87.07 (2.96) | 59.73 (4.90) |  |  |
| NoisyGCN | 76.29 (1.69) | 67.09 (1.50) | 75.04 (0.53) | 88.79 (0.85) | 52.97 (19.11) |  |  |
| RobustCRF | 76.41 (0.70) | 67.90 (0.63) | 75.17 (0.91) | 85.60 (2.75) | 62.16 (4.83) |  |  |

**Table 2: Attacked classification accuracy ($\pm$ standard deviation) of the baselines when combined with the proposed RobustCRF on different benchmark node classification datasets after the features based attack application.**
| Attack | Model | Cora | CiteSeer | PubMed | Texas |
| --- | --- | --- | --- | --- | --- |
| Clean | RGCN | 77.64 (0.52) | 69.88 (0.47) | 75.58 (0.65) | 51.62 (13.91) |
| RGCN w/ RobustCRF | 77.70 (0.46) | 69.84 (0.39) | 75.50 (0.60) | 52.16 (14.20) |  |
| GCORN | 77.83 (2.33) | 71.68 (1.54) | 76.03 (1.29) | 59.73 (4.90) |  |
| GCORN w/ RobustCRF | 78.50 (1.17) | 71.72 (1.46) | 76.13 (1.08) | 59.77 (4.68) |  |
| NoisyGCN | 81.04 (0.74) | 70.36 (0.79) | 78.13 (0.53) | 48.91 (20.02) |  |
| NoisyGCN w/ RobustCRF | 81.07 (0.70) | 70.20 (0.85) | 78.90 (0.46) | 49.18 (19.59) |  |
| Random<br>($\psi=0.5$) | RGCN | 67.61 (0.80) | 59.76 (1.01) | 61.93 (1.18) | 43.51 (10.22) |
| RGCN w/ RobustCRF | 69.08 (0.73) | 60.04 (1.01) | 63.05 (0.88) | 45.05 (9.99) |  |
| GCORN | 76.28 (1.96) | 67.82 (2.18) | 72.35 (1.43) | 60.00 (4.95) |  |
| GCORN w/ RobustCRF | 77.21 (1.17) | 68.94 (3.00) | 72.29 (1.29) | 59.18 (3.71) |  |
| NoisyGCN | 78.59 (1.09) | 66.83 (0.98) | 73.60 (0.58) | 48.91 (19.29) |  |
| NoisyGCN w/ RobustCRF | 81.07 (0.99) | 67.04 (1.38) | 74.18 (0.98) | 45.94 (14.54) |  |
| PGD | RGCN | 68.45 (0.97) | 64.63 (0.82) | 73.35 (0.81) | 60.81 (10.27) |
| RGCN w/ RobustCRF | 68.46 (0.93) | 64.59 (0.84) | 73.47 (0.72) | 58.10 (11.09) |  |
| GCORN | 73.32 (2.19) | 69.05 (2.50) | 74.49 (1.13) | 59.73 (4.90) |  |
| GCORN w/ RobustCRF | 73.65 (1.55) | 69.09 (2.57) | 74.59 (0.90) | 60.27 (4.68) |  |
| NoisyGCN | 76.29 (1.69) | 67.09 (1.50) | 75.04 (0.53) | 52.97 (19.11) |  |
| NoisyGCN w/ RobustCRF | 76.48 (1.65) | 67.21 (1.35) | 75.39 (0.45) | 53.51 (19.07) |  |

Datasets. For our experiments, we focus on node classification within the general perspective of node representation learning. We use the citation networks Cora, CoraML, CiteSeer, and PubMed (Sen et al., ). We additionally consider the co-authorship network CS (Shchur et al., ) and the blog and citation graph PolBlogs (Adamic & Glance, ), and the non-homophilous dataset Texas (Lim et al., ). More details and statistics about the datasets can be found in Table 4. For the CS dataset, we randomly selected 20 nodes from each class to form the training set and 500/1000 nodes for the validation and test sets (Yang et al., ). For all the remaining datasets, we adhere to the public train/valid/test splits provided by the datasets.

Implementation Details. We used the PyTorch Geometric (PyG) open-source library, licensed under MIT (Fey & Lenssen, ). Additionally, for adversarial attacks in this study, we used the DeepRobust package (^1^11https://github.com/DSE-MSU/DeepRobust). The experiments were conducted on an RTX A6000 GPU. For the structure-based CRF, we leveraged the sampling strategy detailed in Section 4. The set of hyperparameters for each dataset can be found in Appendix C. We compute the similarity $g_{ab}$ between two inputs $a=[G,X]$ and $b=[\tilde{G},\tilde{X}]$ using the Cosine Similarity for the features based attacks, namely $\text{CosSim}(X,\tilde{X})$, while for the structural attacks, we use the prior distribution $g_{ab}=\binom{r}{d}\frac{1}{2^{r}}$, where $d$ is the value of the Hamming distance between the original graph $a$ and its sampled neighbor $b$. We note that our code is provided in the supplementary materials and will be made public upon publication.

Attacks. We evaluate RobustCRF via the Attack Success Rate (ASR), the percentage of attack attempts that produce successful adversarial examples. For the feature-based attacks, we consider two main types: (1) we first consider a random attack which consists of injecting Gaussian noise $\mathcal{N}(0,\mathbf{I})$ to the features with a scaling parameter $\psi=0.5$; (2) we have additionally used the white-box Proximal Gradient Descent (Xu et al., ), which is a gradient-based approach to the adversarial optimization task for which we set the perturbation rate to 15%. For the structural perturbations, we evaluated RobustCRF using the “Dice” (Zügner & Günnemann, ) adversarial attack in a black-box setting, where we consider a surrogate model. For this setting, we used an attack budget of $10\%$ (the ratio of perturbed edges).

Baseline Models. When dealing with feature-based attacks, we compare RobustCRF with the vanilla GCN (Kipf & Welling, ), the feature-based defense method RobustGCN (RGCN) (Zhu et al., ), NoisyGNN (Ennadir et al., ), and GCORN (Abbahaddou et al., ). For the structural attacks, we included RobustGCN (RGCN) and other baselines such as GNN-Jaccard (Wu et al., ), GNN-SVD (Entezari et al., ), GNNGuard (Zhang & Zitnik, ) and GOOD-AT (Li et al., ). For all the models, we used the same number of layers $T=2$, and with a hidden dimension of $16$. The models were trained using the cross-entropy loss function with the Adam optimizer (Diederik, ), the number of epochs $N_{\text{{epochs}}}=300$, and learning rate $0.01$ were kept similar for the different approaches across all experiments. To reduce the impact of random initialization, we repeated each experiment 10 times and used the train/validation/test splits provided with the datasets when evaluating against the feature-based attacks, c.f. Table 1. When evaluating against the structural attacks, c.f. Table 3, we used the split strategy of (Zügner et al., ), i.e., we select the largest connected components of the graph and use 10%/10%/80% nodes for training/validation/test.

### 5.2 Experimental Results

Worst-Case Adversarial Evaluation. We now analyze the results of RobustCRF for the node classification task. We additionally compared our approach with baselines on the large dataset OGBN-Arxiv. We report all the results for the feature and structure-based adversarial attacks, respectively, in Tables 1, 3, and 8. The results demonstrate that the performance of the GCN is significantly impacted when subject to adversarial attacks of varying strategies. In contrast, the proposed RobustCRF approach shows a substantial improvement in defense against these attacks compared to other baseline models. Furthermore, in contrast to some other benchmarks, RobustCRF offers an optimal balance between robustness and clean accuracy. Specifically, the proposed approach effectively enhances the robustness against adversarial attacks while maintaining high accuracy on non-attacked, clean datasets. This latter point makes RobustCRF particularly advantageous, as it enhances the model’s defenses without compromising its performance on downstream tasks.

In Table 2, we report the performance of the baselines when combined with RobustCRF. As noticed, for most of the cases, we further enhace the robustness of the baselines when using RobustCRF.

**Table 3: Attacked classification accuracy ($\pm$ standard deviation) of the GCN, the baselines and the proposed RobustCRF on different benchmark node classification datasets after the structural attack application. ① test accuracy on the original structure, ② test accuracy on the perturbed structure.**
|  | Attack | Model | Cora | CoraML | CiteSeer | PolBlogs |
| --- | --- | --- | --- | --- | --- | --- |
| ① | Clean | GCN | 83.42 (1.00) | 85.60 (0.40) | 70.66 (1.18) | 95.16 (0.64) |
| RGCN | 83.46 (0.53) | 85.61 (0.61) | 72.18 (0.97) | 95.32 (0.76) |  |  |
| GCNGuard | 83.72 (0.67) | 85.54 (0.42) | 73.18 (2.36) | 95.07 (0.51) |  |  |
| GCNSVD | 77.96 (0.61) | 81.29 (0.51) | 68.16 (1.15) | 93.80 (0.73) |  |  |
|  | GCNJaccard | 82.20 (0.67) | 84.85 (0.39) | 73.57 (1.21) | 51.81 (1.49) |  |
|  |  | GOOD-AT | 83.43 (0.11) | 84.87 (0.15) | 72.80 (0.45) | 94.85 (0.52) |
|  |  | RobustCRF | 83.52 (0.04) | 85.69 (0.09) | 72.16 (0.30) | 95.40 (0.24) |
| ② | Dice | GCN | 81.87 (0.73) | 83.34 (0.60) | 71.76 (1.06) | 87.14 (0.86) |
| RGCN | 81.27 (0.71) | 83.89 (0.51) | 69.45 (0.92) | 87.35 (0.76) |  |  |
| GCNGuard | 81.63 (0.74) | 83.72 (0.49) | 71.87 (1.19) | 86.98 (1.26) |  |  |
| GCNSVD | 75.62 (0.61) | 79.13 (1.01) | 66.10 (1.29) | 88.50 (0.97) |  |  |
|  | GCNJaccard | 80.67 (0.66) | 82.88 (0.58) | 72.32 (1.10) | 51.81 (1.49) |  |
|  |  | GOOD-AT | 82.21 (0.56) | 84.16 (0.36) | 71.43 (0.28) | 90.93(0.38) |
|  |  | RobustCRF | 82.44 (0.41) | 84.71 (0.32) | 71.48 (0.15) | 90.46 (0.25) |

**Table 4: Statistics of the node classification datasets used in our experiments.**
| Dataset | #Features | #Nodes | #Edges | #Classes |
| --- | --- | --- | --- | --- |
| Cora | 1,433 | 2,708 | 5,208 | 7 |
| CoraML | 300 | 2,995 | 8,226 | 7 |
| CiteSeer | 3,703 | 3,327 | 4,552 | 6 |
| PubMed | 500 | 19,717 | 44,338 | 3 |
| CS | 6,805 | 18,333 | 81,894 | 15 |
| PolBlogs | - | 1,490 | 19,025 | 2 |
| Texas | 1,703 | 183 | 309 | 5 |
| Ogbn-arxiv | 128 | 31,971 | 71,669 | 40 |

Time and Complexity. We study the effect of the number of iterations $K$ and the number of samples $L$ on the inference time. In Appendix D, we report the average time needed to compute the RobustCRF inference. The results validate the intuitive fact that the inference time grows by increasing $K$ and $L$. We recall that we need to use the model $L^{K}$ times in the CRF inference.

## 6 Conclusion

This work addresses the problem of adversarial defense at the inference stage. We propose a model-agnostic, post-hoc approach using Conditional Random Fields (CRFs) to enhance the adversarial robustness of pre-trained models. Our method, RobustCRF, operates without requiring knowledge of the underlying model and necessitates no post-training or architectural modifications. Extensive experiments on multiple datasets demonstrate RobustCRF’s effectiveness in improving the robustness of Graph Neural Networks (GNNs) against both structural and node-feature-based adversarial attacks, while maintaining a balance between attacked and clean accuracy, typically preserving their performance on clean, un-attacked datasets, which makes RobustCRF the best trade-off between robustness and clean accuracy.

## Appendix A Proof of Lemma 4.1

Lemma 4.1
By solving the system of equations in equation 4, we can get the optimal distribution $Q^{*}$ as follows:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}Q(\tilde{Y}_{a})\propto\exp\left\{\mathbb{ E}_{-a}\left[log~{}P\left(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}}\right) \right]\right\}.$ $$

###### Proof.

The $\mathcal{KL}$-divergence includes the true posterior $P(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}})$ which is exactly the unknown value. We can rewrite the $\mathcal{KL}$-divergence as:

$$ $\displaystyle\mathcal{KL}\left(Q|P\right)$ $\displaystyle=\int Q(\tilde{Y})\log\frac{Q(\tilde{Y})}{P(\tilde{Y}|Y,V^{\text{ {CRF}}},E^{\text{{CRF}}})}d\tilde{Y}$ $\displaystyle=\int Q(\tilde{Y})\log\frac{Q(\tilde{Y})P(Y,V^{\text{{CRF}}},E^{ \text{{CRF}}})}{P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})}d\tilde{Y}$ $\displaystyle=\int Q(\tilde{Y})\left(\log~{}P(Y,V^{\text{{CRF}}},E^{\text{{CRF }}})+\log\frac{Q(\tilde{Y})}{P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})} \right)d\tilde{Y}$ $\displaystyle=\log~{}P(Y,V^{\text{{CRF}}},E^{\text{{CRF}}})\int Q(\tilde{Y})d \tilde{Y}-\int Q(\tilde{Y})\log\frac{P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{ CRF}}})}{Q(\tilde{Y})}d\tilde{Y}.$ $$

Since $\int Q(\tilde{Y})d\tilde{Y}=1$, we conclude that:

$$ $\mathcal{KL}\left(Q|P\right)=\log~{}P(Y,V^{\text{{CRF}}},E^{\text{{CRF}}})- \int Q(\tilde{Y})\log\frac{P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})}{Q (\tilde{Y})}d\tilde{Y}.$ $$

We are minimizing the $\mathcal{KL}-$divergence over $Q$, therefore the term $log~{}P(Y,V^{CRF},E^{CRF})$ can be ignored. The second term is the This is the negative ELBO. We know that the $\mathcal{KL}-$divergence is not negative. Thus, $\log~{}P(Y,V^{\text{{CRF}}},E^{\text{{CRF}}})\geq\text{ELBO}(Q)$ justifying the name Evidence lower bound (ELBO).

Therefore, the main objective is to optimize the ELBO in the mean field variational inference, i.e., choose the variational factors that maximize ELBO:

$$ $\displaystyle\text{ELBO}(Q)=$ $$

$$ $\int Q(\tilde{Y})\log\frac{P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})}{Q (\tilde{Y})}d\tilde{Y}=\mathbb{E}_{Q}\left[\log~{}P(\tilde{Y},Y,V^{\text{{CRF} }},E^{\text{{CRF}}})\right]-\mathbb{E}_{Q}\left[\log~{}Q(\tilde{Y})\right].$ (12) $$

We will employ coordinate ascent inference, where we iteratively optimize each variational distribution while keeping the others constant.

We assume that the set of CRF nodes is finite, i.e., $\left|V^{\text{{CRF}}}\right|<\infty$, which is a realistic assumption if we consider the set of all GNN inputs used during inference.
If $\left|V^{\text{{CRF}}}\right|=m$, we can order the elements $V^{\text{{CRF}}}$ in a a specific order $i=1,\ldots,m$. Thus, using the chain rule, we decompose the probability $P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})$ as follows:

$$ $\displaystyle P(\tilde{Y},Y,V^{\text{{CRF}}},E^{\text{{CRF}}})$ $\displaystyle=P(\tilde{Y}_{1:m},Y_{1:m},V^{\text{{CRF}}},E^{\text{{CRF}}})$ $\displaystyle=P(Y_{1:m},V^{\text{{CRF}}},E^{\text{{CRF}}})\prod_{i=1}^{m}P( \tilde{Y}_{i}|Y_{1:(i-1)},V^{\text{{CRF}}},E^{\text{{CRF}}}).$ $$

Using the independence of the mean field approximation, we also have:

$$ $\mathbb{E}_{Q}\left[\log~{}Q(\tilde{Y})\right]=\sum_{i=1}^{m}\mathbb{E}_{Q_{j} }\left[\log~{}Q(\tilde{Y}_{j})\right]$ $$

Now, we have the expression of the two terms appearing in ELBO in equation 12:

$$ $\text{ELBO}(Q)=\log~{}P(Y_{1:m},V^{\text{{CRF}}},E^{\text{{CRF}}})+\sum_{i=1}^ {m}\mathbb{E}_{Q}\left[\log~{}P(\tilde{Y}_{i}|Y_{1:(i-1)},V^{\text{{CRF}}},E^{ \text{{CRF}}})\right]-\mathbb{E}_{Q_{j}}\left[\log~{}Q(\tilde{Y}_{i})\right]$ $$

The above decomposition is valid for any ordering of the GNN inputs. Thus, for a fixed GNN input $a\in V^{\text{{CRF}}}$, if we consider $a$ as the last variable $m$ of the list, we can consider the ELBO as a function of $Q(\tilde{Y}_{a})=Q(\tilde{Y}_{m})$:

$$ $\displaystyle\text{ELBO}(Q(\tilde{Y}_{a}))$ $\displaystyle=\text{ELBO}(Q(\tilde{Y}_{k}))$ $\displaystyle=\mathbb{E}_{Q}\left[\log~{}P(\tilde{Y}_{m}|Y_{1:(m-1)},V^{\text{ {CRF}}},E^{\text{{CRF}}})\right]-\mathbb{E}_{Q_{m}}\left[\log~{}Q(\tilde{Y}_{m })\right]~{}~{}+~{}~{}\text{{const}}$ $\displaystyle=\int Q(\tilde{Y}_{m})\mathbb{E}_{Q_{\neq m}}\left[\log~{}P( \tilde{Y}_{m}|Y_{\neq m},V^{\text{{CRF}}},E^{\text{{CRF}}})\right]d\tilde{Y}_{ m}-\int Q(\tilde{Y}_{m})log~{}Q(\tilde{Y}_{m})d\tilde{Y}_{m}$ $\displaystyle=\int Q(\tilde{Y}_{a})\mathbb{E}_{Q_{\neq a}}\left[\log~{}P( \tilde{Y}_{a}|Y_{\neq a},V^{\text{{CRF}}},E^{\text{{CRF}}})\right]d\tilde{Y}_{ a}-\int Q(\tilde{Y}_{a})\log~{}Q(\tilde{Y}_{a})d\tilde{Y}_{a},$ $$

where $\neq m$ means all indices except the $m^{th}$.
Now, we take the derivative of the ELBO with respect to $Q(\tilde{Y}_{a})$:

$$ $\frac{d~{}\text{ELBO}}{dQ(\tilde{Y}_{a})}=\mathbb{E}_{Q_{\neq a}}\left[\log~{} P(\tilde{Y}_{a}|Y_{\neq a},V^{\text{{CRF}}},E^{\text{{CRF}}})\right]-\log~{}Q( \tilde{Y}_{a})-1=0.$ $$

Therefore,

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}Q(\tilde{Y}_{a})\propto\exp\left\{\mathbb{ E}_{-a}\left[\log~{}P\left(\tilde{Y}|Y,V^{\text{{CRF}}},E^{\text{{CRF}}}\right )\right]\right\}.$ $$

∎

###### Proof.

## Appendix B The Number of CRF Neighbors

### B.1 Proof of Lemma 4.2

Lemma 4.2
For any integer $r$ in $\{0,\ldots,\frac{n(n+1)}{2}\}$, the number of CRF neighboors $\left|\mathcal{N}^{\text{{CRF}}}(a)\right|$ for any $a\in V^{\text{{CRF}}}$, i.e., the set of graphs $[\tilde{G},\tilde{X}]$ with a Hamming Distance smaller or equal than $r$, have the following lower bound:

$$ $\forall a\in V^{\text{{CRF}}},~{}~{}\frac{1}{\sqrt{4N(N+1)\epsilon(1-\epsilon) }}.2^{H(\epsilon)N(N+1)/2}\leq\left|\mathcal{N}^{\text{{CRF}}}(a)\right|,$ (13) $$

where $0\leq\epsilon=\frac{2r}{n(n+1)}\leq 1$ and $H(\cdot)$ is the he binary entropy function:

$$ $H(\epsilon)=-\epsilon\log_{2}(\epsilon)-(1-\epsilon)\log_{2}(1-\epsilon).$ $$

###### Proof.

We use Stirling’s formula;

$$ $\forall s,~{}~{}s!=\sqrt{2\pi s}s^{s}e^{-s}\exp\left(\frac{1}{12s}-\frac{1}{36 0s^{3}}+\ldots\right).$ (14) $$

Thus, for $r$ in $\{0,\ldots,\frac{n(n+1)}{2}\}$ and $L=\frac{n(n+1)}{2}$, we write

$$ $\displaystyle\binom{\frac{n(n+1)}{2}}{r}$ $\displaystyle=\binom{L}{r}$ (15) $\displaystyle=\frac{L\!}{r!(L-r)!}$ (16) $\displaystyle\geq\frac{\sqrt{2\pi L}L^{L}e^{-L}\exp\left[-1/12r-1/12(L-r) \right]}{\sqrt{2\pi r}r^{r}e^{-r}\sqrt{2\pi(L-r)}(L-r)^{(L-r)}e^{-(L-r)}}.$ (17) $$

For $L\geq 4$, for any $r\in\{1,\ldots,L\}$, we always have $L-r\geq 3$ or $r\geq$, thus,

$$ $\frac{1}{12r}+\frac{1}{12(L-r)}\leq\frac{1}{12}+\frac{1}{36}=\frac{1}{9}.$ (18) $$

Therefore,

$$ $\exp\left(-\frac{1}{12r}-\frac{1}{12(L-r)}\right)\geq\frac{1}{12}+\frac{1}{36} =e^{-1/9}\geq\frac{1}{2}\sqrt{\pi}.$ (19) $$

We can then therefore derive a lower bound for $\binom{\frac{n(n+1)}{2}}{r}$ :

$$ $\displaystyle\binom{\frac{n(n+1)}{2}}{r}$ $\displaystyle=\binom{L}{r}$ (20) $\displaystyle\geq\frac{\sqrt{2\pi L}L^{L}e^{-L}\frac{1}{2}\sqrt{\pi}}{\sqrt{2 \pi r}r^{r}e^{-r}\sqrt{2\pi(L-r)}(L-r)^{(}L-r)e^{-(L-r)}}$ (21) $\displaystyle=\frac{\sqrt{L}L^{L}}{\sqrt{8r}r^{r}\sqrt{(L-r)}(L-r)^{(L-r)}}$ (22) $\displaystyle=\sqrt{\frac{L}{8r(L-r)}}\frac{L^{L}}{r^{r}(L-r)^{(L-r)}}$ (23) $\displaystyle=\frac{1}{\sqrt{8L\epsilon(1-\epsilon)}}\frac{1}{\epsilon^{r}(1- \epsilon)^{L-r}}$ (24) $\displaystyle=\frac{1}{\sqrt{8L\epsilon(1-\epsilon)}}\epsilon^{-L\epsilon}(1- \epsilon)^{L(1-\epsilon)}$ (25) $\displaystyle=\frac{1}{\sqrt{8L\epsilon(1-\epsilon)}}2^{LH(\epsilon)}.$ (26) $$

For $d$ in $\{0,\ldots,\frac{n(n+1)}{2}\}$, the number of possible graphs with a Hamming distance equal to $d$ from a graph $a=[G,x]$ is $\binom{L}{d}$.
Thus,

$$ $\displaystyle\left|\mathcal{N}^{\text{{CRF}}}(a)\right|$ $\displaystyle=\sum_{d=0}^{r}\binom{L}{d}$ (27) $\displaystyle\geq\binom{L}{r}$ (28) $\displaystyle\geq\frac{1}{\sqrt{8L\epsilon(1-\epsilon)}}2^{LH(\epsilon)}$ (29) $\displaystyle=\frac{1}{\sqrt{4N(N+1)\epsilon(1-\epsilon)}}.2^{H(\epsilon)N(N+1 )/2}.$ (30) $$

∎

###### Proof.

### B.2 Empirical Investigation of the Lower Bound

We empirically investigate the evolution of the lower-bound stated in Lemma 4.2 as a function of ratio $\epsilon=\epsilon(r)$. As noticed, the number of neighbors increases exponentially as the radius increases. This motivates the need for sampling strategies to reduce the size of the CRF.

Figure: Figure 2: The effect of the radius on the lower bound stated in Lemma 4.2.
Refer to caption: x2.png

## Appendix C The Set of Hyperparameters Used to Construct the CRF

In Tables 5 and 6, we present the hyperparameters used to run the inference of RobustCRF for each dataset. The number of iterations was fixed to 2. $p_{r}$ and we compute the radius as a floor function, i.e.,$r=\left\lfloor p_{r}\times m\right\rfloor$, where $m=|E|$ is the number of existing edges in the original graph.

**Table 5: The optimal RobustCRF’s hyperparameters for the feature-based attacks.**
| Hyperparameter | Cora | CiteSeer | PubMed | CS |
| --- | --- | --- | --- | --- |
| $r$ | 0.1 | 0.9 | 0.3 | 0.3 |
| $\sigma$ | 0.9 | 0.8 | 0.9 | 0.5 |

**Table 6: The optimal RobustCRF’s hyperparameters for the structure-based attacks.**
| Hyperparameters | Cora | CoraML | CiteSeer | PolBlogs |
| --- | --- | --- | --- | --- |
| $p_{r}$ | 0.02 | 0.02 | 0.04 | 0.005 |
| $\sigma$ | 0.05 | 0.2 | 0.05 | 0.05 |

## Appendix D Time and Complexity of RobustCRF

In Table 7, we present the average time (in seconds) required for RobustCRF inference. As observed, the inference time increases exponentially with larger values of $K$ and $L$. Nevertheless, empirical evidence suggests that a small number of samples is sufficient to improve GNN robustness. In our experiments, we specifically used $L=5$ samples and set the number of iterations to 2.

**Table 7: Inference time for different values of the number of iterations/samples.**
| Num Samples $L$ | 0 Iter | 1 Iter | 2 Iter |
| --- | --- | --- | --- |
| 5 | $0.26\pm 0.52$ | $1.99\pm 0.54$ | $16.40\pm 2.04$ |
| 10 | $0.20\pm 0.41$ | $3.24\pm 0.47$ | $58.28\pm 1.15$ |
| 20 | $0.22\pm 0.44$ | $5.86\pm 0.53$ | $224.86\pm 0.71$ |

## Appendix E Resuls on OGBN-Arxiv

In Table 8, we present the attacked classification accuracy of the GCN, a baseline and the proposed RobustCRF on the OGBN-Arxiv dataset.

**Table 8: Attacked classification accuracy ($\pm$ standard deviation) on the OGBN-Arxiv dataset.**
| Dataset | GCN | NoisyGCN | RobustCRF |
| --- | --- | --- | --- |
| Clean | 60.41 (0.15) | 59.97 (0.11) | 60.28 (0.15) |
| Random | 58.97 (0.24) | 58.71 (0.10) | 59.03 (0.26) |
| PGD | 50.24 (0.42) | 50.26 (0.37) | 50.10 (0.56) |

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: **1. What is the difference between defense against evasion attack and post-hoc defense.**

Both of them assume that attack happens during the inference phase, so the training procedure is not affected. If we formalize this problem mathematically, there are no differece. Therefore, all the reference work [1, 2, 3] that I mentioned in the previous review comprise the defense or evaluation on evasion attack. It is very necessary to consider them, see reasons below. [1] provide a systematical way to evaluate adaptive robustness of evasion attack; [2] is the first work that make adversarial training work on GNNs, and adversarial training is considered the only way to defense adversarial attack in the filed of vision community.
soundness: 2
strengths: 1. This works is easy to understand.

2. The motivation of this work is reasonable.
summary: This work studies the adversarial robustness of Graph Neural Networks during inference (evasion attack) and propose a new defense method RobustCRF basde on Conditional Random Field. The basic idea of this work is based on an assumption that similar inputs, including features and structures, should have similar output, and RobustCRF tries to achieve this by adapting the output.
weaknesses: 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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: please refer to weakness.
soundness: 3
strengths: 1. The paper is well-written and easy to follow.
2. Proposed framework is theoretical supported.
3. Introducing CRF to GNN robustness is interesting.
summary: This paper presents RobustCRF, a post-hoc, model-agnostic method to enhance the robustness of Graph Neural Networks (GNNs) against adversarial attacks during inference. By leveraging a Conditional Random Field (CRF), RobustCRF enforces that similar nodes produce similar outputs, improving robustness without prior knowledge of the GNN architecture. The method includes a sampling strategy to reduce computational complexity and is validated through theoretical and empirical analysis on benchmark datasets, demonstrating its efficiency and applicability across various GNN models.
weaknesses: 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?

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: I have some questions.

The first question is about the evaluation metric. As written in line 457 "We evaluate RobustCRF via the eAttack Success Rate(ASR)," However, in the table caption, it says 'Attacked classification accuracy'. So I am a little confused. Does the &#9312;
 in your table 1 represents clean accuracy and &#9313; represents ASR?

The second question is. I think there are there already some Post-Hoc Robustness Enhancement methods for graph neural networks. Can authors add some experiments on how the defense methods (such as GCNSVD, RGCN, and GCORN) perform when combined with those methods?
soundness: 3
strengths: The paper has the following strengths: 
- This paper is well-written and the method is easy to follow.
- The proposed method is model-agnostic and can be applied to many graph neural networks.
- Detailed analysis shows the effectiveness of the proposed method from a theoretical perspective.
summary: This paper put forward a method that can enhance the robustness of graph neural networks during the inference stage. This method is based on a Conditional Random Field. Extensive experiments show the effectiveness of the proposed method.
weaknesses: 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?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Refer to weaknesses
soundness: 1
strengths: 1. Model-Agnostic Robustness: The proposed method, RobustCRF, enhances the robustness of Graph Neural Networks (GNNs) without requiring modifications to the model's underlying architecture, making it versatile and adaptable to various GNN models.

2. Theoretical Foundation and Complexity Reduction: The approach is grounded in a comprehensive theoretical analysis, which strengthens the understanding and reliability of the proposed method. Additionally, it includes sampling techniques that reduce the computational complexity, making it more efficient.

3. Post-Hoc Enhancement: As a post-hoc technique, RobustCRF can be applied after model training, allowing for flexibility and ease of implementation across different GNNs, as it doesn't require prior modifications to the model.
summary: This study introduces RobustCRF, a post-hoc method designed to enhance the robustness of Graph Neural Networks (GNNs) specifically at the inference stage. Unlike most existing defense techniques that focus on training adjustments, RobustCRF leverages Conditional Random Fields in a model-agnostic manner, requiring no prior knowledge of the GNN architecture. The approach is validated on benchmark node classification datasets, demonstrating its effectiveness across various models in improving resilience against adversarial attacks.
weaknesses: 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.