Currently, many High Efficiency Video Coding (HEVC) video steganography algorithms based on Intra Prediction Mode (IPM) have been proposed. However, the existing IPM-based video steganalysis algorithms are almost designed for H.264/AVC videos, without considering the unique coding techniques in HEVC, which is the latest video codec standard. Thus, it is of significant value to study IPM-based steganalysis for HEVC videos. In this paper, the general process of IPM-based HEVC steganography is modelled for the first time, and we find that the basic distortion existing in the change of the relationships between each embedded IPM and the adjacent IPMs. By exploiting these weaknesses, we propose a novel IPM steganalysis algorithm based on the Relationship of Adjacent IPMs (RoAIPM) feature. In detail, the RoAIPM is extracted by generating different directional Gray-Level Co-occurrence Matrixes (GLCMs) and texture characteristics of three refilled matrixes: MPM-IPM matrix, Left-IPM matrix and Up-IPM matrix. Experimental results show that, the proposed RoAIPM feature is very sensitive to the little change introduced by IPM-based steganography. Regardless of whether the feature is after dimension reduction or not, in various coding conditions, the proposed steganalysis can both present a well higher detection accuracy against the latest IPM-based HEVC steganography methods and achieve the lowest computational complexity compared with the state-of-the-art works.