Patch-level Neighborhood Interpolation:  A General and Effective Graph-based Regularization Strategy
Authors: Ke Sun
Bing Yu
Zhouchen Lin
Zhanxing Zhu
Venue:  (2021)
Keywords: Deep Learning
Regularization
Graph-based Representation

Abstract: Regularization plays a crucial role in machine learning models, especially for deep neural networks. The existing regularization techniques mainly rely on the i.i.d. assumption and only consider the knowledge from the current sample, without the leverage of the neighboring relationship between samples. In this work, we propose a general regularizer called Patch-level Neighborhood Interpolation~(\textbf{Pani}) that conducts a non-local representation in the computation of network. Our proposal explicitly constructs patch-level graphs in different network layers and then linearly interpolates neighborhood patch features, serving as a general and effective regularization strategy. Further, we customize our approach into two kinds of popular regularization methods, namely Virtual Adversarial Training (VAT) and MixUp as well as its variants. The first derived \textbf{Pani VAT} presents a novel way to construct non-local adversarial smoothness by employing patch-level interpolated perturbations. In addition, the second derived \textbf{Pani MixUp} method extends the original MixUp regularization and its variant to the Pani version, achieving a  significant improvement in the performance. Finally, extensive experiments are conducted to verify the effectiveness of our Patch-level Neighborhood Interpolation approach in both supervised and semi-supervised settings.

Under review as a conference paper at ICLR 2021
PATCH-LEVEL NEIGHBORHOOD INTERPOLATION: A GENERAL AND EFFECTIVE GRAPH-BASED REGU- LARIZATION STRATEGY
Anonymous authors Paper under double-blind review
ABSTRACT
Regularization plays crucial role in machine learning models, especially for deep neural networks. The existing regularization techniques mainly rely on the i.i.d. assumption and only consider the knowledge from the current sample, without the leverage of neighhoring relationship between samples. this work, we pro- pose general regularizer called Patch-level Neighborhood Interpolation (Pani) that conducts a non-local representation in the computation of network. Our pro- posal explicitly constructs patch-level graphs in different network layers and then linearly interpolates neighborhood patch features, serving as a general and effec- tive regularization strategy. Further, customize approach into two kinds of popular regularization methods, namely Virtual Adversarial Training (VAT) and MixUp well as its variants. The first derived Pani VAT presents novel way to construct non-local adversarial smoothness by employing patch-level interpo- lated perturbations. In addition, the second derived Pani MixUp method extends the original MixUp regularization and its variant to the Pani version, achieving a significant improvement in the performance. Finally, extensive experiments are conducted to verify the effectiveness of our Patch-level Neighborhood Interpola- tion approach both supervised and semi-supervised settings.
INTRODUCTION
In the statistical learning theory, regularization techniques are typically leveraged to achieve the trade-off between empirical eтror minimization and the control of model complexity (Vapnik & Chervonenkis 2015). In contrast to the classical convex empirical risk minimization where regu- larization can rule out trivial solutions, regularization plays rather different role in deep learning due to its highly non-convex optimization nature (Zhang et al. 2016). Among all the explicit and implicit regularization, regularization with stochastic transformation, perturbations and randomness, such as adversarial training (Goodfellow et al.) 2014), dropout and MixUp (Zhang et al. 2017), play key role in the deep learning models due to their superiority in the performance (Berthelot al.) 2019b] [Zhang et al. 2017 Miyato et al.) 2018 Berthelot et al., (2019a). In this section, we firstly re- view two kinds of effective and prestigious regularization branches for deep neural networks, which can elegantly generalize from supervised learning to semi-supervised setting.
Adversarial Training (Goodfellow et al. 2014 Madry et al. 2017 can provide additional regular- ization beyond that provided by other generic regularization strategies, such as dropout, pretraining and model averaging. However, recent works (Zhang al. 2019 Tsipras et al. 2018) demonstrated that this kind of training method holds trade-off between the robustness and accuracy, limiting the efficacy of the adversarial regularization. Besides, Virtual Adversarial Training (VAT) (Miy- ato et al.] (2088) can be regarded as natural extension of adversarial training to semi-supervised setting through adversarially smoothing the posterior output distribution with the leverage unla- beled data. This strategy has achieved great success in image classification (Miyato et al. 2018)) text classification (Miyato et al. 2016) and node classification (Sun et al. 2019). Tangent- Adversarial Regularization (TNAR) (Yu et al. 2019) extended VAT by taking the data manifold into consideration and applied VAT along the tangent space and the orthogonal normal space of the data manifold, outperforming previous semi-supervised approaches.

---

Under review as a conference paper at ICLR 2021
MixUp (Zhang et al. 2017) augmented the training data by incorporating the prior knowledge that linear interpolation of input vectors should lead to linear interpolation of the associated targets, image, speech and tabular data. Mix- Match (Berthelot et al., 2019b) extended MixUp to semi-supervised tasks by guessing low-entropy labels for data-augmented unlabeled examples and mixing labeled and unlabeled data using MixUp- In contrast with VAT, MixMatch (Berthelot et al.) 2019b) utilizes one specific form of consistency regularization, i.c., using the standard data augmentation for images, such as random horizontal flips, rather than computing adversarial perturbations to smooth the posterior distribution of the classifier.
accomplishing consistent improvement of generalization
Nevertheless, the vast majority of regularization methods, including the aforementioned approaches, assume that the training samples are drawn independently and identically from an unknown data generating distribution. For instance, Support Vector Machine (SVM), Back-Prooaggtioo (BP) for Neural Networks, and many other common algorithms implicitly make this assumption as part of their derivation. However, this i.i.d. assumption is commonly violated in realistic scenarios where batches or sub-groups of training samples are likely to have internal correlations. In particular, Dun- dar et al. (2007) demonstrated that accounting for the correlations in real-world training data leads to statistically significant improvements in accuracy. Similarly, Feer-Regularized Networks (Peer- Net) (Svoboda et al.) (018) applied graph convolutions (Velickovic et al.] 2017: Kipf & Welling 2016 to harness information of peer samples, and verified its effectiveness defending adversarial attacks. Motivated by these facts, we aim to design a general regularization strategy that can fully utilize the internal relationship between samples by explicitly constructing graph within mini- batch in order to consistently improve the generalization of deep neural networks in both semi- and supervised settings.
In this paper, we propose the Patch-level Neighborhood Interpolation (Pani) for deep neural net- works, serving as a simple yet effective non-local regularization. We firstly construct patch-level graph in each mini-batch during the stochastic gradient decent training process. Then we apply linear interpolation on the neighboring patch features and the resulting non-local representation ad- ditionally captures the relationship of neighboring patch features in different layers, serving general and effective regularization. Furthermore, to prove the generality and superiority of our Pani method, we explicitly customize approach into two kinds of popular and general regular- ization strategies, i.e., Virtual Adversarial Regularization and Mix resulting in Pani VAT and Pani MixUp. For the Pani VAT, we reformulate the construction of adversarial perturbations, trans- forming from solely depending on the current sample to the linear interpolation of neighboring patch features. This non-local adversarial perturbations can leverage the information of neighboring corre- lation from all samples within a batch, providing more informative adversarial smoothness in semi- supervised setting. Besides, in the Pani MixUp. we extend MixUp and its variant MixMatch from image to patch level by mixing fine-gre ine-grained patch features and corresponding supervised signals. Fi- nally, we conduct extensive experiments to demonstrate that both of the two derived regularization strategies can outperform other state-of-the tiite-of-the-asd approaches in both supervised and semi- semi-supervised tasks. More importantly, these successful cases verify the generality and superiority of our Patch- level Neighborhood Interpolation method. Our contributions can be summarized as follow:
We propose general interpolation strategy either in input or feature space, i.e., Patch-level Neighborhood Interpolation, helping to improve the generalization of deep neural networks on both semi- and supervised scenarios. This strategy can serve as an effective graph-basee based representation method and has much potential to be leveraged in wider range of tasks.
Based on our method, the customized approaches Pani VAT and Pani MixUP as well as Pani MixMatch can boost the generalization performance significantly, and thus provide a guidance to the deployment of our Pani strategy into more regularization methods.
2 OUR METHOD: PATCH-LEVEL NEIGHBORHOOD INTERPOLATION
Before introducing our approach, we highly recommend readers to go through some preliminary knowledge about VAT (Miyato et al. 2017). MixUP (Zhang et al. 2017) and PeerNet (Svoboda et al. 2018) in Appendix A For our method, one related work is PeerNet (Svoboda et al. 2018) that designed graph- based layers to defend against adversarial attacks, but unfortunately the construction of livel-level K-NN graphs in PeerNet (Svoboda et al.) 2018) is costly in computation. By contrast, our motivation is develop general regularization that can consistently boost the performance of
2

---

Under review as a conference paper at ICLR 2021
deep neural networks in both semi- and supervised settings rather than the adversarial scenario. Be- sides, the construction way of a non-local layer in our method is more flexible and can be determined by the specific objective function, as elaborated in Section 2.1 and 2.2 Moreover, our patch-level method can achieve computational advantage over pixel-level regularization, and incorporates more meaningful semantic correlations in different layers. Particularly, flexible patch size can be chosen according to the size of receptive field in different layers, yielding more informative graph-based representation and better regularization performance.
Concretely, as our Patch-level Neighborhood Interpolation (Pani) shown in Figure I in the first step we determine the candidate peer images set S for each image This can be achieved by random matching or computing the semantically nearest image neighbors using e.g. the cosine distance. Next, we construct the whole patches set P3 on the candidate peer images set S; for each image i by clipping the corresponding patches in the different locations on an input or a feature map- Following the establishment of patch set P,, we construct K nearest neighbor patch graphs based on the distance of patch features in order to find the neighbors of each patch in patch set P; for Vi = I,., N. Mathematically, following the definition the PeerNet, let z be the p-th patch on the input or feature map Z' for the i-th image within one batch. Then denote the k-th nearest patch neighbor for z, as z!! taken from the patch qı of the peer image jk in the candidate set S,
Next, in order to leverage the knowledge from neighbors, different from graph attention mechanism in PeerNet, we apply a more straightforward linear interpolation on the neighboring patches for the current patch z. Then, the general formulation of our Patch-level Neighborhood Interpolation can be presented as follows:
+
Tipk 4u =
p
where Tipk is the combination coefficient for the p-th patch of i-th image w.r.t k-th patch neighbor, which can be computed through the power iteration similar to the manner of VAT, or through ran- dom sampling from specific distribution in randomness- boaddd regularization, e.g., Mixup and its variants. Moreover, the choice of linear interpolation in Eq. enjoys great computational advantage the nonlinear GAT form in PeerNet in the computation of networks. Finally, after the patch- level linear interpolation patch features, can obtain the refined graph-based representation Z' for i-th image, Vi = I,...,N: N.
Note that our proposed method can explicitly combine the advantages of manifold regularization and non-local filtering in a flexible way, which we have a more detailed discussion about in Appendix B Besides, to further demonstrate the generality and effectiveness of our Pani method, provide Pani-version of two typical regularization strategies, i.c., Virtual adversarial Training and Mixup as
Ti Zn +
M
22
Z1
Pani VAT
Z4,
(2, A)
Y/3
Patch-level Neighborhood Interpolation (Pani)
Pani MixUp
Figure 1: Pipeline of our Patch-level Neighborhood Interpolation followed by two derived regular- ization, i.e., Pani VAT and Pani MixUp. represents the perturbation constructed by our method and (X, --) X) is the mixing coefficient pair.
3

---

Under review as a conference paper at ICLR 2021
well its variant MixMatch, and verify the superiority of our Pani strategy on the significant boosting of accuracy.
2.1 PANI VAT
Based on our Patch-level Neighborhood Interpolation framework, we can construct novel Pani VAT that utilizes the combination or interpolation of patch neighbors for each sample to manipulate the non-local perturbations, thus providing more informative adversarial smoothness setting. Consider more general composite function form of the classifier f. i.e../ (x)) g(=) and h(x) where z denotes the hidden feature of input x or the input itself when the reduced form happens. Combining VAT formulation, i.e., Eq. 7 in Appendix [A] and Pani formulation, i.c., Eq. [T]
-umi-supereieed
we reformulate our Pani VAT with perturbations on L layers in a deep neural network as follows:
max D(a(=),s((()))
s.t. Σ
11 s
where D measures the divergence between two distributions. " {nppk denotes the generic perturbations from our Pani method and 17 indicates the perturbations 1-th layer of network. F(r) =(2p) represents the smoothed feature map imposed by perturbation 7/ considering all patches in the way shown Eq. []] particular, when L = 1, adversarial perturbations are only imposed on the input feature, which is similar to the traditional virtual adversarial perturbations. Addition- ally, is the hyper- parameter. adjusting the weight of perturbation 17()) in different layers with the overall perturbations restrained in an c-ball.
Next, we still utilize the similar power iteration and finite difference proposed in VAT Miyato et al., 2017 to compute the desired perturbation 11". Then the resulting full loss function defined as:
0 Co + -EEED R (I, 17; :0),
where Co is the original supervised loss and B controls the degree adversarial smoothness. Rvadv (2, y, v²" = (=g(=), (ā] can be attained after solving the optimization problem in Eq, For the implementation details, we describe them in Algorithm
Algorithm 1: Pani VAT within Batch
1: Input: neighbors K₁ and K2, classifier f. batch size B, perturbed layers L
2: Initialization: combination coefficient 1)
3: Compute K1 nearest image neighbors based on the distance of the second last layer output from f and obtain K2 (K₁ < B) peer images set S; for each image i.
4: for I 1 to L do:
5: Compute the patch set P. for all K₁ peer images on layer for each image i.
6: Construct a K2 nearest patch neighbors graph for each patch in each image i.
7: Conduct Patch-level Neighborhood Interpolation via Eq. for each patch.
8: end for
9: Conduct power iteration and finite difference in VAT to compute 17" constrained by Eq.
10: Return Rvadv (I. :)
Remark. As shown in the adversarial part of Figure I the rationality of our Pani VAT method lies in the fact that the constructed perturbations can entail more non-local information coming from the neighbors of current sample. Through the delicate patch-level interpolation among neighbors of each patch, the resulting non-local virtual adversarial perturbations are expected to provide more informative smoothness, thus enhancing the performance of classifier in the semi-supervised setting.
2.2
PANI MIXUP
Next, we leverage Patch-level Neighborhood Interpolation to derive Pani MixUp. The core formu- lation of Pani MixUp can be written
4

---

Input: neighbors K, classifier f. batch size B. perturbed layers L, parameter a Under review as a conference paper at ICLR 2021
R
2
(1
Tspk Zzp +
Tapk Zi
k=1
1=1
Tipk
Tiple
D1
Vie
(4)
P
k=1 p=1
Tip
s... X
P
k=1
where (z', y²) are the feature-target pairs randomly drawn from the training data. P the number of patches in each image and À ~ Beta(a, b) represents the importance of the current input or target while conducting MixUp. To compute Tipk. we firstly sample À from Beta(a, b) and Tipk from uniform distribution respectively, then we normalize Vipk according to the ratio of À to satisfy the constraint in Eq. f and thus obtain Tppk- It should be noted that due to the unsymmetric property of À in our framework, b = and only consider the a as the typer-parameter to pay more attention to the importance of current patch, which inspired by the similar approach in MixMatch (Berthelot al. (019b). Here we reformulate Eq. - to illustrate that Pani MixUp is naturally derived from our Pani framework through udditionally considering several constraints:
should tune both and b in our experiments. For simplicity, we fix
K
(2 -z/)
p
Nipk
(5)
Tipk
s.t. X
Vi I,....
~ Beta(a,,) b), Tipk E [0, 1], pi,p,
where the first constraint in Eq. 5 can be achieved through normalization via A. Mcanwhile, we impose Tipk [0, as Tippk represents the interpolation coefficient. Further, we elaborate the pro- cedure of Pani MixUp in Algorithm 2
Algorithm 2: Pani MixUp within a Batch
2: Compute peer images by random matching and obtain peer images set S, for each image i.
3: for -= to T. do:
4: Compute the patch set P; on layer for each image i.
5: Construct a K nearest patch neighbors graph for each patch in each image i.
6: Sample initial coefficient 1/ = (Tlpp } from U00 1) and À from Beta(a, 1).
7: Normalize 'To according to the ratio À via Eq. 5 to compute ())),
8: Conduct Pani MixUp over patch features and labels via Eq. for each patch.
9: end for
10: Return supervised loss based on mixed features and labels.
Remark. Different from the role of in the aforementioned Pani VAT where serves as the inter- polated perturbations, the physical meaning 7 in our Pani MixUp approach is the linear interpola- tion coefficient to conduct MixUp. Despite this distinction, both of the two extended regularization methods are naturally derived from our Patch-level Neighborhood Interpolation framework, further demonstrating the generality and superiority of our Pani strategy.
EXPERIMENTS
In this section, we conduct extensive experiments for Pani VAT and Pani MixUp and its variant Pani Mix Match both semi- and supervised settings.
5

---

Under review as a conference paper at ICLR 2021
3.1 PANI VAT
Implementation Details. For fair comparison with VAT and its variants, e.g., VAT + SNTG (Luo al. 2017) and TNAR (Yu al. 2019), choose the standard large convolutional network as 2018). For the option of dataset, we focus on the standard semi- supervised setting on CIFAR-IO with 4,000 labeled data. Unless otherwise noted, all the experi- mental settings in our method are the identical with those in the Vanilla VAT (Miyato et al. 2018). In partieular, we conduct our Pani VAT on input layer and one additional hidden layer, yielding two variants Pani VAT (input) and Pani VAT (+hidden). More details can refer to Appendix
the classifier as in (Miyato et al.
Method
CIFAR-10X4,000 labels)
VAT (Miyato et
VAT +SNIG LLub
2017
12.49 + 0.36
II model (Laine & Alla 2010
16,55 + 0.29
Teacher [larvannnn Valpola,
17.74
CCLP (Kamnitaas
CCLP.Kannntaas
2018
18.57 + 0.41
AI.I (Dumoulm ef mll 201h
17.99 1.62
Improved (Salmans
2016
18.63
Tripple GAN [Li 2017
16.99 - 0.36
Bad GAN (Dai et ml.
2017
14.41 + 0.30
LGAN (Qi at
Improved GAN JacobRegu tansent Kumar al. 2017
16,20 - 1.60
Improved GAN ManiReg (Lecouat et a. 2018
14.45 + 0.21
TNAR (with generative modcis] al 2019
12.06 0.35
Pani VAT (ipput)
12.33 0.091
Pani VAT (+hidden)
11.98 0.106
Table 1: Classification errors (%) of compared methods on CIFAR- 10 dataset without data augmen- tation. The results of our Pani methods are the average ones under 4 runs.
Our Results. Table I presents the state-of-the-an performance achieved by Pani VAT (+hidden) compared with other baselines CIFAR-10. We focus the baseline methods especially along the direction of variants of VAT and refer to the results from TNAR (with generative models) method (Yu et al., 2019), the previous state-of-the-art variant of VAT that additionally leverages the data man- ifold by generative models to decompose the directions of virtual adversarial smoothness. It is worthy of remarking that the performance of relevant GAN-based approaches, such Localized GAN (LGAN) (Qi et al. 2018) as well as TNAR (with generative models) in Table heavily rely on the established data manifold by the generative models. It is well-known that one might come across practical difficulties while implementing and deploying these generative models. By contrast, without the requirement of generative models, our approach can eliminate this disturbance and can still outperform these baselines. In addition, our Pani VAT (thidden) achieves slight improvement compared with Pani VAT (input), which serves an ablation study, and thus verifies the superiority of manifold regularization mentioned in our Pani framework part. Overall, the desirable flexibility along with desirable stability (lower standard deviation shown Table T of our Pani VAT further demonstrates the effecttiveness of our Pani strategy.
Analysis of Computational Cost. Another noticeable ad- vantage of our approach the negligible increase of computa- tion cost compared with Vanilla crucial
Trining Eyydee
Taating Fred
100
75-
10-
40
VAT. In particular, operation in our approach is the construction of patch set P and it can be accomplished efficiently by as.strided func- tion in Python or through the specific convolution operation in Pytorch Additionally, the index of nearest neighbor graph be efficiently attained through topk operation. We conduct further
Tranng Tpeket
Traning Eprcalo
Putich
200-
150-
100-
75
50
TensorFlow.
VAT
VAT
Phri
Pani
Figure 2: Average training time each epoch with respect to pa- rameters K1, K2, number of layers L and patch size.

---

Under review as a conference paper at ICLR 2021
sensitivity analysis the computational cost of our method with respect to other parameters, i.e., K1 (number of peer images), K2 (number of patch neighbors). L (number of perturbed layers) and patch size 8.
As shown in Figure 2 the variation of all parameters has negligible impact on the training time cach epoch compared with Vanilla VAT except the number of perturbed layers. The increasing of compu- tational cost presents an almost linear tendency with the increasing of the number of perturbed layer as the amount of floating-point calculation is proportional to the number of perturbation elements, i.e., V). if we temporarily neglect the difference of time in the back propagation process for different layers. Combining results from Table I and Figure 2 we argue that the better performance can be expected if we construct perturbations on more hidden layers despite the increase of computation.
3.2 PANI MIXUP
Implementation Details The experimental settings in this section are strictly followed by those in Vanilla MixUp (Zhang al. (017) and Vanilla MixMatch (Berthelot al.] 2019b) to pursue fair comparison on CIFAR-10, CIFAR-LOR 100 and TinyImageNet datasets. In particular, we compare ERM (Empirical Risk Minimization), MixUp training and approach for different neural archi- tectures. For fair comparison with input MixUp, we conduct our approach only on input layer and the better performance can be expected naturally if we consider more layers. Besides, we introduce mask mechanism on to avoid overfitting. More details can refer to Appendix C
Dalasel
Model
Aug
ERM
Misupia 1)
Ourscipuu)
PreAct R8sNet-18
12.81
5.43
0,16
9.88 0.25
4.3 1 0.15
303 : 0,12
0.09
CIFAR-10
Pr
5.15 0.12
0.20
0.15
10:00
WideResNNtt28-11 10
8.78 0.20
4.59 0.06
8:08 0.39
3.21 0.13
5.79
3,02
0.11
0.03
PreAct ResNet
21.96 1 0.51
39.64 0.58
41 31.961 0.27
22.15
1 0.72
20.90
32,113
0.34
0.21
CIPAR-100
PreActResNet:34
24.85
30.41
41
21.49 0.68
0.29
2i
21.
31.91
27.71
PreAct ResNes-18
44.90 1 0.28
42.84 1 0.35
42.20
0.39
$4.95 1. 0.63
60.58 0.83
$2.25
0.75
TaegeNee
PrcActRe/Nes334
40.66 # 1.64
$1. 03 + 0.57
43 23.18-
55.91
0.84
1.09
40.03
49,56
0.61
0.94
WidekesNee-25-100
42.30
40.64 0.77
38.97
0.81
48.47
51.19
Table 2: Test error in comparison with ERM, MixUp and Pani MixUp (input) across three deep neu- ral network architectures with and without data augmentation. All results are the average ones under 5 runs. Results of MixUp on the settings without data augmentation are based on our implementation on the original code from MixUp.
Our Results. Table 2 presents the consistent superiority of Pani MixUp over ERM (normal training) as well as Vanilla MixUp over different deep neural network architectures. It is worthy of noting that the superiority of our approach in the setting without data augmentation can be more easily observed than that with data augmentation. Another interesting phenomenon is that MixUp suffers from one kind of collapse on the performance as the accuracy of MixUp is even inferior to the ERM on CIFAR- 100 and Tiny ImageNet on the setting without data augmentation. By contrast, our approach exhibits consistent advantage ERM and MixUp across various settings and network architectures.
Analysis of Computational Cost. To provide a comprehensive understanding about the computa- tion cost of our method, we plot the tendency between training time under 200 epoch and the test accuracy as shown in Figure 3 in which we can better observe the computational efficiency as well as the better performance of our approach. To be more specific, we choose ResNet- 18 as the basic test model and conduct the experiment about the variation of test accuracy while training to compare the efficacy of different approaches. From Figure we can easily observe the consistent advantage of performance of our approach and comparable training time under the same number of epochs. One interesting point about the "collapse" phenomenon shown in the fourth subplot of Figure ree- veals the process of this issue. After the learning rate decay around 50-th epoch, the performance of MixUp surprisingly drops steadily to the final result that is even inferior to original ERM. By contrast, our Pani MixUp method achieves consistent improvement on the generalization without the disturbance by any "collapse" issue.
7

---

Under review as a conference paper at ICLR 2021
CIFARIO with Aug
CIPARIO without Aug
CIF 1000 with Aug
CIFAR without Aug
Test Accuracy(%)
50
BRM
ERM
ERM MisUpp
ERM
Mislip
Mix(/p
MixU3
Oues
Otes
Oces
Owts
20
93
100
20
60
50
100
20
18
100
66
40
100
Time(m)
Time(m)
Time(m)
Time(()
Figure 3: Test accuracy with respect to the training time over ERM, MixUp and our approach. m indicates minutes and the leap in the training comes from the learning rate decay. "with Aug" and "without Aug" denote the settings with and without data augmentation, respectively.
Further Extension to MixMatch. To further demonstrate the superi- ority of our Neighborhood Interpo- lation MixUp. proach into MixMatch (Berthelot
Methods
(0/AR-00(4,00) labels)
PiModel (Laine & Aila 2016
17.41 1 0.37
PscudoLabel (Lee 2013
16.21 1 0.11
embed
ap-
Mixup (Zhang 2017
2017
13.15 0.20
VAT [Myylo el
11:05 1 0.31
Mean Teacher ( (arvannnn & Valpola 2017
10.36 +: 0.25
al.] 2019b). the current state-of- the-art approach that naturally ex- tends MixUp supi-supe set- ting. The resulting approach, Pani MixMatch, elegantly replaces the MixUp part in the MixMatch with our Pani MixUp, thus imposing Pani Mixup by additionally incorporat- ing patch neighborhood correlation knowledge. Results shown in Table demonstrate that Pani MixMatch can further improve the performance of MixMatch in the standard semi-supervised setting, thus verify- ing the effectiveness and flexibility of our Patch-level Neighborhood Interpolation.
MixMatch (Beithelot et al. 20196
6.24 + 0.06
MixMalch(ouns)
6,26 0.078
Pani MixMarch
6.08 = 0.074
Table 3: Performance of Pani MixMatch in semi- supervised setting on CIFAR with 4000 labels. The reported result of MixMatch(ours)) and Pani MixMatch is under the same random seed, coming from the median of last 20 epoch while training. The results of Mix MixMatch(ours) and Pani MixMatch are the average ones under 4 runs.
DISCUSSION AND CONCLUSION
The recent tendency of the design of regularization attaches more importance to the consistency and flexibility on various kinds of settings. Along this way, we focus the proposal of general regularization motivated by additional leverage of neighboring information existing in the sub-group of samples, e.g., within one batch, which can elegantly extend previous prestigious regularization approaches and generalize well in wider range of scenarios.
In this paper, we firstly analyze the benefit of leveraging the knowledge from the non-i.i.d rela- tionship while developing more efficient regularization for deep neural networks, thus proposing a general and flexible non-local regularizer called Patch-level Neighborhood Interpolation by inter- polating the neighboring patch features in the computation process of network. Furthermore, we customize our Patch-level Neighborhood Interpolation into VAT and MixUp as well as its variant, respectively. Extensive experiments have verified the effectiveness of the two derived approaches, therefore demonstrating the benefit of our Patch-level Neighborhood Interpolation. Our work paves way toward better understanding and leveraging the knowledge of relationship between samples to design better regularization and improve generalization over a wide range of settings. Since the proposed Pani framework is general and flexible, more regularizations and applications could be considered the future, such as more traditional regularization methods and the application in natural language processing tasks. Also, the theoretical properties of Pani should also be analyzed.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang. and Colin Raffel. Remixmatch: Semi-supervised learning with distribution alignment and au augmenta- tion anchoring. arXiv preprint arXiv:1911.0973 2019a.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raf- fel. Mixmatch: A holistic approach semi-supervised learning. Conference on Neural Informa- tion Processing Systems, 2019b.
Antoni Buades, Bartomeu Coll, and J-M Morel. A non-local algorithm for image denoising. In 2005 IEEE Computer Sociery Conference on Computer Vision and Pattern Recognition (LVPR'05), volume 2. pp. 60-65. IEEE, 2005.
Zihang Dai, Zhilin Yang, Fan Yang, William W Cohen, and Ruslan R Salakhutdinov. Good semi- supervised learning that requires bad gan. In Advances in Neural Information Processing Sys- tems, pp. 6510-6510 (0-6520,220 2017.
Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Olivier Mastropietro, Alex Lamb, Martin Ar- jovsky, and Aaron Courville. Adversarially learned inference. arXiv preprint 160.v01600.00704, 2016.
Murat Dundar, Balaji Krishnapuram, Jinbo Bi, and R Bharat Rao. Learning classifiers when the training data not iid. In IJCAI, pp. 756-761, 2007.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference Learning Representations, 2014.
Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R Salakhutdi- nov. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv: 2012.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Learning, 2015.
Konstantinos Kamnitsas, Daniel Castro, Loie Le Folgoc, Ian Walker, Ryutaro Tanno, Daniel Rueckert, Ben Glocker, Antonio Criminisi, and Aditya Nori. Semi-supervised learning via com- pact latent space clustering. arXiv preprint arXiv:1806.0288 180.00269, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference Learning Representations, 2016. 2016.
Abhishek Kumar, Prasanna Sattigeri, and Tom Fletcher. Semi-supervised learning with gans: Mani- fold invariance with improved inference. In Advances in Neural Information Processing Systems, pp. 5540 55500,5550055 2017.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint drXiv:1610.02242,2000 2016.
Bruno Lecouat, Chuan- Sheun- Foo, Houssam Zenati, and Vijay R Chandrasekhar, Semi -upi-supeee learning with gans: Revisiting manifold regularization. arXiv preprint arXiv:1805.0m 08955. 2018.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on Challenges in Representation Learning. ICML, volume 3, pp- 2, 2013.
Chongxuan Li, Kun Xu, Jun Zhu, and Bo Zhang. Triple generative adversarial nets. arXiv preprint arXiv:1703.02211, 2017.
Yucen Luo, Jun Zhu, Mengxi Li, Yong Ren, and Bo Zhang. Smooth neighbors on teacher graphs for semi-supervised learning. arXiv preprint arXiv: 17X.00/711.00055: 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2017.

---

Under review as a conference paper at ICLR 2021
Takeru Miyato, Andrew M Dai, and Ian Goodfellow. Adversarial training methods for semi- supervised text classification. International Conference on Learning Representations, 2016.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial train- ing: a regularization method for supervised and semi-supervised learning. arXiv preprint arXiv:1704.03976, 2017.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: a regularization method for supervised and supervised learning. IEEE transactions on pattern analysis and machine intelligence, 1199)11979-1993, 2018.
Xian-Sheng Guo-Jun Qi. Liheng Zhang, Hao Hu, Marzich Edraki, Jingdong Wang, and Xian Sheng Hua. Global versus localized generative adversarial nets. In Proceedings of IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2018.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, pp. 2234-2242, 2016.
Nir Sochen, Ron Kimmel, and Ravi Malladi. A general framework for low level vision. IEEE fransactions on image processing, (03):310-318, 1998.
Ke Sun, Zhouchen Lin, Hantao Guo, and Zhanxing Zhu. Virtual adversarial training on graph convolutional networks node classification. Chinese Conference on Pattern Recognition and Computer Vision (PRCV), pp. 431-443. Springer, 2019.
Jan Svoboda, Jonathan Masci, Federico Monti, Michael M Bronstein, and Leonidas Guibas. Peer- nets: Exploiting peer wisdom against adversarial attacks. International Conference on Learning Representations, 2018.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consis- tency targets improve cemi-supervisedd deep learning results. In Advances in neural information processing systems, pp. 1195-1204, 2017.
Carlo Tomasi and Roberto Manduchi. Bilateral filtering for gray and color images. In Sixth interna- fional conference computer vision (IEEE Cat. No. 98CH36271), pp. 839 846. IEEE, 1998.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. International Conference on Learning Representations, 2018.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2017.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7794-7803, 2018.
Bing Yu, Jingfeng Wu, Jinwen Ma, and Zhanxing Zhu. Tangent-normal adversarial regularization for semi-supervised learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10676-10684, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Repre- sentations, 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, 2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. Conference Neural Information Processing Systems, 2017.
10


Reviews:
[{"review_id": "plCcrnD9rW3", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The proposed Pani seems to be novel. It can explore the information of the neighboring relationship between samples and can be regarded as the meta-regularization. For the general formulation of Pani, how does the number of the nearest neighbor patch graphs affect the results?\n\nAs I am not familiar with this topic of the paper, there are lots of regularization methods, it would be better to add more details about the regularization methods that do not neighboring relationship among samples.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oqiWtdVN3Qi", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a regularizer called Patch-level Neighborhood Interpolation (Pani). The idea is to construct a graph over patches, and interpolate new patches during training. The paper applies Pani to othter two regularization methods VAT and MixUp. The paper shows better results through experiments.\n\nThe writing of the paper can be improved. The current version hurts the merits of the paper, making it not self-explanatory. Here are some questions or weaknesses below, which may be all due to the writing issues.\n\nSection 1: Can the authors define \"non-local\" and \"non-local regularization\"? What is the counterpart \"local regularization\"? From remaining part of the paper, it seems that the neighbhoring patches are from different images, not from the same image. \n\nThe paper also motivates from the limitation of iid assumption. But when sampling patches across images, does it also assume iid on the images as it discards other parts of the images?\n\nFigure 1 is very confusing. In the left panel, where are the interpolated patches/images? In the right panel, how to compute $\\eta$? How to use lambda to combine three examples ($z_i$, $y_i$) for $i$=1,2,3? Is there a visualization of $r$? Is there a correspondence between images/patches in the left and symbols (e.g., $z$ and $y$) in the right?\n\nTable 1: what are the setups for Pani within VAT? Figure 2 shows multiple design choices, but the paper does not say any values of them in Table 1. The paper is not self-explanatory although it largely claims that it follows some prior work.\n\nTable 1: While it says \"without data augmentation\", aren't Pani and VAT data augmentation techniques? What happens if all the methods adopt typical data augmentation methods during training (e.g., random flip, random crop, etc.)? Would the proposed method still have advantage?\n\nFigure 2: What is the unit in the y-axis? As there are multiple variables to control (e.g., L, K1, K2, s), what are the fixed values of them in each of the barcharts?\n\nFigure 2: As the paper advocates the graph-based regularization, it must construct the graph. I assume the graph is constructed before-hand, otherwise doing so on-the-fly would increase the compute cost. If this is true, how the proposed method scales to larger datasets (e.g., more images and higher-resolution images)?\n\nSection 3.1: While the authors \"argue that the better performance can be expected if we construct perturbations on more hidden layers despite the increase of computation\", there is no justification on the argument. The paper should conduct such an experiment to justify this by applying Pani on more layers given that the cost is low as studied in Figure 2.\n\nSection 3.2: What is \"mask mechanism\"? The paper does not explain it.\n\nSection 3.2: What does it mean by \"one kind of collapse\"? Although Figure 3 illustrate the issue in the fourth plot, can the authors expand the discussion? What is the learning rates? Does learning rate scheduler cause the issue? What other explanations? Does using another learning rate resolve the issue?\n\nTable 3: What is the rationale behind reporting results \"coming from the median of last 20 epoch while training\"? What are the total training epochs of each methods?\n\nThe appendix is not attached to the paper.\n\n\n----------\npost-rebuttal\n----------\nI appreciate that authors have provided rebuttal that addresses some of my questions. I've read the updated paper and other reviewers' comments. In general, I'd like to maintain my initial rating as a borderline paper. Here are two main reasons.\n\nFirst, I realize that authors are not familiar with the policy, because they did not attach the appendix to the manuscript but uploaded as a separate file. As a result, their updated paper did not address issues in the review effectively. Authors simply say something like below \n\n- \"We promise to improve our writing based on your suggestions in the revised version.\"\n- \"Due to the space limit, we put our related experimental details into Appendix C.\" (9 pages are allowed by policy)\n- \"We will supplementary the results of Pani Mixup(+hidden) to justify it if accepted.\"\n\nSecond, in terms of other data augmentation, the authors merely say \"As data augmentation is a common trick, consistent improvement can be easily expected across all methods\". I don't know if this is true unless there is a justification.", "extra_scores": {}, "extra_text": {}}, {"review_id": "F7xB3dJvVlZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a general regularizer called the Patch-level Neighborhood Interpolation (Pani) that constructs patch-level graphs at different levels of neural networks. Specifically, it is based on the k-nearest patch neighbors at each layer and linear interpolation for each patch. By applying this proposed regularizer framework into two special cases and get Pani VAT and Pani MixUp. Numerical experiments are comprehensive and convincing. \n\nPros:\nA new type of regularization for neural networks is proposed. \nTwo special Pani based algorithms within a batch are proposed with applications in image classification. \nExperimental performance in terms of accuracy and running time shows that the Pani regularizer can improve the algorithm. \n\nCons:\nThe motivation of combining patch based k-NN and linear interpolation is not fully clear. Can we replace each by one of other related methods? \nNo theoretical guarantees for this improvement are provided, which could be strengthened in the revision. \nHow can the Pani be integrated to other types of machine learning regularizations? Some practical guidance could be provided.\n\nOverall, the work is important and interesting which could provide insights to other related works in the area. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CIm00k8w2nj", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new regularization method via patch level interpolation.  During the training,  images within a batch will be used to construct an image graph. For example, for a certain image, its nearest neighbors in the feature spaces will be used.  Then patches from its neighbors will be used to interpolate to each patch in that given image.  Thus a straightforward application for such regularization is semi-supervised training.  Moreover, in this paper it has demonstrated such regularization can be extended with virtual adversarial training and mixup training. \n\nAlthough the proposed training strategy is simple, and the proposed patch interpolation is able to achieve better performance when compared with some baselines. It is still not comparable to existing semi-supervised training works such as Mixmatch or FixMatch. In the last section of the paper, the author shows the extension with mixmatch  by surpass the mixmatch with little improvement. However, when compared to Fixmatch, the performance gap becomes larger. (Note, fixmatch seems simpler than proposed method in terms of computational cost)\n\nThus the proposed method does not convinced me for its effectiveness.\n\nmissing reference.\n[1]FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel way (Pani) that constructs image patch-level graphs and then linearly interpolates the patch-level features. The authors show how this can be used in Virtual Adversarial Training (PaniVAT) and Mixup/MixMatch (Pani Mixup). The method is shown to improve classification compared to standard VAT and related techniques on CIFAR-10 (low data setting), as well as outperform Mixup on CIFAR-10/CIFAR-100/TinyImageNet (standard setting, multiple different architectures) with and without data augmentation.

Reviewer 4 liked that the method was simple, but was not convinced of its effectiveness because of the baselines that were chosen. Specifically they thought that FixMatch was a stronger baseline than MixMatch. The authors said that Pani is complementary to FixMatch and similar improvement could be expected when applying Pani to FixMatch instead of MixMatch.

Reviewer 2 appreciated that the work was “important and interesting” and noted that the experiments showed that Pani improved existing algorithms. They were concerned with lack of motivation and lack of theoretical guarantees. The authors clarified motivation in their response to the reviewer but, understandably, were unable to provide any theoretical analysis.

Reviewer 1 expressed disappointment with the writing and understandability of the paper. I read the paper myself and I agree. They posed several clarifying questions to the authors, to which the authors responded. I note that the reviewer could not find the appendix, but it was attached separately as supplementary material.

Reviewer 3 wrote a very short review and stated that they are not familiar with the topic of the paper. With three other full reviews, I have discounted R3’s review because of their extremely low confidence. They also asked a couple of clarifying questions, to which the authors responded. I found the authors’ response satisfying.

Overall, two reviewers are not extremely excited about the paper and one reviewer thinks the work is interesting but has concerns about clarity. I think that overall it is a neat idea, but the paper could use more polishing and clarification. Compared to other borderline papers in my stack, it is not over the bar. It could get there with further work. I hope the authors continue to improve the paper and re-submit it in the near future.
Decision: Reject