Graph matching endeavors to find corresponding nodes across two or more graphs, which plays a fundamental role in many vision and pattern matching tasks. However, existing graph matching algorithms often meet abnormal graphs with missing node features and suffer from numerous cluttered outliers in practical applications. To address these, we propose a novel deep graph matching method called Random Deep Graph Matching (RDGM). Different from the deterministic affinity inference in existing deep graph matching methods, RDGM performs message passing in a random manner during model training through randomly masking some available node features in the source or target graph, so that the affinity inference between nodes is insensitive to specific neighborhoods. In addition, a hierarchical attention graph neural network framework is devised in the node embedding process of RDGM, which can obtain more sufficient high-order structural information to reduce the impact of latent noise on affinity learning. Extensive experiments suggest that the proposed RDGM outperforms state-of-the-art graph matching methods, and demonstrates strong robustness and generalization performance.