TestRank: Bringing Order into Unlabeled Test Instances for Deep Learning Tasks
Year: 2021

Abstract:
Deep learning (DL) systems are notoriously difficult to test and debug due to the lack of correctness proof and the huge test input space to cover. Given the ubiquitous unlabeled test data and high labeling cost, in this paper, we propose a novel test input prioritization technique, namely TestRank, which aims at revealing more model failures with less labeling effort. TestRank brings order into the unlabeled test data according to their likelihood of being a failure, i.e., their failurerevealing capabilities. Different from existing solutions, TestRank leverages both intrinsic and contextual attributes of the unlabeled test data when prioritizing them. To be specific, we first build a similarity graph on both unlabeled test samples and labeled samples (e.g., training or previously labeled test samples). Then, we conduct graph-based semi-supervised learning to extract contextual features from the correctness of similar labeled samples. For a particular test instance, the contextual features extracted with the graph neural network and the intrinsic features obtained with the DL model itself are combined to predict its failure-revealing capability. Finally, TestRank prioritizes unlabeled test inputs in descending order of the above probability value. We evaluate TestRank on three popular image classification datasets, and results show that TestRank significantly outperforms existing test input prioritization techniques. Our code is available at: https://github.com/cure-lab/TestRank.

heading: 1 Introduction
text: Deep learning (DL) systems are prone to errors due to many factors, such as the biased training/validation dataset, the limitations of the model architecture, and the constraints on training cost. It is essential to conduct high-quality testing before DL models are deployed in the field; otherwise, the behaviors of DL models can be unpredictable and result in severe accidents after deployment. However, the cost of building test oracles (i.e., the ground-truth output) by manually labeling a massive set of test instances is prohibitive, especially for tasks requiring experts for accurate labeling, such as medical images and malware executables.
To tackle the above problem, various test input prioritization techniques [Feng et al., 2020, Byun et al., 2019, Shen et al., 2020] are proposed to identify ‘high-quality’ test instances from a large amount of unlabeled data, which facilitates revealing more failures (e.g., misclassification) of the DL model with reasonable labeling effort. These methods try to derive the failure-revealing capability of a test instance with its intrinsic attributes extracted from the responses of the model under test (e.g., the softmax-based probabilities given by the target DL model to this specific input). DeepGini [Feng et al., 2020] feeds the unlabeled data to the target DL model and calculates confidence-related scores based on the model’s output probabilities to rank the unlabeled test cases. Test cases with nearly equal probabilities on all output classes are regarded as less confident ones and are likely to reveal
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
model failures. Similarly, [Byun et al., 2019] use the uncertainty score obtained from MC-Dropout for test input prioritization. Multiple-boundary clustering and prioritization (MCP) [Shen et al., 2020] considers both the output probabilities and the balance among each classification boundary when selecting test cases. All existing works try to identify instances near the decision boundary and prioritize them. However, we argue that near-boundary instances are not necessarily failures, especially for well-trained classifiers with high accuracy. Also, as failures can be far from the decision boundary, existing methods could fail to reveal these remote failures.
To estimate a test instance’s capability in revealing failures, in addition to the intrinsic attributes mentioned above, there is another type of information: the known classification correctness of labeled samples (i.e., training samples and previously tested samples) and their relationship to the unlabeled instance. This information provides extra insight into the target model’s behavior. Such data is already known, and it provides contextual information that reflects the corresponding inference behaviors of the target model for a set of similar instances.
This work presents a novel test input prioritization technique, namely TestRank, for DL classifiers. TestRank exploits both intrinsic and contextual attributes of test instances to evaluate their failurerevealing capabilities. Based on the intuition that similar inputs are usually associated with the same classification results, we propose to use graph neural networks (GNNs) [Kipf and Welling, 2017] to summarize the neighboring classification correctness for each unlabeled instance into contextual attributes. GNNs have been well-studied and valued for their relational inductive bias for extracting graph information. Our method, TestRank, constructs a similarity graph on both unlabeled and labeled instances and apply the semi-supervised GNN learning to extract the contextual attributes. After that, we aggregate intrinsic (such attributes are extracted from the input samples without considering their neighbors) and contextual attributes with a neural-network-based binary classifier for test input prioritization.
The contributions of our work are as follows:
• To the best of our knowledge, TestRank is the first work that takes the contextual information from the target DL model into consideration for test input prioritization.
• We propose constructing a similarity graph on both labeled and unlabeled samples and training a graph neural network to extract useful contextual attributes from the contextual information for these unlabeled instances. We also present approximation techniques to reduce its computational complexity with minor impact on the performance of TestRank.
• We propose a simple yet effective neural network that combines the intrinsic attributes and contextual attributes of unlabeled test instances for their failure-revealing capability estimation.
We empirically evaluate TestRank on three popular image classification benchmarks: CIFAR-10, SVHN, and STL10. The results show that our method outperforms the state-of-the-art methods by a considerable margin.

heading: 2 Test Input Prioritization
text: Let us use f : X → Y to represent the given target DL model, where X and Y are the input and output space, respectively. For effective testing1, the debugging center needs to perform test input prioritization, i.e., select a certain number of test instances from the large unlabeled test instance pool that can reveal as many failures as possible. Later, these failures are fed back to the training center for failure analysis and model repair. We define the model failures as follows:
Definition 1. DL Model Failure. A failure of the DL model can be uncovered by the test instance x if the predicted label f (x) is inconsistent with its ground truth label yx, namely f (x) , yx.
Formally, the debugging center selects and labels b test cases XS (|XS | = b) from the unlabeled test instance pool XU . The objective of test input prioritization is to maximize the detected failures:
max |{x| f (x) , yx}|,where x ∈ XS and |XS | = b. (1) 1Please note that, we focus on testing the functional correctness of the DL model, and we assume the collected
testing data are clean samples instead of maliciously generated ones.
Different solutions are proposed to quantify the failure-revealing capability of unlabeled instances. DeepGini [Feng et al., 2020] proposes to evaluate a single test instance via the DL model’s final statistical output: f (t) = 1 − ΣNi=1 p2t,i, where pt,i is the predicted probability that the test case t belongs to the class i. Given the sum of pt,i is 1, impurity function f (t) is maximal when all pt,i values are equal. DeepGini also adopts the neuron coverage criteria proposed in DeepXplore [Pei et al., 2017] and DeepGauge [Ma et al., 2018] in test input prioritization, and the result shows that the impurity-based selection is much better than coverage-based selection.
Instead of evaluating the overall likelihood of failure for all classes, Multiple-Boundary Clustering and Prioritization (MCP) proposes to evaluate it for each pair of classes individually [Shen et al., 2020]. In this way, test instances can be evenly selected for each class pair and the failure cases are investigated at the finer granularity. Besides these metrics, [Byun et al., 2019] also propose to measure the likelihood of incorrect prediction by the uncertainty of the model’s output, which reflects the degree to which a model is uncertain about its prediction. In practice, evaluating uncertainty requires the task DL model to be a Bayesian Neural Network [Richard and Lippmann, 1991, Neal, 2012] or containing a dropout layer for approximation [Gal and Ghahramani, 2016].
Besides examining the DL model’s final outputs, [Kim et al., 2019] proposes two surprise adequacy (SA) criteria that make use of the target DL’s internal outputs (e.g., the activation traces). They are Likelihood-based Surprise Adequacy Coverage (LSA) and Distance-based Surprise Adequacy Coverage (DSA). LSA and DSA measure the likelihood or distance of an unlabeled instance to the training instances, respectively. Test samples with higher SA values are preferred in testing.
To sum up, all existing methods use the target model’s outputs to one input, i.e., its intrinsic attributes, for its failure-revealing capability estimation. In contrast, we make use of both intrinsic and contextual attributes of an instance for better estimation (see later sections for details).
3 TestRank
3.1 Motivation
The failure-revealing capability of an unlabeled test input is closely related to its attributes for the DL model under test. In this work, we distinguish two kinds of attributes for an unlabeled instance: the intrinsic attributes and the contextual attributes.
We define the intrinsic attributes of an input as the output responses assigned by the target DL model to this specific input. It could be, for example, the predictive output distribution of the input from the target DL model, reflecting the sentiment derived from the computation performed by the target model [Byun et al., 2019]. This kind of attributes is adopted by existing test input prioritization approaches [Feng et al., 2020, Shen et al., 2020, Byun et al., 2019]. Note that we define such attributes as ‘intrinsic’
because they are extracted from inputs without considering their context, i.e., the classification correctness of its similar instances.
In contrast with the intrinsic attributes, the contextual attributes provide a deeper insight into the target model for the unlabeled samples: the contextual attributes for an unlabeled sample summarize the classification correctness of similar and labeled samples. For a particular test instance, such contextual attributes are useful and complementary to the intrinsic attributes.
An illustrative example is shown in Figure 1, wherein we visualize the behavior of a two-class classifier on the unlabeled test data and historically labeled data distribution. The blue region includes the instances that are near the decision boundary. Intuitively, the classifier is uncertain about the data when data is near the decision boundary and is likely to misclassify it. Existing
works [Shen et al., 2020, Feng et al., 2020, Byun et al., 2019] propose various indicators (e.g., confidence/uncertainty/surprise scores) to help identify the near-boundary instances. However, the near-boundary instances are not necessarily failures, and some of them can be correctly classified by a well-trained classifier. What is worse, such testing approaches fail to capture the failures lying far from the decision boundary (i.e., remote failures, shown in the red region in Figure 1), because DL models usually output high confidence (or low uncertainty) for these inputs. These failures may be caused by limited model capacity, insufficient training data, etc.
Our key insight is that we can use the contextual information (e.g. the classification correctness of similar labeled samples) to help locate both near-boundary and remote failures. The usefulness of the contextual information is due to the local continuity property [Bishop, 2006], which means that inputs close in the feature space share similar prediction behavior, e.g., classification results from the target model. As shown in Figure 1, some already labeled data, whose classification correctness is already known, surround the unlabeled data. If an unlabeled instance is close to already falsely classified data, under the local continuity property, it is likely that this instance is also a model failure. This property motivates us to extract the contextual attributes for an unlabeled instance from its neighboring labeled data. By combining the extracted contextual attributes with the intrinsic attributes, we expect to achieve better failure-revealing capability estimation.

heading: 3.2 Overview
text: Figure 2 shows the overview of TestRank, which consists of two attribute extraction paths for the final failure-revealing capability estimation:
1. Path A: intrinsic attributes extraction. Given a pool of unlabeled inputs XU , we use the target DL model f to extract the intrinsic attributes em for each input. More precisely, we collect the output logits (i.e., vectors before the so f tmax layer) from the DL model as em.
2. Path B: contextual attributes extraction. First, we use a feature extractor to map the original data space into a more compact feature space with good local continuity property. Then, we create a similarity graph (i.e., k-Nearest Neighbor Graph) based on the obtained feature vectors and their corresponding classification correctness, if any, from both unlabeled data pool XU and labeled data pool XL (e.g. training set and previously labeled test samples). Last but not least, the graph-based representation learning technique is applied to extract the contextual attributes ec for each unlabeled instance. The details are elaborated in Sec. 3.3.
After attributes em and ec are extracted, we combine them together via a Multi-Layer Perceptron (MLP) (see Sec. 3.4 for details). The MLP is responsible for predicting the failure-revealing ability for unlabeled test instances. At last, these instances are ranked according to their failure-revealing capability, and the top ones are selected under the given labeling budget.
As intrinsic attributes extraction is straightforward, we discuss the path B and how to combine path A and B in detail in the following subsections.

heading: 3.3 Contextual Attributes Extraction
text: We represent the contextual information from the DL model as a set of labeled inputs XL and the corresponding classification correctness YL ∈ {0, 1}, where correctly classified inputs are labeled as 0 and misclassified ones are labeled as 1. Given the contextual information, our goal is to extract the contextual attributes for each unlabeled test instance x ∈ XU . However, extracting contextual attributes from labeled and unlabeled data is a non-trivial task because of the following reasons.
Algorithm 1: GNN-based Contextual Attributes Extraction Input: Input samples XU ∪ XL, Correctness of labeled samples YL, Number of neighbors k, Feature
extractor fetr, number of GNN layers M, number of training epochs. Output: Contextual attributes Ec for XU
1 X = fetr(XU ∪ XL) # Extract compact representation; 2 Edge = knn_graph(X, k). # KNN Graph construction; 3 Ã = Edge + IN , D̃ = ∑ j Ãi, j; 4 H0 = X; 5 for number of training epochs do 6 for l = 0, 1, . . . ,M − 1 do 7 Hl+1 = σ(D̃− 12 ÃD̃− 12 HlΘl), 8 end 9 loss = CrossEntropyLoss(HM ,YL);
10 Update Θ; 11 end 12 Ec = HM−1[index of Xu] # extract the representation from the M − 1th GNN layer; 13 return Ec;
First, it is well-known that the real data, especially image data, usually locates in high-dimensional space, wherein the underlying data distribution will live on complex and non-linear manifold embedded within the high-dimensional space [Bishop, 2006]. Therefore, constructing the relationships between different instances is difficult. To address the challenge, we adopt the representation learning process [Grill et al., 2020, van den Oord et al., 2018, Chen et al., 2020, He et al., 2020], which map the raw data into a compact feature space with better local continuity property, such that inputs close in the feature space share similar classification results. Thus, in the feature space, the proximity between inputs can be measured with simple distance metrics (e.g., L2, cosine).
Second, manually designing protocols to summarize the neighboring classification results is subject to the imperfection of local continuity. Namely, the result is easily affected by the noisy data in the neighboring space. To solve this challenge, we construct a similarity graph based on the labeled and unlabeled data, and then apply the more powerful graph learning technique – graph neural networks (GNN) – for contextual attribute extraction.
The GNN empowers graph embedding learning, as it employs a learnable aggregation and transform procedure [Kipf and Welling, 2017], which exploits the relational inductive-bias that exhibits in the graph structure. It generates a embedding/representation that summarizes the “contextual information” for each input sample, making it easier to separate the correct and misclassified inputs.The contextual attributes extracted by the graph neural network can then be combined with the intrinsic attributes to conduct the better failure-revealing capability estimation (See Sec. 3.4). The contextual attributes extraction process is formally depicted by Algorithm 1.
Feature Vector Representation (Line 1). As the target model is to be tested, its feature extraction quality is not guaranteed. Out of this concern, and to make full use of the labeled and unlabeled data, we choose to use a out-of-shelf unsupervised model for feature space construction.
Among the unsupervised learning techniques, the BYOL [Grill et al., 2020] explicitly introduces local continuity constraint into the learned feature space and shows good results on various downstream tasks. Therefore, we train a BYOL model fetr to extract the features from the raw input images. The data used to train the BYOL model includes both labeled and unlabeled data: (XU ∪ XL), and the resulting feature matrix is denoted as X. Please note that the feature extractor can be replaced by any other well-trained feature extractor with the local continuity property (e.g., SimCLR [Chen et al., 2020] and MoCo [He et al., 2020]).
Similarity Graph Construction and Approximation (Line 2). After the extraction of feature representation, we use the simple distance metric (i.e., cosine) to measure the similarity between any two test instance xi and x j in X: Dist(i, j) = cosine(xi, x j). Based on the distance matrix Dist, we construct a k-NN Graph G, wherein each sample is connected to its top-k most similar samples. The connection is represented by an adjacency matrix A ∈ RN×N , where N is the number of sample in X. The entry Ai j equals 1 if node j is within the k nearest neighbors of node i, and 0 otherwise. The
edge weight matrix of the similarity graph is denoted as Edge, wherein each edge weight in Edge, if exists, is inversely proportional to the corresponding distance Dist:
Edgei j = {
1/Dist(i, j) Ai j = 1. 0 Ai j = 0. i, j ∈ {0, . . . ,N − 1}. (2)
This means that the connection between two nodes, if exists, is weaker if their proximity is large.
Constructing such a k-NN graph is, however, computationally expensive. This is because, calculating the distance between each pair of test instances requires a computational complexity of O(N2), which is prohibitive to scale up to the current massive unlabeled test instances in real applications. Therefore, we propose an approximation method for k-NN graph construction. Our intuition is that, since the target of graph construction is to exploit the failure patterns of the nearby labeled instances for the unlabeled instances, the connections between unlabeled data are less meaningful. Therefore, we propose to only consider the connections among labeled data XL, and the connections between labeled XL to unlabeled data XU . This approximation reduces the cost from O(N2) to O(P2 + PQ), where P and Q stand for the number of data in XL and XU , respectively. Usually, in the real-world scenario, P is much smaller than Q, thereby we could obtain a near-linear graph construction algorithm with complexity O(PQ).
GNN-based representation Learning (Line 3-12). To apply the GNN algorithm, we first initialize the input node representation matrix H0 in the similarity graph G as X. Recall that in each GNN layer, the node representations are propagated between neighbors and aggregated together. Thus, we can obtain the representation in the next GNN layer by:
Hl+1 = σ(D̃− 1 2 ÃD̃− 1 2 HlΘl), (3)
where Ã = Edge + IN , IN is the identity matrix, D̃ = ∑
j Ãi, j, Θl is the trainable weight matrix for the lth layer, σ is an activation function and Hl+1 is the output representation matrix. The propagation and aggregation are repeated for M layers, with the output dimension of the Mth layer is 1 (for binary classification purpose).
Then, for any labeled node xe ∈ XL, we could obtain a cross entropy loss between the GNN output hM and the expected label y ∈ YL (e.g. misclassified or not): Lce = −(ylog(hM) + (1− y)log(1− hM)), where hM denotes probability that xe is misclassified. The model is trained via minimizing the loss for some training epochs (we set it as 600 in our experiment). After that, we apply the trained GNN model (except the last layer) on XU to obtain the Ec (line 12). In this way, the correctness of the neighboring samples could be effectively summarized for each node.

heading: 3.4 Failure-revealing Capability Estimation
text: To properly combine both the intrinsic attributes em and contextual attributes ec for collaborative failure-revealing capability estimation, we formulate the combination function as a simple binary classifier (e.g. a MLP). Specifically, the input to the MLP is a concatenation of em and ec, and the output is the failure-revealing estimation for an test instance. The final failure-revealing probability is produced by applying a sigmoid function S (t) = 11+e−t on the MLP model’s output. We use the labeled instances (XL,YL) to train the MLP in a supervised manner, with an objective of minimizing the binary Cross-Entropy loss. After training, the MLP shall re-weight the importance of intrinsic and contextual attributes and make a final decision by assigning a high probability to a test instance if it is likely to reveal a failure.
Finally, we rank the unlabeled test instances in a descending order based on their failure-revealing capability. Under the given budget, we select the top ones to label and test.

heading: 4 Experiment

heading: 4.1 Setup
text: Datasets. We evaluate the performance of TestRank on three popular image classification datasets: CIFAR-10 [Krizhevsky et al., 2009], SVHN [Netzer et al., 2011], and STL10 [Coates et al., 2011], as shown in Table 1. More elaboration is shown in the Appendix.
There are mainly two parties involved in the model construction process: the training center and the debugging center. Hence, we manually split the dataset into the training center dataset (see the TC column in Table 1) and the debugging center dataset (see the DC column in Table 1). To mimic the practical scenario where the unlabeled data is abundant, we move a portion of training data to the debugging center to create this scenario. In the debugging center, we let a set of test data as labeled ones to represent the historical test oracles, and they are 8K/10K/1.5K for CIFAR-10, SVHN, and STL10, respectively, which are used to train the GNN and MLP model. The rest of the data in the debugging center are left unlabeled. Also, we spare a hold-out dataset (see the HO column), which is used for evaluating the model accuracy.
Target DL model (model under test). As shown in Table 1, we use the popular ResNet and WideResNet architectures as the backbone models [He et al., 2016, Zagoruyko and Komodakis, 2016]. To simulate models of different qualities, for each dataset, we train three DL models with different randomly drawn sub-sets from the training set owned by the training center. For model B and C, the training set are drawn with in-equivalent class weights. After training, we report the accuracy of models on the debugging center’s hold-out dataset THO in Table 1.
Evaluation metric. We propose a new evaluation metric for test input prioritization techniques: Test Relative Coverage (TRC). TRC is defined as the number of detected failures divided by the number of budget or the number of total failures identified by the whole unlabeled test set, whichever is minimal:
TRC = #Detected Failures
min(#Budget, #Total Failures) . (4)
When # budget ≤ # total failures, the maximum number of failures can be identified equals to the budget. When # budget ≥ # total failures, the maximum number of failures can be detected equals to the total number of failures. Therefore, TRC measures how far a test input prioritization technique is to the ideal case.
In practice, under the massive unlabeled data, the performance under a small budget is considered more important than that under a large budget. To provide an insight on the quality of one test input prioritization technique under a small budget, we also provide an ATRC metric: ATRC measures the average TRC values for budget values less than the total failures:
ATRC = 1 N N−1∑ i TRCi, (5)
where TRCi stands for the TRC value under budget bi, bi , b j, and bi ≤ number of total failures. The proposed metrics enhance the ones used by Feng et. al. [Feng et al., 2020] and Byun et. al. [Byun et al., 2019]. They use the percentage of detected failures against the percentage of budget (and an APFD [Do and Rothermel, 2006] value derived based on it) for evaluation. Their metric would produce a small value under a small budget, regardless of how good the prioritization technique is. For example, let’s assume that there are 10,000 unlabeled data, and 2,000 of them can detect model failures. If the budget is 100, the best percentage of detected failures is 5%, and the worst is 0%. Thus, under their metric, the gap between the best and the worst is only 5%. By contrast, TRC enlarges this gap to 100% to better differentiate the ability of different test input prioritization techniques.

heading: 4.2 Comparison of TestRank with Baselines
text: We evaluate TestRank against five representative baselines: Random, DeepGini [Feng et al., 2020] (the state-of-the-art), MCP [Shen et al., 2020], DSA [Kim et al., 2019], and Dropout-uncertainty [Byun et al., 2019]. The details of each baseline are illustrated in the Appendix. For the dropout uncertainty method, we run 1000 times inferences with a default dropout rate of 0.5 (the dropout rate is consistent with the one used in [Byun et al., 2019]). For the DSA method, we collect the activation
traces of the final convolution layer to calculate the surprise score. For our method, we set the number of neighbors for constructing the kNN graph as 100. Also, we use a two-layer GNN with a hidden dimension of 32. More ablation studies are in Section 4.3.
Table 2 compares TestRank with baselines using the ATRC metric. From this table, we have several observations. First, compared with the baselines, TestRank can achieve the highest ATRC values on all evaluated datasets and models. For instance, on CIFAR-10, TestRank can achieve 9.09%, 20.07%, 14.38% higher ATRC values than the best baseline DeepGini for model A, B, C, respectively. Therefore, our method can distinguish the failure-revealing capability of the unlabeled test inputs much more accurately. Second, the testrank-Contextual-Only column shows the result using only the contextual attributes. We observe that the contextual attributes alone can achieve higher effectiveness than random prioritization. For example, for model A on CIFAR-10, the effectiveness of random prioritization is 30.15% while that of the context-only method is 51.39%. We manually check the distribution of failures of model C and find that many failures are centralized on two classes, where the training data is insufficient. This kind of failure is easily detected by the contextual attributes-based method. Hence, the contextual information is helpful. But still, the context attributes alone are not sufficient. The combination of intrinsic and contextual attributes is essential in achieving high accuracy failure-revealing capability estimation.
To show more detailed results, we present the TRC value against every labeling budget in Figure 3. We observe that the TRC values for most curves decrease in the beginning and then increase. The turning point is when # budget = # total failures. When # budget < # total failures, the TRC values decrease because we rank the test instances according to their failure-revealing probabilities. With the budget increases, the selected test cases have a lower average failure-revealing ability, thus the decreased TRC value. When # budget > # total failures, according to the definition of TRC (see Equation 4), the denominator is fixed. The increase in budget will improve the number of detected failures, and hence the TRC value will increase.
Figure 3 shows that our method consistently outperforms baselines, especially when the budget is small. For example, in Figure 3 (a), TestRank improves the prioritization efficiency by around 20% compared to the best baseline when the budget is around 1%. When the budget is rather high (e.g. budget ≥ 80%), the difference between different methods is less obvious because most failures can be selected under the large budget.

heading: 4.3 Impact of TestRank Configurations
text: Feature Extractor. TestRank uses an unsupervised BYOL model trained on both labeled and unlabeled data to extract their features. One may wonder if it can be replaced by a supervised model (e.g., the target DL model). To investigate this, we replace the feature extractor in TestRank with the front layers (we remove the last few linear layers) of the target DL model. The result is shown in the TestRank-TargetModel column in Table 3. Comparing with the original TestRank, the average ATRC value on the reported datasets and models reduces by 6.23%, which is significant. As the quality of the given model is to be examined, its feature extraction performance may not be reliable. Also, the dimension of the hidden layer could be huge, making it computationally expensive to calculate similarity values between input samples (This is why we do not report results on the SVHN dataset). In contrast, the separate model is more controllable, enabling it to extract better features for these data. Hence, using a separate feature extractor is necessary.
k-NN graph approximation. To reduce the computation complexity, TestRank uses approximation techniques when constructing the k-NN graph (see Section 3.3). The TestRank-w/o-approx. column in Table 3 shows the result when we use the original k-NN graph without approximation. It indicates that the average influence of the approximation is small (e.g. 0.95%). Therefore, if there is a computation resource limit and the unlabeled test instances are massive, we recommend using the approximation to save computation with negligible performance loss greatly.
Number of nearest neighbors k. When constructing the k-NN graph, the number of neighbors k decides the range of the context one node can reach. In previous experiments, the k is set to 100. We enlarge this range to (20 - 800) to study the influence. The result is shown in Figure 4.3. One can observe that the prioritization effectiveness will decrease when k is too small or too large. When k is too small, the context information available to one instance is limited, making it difficult for the GNN to extract valuable contextual attributes. On the other hand, when k is too large, the GNN may grasp irrelevant/noisy information. Still, TestRank can achieve good performance in a wide range of k values. For example, for model A, TestRank is better than the best baseline 69.70% (see Table 2) when k is larger than 20. Hence, selecting the number of nearest neighbors k is relatively flexible.

heading: 5 Conclusion
text: We propose TestRank, a novel test input prioritization framework for DL models. To estimate a test instance’s failure-revealing capability, TestRank not only leverages the intrinsic attributes of an input instance obtained from the target DL model, but also extracts the contextual attributes from the DL model’s historical inputs and responses. Our empirical results show that TestRank outperforms existing solutions significantly. At the same time, this paper considers each test case equally and aims to identify as many failure-revealing test cases as possible. In practice, the impact of each test case could be different. We leave the study of such impact for future work.

heading: Acknowledgment
text: This work is supported in part by General Research Fund (GRF) of Hong Kong Research Grants Council (RGC) under Grant No. 14205018 and No. 14205420.

heading: A Appendix

heading: A.1 Experiment details
text: Our code is implemented with the open-source PyTorch (under BSD license) [Paszke et al., 2019] and PyG (under MIT license) [Fey and Lenssen, 2019] ML libraries. All of our experiments are performed on a single TITAN V GPU 2.

heading: A.1.1 Datasets
text: CIFAR-10 is officially composed of 50,000 training images and 10,000 test images, and it has ten classes of natural images. The Street View House Numbers (SVHN) dataset contains house numbers from Google Street View images. It contains 73,257 training images and 26,032 testing images. Besides, the SVHN dataset also has an extra set of 531,131 images. The STL10 dataset contains ten classes of natural images. In each class, there are 500 training images and 800 test images.
Please note that the datasets we used are open-sourced and available for research purposes 3 4 5. Also, since the data we used is about numbers and the animals, we assume there are no personally identifiable information or offensive content.

heading: A.1.2 Baselines
text: Given a DL model and a specific budget, the goal of our method is to select test cases from an unlabeled data pool to discover the failures of the given DL model. We compare our work with the following test input prioritization techniques:
• DeepGini [Feng et al., 2020]: DeepGini is the state-of-art test case selection technique. DeepGini ranks unlabeled test cases by a score defined based on the output confidence. • MCP [Shen et al., 2020]: In addition to the output confidence, MCP also considers the
balance among different class boundaries of the selected test inputs. Specifically, MCP groups test cases into different clusters, where each cluster stands for a distinct classification boundary, and equally choose low confidence test cases from each cluster. • DSA [Byun et al., 2019]: Byun et. al. propose to use the distance-based surprise score
(DSA) as a test input prioritization metric, which was initially proposed in [Kim et al., 2019]. The surprise score measures the distance between the test case to the training set. Samples with higher surprise scores are prioritized. • Uncertainty [Byun et al., 2019]: The uncertainty is calculated as the entropy on the
averaged output probabilities by running the model multiple times (e.g. t times) with a specific dropout rate. • Random: Test inputs are randomly drawn from all unlabeled samples.

heading: A.2 Evaluation on More Model Structures
text: We evaluate our TestRank on two extra architectures: ShuffleNet and MobileNet. The results are shown in Table 4. The model ID indicates the same meaning (e.g., model training with different parts of the training set) as our main paper (see Section 4.1-Target DL model). As we can observe, TestRank can generalize to other models and architectures.

heading: A.3 Limitation
text: Run-time overhead. We compare TestRank with baseline methods in terms of the run-time overhead in Table 5. However, despite the considerable performance improvement in test input prioritization, TestRank introduces a longer run-time than most baselines. The main reason is due to the calculation of the distances between input features for k-NN graph construction. This limitation hinders the application of TestRank in large datasets, and we will solve it in our future work.
2https://www.nvidia.com/en-us/titan/titan-v/ 3http://ufldl.stanford.edu/housenumbers/ 4https://cs.stanford.edu/ acoates/stl10/ 5https://www.cs.toronto.edu/ kriz/cifar.html
Failure diversity. Besides the number of detected failures, failure diversity is another important factor for model debugging. In this work, we have the implicit assumption that the historical labeled data can cover the input distribution, and under such circumstances, TestRank can prioritize unlabeled tests effectively. If, however, the historical test data is severely biased, before prioritizing tests with TestRank, we should analyze the test pool and try to fill this gap first. Otherwise, the detected failures are lack diversity. We shall consider this problem in our future research.

heading: A.4 Broader Impacts
text: This work targets building an efficient and effective test input prioritization technique for deep learning models, which can help ensure the security of deep learning models after deployment. Various safety-critical tasks, such as autonomous vehicles, industrial robotics, and medical diagnosis, can benefit from test input prioritization techniques. We consider the scenario in which the unlabeled data is abundant, and a subset of unlabeled data is selected for labeling and testing. While building the unlabeled data by collecting them from the Internet or other sources, it may have a chance to include some unauthorized or private data. Also, the collected unlabeled data could be biased, resulting in the testing being incomplete. To avoid such cases, we should always guarantee that the collected data will not violate any privacy or rights and ensure that the collected data cover instances as many as possible.

Review summaries:
This paper introduce a way to test the generalization performance of DNNs using labeled together with unlabeld datasets via less labeling efforts. Authors proposed  TestRank -- an integrated approach that  (1) adopts an semi-supervised learning algorithm to "label" every unlabeled sample using a vector of discriminative features using GNN and label data. (2) retrieves features of every unlabeled sample from the DNN model under testing, and (3) trains an MLP using both GNN-predicted features and DNN-extracted features as inputs to predict failures of the DNN model as targets. Some evaluation has been done using three image classification datasets. 

This paper proposes a new test sample prioritization strategy to test deep learning systems. The objective is to maximize the number of failure-inducing samples selected from unlabeled samples. The authors propose to leverage both the samples' intrinsic properties (from the model's prediction behavior on them) and contextual properties (from other labeled samples close to them) as the criteria to select samples. By learning another binary classifier that takes the two properties as input, TestRank produces probabilities to rank the test samples. Empirical results demonstrate that TestRank outperforms existing test prioritization techniques.

- Given a dataset of labeled and unlabeled examples, authors build a   data point prioritization technique, which helps choose data points   to be labeled next, with a goal of revealing failures as soon as   possible. The technique should help prioritize labelling instances   which currently trained model would misclassify. - They use intrinsic and contextual attributes to build a model   performing data point prioritization. Intrinsic attributes are those   that are obtained by observing outputs of the deep learning model   for a given input. Contextual capture information about similarity   to the other instances -- if a given instance is similar to   misclassified instances, that would be a strong signal that the   instance is problematic. - For intrinsic attributes, they use the output layer logits (before   the softmax activation) of the DL model to construct a vector to be   used for a final model. Second, they use a graph neural network to   create contextual representation vector out of both labeled and   unlabeled data. The aforementioned vectors are input to an   multi-layer perceptron (MLP) model. The output of the MLP is a   probability that a given input would be misclassified by the DL   model. - They evaluate their model against other data point prioritization   techniques measuring number of failure revealing instances for a   given labelling budget.