Spectral Nonlocal Block for Neural Network
Authors: Lei Zhu
Qi She
Lidan Zhang
Ping guo
Venue:  (2020)
Keywords: Nonlocal Neural Network
Image Classification
Action Recgonition

Abstract: The nonlocal network is designed for capturing long-range spatial-temporal dependencies in several computer vision tasks. Although having shown excellent performances, it needs an elaborate preparation for both the number and position of the building blocks. In this paper, we propose a new formulation of the nonlocal block and interpret it from the general graph signal processing perspective, where we view it as a fully-connected graph filter approximated by Chebyshev polynomials. The proposed nonlocal block is more efficient and robust, which is a generalized form of existing nonlocal blocks (e.g. nonlocal block, nonlocal stage). Moreover, we give the stable hypothesis and show that the steady-state of the deeper nonlocal structure should meet with it. Based on the stable hypothesis,  a full-order approximation of the nonlocal block is derived for consecutive connections. Experimental results illustrate the clear-cut improvement and practical applicability of the generalized nonlocal block on both image and video classification tasks.

Under review as a conference paper at ICLR 2020
A SPECTRAL NONLOCAL BLOCK FOR NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The nonlocal network is designed for capturing long-range spatial-temporal de- pendencies in several computer vision tasks. Although having shown excellent performances, it needs elaborate preparation for both the number and position of the building blocks. In this paper, we propose a new formulation of the non- local block and interpret from the general graph signal processing perspective. where we view it as fully-com cully-connected graph filter approximated by Chebyshev polynomials. The proposed nonlocal block more efficient and robust, which is a generalized form of existing nonlocal blocks (e.g. nonlocal block, nonlocal stage). Moreover, we give the stable hypothesis and show that the steady-state of the deeper nonlocal structure should meet with it. Based on the stable hypothesis, a full-order approximation of the nonlocal block derived for consecutive con- nections. Experimental results illustrate the clear-cut improvement and practical applicability of the generalized nonlocal block on both image and video classifi- cation tasks.
INTRODUCTION
Capturing the long-range spatial-temporal dependencies crucial for the Deep Convolutional Neu- ral Networks (CNNs) extract discriminate features in vision tasks such image and video clas- sification. However, the traditional convolution operator only focuses on processing local neighbor- hood at a time. This makes the CNNs need to go deeper with convolutional operations enlarge the receptive fields, which lead to higher computation and memory. Moreover, going deeper cannot always increase the effective receptive fields due to the Gaussian distribution of the kernel weight (Luo et al. (2016)). To eliminate this limitation, some recent works focus on designing the network architecture with wider and well-designed modules to catch the long-range dependencies such as (Peng et al. (2017), Chen et al. (2017). Zhao et al. (2017)) Although having larger receptive fields, these modules still need to applied recursively to catch the dependencies the pairs in large distances.
Inspired by the classical non-local means method image denoising, Wang et al. (2018) proposes the nonlocal neural network which uses the nonlocal (NL) block to concern the "full-range" de- pendencies in only one module by exploring the correlations between each position and all other positions. In the NL block, the affinity matrix is first computed represent the correlations between each position pair. Then the weight means of features are calculated based on the affinity matrix to refine the feature representation. Finally, the residual connection is added to the refined feature map. Due to its simplicity and effectiveness, the nonlocal block has been widely used in image and video classification Wang et al. (2018): Yue et al. (2018): Tao et al. (2018): : Chen al. (2018), image segmentation (Hung et al. (2018) Yue et al. (2018) : Wang et al.
2018 and person re ieeetiffiiiition
(Liao al. (2018): Zhang et al. (2019)) recently.
However, due to the complexity of the affinity matrix, the nonlocal block I needs much more com- putational effort and sensitive to its number and position the neural network (Tao et al. (2018)- Some works solve the first problem by simplifying the calculation of the affinity matrix such as Huang et al. (2018), He et al. (2019), Yue et al. (2018), Chen et al. (2018). Only a few works try to solve the second problem which limits the robustness of the nonlocal network
Tao et al. (011
'The nonlocal block is composed of a nonlocal operator and residual connection
"hhe nonlocal network is composed of several nonlocal blocks

---

Under review as a conference paper at ICLR 2020
proposes the nonlocal stage (NS) block which concerns the diffusion nature and maintains the same affinity matrix for all the nonlocal units in the NS block. Comparing with the NL block, the NS block is insensitive the numbers and allows deeper nonlocal structure. However, the deeper nonlocal structure of NS block increases the complexity and do not have a remarkable improvement.
In this work, focus elaborating robust nonlocal block which is more flexible when using in the neural network. We prove that the nonlocal operator in the nonlocal block is equivalent to the Chebyshee-appproxmmtte fully-connected graph filter with irrational constraints that limits its liberty for learning. To remove these irrational constraints, we propose the Spectral-bage -ased Nonlocal (SNL) block which is more robust and can degrade into the NL and NS with specific assumptions. We also prove that the deeper nonlocal structure satisfies the stable hypothesis with the help of steady- state analysis. Based on this hypothesis, we give the full-order approximated spectral nonlocal (gSNL) block which is well- well-performed for deeper nonlocal structure. Finally, we add our proposed nonlocal blocks into the deep network and evaluate them on the image and video classification tasks. Experiments show that the networks with our proposed blocks are more robust and have higher accuracy than using other types of nonlocal blocks. To summarize, our contributions are threefold:
We propose spectral nonlocal (SNL) block an efficient, simple, and generic component for capturing long-range spatial-temporal dependencies with deep neural networks, which is generalization of the classical nonlocal blocks.
We propose the stable hypothesis, which can enable the deeper nonlocal structure without elaborate preparation for both the number and position of the building blocks. We further extend SNL into generalized SNL (gSNL), which can enable multiple nonlocal blocks to be plugged into the existing computer vision architectures with stable learning dynamies.
Both SNL and gSNL have outperformed other nonlocal blocks across both image and video classification tasks with a clear-cut improvement.
PRELIMINARY
Nonlocal block The NL block consist of NL operator with residual connection and is expressed
(1) where X E NxC, is the input feature map, F(A, Z) is the NL operator, E NxC, is the transferred feature map that compresses the channels of X N by linear transformation with kernel Wg E CC.x,, Here is the number of positions. The affinity matrix A e NxN is composed by pairwise correlations between pixels.
Y = F(A, Z) with Z XW
In the NL block, the NL operator explores the "full-range" dependencies by concerning the relation- ships between all the position pairs:
F(A, Z) AZW with A (aia)NNN Aij -(X.,..
where W E CRCxC is the weight matrix of a linear transformation. f()) the affinity kernel which can adopt the "Dot Product", "Traditional Gasuassian". "Embedded Gasussian" or other kernel ma- trix with a finite Frobenius norm.
Nonlocal stage To make the NI. operator follow the diffusion nature that allows deeper nonlocal
structure Tao et al. (2018), the nonlocal stage (NS) operator uses the graph laplacian L = =DA -A-A A to replace the affinity matrix A in the NL operator:
F(A,
(A DA)ZW with D diag(d:),
where F(A, Z) is the NS operator. d; = Σ, ai is the degree of node i. Moreover, when adding multiple blocks with the same affinity matrix A and replacing the NL operator by the NS operator, these consecutively-coneet
blocks become the NS block. We called these nonlocal blocks in the NS block as the NS units.
3 METHOD
The nonlocal operator can be divided into two steps: calculating the affinity matrix A to repre- sent the correlations between each position pairs and refining the feature map by calculating the
2

---

Under review as a conference paper at ICLR 2020
weighted means based on A. In this section, fully-connected graph filter is utilized for explaining the nonlocal operator. With the Chebyshev approximation, we propose the SNL operator which is proved to be generalized form of NL and NS operator and is more robust with higher performance in computer vision tasks. Furthermore, based on the stable hypothesis that deeper nonfocal struc- ture tends to learn stable affinity matrix, extend SNI. into full-order Chebyshev approximation version, i.c. the gSNL.
3.1 THE PROPOSED SPECTRAL NONLOOCA OPERATOR
Nonlocal operator in the graph view The nonlocal operator F(A. Z) is a filter that computes weighted mean of all the positions in the feature map Z based on the affinity matrix A and then conduct the feature transformation with the kernel W. This is the same as filtering the signal Z by graph filter & in the graph domain defined by the affinity matrix A (Shuman et al. (2013)). Based on this perspective (Shuman et al. (2013), we further define the nonlocal operator as:
Theorem 1. Given an affinity matrix A E RNNN and the signal Z NxC, the nonlocal operator is the same as filtering the signal Z in the graph domain of a fully-connected weighted graph G:
F(A, Z g Ugo Ugo (A)UTZ URU
(4)
with L D, D,. - - AU,
where the graph filter 5 ENNN is a diagonal parameter matrix, i.e. 52 diag(w), w (Wi, W2,,.., Wn). G (V, A) is fully-connected graph with the vertex set V and affinity matrix A. A = diag( ( (11, '2 ..., Ai.... Xx)) and U {u,, U2,... Ui u..... uN are the eigenvectors and eigenvalues of the graph laplacian L.
This definition requires that the graph laplacian has non-singular eigenvalue and eigenvector, so the affinity matrix A should be symmetrie, non-negative, row-normalized matrix. To meet this requirement, the affinity matrix A can be obtained by the following steps. First, the affinity kernel is used to calculate the matrix A (we use the dot product with embeded weight matrix W & RC xC, and W. p E [ xC, as the affinity kernel, i.e. A (XW )) p)). Then make the matrix A symmetric: A A We normalize the row Á to make satisfy d: = 1 and having D A. For the simplicity, in the following sections the symmetric, non-negative, row-normalized matrix Á is denoted as A.
The proposed spectral nonlocal operator The graph filter S in Eq. (4) contains N parameters. To simplify it, we use the Chebyshev polynomials which can reduce the N parameters into k (k < N). For simplicity, we firstly assume that the input Z, the output F(A, Z) and the output F(A, Z) have only one channel.
Following the similar method as Defferrard et al. (2016), the ogder Chebyshev polynomials is used to approximate the graph filter function ga (A):
K-1
with L' = 2L/ Amax In. F(A, = Σ (L))Z
(5)
K=
s.t. To(L)= = Ind Ti(L'= L', TL = 2L 2L'Tp- TT- 2h-)(L
Due to L is random walk laplacican, the maximum eiginvalue Xmaz satisfies Amaz 2 which
makes L' = A (Shuman et al. (2013)). Then Eq. (5) becomes:
K-1
K
F(A Z)
O,Tr(A) = 0, + 0, Σ
(A).
(6)
If A 1, the first-order Chebyshev approximation of Eq. 6 becomes:
F(A, 0, AZ,
where 8g and 01 are the coefficients for the first and second term which are approximated by learning with SGD. Then, extending Eq. (7) into multi-channel conditions, we can get the formation of our SNL operator:
F. ZW1 1 AZW2,
(8)
3

---

Under review as a conference paper at ICLR 2020
where F. Z) is the SNL operator, W1 RCxc, W2 RCxx0. Finally, residual connec- tion is added with the SNL operator to form the SNL block:
Y x F = X ZW1 + AZW2.
Self- AoffAtttention
W;
NL
W22
Self-Preser-inn vnn
W1
W1
NS
SNL
Figure 1: The comparison between the nonlocal operator (NL), nonlocal stage operator (NS) and ours spectral nonlocal operator (SNL). Our SNL has more widely attention range as shown in the red boxes benefited from the composition of the self-attention term and the self-preserving term which is taken effect by the W, and W2. Our SNL degrades into the NL when W, = 0 and NS operator when W1 W W.
Relation with other nonlocal operators As shown in fig. D our SNL operator can degrade into the NL operator by setting W₂ 0, i.e 6g = However, its analytic solution: 6, = Σ Wj controls the total filtering intensity, which cannot be guaranteed be O. This setting will limit the search space when training the network and reduce the robustness of the NL block. The NL operator cannot magnify features of large range and damp some discriminative features such as the beak of the waterfowl. Our SNL operator
W2, i.e. + 6u = Ey=n W5 1 0. When setting it to zero, the filter strength of the fighffrequency signal (with high A) such as the small part or twig is suppressed. Thus, it still cannot magnify the discriminative part such as the beak of the waterfowl as shown in fig. [ Comparing with NI. and NS, our SNL does not have these irrational constraints and give these two parameters liberal learning space. Thus, dp can control the preserve strength of the discriminative features, while 0 can pay more attention to low-frequency signal to diminish the noise.
also degrade into the NS operator by setting W1
8, + fy However, the analytic solution of this equation
3.2
THE PROPOSED GENERALIZED SPECTRAL NONLOCAL OPERATOR
To fully exploit the "full-range" dependencies, the nonlocal block should have the ability to be consecutively stacked into the network to form deeper nonlocal structure. However, some types of nonlocal blocks such the NL and CGNL block cannot achieve this purpose (Tao et al. (2018)). To show the robustness of our SNL block when used in the deeper nonlocal structure, we firstly study the steady-state of deeper nonlocal structure when consecutively adding our SNL block. We also prove the stable hypothesis that the deeper nonlocal structure tends to learn stable affinity. Based this hypothesis, we extend SNL. block into full-order Chebyshev approximation, i.e. the gSL block which is more applicable for deeper nonlocal structure.
The stable hypothesis The Steady state analysis be used to analyze the stable dynamics of the nonlocal block. Here we give the steady-state analysis of our SNL block when consecutively adds into the network structure and get the Stable Hypothesis:
Lemma 1.
The Stable Hypothesis: when adding more than two consecutively-comeent SNL blocks with the same affinity matrix into the network structure, these SNL blocks are stable when the variable affinity matrix A satisfies: A A.
4

---

Under review as a conference paper at ICLR 2020
Source Image
Histogram of NS
Histogram of SNL
#1
#2
#3
#4
#5
#6
#8
#9
A
42
A3
A
4
A
A
4
Figure 2: The histogram of the strength statistics of the affinity matrix A where the abscissa the range of the strength and the ordinates is the number of the elements in A in these ranges. We can see that the histogram of A is nearly the same.
Proof. The stability holds when the weight parameters in Wi. W2 and W are small enough such that the CFL condition is satisfied (Tao et al. (018)). So we ignore them for simplicity. The discrete nonlinear operator of our SNL have a similar formulation as the NS operator:
Lz : -
where h is the discretization parameter. N is the input of the /thh block in the deeper nonlocal structure with z X. The stable assumption demands that N+1 Z.N. so the steady-state equation of the last SNL block can be written as:
Z N+1 N L -L 0.
The deeper nonlocal structure has more than one SNL blocks. So the N-1 and N-1 can be used to express N:
LZN = -I A) = -I (II-A)(ZN---- L
=- A-AA N-1 A) AJ
Finally, the steady-state equation becomes:
A A)ZN-1 -II (I A) = A
This equation can naturally extend to the k-hop affinity matrix A i.e. A - A.
To verify the stable hypothesis, we add five munsecutively-conneetee SNL blocks (and NS blocks) into the PreResnet56 He et al. (2016) and train this model on the train set the CIFARI 100 dataset with the initial learning rate 0.1 which is subsequently divided by 10 150 and 250 epochs (total 300 epochs). A weight decay 1e 4 and momentum 0.9 are also used. Then we test the trained model on the test set and output the affinity matrix of each image. Figure. Siswws the statisties that reflects the strength of the affinity matrix, 2-hop, 3-hop. and 4-hop affinity matrix: A, A A We can that the number of elements in each histogram bin are nearly the same. This means that
5

---

Under review as a conference paper at ICLR 2020
the A, A?, A3, A have similar distribution of all the elements in k-hop affinity matrixes, which also empirically verifies the stable-state equation: A A. Full-order spectral nonlocal operator With the stable hypothesis, the Chebyshev polynomials be simplified into piece-wist function (details in Appendix B). Taking this piece-wise function into the Eq. 7 we can get the full-order approximation of the SNI. operator:
(A = Σ (ATA(A) = Z0, + AZO2 + (2A - 1)Z03,
(10)
where 81 = Σn 1%440
0, 62 Σ K 15644 0, 03 Σ 1%4-3 0ig, whose upper bound is less
than 1. Then, extending it into multi-channel input and output with the residual connection, we can get our gSNL. block:
Y= Y=X+F(AA22) = = ZW, + AZW2 (2A - I)ZW3
(11)
The gSNL block is well-performed when the stable affinity hypothesis is satisfied, i.e. adding more than two nonlocal blocks with the same affinity matrix as shown in Table. 4.
3.3 IMPLEMENTATION DETAILS
The implementation details of the gSNL block is shown in fig. 3 The input feature map X RW*H*C is first fed into three Ixl convolutions with the weight kernel: W E R W RCixC, W, CIXC, to subtract the number of channel. One of the output Z R _ is used as the transferred feature map to reduce the calculation complexity, while the other two output & WxCC, V E R x XXC, are used to get the affinity matrix A. The sub-channel C, are usually two times less than the input channel C1. The affinity matrix is calculated by the affinity kernel function f() and then use the operation in Sec3.1 make it non-negative, symmetric and normalized. Finally, with the affinity matrix and the transferred feature map Z, the output of the nonlocal block can be obtained by the equation Eq. (II). Specifically, the three weight matrixes W1 E RCxC1,
W2 E CCXC, W3 E CCx are implemented as three 1x1 convolutions.
Reshipe
Feature Map
+
Fenture Vector
Affinity Kornel
2A
1x Cont
Reshape
Mup
Copy
Forward
Ouquut Ferture Festure
Haaaama Preduct
Hadama Product
t: I
Y 2PAME
Reshage
1 Cowe
Reshape
Reshage
x Cone
Cover
BN
Figure 3: The implementation of the generalized Spectral Nonlocal Block, which added the self- preserving part (green map) and the full-order approximation part (red map) than the NL block.
EXPERIMENT
4.1 SETTING
Datasets Our proposed SNL and gSNL blocks have been evaluated across several computer vision tasks, including image classification and video-based action recognition. For the image classifica- tion. both CIFAR-10 and CIFAR- 100 datasets (Krizhevsky & Hinton (2009) tested. The CIFAR- 10 dataset contains 60, 000 images of 10 classes, and CÍFAR-100 dataset contains 60, 000 images of 100 classes. For these datasets, 50, 000 images the train set and 10, 000 images as

---

Under review as a conference paper at ICLR 2020
the test set. We also generate experiments for the fine-gres tine-grained classification the Birds-200-201 (CUB-200) dataset (Welinder et al. (2010) which contains 11, 788 images of 200 bird categories. For the action recognition, the experiments are conducted on the UCF-101 dataset (Soomro et al. 22122), ) which contains 101 different actions.
Backbones For the image classification, the ResNet-50 and the PreResNet variations (including both PreResNet-20 and PreResNet-56) are used as the backbone networks. For the video classification task, we follow the I3D structure (Hara et al. (2018)) which uses k x k x k kernels to replace the convolution operator in the residual block.
Setting for the network In the main experiments, we set C, C1/2. Without loss of the generality, we use the "Dot Product" as the affinity kernel in the experiments. We add one SNL (or gSNL) block into these backbone networks to construct the SNL (or gSNL) network. For the ResNet and the I3D (Hara et al. (2018)) following Wang et al. (2018) we add the SNL block right before the last residual block ress- For the Pre series, we add the SNL block right after the second residual block in res i. For the other nonlocal-base block including the NL (Wang et al. (2018). the NS Tao et al. (2018)), the Compact Generalized Nonlocal Block (CGNL) YYue et al. (2018)) and the Double Attention Block (A2), the settings are all the same as ours. The difference of these blocks are shown in Table. 1, in which the Approximated Condition shows the strategy for the Chebyshev approximation and Channel wwis reflect the consideration of the channel relations.
Setting for the training For the image classification on CIFAR- 10 dataset and CIFAR- 100 dataset, train the models end-to-end without using pretrained model. The initial learning rate 0.1 is used for these two datasets with the weight decay le- 4 and momentum 0.9. The learning rate is divided by 10 at 150 and 250 epochs. The models are trained for total 300 epochs.
For the fine-grained classification on CUB-200 dataset, we use the models pretrained on ImageNet (Russakovsky al.] (2015) to initialize the weights. We train the models for total 200 epochs with the initial learning rate 0.1 which is subsequently divided by 10 at 31, 61, 81 epochs. The weight decay and momentum are the same as the setting of CIFAR- 10 and CIFAR-100.
For the video classification on the UCF-101 dataset, the weights are initialized by the pretrained I3D model on Kinetics dataset (Kay et al. (017)). We train the models with the initial learning rate 0.1 which is subsequently divided by 10 each 40 epochs. The training stops at the 100 epochs. The weight decay and momentum are the same as the setting of CIFAR-10 and CIFAR-100.
4.2
ABLATION EXPERIMENT
model
Self- Preserving
Self Attentionn
Approximated Conditions
Channel- Wise
NL
X
[0, 0/: 1,1 1 2]
X
A2
(0: =0 1,1
CGNL
X
V
16, = -0i= 1,1> 2]
NS
V
V
10. 0/i > 2) and (0) 02)
X
*SNL
18, 0l 2}
X
$gSNL
X
Table I: Summary of different types nonlocal block used in the experiments. Our proposed two models have less constraints and are more flexible compared with others.
The number of channels in transferred feature space The nonlocal-based block firstly reduces the channels of original feature map C₁ into the transferred feature space C, by the convolution to reduce the computation complexity. When C, is too large, the feature map will contain redundant information which introduces the noise when calculating the affinity matrix A. However, if C, is too small, it is hard to reconstruct the output feature map due to inadequate features. To test the robustness for the number of the C., we generate three types of models with different number of the transferred channels with the setting: "Sub 1" (C, = C1), "Sub 2" (C. = G), ). "Sub 4" (C, = G) as shown in Table. 2 Other parameters of the models and the training steps are the same as the setting in Sec.4.1. 1. Table. shows the experimental results of the three types of models with different nonlocal blocks. Our SNL and gSNL blocks outperforms other models profited by their flexible for learning. Moreover, from Table. 2 we can see that the performances of the CGNL steeply drops when the number of the transferred channels increases. This is because the CGNL block concerns
=
7

---

Under review as a conference paper at ICLR 2020
the relationship between channels, when the number of the sub-channel increases, the relationship between the redundant channels seriously interferes its effects. Overall, our proposed nonlocal block is the most robust for the large number of transferred channels (our model rise 1.1% in Topl while the best of others only rise 0.4% compared to the baseline).
Table 2: Experiments for transferred chan-
Table 3: Experiments for different positions
nels on CIFAR100 Dataset
on CIFAR Dataset
model
topl
top5
model
top
tops
PR-56
75.33%
93.97%
PR-56
75.33%
93.97%
+ +NL
75.29%
94.07%
+NI.
75.31%
92.84%
+ NS
75.39%
93.00%
NS
75.83%
93.87%
+ A2
75.51%
92.90%
A
75.58%
94.27%
Sub 1
Stage
CGNL
74.71%
93.60%
CGNL
75.75%
93.47%
+ SNL
76.34%
94.48%
+ "SNL
76.41% %
94.38% %
*gSNL
76.21%
94,42%
*gSNL
76.07%
94.16%
+NL
75.31%
92.84%
+N
75.64%
93.79%
NS
75.83%
93.87%
+NS
75.74%
94.02%
+ A2
75.58%
94.27%
A 75.60%
93.82%
Sub
Stage
CGNL
75.75%
93.47%
CGNL
74.64%
92.65%
"SNL
76.41 %
94.38%
*SNNL
76.29 %
94.27
"gSNL
76.07%
96.
+ *gSNI
76.02%
93.98%
+ NL
75.50%
93.75%
+
75.28%
93.93%
+ NS
75.61%
93.66%
NNS
75.44%
93.86%
A2
75.61%
93.61%
A
75.21%
93.65%
Sub 4
Stage 3
CGNL
75.27%
93.05%
CGNL.
74.90%
92.46%
+ SNN
76.02%
94.08%
+ *SNN
75.68%
93.90%
ggNNL
76.05%
94.21%
*gSNL
75.74%
93.78%
The stage for adding the nonlocal blocks The nonlocal-basee blocks be added into the different stages of the preResNet (or the ResNet) to form the Nonlocal Net. In Tao et al. (2018). the nonlocal- based blocks are added into the early stage of the preResNet catch the long-range correlations. Here we experiment the performance of adding different types of nonlocal blocks into the three stages (the first, the second and the third stage of the preResNet) and train the models on CIFAR100 dataset with the same setting discussed in Sec.5.2. The experimental results are shown in Table. We can see that the performances of NL block is lower than the backbones when adding into the early stage. However, our proposed SNL block has 0.81% improvement compared with the backbone when respectively adding into all the three stages, which much higher than the other type nonlocal blocks (only 0.42% for the best case).
Source
Ours
Res50
NL
CGNL
NS
A2
Figure 4: The Feature maps of Nonlocal-bace Network. Our SNL block has better results for the crucial part of the birds as shown in the highlighted boxes.
8

---

Under review as a conference paper at ICLR 2020
To intuitively show the stability and robustness of our SNL, give the spectrum analysis for the estimated weight matrices (Tao et al. (2018)). We extract the self eeff-attention weight matrix: Wg. W of the NL block and the NS block, W go W2 of our proposed SNL block. The dimension of the weight matrix satisfies: W, RCxx, W E RC,C W2 E RC,,C, To make all the eigenvalues
real, we let: W [W, (WW,)"
We do the same to the W2. Figure. shows the top thirty- two eigenvalues of the weight matrix of W on the models in Table. 3] We can see that the density of the negative cigenvalues is higher than the positive eigenvalues of the NL block when adding into all three stages. This phenomenon makes the NL operator F(A, Z) in Eq. (I) less than zero So the output feature map is less than the input feature map, i.c. Y X (more detail of this phenomenon can be seen in Tao et al. (018)). The NS block can avoid "the damping effect" to some extent by concerning the diffusion nature. However, when adding into the early stage, only six eigenvalues of the nonlocal stage are not equal to zero. This phenomenon makes the nonlocal stage cannot effectively magnify the discriminated feature. Comparing with these two models, our proposed SNL block has more positive eigenvalues which takes effect to enhance the discriminated features and also avoids the "damping effect".
OUTS
15
nl
10
05-
-15
20
10
20
25
-20
15
20
25
30
10
15
20
25
30
Stage
1
Stage 2
Stage
Figure 5: The eigenvalue of the the nonlocal weight matrix trained on the CIFARI00 dataset
The number of the nonlocal blocks We test the robustness for adding multiple nonlocal blocks into the backbone network which forms the three type network "Different Position (DP 3)", "Same Position 3 (SP 3y" "Same Position 5 (SP 5)" shown in Table. 4. The result are shown in Table. 4. For the model "DP3", three blocks are added into the stage 1, stage 2, and stage 3 (right after the second residual block). We can see that adding three proposed nonlocal operators into different stages of the backbone generate a larger improvement than the NS operator and NL operator (2.4% improvement). This because when adding NS and NL into the early stage, these two models cannot better aggregate the low-level features and interfere the following blocks. For the model "SP 3" ("SP 5*),, we add three (five) consecutively-comee connected nonlocal blocks into the stage 1. Note that different from the experiment in Tao et al. (218) and Wang et al. (2018), these consecutively- connected nonlocal blocks have the same affinity matrix. From Table. 4, we can see that profited by concerning the stable hypothesis discussed in Sec 3.3, our gSNL outperform all other models when adding consecutively-conneee 0.41% higher than the best performance of other type nonlocal blocks) and has relatively stable performance. However, one drawback is that our gSNL may interfere the learning when adding only one nonlocal block (the stable hypothesis satisfied).
nonlocal blocks (rises average 0.72% to the backbone and
4.3 MAIN RESULTS
We test the networks with the Nonlocal Block (NL), the Nonlocal Stage (NS), the Compact Gen- eralized Nonlocal block (CGNL), the Double Attention Block (A2) and our SNL (gSNL) blocks in the different visual learning tasks. The experiment settings are discussed in Sec.4.1. Our models outperform other types of the nonlocal blocks across several standard benchmarks. Table. 5 shows the experimental results the CIFAR10 dataset, the Topl rises about 65%, which is higher than adding other type nonlocal blocks (0.3%). As the experiments CIFAR 100 dataset shown in Table. 7 using our proposed block brings improvement about 1.8% with ResNet50. While using a more simple backbone PreResnet56, our model can still generate 1.1% improvement as shown in Table. 6
see that by adding one proposed block,
Table. g shows the experimental results on the fine-grained image classification task on CUB-200 datasets. Our model outperforms other non-channel-concemingg blocks and generate (0.42%) im-

---

Under review as a conference paper at ICLR 2020
model
top
top5
model
top1
top5
PR-56
75.33%
93.97%
PR-56
75.33%
93.97%
N
75.31%
92.84%
+ +NI.
75.43%
93.67%
NNS
15.83%
93.87%
NS
75.30 %
93.74%
SP
A2
75.38%
94.27%
SP
+ F2
75.23%
94.03%
CGNL
75.75%
93.47%
+ CGNL
75.64%
93.05%
SNNL
76.41% %
94.38 %
*SNL
75.70%
94, 10%
+ "gSNL
76.07%
94.16%
*gSNNL
76.16%
94.32% %
NNL
74.34%
93.31%
+ NL
75.13%
93.53%
NS
75.00%
93.57%
+ NS
75.25%
94.00%
DP 3
A2 75.63%
94.12%
SP
+ A2
75.61%
93.81%
CGNL
75.96%
93.10%
CGNL
75.15%
92.93%
*SNL 76.70%
93.94%
+ SNL
76.04%
94, 19%
+ *gSNL 76.45%
94.53%
-gSNL
76.04%
94.35 %
Table 4: Experiments for different numbers on CIFAR100 Dataset
provement. Comparing with the channel-wise concerning CGNL. block, our model only a bit lower in Top1. Fig. 3 also shows the visualized feature map which is formed by adding the up- sampled feature output with the source image. We can see that the feature maps of our proposed block can cover more critical area of the birds. For example, both the left and right wings (red square) of the birds can be focused profited by the better long-range concerning of our SNL. More- over, benefited from the flexibility of the W1. proposed SNL can also catch relatively large range of the discriminative parts. Table. shows the experimental results on the action recognition task. The network with our proposed block generate 1.8% improvement than the I3D model and outperforms all other nonlocal models on the UCF-101 dataset.
Table 5: The Results on Cifar10 Table 6: The Results Cifar Table 7: The Results Cifar 100
model
topl
top5
model
topl
top5
model
topl
top5
PR-20
94.94%
99.87%
PR-56
75.33%
93.97%
R-50
76.50%
93.14%
+
94.01%
99.82%
+ NL
75.31%
92.84%
+ NL
76.77%
93.55%
+ NS
95.15%
99.88%
+ NS
75.83%
93.87%
NS
77.90%
94.34%
+ A2
92.44%
99.86%
+
75.58%
94.27%
A2
77.30%
93.40%
+ CGNI.
94.49%
99.92%
+ CGNL
75.75%
93.47%
CGNL.
74.88%
92.56%
*NL
94.69%
99.84%
SNNL
76,41 %
94.38%
+ *SNI.
78.17%
94.17%
*gSNL
95.59%
99.92%
gSNL
76.07%
94.16%
*gSNL
77.28%
93.63%
Table 8: The Results on UCF101
Table 9: The Results on CUB
model
topl
top5
model
topl
top5
I3D
81.57%
95.40%
R-50
85.43%
96. 70%
NL
81.37%
95.765
NL
85. 85.34%
96.77%
NS
82.50%
95.84%
NS
85.54%
96.56%
A2
82.68%
95.85%
A2
86.02%
96.56%
CGNL
83.16%
96. 16.16. %
CGNL.
86.14%
96.34%
*SNL
82.30%
95.56%
*SNL.
85.91%
96.65
+ *gSNL
83.21%
96.53%
+ *gSNL
85,95%
96.79 %
5 CONCLUSION
In this paper, we explain the nonlocal block in the graph view and propose the spectral nonlocal (SNL) block which is more robust and well-behaved. Our SNL block is generalized version of the NL and NS block and having more liberty for the parameter learning. We also give the stable hypothesis for deeper nonlocal structure and extend the SNL to gSNL that can be applied to the deeper nonlocal structures. The experiments on multiple computer vision tasks show the high robustness and performance of our proposed nonlocal block. Feature works will focus using the SNL block into different vision task and its roubustness for the other type of neural network such as the Generative Adversarial Networks (GAN).
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Liang-Chies Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI),
40(4):834-848, 2017.
Yunpeng Chen, Yannis Kalantidis, Jianshu Li, Shuicheng Yan, and Jiashi Feng. A 2-nets: Double attention networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 352- 361, 2018.
Nieves Crasto, Philippe Weinzaepfel, Karteek Alahari, and Cordelia Schmid. Mars: Motion- augmented rgb stream for action recognition. In Proceedings of the IEEE Conference on Com- puter Vision and Pattern Recognition, pp. 7882-7891, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3844-3852, 2016.
Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He. Slowfast networks for video recognition. In Proceedings of the IEEE International Conference on Computer Vision, pp. 6202- 2211,2019
Jiyang Gao and Ram Nevatia. Revisiting temporal modeling for video-based person reid. arXiv preprint arXiv:1805.02104 2018.
Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh. Can spatiotemporal 3d cnns retrace the history of 2d cnns and imagenet? In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6546-6555, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision (ECCV), pp. 630-645. Springer, 2016.
Xiangyu He, Ke Cheng, Qiang Chen, Qinghao Hu, Peisong Wang. and Jian Cheng. Compact global descriptor for neural networks. arXiv preprint 1rXivv1907.09665 2019.
Zilong Huang, Xinggang Wang. Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu. Conet: 1rXiv:1811. 1811.1121, 2018.
Criss-cross attention for semantic segmentation. arXiv preprint arXiv: 1.11.1111111
Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijaya- narasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al. The kinetics human action video dataset. arXiv preprint 1XX5:07005006500 2017.
Alexander Kozlov, Vadim Andronov, and Yana Gritsenko. Lightweight network architecture for real-time action recognition. arXiv preprint arXiv: 1oXxv:/005007/11 2019..
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, Tech. Rep, 1, 01 2009.
Xingyu Liao, Lingxiao He, Zhouwang Yang, and Chi Zhang. Video-based person re-identification via 3d convolutional networks and non-local attention. In Asian Conference on Computer Vision (ACCV), pp. 634..34.500 Springer, 2018
Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field deep convolutional neural networks. In Advances in Neural Information Processing Sys- tems (NeurIPS), pp.
2016.
Chao Peng, Xiangyu Zhang, Gang Yu, Guiming Luo, and Jian Sun. Large kernel matters-improve semantic segmentation by global convolutional network. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4353-4361, 2017.
George M Phillips. Interpolation and approximation by polynomials, volume 14. Springer Science & Business Media, 2003.

---

Under review as a conference paper at ICLR 2020
Zhaofan Qiu, Ting Yao, and Tao Mei. Learning spatio-tempont representation with pseudo-3d residual networks. In proceedings of the IEEE International Conference on Computer Vision, pp- 5533-5541, 2017.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision (IJCV), 115(3):211-252 2015.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. Ucf101: dataset of 101 human actions classes from videos in the wild. arXiv preprint arXiv: 12 12.0402, 2012.
Yunzhe Tao, Sun, Qiang Du, and Wei Liu. Nonlocal neural networks, nonlocal diffusion and nonlocal modeling. In Advances in Neural Information Processing Systems (NeurIPS), pp. 496- 506, 2018.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp- 7794-7803, 2018
P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. Belongie, and P. Perona. Caltech-UCSD Birds 200. Technical Report CNS-TR-2010-001, California Institute of Technology. 2010.
Kaiyu Yue, Ming Sun, Yuchen Yuan, Feng Zhou, Errui Ding, and Fuxin Xu. Compact generalized non-local network. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6510- 6519, 2018.
Ruimao Zhang, Jingyu Li, Hongbin Sun, Yuying Ge, Ping Luo, Xiaogang Wang, and Liang Lin. Scan: Seff-and-collaboraae attention network for video person re-identification. IEEE Transac- tions on Image Processing (TIP). 2019.
Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia. Pyramid scene parsing network. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2881-2890, 2017.
12

---

Under review as a conference paper at ICLR 2020
A ANALYTIC SOLUTION OF THE CHEBYSHEV APPROXIMATE
Here we give the analytic solution for the coefficients in Chebyshev polynomials (Phillips) (2003)):
Theorem 2. Giving a function f(x), x = (2,,"",-,,NNN EN), can be optimally approxi- mated by Chebyshev polynomials: f(x) s K-1 (x),,x), only when as satisfies: an N [xx
We call the og as the analytic solution of the Chebyshev coeffcients.
Based these theorem,
get the analytic solution of the parameter 0 for Eq.
Lemma 2. The spectral nonlocal operator can be best approximated when the function g( w can be best approximated by the Chebyshev polynomials, iee. the analytic solutions of the Chebyshev coeffcients satisfy:
N Σ N 1=
02 =
((A))T((A)))
2 N
Σ wy (2(T)) -=
(12)
B THE PIECEWISE CHEBYSHEV POLYNOMIALS
Taking A = A into the Chebyshev polynomials of the affinity matrix A, the Chehyshev polyno- mials becomes:
(A(A)
Ti(A) A
(2(A) (AT) (A( 2AA I 2A
Ts(A) = (AT) T(() = 2A(2A 1) - - =
(13)
(AA 2AT((A) (A) 2AA 2A I To(A)
Tb(A) = (AT((A T3(A) = 2AI A = A A= =i{AA)
(A) 2ATA(A) TA(A) I₂(A) (A) (A)
This cyclic form of Chebshev polynomials & can be reformulated as a piecewise function:
I
k%4 0
(A(A)
A
4%44 = 1
||
k%4 3
(14)
2A
4%4 2
C EXPERIMENT OF SEMANTIC SEGMENTATION ON VOC2012 DATASET
For the semantic segmentation tasks, we generate experiment on the VOC2012 dataset with the model proposed by Chen et al. (2017). We add different types of nonlocal blocks on right before the last residual block in res4 of the ResNet50. The models are trained for 50 epochs with the SGD optimize algorithm. The learning rate set 0.007 with the weight decay 5e 4 and momentum 0.9. Experimental results show that the model with our proposed block can the best results.
model
mloU
fwloU
acc
R-50
0.713
0.868
0.926
+ NL
0.722
0.872
0.927
+ NS
0.722
0.873
0.927
A2
0.723
0.874
0.928
+ CGNL
0.722
0.872
0.928
*NNL
0.726
0.875
0,930
*pSNL
0.727
0.875
0.929
Table 10: Experiment on VOC2012 Dataset
13

---

Under review as a conference paper at ICLR 2020
D THE EXAMPLE OF THE AFFINITY MATRIX ON CUB DATASETS
Experiments to verify the stable hypothesis is also generated on the CUB datasets, we add three consecutively-commeeed SNL blocks (and NS blocks) into the ResNet50 (right before the last resid- ual block of res4) and train this model on the train set of the CUB dataset with the initial learning rate 0.1 which is subsequently divided by 10 31, 61 and epochs (total 200 epochs). weight decay le - 4 and momentum 0.9 are also used. Figure. 6 shows the histogram of the strength statis- ties of the affinity matrix A. We can see that although using different backbone and dataset, the distribution of the k-hop affinity matrixes are corresponded with the experiments on CIFAR 100.
Histogram of NS
Histogram of SNL
A1 2
3
A
A
A2
33
A
Figure 6: The histogram of the strength statistics of the affinity matrix A where the abscissa is the range of the strength and the ordinates is the number of the elements in these ranges. We can see that the histogram of A is nearly the same.
E EXPERIMENTS ON VIDEO-BASED PERSON RE-IDENTIFICATION
Experiments are also conducted on the challenging datasets on Video-based Person Re-identification task including the Mars, ILID-SVID and PRID2011. For the backbone, follow the strategy of Gao & Nevatia (201)) that uses the pooling (RTMtp) and attention (RTMta) to fuse the spatial- temporal features. Note that the models are totally trained on ilidsvid and prid2011 rather than fine- tuning the pre-trained model on Mars dataset. The experimental results are shown in Table. 12, 13. We can see that in these datasets, our proposed block can still generate consistent improvements.
Table 11: The Results Mars Table 12: The Results ILID- Table 13: The Results on
dataset
SVID dataset
PRID2011 1 dataset
model
mAP
Rank
model
mAP
Rank1
model
mAP
Rankl
RTMta
77.70%
79.10%
RTMta
69.70%
58.70%
RTMta
86.60%
79.80%
NI.
72.90%
80.90%
NL
66.30%
56.00%
NL
90.70%
85,40%
*SNN.
74.00%
81.9%%
+ *SNL
79.40%
70.00%
+ *SNL
91.50%
86.50%
RTMtp
75.70%
82.30%
RTMIp
81.60%
74.70%
RTMtp
90.50%
86.50%
NL.
75.54%
83.40%
NL
83.00%
75.30%
NL
89.70%
85. 85,40%
*SNL
76.80%
99.92%
*SNL.
84.80%
76.60 %
+ *SNL
92.40%
88.80 %
14

---

Under review as a conference paper at ICLR 2020
F ADDITIONAL EXPERIMENTS ON ACTION CLASSIHICATION
Ours SNL can also improve the performance of other network structures such as the Pseudo 3D Convolutional Network (P3D) (Qiu al. (2017)), the Motion-augmented RGB Stream (MARS) (Crasto et al. 2019)), the Slow-Fast Network (Slow-Fast) (Feichtenhofer et al. (2019) and the Video Transformer Network (VTN) (Kozlov et al. (019)). For P3D and MARS, our SNL block inserted right before the last residual layer of the res3. For the Slow-Fast, we replace its original NL block with our SNL block. For the VTN, we replace its multi-head self-attention blocks (paralleled- connected NI blocks) with our SNL blocks. The Slow-Fast network are trained end-to-end on the UCF-101 dataset while others use the model pretrained on Kinetic400 dataset and finetuning on the UCF-101 dataset. From Table. 14, We can see that all the performances are improved when adding our proposed SNL model.
Experiments Kinetics-400 dataset are also given in Table. 15. block into the Slow-Fast Network can generate 2. % improvement.
We can see that inserting SNL
model
Topl
P3D
81 $1.23%
P3D *SNL
82.65%
SlowFast
81.17%
SlowFast *SNI
80.54%
VTN
90.06%
VTN + *SNL
90.34%
MARS
92.29%
MARS SNL
92.79%
Table 14: Experiment on UCF-101 Dataset
model
Top1
SlowFast
77.88%
SlowFast + NL
79.16%
SlowFast + *SNL.
79.98%
Table 15: Experiment Kinetics-400
15


Reviews:
[{"review_id": "rkeQXGZ_qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "SUMMARY: \n- Propose spectral non-local block\n- improvement on image and video classification tasks\n\nApologies, I am not at all familiar with the theory and math behind this proposal, I do not think I am in a position to review this paper. The experiments seem convincing enough that the authors made enough effort to prove their method might work.\n\n- Feature maps to show robustness of method is a good point\n- CIFAR-10 and CIFAR-100 are certainly a good start, but might not be the best datasets to test for image classification, in lieu of ImageNet and others.\n- Classification itself is a good start, it might be interesting to think about using this in a generative model such as GAN. The content reminds me of Self-Attention GAN which uses a similar non-local block (self-attention).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rke6CgqpqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "I have two general concerns, the first is related to the presentation and the second to the relevance of the results.\n\n(1) Presentation is confusing at many points, for instance:\n\n* It is unclear if theorem in Eq. 4 is original or belongs to Shuman et al 2013. (no proof is given)\n\n* Eq. 8 seems an arbitrary decomposition of the original NonLocal operator that could have been proposed without any reference to the Chebyshev expansion (which, on the other hand, is truncated to 1st order with no extra explanation).\n\n* The point of Fig. 1 and Fig 4 is not clear. Fig. 1 explains how SpectralNonLocal reduces to NonLocal and NonLocalStage, but we can see this from the formulas. I dont see how this discussion on the Ws relates to the regions highlighted in the bird.\nThe same applies to Fig. 4. What are we supposed to see in Fig. 4 (and, more importantly, why?).\n\n* What is the CFL condition? (is it the Courant-Friedrichs–Lewy sampling condition?). How is that related to the values of Ws. Can we take those arbitrarily small as suggested in that proof?\n\n* The upper limit in the sums after Eq. 10 is unclear.\n\n* First time table 4.2 is cited there is no context to understand it. (actually there is no table labeled as \"Table 4.2\") Where do we see the different number of NonLocal units?. This is only clear when you arrive and read text of page 9 (but not when cited the first time from page 6).\n\n* Explanation of experiments is a little bit confusing (e.g. what does it mean top1 and top5 in tables?). The only explanation of \"top-something\" I found in the text has to do with eigenvectors in fig. 5. This also apply to the \"topX\" in the figures?\n\n(2) Nevertheless, the main concern is the scarce relevance of the results: differences of behavior in all tables are about 1%. Then, what is the real advantage of the proposed modification? \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1gW3qf29r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 spectral non-local block, which is a generalized method of the non-local block and non-local stage in the literature. The proposed spectral non-local block can be plugged into a neural network to improve its effectiveness. The paper also provides theoretical analyses of the stability of the proposed method, and also extend the method by including more  Chebyshev polynomial terms. Experiments are conducted on image classification and action recognition tasks, and they valid the effectiveness of the proposed method. \n\nThe idea is well-motivated, and it is a generalization of existing works in the literature. I do like this idea. However, I am afraid that the idea is not well explained and supported, thus I gave a weak reject to encourage the authors to further improve the paper.\n\nThe major concern I have is the reasonability of the experiments.  The experiments in the paper show relative performance gain with respect to a baseline method. It seems that there is a lack of comparison with state-of-the-art methods in the literature. For example, in Table 8, a performance gain is observed when compared with I3D. However, the recent STOA models can achieve much higher accuracy than the baseline. and also the proposed method. Since the proposed method is generic to all neural nets, it makes more sense to compare with SOTA and make improvements based on SOTA.  What is the conclusion from Table 4? Are you trying to demonstrate that the best configuration is DP3, and increasing the number of consecutive non-local blocks (from SP3 to SP5) doesn't work? It is awkward since the paper gives a stable hypothesis for deeper nonlocal structure, but experimentally the deeper structure doesn't work well. Figure 4 is abrupt without much background descriptions. Are the images randomly chosen? Ours here means SNL or gSNL? Is the colored superimposition the attention map (I believe so but the paper doesn't indicate so) and how to interpret it? What is the relation of the coverage of the critical parts on birds and the long-range dependency? More background descriptions and interpretations of the results are needed. \n\nAnother concern I have is the clarity of the writing. There are quite a number of informal use of English, mismatched descriptions, undefined acronyms, etc. For example, in the caption of Fig. 1, it is said self-attention and self-preserving are taken effect by W1 and W2, which is contradictory to what is illustrated in the figure. Also, the terms self-attention and self-preserving, and other terms such as CGNL, A2, Hadama (Hadamard?) product, are not formally defined or described.  A lot of grammar errors and informal use of English are present, such as \"which lead to\", \"the weight means\", \"when using in the neural network\", \"fig. 4\", \"Figure. 2\", \"more liberty for the parameter learning.\", etc. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Hyg-EusOKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "In this paper, authors propose a spectral nonlocal block. First, they re-interpret the nonlocal blocks in a graph view and then use Chebyshev approximation to obtain the spectral nonlocal block which is quite simple by adding a ZW_1 term. Furthermore, they analyze the steady-state to build up a deeper nonlocal structure. Also, the gSNL is simple by adding a (2A-I)ZW_3 term.\n\nOverall, the paper is written well. I like the idea to interpret the nonlocal operation in the graph view. More important, the resulting formulation is quit concise for implementation. However, my main concern is the experiment, which should be further enhanced by perform large-scale video classification like Kinetics400.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new formulation of the non-local block and interpret it from the graph view. The idea is interesting and the experimental results seems to be promising.

Reviewer has two major concerns. The first is the presentation, which is not clear enough. The second is the experimental design and analysis. The authors add more video dataset in the revision, but still lack comprehensive experimental analysis for video-based applications. 

Overall, the idea of non-local block from graph view is interesting. However, the presentation of the paper needs further polish and thus does not meet the standard of ICLR

Decision: Reject