Summary: In this paper, we explore the multiple testing problem of paired null hypotheses, for which the data are collected on pairs of entities and tests have to be performed for each pair. Typically, for each pair \((i,j)\), we observe some interaction/association score between \(i\) and \(j\) and the aim is to detect the pairs with a significant score. In this setting, it is natural to assume that the true/false null constellation is structured according to an unobserved graph, where present edges correspond to a significant association score. The point of this work is to build an improved multiple testing decision by learning the graph structure. Our approach is in line with the seminal work of W. Sun and T. T. Cai [J. R. Stat. Soc., Ser. B, Stat. Methodol. 71, No. 2, 393–424 (2009; Zbl 1248.62005)], that uses the hidden Markov model to structure the dependencies between null hypotheses. Here, we adapt this strategy by considering the stochastic block model for the latent graph. Under appropriate assumptions, the new proposed procedure is shown to control the false discovery rate, up to remainder terms that vanish when the size of the number of hypotheses increases. The procedure is also shown to be nearly optimal in the sense that it is close to the procedure maximizing the true discovery rate. Numerical experiments reveal that our method outperforms state-of-the-art methods and is robust to model mis-specification. Finally, the applicability of the new method is demonstrated on data concerning the usage of self-service bicycles in London.