  Non-local operation is widely explored to model the long-range dependencies.
However, the redundant computation in this operation leads to a prohibitive
complexity. In this paper, we present a Representative Graph (RepGraph) layer
to dynamically sample a few representative features, which dramatically reduces
redundancy. Instead of propagating the messages from all positions, our
RepGraph layer computes the response of one node merely with a few
representative nodes. The locations of representative nodes come from a learned
spatial offset matrix. The RepGraph layer is flexible to integrate into many
visual architectures and combine with other operations. With the application of
semantic segmentation, without any bells and whistles, our RepGraph network can
compete or perform favourably against the state-of-the-art methods on three
challenging benchmarks: ADE20K, Cityscapes, and PASCAL-Context datasets. In the
task of object detection, our RepGraph layer can also improve the performance
on the COCO dataset compared to the non-local operation. Code is available at
https://git.io/RepGraph.
