Abstract: Interval-valued hesitant fuzzy sets are generalizations of interval numbers and hesitant fuzzy sets, which are usually used to depict the incompleteness and hesitancy in uncertain information. In recent years, interval-valued hesitant fuzzy multi-attribute decision making problems have received extensive attentions of scholars. In allusion to interval-valued hesitant fuzzy multi-attribute decision making problems that are possessed with correlations and prioritization relationships between attributes at the same time, by taking advantages of fuzzy graphs could represent the correlations between attributes through edges between vertices, this paper studies multi-attribute decision making approaches based on interval-valued hesitant fuzzy graphs. Firstly, the related notion of interval-valued hesitant fuzzy graphs is established from the aspect of definitions, operation rules and mapping relationships. Based on the constructed notion, an approach to interval-valued hesitant fuzzy graphs in multi-attribute decision making with correlations and prioritization relationships is proposed. At last, a case study along with a comparative analysis is given to illustrate the feasibility and efficiency of the proposed multi-attribute decision making approach. Compared with classical interval-valued hesitant fuzzy multi-attribute decision making approaches, the results show that the proposed approach could reasonably solve interval-valued hesitant fuzzy multi-attribute decision making problems that are characterized by correlations and prioritization relationships between attributes at the same time.