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 procedure can improve the identification of relevant variables, especially those with subtle effects. For example, in genetic and genomic studies, the integration of such information can help identify genomic regions or sets of markers associated with complex traits. The Bayesian approach provides a natural framework to integrate the graph information through the prior distributions. In this work we propose combining two priors that have been well studied separately, the Gaussian Markov random field (GMRF) prior and the horseshoe prior, to perform selection on graph-structured variables. Local shrinkage parameters that capture the dependence between connected covariates are specified for the regression coefficients with the option of incorporating the sign of their empirical correlations. This encourages a similar amount of shrinkage for the regression coefficients while allowing them to have opposite signs. For non-connected variables, a standard horseshoe prior is specified. After evaluating the performance of the method using different simulated scenarios, we analyze the quantitative trait loci mapping study that motivated the proposed method. We also present two other real data applications, one in near-infrared spectroscopy with sequential dependence structure across all wavelengths and the other in gene expression study with a general dependence structure among transcripts.