Most modern Graph Neural Networks (GNNs) share a common engine: message passing. In this paradigm, nodes update their representations by aggregating features from their immediate neighbors. While intuitive and scalable, this mechanism has a fundamental theoretical ceiling. As established by Keyulu Xu, Jure Leskovec, and Weihua Hu in How Powerful are Graph Neural Networks?, these models are at most as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) test, a classical algorithm for graph isomorphism.
This means that if the 1-WL test cannot distinguish between two different graph structures, a standard GNN cannot either—no matter how many layers or parameters it has. This "expressivity bottleneck" prevents models from detecting critical motifs like triangles, cycles, or rings, which are essential for understanding molecular chemistry and social network dynamics.
The 1-WL Bottleneck
The 1-WL test works by iteratively refining node labels based on the labels of their neighbors. If two graphs result in the same set of labels, they are considered potentially isomorphic. However, 1-WL is "blind" to certain structures. For example, it cannot distinguish a graph composed of two disjoint triangles from a graph composed of a single six-node cycle.
Because standard GNNs mimic this local aggregation, they inherit this blindness. As noted by Maosong Sun and Ganqu Cui in their comprehensive review, this limitation is not just theoretical; it leads to practical failures in tasks like counting subgraphs or predicting the properties of complex chemical isomers.
Scaling Up to Higher-Order Structures
To break the 1-WL barrier, researchers have moved toward higher-order GNNs. Instead of passing messages between individual nodes, these models operate on subgraphs or tuples of nodes.
Christopher Morris and William L. Hamilton introduced $k$-GNNs in Weisfeiler and Leman Go Neural, which perform message passing between sets of $k$ nodes. By considering these higher-order interactions, the model becomes equivalent to the $k$-WL test, which is provably more powerful than 1-WL. While these "dense" higher-order models can be computationally expensive, Gaurav Rattan and Petra Mutzel demonstrated in Weisfeiler and Leman go sparse that local, sparse variants can maintain this expressivity while remaining scalable.
Topological Deep Learning
Another frontier involves shifting the perspective from graphs to simplicial and cell complexes. In this view, a graph is not just nodes and edges, but a collection of higher-dimensional "faces" like triangles (2-simplices) and tetrahedra (3-simplices).
Cai Zhou and Muhan Zhang proposed using random walks on simplicial complexes to capture topological "holes" and cycles that node-based GNNs miss. By using operators like the Hodge Laplacian, these models can process "flows" across edges and surfaces, providing a richer geometric understanding of the data. This is particularly useful in physical systems where data isn't just at nodes, but represents movement across a network, as explored in Topological Neural Networks over the Air.
Injecting Structural and Spatial Bias
If the architecture itself is limited, one solution is to "feed" the model the structural information it lacks. This is the philosophy behind structural encodings.
- Graph Transformers: Chengxuan Ying and colleagues showed in Do Transformers Really Perform Bad for Graph Representation? that a standard Transformer can outperform GNNs if it is equipped with spatial encodings (like shortest-path distances) and centrality encodings.
- Directional Kernels: Dominique Beaini and Saro Passaro introduced Directional Graph Networks, which use the gradients of Laplacian eigenvectors to give the network a sense of "direction," allowing for anisotropic message passing that overcomes the over-smoothing common in isotropic GNNs.
- Explicit Motif Extraction: Frameworks like CoCo, developed by Nan Yin and Li Shen, explicitly extract high-order motifs and functional groups to bridge the gap between implicit message passing and the actual structural requirements of domain-specific tasks like molecular classification.
Why Expressivity Matters
The quest to move beyond 1-WL is not merely a mathematical exercise. In drug discovery, the difference between an effective medicine and a toxic compound often lies in a specific ring structure or molecular symmetry that a 1-WL GNN cannot see. In generative modeling, as seen in DiGress, capturing the spectral properties and cycle counts of a graph is the only way to generate realistic synthetic data. By expanding the expressive power of GNNs, researchers are enabling AI to understand the complex, non-Euclidean geometry of the real world.