  Interference exists when a unit's outcome depends on another unit's treatment
assignment. For example, intensive policing on one street could have a
spillover effect on neighboring streets. Classical randomization tests
typically break down in this setting because many null hypotheses of interest
are no longer sharp under interference. A promising alternative is to instead
construct a conditional randomization test on a subset of units and assignments
for which a given null hypothesis is sharp. Finding these subsets is
challenging, however, and existing methods are limited to special cases or have
limited power. In this paper, we propose valid and easy-to-implement
randomization tests for a general class of null hypotheses under arbitrary
interference between units. Our key idea is to represent the hypothesis of
interest as a bipartite graph between units and assignments, and to find an
appropriate biclique of this graph. Importantly, the null hypothesis is sharp
within this biclique, enabling conditional randomization-based tests. We also
connect the size of the biclique to statistical power. Moreover, we can apply
off-the-shelf graph clustering methods to find such bicliques efficiently and
at scale. We illustrate our approach in settings with clustered interference
and show advantages over methods designed specifically for that setting. We
then apply our method to a large-scale policing experiment in Medellin,
Colombia, where interference has a spatial structure.
