In modern smart cities, the scale of urban backbone networks used to provide Internet communication environment are constantly increasing. When faults occur, it usually takes lots of efforts to detect and locate the faults. As a result, automatic detection and positioning of faults with use of intelligent algorithms have been a practical demand in this area. In this paper, the complicated whole urban backbone network is viewed as a graph-level object, in which massive nodes and edges are involved. On this basis, a two-stage graph deep learning-based fault detection and positioning method for Internet communication networks. For the first stage, the graph neural network is employed to extract graph-level features from Internet communication networks. This is expected to obtain proper feature representation for core characteristics of backbone networks. For the second stage, the fault detection and positioning algorithm is formulated to output final results. At last, experiments are conducted to assess performance of the proposal. The results show that the proposed method has good performance in abnormal node detection as well as high accuracy in fault positioning. The accuracy of the two-stage graph deep learning algorithm proposed in this chapter is much higher than that of KNN algorithm, reaching 96.5% in the end, slightly lower than that of pure graph deep learning algorithm, while the accuracy of IRBFG algorithm can only reach 92%.