  Spatial self-attention layers, in the form of Non-Local blocks, introduce
long-range dependencies in Convolutional Neural Networks by computing pairwise
similarities among all possible positions. Such pairwise functions underpin the
effectiveness of non-local layers, but also determine a complexity that scales
quadratically with respect to the input size both in space and time. This is a
severely limiting factor that practically hinders the applicability of
non-local blocks to even moderately sized inputs. Previous works focused on
reducing the complexity by modifying the underlying matrix operations, however
in this work we aim to retain full expressiveness of non-local layers while
keeping complexity linear. We overcome the efficiency limitation of non-local
blocks by framing them as special cases of 3rd order polynomial functions. This
fact enables us to formulate novel fast Non-Local blocks, capable of reducing
the complexity from quadratic to linear with no loss in performance, by
replacing any direct computation of pairwise similarities with element-wise
multiplications. The proposed method, which we dub as "Poly-NL", is competitive
with state-of-the-art performance across image recognition, instance
segmentation, and face detection tasks, while having considerably less
computational overhead.
