In real world, there exist a kind of Multi-Attribute Decision Making (MADM) problems in which correlations and prioritization relationships of attributes can be found. The notion of Fuzzy Graphs (FGs) performs well when expressing correlations between attributes via edges between vertices in fuzzy information systems, which makes it possible for addressing correlational MADM problems. In addition, as a significant information depiction tool, Dual Hesitant Fuzzy Sets (DHFSs) generalize traditional Intuitionistic Fuzzy Sets (IFSs) to the context of hesitations, thus DHFSs excel in recording numerous imprecise and hesitant information. In this paper, we aim to investigate FGs in the Dual Hesitant Fuzzy (DHF) background and further explore efficient approaches to complicated MADM situations. Following the above motivation, we first develop the definition of Dual Hesitant Fuzzy Graphs (DHFGs). Then, some common operational laws and mapping relationships are put forward. Afterwards, we construct a two-stage MADM approach by means of DHFGs for addressing complicated MADM situations with correlations and prioritization relationships. At last, a realistic case study along with a comparative analysis is presented to show the applicability of the established methodology. The proposed model and approach are conducive to addressing DHF MADM problems that are characterized by correlations and prioritization relationships between attributes at the same time, and further enrich the family of DHF MADM methods to a large extent.