PROSPECT: Learn MLPs Robust against Graph Adversarial Structure Attacks

Question 2: About Figure 1.

• "However, the fixed version seems noncompetitive against other defense baselines. " As discussed in the Contributions/The key to future mutual distillation section of joint response, simply combining GNNs and MLPs for mutual distillation may easily lead to failure because of the model heterogeneity issue identified and (partially) solved by us.

• "Is the QACA scheduler the one that actually contributes to the performance?" 1) As discussed in Weakness 1, GNN-to-MLP and MLP-to-GNN distillation, i.e., the interaction between GNN and MLP contributes to the clean accuracy and robustness due to the accumulated knowledge post knowledge fusion (through mutual distillation). This gain has nothing to do with a specific optimization method. 2) However, as pointed out in the Contributions/The key to future mutual distillation section of joint response, simply combining GNN and MLP can lead to failure and that's why we need a QACA optimization paradigm. 3) In short, we think that the PROSPECT framework itself determines its capability, but this capability is locked. And QACA is just the key that opens the lock.*

• "Can the previous distillation methods be enhanced by QACA as well?" 1) QACA addresses underlying knowledge discrepancies within heterogeneous model distillation, hence offline frameworks, e.g.,GLNN, do not stand to benefit. Potentially, QACA mitigates conflicts even for general heterogeneous mutual distillation, but space constraints precluded detailed analysis beyond GNN-MLP. 2) As pioneering GNN-MLP mutual distillation research, this paper validates QACA efficacy for this task. Intuitively, distilling between similar models unlikely exhibits severe conflicts, limiting QACA’s boons for GNN-GNN. However, QACA could assist future GNN-GNN models incorporating knowledge conflicts.

Question 3: Concerns when faced with other attacks.

• Graph injection attack Graph injection attacker, e.g., $G^2A2C$ [4], first adds a virtual node $a$ for the target node $i$ and then connect it to the original graph. During the neighborhood aggregation, the feature of node $i$ will be interfered such that its score on the correct category $c$ will decrease significantly. Now the case fails back to the first question in Weakness 1 and the point becomes that whether the MLP is affected by node $a$ such that the MLP have a smaller score on $c$ than that of the GNN and thus becomes unqualified to be a teacher. Since the injected nodes are not used to train the MLP (no neighbor aggregation), they do not impact the MLP. Thus PROSPECT can work like under the structure attack, e.g., Metattack, as shown by our submission. Our supplementary experiments (see Section Appended Experiments/Graph injection attacks in the joint response) with the SOTA injection attack $G^2A2C$ demonstrate this.
• Node feature attack We discuss the node feature attack scenario in the Concerns about joint, injection and adaptive attacks section of joint response.
• "It would be more convincing if PROSPECT is tested under more attack settings." To improve the persuasiveness regarding robustness, results across four additional attack methods have been included in the Appended Experiments section of the joint response.

[1] E. Chien, et al., “Adaptive Universal Generalized PageRank Graph Neural Network,” ICLR'2021.

[2] Deng, Chenhui, et al. "GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks," LoG'2022.

[3] X. Han, T. Zhao, Y. Liu X. Hu, and N. Shah, “MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization,” ICLR'2023.

[4] M. Ju, et al. "Let Graph Be the Go Board: Gradient-Free Node Injection Attack for Graph Neural Networks via Reinforcement Learning," AAAI'2023.

Weakness 2: Number of Hyperparams.

• The hyperparameters of PROSPECT: The hyperparameters introduced by PROSPECT include the loss weights for the logit distillation terms of the individual MLP and GNN optimization objectives, and the knowledge distillation temperatures of them. These are inevitable hyperparameters present in all mutual distillation architectures.

• The hyperparameters of QACA: Although QACA contains hyperparameters including individual learning rates, weight decay values, minimum optimization cycle, and minimum learning rates of MLP and GNN, only the last three hyperparameters are actually introduced by the QACA scheduler. The other hyperparameters are originally present in the individual MLP and GNN models themselves.

• Why these hyperparameters? 1) The differences in these hyperparameters across datasets are primarily to accommodate the behaviour differences between the MLP and GNN on datasets with different characteristics (see Table A for a glance). How to design mutual distillation schemes between GNNs and MLPs that can self-adapt to different dataset characteristics is an important future research direction that would require a series of complete independent studies to elaborate (we are working on such a project). Adding this would make this already lengthy paper even more complex and diffuse in focus.

Weakness 3: Baseline Missing.

We have supplemented many experiments, including the comprehensive comparison between GPRGNN [1], GARNET [2] and our PROSPECT under 4 other attacks in addition to Metattack. Please refer to the Appended Experiments section of joint response above for details.

Weakness 4: Presentation.

• More details about graph distillation We can only add an introduction about offline and online graph distillation models to the appendix due to the length limit of main text.
• A pseudo-code By aggregating the losses of the MLP and GNN components to derive an overall loss term loss, then invoking loss.backward(), the PROSPECT training procedure resembles optimizing a solitary model, except that the MLP and GNN each have their own optimizers and QACA scheduler. If the reviewer feels necessary, we can add a pseudocode in the appendix.

Question 1: Training time. The MLP, GCN and SAGE can be formulated as $H=XW$, $H=AXW$ and $H=XW_1+AXW_2$ , respectively. And the basic operations to build them are $Z=WX$ and $H=AZ$. Han et al. [3] have reported the forward and backward time of these two basic operations on serveral graphs. We extracte the data on Arxiv from the time comparison Tabel 1 in [3] into Table B below. According to the snippet, we can roughly estimate the training time of PROSPECT (that comprises one SAGE and one MLP), which shows that the additional training overhead incurred by PROSPECT over SAGE is almost negligible. Moreover, in the supplemented GR-BCD attack experiments on Arxiv (see the joint response), we report the training times of PROSPECT and GARNET. These results show that the training overhead of PROSPECT is almost the same as using GCN alone, and much lower than GARNET.

Table B: Forward and backward times (ms). The first two rows are from Table 1 of [3], and the last two rows are the estimations based on the first rows.

• The benefits of GNN-to-MLP distillation.

Prior works, e.g., GLNN,first train a GNN teacher, then the GNN-to-MLP direction distillation is leveraged to transfer the knowledge from a pretrained GNN to a student MLP for fast inference. As shown by the clean accuracy results in Table 2, GLNN (i.e., GNN-to-MLP distillation) cannot consistently improve the teacher SAGE (on heterophilic graphs) but succeeds in boosting the student MLP. That is GNN-to-MLP distillation is important to get a decent MLP w.r.t. clean accuracy. The observation 2 in Appendix G.2.2 have revealed that GLNN often exceeds an alone SAGE teacher w.r.t. adversarial robustness, meaning that GNN-to-MLP distillation can sometimes slightly mitigate the poisoning attacks.

• PROSPECT incorporates both GNN-to-MLP and MLP-to-GNN distillation.

Our PROSPECT simultaneously performs both GNN-to-MLP direction distillation and MLP-to-GNN direction distillation to jointly learn decent GNN and MLP. While the benefits of GNN-to-MLP distillation are shown by the above discussion, the benefits of MLP-to-GNN distillation is supported by Theorem 1. The goal of PROSPECT is to merge the knowledge from both MLP and GNN sides via these two distillation directions. Such knowledge fusion brings about desired effects, such as the robustness and adaptability to heterophily.

• How PROSPECT excels GLNN and SAGE against (structure) attacks? Substantially by MLP-to-GNN distillation.

  As stated by the paragraph between Remark1 and Remark2 (at p.5) and discussed by Observation 3 in Appendix G.2.2, the Prospect Condition is usually met for node $i$ under successful structure attacks that drastically degrade the SAGE performance but have no influence on the MLP due to its independence to graph structure.

  One thing worth noting is that for the attacked node $i$, the MLP does NOT need to correctly classify it to be a good teacher because any successful structure attacks can always significantly decrease the SAGE classificaiton score on the ground-truth class $c$ of node $i$ such that even an MLP can output a higher score on class $c$. This makes the defense mechanism of PROSPECT more applicable.

• How PROSPECT excels GLNN and SAGE against heterophily? By mutual distillation.

  On one hand, as shown by Table 2 (at p.8), MLP can have decent performance on heterophilous graphs. On Texas and UAI, MLP even outperforms SAGE, meaning that MLP has some useful information to exploit. On the other hand, given their respective emphases on node attributes and topological structures, MLPs and GNNs are very likely to exhibit divergence in their correct prediction test sets V_{mlp} and V_{gnn}. So the union of these two sets (i.e., the knowledge fusion of MLP and GNN) V_{union} could lead to a larger correct prediction set than alone MLP or alone GNN. We have observed this phenomena across all clean and attacked (LLC) datasets used in the paper. Owing to the space limit, we only show the case on clean datasets in Table A. With the offline procedure, the SAGE teacher in GLNN can never acquire the knowledge from MLP. In contrast, the mutual disitllation mechanism of PROSPECT makes it possible to merge the knowledge from both GNN and MLP sides, and this is why PROSPECT excels alone MLP/SAGE and GLNN in clean (heterophily) accuracy.

According to the above analysis, the improvement of PROSPECT over GLNN (solely based on GNN-to-MLP distillation) and alone GNN results from the introduction of the neglected MLP-to-GNN distillation and the knowledge fusion achieved through mutual interaction.

Table A: Test Acc. (%) on the correct test sets of MLP and GNN, and the union correct set, with seed=15

Dear Reviewer 9crP,

We really appreciate your comments. We hope our point-to-point response can address your concerns.

Weakness 1: "Missing relevant defense models for evaluation."

We thank the reviewer for the reminder and add GPRGNN [1] GARNET [2] baselines. GARNET is indeed the master of current graph purification methods, but its scalability is limited by the (truncated) SVD decomposition and is weaker than PROSPECT, as shown by the supplementary experiments (see Section Appended Experiments/Arxiv attacked by GR-BCD of the joint reponse).

Weakness 2: "Missing adaptive attack results."

We explain in the Concerns about joint, injection and adaptive attacks/Adaptive attacks section of joint response why the adaptive attack test is missing and add the experiments with the black-box unit test datasets provided by Mujkanovic et al. [3].

Weakness 3: "The heterophilous datasets used in this work are known to have some critical issues."

We thank the reviewer for pointing out this critical issue. After seeing the comments, we tried to make attack datasets with the dataset proposed in [4], but due to time and computing resource constraints, we were unable to supplement the corresponding experimental results during the discussion period. Therefore, we hope you can refer more to the results on UAI, a safe heterophilic data set.

Weakness 4: "Missing detailed hyperparameter settings for baselines."

Initially, we observed inconsistencies in current pre-attacked dataset creation paradigms. Specifically, certain works only utilize a sole train/validation/test split, risking less comprehensive evaluations. Hence, we strived to construct over 10 pre-attacked datasets under 4 attack budgets and 5 splits. During baseline hyperparameter tuning however, even abiding by original author guidelines, optimizing across the 5 splits proved challenging for some methods. We are benchmarking existing robust GNN techniques, tuning their hyperparameters accordingly, and will update performances if improvements emerge. Moreover, the diverse pre-processed attack datasets alongside all benchmark outcomes will be publicly disclosed in future endeavors.

Weakness 5: "Claim 3 is too strong."

Thanks for pointing this out, we've narrowed the claims in Claim 3 (now renamed to Remark 3) to SAGE.

Question 1: "Why didn't the authors choose heterophilous GNNs as the surrogate model?"

We also agree with that heterophilous GNNs seems more reasonable, but for the following reasons, we have temporarily compromised. 1) We found that GCN, as a surrogate for heterophilic data, can actually produce effective attacks, so this does not prevent the evaluation of the defense model. 2) Attacking under the unified agent model, namely GCN, can provide a reference benchmark for exploring attack and defense on heterophilic graphs. 3) the MetaAttack and Nettack implementations from current tools, e.g., DeepRobust [5], do not support flexible proxy model settings.

Question 2: "Are baseline models trained with cosine annealing learning rate scheduler?"

The baseline models are not trained with cosine annealing. The performance improvement of PROSPECT mainly comes from the knowledge fusion of GNN and MLP sides. QACA works by solving the knowledge conflict problem in the fusion process but it never brings additional knowledge to one alone GNN or MLP. That is, training SAGE and MLP individually with cosine annealing does not bring additional knowledge and thus is not necessary.

[1] E. Chien, et al., “Adaptive Universal Generalized PageRank Graph Neural Network,” ICLR'2021.

[2] C. Deng, et al., “GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks,” LoG'2022.

[3] F. Mujkanovic, et al., “Are Defenses for Graph Neural Networks Robust?,” NeurIPS'2023.

[4] O. Platonov, et al., “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?,” ICLR'2023.

[5] Y. Li, et al., "DeepRobust: A Platform for Adversarial Attacks and Defenses," AAAI' 2021.

Dear Reviewer GM8H,

We really appreciate your positive comments. We hope the response can address your concerns and clarify our contribution.

Weakness 1: Limited novelty and absence of design tailored to GNN.

In the joitn response at the top of the page, we reiterate and discuss the contribution and broader impact of our work in the Contributions section, hoping that the discussion can solve your concerns.

Question 1: More attack scenarios.

Following your suggestion, we have evaluated PROSPECT with 4 other kinds of attacks [1,2,3,4], including both untargeted and targeted ones. (The details of these new experiments are provided in Section Appended Experiments of the joint response.)

Question 2: More backbones.

We absolutely agree with your opinion and plan to conduct relevant experiments. However, due to time constraints, we deeply regret that we are unable to complete the experiments and provide results during the discussion period.

[1] D. Zügner, A. Akbarnejad, and S. Günnemann, “Adversarial Attacks on Neural Networks for Graph Data,” KDD'2018.

[2] M. Ju, Y. Fan, C. Zhang, and Y. Ye, “Let Graph Be the Go Board: Gradient-Free Node Injection Attack for Graph Neural Networks via Reinforcement Learning,” AAAI'2023.

[3] F. Mujkanovic, S. Geisler, S. Günnemann, and A. Bojchevski, “Are Defenses for Graph Neural Networks Robust?,” NeurIPS'2023.

[4] S. Geisler, et al., “Robustness of Graph Neural Networks at Scale,” NeurIPS'2021.

Weakness 6:"The presentation of the Theorems in the main part could be improved. It is unclear how the reader should deduce Theorem 1 from Proposition 1&2. Perhaps it would be better to move the propositions to the appendix and instead add a proof sketch to the main part."

We are very sorry that we did not add proof schetch due to page limit. However, we are happy to add a proof sketch summarizing the high-level approach before formally proving Theorem 1, if you think this would further enhance the presentation.

We give the main proof schetch of Theorem 1 and point out how Prop.1 and Prop.2 relate to the proof below.

1. Prop. 1 gives the distribution of processed features $\mathbf{h}$ obtained by feeding the CSBM raw data to a SAGE layer.
2. Prop. 2 gives the ideal optimal decision boundary of the processed featuress $\mathbf{h}$.
3. Based on the gradients of the cross-entropy and KLD losses w.r.t. the SAGE layer parameters, we can get different SAGE weights that output different processed features with and without MLP-to-GNN distillation, denoted by $\mathbf{h}^{kd}$ and $\mathbf{h}$, respectively. In this process, the conclusion of Prop. 1 and some other auxiliary propositons in the appendix are required.
4. Per Prop.2, the optimal decision boundaries of $\mathbf{h}^{kd}$ and $\mathbf{h}$ can be derived. Then we comapre the (expected) distances of $\mathbf{h}_i^{kd}$ and $\mathbf{h}_i$ from their respective optimal decision boundaries (i.e., the mis-classified probabilities).
5. Prove that $\mathbf{h}_i^{kd}$ is more far away from the optimal decision boundary of $\mathbf{h}^{kd}$. And thus the distillation is helpful to SAGE.

As cSBM may be unfamiliar to some readers, keeping the propositions provides context about the data characteristics right before Theorem 1. So perhaps we should keep them before Theorem 1 in the main text. How do you think?

Question 1: "Can the authors please provide a full list of assumptions required for Proposition 1 & 2 as well as Theorem 1?"

Prop. 1 is the probabilistic description of the data generated by the CSBM model and the features obtained after oen SAGE layer. Prop. 2 gives the best decision boundary for the obtained features. Neither of these contains any assumptions per se.

Regarding Theorem 1, the assumption about data is that the raw graph data are generated by a CSBM or aCSBM model. Another assumption implicit in the proof is that the learning rate is not too large and the number of nodes in the graph is not too small. As mentioned in the example on page 23, this is easily satisfied by almost all popular (and real-life) graph datasets and learning rate settings.

Question 2: "Could the theory be extended to further data-generating distributions like Barabasi–Albert?"

We examined the Barabasi–Albert data-generating distribution described in [D]. The biggest difference from the graph data generator used in our paper is probably that it does not contain node features, whereas Theorem 1 illustrates the benefits of MLP-to-GNN distillation by examining the distance between node features and the optimal decision boundary. Therefore, it cannot be directly generalized to the data generator you mentioned. Nevertheless, we guess that treating the category probability distribution of each node as its node feature may yield some interesting results with the Barabasi–Albert data-generating distribution.

By the way, the key to generalizing Theorem 1 to other data-generating distributions is that you need to know and derive the distribution of node features after SAGE convolution under "different matrices of strictly positive affinities for vertices of different labels" [D].

[A] F. Mujkanovic, et al., “Are Defenses for Graph Neural Networks Robust?,” NeurIPS'2023.

[B] Li et al., "Adversarial attack on large scale graph," IEEE TKDE, 2021.

[C] Geisler et al., "Robustness of Graph Neural Networks at Scale," NeurIPS'2021.

[D] Community recovery in a preferential attachment graph, Hajek and Sankagiri, IEEE TIT, 2019.

Dear Reviewer JnCK,

We really appreciate your comments. We hope our point-to-point response can address your concerns.

Weakness 1: Overstating claims.

We apologize that there were overstated claims in our original manuscript. We have re-examined the paper, eliminating overstated claims. We understand the importance of avoiding overstatements in academic writing, and your feedback has helped us improve the manuscript in this regard. Please let us know if there are any remaining issues with overclaiming and we will be happy to address them.

Weakness 2: “The authors should discuss this and evaluate w.r.t., e.g., a joint attack on the graph structure and node features.”

Please refer to the discussion section Concerns about joint, injection and adaptive attacks in the joint response.

Weakness 3: “The empirical evaluation is insufficient.”

We explained in the Concerns about joint, injection and adaptive attacks/Adaptive attacks section of joint response why the test with an adaptive attack is not performed at the first place. Due to the adaption issue pointed out here and urgent discussion deadline, we can only conduct part of black box unit tests provided by [A]. The experiment results can found in Section Appended Experiments of the joint response.

Weakness 4: “The authors claim scalability. Thus, they should compare to other works using large graphs.”

Although we have made every effort to supplement all experiments, time and computational constraints prevent us from conducting experiments on data beyond the pre-made large-scale perturbation datasets. We are so sorry that we only directly adopt the pre-attacked arxiv dataset from [C] and did not make pre-attacked datasets with the method from [B]. Nonetheless, we believe it is necessary to briefly introduce [B] in our paper.

Weakness 5.1: “Just because an MLP is robust w.r.t. structure perturbations does not imply it is useful. Moreover, there might be an interaction between the GNN and MLP.”

You did capture the key point of PROSPECT - the naive interactive behavior resulted from simply combining GNN and MLP for mutual distillation will cause the mutual distillation between these two types of heterogeneous models to fail, as stressed out in the Contributions/The key to future mutual distillation section of joint response.

However, it should be noted that the performance gain of PROSPECT mainly comes from the fusion of the respective knowledge of GNN and MLP (regardless of attack or clean scenarios), so its theoretical performance has nothing to do with a specific optimization method like QACA.

We think that the knowledge conflict caused by the model heterogeneity locks the performance of PROSPECT, and QACA is just the key to this lock.

Weakness 5.2: “If the authors make a claim about evasion (e.g. second last line of page 3), they should also verify that empirically.”

We apologize for misleading you with the imprecise statement on page 3. In fact, we want to say that PROSPECT-MLP trained by the PROSPECT framework does not require graph structure for inference, so it is completely robust to (structure) evasion attacks. Considering that both Prospect-MLP and Prospect-SAGE can be deployed for inference, we attribute this property to the PROSPECT framework.

By the way, the performance of PROSPECT-MLP under evasion structure attacks is actually the same as that in the clean accuracy table, i.e., Table 2 of our paper.