Abstract
Motivated by gene set enrichment analysis, we investigate the problem of combined hypothesis testing on a graph. A general framework is introduced to make effective use of the structural information of the underlying graph when testing multivariate means. A new testing procedure is proposed within this framework, and shown to be optimal in that it can consistently detect departures from the collective null at a rate that no other test could improve, for almost all graphs. We also provide general performance bounds for the proposed test under any specific graph, and illustrate their utility through several common types of graphs. Numerical experiments are presented to further demonstrate the merits of our approach.