This paper focuses on adversarially robust machine learning. As existing literature struggles to develop adversarially robust models, the authors suggest to focus on building adversarially robust features. The authors present a method to build adversarially robust features, leveraging on the eigenvectors of the laplacian of a graph G obtained from the distances between the points in the training set. As a validation for their approach, the authors present a theoretical example where traditional methods (neural nets and nearest neighbors) fail to provide robust classifiers, while the proposed method provably provides robust features, and present experimental comparisons on MNIST data. Furthermore, the authors show that if there exists a robust function on the training data, then the spectral approach provides features whose robustness can be related to that of the robust function, which suggests that the spectral properties of the training data are related to the adversarial robustness. This intuition is also validated experimentally at the end of the paper.

The nonlocal-based blocks are designed for capturing long-range spatial-temporal dependencies in computer vision tasks. Although having shown excellent performance, they still lack the mechanism to encode the rich, structured information among elements in an image or video. In this paper, to theoretically analyze the property of these nonlocal-based blocks, we provide a new perspective to interpret them, where we view them as a set of graph filters generated on a fully-connected graph. Specifically, when choosing the Chebyshev graph filter, a unified formulation can be derived for explaining and analyzing the existing nonlocal-based blocks (e.g., nonlocal block, nonlocal stage, double attention block). Furthermore, by concerning the property of spectral, we propose an efficient and robust spectral nonlocal block, which can be more robust and flexible to catch long-range dependencies when inserted into deep neural networks than the existing nonlocal blocks. Experimental results demonstrate the clear-cut improvements and practical applicabilities of our method on image classification, action recognition, semantic segmentation, and person re-identification tasks.