A graph structure is commonly used to characterize the dependence between variables, which may be induced by time, space, biological networks or other factors. Incorporating this dependence structure into the variable selection process can increase the power to detect subtle effects without increasing the probability of false discoveries and can improve predictive performance. Methods presented are proposed to accomplish this in the context of spike-and-slab priors as well as global-local shrinkage priors. For the former, a binary Markov random field prior is specified that leverages evidence from correlated outcomes on the variable selection indicators to identify outcome-specific covariates. For the latter, a Gaussian Markov random field prior is combined with a horseshoe prior to performing selection on graph-structured variables. The methods using epigenomic are illustrated, genomic and transcriptomic data.