Researches have indicated that the capabilities of MP-GNNs (Message-Passing GNN) are confined within the constraints of the Weisfeiler Lehman (WL) test for graph isomorphism. This includes the notable shortcoming of MP-GNNs being unable to effectively identify and quantify substructures within the graph, which are crucial for many applications. To address the deficiencies, we introduce K-Division Graph Neural Networks, a novel message-passing framework that is designed to be able to classify different node’s neighbors. Through theoretical analysis, we have demonstrated that our architecture is strictly more powerful than WL test. Meanwhile, to understand what kinds of problem that k-div GNNs is competent to solve, we have introduced k-div GNNs’ equivalent logic language and model based on model theory to investigate k-div GNNs’ expressive power. Also we have proved that if the longest circle in graph is bounded, k-div WL is able to recognize all non-isomorphic graphs. We have conducted both synthetic and real-world experimental evaluations on tasks related to graph and node classification and regression. These results have validated our theory and demonstrated the effectiveness and practicality of our approach.