In this article, we propose a novel and effective incomplete multi-view clustering (IMVC) framework, referred to as incomplete multi-view clustering with regularized hierarchical graph (IMVC-RHG). Different from the existing graph learning-based IMVC methods, IMVC-RHG introduces a novel heterogeneous-graph learning and embedding strategy, which adopts the high-order structures between four tuples for each view, rather than a simple paired-sample intrinsic structure. Besides this, with the aid of the learned heterogeneous graphs, a between-view preserving strategy is designed to recover the incomplete graph for each view. Finally, a consensus representation for each sample is gained with a co-regularization term for final clustering. As a result of integrating these three learning strategies, IMVC-RHG can be flexibly applied to different types of IMVC tasks. Comparing with the other state-of-the-art methods, the proposed IMVC-RHG can achieve the best performances on real-world incomplete multi-view databases.