Neural Relation Graph: A Unified Framework for Identifying Label Noise and Outlier Data
Authors: Jang-Hyun Kim
Sangdoo Yun
Hyun Oh Song
Venue: NeurIPS 2023 poster (2023)
Keywords: Dataset cleaning
Label error detection
Outlier detection
Neural Networks
Robustness
TL;DR: We present a scalable and domain-agnostic approach utilizing the relational structure of data for identifying label noise and outliers.

Abstract: Diagnosing and cleaning data is a crucial step for building robust machine learning systems. However, identifying problems within large-scale datasets with real-world distributions is challenging due to the presence of complex issues such as label errors, under-representation, and outliers. In this paper, we propose a unified approach for identifying the problematic data by utilizing a largely ignored source of information: a relational structure of data in the feature-embedded space. To this end, we present scalable and effective algorithms for detecting label errors and outlier data based on the relational graph structure of data. We further introduce a visualization tool that provides contextual information of a data point in the feature-embedded space, serving as an effective tool for interactively diagnosing data. We evaluate the label error and outlier/out-of-distribution (OOD) detection performances of our approach on the large-scale image, speech, and language domain tasks, including ImageNet, ESC-50, and SST2. Our approach achieves state-of-the-art detection performance on all tasks considered and demonstrates its effectiveness in debugging large-scale real-world datasets across various domains. We release codes at https://github.com/snu-mllab/Neural-Relation-Graph.

Neural Relation Graph: A Unified Framework for Identifying Label Noise and Outlier Data
Jang-Hyun Kim Seoul National University janghyun www.laa.su.ua.....
Sangdoo Yun
Hyun Oh Song" Seoul National University hyunoh @amoh@mmlann @ww.@mmmllaaa.......
NAVER AI Lab
Sungdoo.yun@naveeee
Abstract
Diagnosing and cleaning data a erucial step for building robust machine learning systems. However, identifying problems within large-scale datasets with real-world distributions challenging due the presence of complex issues such as label errors, under-repressnttaiin, and outliers. In this paper, propose unified approach for identifying the problematic data by utilizing a largely ignored source of information: a relational structure of data in the feature-embedded space. To this end, we present scalable and effective algorithms for detecting label errors and outlier data based on the relational graph structure of data. We further introduce visualization tool that provides contextual information of a data point in the feature- embedded space, serving as an effective tool for interactively diagnosing data. We evaluate the label error and auttier/out-of-ddsribbuut mances of approach on the large- image, speech, and language domain tasks, including ImageNet, ESC-50, and SST2. Our approach achieves state-of the detection performance all tasks considered and demonstrates its effectiveness in debugging large-scale real-world datasets across various domains. We release codes https // git.uu......... com/smmm//o//oe lallaabubueralll. IellattinnGraapa
(OOD) detection perfor-
Introduction
Identifying problems within datasets is crucial for improving the robustness of machine learning systems and analyzing the model failures [45]. For instance, identifying mislaheled uninformative data helps construct concise and effective training datasets [33], while identifying whether test data is OOD corrupted allows for more accurate model evaluation and analysis [54].
In recent years, efforts have been made to identify problematic data by utilizing unary scores on individual data from trained models, such as estimating data influence [22], monitoring prediction variability throughout training [52], and calculating prediction error margins [34]. However, identify- ing such data can be challenging, particularly when dealing with large-scale datasets from real- sol-world distributions. In real-world settings, datasets may have complex problems, including label errors, under-repressentatin, and outliers, each of which can lead to the model error and prediction sensitivity [23]. For example, Figure 1 shows that a neural network exhibits low negative prediction margins and high loss values for both sample with label error and outlier data. This observation indicates that previous unary scoring methods may have limitations in discerning whether the problem lies with the label or the data itself.
In this work, we propose a unified framework for identifying label errors and outliers by leveraging the feature-embedded structure of dataset that provides richer information than individual data alone [47, 36). We measure the relationship among data in the feature embedding space while comparing the assigned labels independently. By comparing input data and labels separately,
able to
"oorreppondigg author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Sorrel (clean)/ / Margin: 0.87, Losse 0.1
(label error)
Margin: -0.89, Loss: 4.1
Envelope (outlier) Margin: -0.86, Lesst 3.6
Rolatoon awvonae
0.0 0.1
Relation
Figure I: ImageNet samples with their labels and the corresponding relation maps by an MAE-Large model [13]. We report the prediction margin score (E [-1, 1] and the loss value next to the label. The relation map draws a scatter plot of the mean and variance of relation values of a data pair throughout the training process. Here the color represents the relation value the last converged checkpoint. We present the detailed procedure for generating the relation maps in Section 3.5.
Label
Label set
Clean Label issue Outlier
Clean
Score
Noisy
Neural network
Neural network
Input data
Datasct
Relation graph
Figure 2: The conceptual illustration of the conventional approaches (left) and our proposed approach (right). In the relation graph, positive edges signify complementary relations, negative edges denote conflicting relations, and dashed lines indicate negligible relations between data.
isolate the factors contributing to model errors, resulting in improved identification of label errors and outlier data, respectively. Based the relational information, construct novel graph structure on the dataset and identify whether the data itself or the label is problematic (Figure 2). To this end, develop scalable graph algorithms that accurately identify label errors and outlier data points.
In Section 3.5, we further introduce visualization tool named data relation map that captures the rela- tional structure of a data point. Through the map, we understand the underlying relational structure and interactively diagnose data. Figure we observe different patterns in the relation maps of the second and third samples, despite their similar margin and loss scores. This highlights that the relational structure provides complementary information not captured by the unary scoring methods.
Our approach only requires the model's feature embedding and prediction score on data, making it more scalable compared to methods that require calculating the network gradient on each data point or retraining models multiple times to estimate data influence [39, 17]. Furthermore, our method is domain- and aagnssig,,,,ic, and thus applicable to various tasks. We evaluate our approach on label error and outlier/OOD detection tasks with large-scale image, speech, and language datasets: ImageNet [43], ESC-50 [37], and SST2 [55]. Our experiments show state-of-the-a performance on all tasks, demonstrating its effectiveness for debugging and cleaning datasets over various domains.
Related works
Label error detection Label errors in datasets can negatively impact model generalization and destabilize evaluation systems [16, 34]. Prior works address this issue through label error detection using bagging and bootstrapping [46, 41], or employing neural networks [18, 27, 9, 19]. To mitigate overfitting on label errors, Pleiss et al. [38] propose tracking the training process to measure the area under the margin curve. Recent studies demonstrate that simple scoring methods with large pre-trained models, such as prediction margins or loss values, achieve comparable results to previous complex approaches [33, 5J. Meanwhile, Wu et al. [57] propose unified approach for learning with open-wer world noisy data. However, the method involves complicated optimization process during training, which is not suitable for large-scale settings. Another line of approach to identifying label eтrors involves measuring the influence of a training data point on its own loss [22, 39]. However, these approaches require calculating computationally expensive network gradients on each data point, and their performance is known to be sensitive to outliers and training schemes [2, 3]. In this work, we present a scalable approach that leverages the data relational structure of trained models without additional training procedures, facilitating practical analysis of label issues.

---

Outlier/OOD detection Detecting outlier data is crucial for building robust machine learning systems in real-world environments [23]. A recent survey paper defines the problem of finding outliers in training set as outlier detection and finding outliers in the inference process as OOD detection [59]. The conventional approach for detecting outliers involves measuring k-nearest distance using efficient sampling methods [48]. More recently, attempts have been made to detect outlier data using scores obtained from trained neural networks, such as Maximum Softmax Probability [14], Energy score [29], and Max Logit score [15]. Other approaches suggest adding perturbations
the inputs or rectifying the activation values to identify the outlier data [28, 49]. Lee et al. [26] propose fitting a Gaussian probabilistic model to estimate the data distribution. Recently, Sun et al. [50] propose non-parametric approach measuring the k-nearest feature distance. In our work, we explore the use of the relational structure the is applicable to a wide range of domains without requiring additional training while outperforming existing scoring methods on large-scale outlier/OOD) detection benchmarks.
space for identifying outlier data. Our approach
3 Methods
In this section, describe our method for identifying label errors and outliers using model trained on the noisy training dataset. We exploit the feature-embedded structure of the learned neural networks, which are known effectively capture the underlying semantics of the data [40]. We define data relation to construct a data relation graph on the feature space, and introduce our novel graph algorithms for identifying label errors and outlier data. In Section 3.5, introduce the data relation map as an effective visualization tool for diagnosing and contextualizing data.
3.1 Data relation
We describe our approach in the context of classification task, while also noting that the ideas are generalizable to other types of tasks as well. We assume the presence of a trained neural network on a noisy training dataset with label errors and outliers, T (x., y:) i= 1.... n]. By utilizing data features extracted from the network, we measure the semantic similarity between data points x X' [0, M), where a higher kernel value indicates greater similarity
with bounded kernel between data points. Our framework can accommodate various bounded kernels such as RBF kernel
or cosine similarity [60]. We provide detailed information on the kernel function used in our main experiments in Section 3.4.
By incorporating the assigned label information with the similarity kernel k, we define the relation func- tion r: X
Lesser panda
Weasel
0.0
X + |-M, M]:
r ((z,, v.), (1). (1)) 1(y: = y3) x)),,,)), (1)
-0.44
Weasel
0.0
where 1w:: vj)= 1-,, is signed indicator value. The relation function reflects the degree to which data samples are complementary or conflict- ing with each other. In Figure 3, the center image with a label error has negative relations to the left samples that belong to the same ground-truth class. In contrast, the two left samples with correct labels have a positive relation. We also note that samples with dissimilar semantics exhibit near-zero relations.
0.76
0.0
Lesser panda
-0. 76
0000
Rudily
0.0
Figure 3: Relation values of samples from Im- ageNet with MAE-Large [13]. We denote the assigned label above each sample. Here, the center image has label error.
Our relation function relies solely on the paral- lelizable forward computation of neural networks, ensuring scalability in large-scale settings.
3.2 Label error detection
We consider a fully-connected undirected graph 9 = E W), where the set of nodes corresponds to T and the weights W on edges & are the negative relation values defined in Equation (1). For notation clarity, we denote a data point by an index, ie., T (1......) n). Then, for nodes and j. the edge weight is wii.j) -r(i.)) -r((2,, v.), (zz, 2,)). We set w(i, i) to O, which does not
3

---

Calculate label noisiness score
Outlier score calculation
TW
(w 3)
k(z, x1)
= SA
Partition data by thresholding
Figure 4: Illustration of our scoring algorithms for identifying label noise (left) and outliers (right).
correspond to any edges in the graph. Consistent with previous works [33]. we aim to measure the label noisiness score for each data, where a higher score indicates a higher likelihood of label error. We denote the label noisiness scores for T as & E IR", where s(i] is the score for data
As depicted in Figure 3, data with label errors exhibit negative relations with other samples, implying that the data have similar features in the embedding space yet have dissimilarly assigned labels. This suggests that the edge weights w(i..) quantify the extent to which the label assigned to node i conflicts with the labels of other nodes. However, simply aggregating all edge weights of node can yield suboptimal results, negative relations also contribute to the score for clean data, as shown in Figure 3. In Appendix D.2, we provide a more detailed experimental analysis of this issue.
To rectify this issue, we develop an algorithm that considers the global structure of the graph instead of simply summing the edge weights of individual nodes. Specifically, we identify subsets of data likely to have correct/incorrect labels and calculate the label noisiness score based on the subsets. We partition the nodes in 7 into two groups, where N C T denotes the estimated noisy subset and TW denotes the clean subset. To optimize N, we aim to maximize the sum of the edges between the two groups, indicating that the label information of the two groups the most conflicting. To ensure that A contains data with incorrect labels, which constitute relatively small proportion of T, impose regularization to the cardinality of V with 2 and formulate the following max-cut problem:
N argmax TWW) (RA0(=1) (= DEE w(i.))) ALA- NCT
(2)
JETIA
The max-cut problem is NP-complete [11]. To solve this problem, we adopt the Kerninghan-Lin algorithm, which finds local optimum by iteratively updating the solution [20]. However, the original algorithm that swaps data one by one at each optimization iteration not suitable for lurge-scale settings. To this end, we propose an efficient set-level algorithm in Algorithm that alternatively updates the noisy set N and label noisiness score vector 8.
Specifically, given the current estimation of N, the cut value excluding edges of node E T is cut(NV (1), TW)( (()).. Algorithm measures the label noisiness score of node by comparing the objective cut values when including i in N and when including in TW:
+|+] = Cul(AN)) -
= E w(i.))
Iwii.). JEN
JETW
Here we use the assumption w(i, i) 0. In prac- tice, the cardinality of N is small, so we can ef- ficiently update the score vector by caching the initial score vector S as in Algorithm 1. After cal- culating the score vector s, we update the noisy set set N' by selecting nodes with score values above the value X. Figure 4 illustrates the optimization process. Here larger values of À result in smaller N consisting of data samples that more likely to have label noise. We provide the sensitivity analysis of À in Appendix C. with Table 7.
Algorithm 1 Label noise identification
Input: Relation function r (= -w) Notation: The number of data n
for i to n do
3[i] = Σi w(iij) # caching initial score
end for
8 repeat
AV
{i s > [L,
for
i no
s|i] f- 5 - EEEN
Algorithm satisfies the convergence property Proposition 1. In Appendix A, we provide proof and present an empirical convergence analysis on large-scale datasets. We also conduct runtime
end for until convergence Output: s.

---

analysis of our algorithm in Appendix A.3, demonstrating that the computation overhead of Algo- rithm 1 is negligible in large-scale settings.
Proposition 1. Algorithm with a single node update at each iteration converges to local optimum.
Complexity analysis The time complexity of Algorithm 1 is O(n²), proportional to the number of edges in a graph. It is noteworthy that our method maintains the best performance when used with graphs consisting of small number of nodes, as shown in Figure 5. This implies that we can partition large datasets and run the algorithm repeatedly for each partition to enhance efficiency while maintaining performance. In this case, the complexity becomes On//k k2) (nnk), with k representing the size each partition and n/k being the number of partitions. Also, computations on these partitions are embarrassingly parallelizable, meaning that the complexity becomes Ok-2) for k < n in distributed computing environments.
3.3 Outlier/OOD detection
In the previous section, presented method for detecting label errors based on data relations with similar feature embeddings but different label information. By employing the identical feature embedding structure, we identify outlier data by measuring the extent to which similar data absent in the feature embedding space. To quantify the extent of a data point being an outlier, we aggregate the similarity kernel values of a data point in Equation (3), thereby processing the entire relational information of the data point. Our approach leverages global information about the data distribution, resulting in more robust performance across range of experimental settings compared existing methods that rely on local information such as k-nearest distance [50]. Specifically, for a subset S C T and data x, measure the outlier score as
outlier(x) Eies k(x, xx)
Higher values in the outlier score indicate that the data more distributionally outliers. We propose to use uniform random sampling for S, adjusting the computational cost and memory requirements for the outlier score calculation to suit the inference environment. In Section 4.2, verify our method maintains the best OOD detection performance even when using only 0.4% of the data in ImageNet.
3.4 Proposed similarity kernel
For v; X, we extract the feature representation f; and the prediction probability vector pe from the trained model. We propose class of bounded kernel k X' X - [0, M) with the following form:
k(2,, x.)) = (s( c(p:,
positive scalar value controls the sharpness of the kernel value distribution. larger value of t makes a small kernel value smaller, which is effective in handling small noisy kernel values. A scalar value (f, f2) E IR+ denotes a similarity measurement between features. In our main experiments, we adopt the truncated cosine-similarity that has been widely used in representation learning [44, 42]. We use the hinge function at zero, resulting in the following positive ceature-similarig function:
sf,, fy) max(O, cos f2)).
is worth noting the utility of our framework is not limited to a specific kernel design. In Section 4.3, we verify our approach maintains the best performance with sf,,, f2) defined the RBF kernel [60].
While the feature similarity captures the meaningful semantic relationship between data points, we observe that considering the prediction scores P. can further improve the identification of problematic data. To incorporate prediction scores into our approach, we introduce a sealar term c(p;, Pj)
that measures the compatibility between the predictions on data points. Any positive and bounded compatibility function is suitable for the kernel class defined in Equation (3). In our main experiments, we use the predicted probability of belonging to the same class as the compatibility term c(p,, Pa). Specifically, given the predicted label random variables ÿJ and 2, the proposed compatibility term is
c(p;, p,)) P(ù ú2) p.P.A.
(4)
From a different perspective, we interpret this term as a measure of confidence for feature similarity. In Section 4.3, we verify the effectiveness of the compatibility term through ablation study.
5

---

Interpretation To better understand our relation function with kernel defined in Equation (3), we draw connection to the influence function [39], which estimates the influence between data points by computing the inner product of the network gradient on the loss function É of each data point as vin((x)) (V V=((())), where w denotes the network weights. Following the convention, we consider an influence function on the feed-forward layer, where ((x,) h((f)) hf By the chain rule, we can decompose the network gradient as V. (x,) = (f(((f) and represent the influence as (f, (p:h(f)) f/ f,. Our relation function differs from the influence function in that it does not rely on feature gradients (r,((f;) to evaluate the relationship between data points. Instead, our rela- tion function compares model predictions and assigned labels independently using the terms c(P,, P,) and [gt, y2). Our formulation does not require computationally expensive back poock-ropggttion and more robustly identifies conflicting data information than influence functions which are known to be sensitive outliers [2]. We provide more detailed theoretical analysis in Appendix A.4.
3.5 Data relation map
In this section, we present a visualization method based on our data relation function contextualize data and comprehend its relational structure. One of the effective approaches for visualizing a dataset dataset cartography [51], which projects the dataset onto 2D plot. This approach draws a scatter plot of the mean and standard deviation of the model's prediction probabilities for each data sample during training. Inspired by the dataset cartography, we propose a data relation map, which visualizes the relationship between data along the training process. To this end, we uniformly store checkpoints during training. We denote a set of these checkpoints as K, where ra refers to the relation function for checkpoint 1 E IC. For each data sample E TT we draw scatter plot of the mean and standard deviation of relation values (rx(1, k E K.} for j E (T.)).
In Figure 1, we provide relation maps of three samples from ImageNet, using 10 checkpoints of MAE-Large [13]. The three samples each represent clean data, data with label error, and outlier data. From the figure, samples show different relation map patters.. Specifically, the relation map of a clean data sample exhibits a majority of positive relations with relatively small variability. We note that there are gray-colored relations in high variability regions (0.2<std), indicating that the model resolves conflicting relations at convergence. On the other hand, the relation map of the sample with a label error demonstrates a majority of negative relations. Notably, high variance relations result in largely negative relations at convergence, suggesting that conflicts intensify. Lastly, the relation map of the outlier data sample reveals that relations are close to O during training. These relation maps can serve as a model-based fingerprint of the data, which our algorithm effectively exploits to identify problematic data. We provide additional data relational maps for various models in Appendix E.
4 Experimental results
In this section, we experimentally verify the effectiveness of our approach in detecting label errors and outliers. We provide implementation details, including hyperparameter settings in Appendix C.I. We provide qualitative results including detected label errors and outlier samples in Appendix E.2.
4.1 Label error detection
4.1.1
Setting
Datasets We conduct label error detection experiments on large-scale datasets: ImageNet [43], ESC-50 [37], and SST2 [55]. ImageNet consists of about 1.2M image data from 1,000 classes. ESC-50 consists of 2,000 5-second environmental audio recordings organized into 50 classes. SST2 is a binary text sentiment classification dataset, consisting of 67k movie review sentences. We also conduct experiments MNLI [55] and provide results in Appendix, Table 13.
Following Pruthi et al. [39], we construct a noisy training set by flipping labels of certain percentages of correctly classified training data with the top-2 prediction of the trained model. We use different neural network architectures for constructing a noisy training set and detecting label errors to avoid possible correlation. We leave more detailed procedure for constructing the noisy training set in Appendix C.2. When training the MAE-Large model [13] on ImageNet with 8% label noise, the vali- dation topl -accuracy decreases by 1.7% compared to the performance of the model trained on the orig-

---

Entropy - Leat--confidcoee
CWE -B Loss
Tracin
Margin
Relation (ours)
0.05
0.7
0.7
0.50
0.5
0.8
TNR9S
0.5
INRYS
0.5
0.4
0.4
0.40
0.3
0.3
0.35
0.3
0.2
0.25
0.1
498
8%
1.2%
15%
4%
85%
12%
15%
12k
24k
0.1M 0.4M
1.2M
12k
24%
0.1M 0.4M 1.2M
(a) Label noise ratio (%)
(b) The number of data (log-scale)
Figure 5: Label error detection performance on ImageNet with MAR-Large according to (a) label noise ratios and (b) the number of data. We obtain the results in (b) with 8% label noise. We report performance values of all methods in Appendix D.3, with Tables 10 and 11.
inal training set, as reported in Appendix Table 8. The decrease becomes more significant with 15% label noise, with drop of 4.4%, highlighting the importance of label noise detection and cleaning.
Baselines We compare our method (Relation) to six baselines that are suitable for large-scale datasets. We consider fine-tuned loss from pre-trained models (Loss) [5], prediction probability mar- gin score (Margin) [33], and the influence-based approach called TracIn [39]. We also evaluate model- agnostic scoring methods: Entropy, Least-confidence, and Confidence-weing For a fair comparison, we evaluate methods using a single converged neural network in our main ex- periments, while also providing results with temporal ensemble suggested by [39] in Appendix D.I.
Entropy (CWE) [24].
Metric We evaluate the detection performance based on label noisiness scores by each method. We note that detecting label errors is an imbalanced detection problem, which makes the AUROC metric prone to being optimistic and misleading [7]. In this respect, we mainly report the AP (average precision) and TNR95 (TNR 0.95 TPR), and provide AUROC results in Appendix D.3.
4.1.2 Results and analysis
ImageNet We measure the label eиror detection performance on ImageNet with the synthetic label noise by training an MAE-Large model [13]. Note that the model does not have access to information about the changed clean labels during the entire training process. Figure (a) shows the detection performance over a wide range label noise ratios from 4% to 15%. As shown in the figure, our approach achieves the best AP and TNR95 performance compared to the baselines. Especially, our method maintains a high TNR95 over a wide range of noise ratios, indicating that the number of data that need to be reviewed by human annotators significantly smaller when cleaning the dataset. In Figure 9, we present detected label error samples by our algorithm.
It is worth noting that our method relies the number of data for constructing relation graph. To measure the sensitivity of our algorithm to the number of data, we evaluate the detection performance using reduced number of data with uniform random sampling. Figure 5 (b) shows the detection performance on 8% label noise with MAE-Large. From the figure, we find that our algorithm maintains the best detection performance our algorithm is effective even when only a small portion of the training data available, such as continual learning or federated learning [35, 32]. In Table (a), we provide detection performance for different scales of MAE models on 8% label noise. The table shows our approach achieves the best AP with MAE-Base, verifying the robustness of our approach to the network scales. From the table, we note that larger models are more robust to label noise and show better detection performance.
with 1 1% of the data (12k). This demonstrates that
Speech and language domains We apply our method speech and language domain datasets: ESC-50 [37] and SST2 [55]. We design the label noise detection settings identical to the previous ImageNet section. Specifically, we train the AST model [10] for ESC-50 and the RoBERTa- model [30] for SST2 under the 10% label noise setting. Table (b) shows our approach achieves the best AP and TNR95 on the speech and language datasets, demonstrating the generality of our approach across various data types.
7

---

Table Label error detection performance on ImageNet with 8% label noise. Baseline refers the best performance among the six baselines considered in Figure 5. In Table (c), the evaluation metric
AP. We report the performance of all baselines Appendix D.3, with Tables 12 to 14.
(a) Model architecture scales
(b) Speech/language domains
(c) Realistic label noise scenario
Scale
Metric
Baseline
Relation
Dataset
Matric
Baseline
Relation
Model
Bascline Relation
Base
AP
TNR95
0.477
0.488
0.514
0.672
ESC50
TNR95
AP
0.793
0.739
0.779
0.847
MAE
BEIT
0.708
0.719
0.733
0.737
AP
0.484
0.526
AP
0,861
0.881
ConvNeXt
0.713
0.735
Large
TNR95
0,521
0.695
SST2
TNR95
0,850
0.870
ConvNeXt-22k
0.724
0.744
Realistic label noise The ImageNet validation set is known to contain numerous label errors [34]. To tackle this issue, Beyer al. [4] cleaned the labels with human experts and corrected around 29% of the labels via multi-labelingg With this re-labeled validation set, we conduct experiments under the realistic label noise, with the task of detecting the data samples with changed labels. We measure the detection performance with MAE-Large [13], BErT-Large [I], and ConvNeXt-Large [31] models. To examine the impact of pre-training on external data, we also include ConvNeXt pre-trained on ImageNett222k, denoted ConwNeXt-222k. We construct the relation graph using only the validation set, considering scenarios where the training data are not available. Table I (c) verifies that our approach outperforms the best baseline across various models. The results on NonyNeXt-222 indicate that pre-training on external data improves the detection performance.
Memorization issue We investigate the im- pact of large neural networks' ability to memo- rize label errors on detection performance [61]. In the left figure of Figure 6, we find that the AP score decreases as the training progresses after 30 epochs with MAE-Large which converges at 50 epochs. The right figure of Figure 6 plots the precision-recall curves, where we observe that precision increases at low recall area but decreases at mid-level recall (~ 0.5) as the train- ing progresses. This suggests that training has both positive and negative effects detecting label noise, and we speculate that memorization is one cause. Leveraging these observations, improve detection AP by 3.6%pp by using temporal ensemble of models [25]. We provide a more detailed description and results in Appendix D.1.
0.54
Epoch 10
0.8
Epoch 30
Precision
0.6
Fijoch so
0.50
0.4
0.48
0.2
30
Epoch
Recall
Figure 6: Label error detection performance of relation graph throughout the MAR-Large training process on ImageNet with 8% label noise.
4.2 Outlier/OOD detection
Baselines We consider the following representative outlier scoring approaches: Maximum Softmax Probability (MSP) [14], Max Logit [15], Mahalanobis [26]. Energy score [29], ReAct [49], KL- Matching [15], and KNN [50]. We tune the KNN method's 's hyperparameter k based on the paper's guidance as k = 1000 a, where represents the ratio of training data used for OOD detection. We also evaluate outlier detection approaches, Iterative sampling [48] and Local outlier factor [56).
OOD detection Following Sun et al. [50], we evaluate OOD detection performance on the ImageNet validation set consisting of 50k in-distribution data samples, along with four distinct OOD datasets: Places [62], SUN [58], iNaturalist [53], and Textures [6]. Each of these OOD datasets consists of 10k data samples except for Textures which has 5,640 data samples. We also combine these four datasets, this dataset.
denoted as ALL, and measure the overall OOD detection performance
Figure shows OOD detection performance of MAE-Large on ALL outlier dataset. Note that our approach and KNN both rely on the number of training data samples ([S)) for outlier score calculation. We examine the effect training set size by measuring the performance with a reduced number of data using uniform random sampling. Figure 7 verifies that our approach outperforms other baselines while maintaining performance even with 0.4% of the training dataset (5k). Note that KNN requires hyperparameter tuning according to the training set size, whereas approach uses the identical
8

---

Unary-beat
KNN
Relation (ours)
Baseline best
Relation (purs)
AP (8%: lahel Lahe] neriee)
0.86
0.02
0.52
AP(OOD)
0.870
0.09
0.94
0.563
0.50
0.82
0.53
0.49
0.860
0.90
0.50
0.48
0.855
5k
120k
1.2M
24k
120K 1.2M
6
0.6
0.8
1
training
traaining data (|S))
Temperature
Temperature
P.
Figure 7: OOD detection performance on Ima- geNet (ALL) with MAE-Large. Unary-best refers to the best performance among the methods that do not rely on the training data for outlier score calculation. We provide performance values of all baselines in Appendix D.4, with Table 15.
Figure 8: The detection AP of the MAE-Large model across a range of kernel temperatures t. The dashed blue line means the performance of the best baseline.
Table Outlier detection performance with Vit-Base on noisy ImageNet- 100. Some OOD scoring methods (Mahalanobis, ReAct, KL-Matching) are excluded from the comparison because they require a clean training dataset which available in the outlier detection setup.
(a) ImageNet-100 with SUN
(b) ImageNet- 100 with iNaturalist
Method
AUROC
AP
TNR95
Method
AUROC
AP
TNR95
MSP
0.708
0.335
0.032
MSP
0.706
0.309
0.040
Max Logit
0.499
0.216
0.011
Max Logit
0,469
0.171
0.012
Energy
0.417
0.106
0.010
Energy
0.375
0.075
0.012
KNN
0.990
0.899
0.960
KNN
0.993
0.923
0.972
Iterative sampling
0.973
0.687
0.903
Iterative sampling
0.979
0.734
0.922
Local outlier factor
0.986
0.850
0.941
Local outlier factor
0.990
0.890
0.958
Relation (Ours)
0.993
0.906
0.971
Relation (Ours)
0.995
0.940
0.982
hyperparameter 1) regardless of the size. In Appendix D.4, Tables 15 and 16, provide OOD) detection results on four individual OOD datasets as well as the performance with ResNet-50 [12], where our approach achieves the best OOD detection performance over the nine baselines considered.
Outlier detection We perform outlier detection experiments following the methodology by Wang al. [56], where the training set contains outlier data with random labels. We construct the noisy ImageNet- 100 training sets by using iNaturalist [53] and SUN [58] datasets. We train ViT-Base model [8] from scratch on these noisy training datasets, and measure outlier detection performance using the trained model. For more detailed description, please refer to Appendix C.3.
Table 2 shows the outlier detection results on two outlier datasets. As indicated, our method achieves the best performance in both outlier settings, demonstrating its effectiveness in outlier detection. It is worth noting that the considered OOD scoring methods (MSP, Max Logit, Energy) do not achieve good outlier detection performance. We speculate that this is due to the overfitting of the neural network's predictions on outliers.
Detecting outliers in validation set We further utilize method for identifying outliers in the validation set by retrieving data samples with the highest outlier score (Section 3.3). In Figure 10, we present samples detected by algorithm from ImageNet and SST2. In the figure, we observe that these samples are not suitable for measuring the predictive performance on labels, which should be excluded from the evaluation dataset.
4.3 Ablation study
Temperature / In Equation (3), we introduced a temperature where large value of / increases the influence of large relation values in our algorithm. We conduct sensitivity analysis on & with MAE-Large ImageNet under 8% label noise. Figure 8 shows the effeect of the temperature value

---

Water ouzel
Junco (-0.754)
Junco (-0.752)
Impala
Harteboest (-0.794)
Hartebocst (-0.768)
Negative
(-0.850)
Prsitive (-0.846)
"entertaining and informative documentary"
"entertaining movie"
"fascinating and timely content"
Figure 9: Detected data samples with label errors (marked in red) from ImageNet (top) and SST2 (bottom). We present samples with conflicting relations next to the detected samples and denote the corresponding relation value in parenthesis. We present more samples in Appendix E.2, Figure 14.
Flute
Airship
Vase
Honeycomb
Maze
Alligator lizard
Cockreach
Positive
Negative
"leather pants"
give a backbone to the company"
"the isracli/palcstinian conflict as"
Figure 10: Data samples with the highest outlier scores by our method on ImageNet (top) and SST2 (bottom) validation sets. We denote the assigned labels above each data sample. We present more outlier samples in Appendix E.2, Figure and Table 18.
on our detection algorithm's 's performance. From the figure, we observe that the label error detection performance increases the value increases, saturating at 6. In the case of OOD detection, achieve the best performance at around = 1. Our algorithm outperforms the best baseline over wide range of hyperparameters, demonstrating the robustness of our algorithm the hyperparameter.
Similarity kernel design We present an em- pirical analysis of the kernel design choices. Specifically, we replace the cosine similarity term in Equation (3) as the RBF kernel and eval- uate the detection performance. We further con- duct an ablation study on compatibility terms (Equation (4)). Table 3 summarizes the label error detection performance with different ker- nel functions on ImageNet with 8% noise ratio. The table shows that our approach largely out- performs the best baseline even with the RBF
Table 3: Comparison of similarity kernel designs. Baseline represents the best baseline performance. The term denotes compatibility tion (4), Note, Cos e is the kernel function consid- ered in our main experiments, and RBF Cos refers to our method without the compatibility term c.
in Equa-
Metric
Baseline
RBF
RBF-
Cos
AP TNR95
0.484
0.470
0.471
0.525
0.526
0.703
kernel. Also, we find that our approach without the compatibility term shows comparable AP perfor- mance while significantly outperforming basclines in TNR95. These results demonstrate the generality and utility of our relational structure- -baeetrrr--eedddddd framework, which not limited to specific kernel design.
5 Conclusion
In this paper, we propose a novel data relation function and graph algorithms for detecting label errors and outlier data using the relational structure of data in the feature embedding space. Our approach achieves of-te-of-hh-ar- performance in both label error and outlier/OOD detection tasks, as demonstrated through extensive experiments on large-scale benchmarks. Furthermore, we introduce a data contextualization tool based on our data relation that can aid in data diagnosis. Our algorithms and tools can facilitate the analysis of large-scale datasets, which is crucial for the development of robust machine- learning systems.
10

---

Acknowledgement
We are grateful to Jinuk Kim for helpful discussions. This work was supported by SNU-NAVER Hy- perscale AI Center, Institute of Information & Communications Technology Planning & Evaluation (ITTP) grant funded by the Korea government (MSIT) [No. 2020-0-00882, (SW STAR LAB) Devel- opment of deployable learning intelligence via euttsuustie and trustworthy machine learning and N0.2001--001144 Artificial Intelligence Graduate School Program (Seoul National University)], and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (RS-2023-00274280) Hyun Oh Song is the corresponding author.
References
[1] H. Bao, L. Dong, and F. Wei. Beit: Bert pre-training of image transformers. In ICLR, 2022.
[2] E. Barshan, M.-E. Brunet, and G. K. Dziugaite. Relatif: Identifying explanatory training samples via relative influence. In AISTATS, 2020.
[3] S. Basu, P. Pope, and Feizi. Influence functions in deep learning are fragile. In ICLR, 2021.
[4] L. Beyer, J. Hénaff, A. Kolesnikov, X. Zhai, and A. d. Oord. Are done with imagenet? arXiv preprini arXiv:2006.077 00.,099,,,,,, 2020.
[5] D. Chong, J. Hong, and C. D. Manning. Detecting label errors using pre-trained language models. arXiv preprint arXiv:2205. /2702, 2022.
[6] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi. Describing textures in the wild.
In CVPR, 2014.
[7] J. Davis and M. Goadrich. The relationship between precision-recall and roc curves. In ICML,
2006.
[8] A. Dosovitskiy, L.. Beyer, Kolesnikov, D. Weissenborn, Zhai, Unterthiner, M. Dehghani,
M. Minderer, G. Heigold, S. Gelly, et al. An image is worth 16x words: Transformers for image recognition at scale. ICLR, 2021.
[9] A. Ghorbani and J. Zou. Data shapley: Equitable valuation of data for machine learning. In ICML, 2019.
[10] Y. Gong, Y.-A. Chung, and Glass. Ast: Audio spectrogram transformer. In Interspeech, 2021.
[11] Hartmanis. Computers and intractability: a guide the theory of np-completeness (michael r. garey and david johnson). Siam Review, 24(1), 1982.
[12] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
[13] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick. Masked autoencoders are scalable vision learners. CVPR, 2022.
[14] D. Hendrycks and K. Gimpel. baseline for detecting misclassified and out-of-distribution examples in neural networks. In ICLR, 2017.
[15] D. Hendrycks, S. Basart, M. Mazeika, M. Mostajabi, J. Steinhardt, and D. Song. Scaling out-of-distribution detection for real-world settings. In /CML, 2022.
[16) W. Hu, 7. Li, and D. Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In ICLR, 2021.
[17] A. Ilyas, S. M. Park, I.. Engstrom, G. Leclere, and A. Madry. Datamodels: Predicting predictions
from training data. In ICML, 2022.
[18] L. Jiang, Z. Zhou, T. Leung, L. Li, and L. Fei-Fei. Mentoret: Learning data-driven curriculum for very deep neural networks corrupted labels. In ICML, 2018.
[19] N. Karim, M. N. Rizve, N. Rahnavard, A. Mian, and M. Shah. Unicon: Combating label noise
through uniform selection and contrastive learning. In CVPR, 2022.
[20] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell
system technical journal, 49(2), 1970.
[21] J.-H. Kim, Kim, J. Oh, S. Yun, H. Song, J. Jeong, J.-W. Ha, and O. Song. Dataset condensation via efficient synthetic-data parameterization. In ICML, 2022.
11

---

[22] P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In ICML, 2017.
[23] W. Koh, Sagawa, H. Marklund, M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Ya- sunaga, R. L.. Phillips, I. Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In ICMI., 2021.
[24] Kuan and Mueller. Model-agnostic label quality scoring to detect real-world label errors. In ICML DataPerf Workshop, 2022.
[25] S. Laine and T. Aila. Temporal ensembling for semi-supervised learning. In ICLR, 2017.
[26] K. Lee, K. Lee, H. Lee, and Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In NeurlPS, 2018.
[27] Li, R. Socher, and S. C. Hoi. Dividemix: Learning with noisy labels as semi-supervised learning. In ICLR, 2020.
[28] S. Liang, Y. Li, and R. Srikant. Enhancing the reliability of out-of-distribute image detection in neural networks. ICLR, 2018.
[29] W. Liu, X. Wang, Owens, and Li. Energy-based out-of-distribution detection. In NeurIPS, 2020.
[30] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis. L. Zettlemoyer, and Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint 190.v 2019.
[31] Z. Liu, H. Mao, C.-Y. Wu, C. Feichtenhofer, T. Darrell, and S. Xie. A convnet for the 2020s. In CVPR, 2022.
[32] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication--fficcienn learning of deep networks from decentralized data. In AISTATS, 2017.
[33] C. Northcutt, L. Jiang, and I. Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70, 2021.
[34] C. G. Northcutt, A. Athalye, and J. Mueller. Pervasive label errors in test sets destabilize machine learning benchmarks. In NeurlPS Datasets and Benchmarks Track, 2021.
[35] G. I. Parisi, R. Kemker, J. I.. Part, C. Kanan, and S. Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113, 2019.
[36] W. Park, D. Kim, Y. Lu, and Cho. Relational knowledge distillation. In CVPR, 2019.
[37] K. J. Piezak. ESC: Dataset for Environmental Sound Classification. In Proceedings of the 23rd
Annual ACM Conference on Multimedia, 2015.
[38] G. Pleiss, T. Zhang, F. Elenberg, and K. Q. Weinberger. Identifying mislabeled data using the area under the margin ranking. NeurlPS, 2020.
[39] G. Pruthi, F. Liu, Kale, and M. Sundararajan. Estimating training data influence by tracing gradient descent. In NeurlPS, 2020.
[40] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.0 /25,, 2022.
[41] Reed, Lee, D. Anguelov, Szegedy, Erhan, and A. Rabinovich. Training deep neural networks on noisy labels with bootstrapping. arXiv preprint
2014.
[42] N. Reimers and I. Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks.
In EMNLP-IJCNLP, 2019.
[43] O. Russakovsky, J. Deng, H. Su, Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3), 2015.
[44] Schroff, D. Kalenichenko, and J. Philbin. Facenet: A unified embedding for face recognition and clustering. In CVPR, 2015.
[45] K. Shuster, J. Xu, M. Komeili, D. Ju, E. M. Smith, S. Roller, M. Ung. M. Chen, K. Arora, J. Lane, al. Blenderbot 3: a deployed conversational agent that continually learns to responsibly engage. arXiv preprint arXiv:2208.03188 2022.
12

---

[46] B. Sluban, D. Gamberger, and N. Lavrač. Ensemble-base noise detection: noise ranking and visual performance evaluation. Data mining and knowledge discovery, 28(2), 2014.
[47] H. O. Song, Y. Xiang. S. Jegelka, and S. Savarese. Deep metric learning via lifted structured feature embedding. In CVPR, 2016.
[48] M. Sugiyama and K. Borgwardt. Rapid distance-based outlier detection via sampling. In NeurIPS, 2013.
[49] Y. Sun, C. Guo, and Y. Li. React: Out-of-distributie detection with rectified activations. In NeurIPS, 2021.
[50] Y. Sun, Y. Ming, X. Zhu, and Y. Li. Out-of-distribution detection with deep nearest neighbors.
In ICML, 2022.
[51] S. Swayamdipta, R. Schwartz, N. Lourie, Y. Wang. H. Hajishirzi, N. A. Smith, and Choi Dataset cartography: Mapping and diagnosing datasets with training dynamics. In EMNLP, 2020.
[52] M. Toneva, A. Sordoni, R. T. Combes, A. Trischler, Y. Bengio, and G. J. Gordon. An empirical study of example forgetting during deep neural network learning. In ICLR, 2019.
[53] G. Van Horn, O. Mac Aodha, Y. Song. Y. Cui, C. Sun, A. Shepard, H. Adam, P. Perona, and Belongie. The inaturalist species classification and detection dataset. In CVPR, 2018.
[54] V. Vasudevan, B. Caine, R. Gontijo-Lppes, S. Fridovich-Kell and R. Roelofs. When does dough become a bagel? analyzing the remaining mistakes on imagenet. In NeurIPS, 2022.
[55] A. Wang. A. Singh, J. Michael, F. Hill, O. Levy, and Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In ICLR, 2019.
[56] Y. Wang, W. Liu, X. Ma, J. Bailey, H. Zha, L. Song, and S.-T. Xia. Iterative learning with open-set noisy labels. In CVPR, 2018.
[57] Z.-F. Wu, T. Wei, J. Jiang, C. Mao, M. Tang, and Y.-F. Li. Nge: A unified framework for learning with open-world noisy data. In ICCV, 2021.
[58] Xiao, Hays, A. Ehinger, A. Oliva, and A. Torralba. Sun database: Large-scale scene recognition from abbey to zoo. In CVPR, 2010.
[59] J. Yang, K. Zhou, Y. Li, and Z. Liu. Generalized out-of-distribution detection: A survey, arXiv preprint arXiv:21 113343 2021.
[60] B. Yekkehkhany, A. Safari, S. Homayouni, and M. Hasanlou. A comparison study of different kernel functions for svm based classification of multi-temporal polarimetry sar data. The International Archives Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014.
[61] C. Zhang, S. Bengio, M. Hardt, Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 2021.
[62] B. Zhou, A. Lapedriza, A. Khosla, A. Oliva, and A. Torralba. Places: A 10 million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence. 40(6), 2017.
13

---

A Algorithm analysis
A.1
Proof
In this section, we provide proof for Proposition 1. Recall that Algorithm updates an estimated noisy Set at set-level N = {i s[i] > A}. We can conduct Algorithm with single node update at each iteration using the criterion s[i] > X, referred to as a sample-level version of Algorithm 1. Specifically, let us define algorithm moves a sample & to another partition at each iteration, where k argmax;e (s(i)-)) The algorithm stops when (s(k X)
R such that v/i]
for E N and ufi]] = for else. Then the
Proposition 1. Algorithm I with single node update each iteration converges local optimum.
Proof. The change in the objective value of Equation (2) by moving data from TW to
Σ
w(i,))
Σ
w(i.)) X,
(5)
JETW
JEN
where the change by moving data i from N to TW
Σ
Ew(i,)) Σ
mli.)) +
JEN
JETW
Note the score in Algorithm is
s[i]
Σ JET
(i.j)) - Σ w(i,)) Σ w(i,)) - E w(i,s). JETW
JEN
JEN
Thus the change in the objective value by moving data i to another partition is s|i] - A for E.W A).
and -s[i]+ + for i E N, which can be represented v|il [s[i] - Therefore, moving sample with a positive value of (s{i] A) to another partition guarantees an increase in the objective function value. Because cut value in graph bounded, the algorithm converges the local optimum by the monotone convergence theorem.
A.2 Empirical convergence analysis
We conduct empirical study on the convergence of Algorithm 1. Specifically, we randomly sample 100,000 data from ImageNet and construct relation graph. We compare the set-level Algorithm and the original Kerninghan-Lin algorithm in Figure 11. The figure indicates that both algorithms converge to the local optimum, while our set-level algorithm converges faster. Additionally, we observe that the set-level algorithm achieves lower objective value, verifying its effectiveness in large-scale settings.
Objecrive increase
100
50
Set (ours)
Single
Time (8)
Figure 11: Empirical convergence analysis of max-cut algorithms. Set denotes Algorithm 1 and Single denotes the Kerninghan-Lae algorithm which updates a single node at each optimization step.
A.3 Computation time comparison
In this section, we measure the time spent on detection algorithms. We use RTX3090-Ti GPU and conduct experiments on the full ImageNet training set. Table 4 compares computation time for Algorithm| and feature calculation. Note that all existing methods based on neural networks, including ours, require the calculation of features. The table shows that Algorithm (excluding
14

---

Table Time spent (s) for label error detection on ImageNet 1.2M dataset. Feature indicates the total computing time for calculating feature embeddings of all data points, and Gradi- ent means the total computing time for calculating network gradient on each data point. Algorithm indicates the time spent by our algorithm, excluding feature calculation.
Table Time spent per sample (ms) for OOD detection on Ima- geNet with various models. Unary refers to unary scoring methods utilizing logit or probability score for each data point.
Model
Feature
Algorithm 1 Gradient
Model
Unary
Relation
MAE-Base
2300
400
6000
MAB-Large ResNet-50
12.2
12.3
MAE-Large
6900
420
21000
8.1
8.2
feature calculation) requires significantly less computation time than forward computation. We also observe that our algorithm efficiently scales up to larger neural networks which have a larger number of feature embedding dimensions. is also worth noting that computing gradient takes a much longer time and also requires large memory budget, demonstrating the efficiency of our algorithm in large-scale label eтror detection.
In Table 5, we measure the time spent for OOD detection the full ImageNet training set. The computation of our similarity kernel is embarrassingly parallelizable on GPUs. As shown in the table, the overhead time for computing our outlier scores is negligible compared to the time spent for the neural networks' forward computation on a single data point. We can further reduce the time and memory requirements by measuring the outlier score on a subset of the training (Figure 7).
A.4 Interpretation of relation function
We establish an understanding of our relation function in Equation (I) by drawing a connection to the influence function [39]. For simplicity, we consider the influence function with single checkpoint, where the influence between data 2; and æ, is given by denotes the loss function, and denotes the weight of the checkpoint. We consider the influence function at the ford-forward layer, where {(x;) = h(f') = h(wTf,) following the convention [39]. By the chain rule, represent the influence as Vr(((()V f. In contrast, our relation function has a form of
Here, &
decompose the weight gradient as V=.((x;)) (F.)(f) and
1( = 1,) (s(f,, fy) (()::.;))
The main distinction between our relation function and the influence function is the existence of the feature gradient term (f') As observed in Barshan et al. [2], outliers have a large feature- gradient norm, leading difficulties in detecting label errors. Specifically, let us consider the weight w at the classifier layer, where the function h is the softmax cross-entropy loss function. As Pruthi al. [39], can express the feature gradient inner-product as
Vrrh(E)
(y, (y)
where denote the one-hot label. The equation above shows that the correctly classified data with y; P, yields near zero inner-product values, whereas outliers with high entropy predictions exhibit large inner-product values. Consequently, existing influence-based label error detection methods, which detect label errors by identifying data with high influence values, have degraded performance in the presence of outliers [2].
Our relation function differs from influence functions in that it separates label and prediction infor- mation using a label comparison term 1 yj) and a compatibility term c(p;, P;)., respectively. Outlier data typically have high entropy of model predictions, resulting in lower compatibility values with other data [14]. On the other hand, normal data with label errors exhibit high compatibil- ity values with other normal data. Our detection algorithms exploit these differences and achieve improved detection performance compared to the influence functions.
B Additional discussions
Why does relation graph work? We discuss the conceptual differences between our relation graph- based approach and previous baselines. Firstly, our method is data-centrie, whereas the previous
15

---

Table 6: Hyperparameter settings. We use identical hy perpaaaaaeterss for all experiments of each task regardless of model types.
Table 7: Label error detection performance
range of À values (ImageNet 8% noise, MAE-Large).
Task
(Equation (3))
A (Algorithm 1)
Metric / À
0.0
0.01
0.05
0.1
Label error
0.05
AP TNR95
0.522
0.524
0.527
0.527
Outlier OOD
6
0.692
0.693
0.695
0.693
1
approaches rely on a unary score by models. Our approach identifies problematic data by comparing them to other data, which leads to more reliable identification of problematic data than unary scoring methods that are vulnerable to overfitting [38]. Secondly, our approach aggregates global relational information, whereas previous methods rely on local information such as k-nearest distance [50]. Considering all edge connections, our method obtains more representative information about the data distribution. Through temperature parameter i and efficient graph algorithms, we effectively process the entire relations and achieve the improved identification of problematic data.
Limitations and future works There are several promising future directions for work. Firstly, the current experiments are limited to the classification task, and it would be valuable to apply our approach to wider range of tasks, such as segmentation generative models. These tasks may introduce new and interesting categories of problematic data arising from different label spaces and data structures. Secondly, integrating processes will also be valuable. This could involve using our approach to identify inconsistencies in label assignments to conduct fine-grained evaluation of models.
method with human annotation and model training
Broader impact Regarding social impact, we anticipate that our method will largely reduce the cost of the data cleaning and annotation process, while also providing developers with valuable insights into their data and training process through our data relation map. We do not anticipate negative social effects, as our method does not deal with socially sensitive issues.
C Experiment settings
C.1 Implementation details
Models For label error detection, we train models on datasets with label noise. In the case of ImageNet, we fine-tune the pre-trained MAE models following the official training codes?, which train MAE-Large for 50 epochs and MAE-Bass for 100 epochs. The MAE-Large model has a feature dimension of 1024, where the MAE-Bas Base model has dimension of 768. It is worth noting that the masked auto-encoding pre-training process of MAE does not utilize label information. We use RTX3090-Ti GPUs for the training and 1 RTX3090-Ti GPU for executing our al algorithm. In the case of 50,-50, we fine-tune the AST model with a 768 feature dimension for 25 epochs following the official training codes3. In the case of language domain tasks, we fine-tune RoBERTS Tasee with 768 feature dimension following the official training codest, where we train models for 5 epochs. For other models, we use the trained models provided by the Timm library For all experiments, we use the inputs of the classification layers as feature embeddings. the case RoBERTa, this corresponds to the encoder output of the [CLS] token.
Hyperparameter As shown in Figure 8, we observe that a large value temperature t benefits label error detection, while moderate temperature value around shows the best performance OOD detection. We summarized the hyperparameter used in our experiments in Table Note we use 0.05 in Algorithm 1 after scaling the label noisiness score to have maximum absolute value of 1. We observe that the conservative estimation of noisy set A by using small positive À values leads to better results than > as shown in Table 7. The results in the table confirm that method
bttttpe://iithub.ca.t cat//aaceboorreeerrc//eeee
3 http:///ttuub.cmm/uuaaa////aaaaa
'ttppe //tp://ggbt../tt/// www.auu...c//wiilieeee con//vvightnnm//yyorr... inw.eechiinnnnnn-ooneeoeee
16

---

Table 8: Validation top-1 accuracy Mag-Large trained on ImageNet with noisy labels.
Label Noise Ratio
0.
0.04
0.08
0.12
0.15
Top-1 Accuracy
85.89
84.96
84.15
82.88
81.50
Table 9: Label error detection AP by the temporal model ensemble with 4 MAE-Large checkpoints (ImageNet, 8% label noise). In parenthesis, we denote the performance gain compared to the detection by single converged model.
Finrrppy
Least-conf.
CWE
Loss
TracIn
Margin
Relation
0.246 (0.007) 0.282 (0.001) 0.397 (0.031)
0.465 (0.041) 0.449 (0.034) 0.544 (0.06) 0.562 (0.036)
performs effectively over a wide range of À values, outperforming the best scores 0.484 AP and 0.521 TNR95 from the six baselines tested.
Other tricks We find that small noisy kernel values accumulate errors as we consider large numbers of data. To resolve this issue, we clamp small similarity kernel values that fall below an absolute value of 0.03 as zero in Equation (3).
C.2 Synthetic label noise
In Section 4.1, we conduct controlled experiments by generating synthetic label noise. Specifically, we flip labels of certain percentage of training data with the top-2 prediction of trained models on correctly classified data. For the label flip, use MAE- Huge for ImageNet and RoBERTa-Laad for language datasets. Note that we did not use these models for detecting label errors to prevent possible correlations. In the case of speech domain, we the identical AST architecture. We note that the original ImageNet training set may contain label issues which can lead to misleading experimental results [34]. Therefore, by following Northcutt et al. [33] with MAE-Huge, resulting in a total of 1, 1,242,890 data samples. We conduct label error detection experiments this pre-cleaned training set. In Table 8, we provide the top-1 validation accuracy of MAE-Large trained on training sets with noisy labels, demonstrating the importance of label noise identification and cleaning.
remove about 4% of data that are likely to have label issues
C.3 Outlier detection setting
As outlier detection is not well-benchmarked in modern computer vision [59], we design an exper- imental setup with the ImageNet dataset and two outlier datasets: SUN [58] and iNaturalist [53], each with 10k outlier data. To ensure an appropriate outlier data ratio (~88),, we use ImageNet-100 [21], subset of ImageNet consisting of 120k data from 100 classes. We adopt the outlier detection setting of Wang et al. [56], where the training set has the outlier data with random labels. To consider multiple types of outlier data, we construct two noisy training sets: ImageNet-100 100 with SUN and ImageNet-100 with iNaturalist. We train a ViT-Base model [8] from scratch for 300 epochs on these noisy training datasets and measure outlier detection performance using the trained model.
D Additional experimental results
D.1 Temporal model ensemble
Following Pruthi et al. [39], we measure the label error detection performance by using the temporal model ensemble. Specifically, we average the label noisiness scores from 4 checkpoints that are uniformly sampled throughout training. Table shows that this technique improves the performance of all methods, with our approach still exhibiting the best performance. These results confirm the effectiveness of temporal ensembles when more computation and storage available.
17

---

(a) Clean label
(b) Noisy label
Max-cut
Sum
Denaity
Density
0.5
-0.5
0.5
-0.5
lahel noisiness score
label noisiness score
Figure 12: Normalized histogram of label noisiness scores by simple edge aggregation (Sum) and max-cut, Arrows indicate differences between the density functions.
D.2 Analysis edge aggregation
In this section, we analyze the difference between label noisiness scores calculated using max-cut and simple edge sum. Specifically, in Figure 12, we draw histograms of label noisiness scores for two groups of data: one with clean labels and the other with label errors. The figure shows that the score calculated through max-cut shifts the density in a positive direction for data with clean labels and in a negative direction for data with label errors, compared to the simple edge sum. This indicates that the label noisiness score calculated with max-cut better separates label errors from the clean data. this case, TNR95 increases from 0.628 to 0.647 by applying the max-cut.
D.3 Label error detection
In this section, we provide the exact performance values for Figure 5, including AUROC results. We report label error detection performances under various noise levels in Table 10, and provide performances according to the number data in Table 11. The tables confirm that our relation graph approach achieves the best label eтror detection performances in all three metrics, regardless of the noise ratio and the number of data. Tables 12 14, we provide performance values of all baselines considered in Table 1.
D.4 OOD detection
In Tables 15 and 16, we provide OOD detection results individual datasets mentioned in Section 4.2: Places, SUN, iNaturalist, and Textures. We report the OOD detection performance MAE-Large in Table 15 and the performance of ResNet-50 in Table 16. The tables demonstrate that approach achieves the best OOD detection performance on three out of four datasets considered, while achieving the best overall performance. Furthermore, method shows the best performance all three metrics with both models, which highlights its effectiveness detecting OOD data.
E
Additional qualitative results
E.1
Relation map
In Figure 13, we present additional relation maps ImageNet. We draw the relation maps with MAE-Large and ResNet-50. Note, MAE-Large utilizes masked auto-encoding pre-training whereas ResNet-50 is trained from scratch. From the figure, observe that the models exhibit similar distributions positive and negative relations for each data point. However, the ResNet model tends to have overall larger variance of relation, indicating that the pre-training process reduces the relation variance and is helpful in forming relationships between data.
The visualization tool helps to comprehend the distribution of complementary and conflicting relations associated with data point, aiding dataset analysis and debugging. For example, in Figure 13, the relation map of the Ram sample exhibits a combination of positive and negative relations. Specifically, it exhibits positive relations with other Ram class samples while showing negative relations with samples from the Big Hom class, which are visually challenging distinguish.
18

---

This observation suggests the need for multi-labeliig or refineent of the label space definition. In this way, we can intuitively identify problems in the dataset by using the visualization tool.
E.2 Qualitative results
We present problematic data samples detected by our algorithm. Specifically, Figure 14 shows ImageNet samples with label errors and their most conflicting data samples having negative relation values. Figure 15 shows the outlier data detected by our algorithm on the ImageNet validation set, indicating the existence of inappropriate data for evaluation. We also present results on SST2 [55], binary text sentiment classification dataset, in Tables 17 and 18.
19

---

Table 10: Label error detection performance on range of label error ratios (MAg-Large, ImageNet).
AUROC
AP
TNR95
Method Ratio
4%
8%
12%
15%
4%
8%
12%
15%
8%
12%
15%
Entropy
0.790
0.796
0.801
0.803
0.153
0.246
0.334
0.389
0.115
0.137
0.162
0.181
Least-conf.
0.829
0.836
0.843
0,847
0.176
0.282
0.380
0.443
0.223
0.270
0.327
0.368
CWE
0.845
0.845
0.845
0,844
0.301
0.397
0.471
0.506
0.135
0.160
0.188
0.212
Loss
0.864
0.864
0.865
0,865
0.328
0.424
0.497
0.530
0.229
0.276
0.334
0.374
TracIn
0.889
0.888
0.887
0,885
0.303
0.415
0.498
0.536
0.503
0.521
0.556
0.582
Margin
0.876
0.875
0.876
0.876
0,403
0.484
0.544
0.568
0.346
0.392
0.457
0.505
Relation (Ours)
0.917
0.914
0.910
0.904
0.437
0.526
0.590
0.611
0.695
0.695
0.687
0.683
Table 11: Label error detection performance according to the number of data (MAF-Large, ImageNet, 8% label noise).
AUROC
AP
TNR95 100k
Method #data
12k
25k
100k
400k
1.2M
12k
25k
100k
400k
1.2M
12k
25k
400k
1.2M
Entropy
0.806
0.801
0.797
0.796
0.796
0.250
0.248
0.246
0.246
0.161
0.161
0.144
0.137
Least-conf.
0.844
0.836
0.837
0.836
0.289
0.287
0.283
0.282
0.269
0.275
0.27
CWE
0.852
0.845
0.845
0.390
0.394
0.392
0.394
0.397
0.169
0.184
0.177
0.16
Loss
0.869
0.863
0.864
0.415
0.421
0,418
0.421
0.424
0.298
0.282
0.284
0,276
TracIn
0.886
0,887
0.408
0.415
0,409
0.412
0.415
0.541
0.523
0.521
Margin
0.878
0.874
0.875
0.875
0.481
0.486
0.481
0.484
0.424
0.412
0.392
Relation (Ours)
0.910
0.912
0.912
0.914
0.914
0.502
0.515
0.518
0.523
0.526
0.679
0.692
0.692
0.696
0.695
20

---

Table 12: Label error detection performance various scales of MAE (ImageNet, 8% noise).
Scale
Metric
Entropy
Least-conf.
CWE
Loss
Tracin
Margin
Relation
AP
0.231
0.280
0.373
0.412
0.393
0.477
0.514
Base
TNR95
0.120
0.217
0.132
0.223
0.488
0.342
0.672
AP
0.246
0.282
0.397
0.424
0.415
0.484
0.526
Large
TNR95
0.137
0.270
0.160
0.276
0.521
0.392
0.695
Table 13: Label error detection performance on speech (ESC-50) and language (SST2, MNLI) datasets with 10% label noise. For ESC-50, we use the AST model [10], and for SST2 and MNLI, we use the RoBERTa- Base model [30].
Dataset
Metric
Entropy
Least-conf.
CWE
Loss
TracIn
Margin
Relation
AP
0.715
0.737
0.720
0.737
0.739
0.737
0.779
ESC-50
TNR95
0.784
0.783
0.790
0.783
0.789
0.793
0.847
AP
0.227
0.227
0.861
0.861
0.854
0.861
0.881
SST2
TNR9S
0.175
0.175
0.850
0.850
0.837
0.850
0.870
AP
0.199
0.197
0.753
0.764
0.724
0.754
0.758
MNLI
TNR95
0.103
0.104
0.494
0.497
0.510
0.514
0.660
Table 14: Label error detection AP on ImageNet validation set. All the model scales are Large.
Model
Entropy
Least-conf.
CWE
Loss
TracIn
Margin
Relation
MAE
0.558
0.609
0.688
0.703
0.695
0.708
0.733
BEIT
0.614
0.644
0.707
0.719
0.718
0.718
0.737
ConvNeXt
0.587
0.625
0.696
0.710
0.700
0.713
0.735
Con2NeXt-22k
0.617
0.642
0.707
0.722
0.719
0.724
0.744
21

---

Table 15: OOD detection performance on ImageNet with MAF-Large.
AUROC SUN
TNR95
Method (OOD dataset
ALL
Textures
ALL
Places
SUN
iNat.
Textures
Places
SUN
iNat.
Textures
MSP
0.857
0.835
0.833
0.907
0.853
0.818
0.543
0.567
0.699
0.514
0.428
0.386
0.315
0.651
0.376
Max Logit
0.824
0.787
0.790
0.881
0.850
0.808
0.531
0.557
0.700
0.570
0.138
0.106
0.088
0.320
0.216
Mahalanobis
0.875
0,819
0,841
0,948
0,904
0.815
0.471
0.489
0.722
0.532
0.521
0.407
0.474
0.847
0,599
Energy
0.738
0.757
0.446
0,592
0.050
0,154
ReAct
0.896
0.862
0.872
0.909
0.857
0.586
0.611
0.746
0.634
0.550
0.449
0.463
0.793
0.547
KL-Matching
0.877
0.848
0.857
0.928
0.874
0.818
0.500
0.526
0.708
0.455
0.548
0.473
0.490
0.738
0.511
Iterative sampling
0.444
0.377
0.409
0.457
0.600
0.382
0.127
0.134
0.145
0.173
0.073
0.051
0.061
0.125
0.131
Local outlier factor
0.556
0.492
0.521
0.594
0.665
0.431
0.151
0.160
0.183
0.173
0.156
0.113
0.136
0.283
0.240
KNN
0.901
0.861
0.884
0.946
0.922
0.854
0.550
0.593
0.736
0.648
0.590
0.487
0.560
0.808
0.626
Relation (Ours)
0.911
0.883
0.894
0.951
0.921
0.874
0.618
0.653
0.782
0.642
0.636
0.547
0.587
0.810
0.641
Table 16: OOD detection performance on ImageNet with ResNer-50.
AUROC SUN
AP
TNR95
Method \ 1ODD dataset
ALL
Places
iNat.
Textures
ALL
Places
SUN
iNat.
Textures
ALL
Places
SUN
iNat.
Textures
MSP
0.847
0.829
0.836
0.896
0.814
0.782
0.469
0.501
0.641
0.369
0.496
0.471
0.461
0.634
0.352
Max Logit
0.844
0.827
0.833
0.894
0.807
0.767
0,445
0.468
0.605
0.331
0.482
0.463
0.448
0.622
0.340
Mahalanohis
0.693
0.644
0.628
0.735
0.823
0.567
0.228
0.209
0.270
0.375
0.265
0.194
0.229
0.436
0.371
Energy
0.836
0.821
0.825
0.883
0.798
0.721
0.398
0.407
0.503
0.269
0.481
0.463
0.448
0.622
0.340
ReAct
0.624
0.610
0.623
0.626
0.650
0.446
0.185
0.189
0.188
0.128
0.361
0.302
0.370
0.429
0.371
KL-Matching
0.838
0,811
0.822
0.894
0.817
0.784
0.439
0.463
0.693
0.404
0.307
0.268
0.224
0.477
0.291
Iterative sampling
0.624
0,530
0.578
0.659
0.809
0.516
0.167
0.190
0.229
0.380
0.150
0.112
0.134
0,223
0.269
Local outlier factor
0.648
0.556
0.602
0.686
0.824
0.533
0.175
0.199
0,244
0.397
0.186
0.143
0.167
0,272
0.315
KNN
0.822
0.783
0.884
0.922
0.764
0.335
0.384
0.546
0.774
0.295
0.372
0.587
0.496
Relation (Ours)
0.870
0.830
0.853
0.922
0.879
0.818
0.493
0.543
0,708
0.513
0.515
0.429
0.498
0.691
0.465
22

---

Ostrich
MAE
ResNet
Parachute
ResNot
1.00
1.00
1.00
1.00
030
0,00
0.90
-025
10.25
-8.25
-0.25
-0.0
6.79
-0.23
-2.5
0.1
Relation Variance
Clumber
MAE
ResNet
Mopod
MAE
ResNet
0.29
-0.3
-0.22
-0.25
-1.55
6.75
0.72
0.73
0.75
Narwich lerrier
MAE
ResNel
Ram
MAE
ResNet
1.02
6.30
0.50
0.80
5.00
0.02
0.00
0.00
-0.50
-0.00
-0.00
-0.75
-1.5
0.1
0.2
0.0
0.1
0.2
0.1
0.0
011
Lemon
MAE
ResNet
Barbell
MAE
ResNet
6.75
07
8.75
0.25
6.25
0.2
0,25
0.25
-0.35
-0.50
-0.52
-3.50
1.00
-1.00
0.1
-100
0.5
Bucket
RexNet
1,50
1.00
1.00 1.00
0.50
0.50
-0.75
-0
-0 75
-1.5
Water ouzel
MAE
ResNet
Chihuahua
MAE
ResNet
1.0
0.00
-0.50
-0.55
0.50
-3.00
-1.00
0.1
0.2
-1.05
0.0
0.1
0.2
3.3
1..00
30
0.1
0.2
0.3
-1.00
511
0.2
0.3
Wool
MAE
ResNet
Binder
MAE
ResNet
AA
635
03
BaRTH
825
0.55
-035
-122
-0.5
-2.55
6.75
0.73
0.75
0.75
Figure 13: Data relation maps on ImageNet with MAE-Large and ResNet-50. We denote the assigned label above each image. The color represents the relation value the last checkpoint. The x-axis is the standard deviation and the y-axis is the mean value of the relation values throughout training.
23

---

Kile
Bald eugle (-0.761)
Rald engle (-0.660)
Bald eagle (-0.760)
Bald engle (-0.759)
Lesser panda (-0.761)
Lesser (-0.761)
Lesser panda (-0.758)
panda (-0.757)
Ringlet
Monarch (-0.763)
Manarch (-0.754)
Monarch (-0.753)
Monarch (.0.533)
Impala
Hartebeest (-0.794)
Hartcheest (-0,768)
Hartebeest (-0.763)
Harteheest (-0.761)
Pussenger
Steam locomotive (-0.751) Steam locomotive (-0.751)
locomotive (-0.749)
Steam locometive (-0.747)
Redshank
Ruddy turnstone (-0.761)
Ruddy tumstone (-0.76l)
Ruddy turnstone (-0.758)
Ruddy turnstone (-0.757)
Figure 14: The first column shows the data samples detected by label error detection algorithm using MAE-Large on ImageNet. We present the samples with the most conflicting relation next to the detected samples. We denote the assigned label and the corresponding relation value above the image.
24

---

Coffee mug
Maze
Stopwatch
Barrow
Cocknaach
Airship
Stone wall
Vault
Apiary
Wig
African grey
Whistle
Stretcher
Teddy
Breasiplate
Hammer
Honeycomb
Pretzel
Alligator lizard
Vase
Gasmask
Barber chair
Flute
Figure 15: Data samples with the highest outlier score by our method on the ImageNet validation set. We denote the assigned label above the image.
25

---

Table 17: Text samples with label errors detected by algorithm the SST2 dataset. Below the text with label error, we present two text samples with conflicting relations and denote the corresponding relation value in parenthesis.
Text
Label
a damn fine and a truly distinctive and a deeply pertinent film
Negative
- breathtakingly assured and stylish work
Positive (-0.980)
winning and wildly fascinating work
Positive (-0.978)
fails to have heart, mind or humor of its own
Positive
failing to find spark of its own
Negative (-0.970)
movie's 's lack of ideas
Negative (-0,958)
a ploddingly melodramatic structure
Positive
plodding action sequences plodding picture
Negative (-0,959)
Negative (-0.957)
somewhat problematic
Positive
the more problematic aspects
Negative (-0.945)
the problematic script
Negative (-0.930)
a bittersweet contemporary comedy
Negative Positive (-0.940)
bittersweet film
of bittersweet camaraderie and history
Positive (-0.921)
Table 18: Outlier text samples detected by algorithm the SST2 dataset.
Text
Label
the battle
Negative
give a hackhone the company leather pants the istaeli/palestinian conflict as the story relevant in the first place from television monitor loud, movie instead of an endless trailer
Positive
Positive
Negative
Positive
Positive
Positive
Negative
doctor's office, emergency room, hospital bed or insurance company office this is appetizing than side dish of asparagus
Positive
Negative
26


Reviews:
[{"review_id": "FyxMxgwMum", "reviewer": "Reviewer_nM5G", "summary": "The paper under review outlines a novel method utilizing graph structure to identify label errors and outlier data. It proposes an algorithm that makes use of data feature embeddings to produce relation graphs. By incorporating a newly defined data relation function, the algorithm can globally capture mislabeled and outlier data. The experiments conducted exhibit a marked improvement in performance compared to extant detection methods. ", "questions": "+ Could you elaborate on the unique advantages of your proposed method over existing semi-supervised and self-supervised techniques, especially considering the shared approach of using feature similarity to help learn a noise-robust classifier? What distinguishes your method from others that also exploit $P(X)$ to help learn $P(Y|X)$?\n\n+ Could you specify the assumptions under which your method is expected to perform well?\n\n+ Could you provide the reasoning behind the choice of using a kernel in your method? How does the kernel contribute to the effectiveness of the method and why was this specific kernel chosen over potential alternatives?\n\n+ To convince others about the method's practical significance, could you include a comparison of your method with DividMix (ICLR20) and  UNICON (CVPR22) in the field of learning with noisy labels? ", "limitations": "I did not come across a sufficient discussion of the limitations of the proposed method. I would highly recommend the authors include a section on potential limitations in their revision.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ Innovation: The paper introduces a novel method, which is an important contribution to the field. This new approach potentially provides a fresh perspective and further insights into the problem at hand.\n\n+ Clarity and Comprehensiveness: The paper is well-structured and clearly written, making it easy for readers to understand the content. The authors have adequately cited related works, showing a thorough understanding of the existing literature and situating their work appropriately within that context.\n\n+ Important Problem: The paper tackles an important problem, making its potential impact highly relevant and timely. This problem is pertinent to many real-world scenarios, amplifying the value of the proposed solution.", "weaknesses": "+ Unclear Advantage: Despite the introduction of a new method, the paper lacks clear explanation of the motivation and advantages of the chosen approach compared to existing methods. The authors proposed to use the feature similarity ( 'semantic similarity between data points') to help learn a noise-robust classifier, which exploits $P(X)$ to help learn $P(Y|X)$. It shares the same underlying physiology with semi-supervised based methods (e.g., DividMix, ICLR20) or self-supervised based methods (e.g., UNICON, CVPR22). \n\n+ Lack of Explicit Assumptions: The authors do not clarify the assumptions under which the proposed method is expected to perform well. This lack of clarity could impede understanding and application of the method in practical scenarios.\n\n+ Unknown Motivation for Kernel Usage: The motivation for using a kernel in the proposed method is not explained. Without this, it's hard to understand the reason behind the choice of a kernel and how it contributes to the method's effectiveness.\n\n+ Absence of Baseline Comparisons: The paper does not compare the proposed method with significant baselines in the field of learning with noisy labels (e.g., DividMix, ICLR20; ELR, NeurIPS20; CausalNL, NeurIPS21; C2D, WACV23; UNICON, CVPR22). Such comparisons are crucial for evaluating the performance of the new method and understanding its standing relative to existing techniques. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable efforts and time in providing insightful feedback. We would like to address questions below.\n\n**Advantage over the semi-/self-supervised techniques**  \n- Thank you for the pointer. We would like to clarify that the goal of our paper is to identify the problematic data not only during training but also in more general situations such as evaluation and inference. Our method has some advantages over the mentioned semi-/self-supervised techniques: \n1. Our approach has **various other applications**, including data annotation, evaluation set debugging, and robust inference (lines 17-20), whereas the semi-/self-supervised methods focus on training with noisy labels. For instance, as shown in Table 1-c, our method can effectively detect label issues in the validation set, enabling a more accurate evaluation system. Furthermore, as shown in Appendix Figure 13, our method can identify whether a data point is an outlier, which helps build a reliable inference system.\n2. Our method does **not rely on specific training techniques**, making it applicable to more general data types and models. For instance, DivideMix and UNICON require mixup training, which is not commonly used in text domains, e.g., GPT-3 [1]. Our method assumes that the model is given, allowing it to be effortlessly applied to multiple domains using different training techniques, as demonstrated in Table 1-b.  \n[1] Brown et al., \"Language Models are Few-Shot Learners\", 2020\n3. Our method does **not demand additional training costs**, making it easier to scale to large-scale models and datasets. The semi-/self-supervised methods like DivideMix and UNICON require training two networks and numerous augmented training samples for SSL. Our approach, on the other hand, only needs a single trained network and identifies problematic data without additional training.\n\n- In the revision, we will incorporate the aforementioned points into the related work section.\n\n**Comparison with DivideMix and UNICON**   \n- Thank you for the valuable suggestion. While the mentioned methods aim to train image classifiers with noisy labels, our approach is focused on the task of identifying and debugging problematic data in different scenarios and domains. Technically, we focus on determining whether a data point $x_i$ or its label $y_i$ is anomalous, whereas the mentioned methods aim to directly infer a clean label $y_i$, making a direct comparison less straightforward. For instance, due to the difference, our approach is applicable to outlier detection as well, whereas those baselines cannot be applied.\n- We recognize that DivideMix and UNICON proposed partitioning algorithms for clean/noisy labels using GMM and Uniform Clean Sampling. However, it's worth noting that their approaches rely on sample-level cross-entropy or JSD loss, while our method explicitly models the relation between data. We reproduced the baseline algorithms using publicly available GitHub code and compared them with our relation graph approach:\n|dataset \\ method|DivideMix|UNICON|Relation (ours)|\n|:-|:-:|:-:|:-:|\n|ImageNet|0.424|0.447|0.526|\n|ESC-50|0.737|0.739|0.779|\n|MNLI|0.754|0.762|0.766|\n\n- The table above compares the label error detection AP over various datasets in different domains (Table 1-a,b of our paper). Our approach demonstrates better performance compared to DivideMix and UNICON, confirming the advantages of our method across various datasets in label error detection. We acknowledge the importance of these related works and we will incorporate the results into the revision.\n\n**Assumptions under which the method is expected to perform well**  \n- Thank you for the pointer. In our approach, we assume the availability of a model trained on the noisy training dataset (line 89). As illustrated in Figure 6-left, when the model is insufficiently trained (e.g., trained for 10 epochs), the label noise detection performance tends to decrease, as the model does not capture meaningful semantic relationships between the data. It is worth noting that the model training requirement is a common assumption for other baseline techniques as well. \n- Furthermore, as evident from Figure 5, the performance of our algorithm improves as the number of data points in the relation graph increases. This analysis suggests that our method's performance can be effectively enhanced when handling massive data in real-world applications. We will ensure to present these discussions more clearly in our revision.\n\n**Motivation and reasoning behind the kernel used**  \n- To evaluate our relation graph framework, we adopted the most commonly used and computationally efficient kernel, i.e., feature cosine similarity. Notably, our framework demonstrates strong performance with other kernels, e.g., RBF kernel (Sec 4.3. Table 2), indicating that the effectiveness of our approach primarily stems from the graph structure and algorithm rather than the specific kernel design. \n- Another notable advantage of the kernel described in Section 3.4 is interpretability. In lines 200-211, we establish a relationship between the proposed kernel and the influence function. Additionally, in Appendix A.4, we provide a formal explanation demonstrating that the proposed kernel can exhibit better robustness to outliers compared to the influence function. \n\n**Potential limitations**  \n- Thank you for your feedback. Due to space limitations, we included the limitations and future work in Appendix B, line 568. Currently, we have evaluated our method within the scope of classification. Applying it to a broader range of tasks, such as generative modeling or segmentation, is an important future endeavor. Additionally, establishing a more rigorous theoretical foundation for our approach is also an important future direction. We will supplement these points and move them to the main text in the revision.\n\nThank you once again for the valuable feedback. If you have any remained questions, please let us know."}, {"review_id": "KwvzMAvBMP", "reviewer": "Reviewer_6KY3", "summary": "This paper proposes a new method using graph structure for detecting label errors and outlier data. Briefly speaking, the algorithm utilizes data feature embeddings to generate relation graph and using the new defined data relation function, its algorithm can capture mislabeled and outlier data from a global prospective. A large number of experimental results show that the performance of this method is greatly improved compared with the existing detection methods. ", "questions": "\n(1)\tLine 159 in Complexity analysis, the paper demonstrates the complexity can be reduced to O(nk). But in the fourth last row in algo 1 each point in partition seems also need to calculate n relation score instead of k. Can you deeper explain the improvement in complexity？ And there is no empirical results of the acceleration.\n(2)\tThe paper mentions it’s the first using data relation graph on the feature space. The “first” points to “relation graph” or “feature space”? Are there any other methods using graph to detect error data and need to be compared with?\n", "limitations": "(1)\tAlthough extensive experiments on real-world datasets corroborate the effectiveness of the proposed method, there is lack of theoretical analysis of the effectiveness of the method.\n(2)\tSome content lacks detailed explanations.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) This paper presents a novel relation graph-based approach to achieve better utility and considers error label and outlier detection in a global way. \n(2) Extensive experiments on datasets from different domains show the improvement of the new method is promising.\n(3) Comprehensive ablation study is performed, which helps to understand the proposed model better.\n(4) The overall expression of the article is clearer and easier to understand, and related works are adequately cited.\n", "weaknesses": "(1) Certain statements in this paper lack justification. For example, the method is based on building graph on feature space, but there is a little discussion about feature spaces and how to generate it.\n(2) Lack of sufficient theoretical analysis (e.g. convergence but not only empirical analysis) , the proof of proposition and analysis of relation function are relatively simple.\n(3) Lack of explanation of choosing parameter in baseline method, like whether there is a finetune on the choice of K in KNN method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable efforts and time in providing insightful feedback on our work. We would like to address questions from the reviewer below.\n\n**Discussion about feature spaces**  \n- Thank you for the pointer. We would like to mention that specific information regarding the feature space can be found in Appendix C.1, lines 589-590. We used neural networks trained on a noisy training set as feature extractors. Specifically, we followed the references of TracIn, MAE, and RoBERTa, using the input vector to the classification layer of neural networks as features. We will incorporate this information into the main text in the revision.\n\n**About theoretical analysis**  \n- Thank you for your response. In Proposition 1, we theoretically prove the convergence of our proposed algorithm, which is also empirically demonstrated in Appendix A.2. We believe that the simplicity and intuitiveness of our proof offer an advantage, as they make the concepts more accessible to a broad readership, ensuring a clear understanding of our work.\n\n**Hyperparameter of baselines**  \n- Thank you for your question. We tuned the hyperparameters of the baseline methods by adhering to the instructions provided in the respective papers, as mentioned in Section 4.3, lines 314-315. Specifically, for the KNN method, we followed the formula presented in the paper, which specifies that $k=n_{\\text{class}} \\times \\alpha$ (where alpha represents the ratio of training data used) for the tuning. We will elaborate on these details in the revision. Additionally, we will make the source code, including the baseline methods, publicly available to further support reproducibility.\n\n**Questions on complexity (+empirical comparison)**  \n- Figure 5 (b) demonstrates that our method maintains superior detection performance even with a small number of data in the relation graph, e.g., 1% of the ImageNet training set. Based on the observation, the complexity analysis suggests that when given a dataset with $n$ samples, dividing it into $n/k$ partitions of size $k$ and running the algorithm on each partition improves the complexity. In this case, the complexity for each partition is $O(k^2)$, and when applied sequentially to $n/k$ partitions, the complexity becomes $O(k^2 * n / k) = O(nk)$. Following the suggestion, we empirically validate the complexity of our Algorithm on ImageNet with 1 RTX-3090Ti GPU:  \n|# data | 0.1M | 1M (accelerated) | &nbsp;&nbsp;1M |\n|:--|:--:|:--:|:--:|\n| Time (s) | 3 | 31 | 424 | \n| AP | 0.518 | 0.522 | 0.526 | \n\n- In the table above, we examine the computation time and label error detection performance of our algorithm on ImageNet with MAE-Large. Specifically, the column labeled 1M (accelerated) represents the results of our algorithm's accelerated version, achieved through partitioning of size 0.1M. Considering that the performance of the best baseline is 0.484, our algorithm demonstrates efficient acceleration while maintaining the best performance. We will incorporate this information in the revised version.\n\n**The “first” points to “relation graph” or “feature space”?**  \n- We appreciate your feedback and would like to clarify the point mentioned in lines 83-85. The term \"first\" was used to indicate the order of the contents in the following sections rather than claiming to be the initial proposer of the concept. Our main contribution lies in presenting a unified framework, novel relation graph structure, and effective algorithms, which differ from the baseline methods, primarily relying on a single score of each feature. While there are other methods that also utilize relationships between data, such as the KNN method, it's important to note that this approach is limited to OOD issues and does not leverage a global relational structure. As a result, our proposed approach demonstrates higher performance, as presented in Figure 7, page 9.\n\nThank you once again for the valuable feedback. If you have any remained questions, please let us know."}, {"review_id": "uhFkkENnLV", "reviewer": "Reviewer_Cygf", "summary": "The authors identified the issue of how existing label errors in the training data and the OOD in the test set can affect the model training and evaluation and further proposed a novel approach utilizing the learned feature embeddings and label information to compute the relations between data instances. The relations represent how similar the two data instances are in terms of their feature embeddings and also assigned labels. This is further used to construct a relational graph structure. Based on the graph structure, they introduce a min-cut algorithm based on the label noisiness score to identify a subset of label errors. They further visualized the derived graph structure for the purpose of interactive data error diagnosis. Extensive experiments are conducted on multiple data types (images, audio, texts), and all show superior performance over the baseline methods. Through comparison, authors showed their relational data structure provides complementary information not captured by the unary scoring methods. Generally, this paper is well-written, the ideas are pretty clear, the methods are novel, and results are solid.", "questions": "\n1.\tIn Figure 1, What makes the Coil example a label error, while the Envelope example an outlier? Some elaboration on this would be helpful.\n2.\tIn Section 3.2, pp3 line114, authors set $r(i,i)=0$, this is not very straightforward and the reason is not clear to me. More elaboration on this would be helpful.\n3.\tIn section 3.2, pp4 line 127, authors minimize the sum of the edges between two groups. One question comes naturally - what about the sums of edges within each group? \n4.\tIn terms of different datasets used in this work, several data types were involved (images, speeches, texts), it would be helpful to see what the embedding dimensions are for each dataset.\n", "limitations": "Minor edit suggestion: pp8 line309, ‘3.6%p’ should be ‘3.6%’.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "A substantive assessment of the paper's strengths, touching on each of the following dimensions: originality, quality, clarity, and significance. We encourage reviewers to be broad in their definitions of originality and significance. For example, originality may arise from a new definition or problem formulation, creative combinations of existing ideas, application to a new domain, or removing limitations from prior results. You can incorporate Markdown and Latex into your review. See /faq.\n\n1.\tThis paper is well-written, and the authors explain the ideas clearly. The method is novel, and experiments and results are solid. \n2.\tThe example provided in Figure 1 explained well the limitations of using the unary scoring method when identifying the label error and the outlier data.\n3.\tThe design of the data relation function in Section 3.1 looks simple but still effective.\n4.\tIn section 3.2, the authors pointed out that simply aggregating all edges of a node can yield suboptimal results, which makes much sense, and they further proposed using the min-cut method as a walkaround. This looks interesting.\n5.\tThe experiments are conducted using various data types, including images, speeches, and texts. This also covers multi-class tasks and binary tasks. All experiments show the effectiveness of their methods, which is solid.\n", "weaknesses": "\n1.\tIn Figure 1, the difference between the Coil (label error) and the Envelope (outlier) is not very clear. More elaborations will be helpful.\n2.\tConstructing the relational graph is a fully connected graph, the time complexity would be O(N^2), and the scalability to a large dataset is a concern.\n3.\tIn section 3.2, pp3 line 115, ‘a lower (label noisiness) score indicates a higher likelihood of label error’. A lower label noisiness indicates a higher error possibility, this is a bit confusing and not very intuitive.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable efforts and time in providing insightful feedback on our work. We would like to address questions from the reviewer below.\n\n**Difference between the Coil (label error) and the Envelope (outlier)**  \n- In the case where a data point is associated with a different ground truth label, it is considered a label error, and when it is not possible to assign a suitable label, the data point is referred to as an outlier. For instance, in the case of the \"Coil\" example, it corresponds to the \"park bench\" label in ImageNet (incorrectly labeled as \"coil\" in the actual ImageNet dataset), and for the \"envelope\" example, a suitable ImageNet label cannot be found for the given data. We will clarify these explanations in the revision.\n\n**The complexity of constructing the relational graph**  \n- Our method employs a simple cosine feature similarity for relation values, which involves a simple matrix multiplication of $n$ pre-computed features. This computation can be efficiently carried out on GPUs. In practice, extracting features from 1.2M ImageNet data points using an MAE-Large model takes 15x longer time than the execution time of Algorithm 1 (Appendix A.3, Table 3). Specifically, the computation of Algorithm 1 with full ImageNet can be accomplished within a few minutes by using a single GPU. Furthermore, as demonstrated in the complexity analysis in lines 159-166, we can improve complexity to O(k^2), for $k \\ll n$, leveraging partitioning and parallel computing techniques.\n\n**A lower label noisiness indicates a higher error possibility, this is a bit confusing and not very intuitive**  \n- Thank you for the pointer. We will modify the expression to be more intuitive. \n\n**More elaboration on the assumption r(i,i)=0**  \n- Our approach only considers relations between different data points, which means the value $r(i, i)$ is not taken into account in the algorithm. However, if the formula is expressed considering this value, the notation becomes complicated, and to enhance the clarity of the expressions, we have chosen to set this value to 0. We will make this more clear in the revised version.\n\n**About the sums of edges within each group**  \n- That's a great point. The sum of all edges in the graph is equal to the sum of edges between groups plus the sum of edges within each group. Since the total sum of edges for a specific dataset is fixed, minimizing the sum of edges between groups is equivalent to maximizing the sum of edges within each group. This new perspective is highly intriguing, and to aid the reader's understanding, we will incorporate this information into the main text.\n\n**Embedding dimensions of each dataset**  \n- Thank you for the point. The embedding dimensions for each case are as follows:  \n| Image (MAE-Large) | speech (Ast) | text (RoBERTa-Base) |\n|:-:|:-:|:-:|\n| 1024 | 768 | 768 |\n\n- We will include the information above in the revision.\n\n**Minor edit suggestion: pp8 line309, ‘3.6%p’ should be ‘3.6%’**  \n- Thank you for the pointer. We will fix it in the revision. \n\nThank you once again for the valuable feedback. If you have any remained questions, please let us know.\n"}, {"review_id": "9eBblg9T7Q", "reviewer": "Reviewer_Yk3p", "summary": "This paper proposes a novel approach called the Neural Relation Graph framework for identifying label noise and outlier data in large-scale datasets with real-world distributions. The approach utilizes a relational structure of data in the feature-embedded space to detect label errors and outlier data, and introduces a visualization tool for interactive data diagnosis. The authors conduct extensive experiments on various tasks and demonstrate that their approach achieves state-of-the-art detection performance and is effective in debugging real-world datasets. The contributions of this paper include a unified approach for diagnosing and cleaning large-scale datasets, a data relation function and graph algorithms for detecting label errors and outlier data, and a visualization tool for interactive data diagnosis.", "questions": "Can you provide a more detailed analysis of the limitations of your approach? While the proposed approach achieves state-of-the-art detection performance on various tasks, it is unclear how it would perform on datasets with different characteristics or in different domains.\n\nCan you provide a more detailed discussion of the computational complexity of your approach? While the paper mentions that the proposed algorithms are scalable, it is unclear how they would perform on very large datasets or in real-time applications.\n\nCan you discuss potential use cases for the proposed approach and provide guidance on how it could be integrated into existing machine learning pipelines? While the paper demonstrates the effectiveness of the approach in detecting label errors and outlier data, it is unclear how it could be applied in real-world scenarios.\n\nCan you provide more details on the visualization tool introduced in the paper? While the tool is mentioned briefly, it would be helpful to have a more detailed description of its functionality and how it can be used to diagnose data.\n\nCan you provide more details on the datasets used in the experiments? While the paper mentions that experiments were conducted on various tasks, it would be helpful to have more information on the characteristics of the datasets and how they were selected.\n\nCan you provide more details on the hyperparameters used in the experiments? While the paper mentions that hyperparameters were tuned using cross-validation, it would be helpful to have more information on the specific values used and how they were selected.\n\nCan you provide more details on the implementation of the proposed algorithms? While the paper mentions that the algorithms were implemented using PyTorch, it would be helpful to have more information on the specific implementation details and any potential optimizations that were made.\n\nCan you discuss potential future directions for this research? While the paper presents a novel and innovative approach, it would be helpful to have a discussion on potential future directions for this research and how it could be extended or improved upon.", "limitations": "The paper does not explicitly address the potential negative societal impact of the proposed approach. While the focus of the paper is on diagnosing and cleaning large-scale datasets, it is possible that the approach could be used for other purposes, such as identifying individuals or groups based on their data. This could potentially lead to privacy concerns or other negative societal impacts.\n\nHowever, it should be noted that the paper does not provide any evidence that the proposed approach has been used for such purposes, and the authors do not make any claims about the potential negative societal impact of their work. Additionally, the paper does not explicitly address the limitations of the proposed approach, which could potentially lead to unintended consequences if the approach is used in real-world scenarios.\n\nOverall, while the paper does not explicitly address the potential negative societal impact of the proposed approach, it should be noted that the authors do not make any claims about the potential negative impact of their work, and the focus of the paper is on diagnosing and cleaning large-scale datasets.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThe Neural Relation Graph framework proposed in this paper is a novel approach for identifying label noise and outlier data in large-scale datasets. The authors utilize a relational structure of data in the feature-embedded space to detect label errors and outlier data, which is a unique and innovative approach. The paper also introduces a visualization tool for interactive data diagnosis, which is a novel contribution to the field. Overall, the paper is highly original and presents a new perspective on diagnosing and cleaning large-scale datasets.\n\nQuality:\nThe paper is of high quality, with a well-designed methodology and extensive experiments conducted on various tasks. The authors provide detailed descriptions of the proposed approach and the experiments conducted, which makes it easy to understand and replicate the results. The paper also includes a thorough evaluation of the proposed approach, comparing it to existing methods and demonstrating its effectiveness in detecting label errors and outlier data. The quality of the paper is further enhanced by the use of clear and concise language, making it easy to follow and understand.\n\nClarity:\nThe paper is well-written and easy to understand, with clear descriptions of the proposed approach and the experiments conducted. The authors provide detailed explanations of the technical terms used, making it accessible to a wide range of readers. The paper also includes visual aids, such as figures and tables, which help to illustrate the concepts presented. Overall, the clarity of the paper is excellent, making it easy to follow and understand.\n\nSignificance:\nThe paper is highly significant, as it presents a novel approach for diagnosing and cleaning large-scale datasets with real-world distributions. The proposed approach utilizes a relational structure of data in the feature-embedded space to detect label errors and outlier data, which is a unique and innovative approach. The paper also introduces a visualization tool for interactive data diagnosis, which is a valuable contribution to the field. The results of the experiments conducted demonstrate the effectiveness of the proposed approach, making it a significant contribution to the field of machine learning.", "weaknesses": "One potential weakness of the paper is that the authors do not provide a detailed analysis of the limitations of their approach. While the proposed approach achieves state-of-the-art detection performance on various tasks, it is unclear how it would perform on datasets with different characteristics or in different domains. The authors could address this weakness by conducting experiments on a wider range of datasets and providing a more detailed analysis of the limitations of their approach.\n\nAnother weakness of the paper is that the authors do not provide a detailed discussion of the computational complexity of their approach. While the paper mentions that the proposed algorithms are scalable, it is unclear how they would perform on very large datasets or in real-time applications. The authors could address this weakness by providing a more detailed analysis of the computational complexity of their approach and discussing potential strategies for improving its scalability.\n\nFinally, the paper could benefit from a more detailed discussion of the practical implications of the proposed approach. While the paper demonstrates the effectiveness of the approach in detecting label errors and outlier data, it is unclear how it could be applied in real-world scenarios. The authors could address this weakness by discussing potential use cases for the proposed approach and providing guidance on how it could be integrated into existing machine learning pipelines.\n\nOverall, the paper presents a novel and innovative approach for diagnosing and cleaning large-scale datasets, but could benefit from a more detailed analysis of its limitations, computational complexity, and practical implications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable efforts and time in providing insightful feedback. We would like to address the questions below.\n\n**Limitations of the proposed approach (with different domains)**  \n- Thank you for your feedback. In Table 1-b from Sec 4.1.2, we demonstrate that our method consistently outperforms baselines across **various data types, including image, speech, and text** domains. Meanwhile, we acknowledge some limitations of our work. \n- Firstly, our current approach is confined to classification tasks. Expanding the application of our method to a more diverse set of tasks, such as generative modeling or segmentation, is an important future direction. Furthermore, we observed from Figure 5 (b) that the performance gap between our approach and the baselines narrows as the number of data points in the relation graph decreases. While our method demonstrates superior performance even with 12k data from ImageNet, it is essential to address this limitation of decreased performance when dealing with a small number of data points. We will include these discussions in the main text.\n\n**Discussion on computational complexity**  \n- We would like to highlight our theoretical complexity analysis in L159-166. We demonstrate that when utilizing parallel computing, the complexity of our algorithm is $O(k^2)$ for $k\\ll n$, with $n$ representing the total number of data points. In Appendix A.3, we examine the time taken by the algorithm to process a large-scale dataset (1.2M ImageNet) in a real-world computing environment. The results show that our algorithm takes only a few minutes and comprises only 5~20% of the execution time for feature extraction, demonstrating its efficiency in handling large-scale datasets.\n\n**Potential use cases**  \n- Thank you for your suggestion. Our method can be applied to various application scenarios, including data annotation, model evaluation, and robust inference. For instance, our problematic data detection algorithms can aid human annotators during the data annotation process. In addition, as shown in Appendix Figure 13 and Table 19, our algorithm allows for the effective detection and removal of outlier data from the evaluation set, leading to a more accurate model evaluation. Furthermore, our algorithm can determine whether a data point is out-of-distribution during inference, enabling a more reliable inference system. We will incorporate these discussions in the revised version. \n\n**Details on the visualization tool**  \n- The visualization tool described in Section 3.5 helps us to comprehend the distribution of complementary and conflicting relations associated with a data point, aiding dataset analysis and debugging. For example, in Appendix Figure 11, the relation map of the Ram sample exhibits a combination of positive and negative relations. Specifically, it exhibits positive relations with other Ram class samples while showing negative relations with samples from the Big Horn class, which are visually challenging to distinguish. This observation suggests the need for multi-labeling or refinement of the label space definition. In this way, we can intuitively identify problems in the dataset by using the visualization tool. We will elaborate on these explanations in the revised version.\n\n**Details on the datasets**  \n- Thank you for your feedback. The brief description and references for the datasets are provided in lines 239-243. We will update the dataset descriptions in a table format, including the number of data points and classes. These datasets were selected from the baseline methods, focusing on those with large scales. For example, ImageNet was used in the TracIn paper, and MNLI was used in Dataset Cartography. We will update this detailed information in the revision.\n\n**Hyperparameter details**  \n- Thank you for your comment. In Appendix C, Table 5, we provide a summary of the hyperparameters used in our method. As noted, we used a **fixed set of hyperparameters** for each task (label error detection, OOD/outlier detection) across various datasets and models during the evaluation. We performed hyperparameter tuning on ImageNet, guided by the hyperparameter sensitivity analysis presented in Figure 8 and Table 6. The results indicate that our method does not require specific tuning for each model or dataset, enabling efficient adaptation in real-world applications.\n\n**Implementation details**  \n- Our implementation is based on PyTorch, and we conducted each experiment on a single RTX3090-Ti GPU. To optimize computation efficiency, we utilized a caching technique to store the initial label noisiness scores, as described in lines 140-143. Moreover, in Appendix C.1, lines 599-601, we provided an implementation detail for handling small noisy values. We will release the detailed source code for reproducibility.\n\n**Potential future direction**  \n- Thank you for your feedback. We briefly described the future direction of our approach in Appendix B, lines 568-574. We believe expanding our approach beyond classification to encompass tasks like generative modeling or segmentation is an important future direction. Furthermore, integrating our method into a real-world data annotation process is one of the future directions. We will elaborate on these points in the main text.\n\n**Potential negative social impact**  \n- Our research primarily focuses on tackling technical challenges related to label errors and outliers, and does not directly relate to sensitive social issues. Nevertheless, we acknowledge the possibility that the algorithm could be utilized to detect specific group data, potentially leading to social implications. During the revision process, we will emphasize in the main text that the primary objective of our paper is strictly confined to addressing technical issues and does not advocate any discriminatory usage of the algorithm.\n\nThank you once again for the valuable feedback. If you have any remained questions, please let us know."}]

Author rebuttal:
Dear reviewers,

Thank you for your valuable effort and time in providing helpful feedback on our work. We sincerely appreciate your encouraging comments, including:

- The paper introduces a novel method, provides a fresh perspective into the problem, and is highly original. (Reviewer nM5G, 6KY3, Yk3p) 
- The paper tackles an important problem, making its potential impact highly relevant and timely (Reviewer nM5G)
- Extensive and solid experiments show the improvement of the new method is promising. (Reviewer 6KY3, Cygf)
- The clarity of the paper is excellent (Reviewer Yk3p)

We have carefully considered all the points raised and provided rebuttals accordingly. If you have any further questions, please let us know. We will reflect all discussions in the revision and release the code for reproducibility.

Best regards,  
The authors

Meta-review: This paper introduces a unified method that leverages graph structures to detect label errors and outliers. The core idea is to build a relation graph by using training data and identify label errors or outliers using a min-cut algorithm based on a noisiness score. 

During the rebuttal, reviewers acknowledge that 1). A novel approach is proposed for identifying label noise and outlier; 2). contributes to an important problem; 3). The written quality overall is high.

Reviewers have also voiced some concerns about the clarity regarding the method's limitations, its unique advantages, the omission some baselines, and possible issues related to computational complexity. After the response by the authors, the raised concerns are properly addressed. One reviewer increased score. All reviewers' scores are now positive.

AC recommends acceptance of this paper. For the camera-ready version, the authors should integrate the reviewers' feedback and implement the suggested changes. For the convenience of readers, it would also be great to include a brief survey of learning with noisy labels, e.g., covering model-free methods and transition-matrix-based methods.
Decision: Accept (poster)