SheAttack: A Silhouette Score Motivated Restricted Black-Box Attack on Graphs

Thanks for your time and efforts!

Reply to the Weaknesses

1. The quality of clusters would be a concern in practice. However, stand at the attacker side, the quality of features would lead to a somewhat chicken and egg paradox. If the cluster performance is extremely undesirable, or there exists huge feature noise, the defenders will not be able to achieve desirable classification performance, and therefore no need for attacks. Note that the defender have no access to inject controllable noise in most cases. If so, the results of all current attack methods would be unreliable.
   In our empirical results, Kmeans achieves acceptable clustering and lead to successful attacks in most graphs. As we discussed in Section 7, improving the quality of clusters is feasible. One could adopt Graph Constrative Learning, advanced or dataset-tailored clustering methods to achieve better cluster performance. And as we discussed in Appendix F.2, such modifications would lead to even better performance for SheAttack.
2. Attacking node features would be an opportunity for further improvement. It can be easily incorporated into our framework by updating $X$ and $A$ simultaneously through the gradients. We do not focus on feature attacks for more fair evaluation as most RBAs only focus on structural attacks.
3. It is hard to derive general theoretical results for an RBA to surpass the others in all aspects. In our paper, we pay attention to heterophily, which has been ignored in previous RBA design. We theoretically verify that SheAttack is suitable for both homophilic and heterophilic settings, which is in accordance with the empirical results in synthetic datasets.
4. The novelty of our methods is that we get rid of the homophily assumption and costly spectral techniques. We try to induce the graph into a more general dilemma, where nodes are of less distinguishablility from the perspective of the class-wise distance. The class-wise distance is more fundamental, yet rarely explored in graph adversarial attacks. We provide theoretical interpretation for previous losses, and propose a more general attack framework.
5. The modification in $b$ is to enlarge the scope of the attacker to fit in practical attack scenario. When considering just clustering, Silhouette Score is good enough. But during attacks, the Silhouette Score without modifications tend to ignore opportunities. The modifications do not aim to push intra-class nodes further apart, but enlarge the feasible sets during edge flipping. The benefits are verified empirically in Table 5 in Section 6.
6. We include experiments with different $\Delta$ in Appendix F.5, with the perturb ratio being 10%, 15% and 20%. SheAttack constantly hold promising performance.
7. Thanks for pointing the typos out. We will ensure the consistency of notations in the revised version.
8. The RL-based models mentioned in the related works are RL-S2V and ReWatt. RL-S2V consider target-attacks, and is of extremely high time costs compared to loss-based methods. ReWatt explores graph-level attacks, and only focus on rewiring attacks which are different to most RBA settings.
   So we decide to not include them for the setting differences and efficiency issues following previous loss-based RBAs.

Thanks for your insightful feedbacks!

Reply to the Weaknesses

1. While perturb ratio above 0.10 might seem unrealistic, a sad fact about RBAs is that it could be extremely hard to find a powerful attack if the perturb ratio is low. Take Cora_ml with perturb ratio 0.05 for example, the results against a two-layer GCN are summarized below. | Attack | Evasion | Poison | |----------|----------|----------| | Clean | 85.94 | 85.94 | | Random | 84.79 | 84.72 | | DICE | 84.09 | 83.82 | | SPAC-A |84.97 | 84.69 | | GFAttack| 84.83 | 83.92 | | PEEGA | 82.49 | 81.56 | | She | 81.95 | 80.77 | | She-A | 82.07 | 80.92 |

While the results of SheAttack is promising, the performance drop is marginal for all RBAs. Based on our discussion in Section 7, we highly suspect that the attack performance of white-box attacks would be similarly marginal without utilizing split information. So following the settings of previous RBAs, we set the perturb ratio in most experiments equal of higher than 10%. We include experiments with perturb ratio 0.15 in Appendix F.5.

2. Unnoticability. In our paper, we do not focus on addressing unnoticability for the following reasons.

• The requirements of unnoticability is varied. Besides of the degree shift mentioned, there are homophily shift [1] and spectral shift [2] that might also be noticeable for the defender. It is hard for an RBA to tackle unnoticability from all perspective while staying effective.
• Difficulties for evaluation. For example, baselines like DICE and PEEGA are based on utilizing homophily shift for performance improvement. So it could be meaningless to impose unnoticability constraints about homophily for them. Based on our knowledge, it is still hard to ensure a fair evaluation setting with reasonable unnoticability constraint.

Despite the above difficulties, SheAttack could incorporate plug-in unnoticability designs if necessary. In the cases where a large degree shift is not allowed, we could include a degree-shift loss into the loss term as a penalty: $L_{atk} = L_{she} + \lambda L_{shift} - \gamma L_{deg-shift}$ We test the performance of She-Comb and She-Comb with degree constraints in Cora-ML with 20% perturb ratio. The result is:

While the attack performance slightly drops, the degree shift is almost eliminated.

3. Yes, RBAs do not allow the attacker to have access to any node labels. For example, in a social network, the attacker could hack the member accounts, but do not know the downstream tasks of defenders (e.g., whether they predict the genders or regions of members). In the experiments, we have include a self-atk attack, which can be seen as GRBCD trained on surrogate labels. The attack aims to make the output of the attacked graph different to clusters as labels, but the performance is not satisfactory. We will include a more detailed illustration of the RBA setting in the Appendix in the revised version.

Reply to the Questions

We have included the reply to questions in the Reply to the Weaknesses. If you have any further questions, we are willing for more discussion.

[1] Chen, Yongqiang, et al. "Understanding and improving graph injection attack by promoting unnoticeability." In ICLR 2022.

[2] Lin, Lu, Ethan Blaser, and Hongning Wang. "Graph structural attack by perturbing spectral distance." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.

Thanks for your detailed feedback!

Reply to the Weakness:

1. PRBCD / GRBCD are white-box attacks that utilize training-test spilts, architecture of victim models, and node labels. The results of PRBCD and GRBCD would be extremely strong with these extra information. Therefore, we do not compare our attack with these white-box attacks following previous literature addressing RBAs. We include the shuffled version of them that dismiss the splits information in Table 6. Without the splits information, PRBCD/GRBCD suffers from severe performance drop even with the knowledge of ground-truth node labels.

We further test PRBCD and PRBCD-shuffle on ogbn-arxiv. We see that if the split is shuffled, PRBCD as white-box attacks is just slightly better than SheAttack although it utilizes node labels.

2. We carefully go through the baseline the reviewer mentioned, but it seems that the paper is about heterogenous graphs, which are graphs of multiple edge types. The heterophily concept we adopt in the paper is about the preference of connections in edges.
   Nevertheless, we test the performance of SheAttack against a robust heterophilic baseline EvenNet [1] on the synthetic datasets with perturb ratio being 20%. The results are summarized below. SheAttack still perform well against the robust defense model.

3. We have included the time efficiency on cSBM datasets and ogbn-products in Appendix F.6. If you are interested in the time efficiency of other datasets, we are willing for more discussion.

[1] Lei, Runlin, et al. "Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks." Advances in Neural Information Processing Systems 35 (2022): 4694-4706.

Thank you for your time and efforts!

Reply to the Weakness:

1. For the hyperparameter $k$, we have included a sensitivity analysis in Appendix F.3. Our results show that our method is not sensitive to it, and we provide suggestions for choosing a proper $k$ in practice. For the hyperparameter $\lambda$, we only tune it in within a small range, which is [0, 1.0, 5.0]. the result turned out to be desired enough. To sum up, SheAttack is not dependent on well-chosen hyperparameters.
2. On synthetic datasets and homophilic datasets, SheAttack is only inferior to DICE in the homophilic setting, which utilizes ground-truth labels and is not strictly an RBA. On real-world datasets, SheAttack is inferior to baselines in the poison setting in Chameleon and Squirrel. In [1], the authors questioned that the two datasets may face data leakage problems.
   In the filtered Chameleon and Squirrel, the results with 20% the perturb ratio is: | Attack | Chameleon_filtered (Evasion)| Chameleon_filtered (Poison) | Squirrel_filtered (Evasion) | Squirrel_filtered (Poison) | |-------------|-----------------|-------------------|-----------------|-------------------| | Clean | 40.36±2.36 | 40.36±2.36 | 35.47±1.00 | 35.47±1.00 |
   | Random | 35.52±3.44 | 36.50±1.72 | 32.70±2.39 | 35.36±1.55|
   | DICE | 33.00±2.43 | 32.91±2.08 | 28.78±1.38 | 38.81±1.82 | | SPEC | 38.30±2.02 | 37.85±2.43 | 31.22±2.81 | 35.72±0.80 | | GFAttack | 34.44±2.51 | 35.34±4.51 | 32.01±3.10 | 33.88±1.98 | | Self-atk | 39.82±2.48 | 37.13±2.67 | 33.13±3.60 | 35.36±1.64 |
   | PEEGA | 33.00±2.68 | 35.96±2.48 | 29.46±2.02 | 33.53±0.50 |
   | She | 35.78±3.15 | 33.72±2.43 | 28.38±2.55 | 33.24±0.93 |
   | She-A | 36.23±1.64 | 36.68±1.80 | 28.67±1.39 | 32.91±2.33 |

We see that SheAttack holds best performance in the three of four new heterophilic settings. A recent study [1] points out that these two datasets also exhibit a mixing pattern of homophily and heterophily, which would be complex for both attackers and defenders. As a result, no methods show general superiority in these two datasets.

3. Thanks you for your advice in the writings. For the citations and writing, we will adopt a unify format and carefully revise the spellings. For the definition about poison attacks and evasion attacks, we only include a brief introduction due to space limitations. We adopt the most common definition for them as previous graph adversarial literature, and we will include a detailed explanation to it in the Appendix for the readers' convenience in the revised version.

Reply to the Questions:

1. In Figure 3, GRBCD and RandAttack exhibits almost the same Modified Silhouette Score at epoch 0 when evaluated given the labels (warm-colored) and clusters (cold-colored). The slight difference could be due to visualization issues. We would appreciate that if more details about the question could be provided.
2. In the experiments against ogbn-arxiv and ogbn-products, we set the number of GNN as 3 following ogb-example. Based on the result in our paper, the performance of SheAttack is still promising.

[1] Platonov, Oleg, et al. "A critical look at the evaluation of GNNs under heterophily: are we really making progress?." In ICLR 2023.

[2] Mao, Haitao, et al. "Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?." In NIPS 2023.