# CRank: Reusable Word Importance Ranking for Text Adversarial Attack
## 5 Experiment and Evaluation
### Performance  
We analyze the effectiveness and the computational complexity of seven methods on the two models on three datasets as Table 8 demonstrates. In terms of the computational complexity, \(n\) is the word length of the attacked text. Classic needs to query each word in the target sentence and, thus, has a \(O(n)\) complexity, while CRank uses a reusable query strategy and has a \(O(1)\) complexity, as long as the test set is big enough. Moreover, our greedy has a \(O(n^{2})\) complexity, as with any other greedy search.  
In terms of effectiveness, our baseline classic reaches a success rate of 67% at the cost of 102 queries, while CRank(Middle) reaches 66% with only 25 queries (increases 75%  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **SST-2** & **IMDB** & **AG News** \\ \hline CNN & 82.68\% & 81\% & 90.8\% \\ LSTM & 84.52\% & 82\% & 91.9\% \\ \hline \hline \end{tabular}
\end{table}
Table 6: Accuracy of Target Models.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Metric** & **Explanation** \\ \hline \% Success & Successfully attacked examples/Attacked examples. \\ \% Perturbed & Perturbed words/total words. \\ Query Number & Average queries for one successful adversarial example. \\ \hline \hline \end{tabular}
\end{table}
Table 7: Evaluation Metrics.  
efficiency, but has a 1% drop of the success rate, compared with classic). When we introduce greedy, it gains an 11% increase of the success rate, but consumes 2.5 times the queries. Among the sub-methods of CRank, CRank(Middle) has the best performance, so we refer to it as CRank in the following paper. As for CRankPlus, it has a very small improvement over CRank and we consider that it is because of our weak updating algorithm. For detailed results of the efficiency of all methods, see Figure 2; the distribution of the query number proves the advantage of CRank. In all, CRank proves its efficiency by greatly reducing the query number while keeping a similar success rate.  
In Table 9, we compare results of classic, greedy, CRank, and CRankPlus against CNN and LSTM. Despite greedy, all other methods have a similar success rate. However, LSTM is harder to attack and brings a roughly 10% drop in the success rate. The query number also rises with a small amount.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Method** & **\% Success** & **\% Perturbed** & **QN** & **CC** \\ \hline Classic & 66.87 & 11.81 & 102 & \(O(n)\) \\ \hline Greedy & 78.30 & 11.41 & 253 & \(O(n^{2})\) \\ CRank(Head) & 63.36 & 12.90 & 28 & \(O(1)\) \\ CRank(Middle) & 65.91 & 12.76 & 25 & \(O(1)\) \\ CRank(Tail) & 64.79 & 12.60 & 26 & \(O(1)\) \\ CRank(Single) & 62.94 & 13.05 & 28 & \(O(1)\) \\ CRankPlus & 66.09 & 12.84 & 26 & \(O(1)\) \\ \hline \hline \end{tabular}
\end{table}
Table 8: Average results. “QN” is query number. “CC” is computational complexity.  
Figure 2: Query number distribution of classic, greedy, CRank, and CRankPlus.  
We also demonstrate the results of attacking various datasets in Table 10. Such results illustrate the advantages of CRank in two aspects. Firstly, when attacking datasets with very long text lengths, classic's query number grows linearly, while CRank keeps it small. Secondly, when attacking multi-classification datasets, such as AG News, CRank tends to be more effective than classic, as its success rate is 8% higher. Moreover, our innovated greedy achieves the highest success rate in all datasets, but consumes most queries.