An Optimization-Based Framework for Adversarial Defence of Graph Neural Networks Via Adaptive Lipschitz Regularization

Thanks for your detailed review. We are going to address your concerns one by one as follows:

Question: Clarification on the relaxation of problem (3) to (4)

Response: The authors agree that optimization problem (4) is relaxed version of (3). By solving (4) graph denoising and GNN training is done jointly, making the method adaptive.

Suggestion on using log based definition in (9)

Response: Thank you for the suggestion. We will revise the original definition according to the suggestion.

Question: Computational cost analysis

Response: The table shows runtime comparison of different methods for 400 epochs on Cora dataset.

Question: Convergence of two-stage approach

Response: We acknowledge that the two-stage algorithm aims to provide an approximate solution to the problem (11) with reduced computational resources. We intend to strike a balance between computational efficiency and solution quality. The results in the Table above demonstrate that our approach effectively achieves this objective, offering a compelling alternative that merits consideration. Indeed, the optimal solution obtained through the two-stage process may not strictly minimize the problem (11). However, in our analysis, we have observed that the solution serves as a robust proxy. The results align well with recent findings indicating the significance of the average degree of the input graph in the convergence of GNN [1]. Solving the problem (12) filters the adversarial connections, leading to a lower average degree in the data.

Question: Clarification on the proof of Theorem 1

Response: Thank you for the suggestion. We have modified the proof in the paper with all assumptions and details.

Question: Clarification of $\mathcal{N}$ in (1) Response: It is the neighbourhood function.

Question: Clarification on $\phi$ in (3) Response: It is the graph Laplacian

Question: Clarification on $\|\|E\|\|$ in Theorem 1 Response: Thank you for highlighting this. We have rectified in the paper.

Question: Clarification on $\omega$ in Lemma 2 Response: It is a vector. Detailed description is in Appendix C.

Question: Clarification on $L_q$ in (21) Response: It is the Lipschitz constant of the function $q(\omega)$ defined in (19).

[1]: Awasthi, P., Das, A., & Gollapudi, S. (2021). A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34, 20385-20397.

Thank the authors for their responce. My concerns has been partially addressed. However, there are still unaddressed issues. For the computational cost, what I expected was a computational complexity analysis, which can give us a sense of how fast the algorithm is in a direct way. The authors provided some experiment result on Cora. Although I appreciate the authors' efforts in conduction extra experiments, it is worth noting that Cora is a fairly small dataset and can not reflect the true complexity of an algorithm. Not to mention the proposed method looks quite slow on Cora. Based on this, I have decided to keep my current rating to this paper unchanged. I suggest the authors to rewrite and reorganize this paper with a more rigorous and consistent math notation and language and resubmit it.

Robustness Unit Test

We perform a robustness test of our proposed method following [1]. A unit test is proposed consisting of several adaptive attacks. The attacks that are based on Vanilla GCN are considered non-adaptive. The unit test consists of poisoning attacks over a range of budget 0 to 15% of E (E=Total no. of edges). We present the results of the attacks that lead to maximum degradation in Vanilla GCN performance on Cora-ML dataset.

Note that the hyperparameters for each model are tuned based on clean data and kept same throughout the experiment.

[1]: Mujkanovic, F., Geisler, S., Günnemann, S., & Bojchevski, A. (2022). Are Defenses for Graph Neural Networks Robust?. Advances in Neural Information Processing Systems, 35, 8954-8968.

Thanks for your detailed review. We are going to address your concerns one by one as follows:

Question: Clarification on smoothness of vertices?

Response: By smoothness of vertices, the authors mean smoothness of node-level attributes over the graph (clarification will be updated in the paper).

Question: Comparison with GARNET [1]

Response: Thank you for the suggestion. We present the comparison on Cora, CS, and Chameleon dataset. The backbone is GCN for both, hence for Chameleon dataset we have only used 10% Metattack.

Question: Use of Projected Gradient descent

Response: By using projected gradient descent similar to [2], the parameters can be normalized after every iteration in order to have a $\kappa$-Lipschitz stable model ($\kappa$ being tuned as hyperparameter). In literature often the $\kappa$ is taken as unity. However, several studies have pointed the tradeoff in terms of expressiveness while doing such normalization [3,4]. Hence, in this work we propose an optimization based method for adaptive Lipschitz regularization. The discussion will be added in the paper.

Question: Clarification on heterophily datasets.

Response: In the experiment section, we have mentioned that for heterophily datasets we have set parameter $\beta\rightarrow 0$.

Question: Clarification of data adaptivity

Response: Since, the proposed approach have a joint method to learn GNN parameters along with graph denoising, the algorithm becomes adaptive to the data given as input.

Question: Clarification of "adaLip w/o GD" in Figure 1

Response: In Figure 1, AdaLip w/o GD means our proposed approach without using graph denoising objective ($\beta=0$).

Question: Clarification on Remark 2

Response: In Remark 2, we mean to say that low-rank approximation based graph denoising can also be used within the framework of AdaLip. Also, in figure 1 we have compared the accuracy and Lipschitz bound of different methods.

[1]: Deng, C., Li, X., Feng, Z., & Zhang, Z. (2022, December). GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks. In Learning on Graphs Conference (pp. 3-1). PMLR.

[2]: Gouk, H., Frank, E., Pfahringer, B., & Cree, M. J. (2021). Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110, 393-416.

[3]: Zhao, X., Zhang, Z., Zhang, Z., Wu, L., Jin, J., Zhou, Y., ... & Yan, D. (2021, July). Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In International Conference on Machine Learning (pp. 12719-12735). PMLR.

[4]: Anil, C., Lucas, J., & Grosse, R. (2019, May). Sorting out Lipschitz function approximation. In International Conference on Machine Learning (pp. 291-301). PMLR.

Thanks for your detailed review. We are going to address your concerns one by one as follows:

Question: Undefined Notations.

Response: Thanks for pointing it out. We will clearly state each notation in the paper. $f_{\theta}$ in (12) represents the GNN function. $\lambda$ in (4) is a regularization parameter. $d$ in (7) represents the input feature dimension. $\chi$ is the domain set. $\theta(x,\Delta)$ is a typo; kindly consider it $f_{\theta}(x,\Delta)$, which represents GNN as a function of input feature and graph.

Question: Lemma 2 and operators $\mathcal{L}$ and $\mathcal{A}$.

Response: The detailed analysis of Lemma 2 and both operators is presented in Appendix C. Using the Lemma 2 problem (10) gets simplified as the matrix variable $\phi$, which is graph Laplacian can be replaced by the vector $\omega$.

Question: How does your approach differ in terms of "robustness of training" compared to other methods? How exactly is a "stable hypothesis" defined in this context?

Response: The stability of a neural network is quantified by its sensitivity toward small variations in the inputs. In literature, several approaches have been used to make the machine robust towards perturbations in the input data. The methods can broadly be summarized in three approaches:

1.) Training networks with perturbed versions of the data.

2.) Approaches where the goal is first to obtain the clean data and then train the network

3.) Studies that aim to use mathematical notions of stability.

Previous methods are not mathematically proven to be robust toward input perturbations. In this paper, we have considered the notion of stability as a bounded Lipschitz constant for the graph neural network. The notion of stability using the Lipschitz property is quite popular in the analysis of non-linear systems. A system with a bounded Lipschitz constant can be easily proven robust toward input variations.

Our current work focuses on providing a unified way where one can use the Lipschitz property while training the neural network without changing the overall architecture to provide robustness towards adversarial perturbations. Previous works that have enforced Lipschitz property while training have used brute-force methods where the layerwise weights are normalized [1,2]. This is the first work to formulate an optimization problem where the Lipschitz property is posed as an objective. Additionally, we have provided an iterative algorithm to solve the proposed optimization problem. Extensive experiments have demonstrated that the proposed approach is superior compared to state-of-the-art methods.

Question: Use of Projected Gradient descent

Response: By using projected gradient descent similar to [1], the parameters can be normalized after every iteration in order to have a $\kappa$-Lipschitz stable model. In literature often the $\kappa$ is taken as unity. However, several studies have pointed the tradeoff in terms of expressiveness while doing such normalization [2,3]. Hence, in this work we propose an optimization based method for adaptive Lipschitz regularization.

Question: Clarification on the proof of Theorem 1

Response: Thank you for highlighting this concern. We have modified the proof in the paper with all assumptions and details.

Question: Results on Heterophily datasets.

Response: The results are presented in Section 5.3.

Question: Use of $\log$ in (10)

Response: Thank you for bringing this to our attention. The problem of minimizing the product of functions is indeed transformed to minimize the sum of logarithms, aiming at simplifying mathematical analysis and ensuring numerical stability. However, our previous formulation did not explicitly involve taking the logarithm of the entire objective function, leading to a non-equivalent representation between equations (9) and (10). In line with the feedback from reviewer C1i6, we agree with the suggestion to directly add the log in the original definition eq (9).

Question: Meaning of iterations

Response: Since the problem (9) is a multi-block non-convex optimization problem, we devise an iterative algorithm for solving it.

[1]: Gouk, H., Frank, E., Pfahringer, B., & Cree, M. J. (2021). Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110, 393-416.

[2]: Zhao, X., Zhang, Z., Zhang, Z., Wu, L., Jin, J., Zhou, Y., ... & Yan, D. (2021, July). Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In International Conference on Machine Learning (pp. 12719-12735). PMLR.

[3]: Anil, C., Lucas, J., & Grosse, R. (2019, May). Sorting out Lipschitz function approximation. In International Conference on Machine Learning (pp. 291-301). PMLR.

Thanks for your detailed review. We are going to address your concerns one by one as follows:

Question: Convergence of the algorithm

Response: In the proposed approach, we regularize the GCN loss for Lipschitz stability. There has been multitude of work proving the convergence guarantees of GCN [1,2]. Proof is presented in Appendix E.

Question: Comparison with Robust Mid-Pass Filtering Graph Convolutional Networks (Mid-GCN) [3]

Response: Thank you for the suggestion. The table presents average accuracy over ten random runs.

Question: Runtime Comparison

Response: The table shows runtime comparison of different methods for 400 epochs on Cora dataset.

[1]: Awasthi, P., Das, A., & Gollapudi, S. (2021). A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34, 20385-20397.

[2]: Keriven, N., Bietti, A., & Vaiter, S. (2020). Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33, 21512-21523.

[3]: Huang, J., Du, L., Chen, X., Fu, Q., Han, S., & Zhang, D. (2023, April). Robust Mid-Pass Filtering Graph Convolutional Networks. In Proceedings of the ACM Web Conference 2023 (pp. 328-338).