Graph Neural Networks (GNNs) have achieved remarkable success in fields ranging from drug discovery to social network analysis. However, for years, their success was largely empirical. A growing body of research has sought to move beyond "black-box" intuition to establish a formal theory of what GNNs can actually compute, what they can see, and where they fundamentally fail.
The Weisfeiler-Lehman Ceiling
The foundational framework for understanding GNN expressivity is the Weisfeiler-Lehman (WL) test, a classical algorithm for checking graph isomorphism. The 1-WL test works by "color refinement": nodes iteratively aggregate the colors of their neighbors until the distribution of colors stabilizes. If two graphs result in different color distributions, they are definitely not isomorphic.
In a seminal proof, Keyulu Xu, Jure Leskovec, and colleagues demonstrated in How Powerful are Graph Neural Networks? that standard message-passing GNNs are at most as powerful as the 1-WL test. They introduced the Graph Isomorphism Network (GIN), proving that if the aggregation and update functions are injective (meaning they map distinct inputs to distinct outputs), the GNN reaches this 1-WL upper bound.
However, 1-WL is not perfect; it fails to distinguish even simple structures like a graph of two triangles versus one hexagon. To break this "ceiling," Christopher Morris, Matthias Fey, and others proposed $k$-GNNs in Weisfeiler and Leman Go Neural. These models perform message passing between subgraphs of size $k$ rather than individual nodes, matching the power of higher-order $k$-WL tests.
GNNs as Logical Reasoners
If the WL test tells us which graphs a GNN can distinguish, mathematical logic tells us what properties a GNN can describe. Researchers have established a rigorous correspondence between GNN architectures and formal logic languages.
For instance, Martin Grohe has explored how GNNs relate to first-order logic with counting. More specifically, David Jaime Tena Cucala and Boris Motik proved in On the Correspondence Between Monotonic Max-Sum GNNs and Datalog that certain GNNs are mathematically equivalent to Datalog, a logic language used in databases. This means a GNN can be viewed as a set of recursive rules, making them potentially verifiable and explainable.
Further extending this, Damian Heiman and Antti Kuusisto showed in Graph neural networks and MSO that recurrent GNNs can capture the expressive power of Monadic Second-Order logic (MSO) over node properties. This bridge allows researchers to use the tools of descriptive complexity to determine the minimum resources—like formula size or depth—required for a GNN to solve a specific task, as explored by György Turán in A Game for Counting Logic Formula Size.
Permutation Compatibility and Universal Approximation
While the WL test focuses on discrete structures, GNNs are continuous function approximators. What is the exact class of functions a GNN can represent?
Mohammad Fereydounian, Hamed Hassani, and Amin Karbasi identified a definitive algebraic condition called permutation compatibility in The Exact Class of Graph Functions Generated by Graph Neural Networks. Because nodes in a graph have no inherent order, any function a GNN learns must be invariant to how we label those nodes. They proved that GNNs are exactly the class of functions that satisfy this condition.
Crucially, they also showed that by adding "node individualization"—such as unique IDs or random features—GNNs can overcome the 1-WL limit and approximate any graph function, effectively becoming universal. This is echoed by Arie Soeteman and Balder ten Cate, who introduced Hierarchical Ego GNNs (HE-GNNs) in Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization, using recursive node marking to reach the power of Graded Hybrid Logic.
The Secret to Link Prediction
A major gap in GNN theory was the transition from node-level tasks to link prediction (predicting relationships between pairs of nodes). Standard GNNs often struggle here because they compute node representations independently of the target pair.
In A Theory of Link Prediction via Relational Weisfeiler-Leman, Xingyue Huang, Ismail Ilkan Ceylan, and Pablo Barcelo proved that the secret to high-performance link prediction is Conditional Message Passing (C-MPNNs). By conditioning the message passing on the source node of a potential link, the model can compute pairwise representations that are far more expressive than simple node-embedding concatenations. This theoretical insight explains the success of the "Entity Labeling" trick used in state-of-the-art knowledge graph reasoning models, as noted by Haiquan Qiu and Quanming Yao in Understanding Expressivity of GNN in Rule Learning.
Geometry and Activations
Finally, the "intelligence" of a GNN is not just in its topology, but in its calculus. Pablo Barcelo and Matthias Lanzinger demonstrated in A Logical View of GNN-Style Computation that the choice of activation function is critical. GNNs using ReLU are strictly more powerful than those using bounded activations (like Sigmoid) because ReLU allows the model to exploit the interaction between linear layers and unbounded growth to count and distinguish complex features.
From a geometric perspective, Tuan Anh Pham and Vikas K. Garg used tropical geometry in What do Graph Neural Networks learn? to show that while GNNs learn piecewise linear maps, the choice of aggregation matters immensely: coordinate-wise max aggregation provides significantly higher geometric complexity than simple summation. This explains why deeper GCNs can represent exponentially more "linear regions" than shallow ones, as proved by Hao Chen and Huan Xiong in Lower and Upper Bounds for Numbers of Linear Regions.