If You Want to Be Robust, Be Wary of Initialization

We thank the reviewer for their insightful feedback. We would like to answer their main concerns and questions as follows:

[W1 - General comment] We feel slightly misunderstood by this comment and therefore want to apologize for any confusion that may have arisen from a possible lack of clarity in our explanations. In what follows, we try to address some of the perspectives that we feel weren’t fully clear:

• Starting from our risk definition, we can fairly consider that if for an input point $x$, the output representation of the clean classifier and the attack classifier is close in the output space, then we can expect that the attack has failed (since the softmax function is just a monotone transformation based on the final output presentation). The motivation for not taking into account the softmax function in our setting was due to the desire to be general which is important in the case of GNNs since different downstream tasks are considered (node classification, node regression, graph classification/regression and link prediction).
• “Smaller norm weights” was actually already investigated by other papers (such as Parseval regularization[1]). In our case, we rather consider how different training dynamics (such as number of epochs, the considered initialization and the learning rate) can affect reaching robustness. Hence, the novelty of our approach is focused on the training dynamics instead of making the statement that “smaller weight norm” will help in robustness (which is already well investigated and well known in the adversarial literature).
• Regarding the tightness of the bounds, the idea was to show the link between the previously discussed dynamics and the adversarial robustness. The provided bounds were actually the best we could come up without additional assumptions (making the study not relevant in practice). For instance, the bound can be tightened as stated after Theorem 2: " the dependence of $\gamma$ on $t$ can be sharpened by having $(1+\eta L)^t$ instead of $2^t$. With small $\eta$ (which is the case usually in practice), $(1+\eta L)^t \approx 1+ t\eta L$ resulting in a bound which depends linearly in $t$”.

[W2 - Regarding the generalization aspect] We are grateful that this sub-result is of interest to you and the other reviewers. We have drafted a more detailed clarification to this point in our “General Rebuttal”. The main idea is that our interest revolves around GNNs in which we have enough knowledge to make assumptions about the architectures and the internal dynamics of the Message-passing framework. For instance, in the GCN’s case (Theorem 2), the upper-bound is dependent on the “normalized walks” within the input graph (meaning that denser graphs shall result in more adversarial effect). We believe that similar insights can be derived for other architectures such as those in the image domain. Consequently, the proposed generalization serves as a theoretical pointer to other researchers from the images or NLP domain to extend these results and eventually find more relevant and concise upper-bounds. We finally would like to refer the reviewer to the additional results on ResNet using the CIFAR 10 dataset in our general rebuttal (Table 1) and also the effect of adversarial training and other defenses such as TRACES on the same architecture (Table 2 - Response to Reviewer 1) which will be added to our revised manuscript.

[Q1 - On the convergence of the models] All the considered models in Figure 2 were trained until convergence. Of course as pointed out, the initialization can have an effect of the clean accuracy. We have therefore chosen the distribution’s range of parameters (value of $\sigma$ of the gaussian distribution and the scale value in the Orthonormal and Uniform distributions) such as to be close to the state-of-the art performance of a GCN (with a maximum 2% margin). In the now following Table 4, we present the clean accuracy in the case of the extreme cases of the initial distributions:

Table 4: GCN’s clean accuracy when subject to different initialization distribution using different parameters.

[Q2 - On the number of trials] We apologize if this wasn’t highlighted enough in our manuscript. As explained in our experimental setting (Section 6.1 and in details in Appendix H): “To mitigate the impact of randomness during training, each experiment was repeated 10 times, using the train/validation/test splits provided with the datasets.” We will add this also to the figure caption as well in the revised manuscript.

—

[1] Cisse, Moustapha, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. "Parseval networks: Improving robustness to adversarial examples." In International conference on machine learning, pp. 854-863. PMLR, 2017.

We thank the reviewer for their constructive feedback and we would like to answer their main concerns and questions as follows:

[W1 - Regarding the provided references] We thank the reviewer for these references that we weren’t aware of and we will include a complete analysis and discussion in our “Related work” section. It seems that the majority of these works are rather interested in the specific effect of initialization and other dynamics in the case of adversarial training. Our framework is rather more focused on the classical training and how different parameters (such as number of layers, number of epochs and learning rate) can affect the final underlying robustness. The majority of these proposed papers are also focusing on the empirical side hence our theoretical analysis can be of relevant to close the gap. In fact, we believe that our theoretical analysis can be adapted for the case of adversarial training (where we can consider that the “real” inputs have a gradient towards the downstream task and the “generated adversarial” inputs have a rather negative one).

[W2 - On the considered benchmarks] We would like to thank the reviewer for seeing the value of the generalization section of our theoretical framework (which we note is not our main focus). We have drafted a more complete answer in our “General Rebuttal” as it was a common point between the reviewers. Typically, we wanted to underline that our main interest revolves around GNNs in which we have enough knowledge to make assumptions about the architectures and the internal dynamics of the Message-passing framework. For instance, in the specific case of GCN (Theorem 2), the upper-bound is dependent on the “normalized walks” within the input graph (meaning that denser graphs shall result in more adversarial effect). With a higher knowledge of the domain, similar theoretical results can be derived in the case of other domains such as NLP or Images resulting in more useful insights. Consequently, we believe that the introduced generalization part can be seen as pointers aimed to help close a gap which we have seen to be missing in the literature and which can be a first direction for other researchers to expand (such as the previously discussed adversarial training setting). Upon your suggestion (for which we are deeply grateful), we have initiated some new experiments to show the validity of our results on the ResNet family as well and to extend from MNIST (which was used for the DNN) to the Cifar-10 dataset. Table 1 reports the effect of the initialization on the ResNet model with both PGD and FGSM attacks. We will add these results (and expand them to other attacks) in our revised manuscript.

Table 5: Effect of Initialization on ResNet when subject to FGSM and PGD attacks using CIFAR-10 Dataset.

We have also conducted a number of experiments on the interaction of our theoretical results with possible other defense methods (such as Adversarial training and TRADES [1]) which are in the same direction as the references you have provided.

Table 6: Effect of Initialization on ResNet on the clean and attacked accuracy when subject to PGD adversarial training (AT-PGD) and TRADES with $\epsilon=8/255$.

—

[1] Zhang, Hongyang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. "Theoretically principled trade-off between robustness and accuracy." In International conference on machine learning, pp. 7472-7482. PMLR, 2019.

We would like to sincerely thank the reviewer for their feedback and comments.

As detailed in our “General Rebuttal”, the main focus of our research is related to GNNs, hence why the experimental setting was rather focused on this side. The extension to other models (such as DNNs in the paper or the additional ResNet on Cifar-10 that we provide in the general rebuttal - Table 1) was rather to show the extensibility of the theoretical results which we have seen to be missing from the corresponding literature. We will point out this further in our limitation section. In what follows we aim to address the raised concerns and questions one-by-one.

[W1 - Regarding the hyper-parameters] Note that the provided theoretical results (Theorem 2 & 3) does indeed show the possible effect of the “number of layers” and “learning rate” (Equation 3 Section A of the Appendix). Hence, the reviewer is right on their intuition regarding the possible effect of hyper-parameters. Since the goal of our experimental setting (described in Appendix H) was aimed to validate the theoretical results, we followed the same hyperparameters that are “usually” used in the literature to ensure the classifier and the attacker’s convergence. Typically, we focused on a 2-layer GCN (since it can reach state-of the art accuracy and also because too many more layers result in the downgrade of the accuracy – which is known as over-smoothing in the GNN literature).

[W2 - Regarding the practical usage of the results] This is indeed a fair and important point. Our theoretical analysis main result is that the dynamics of the training (Number of epochs, learning rate and the number of layers) also affect the final model’s adversarial robustness. Consequently, one possible future direction that could be investigated is a robustness metric to track the advancement of a model’s robustness (similar to the validation accuracy which is used to select the top model). Typically, one possible metric or measure would be to approach the proposed adversarial risk quantity (Equation2) using an estimator (such as randomised or stratified sampling from the input’s neighbourhood and evaluating the distance to the input’s prediction). To summarise, in addition to taking into account our proposed results (such as finding the right trade-off of epochs to reach convergence and adversarial robustness and choosing the right initialization), we need to investigate a model’s validation approach to keep track of its adversarial aspect. We will incorporate these practical guidelines in our revised manuscript, serving to make our theoretical and experimental insights more useful in practice.

[Q1 - On the interaction with the adversarial defenses] We have indeed studied the possible combination of our proposed insights with some “benchmark” graph adversarial defenses in Appendix G.4 where we studied RGCN (Figure 8) and GNN-Jaccard (Figure 9). For the sake of generalization, and we thank the reviewer for pointing out the idea, we have computed the results on adversarial training (based on PGD) and using TRADES [1] on the ResNet model using the Cifar-10 dataset. Table 2 reports the clean and attacked accuracy, showcasing therefore the application of our theoretical insights both to adversarial defenses but also to other architectures (besides GNNs and DNNs).

Table 2: Effect of Initialization on ResNet on the clean and attacked accuracy when subject to PGD adversarial training (AT-PGD) and TRADES with $\epsilon=8/255$.

—

[1] Zhang, Hongyang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. "Theoretically principled trade-off between robustness and accuracy." In International conference on machine learning, pp. 7472-7482. PMLR, 2019.

We would like to sincerely thank the reviewer for their feedback and their comments.

We are grateful for your comment on the novelty of our theoretical analysis and direction. Regarding the generalization of the results, we have drafted a complete response in the “General Rebuttal” as all the reviewers evoked this point. While this interest is certainly encouraging, we note that the framing of the paper was in direction with our main interest which revolves around GNNs in which we have enough knowledge to make assumptions about the architectures and the internal dynamics. For instance, in the GCN’s case (Theorem 2), the upper-bound is dependent on the “normalized walks” within the input graph (meaning that denser graphs shall result in more adversarial effect). We believe that similar insights can be derived for other architectures such as those in the image domain. Hence, this part of our manuscript can be seen as pointers to more advanced specific studies in each domain that can eventually result in interesting upper-bounds. Finally, we would like to refer the reviewer to the additional results on ResNet using the CIFAR 10 dataset in our general rebuttal (Table 1) and also the effect of adversarial training and other defenses such as TRACES on the same architecture (Table 2 - Response to Reviewer 1).

In what follows, we try to address the additional questions/concerns raised by the reviewer:

[W1 - In respect to the clean accuracy of Figure 2] In our experimental results, we have chosen to report the success of the attack since we thought it’s a better experimental representation of the theoretical results (our adversarial risk definition consists of the gap between the clean/attacked model). Nonetheless, ensuring a reasonable initial/clean accuracy (close to the state-of-the art by a 2% order) was important, hence the choice of the distribution’s range of parameters (value of $\sigma$ of the gaussian distribution and the scale value in the Orthonormal and Uniform distributions). Table 2 reports the clean accuracy in the case of the extreme cases of the initial distributions used in the analysis in Figure 2. We will add the complete figure of clean accuracies in the Appendix.

Table 3: GCN’s clean accuracy when subject to different initialization distribution using different parameters.

[Q1 - Regarding the tightness of the upper-bounds] Indeed, these bounds can be tightened depending on the used optimization algorithm and the considered assumptions. In the case of Gradient Descent (GD) that we considered in the paper, we did not find better bounds for the iterates than those presented in the appendix (Eqs. (3) and (4) under non convex assumption and Eqs. (12) and (13) under strong convexity assumption). Regarding the final bounds we gave in sections 4, they can be tightened as stated after Theorem 2: " the dependence of $\gamma$ on $t$ can be sharpened by having $(1+\eta L)^t$ instead of $2^t$. With small $\eta$ (which is the case usually in practice), $(1+\eta L)^t \approx 1+ t\eta L$ resulting in a bound which depends linearly in $t$”.

[Q2 - On the definition of adversarial risk] This is a small typo in writing, note that we have used the correct formulation in the Theorem’s proof (Appendix E - Eq. 10). We thank the reviewer for spotting this and we will correct it in the revised manuscript.

[Q3 - Linking to regularization techniques] The idea of adversarial defense through regularization techniques is indeed very related to our work. The main difference is that in addition to the final weight’s norm, we also consider the initial weights, the learning rate and the number of epochs. Hence, our method can be seen as a generalization of studying the regularization techniques, in which we also focus on the training dynamics.

[Q4 - Extending to fine-tuning] This is indeed a very interesting direction that could be seen as a sub-result of our theoretical analysis. For now, there isn’t much work on pre-trained GNNs, but we expect this field to expand in the coming years, which makes this question all the more relevant. In the case of other domains (such as NLP), there are two directions that could be investigated in this perspective. The first direction is when we consider that we have no control over the pre-trained model, hence the only control is over the classification/regression head that would be trained. In this case, our theoretical result is applied in the choice of the initial distribution of the weights and the number of fine-tuning epochs where a balance between accuracy and robustness should be found. In the second direction, where we have control over the pre-trained model, we don’t think our theoretical result can be applied since the pre-training consists of a number of “self-supervised tasks” (such as token masking or contrastive learning), and we believe that our adversarial risk definition doesn’t necessary extend from the pre-training embedding space to the downstream tasks. This latter point can be indeed an excellent research direction in which the goal would be to investigate the best pre-training dynamics capable of ensuring the downstream adversarial robustness of a pre-trained model.