How does a Neural Network's Architecture Impact its Robustness to Noisy Labels?
Authors: Jingling Li
Mozhi Zhang
Keyulu Xu
John P Dickerson
Jimmy Ba
Venue: NeurIPS 2021 Poster (2021)
Keywords: noisy labels
architectural inductive bias
algorithmic alignment
graph neural networks

Abstract: Noisy labels are inevitable in large real-world datasets. In this work, we explore an area understudied by previous works --- how the network's architecture impacts its robustness to noisy labels. We provide a formal framework connecting the robustness of a network to the alignments between its architecture and target/noise functions. Our framework measures a network's robustness via the predictive power in its representations --- the test performance of a linear model trained on the learned representations using a small set of clean labels. We hypothesize that a network is more robust to noisy labels if its architecture is more aligned with the target function than the noise. To support our hypothesis, we provide both theoretical and empirical evidence across various neural network architectures and different domains. We also find that when the network is well-aligned with the target function, its predictive power in representations could improve upon state-of-the-art (SOTA) noisy-label-training methods in terms of test accuracy and even outperform sophisticated methods that use clean labels.

How Does a Neural Network's Architecture Impact Its Robustness to Noisy Labels?
Jingling Li
Mozhi Zhang
Department of Computer Science University of Maryland College Park, MD 20740 j jinglinggee ingêcs umd edu
Department of Computer Science
University of Maryland College Park, MD 20740
mozhi @cs umd. edu
Keyulu Xu
Computer Science and Artificial Intelligence Laboratory (CSAIL) Massachusetts Institute of Technology (MIT)
Cambridge, MA 02139 keyulu@mit. .ddu
John Dickerson
Jimmy Ba
Department of Computer Science University of Maryland College Park, MD 20740 johnêcs. umd. edu
Department of Computer Science University of Toronto, Canada jbaêes. toronto.
Abstract
Noisy labels inevitable in large real-world datasets. In this work, we explore area understudied by previous works - how the network's architecture impacts its robustness noisy labels. We provide formal framework connecting the robustness of network to the alignments between its architecture and target/noise functions. Our framework measures a network's robustness via the predictive power in its representations the test performance of a linear model trained on the learned representations using small a network is more robust to noisy labels if its architecture is more aligned with the target function than the noise. To support our hypothesis, we provide both theoretical and empirical evidence across various neural network architectures and different domains. We also find that when the network well-aligned with the target function, its predictive power in representations could improve upon state-of-the-art (SOTA) boisy-label-training methods terms of test accuracy and even outperform sophisticated methods that use clean labels.
clean labels. We hypothesize that
Introduction
Supervised learning starts with collecting labeled data. Yet, high-quality labels are often expensive.
To reduce annotation cost, collect labels from non-experts [1] online queries [577], which are
inevitably noisy. To learn from these noisy labels, previous works propose many techniques, including
modeling the label noise 1-10), designing robust losses [1H144, adjusting loss before gradient
updates [3), selecting trust-worthy samples [12
22
24
31
designing robust architectures [32
39 applying robust regularization in training 40 using meta-learning to avoid over-fitting [46]
and applying semi-supervised learning 28 48
to learn better representations.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

While these methods improve some networks' robustness to noisy labels, we observe that their effectiveness depends on how well the network's architecture aligns with the target/noise functions, and they are less effective when encountering more realistic label noise that is dlasedeepn or instance-dependent. This motivates us to investigate an understudied topic: how the network's architecture impacts its robustness to noisy labels.
We formally answer this question by analyzing how network's architecture aligns with the target function and the noise. To start, we measure the robustness of network via the predictive power in its learned representations (Definition I. as models with large test errors may still learn useful predictive hidden representations [52 [3 Intuitively, the predictive power measures how well the representations can predict the target function. practice, we measure by training a linear model on top of the learned representations using a small set of clean labels and evaluate the linear model's test performance
We find that a network having a more aligned architecture with the target function is more robust noisy labels due its more predictive representations, whereas a network having an architecture more aligned with the noise function is less robust. Intuitively, a good alignment between network's s architecture and a function exists the architecture can be decomposed into several modules such that each module can simulate one part of the function with a small sample complexity. The formal definition of alignment is in Section 2.3 adapted from 55
Our proposed framework provides initial theoretical support for our findings on a simplified noisy setting (Theorem 2 Empirically, we validate our findings synthetic graph algorithmic tasks by designing several variants of Graph Neural Networks (GNNs), whose theoretical properties and alignment with algorithmic functions have been well-studied (55 Many noisy label training methods are applied to image classification datasets, so we also validate our findings on image domains using different architectures.
Most of our analysis and experiments use standard neural network training. Interestingly, we find similar results when using DivideMix [49]. SOTA method for learning with noisy labels: for networks less aligned with the target function, the SOTA method barely helps and sometimes even hurts test accuracy; whereas for more aligned networks, it helps greatly.
For well-aligned networks, the predictive power of their learned representation could further improve the test performance of SOTA methods, especially on class-dependen or instance-depende label noise where current methods on noisy label training are less effective. Moreover, on Clothing M (58), a large-scale dataset with real-world label noise, the predictive power of well-aligned network's learned representations could even outperform some sophisticated methods that use clean labels.
In summary, we investigate how an architecture's alignments with different (target and noise) functions affect the network's 'ss robustness to noisy labels, which we discover that despite having large test errors, networks well-aligned with the target function can still be robust to noisy labels when evaluating their predictive power in learned representations. To formalize our finding, we provide a theoretical framework to illustrate the above connections. At the same time, we conduct empirical experiments on various datasets with various network architectures to validate this finding. Besides, this finding further leads to improvements over SOTA loisy-lbbel-traiing methods on various datasets and under various kinds of noisy labels (Tables 10 in Appendix A).
1.1 Related Work
commonly studied type of noisy label is the random label noise, where the noisy labels are drawn i. from a uniform distribution. While neural networks trained with random labels easily overfit (59). has been observed that networks learn simple patterns first (52). converge faster on downstream tasks (53), and benefit from memorizing atypical training samples [60].
Accordingly, many recent works noisy label training are based on the assumption that when trained
with noisy labels, neural networks would first fit to clean labels 12 25 26 50 and learn useful
feature patterns [18 61 63). Yet, these methods are often more effective random label noise than
on more realistic label noise (i.e., class-dependent and instance-dependent label noise).
Many works on representation learning have investigated the features preferred by network during training [2 64 66), and how to interpret or control the learned representations on clean data [54] 64 67
69
Our paper focuses more on the predictive power rather than the explanatory power

---

in the learned representations. We adapt the method in [54] to measure the predictive power in representations, and we study learning from noisy labels rather than from clean distribution.
On noiseless settings, prior works show that neural networks have the inductive bias to learn simple patterns [52] 66]. Our work formalizes what is considered simple pattern for a given network via architectural alignments, and we extend the definition of alignment in [5 to noisy settings.
2
Theoretical Framework
In this section, we introduce our problem settings, give formal definitions for "predictive power" and "alignment," and present our main hypothesis as well our main theorem.
2.1 Problem Settings
Let X' denote the input domain, which can be vectors, images, or graphs. The task is to learn an un- derlying target function f: X + y noisy training dataset S = {( y:)] U { út) Her, where == (xx denotes the true label for an input æ, and I denotes the noisy label. Here, the set I
contains indices with clean labels, and I' contains indices with noisy labels. We denote noise ratio in the dataset S. We consider both regression and classification problems.
[T') [S]
as the
Regression settings. We consider a label space y C IR and two types of label noise: a) additive label noise [70] : y + e, where e random variable independent from æ; dependet label noise: == g(x)) where g X'' - ) is noise function dependent on the input.
Classification settings. We consider discrete label space with C' classes: Y (1,2..... .C, and three types of label noise: a) uniform label noise: ÿ ~ Unif(1, C),, where the noisy label is drawn from discrete uniform distribution with values between 1 and C, and thus is independent of the true label; b) flipped label noise: ý is generated based on the value of the true label and does not consider other input structures; c) instance-dependent label noise: ý g(x) where g X' + y is function dependent on the input æ's internal structures. Previous works on noisy label learning commonly study uniform and flipped label noise. few recent works [7] 72) explore the instance-dependent label noise as it is more realistic.
2.2 Predictive Power in Representations
network's robustness is often measured by its test performance after trained with noisy labels. Yet, since models with large test errors may still learn useful representations, we measure the robustness of a network by how good the learned representations are at predicting the target function the predictive power in representations. To formalize this definition, we decompose a neural network ' into different modules N1, N2, ... where each module can be single layer (e.g., a convolutional layer) or a block of layers (e.g., residual block).
Definition 1. (Predictive power). Let : X y denote the underlying target function where the input æ E X' is drawn from distribution 'D. Let C = {(x,;, ys ys)) | denote small set of clean data (i.e., f(x:)). Given a network N with modules NG. let (xx) denote the representation from module N2 on the input (i.e., the output of Nf). Let denote the linear model trained with the clean set C where we use (x) as the input, and y/4 as the target value during training. Then the predictive power of representations from the module N, is defined as
Pf(f,N.C)=
E [((6)),
ænD
where is loss function used evaluate the test performance the learning task.
Remark. Notice that smaller PJ C) indicates better predictive power; i.e., the representations are better at predicting the target function. We empirically evaluate the predictive power using linear regression to obtain trained linear model I., which avoids the issue of local minima as we are solving convex problem; then evaluate L on the test set.

---

2.3 Formalization of Alignment
Our analysis stems from the intuition that a network would be more robust to noisy labels if could learn the target function more easily than the noise function. Thus, we use architectural alignment to formalize what is easy to learn by given network. Xu et al. [55] define the alignment between network and a deterministic function via a sample complexity measure (i.e., the number of samples needed to ensure low test error with high probability) in PAC learning framework (Definition 3.3 (55) Intuitively, network aligns well with function if each network module can easily learn one part of the function with a small sample complexity.
in Xu et al.
Definition 2. (Alignment, simplified based on Xu et al. (55)). Net denote neural network with n modules Ny. Given a function f : X' + y which can be decomposed into n functions fy (e.g., f(x) (f. (x)) ))), the alignment between the network N and f is defined via
Alignment(N, f, y MA, Nf,
where MA, (f,, 6,0) d) denotes the sample complexity measure for Nj to learn fy with precision failure probability 8 under a learning algorithm Aj.
Remark. Notice that smaller Alignmenr(N (N f: c, 6) indicates better alignment between network N and function f. If ff is obtuse does not have structural decomposition, can choose 1, and the definition of alignment degenerates into the sample complexity measure for N to learn f. Although it is sometimes non-trivial compute the exact alignment for task without clear algorithmic structures, we could break this complicated task into sub-tasks, and would be easier to measure the sample complexity of learning each sub-task.
Xu et al. (55) further prove that better alignment implies better sample complexity and vice versa. Theorem 1. (Informal: (55)) Fix e and 8. Given a target function f : X - y and a network N. suppose { are Li.d. samples drawn from distribution D, and let :- f(x)). Then Alignment( 5,,,,, M if and only if there exists a learning algorithm A such that
PAND [IINN,(()) f(x))I S 5 1121-
where IN,A is the function generated by A on the training data {x.4- V1 )
Remark. Intuitively, a function f (with a decomposition {fg}s) can be efficiently learned by network N (with modules {NgHy) iff each fy can be efficiently learned by Ng..
We further extend Definition 2 to work with random process F (i.e., set of all possible sample functions that describes the noisy label distribution).
Definition 3. (Alignment, extension to various noise functions). Given a neural network W and random process F, for each f E F. the alignment between A and f is measured via max, MA, (,,, 5) based on Definition Then the alignment between A and defined as
Alignment" (N,F,e, := sup max (f,,Ny,,e,), feF
where N can be decomposed differently for various f.
2.4 Better Alignment Implies Better Robustness (Better Predictive Power)
Building on the definitions of predictive power and alignment, we hypothesize that a network better-aligned with the target function (smaller Aligument(NN, f, 6)) would learn more predictive representations (smaller (f,,NCCC) when trained on a given noisy dataset.
Hypothesis 1. (Main Hypothesis). Let f > y denote the target function. Fix e, 6, a learning algorithm A, noise ratio, and noise function X' + y (which may be drawn from a random process). Let denote a noisy training dataset and C denote small set of clean data. Then for network N trained on S with the learning algorithm A.
Aligmmen(NN, f,,, - P,0,,N,C) 4,
(4)
where j is selected based on the network's architectural alignment with the target function (for simplicity, consider j in this work).

---

We prove this hypothesis for simplified case where the target function shares some common struc- tures with the noise function (e.g., class-dependent label noise). We refer the readers to Appendix C for full statement of our main theorem with detailed assumptions.
Theorem 2. (Main Theorem; informal) For a target function f - y and a noise function
g X - Y. consider neural network N well-aligned with I such that P, C) is small when training N on clean data (i.e., PJ
NNN. C) < e efor some small constant c). If there exists a function
on the input domain X such that I and g can be decomposed as follows: Vx E X, f(x) Jr (h(r))
with fr being a linear function, and g(z) = gr (h(x))) ) for some function gr. then the representations learned by N the noisy dataset still have good predictive power with P,f,,NCC <
We further provide empirical support for our hypothesis via systematic experiments on various architectures, target and noise functions across both regression and classification settings.
3 Experiments on Graph Neural Networks
We first validate our hypothesis on synthetic graph algorithmic tasks by designing GNNs with different levels of alignments to the underlying target/noise functions. We consider regression tasks. The theoretical properties of GNNs and their alignment with algorithmic regression tasks well- studied 57 73). To start, we conduct experiments on different types of additive label noise and extend our experiments instance-dependent label noise, which closer to real-life noisy labels.
Common Experimental Settings. The training and validation sets always have the same noise ratio, the percentage of data with noisy labels. We choose Error (MAE) as our loss functions. Due to space limit, the results using MAE are in Appendix [A.3] All training details are in Appendix [B.3] The test error is measured by mean absolute percentage error (MAPE), a relative error metric.
squared error (MSE) and Mean Absolute
3.1 Background: Graph Neural Networks
GNNs are structured networks operating on graphs with MLP modules [7 The input is graph g = (V. E) where each node u E V has a feature vector 2u, and we use (N) to denote the set of neighbors of GNNs iteratively compute the node representations via message passing: (1) the node representation h. is initialized as the node feature: h: æ.i (2) iteration k L..K, the node representations (k) are updated by aggregating the neighboring nodes' representations with MIP modules [8T). We can optionally compute a graph representation hg by aggregating the final node representations with another MLP module. Formally,
h (k)
Σ MEN(M)
MLP(() (n (k-1) (11-1),1!--111 11/
(5)
hg = MLP(K+1)
(K)
(6)
WEGT
Depending on the task, the output is either the graph representation hG or the final node representa- tions (K), We refer to the neighbor aggregation step for (kk as aggregation and the pooling step for hg as readout. Different tasks require different aggregation and readout functions.
3.2 Additive Label Noise
Hu al. [70] prove that MLPs are robust additive label noises with zero mean, if the labels are drawn i.i.d. from Sub-Gaussian distribution. Wu and Xu [82] also show that linear models are robust to zero-mean additive label noise even in the absence of explicit regularization.
this section, we show that GNN well-aligned to the target function not only achieves low test errors on additive label noise with zero-mean, but also learns predictive representations on noisy labels that are drawn from non-zero-mean distributions despite having large test error.
Task and A Architecture. The task is to compute the maximum node degree:
f(g) max vEN(u)
Σ
1.
5

---

Module
Module(!)
30
hig MLP (2) (max
MLP (hw Hy))
25
KES
DEN
(()) i mmax
-15
WCS
PCN
10
22
f1()
Figure 1: Max-sum GNN aligns well with the task maximum degree. Max-sum GNN hg be decomposed into two modules: Module and Module and the target function f(g) be similarly divided as f()) = fa(fi( As the nonlinearities of the target function have been en- coded in the GNN's architecture, (C) can be eas- ily learned hg: f+) can be easily learned by (* and fa(-) is the same as !odule!
PCA visualization of hidden represen- tations from a max sum GNN trained with addi- tive label noise drawn from ((00 15) at 100% noise ratio. Each dot denotes single training ex- ample and is colored with its true label. The x-axis and y-axis denote the projected values the first and second principal components. As the colors change gradually from left to right, the largest prin- cipal component of the representations have clear linear relationship with the true labels.
Figure 2:
We choose this task as we know which GNN architecture aligns well with this target function 2 2-layer GNN with aggeegggen and sum-readout (max-sum GNN):
hg 2LP
max.eg
Σ
MLP(1) (bus (hr))
(8)
vEN(u)
h2 =
Σ vEV(u)
MLP
Lu. 2.
(9)
Figure demonstrates how exactly the max-sum GNN aligns with fG).. Intuitively, they are well- aligned the MLP modules of max-sum GNN only need to learn simple constant functions to simulate f(g). Based Figure 1 take the output of Module as the learned representations for max-sum GNNs when evaluating the predictive power.
Label Noise. We corrupt labels by adding independent noise drawn from three distributions: Gaussian distributions with zero mean (O, 40) and non-zero mean ((10, 15), and long-tailed Gamma distribution with zero-mean I(2, 1/15) 30. We also consider more distributions with non-zero mean in Appendix A.2
Findings. In Figure 3 while the max-sum GNN is robust to zero-mean additive label noise (dotted yellow and purple lines), its test error is much higher under non-zero-mean noise N(00, 15) (dotted red line) as the learned signal may be "shifted" by the non-centered label noise. Yet, max-sum GNNs learned representations under these three types label noise predict the target function well when evaluating their predictive powers with 10% clean labels (solid lines in Figure 3).
Moreover, when we plot the representations (using PCA) from max-sum GNN trained under 100%
noise ratio with e ~ (10,, 15), the representations indeed correlate well with true labels (Figure 2 This explains why the representation learned under noisy labels can recover surprisingly good test performance despite that the original model has large test errors.
The predictive power of -inttali-i max-sum GNNs is in Table (Appendix A.I
3.3 Instance-Dependen Label Noise
Realistic label noise is often instance-dependent For example, an option is often incorrectly priced in the market, its incorrect price (i.e., the noisy label) should depend on properties of the underlying stock. Such instance-dependen label noise is more challenging, as it may contain spurious signals that are easy to learn by certain architectures. In this section, we evaluate the representation' predictive power for three different GNNs trained with instance-dependent label noise.

---

40
<- --N 40)
3
DeepSit
max max CNN
mi sum GNN
E- -(100 15)
12
Test Test MAPE (%)
30
T(2, 1/15) 30
Test MAPE (log
25
15-
3
10
1.
15
20
40 60 50 [00
Noise ratio (%)
0
20
40
60
80
100
Noise ratio (%)
Figure 4: Representations are more predictive for GNNs more aligned with the target func- tion, and less predictive for GNNs more aligned with the noise function. On the maximum node feature task, while all three GNNs have large test errors under high noise ratios (dotted lines), the predictive power (solid lines) in representations from Deepset (yellow) and max-max GNN (red) greatly reduces the test MAPE. In contrast, the rep- resentation's 's predictive power for max-sum GNN barely reduces the model's test MAPE (tiny gap between dotted and solid purple lines).
Figure Representations are very predictive for a GNN well-aligned with the target function under additive label noise. On the maximum de- gree task, the representations' predictive power (solid lines) achieves low test MAPE (< 5%) across all three types noise the max-sum GNN, despite that the model's test MAPE (dot- ted lines) may be quite large (for noise). We average the statisties over runs using different random seeds.
Task and Label Noise. We experiment with a new task compuunng the maximum node feature:
(()) == max g puullss
(10)
To create a instance-dependent noise, we randomly replace the label with the maximum degree:
(
max
Σ
(11)
vEN(w)
Architecture. We consider three GNNs: DeepSet 83 max-max GNN, and max-sum GNN. DeepSet can be interpreted special GNN that does not use neighborhood information:
hg = MLP(1)
mmxx,ecMLP(O)
(12)
Max-max GNN is a 2-layer GNN with max-aggregation and max-readout. Max-sum GNN the same as the one in the previous section.
DeepSet and max-max GNN are well-aligned with the target function f()), as their MLP modules only need to learn simple linear functions. In contrast, max-sum GNN is more aligned with g(G) than fG) since neither its MLP modules sum-aggregation module can efficiently learn the max-operation in f() 57)
Moreover, DeepSet cannot learn (()) the model ignores edge information. We take the hidden representations before the last MLP modules in all three GNNs and compare their predictive power.
Findings. While all three GNNs have large test errors under high noise ratios (dotted lines in Figure the predictive power in representations from GNNs more aligned with the target function DeepSet (solid yellow line) and max-max GNN (solid red line) significantly reduces the original models' test errors by 10 and 1000 times respectively. Yet, for the max-sum GNN, which is more aligned with the noise function, training with noisy labels indeed destroy the internal representations such that they are no longer to predict the target function - its representations' predictive power (solid purple line) barely decreases test error. We also evaluate the predictive power of these three types of randomly-initialized initialized GNNs, and the results are in Table (Appendix A.. A.I.
4 Experiments on Vision Datasets
Many noisy label training methods are benchmarked on image classification; thus, we also validate our hypothesis on image domains. We compare the representations' predictive power between MLPs and CNN-based networks using 10% clean labels (all models are trained until they could perfectly fit the noisy labels, a.k.a., achieving close to 100% training accuracy). We further evaluate the predictive
7

---

CIFAR-Easy
0
2
100
Test. Accuracy (%)
5
80
8 (4) Class locations
40
MLP
CNN
Oh) The masked
2000
7500
15 30
25
# of training samples
image
( "cal" image from CIFARIO
Figure 6: Sample complexity of MLPs and CNNs on CIFAR-Easy. Both MLPs and CNNs can achieve 100% test. accuracy given sufficient training examples, but MLPs need far fewer exam- ples than CNNs and thus more sample-efficient CIFAR-Easy.
Figure 5: Synthetic Labels on CIFAR-Easy. For each image, we mask pixel the top left corner with pink color. Then the synthetic label for this image the location of the pink pixel/mask (i.c., the cat image in the above example has label 4),
power in representations learned with SOTA methods. Predictive power on networks that aligned well with the target function could further improve SOTA method's test performance (Section 4.2). The final model also outperforms some sophisticated methods on noisy label training which also use clean labels (Appendix A.4). All our experiment details are in Appendix B.4
4.1 MLPs vs. CNN-based networks
To validate our hypothesis, we consider several target functions with different levels of alignments to MLPs and CNN-based networks. All models in this section are trained with standard procedures without any robust training methods or robust losses.
Datasets and Label Noise. We consider two types of target functions: one aligns better with CNN-based models than MLPs, and the other aligns better with MLPs than CNN-based networks.
1). CIFAR-10 and CIFAR-100 [4] come with clean labels. Therefore, we generate two types of noisy labels following existing works: (1) uniform label noise randomly replaces the true labels with all possible labels, and (2) flipped label noise swaps the labels between similar classes (e.g.. deert+ dog+>cat) on CIFAR-10 10 [4). or flips the labels to the next class CIFAR- -10AR-100-- [
2). CIFyR-Easy a dataset modified on CIFAR-10 10 with labels generated by procedures in Figure
the class/label of each image depends on the location of a special pixel. We consider three types
of noisy labels on CIFAR-Easy: (1) uniform label noise and (2) flipped label noise (described as
above); and (3) instance-d label noise which takes the original image classification label as the noisy label.
Uniform Noise (CIFAR-10)
F Flipped Noise (CIFAR-10)
Uniffomm Noise (CIFAR-160)
Flipped Naise (CIFAR (CFFAR-100)
70
nocumcy
52
90
MLP
20
42
10
Noise ratio (%)
ratio (%)
Noise ratio (%)
Figure 7: CIFAR-10/100 with uniform and flipped label noise. Fach line indicates the raw test accuracy (dotted) and the predictive power in representations (solid) learned by a model trained across various noise ratios.
As CNN-based networks align better with image classification tasks than MLPs. their representations' predictive power (solid yellow and red lines) higher than that of MLPs (solid purple lines) on most noise ratios.
Architectures. On CIFAR-10/100, we evaluate the predictive power in representations for three architectures: 4-yer MLPs, 9-layer CNNs, and 18-layer PreAct ResNets [85]. On CIFAR-Easy compare between MLPs and CNNs. We take the representations before the penultimate layer when evaluating the predictive power for these networks.
As the designs of CNN-based networks (e.g., CNNs and ResNets) are similar to human perception system because of the receptive fields in convolutional layers and a hierarchical extraction of more
8

---

Uniform Noise
Flipped Noise
Instance- Dennndent Noise
Test accuracy (%)
50-
60
40-
MLP
40
20-
CNN
50-
20-
50%
305
75%
90%
Noise ratio (%)
Noise ratio (%)
Noise ratio (%)
Figure 8: CIFAR-Easy with uniform, flipped, and instance-dependent label noise. Each line indicates the raw test accuracy (dotted) and the predictive power in representations (solid) learned by a model trained across various noise ratios. As MIPs align better with the target function than CNN-based networks on CIFAR-Ease their representations' predictive power MLPs (solid purple lines) consistently better than that of CNNs (solid yellow lines) across various noise ratios and noise types.
Table I: Comparison of different networks' test accuracies ( (%) CIFAR-10/11 We color test accuracy red if it lower than the test accuracy from vanilla training, and we color in green if it higher.
CIFARIO
CIFARIOO
Midal
Setting
Unifor
I|
Utifeem
Flpped
||
PC (MI Pt)
DivalaNi (X)
62.2
55.3
34,4
18.1
M4.2
56.8
44.0
32.8
25.0
13.9
7.2
31.5
22.3
1.3
Distridicks Preehiiine Power
10.6
39.0
14.8
18.7
18.5
11.1
11.6
11.1
13.0
Profet
Vovilla rointee
[2)
86-4
58.5
21.3
12.3
96.1
26-8
16.7
613
40.3
11.5
1.9
67A
45.3
24
DisideMic's & Predkctri Power
06.0
94.3
93.5
83.6
94.9
94.0
936
76.6
60.9
30.3
76.8
74.3
76.1
9-Kmeer CNN
Divdd-Mix
8U.5
91.4
55.7
91.3
25.5
78.3
90.9
88.8
544
15.3
71.4
69.0
51.8
72.9
71.
59.0
$3.0
0.3
Deridshiic's Prodecine Power
93.6
91.4
$1.8
93.1
26.3
702
690
and more abstracted features 86 87), CNN-based networks are expected to align better with the target functions than MLPs on image classification datasets (e.g., CIFAR-10/100),
On the other hand, on CIFAR-Easy, while both CNNs and MLPs can generalize perfectly given sufficient training examples, MLPs have a much smaller sample complexity than CNNs (Figure 6 Thus, both MLP and CNN well-alignes with the target function CIFAR-Easy, but MLP is better-aligned than CNN according to Theorem 2 Moreover, since the instance-dependen label on CIFAR-Fas -asy is the original image classificatinn label, CNN is also aligned with this instance- dependent noise function on CIFAR-Easy.
Experimental Results. First, we empirically verify our hypothesis that networks better-aligned with the target function have more predictive representations. As expected, across most noise ratios on CIFAR- 10/100, the representations in CNN-based networks (i.e., CNN and ResNet) are more predictive than those in MIPs (Figure under both types of label noise. Moreover, the predictive power in representations learned by less aligned networks (i.e., MLPs) sometimes are even worse than the vanilla-trained models' test performance, suggesting that the noisy representations on less aligned networks may be more corrupted and less linearly separable. On the other hand, across all three types of label noise CIFAR-Easy, MLPs, which align better with the target function, have more predictive representations than CNNs (Figure S).
Table 2: Comparison of different networks' test accuracies (%) on CIFAR-Easy We color a test accuracy in red if it is lower than the test accuracy from vanilla training, and we color it in green if it is higher.
Model
II
Flipped
Spurtoos meise
80%
90%6
48h5
50%
25%
5075
100%
4dayer (MLP)
Visiila trizzing
100,00
99.88
97.37
96.20
87.52
75.01
51.94
95.55
90:45
60.18
31.05
10:25
DivideMiis (3)
35.35
10. 00000*
59:50
16:33
100.00
$5.36
50.04
10010
100100
45.59
14.16
10.10
CNN
BivieMic'ss Preductio Power
Divadibii (1)
30000
200000
10000
10000
10300
100.00
10.00
10.05
92:25
99.33
98.43
50.00
96.76
96.55
10000
9652
99.59
14.59
10.09
16.70
10.14
10115
The phenomenon that DivideMix fails under 50% uniform noise but succeeds under 80% uniform noise is due to the unstable behaviors of DivideMix's 's division process, indicating that the predictive power in representations could be more stable measure of a model's robustness, the model can fail miscrably (a.k.a., performance close to random guessing), but its learned representation can still predict the target function well.

---

We also observe that models with similar test performance could have various levels of predictive powers in their learned representations. For example, in Figure 8 while the test accuracies of MLPs and CNNs are very similar on CIFAR-Fasy under flipped label noise (i.e., dotted purple and yellow lines overlap), the predictive power representations from MIPs is much stronger than the one from CNNs (i.e., solid purple lines are much higher than yellow lines). This also suggests that when trained with noisy labels, if we do not know which architecture more aligned with the underlying target function, we can evaluate the predictive power in their representations to test alignment.
We further discover for networks well- well-aligned with the target function, its learned representations are more predictive when the noise function shares more mutual information with the target function. We compute the empirical mutual information between the noisy training labels and the original clean labels across different noise ratios on various types of label noise. The predictive power in representations improves as the mutual information increases (Figure T1 in Appendix (A) This explains why the predictive power for a network is often higher under flipped noise than uniform noise: at the same noise ratio, flipped noise has higher mutual information than uniform noise. Moreover, comparing across the three datasets in Figure [I] we observe the growth rate of network's s predictive power w.r.t the mutual information depends on both the intrinsic difficulties of the learning task and the alignment between the network and the target function.
4.2 Predictive Power in Representations for Models Trained with SOTA Methods
As previous experiments are standard training procedures, we also validate our hypothesis on models learned with SOTA methods on noisy label training. We evaluate the representations' predictive power for models trained with the SOTA method, DivideMix [49]. which leverages techniques from semi-supervised learning to treat examples with unreliable labels as unlabeled data.
We compare (1) the test performance for models trained with standard procedures on noisy labels (denoted as Vanilla training), (2) the SOTA method's test performance (denoted as DivideMix), and (3) the predictive power in representations from models trained with DivideMix in (2) (denoted as Mix's Predictive Power).
We discover that the effectiveness of DivideMix also depends on the alignment between the network and the target/noise functions. DivideMix only slightly improves the test accuracy of MLPs on CIFAR- 10/100 (Table I]. and DivideMix's s predictive power does not improve the test performance of MLPs, either. In Table 2 DivideMix also barely helps CNNs as they are well-aligned with the instance-dependent noise, where the noisy label is the original image classification label.
Moreover, we observe that even for nelworks well-aligned with the target function, DivideMix may only slightly improve or do not improve its test performance at all (c.g., red entries of DivideMix on MLPs in Table 2). Yet, the representations learned with DivideMix can still be very predictive: the predictive power can achieve over 50% improvements over DivideMix for CNN- models on CIFAR-10/100 (e.g., 80% flipped noise), and the improvements can be over 80% for MLPs on Casy (e.g., 90% uniform noise).
Tables I and 2 shows that the representations' predictive power on networks well aligned with the target function could further improve SOTA test performance. Appendix [A.4 further demonstrates that on large-scale datasets with real-world noisy labels, the predictive power in well-aligned networks could outperform sophisticated methods that also use clean labels (Table 9 and Table T0p.
5 Concluding Remarks
This paper is an initial step towards formally understanding how a network's 's architectures impacts its robustness to noisy labels. We formalize our intuitions and hypothesize that network aligee with the target function would learn more predictive representations under noisy label training. We prove our hypothesis on simplified noisy setting and conduct systematic experiments across various noisy settings to further validate our hypothesis.
Our empirical results along with Theorem Theorem[jsugges that knowing more structures of the target function can help design more robust architectures. practice, although an exact mathematical formula for a decomposition of a given target function is often hard to obtain, high-level decomposition of the target function often exists for real-world tasks and will be helpful in designing robust architectures direction undervalued by existing works on learning with noisy labels.
10

---

Acknowledgments
We thank Denny Wu, Xiaoyu Liu, Dongruo Zhou, Vedant Nanda, Ziyan Yang, Xiaoxiao Li, Jiahao Su, Wei Hu, Bo Han, Simon S. Du, Justin Brody, and Don Perlis for helpful feedback and insightful discussions. Additionally, we thank Houze Wang, Qin Yang, Xin Li, Guodong Zhang, Yixuan Ren, and Kai Wang for help with computing resources. This research is partially performed while Jingling Li a remote research intern at the Vector Institute and the University of Toronto. Li and Dickerson were supported by an ARPA-E DIFFERENTIATE Award, NSF CAREER IIS- (IS-184627,, NSF CCF-1 1852352. NSF D-ISN #2039862. NIST MSE #20126334, NIH ROI NLM-01 3039--00, DARPA GARD #HR001 12020007, DoD WHS #HQ003420F0035,, and Google Faculty Research Award. Ba is supported in part by the CIFAR AI Chairs program, LG Electronics, and NSERC. Xu is supported by NSF CAREER award 1553284 and NSF III 1900933. Xu is also partially supported by IST ERATO JPMJERI20 and JSPS Kakenhi JP18H05291. Zhang is supported by ODNI, IARPA, via the BETTER Program contract #2019- 1905 1600005. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed implied, of ODNI, IARPA, the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
References
[1] Rion Snow, Brendan O' D'connor, Dan Jurafsky, and Andrew Y Ng. Cheap and fast-but good? evaluating non-expert annotations for natural language tasks. In Proceedings of Empirical Methods in Natural Language Processing, 2008
[2] Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie. The multidimensional wisdom of crowds. In Advances in neural information processing systems, pages 2424 2432, 2010.
[3] Yan Yan, Rómer Rosales, Glenn Fung, Ramanathan Subramanian, and Jennifer Dy. Learning from multiple annotators with varying expertise. Machine learning, 95(3):291-327, 2014.
[4] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the European Conference on Computer Vision (ECCV), pages 68-88 83,, 2018.
[5] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), (0(())00005)5))) 519, 2003.
[6] Lu Jiang, Di Huang, Mason Liu, and Weilong Yang. Beyond synthetic noise: Deep learning on controlled noisy labels. In ICML, 2020. URL https:: wwtp:///gga/aa/ageeeeo 1911109119999
[7] Wei Liu, Yu-Gang Jiang, Jiebo Luo, and Shih-Fu Chang. Noise resistant graph ranking for improved web image search. In CVPR 2011, pages 849-856. IEEE, 2011.
[8] Nagarajan Natarajan, Inderjit Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances neural information processing systems, pages 1196-1204, 2013.
[9] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on pattern analysis and machine intelligence, 38(3):447-461 2015.
[10] Yu Yao, Tongliang Liu, Bo Han, Mingming Gong. Jiankang Deng. Gang Niu, and Masashi Sugiyama. Dual t: Reducing estimation error for transition matrix in label-noise learning. arXiv preprint 07880 2020.
[11] Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. arXiv preprint 1721v:1712.09452. 2017.
[12] Yueming Lyu and Ivor W Tsang. Curriculum loss: Robust learning and generalization against label corruption. arXiv preprint orXiv: 10045, 2019.
[13] Yisen Wang, Xingjun Ma, Zaiyi Chen. Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE International Conference on Computer Vision, pages 322 2200 2019.
[14] Zhilu Zhang and Men Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances neural information processing systems, pages 8778-8788. 2018
11

---

[15] Eric Arazo, Diego Ortego. Paul Albert. Noel E O' CoCnnor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. arXiv preprint arXiv:1904.1122 12238 2019.
[16] Haw-Shiuan Chang, Erik Learned Learned-Miller, and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Advances in Neural Information Processing Systems, pages 1002-1012, 2017.
[17] Bo Han, Gang Niu, Xingrui Yu, Quanming Yao, Miao Xu, Ivor W Tsang, and Masashi Sugiyama. Sigua: Forgetting may make learning with noisy labels more robust. In Proceedings of the 37-th International conference on machine learning (ICML-20), 2020.
[18] Dan Hendrycks, Mantas Mazeika, Dunean Wilson, and Kevin Gimpel. Using trusted data to train deep networks on labels corrupted by severe noise. In Advances in neural information processing systems, pages 10456-10465, 10465, 2018.
[19] Xingjun Ma, Yisen Wang. Michael Houle, Shuo Zhou, Sarah Erfani, Shu-Tao Xia, Sudanthi Wijewickrema, and James Bailey. Dimensionality-drienn learning with noisy lahels. arXiv preprint arXiv: 1806.02612, 2018.
[20] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1944-1952, 2017.
[21] Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. arXiv preprint 1Xxv:1412.6596 2014.
[22] Hwanjun Song, Minseok Kim, and Jae-Gil Lee. Selfie: Refurbishing unclean samples for robust deep learning. In International Conference on Machine Learning, pages 5907-5915, 2019.
[23] Ruxin Wang. Tongliang Liu, and Dacheng Tao. Multiclass learning with partially corrupted labels. IEEE transactions neural networks and learning systems, 296))2266 2580, 2017.
[24] Pengfei Chen, Benben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and utilizing deep neural networks trained with noisy labels. arXiv preprint (tt::::9900000044 2019.
[25] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information proessing systems, pages 8527-8537, 2018
[26] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentomet: Learning data-driven driven curriculum for very deep neural networks on corrupted labels. In International Conference on Machine Learning, pages 2304-2313, 23,,, 2018.
[27] Eran Malach and Shai Shalev-Shwartz. Decoupling" when to update" from" how to update". In Advances in Neural Information Processing Systems, pages 960-970, 2017.
[28] Due Tam Nguyen, Chaithanya Kumar Mummadi, Thi Phuong Nhung Ngo, Thi Hoai Phuong Nguyen, Laura Beggel, and Thomas Brox Self: learning to filter noisy labels with self-ensembling. arXiv preprint arXiv: 1910,01842, 2019.
[29] Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning, pages 5739-5748. PMLR, 2019.
[30] Yisen Wang. Weiyang Liu, Xingjun Ma, James Bailey, Hongyuan Zha, Le Song, and Shu-Tao Xia. Iterative learning with open-set noisy labels. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 8688-8699 2018
[31] Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor W Tsang. and Masashi Sugiyama. How does disagreement help generalization against label corruption? arXiv preprint 1X01:1901.042) 2019.
[32] Alan Joseph Bekker and Jacob Goldberger. Training deep neural-networks based on unreliable labels. In 2016 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pages 2682 2686. IEEE, 2016.
[33] Xinlei Chen and Abhinav Gupta. Webly supervised learning of convolutional networks. In Proceedings of the IEEE International Conference Computer Vision, pages 1431-1439 2015.
[34] J. Goldberger and E, Ben-Reuven Training deep 2017.
using noise adaptation layer. In ICLR,
12

---

[35] Bo Han, Jiangchao Yao, Gang Niu. Mingyuan Zhou, Ivor Tsang. Ya Zhang, and Masashi Sugiyama. Masking: A new perspective of noisy supervision. Advances in Neural Information Processing Systems. 31:5836-5846, 2018.
[36] Ishan Jindal, Matthew Nokleby, and Xuewen Chen. Learning deep networks from noisy labels with dropout regularization. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 967-972. IEEE, 2016.
[37] Jingling Li, Yanchao Sun, Jiahao Su, Taiji Suzuki, and Furong Huang. Understanding generalizatnnnnnnnnnnn in deep learning via tensor methods. arXiv preprint arXiv:2001. 2020.
[38] Sainbayar Sukhbaatar, Joan Bruna, Manohar Paluri, Lubomir Bourdev, and Rob Fergus. Training convolu- tional networks with noisy labels. arXiv preprint 1rXiv:1406.2080 2014.
[39] Jiangchao Yao, Jiajie Wang, Ivor W Tsang, Ya Zhang. Jun Sun, Chengqi Zhang, and Rui Zhang. Deep learning from noisy image labels with quality embedding. IEEE Transactions on Image Processing, 28(4): 1909-1922, 2018
[40] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hameessing adversarial examples. In International Conference on Learning Representations, 2015.
[41] Dan Hendrycks, Kimin Lee, and Mantas Mazeika. Using pre-training can improve model robustness and uncertainty. arXiv preprint arXiv:/901.09960 2019.
[42] Simon Jenni and Paolo Favaro. Deep bilevel learning, In Proceedings of the European Conference on Computer Vision (ECCV), pages 618-633 2018.
[43] Gabriel Pereyra, George Tucker, Jan Chorowski, Eukasz Kaiser, and Geoffrey Hinton. Regularizing neural networks by penalizing confident output distributions. arXiv preprint arXiv:1701.06545 2017.
[44] Ryutaro Tanno, Ardavan Sacedi, Swami Sankaranarayanan, Daniel C Alexander, and Nathan Silberman. Learning from noisy labels by regularized estimation of annotator confusion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1244-11253, 2019.
[45] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv: 1710::77100091122 2017.
[46] Luís PF Garcia, André CPLF de Carvalho, and Ana Lorena. Noise detection in the meta-learning level. Neurocomputing, 176:14 14-25, 2016.
[47] Junnan Li, Yongkang Wong, Qi Zhao, and Mohan S Kankanhalli. Learning to learn from noisy labeled data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 505 105599 2019.
[48] Yifan Ding, Liqiang Wang, Deliang Fan, and Boqing Gong. semi-supervised two-stage approach learning from noisy labels. In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV). pages 1215-1224. IEEE, 2018.
[49] Junnan Li, Richard Socher, and Steven CH Hoi. Dividemix: Learning with noisy labels as semi-supervine learning. arXiv preprint arXiv:2002.07334 2020.
[50] Sheng Liu, Jonathan Niles-Weed, Narges Razavian, and Carlos Fernandez-Granda. Early- Learnnng regular- ization prevents memorization of noisy labels. arXiv preprint 2000
[51] Yan Yan, Zhongwen Xu, Ivor Tsang, Guodong Long, and Yi Yang. Robust semi- suni-supervised learning through label aggregation. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[52] Devansh Arpit, Stanistaw Jastrzehski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kan- wal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. arXiv preprint 1ww.vv:7006003%4 2017.
[53] Hartmut Maennel, Ibrahim Alabdulmonsin, Ilya Tolstikhin, Robert JN Baldock, Olivier Bousquet, Sylvain Gelly, and Daniel Keysers. What do neural networks learn when trained with random labels? arXiv preprint arXiv:2006. 10455, 2020.
[54] Guillaume Alain and Yoshua Bengio. Understanding intermediate layers using linear classifier probes. arXiv preprint arXiv:1610.016444 2016.
13

---

[55] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Reprexentations, 2020. URL https://openreview..rt wttpee/ee/oormmm..e.....eeeeeeee
[56] Simon S Du, Kangcheng Hou, Russ Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kemels.. In Advances in Neural Information Processing Systems, pages 5724-5734, 2019.
[57] Keyulu Xu, Mozhi Zhang. Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009. 1848, 2020.
[58] Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang- Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2691-2699, 2015.
[59] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations. 2017.
[60] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. arXiv preprint arXiv:2008.03700 2020.
[61] Kimin Lee, Sukmin Yun, Kibok Lee, Honglak Lee, Li, and Jinwoo Shin. Robust inference via generative classifiers for handling noisy labels. In International Conference on Machine Learning, pages 3763-3772. PMLR, 2019.
[62] Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. In International Conference on Machine Learning, pages 540-550. PMLR, 2020.
[63] Pengxiang Wu, Songzhu Zheng, Mayank Goswami, Dimitris Metaxas, and Chao Chen. A topological filter for learning with label noise. arXiv preprint arX1v:20/2.04335, 2020.
[64] Katherine L Hermann and Andrew K Lampinen. What shapes feature representations? exploring datasets, architectures, and training. arXiv preprint arXiv:2006. 12433, 2020.
[65] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateck Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks. arXiv preprint arXiv:2006.07710 07710, 2020.
[66] Amartya Sanyal, Puneet K Dokania, Varun Kanade, and Philip HS Torr. How benign is benign overfitting? arXiv preprint arXiv:2007.00 044028 2020.
[67] Katherine L Hermann, Ting Chen, and Simon Kornblith. The origins and prevalence of texture bias in convolutional neural networks. arXiv preprint 19X 2019.
[68] Grégoire Montavon, Wojeiech Samek, and Klaus-Robert Müller. Methods for interpreting and understand- ing deep neural networks. Digital Signal Processing, 73:1-15, 2018
[69] Michelle Yuan, Mozhi Zhang. Benjamin Van Durme, Leah Findlater, and Jordan Boyd-Graber Interactive refinement of cross-lingual word embeddings. In Proceedings of Empirical Methods in Natural Language P Processing. 2020.
[70] Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020. httlitttss//openree/r/
[71] Hao Cheng, Zhaowei Zhu, Xingyu Li. Yifei Gong, Xing Sun, and Yang Liu. Learning with instance- dependent label noise: A sample sieve approach. arXiv preprint arXiv:2010.02347, 2020.
[72] Xinshao Wang. Yang Hua, Elyor Kodirov, and Neil Robertson. Proselfle: Progressive self label correction for target revising in label noise. arXiv preprint 2755:22005.03788, 2020.
[73] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios graph neural networks for combinatorial problems. In Advances in Newral Information Processing Systems, pages 4081-4090, 2019.
[74] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro. Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.0223 2018.
14

---

[75] Franco Scarselli, Marco Gori, Ah Chung Tsoi. Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20-1)66-80, 2009.
[76] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations. 2019.
[77] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462, 2018.
[78] Keyulu Xu, Mozhi Zhang. Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. arXiv preprint arXiv:2105.04550 2021.
[79] Peiyuan Liao, Han Zhao, Keyulu Xu, Tommi Jaakkola, Geoffrey J Gordon, Stefanie Jegelka, and Ruslan Salakhutdinov. Information obfuscation of graph neural networks. In International Conference on Machine Learning, pages 6600-6610. PMLR, 2021.
[80] Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: principled approach to accelerating graph neural network training. In International Conference on Muchine Learning, pages 1204-1215, PMLR, 2021.
[81] Justin Gilmer, Samuel S Schoenholz. Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Muchine Learning, pages 1273-1272, 2017.
[82] Denny Wu and Ji Xu. On the optimal weighted E regularization in overparameterized linear regression. arXiv preprint (1di:200060080000 2020.
[83] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Púczos, Ruslan Salakhuidinov, and Alexan- der J Smola. Deep sets. cor abs/1703.061 14 (2017). arXiv preprint orXiv::703.06// 2017.
[84] A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[85] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pages 630-645. Springer, 2016.
(86] Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10); (10):1999, 1995.
[87] Saeed Reza Kheradpisheh, Masoud Ghodrati, Mohammad Ganjtabesh, and Timothée Masquelier. Deep networks can resemble human feed-forward vision in invariant object recognition. Scientific reports, 6(1): 1-24, 2016.
[88] Zizhao Zhang, Han Zhang, Serean O Arik, Honglak Lee, and Tomas Pfister. Distilling effective supervision from severe label noise. CVPR 2020, pages 2294-9303. JEEE, 2020.
[89] Mengye Ren, Wenyuan Zeng, Bin Yang. and Raquel Urtasun. Learnnng reweight examples for robust deep learning. arXiv preprint arXiv: 1803009000 2018
[90] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta-war nett- Learning an explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, pages 1919-1930, 2019.
[91] Kuang- Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5447-5456 2018.
[92] Jiangfan Han, Ping Luo, and Xiaogang Wang. Deep self-learning from noisy labels. In Proceedings of the IEEE International Conference on Computer Vision, pages 5138-5147, 2019.
[93] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool. Webvision database: Visual learning and understanding from web data. arXiv preprint arXiv: 770.0020...2222, 2017.
[94] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Iccc, 2009.
[95] Christian Szegedy, Sergey loffe. Vincent Vanhoucke, and Alex Alemi. Inception-v4, v4, inception resnett and the impact of residual connections on learning. arXiv preprint arXiv:1602.07261, 2016.
15

---

[96] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and semi-supervised learning. IEEE transactions on puttern andysis and machine intelligence. 1199)11979-1993, 2018.
[97] David D Lewis and William A Gale. A sequential algorithm for training text classifiers. In Special Interest Group on Information Retrieval, 1994.
16


Reviews:
[{"review_id": "7tjOUqyG0KR", "reviewer": "Reviewer_Qmfd", "summary": "The paper aims to bridge the connection between the network’s architecture and robustness to noisy labels. I surely agree that this topic is important. However, the presented results are very intuitive rather than theoretical as claimed. The paper does not propose an appliable measurement that has a connection to the robustness and can be obtained empirically (at least qualitatively). The alignment measurement largely follows from existing works and the measurement is not used at all in the presented experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality** and **Clarity**\n\nThe studied topic is novel and important in learning with noisy labels. The paper is clearly written.\n\n**Significance** and **Quality**\n\nThe paper claims to propose a formal framework connecting the robustness of a network to the alignments between its architecture and target/noise functions. However, there are several concerns on the significance and novelty.\n-\tThe robustness is measured by the predictive power in representations, which follows from the work [43]. It is simply the expected test loss after training on clean labels. That is, such a measure is a known result rather than a novel contribution.\n-\tThe alignment measure largely follows from the work [44]. It is straightforward to extend Definition 2 (for a deterministic function) to Definition 3 (for a set of all possible functions).\n-\tThe alignment measure cannot be computed in practice (as admitted by the author on line 126), which limited the utility of the proposed framework.\n-\tThe main theorem (Theorem 2) is based on strong assumptions and a simplified noisy setting.\n-\tThe empirical studies have a limited connection to the proposed numerical framework and do not support the main hypothesis (Hypothesis 1). The alignment measure is not directly demonstrated in experiments (since it can not be computed). Instead, the author directly claims that some architectures have higher/lower alignment with the target functions, based on intuition (line 224-227 and line 262-265). Such claims are not convincing and as a result, the experiments fail to draw a connection to the proposed alignment measure.\n\n**Summary**\n\nGiven the above comments, the paper fails to present results that could go deeper on the common intuition, i.e., the findings presented in the paper are no more than an intuition: a network with architecture more aligned with the target clean function can be more robust to label noise. In experiments, the alignment is still evaluated based on intuition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5Z9dqg2QrDx", "reviewer": "Reviewer_G3rQ", "summary": "This paper studies the impact of model architecture on the robustness of its representation upon training with noisy labels. The main hypothesis in the paper is that if the model architecture is \"aligned\" to the underlying task being solved, then it learns such noise robust representations. This hypothesis is tested using two experimental settings, first using graph neural networks and the second on a CNN / MLP architecture. These experiments confirm the hypothesis considered: in the GNN setting, architectures that are able to represent the underlying max node feature task have noise robust representations, and in the CNN / MLP experiments, CNNs performed better at the default CIFAR experiments and MLP at a synthetic task requiring identifying a particular pixel location. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity: This paper is very clearly written and reads beautifully. The main hypothesis, the accompanying math and the assumptions made are clearly laid out and easy to understand. The experimental section is also explains all settings in detail, and seems like it should be straightforward to reproduce from the description. \n\nOriginality: I am not an expert on the \"learning with noisy labels\" literature, but to the best of my knowledge this paper seems to be the first to analyse the importance of the architecture to this noise robustness property, particularly in this line of reasoning regarding the \"alignment\" of architecture and task. There are no new techniques introduced in this paper, and the only novelty lies in its analysis of the impact of architecture, which I believe is useful.\n\nQuality: This paper is of generally high quality both with regard to theoretical arguments and experiments. Although I see a few issues which I will elaborate below, the claims in the paper are generally well supported by experiments.\n\nSignificance: I believe that understanding the inductive biases of model architecture is of high significance to machine learning in general, and the particular tool of function \"alignment\" is particularly interesting in this regard.\n\nComments:\n\n1) The definition of alignment in this paper considers target functions which have a naturally decomposable structure as a function composition. For functions without such structure, alignment is the same as sample complexity, and Theorem 1 is a tautology. However it is unclear from the paper which practical problems have such decomposable structure, and where such structure is known in advance. The decomposable structure of the max node degree problem in Figure 1 does not benefit from such decomposability property as the sample complexity of learning Module 1 is the same as learning the entire function (as Module 2 does not require learning). Hence it would be great that the draft clarify on the benefit of the decomposability property, and add some practical examples where such problems might occur (maybe distillation?). If not, then it is better to simplify the definition of alignment to mean only sample complexity, and discard the decomposability property.\n\n2) In Section 4.2, there is a remark that the alignment of the noise function with the network is also an important consideration for robustness to noisy labels. In light of this, does it make sense to update the hypothesis 1, to include an assumption that the noise function is unaligned with the network? \n\n3) The paper would benefit from adding a section on examining why hypothesis 1 can be true. For instance, it is also plausible that training with noisy labels can completely destroy the internal representations in such a way that they would no longer have useful predictive power. Why does this not happen? Is it that the training loss on noisy samples is non-zero and these samples are effectively not learnt, possibly an artefact of early stopping or other forms of regularization? Or is it due to over-completeness of representations? If not for experiments, a section on speculating on possible reasons for this phenomenon, or providing a proof sketch for Theorem 2 (which seems to hint at over-completeness of representations), might be instructive for future research.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work has no direct societal impact as it is a fundamental work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "46gFDdtTawt", "reviewer": "Reviewer_oX51", "summary": "This paper studies the model robustness to noisy labels from the neural network architecture perspective. Specifically, the authors propose to investigate the alignment between neural network architecture and the (noise) label function, and identify the connection between the proposed alignment measure and model robustness to label noise. The alignment hypothesis is one of the key contributions of this paper, i.e., 'model architecture more aligned with (noise) label function --> better model robustness to label noise'. Experiments on both graph neural networks (GNN) and vision tasks support this hypothesis.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This submission studies the model robustness from the model architecture perspective by investigating the proposed alignment hypothesis.\n\n**Originality**: The proposed alignment measurement is mainly built on Xu et al. [44].\n\n**Quality**: This submission is a complete piece of work and the claims are well supported by the empirical results. The evaluations are reasonable.\n\n**Clarity**: This submission is well-written and easy to follow.\n\n**Significance**: This paper proposes an interesting hypothesis that is well supported by empirical experimental results.\n\n\nPros:\n\n1. The 'alignment & model robustness' hypothesis is interesting, and this brings a new perspective to understand the model robustness to label noise.\n2. Experiments on both GNN and vision tasks support the proposed hypothesis, and the experiments are well designed.\n3. The 'prior knowledge about structures of the target function' argument is inspiring for improving model robustness to label noise for future work.\n\nCons:\n\n1. The predictive power $P_j(f, \\mathcal{N}, \\mathcal{C})$ requires clean data, and in the label noise setting it is hard to access a set of clean data.\n2. The alignment measurement is not easy to compute. In this submission, several alignment arguments are made by applying prior knowledge. Also, by looking at definition 2, the $\\text{Alignment}(\\mathcal{N}, f, \\epsilon, \\delta)$ requires access to the true function/clean label for calculation.\n\nQuestions:\n\n1. As mentioned in Line 107-109, the predictive power is evaluated by using linear regression. For classification tasks, are the targets just the one-hot encoding vectors? Also, maybe it is more reasonable to apply logistic regression for classification tasks (which is also a convex problem).\n2. For results shown in Figure 3 and Figure 4, could the authors provide the results for models that are randomly initialized? This might provide more information on the alignment between the architecture and the label function.\n3. Could the authors provide one or two baselines in Table 1 and Table 2? For example, methods in [12] and [23] (references in the main body).\n\nOverall, I think this paper provides an interesting perspective for understanding the model robustness to label noise. I would suggest `Marginally above the acceptance threshold'. I would also be willing to raise my score if the questions listed above are answered.\n\n\n\n======================================[updates]======================================\n\nThanks for the authors' response. I have read the authors' responses as well as the other reviews. I will stick with my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There were a range of opinions on the paper amongst the reviewers. Based on my reading of the paper, the insight is limited and there are serious issues in the way "alignment" is used and presented in the paper. Here are the key reasons for rejection:

1. There is a gap between the notion of "alignment" and what's actually being used to evaluate alignment, which seems to be "representation predictive power"; the former of which is difficult to determine in practice and the latter of which involves training a linear model on top of the second-last layer representation using a set of clean labels. Although the paper shows a result that better alignment implies better representation predictive power, the other direction isn't shown and thus the paper actually seems to claim that better representation predictive power implies better robustness to label noise. In other words, this "alignment" as used in the paper is a qualitative measure and lacks rigor.

2. It is not a surprising result that if the performance of the second-last layer is better, then the model will be more robust to label noise. This appears to come from the fact that you have a better model for the task regardless of how noisy the labels are; and the fact that the representation does better than the model itself comes from the fact that the representation is trained on clean labels while the model is trained on noisy labels. Furthermore, it's already known that DNNs tend to learn useful representations even in the presence of noisy labels.

Decision: Accept (Poster)