Neural Nearest Neighbors Networks
Non-local methods exploiting the self-similarity of natural signals have been well studied, for example in image analysis and restoration. Existing approaches, however, rely on k-nearest neighbors (KNN) matching in a fixed feature space. The main hurdle in optimizing this feature space w. r. t. application performance is the non-differentiability of the KNN selection rule. To overcome this, we propose a continuous deterministic relaxation of KNN selection that maintains differentiability w. r. t. pairwise distances, but retains the original KNN as the limit of a temperature parameter approaching zero. To exploit our relaxation, we propose the neural nearest neighbors block (N 3 block), a novel non-local processing layer that leverages the principle of self-similarity and can be used as building block in modern neural network architectures. 1 We show its effectiveness for the set reasoning task of correspondence classification as well as for image restoration, including image denoising and single image super-resolution, where we outperform strong convolutional neural network (CNN) baselines and recent non-local models that rely on KNN selection in hand-chosen features spaces.
Update: I am somewhat convinced by the rebuttal. I will increase my rating, although I think that the quantitative improvements are quite marginal.  Summary: Authors propose a neural network layer based on attention-like mechanism (a "non-local method") and apply it for the problem of image restoration. The main idea is to substitute "hard" k-NN selection with a continuous approximation: which is essentially a weighted average based on the pairwise distances between the predicted embeddings (very similar to mean-shift update rule).  Although the paper is clearly written, the significance of the technical contributions is doubtful (see weaknesses), thus the overall score is marginally below the acceptance threshold.  Strengths: + The paper is clearly written. + There is a (small) ablation study. +/- I like the connection with latent variable models learning (L114), the high variance of the gradient estimators is a big problem. However, I would expect a deeper analysis of this issue, and in particular how does the "continuous deterministic relaxation" help this.   Weaknesses: - In general, very similar approaches have been widely used before (matching networks, memory networks, non-local neural networks to name a few), and the difference suggested by the authors (L71, label probabilities vs features), does not seem very significant. Effectively, instead of aggregating the labels of the neighbours authors aggregate the features of the neighbours.  - Authors clearly state that the "N3 block" can be used as a generic non-local module, yet the only problem they consider is image restoration.  - In Table 2, the results for k=1 are already better than the baselines. This actually hints that the performance gain might be for a reason different from applying Eq.10. - It is not entirely clear if the equivalence with hard k-NN for t -> 0 is really of practical importance: there are no details in the paper of what kind of values the network produces for the temperature.