Contractive Systems Improve Graph Neural Networks Against Adversarial Attacks

Regarding GNNGuard in Table 1: In our experimental results section, we seek to provide a comprehensive comparison with the latest methods. We did not include GNNGuard in Table 1 because there were no reported results on Metattack using a variable % of attack in the original paper. However, to address the reviewer's question, we provide a comparison below with GNNGuard on Metattack with a 20% perturbation rate and 5 targeted nodes using Nettack, as reported in GNNGuard, both on Cora and on Citeseer.

Those results further highlight the significance of our method, given that in most cases, CSGNN outperforms GNNGuard. We have added those results to our revised paper marked in Orange, in the paragraph titled “Comparison with GNNGuard” of Appendix J.

Regarding the strength of the attack: In our experimental section, we provide results using various settings that follow those presented in Pro-GNN and Mujkanovic et al. (2022). This approach allows us to provide an accurate and comprehensive picture of the current state of GNN defense mechanisms. Furthermore, we would like to kindly note that we include recent tests from Mujkanovic et al. (2022), that indeed seem to be stronger. Still, even under this harder attack, our CSGNN achieves improved results compared to other methods, as can be seen in Figures 4 and 7.

We sincerely appreciate the review comments regarding the novelty of our work and its performance, stating that ‘Using a diffusion process to model the joint evolution of node features and graph adjacency matrix seems to be novel.’ and that it provides ‘robustness against adversarial attacks’. We thank the reviewer for the insightful comments and questions, which we address below. In our revised paper, our responses to your queries are marked in Orange.

Regarding why contractivity improves robustness: As defined in our original submission (please see Equations (10) and (11)), contractivity leads to the reduction of the sensitivity of network outputs to input perturbations. Because graph attacks are based on input perturbations such as changes to the node features or adjacency matrix, and our CSGNN encapsulates an inductive bias in the form of a contractive system, it learns to fortify itself against graph attacks (i.e., perturbations), thereby improving the robustness of the model. More explicitly, even without the knowledge of the clean adjacency and feature matrices, having a contractive and stable system allows the outputs one gets with perturbed inputs to be close to the one would get feeding in the clean inputs. Indeed, this understanding is also empirically validated throughout our extensive experiments in Section 4. We discuss this point in our Preliminaries section (Section 3), and have now added an appendix section (Appendix A), to provide a better background on contractive systems.

Regarding "On the robustness of graph neural diffusion to topology perturbations" (NeurIPS 2022): We thank you for this important reference, which we now cite and discuss in our revised paper. The most crucial difference is the underlying method, novelty, and the performance of the methods on various benchmarks. While the mentioned paper also takes inspiration from neural diffusion GNNs, it utilizes only node feature update neural ODEs. On the contrary, our CSGNN offers a novel coupled neural ODE that learns both node features and adjacency matrix updates. This addition is proven to provide improved performance, as reported in the paragraph “Learning contractive adjacency dynamics is beneficial” of Appendix J (of the revised version of the manuscript). As 3 of 4 of the reviewers noted, this is a novel approach.

Regarding attack type: We follow the experimental settings in Pro-GNN, which considers inductive poisoning attacks using both white (metattack, nettack) and black box (random) configurations. In our original submission, we mentioned that in our experimental section, in Section 5.2. We have also revised our Introduction to highlight that, following your question.

Regarding adaptive attack: The reviewer is correct that we use the ‘unit-tests’ from Mujkanovic et al. (2022)., as stated in our original submission. As we discuss in Section 5.2, under the paragraph “Robustness to Adaptive Attacks”, the unit-tests are adaptive in that a different attack can be utilized for a different attack strength. We also note regarding the statement in Mujkanovic et al. (2022), “we cannot stress enough that this collection does not replace a properly developed adaptive attack”, that our goal is not to propose new attacks based on our method but rather to design a defensive mechanism. Thus, our motivation for using those useful unit tests was to be able to compare with recent baselines on challenging test cases, as shown in Figures 4 and 7. To address your concern, we have revised our text to reflect this discussion. Please see our changes in the revised paper, marked in Orange.

Regarding attack scope: We follow the same experimental setting as in [R8], a popular paper whose settings were followed in multiple papers, allowing us to present a broad picture of the adversarial defense capabilities of our CSGNN and compare it with many methods. The Reviewer is correct that our theoretical assumptions are motivated by attacks where the nodes do not change between clean and attacked graphs (i.e., we do not focus on injection attacks). This is also stated in our “Notations” paragraph in Section 3 (“Preliminaries”). Following your question, we revised our Introduction (Section 1) to highlight this fact to enhance the focus of the paper. Furthermore, we would like to add that while our focus is on poisoning attacks (i.e., not on injection attacks), in principle, we are unaware of any inherent limitation in our presented theoretical results regarding changing the number of nodes, which translates to injection attacks. Therefore, in principle, one could extend our work to injection attacks. However, as previously discussed, this is not the main focus of our paper, and it is left for future work.

Regarding black box evaluation, we would like to refer the reviewer to our experiments that include random perturbations in Figures 3, 6, and 9.

Regarding the Pubmed dataset, we do not agree that our model achieves suboptimal results. Indeed, our CSGNN does not achieve the highest accuracy on all configurations on Pubmed. Still, a close look at our tables will also suggest that no model is perfect and offers the highest results across all datasets and configurations, and this is also not our claim. We claim that CSGNN offers a powerful model that stems from an ODE perspective and is the first model within the family of ODE-inspired GNNs, at least to our knowledge, to also learn the adjacency matrix. As we discuss in this rebuttal and the paper, this construction is non-trivial as it requires preserving the equivariance and symmetry of the adjacency matrix. Our model indeed offers impressive (also according to most of the reviewers) results on most of the datasets and configurations in this paper. Furthermore, we kindly ask the reviewer to look at Figures 5 and 6, where our CSGNN achieves the highest results on Pubmed, and also in Table 4 our results are among the top 3 models. As previously mentioned, in our experiments, we seek to offer a broad comparison with as many models as possible, and this is the motivation that led to the selection of datasets included in our paper.

Regarding large datasets: We would like to refer the reviewer to Appendix I (Appendix J in the updated submission), where we provide results on the larger dataset Pubmed. Since our method includes an adaptive mechanism that alters the adjacency matrix in an end-to-end manner, using even larger datasets can be restrictive (memory-wise, due to the $O(n^2)$ possible edges and the need to keep gradients for backpropagation), which is in line with other GNN defense methods that include a learnable adjacency matrix mechanism, see for example [R8]. For reference, we did manage to run our CSGNN on a GPU with 24GB of memory on Pubmed but could not do the same with Pro-GNN [R8] due to out-of-memory errors. This can be attributed to the rather lightweight parameterization of our adjacency matrix update described in Equation (14). In addition, we note that employing an adaptive adjacency matrix mechanism to even larger scale datasets is a challenge on its own due to the quadratic complexity in the number of nodes. We agree that it would be interesting to develop methods that can significantly reduce the existing computational costs (which could potentially reduce the complexity of O($n^2$), the maximal number of possible edges). However, as previously discussed in our rebuttal, such development is out of the scope of this paper. The investigation of this research direction can have a large positive impact on the GNN community beyond adversarial defense and is left for future research.

[R1] Stable Architectures for Deep Neural Networks

[R2] Neural Ordinary Differential Equations

[R3] GRAND: Graph Neural Diffusion

[R4] PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations

[R5] GRAND++: Graph Neural Diffusion with A Source Term

[R6] Graph Neural Networks as Gradient Flows: understanding graph convolutions via energy

[R7] Invariant and Equivariant Graph Networks

[R8] Graph Structure Learning for Robust Graph Neural Networks

Regarding computational overhead: The reviewer is correct that learning to modify the adjacency matrix in an end-to-end fashion incurs additional computational overhead. We would like to start by noting that such an approach is not computationally light, regardless of the method (whether our CSGNN or other well-known methods like Pro-GNN [R8]). While such mechanisms do require more computations, they also offer improved performance. We now provide a complexity analysis of our CSGNN, followed by a table that reports the training and inference times and memory consumption on an Nvidia RTX-3090 GPU with 24GB of memory, on the Cora dataset. Theoretically, the added runtime complexity for a CSGNN adjacency matrix learning layer is $O(9 \cdot n^2)$ where $n$ is the number of nodes. Thus, assuming L layers, the overall complexity of a CSGNN network is $O(L(n \cdot c^2 + m\cdot c + 9\cdot n^2))$, whereas node-based ODE systems usually are of runtime complexity $O(L(n \cdot c^2 + m\cdot c))$. Please recall that $n$ is the number of nodes, $m$ is the number of edges in the graph, and the term of $c^2$ stems from the channel mixing term in Equation (8). The factor of 9 stems from the 9 parameters to be learned in Equation (14). Below, we report the runtimes and memory consumption of our CSGNN and compare it with CSGNN$_{\textrm{noAdj}}$ (that is, CSGNN without the adjacency matrix update), and Pro-GNN for reference. These experiments were run on the Cora dataset with networks with 64 channels and 2 layers. It can be seen that both CSGNN and Pro-GNN require more resources, however, such an approach offers improved performance.

Also, we note that while both our CSGNN and Pro-GNN propose methods to evolve the adjacency matrix, our CSGNN shows significantly lower training computational time, due to our solution taking the form of a learned neural ODE system for the adjacency matrix, while Pro-GNN solves an optimization problem with feedback to the downstream task (which is also an end-to-end solution, although different than ours). For inference, Pro-GNN uses the fixed adjacency matrix found by training, while our CSGNN evolves the input adjacency matrix using the learned network. This can also be seen as an advantage of CSGNN, as it can be used for inference on different kinds of attacks and, therefore, can potentially generalize to different attacks, and this is a future research direction.

We also add that investigating the possibility of reducing the computational costs for learning adjacency matrices is an important and interesting topic on its own, that is left for future work.

We added the complexity analysis, reported runtimes, and future directions discussion to our revised paper.

Regarding motivation: We thank the reviewer for the questions. We split our response into different parts according to the questions raised by the reviewer.

(i) The assumption of a piecewise constant function in Equation (6) is a common practice in neural ODEs, and it allows us to assume that we can interpret the learned neural network layers as the discretization of some continuous ODE. This is a very basic assumption, and it is also made in [1] as suggested by the reviewer. Furthermore, we kindly refer the reviewer to the following papers [R1,R2,R3,R4,R5] (cited in our original submission), where a similar assumption is made. To clarify this point, we have revised our text (please see changes in Magenta).

(ii) We would like to kindly refer the reviewer to the text above Equation (8), where we discuss the motivation for constructing our node dynamics. As stated, “We build upon a diffusion-based GNN layer, (Chamberlain et al., 2021; Eliasof et al.,2021), that is known to be stable, and under certain assumptions is contractive”. That is, the construction of this mechanism allows us to theoretically analyze and explain the behavior of the node feature dynamical system of CSGNN. Using the gradient operator in Equation (8), we rely on the definition made in (Chamberlain et al., 2021; Eliasof et al.,2021). The same definitions are also used in the paper provided by the reviewer (paper [5]). To better accommodate the reviewer’s question, we added an explicit definition of the gradient operator in our revised paper in Appendix B (which used to be Appendix A). We refer to appendix B before equation (8) in our revised version.

(iii) Our choice to keep $\tilde{\mathbf K}_l$ symmetric is not arbitrary. It stems from [R6] (also cited in our original submission), allowing us to view the layers of the GNN as a discretization of a gradient flow. Therefore, it is important so as not to compromise the dynamical system view in our CSGNN. We have revised our paper to include this discussion.

In addition to the findings in [R6], in our case, it is reasonable to keep $\tilde{\mathbf K}_l$ symmetric so that if it is also learned to be positive definite, then the forward propagation of our node feature system is stable, as pointed out in Appendix A (now Appendix B after the updates introduced in the revised manuscript). Our original submission also provided this discussion; please see the paragraph after Equation (10) up to Section 4.3.

(iv) We would like to note that the design of Equation (14) is far from an arbitrary choice. As discussed in our original submission, we build on the results shown in [R7], to design an equivariant and symmetry-preserving parameterization of the adjacency matrix, which is used to define our adjacency matrix update step. Furthermore, the design of Equation (14) is a major contribution of our work, and it addresses both mathematical and technical challenges in implementing an adjacency matrix dynamical system. We gently ask the reviewer to read our discussion that motivates this structure in Section 4.3.

Regarding reproducibility: We are currently not at liberty to share the source code. However, we pledge to publicly share it on GitHub upon acceptance. Additionally, we note that for reproducibility purposes, our original submission includes a detailed description of our method and architectures in Appendices G, H, and I (which used to be E, F, and G in our original submission).

Regarding checking $\mathbf K_l$ being positive-definite: In our submission, we clearly state in Appendix B (used to be Appendix A) that depending on the weights of $K$, we may or may not get a stable update for the node features (which translates to $\tilde{\mathbf K}_l$ being positive-definite). Furthermore, our experiments check the influence of $\tilde{\mathbf K}_l$ being positive-definite or not. Specifically, in Appendix J, under the paragraph “Enforcing contractive node dynamics improves baseline performance”, we experiment with a variant of CSGNN that enforces the stability of the node dynamical system, called ECSGNN. Our results indicate improved performance compared to existing methods with ECSGNN, but further improvements can be obtained if we let $K$ be learned in a data-driven fashion. Our original submission included a reference to the results provided in Appendix J in the paragraph after Equation (10) up to Section 4.3. Therefore, we believe that our original submission offers a fair exposition of our work, both quantitatively and qualitatively, and we would like to hear the reviewer’s opinion on this point after our clarification. To further address your concern, we have revised Appendix J text to reflect the discussion here better.

We thank the reviewer for the thorough and detailed feedback. The reviewer says that our paper proposes ‘a novel architecture, CSGNN, that innovatively integrates the principles of contractive dynamical systems to enhance the robustness of GNNs against adversarial poisoning attacks’ and that ‘The authors fortify their claims with a rigorous theoretical analysis.’ We thank you for acknowledging the novelty of our work. In our revised paper, our responses to your queries are marked in Magenta.

The reviewer also suggests several important points to improve our paper. We now address them individually. Our changes to the submission are marked in Magenta. We hope that the reviewer is satisfied with our updated paper and responses below and that they will consider raising their score. We are also happy to continue the discussion and address any remaining questions.

Regarding literature review: We thank the reviewer for the important references, which we now include and discuss in our revised version. Specifically, we note that papers [1-4] consider structured grid data (e.g., 2D images), while our work considers graphs and GNNs. Still, we agree it is essential to discuss the papers working on adversarial robustness and following a similar approach to the one we suggest. We have now updated the manuscript, including Appendix E, where the mentioned references and a few more are included and briefly discussed. This appendix is also referenced in the Introduction section of the main body. Regarding paper [5], it studies the effectiveness of diffusion neural GNNs to graph topology attacks, showing its resilience compared to other methods. This paper is indeed very important and also adds to the motivation for using such networks for defense. Also, please see, regarding your query about the design of Equation (8), that paper [5] proposes a similar definition of the node feature system. Regarding paper [6], it offers a way to generate new injection attacks, while our paper focuses on a defense mechanism for GNNs. We added papers [5,6] to our Related Work section and a discussion of [1-4] to our revised Appendix. Please see our changes in Magenta.

Finally, we would like to mention that the main novelty of our work, which is the learning of a coupled dynamical system that includes the adjacency matrix, is indeed an original contribution of our work, which is not considered in [1-6]. We add to our revised paper Appendix E, that discusses papers [1-4], and include references [5-6] in the “Related Work” section of the main text.

Dear Reviewer SPJa,

We sincerely appreciate the time and effort you dedicated to reviewing our paper, as well as the constructive feedback that helped us to improve our revised submission. After providing clarifications to your question, responding to your suggestions, and revising our paper, we hope that the concerns raised by you have been resolved. Could you kindly let us know if our responses have sufficiently addressed your concerns? We are happy to continue the discussion to clarify any standing doubt you may have. We thank you again for your valuable time.

With warm regards,

The authors

We would like to thank the reviewer for the positive feedback, saying that our paper is ‘well-written, ensuring clarity and accessibility for readers’, as well as praising the novelty of our method, stating that ‘The simultaneous evolution of node features and adjacency matrices is a unique aspect of this approach, demonstrating a high degree of originality.’ We now address your question below. In our revised paper, our responses to your queries are marked in Red.

Regarding the assumptions of Theorems 1 and 2: In our original submission, we state in Appendix A (now turned to Appendix B, in our revised version), after Equation (16) (now Equation (18)), that we assume the activation function $\sigma$ should be monotonically increasing and 1-Lipschitz. We agree that explicitly adding the assumptions to Theorems 1 and 2 improves the quality and clarity of our paper, and we have now added them to our revised version. Please see our changes, marked in Red.

We thank the reviewer for the overall positive assessment of our submission. The reviewer mentioned the ‘well written’ manner of our paper and the ‘complete theoretical analysis’ with ‘strong results’. Below, we provide our responses to your concerns. In our revised paper, our responses to your queries are marked in Blue.

Regarding background on contractive systems: The reviewer is correct that our submission can benefit from an overview of contractive systems. In our original submission, we briefly discussed the meaning of a contractive system in the last paragraph of Section 3 (Preliminaries) and in the Method section (Section 4). Specifically, we provide the discretized definition of a node contractive system in Theorem 2 (please see Equation (10)) and of the adjacency matrix contractive system definition in Equation (11). In our submission, we focus on discretized dynamical systems and therefore only provided those definitions.

We also note that Reviewer fwuD highlights the mathematical background provided in our submission: “2. The paper provides a rigorous mathematical derivation of the proposed architecture and comprehensive empirical evaluations. The authors offer theoretical insights into the expected behavior of their method, and empirical results affirm its effectiveness in bolstering GNNs against adversarial attacks.”

To make our paper more self-contained, following your suggestion, we have added an Appendix section (“Contractive Systems”) that discusses the continuous definition of contractive systems and provides a few of their properties. We now refer to the added Appendix section from our main text in the Preliminaries section. Our changes can be viewed in the updated submission, marked in Blue.