Predictive Maintenance (PdM) has continually attracted interest from the manufacturing community due to its significant potential in reducing unexpected machine downtime and related cost. Much attention to existing PdM research has been paid to perceiving the fault, while the identification and estimation processes are affected by many factors. Many existing approaches have not been able to manage the existing knowledge effectively for reasoning the causal relationship of fault. Meanwhile, complete correlation analysis of identified faults and the corresponding root causes is often missing. To address this problem, graph-based approaches (GbA) with cognitive intelligence are proposed, because the GbA are superior in semantic causal inference, heterogeneous association, and visualized explanation. In addition, GbA can achieve promising performance on PdM's perception tasks by revealing the dependency relationship among parts/components of the equipment. However, despite its advantages, few papers discuss cognitive inference in PdM, let alone GbA. Aiming to fill this gap, this paper concentrates on GbA, and carries out a comprehensive survey organized by the sequential stages in PdM, i. e., anomaly detection, diagnosis, prognosis, and maintenance decision-making. Firstly, GbA and their corresponding graph construction methods are introduced. Secondly, the implementation strategies and instances of GbA in PdM are presented. Finally, challenges and future works toward cognitive PdM are proposed. It is hoped that this work can provide a fundamental basis for researchers and industrial practitioners in adopting GbAbased PdM, and initiate several future research directions to achieve the cognitive PdM.