Adversarial Robust Generalization of Graph Neural Networks

We sincerely appreciate your thorough review and valuable suggestions. However, we would like to clarify the first misunderstanding below:

1. Lack of new insights, comparison with existing methods, and application to real-world scenarios.

A1: Generally speaking, our focus does not lie in proposing a competitive algorithm tailored for a real-world application scenario (including real-world datasets and attack scenarios). Instead, this paper aims at a broader theoretical exploration of the robust overfitting in a general adversarial scenario. Our work not only develops a novel analytical framework for general GNNs (Theorem 4.8), but also provides helpful insights into model construction and algorithm designs (Proposition 4.14~4.18).

So, it is imperative for us to further clarify that " The lack of comparison with state-of-the-art methods and the limited scope of the experiments weaken the paper's contribution to the field" is not valid.

To be specific, this paper focuses on the robust overfitting phenomenon of GNN and provides theoretical guidance for improving their robust generalization in a general adversarial scenario. Based on our theoretical results, our empirical evaluation focuses on the influencing factors (some model architecture-related factors, like graph filter, weight norm, hyperparameters, etc.) and demonstrates their important roles in improving (or deteriorating) the adversarial generalization.

2. Analytical challenges introduced by graph data.

A2: Challenge 1: The information interaction of nodes leads to the correlation of perturbations between different nodes, making the adversarial perturbation set of graph data different from that of non-graph data. Solvement 1: In adversarial settings, we search for the worst perturbation vector $\delta$ from all node features that consists of a perturbation matrix. Then, by incorporating the worst perturbation vector $\delta$ into coverage analysis, Lemma 4.6 reveals an additional term $(\frac{6\theta C_{\ell}K_f}{\epsilon})^d$ influencing generalization caused by the interaction between perturbed nodes.

Challenge 2: Each node in GNN aggregates messages from its neighbor nodes through the message-passing mechanism, making the complexity measure of GNN model class different from NN. Solvement 2: In the decomposition of the propagation process (Proposition 4.14~4.18), we pay attention to the information interaction of graph data in the propagation process, which is reflected in the graph filter $\sum_{j=1}^n[g(A)]_{ij}$.

3. Lack of discussion of the assumptions made.

A3: Our analytical framework doesn't require smoothness assumptions of the loss function. This paper only needs the Lipschitz continuity assumption of loss function (Assumption 4.2) and activation function (Assumption 4.10), which can be easily satisfied by some commonly used functions (eg, cross-entropy and hinge loss; Sigmoid and ELU). Other assumptions about the norm constraint of input feature and weight matrix are also usually used in literature [1, 2].

In particular, for Assumption 4.1, we give the specific Lipschitz constant of each GNN model. For example, for a two-layer GCN, and $X(\delta)=[x_1+\delta,\dots,x_n+\delta]$, we have

$\Vert f_i(A,X(\delta),W)-f_i(A,X(\delta'),W)\Vert$

$\leq\rho_2\Vert\sum_{j=1}^n[g(A)] _ {ij}[\sigma(g(A)X(\delta)W_1] _ {j*}W_2-\sum_{j=1}^n[g(A)] _ {ij}[\sigma(g(A)X(\delta')W_1] _ {j*}W_2\Vert$

$\leq \rho_2w_2 \Vert g(A)\Vert\max_j\Vert[\sigma(g(A)X(\delta)W_1] _ {j*}-[\sigma(g(A)X(\delta')W_1] _ {j*}\Vert$

$\leq\rho_1\rho_2w_1w_2\Vert g(A)\Vert^2\max_j\Vert [X(\delta)] _ {j*}-[X(\delta')] _ {j*}\Vert$

$\leq K_{GCN}\Vert\delta-\delta'\Vert$.

Given the GCN with ELU activation and normalized filter ($\rho=1$, $\Vert g(A)\Vert=1$), conducting adversarial training with Algorithm 1 ($\Vert W\Vert$ is controlled) could lead to a controllable and small Lipschitz constant.

4. Irrelevance and misses of some referred papers.

A4: Thanks for pointing out the inaccuracy and misses. We will rectify the incorrect references (see [3,4]). As this paper focuses more on the theoretical analysis for adversarial training of GNNs, we will add additional related works about GNN attacks and defenses in the appendix for reference.

5. Applicable GNN types
6. Extension to structure perturbations.

A5/A6: Please refer to A2/A4 to the first reviewer (jE3b).

[1] Zhou, X. and Wang, H. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing, 424:97–106, 2021.

[2] Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. ICML, pp. 33674–33719. PMLR, 2023.

[3] Ben, F., et al. Single-node attacks for fooling graph neural networks. Neurocomputing, 513:1–12, 2022.

[4] Liu, T., et al. Nt-gnn: Network traffic graph for 5g mobile iot android malware detection. Electronics, 12(4):789, 2023.

We deeply thank you for acknowledging the rigorous logic, clear structure, and extensive formula reasoning of our work. Below are our detailed responses.

1. Why does the experimental part of this paper seem to lack a comparative study with previous work?

A1: Generally speaking, our focus does not lie in proposing a competitive algorithm tailored for a specific application scenario. Instead, this paper aims at a broader theoretical exploration of robust overfitting in a general adversarial scenario.

To be specific, this paper focuses on the robust overfitting phenomenon of GNNs and provides theoretical guidance for improving their robust generalization in a general adversarial scenario. Our work not only develops a novel analytical framework for general GNNs (Theorem 4.8), but also provides helpful insights into model construction and algorithm designs (Proposition 4.14~4.18). Based on our theoretical results, our empirical evaluation focuses on the influencing factors (some model architecture-related factors, like graph filter, weight norm, number of layers, hyperparameters, etc.) and demonstrates their important roles in improving (or deteriorating) the adversarial generalization.

2. The description of Algorithm 1 seems somewhat vague.

A2: Thanks for your helpful suggestion. Let $\mathcal{A}$ be a gradient-based attack algorithm (e.g., PGD, BIM, Mettack), the updated version is provided below.

Input: Graph $G=(A,X)$, dataset $S$, perturbed dataset $\tilde{S}$, perturbation budget $\theta$, regularization parameter $\lambda$, initialization $W_0$, learning rate $\eta$, number of iterations $T$.

while $t<T$ do

$\tilde{S}\leftarrow\emptyset$.

for $i = 1, 2, \ldots, n$ do

For the input matrix $X_t=[x_{1,t},\dots,x_{n,t}]$, perturb $\tilde{X_t} \leftarrow X_t+\mathcal{A} (X_t,A, \theta)$. ​
For each perturbed node in $\tilde{X_t}=[\tilde{x} _ {1,t},\dots,\tilde{x} _ {n,t}]$, append it to $\tilde{S_t}$ and choose $m$ samples randomly to the training set $\tilde{S} _ {m,t}$. ​
end for ​
Define a new objective $L(W _ {i,t})=\frac{1}{m}\sum_{\tilde{X} _ {i,t}\in\tilde{S} _ {m,t}} \ell(f _ {i,t}(A,X, W), y _ {i,t}) + \lambda \Vert W _ {i,t}\Vert _ {\infty}$. ​
For all $i\in [m]$, update $W_t$ using SGD: $W_{i,t+1}\leftarrow W_{i,t}-\eta\nabla {L}(W_{i,t})$.

end while

3. Can the derivation process of coverage analysis be simplified? It seems to be difficult to understand and apply.

A3: Covering number is a commonly used tool in (adversarial) generalization analysis [1,2]. Please let me briefly introduce our analysis technology first.

1. For the maximization over adversarial loss ( $\max_{\tilde{X}}\ell(f_i(A,\tilde{X},W),y_i)$)(Lemma 4.4). We construct new function classes ( $L$ and $L_{dis}$) and use their covering number to control the covering number of the adversarial loss class $L_{adv}$.

2. For the interplay between perturbed nodes (Lemma 4.6). We cover the perturbation set $\mathcal{B}$ and transform the cover of the loss class $L_{disc}$ to that of the perturbed model function class $\hat{F}$ .

3 (Theorem 4.8). Now we can obtain the relation between the adversarial generalization and the covering number of GNN model class!

4. Covering number derivation (Proposition 4.14~4.18). We utilize the relation between the model function $\hat{F}$ and its weight matrix $W$ to derive the covering number of the perturbed GNN class $\mathcal{N}(\hat{F},\epsilon,\Vert\cdot\Vert)$ by that of the weight matrix set $\mathcal{N}(${$W_j,\Vert W_j\Vert\leq w_j$}$,\epsilon_j,\Vert\cdot\Vert)$.

Actually, the main step that requires complex calculations is step 4, which is due to the propagation rules of GNN.

Therefore, given the Lipschitz continuity assumption about the adjacency matrix, our work can be applied to topology attack scenarios (by step 1-3). Since our covering number-based framework is applicable to general GNNs, given a specific GNN model with the relation between model function and weight matrix, it can be applied to other types of GNN models (by step 4).

[1] Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. ICML, pp. 33674–33719. PMLR, 2023.

[2] Tu, Z. et al. Theoretical Analysis of Adversarial Learning: A Minimax Approach. Neurips, 32, 2019.

We deeply appreciate your acknowledgment of the solid and comprehensive theoretical analysis and the thoughtfully designed empirical results presented in our paper. Thanks for pointing out the typo, and we will fix it in the future version.

Thank you very much for your valuable comments! Please refer to our response below.

1. Lack of testing for randomized splits of datasets.

A1: Thanks for pointing out the lack of considering the impact of dataset splitting. Taking two-layer GCN and two datasets for example, we show the generalization gap under different random split rates of training data (including 0.1, 0.3, and 0.5) in the table below.

The results show that they have consistent trends under increasing perturbation budgets. We will include a comprehensive version of the experiments in our future version.

2. Adaptation to other GNNs.

A2: Our results provide a general analytical framework for GNN, and give three classical examples of spectral GNN. Although specific results are not presented in the paper, spectral GNN like SGC, AGCN and GPR-GNN are feasible.

Moreover, we are reasonably confident in extending our results to other types of GNN (spatial-based GNN). Taking a single-head GAT for example, as for the model function $f_i(X,W)=\sigma_2(\sum_j\alpha_{ij}W_2X_{j*})$, and $\alpha_{ij}=softmax(\sigma_1(w[W_1X_{i*}\Vert W_1X_{j*}]))$, we can get the relation between the covering number of the model function class and that of the weight matrix set (i.e. $\mathcal{N}(\hat{F},\epsilon,\Vert \cdot\Vert)$ and $\mathcal{N}(\{W_j,\Vert W_j\Vert\leq w_j\},\epsilon_j,\Vert\cdot\Vert)$), which can be applied to our analytical framework.

3. Large-scale datasets are missing.

A3: Thanks for your valuable suggestions. Large-scale datasets like Nell and ogbn-arxiv will be included in our future versions.

4. Extension to attacks against structures.

A4: Given the similar adversarial settings for topology attacks and node attacks, we suggest that the methodology (e.g., Lemma 4.4 and Theorem 4.8) developed in this paper could be expanded upon the topology attack.

To be more specific, let the adversarial graph be generated from $\{\tilde{A}:\Vert\tilde{A}\Vert\leq \gamma \}$, where $\tilde{A}=A - A'$ denotes the perturbation matrix added to the original adjacency matrix. The adversarial loss w.r.t. adversarial graph is defined by $\max_{\Vert\tilde{A}\Vert \leq \gamma} \ell(f_i(\tilde{A},X,W),y_i)$.

Analyzing analogously to the node attacks. For each function $f\in\mathcal{F}$ and a fixed $\tilde{A} _ c\in\mathcal{A}$, we construct a new function $h:\mathcal{Z}\rightarrow(\mathbb{R}^n)^{\mathcal{A}}$ as $h(z_i,\tilde{A} _ c)=\ell(f_i(\tilde{A} _ c,X,W),y_i)$. The adversarial loss is denoted by $\max_{\tilde{A}\in\mathcal{A}} h(z_i,\tilde{A})=\max_{\Vert\tilde{A}\Vert \leq \gamma}\ell(f_i(\tilde{A},X,W),y_i)$ for any $\tilde{A}\in\mathcal{A}$.

From the definition of covering number, we construct the cover of the class $H$ of function $h(z_i,\tilde{A} _ c)$ and obtain the cover of the class $H_{adv}$ of function $\max_{\tilde{A}\in\mathcal{A}} h(z_i,\tilde{A})$. Thus, the following inequality holds

$\mathcal{N}(H_{adv},\epsilon,|\cdot| _ {\infty})\leq\mathcal{N}(H,\epsilon,\Vert\cdot\Vert _ {\infty}).$

Next, we construct a cover to control the infinite class $\mathcal{A}$ by $\mathcal{C} _ {\mathcal{A}}:=${$\hat{A} _ j,j\in[N_A]$}. Similarly, we can obtain the relation between $\mathcal{N}(H,\epsilon,\Vert\cdot\Vert_{\infty})$ and $\mathcal{N}(H_{dis},\epsilon,\Vert\cdot\Vert_{\infty})$, which needs an assumption that

$|\max h(z,A)-\max h(z,A')|\leq L_A\Vert A-A'\Vert$,

where the constant $L_A$ can be obtained if given specific GNN models.

This allows us to solve the measurement difficulty caused by the graph structure perturbations and apply it to our main results (Theorem 4.8). The remaining analysis will be left to future work.