Many therapeutic molecules are known to bind several proteins, which can be different from the initially targeted one. Such unexpected interactions with proteins called off-targets can lead to adverse effects. Potential off-target identification is important to predict to avoid drug side effects or to discover new targets for existing drugs. We propose a new program named PatchSearch that implements local nonsequential searching for similar binding sites on protein surfaces with a controlled amount of flexibility. It is based on detection of quasi-cliques in product graphs representing all the possible matchings between two compared structures. This method has been benchmarked on a large diversity of ligands and on five data sets ranging from 12 to more than 7000 protein structures. The experiments conducted in this study show that the PatchSearch method could be useful in the early identification of off-targets. The program and the benchmarks presented in this paper are available as an R package at https://github.com/MTiPatchSearch .