To accelerate high-density interactome mapping, we developed a yeast two-hybrid interaction screening approach involving short-read second-generation sequencing (Y2H-seq) with improved sensitivity and a quantitative scoring readout allowing rapid interaction validation. We applied Y2H-seq to investigate enzymes involved in protein methylation, a largely unexplored post-translational modification. The reported network of 523 interactions involving 22 methyltransferases or demethylases is comprehensively annotated and validated through coimmunoprecipitation experiments and defines previously undiscovered cellular roles of nonhistone protein methylation.