Standard Graph Neural Networks (GNNs) process graph data through neighborhood aggregation: each node updates its state by collecting and summarizing features from its immediate neighbors. While computationally efficient, this local message-passing paradigm has a fundamental theoretical blind spot. As established by Vijay Prakash Dwivedi et al. in Benchmarking Graph Neural Networks, standard message passing is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test.
This means standard GNNs are structurally "blind" to certain topological features. For example, if a node aggregates messages from three neighbors, it cannot distinguish whether those neighbors are completely isolated from one another or if they form a closed triangle. Because local neighborhood aggregation flattens structural relationships into a simple multiset of features, critical topological patterns—such as cycles, cliques, and hollow voids—are completely lost.
To overcome this limitation, a rapidly growing body of research focuses on enhancing the topological expressivity of graph architectures. Rather than simply aggregating local neighborhoods, these approaches explicitly capture higher-order structural relationships, allowing models to provably break through the 1-WL hierarchy.
Lifting Graphs to Higher-Order Complexes
One of the most direct ways to fix the blind spot of message passing is to change the underlying representation of the graph itself. Instead of treating a graph strictly as a collection of pairwise relationships (nodes and edges), we can "lift" it into a higher-dimensional topological space.
Theodore Papamarkou et al. formalize this perspective in Position: Topological Deep Learning is the New Frontier for Relational Learning. By transitioning to simplicial complexes or regular cell complexes, models can explicitly represent multi-way interactions. For instance, a triangle of three nodes is no longer just three edges; it is filled in and treated as a distinct 2-dimensional "cell."
This structural lifting enables hierarchical message passing. In CW Networks (CWNs), introduced by Cristian Bodnar et al. in Weisfeiler and Lehman Go Cellular: CW Networks, messages flow not just between adjacent nodes, but up and down the cellular hierarchy (from nodes to edges, and edges to cells). This allows the network to natively identify molecular rings and loops, achieving an expressivity level that matches or exceeds higher-order WL tests. To preserve the orientation of these interactions, the authors of Higher-Order Topological Directionality and Directed Simplicial Neural Networks extend this framework to directed simplicial complexes, ensuring that vertex ordering and directional flows are preserved in higher dimensions.
Alternatively, graphs can be lifted into hypergraphs, where a single hyperedge can encapsulate an arbitrary number of nodes. Raphaël Pellegrin et al. demonstrate in Higher-Order Learning with Graph Neural Networks via Hypergraph Encodings that incorporating hypergraph-level structural fingerprints allows standard GNNs to easily distinguish complex, non-isomorphic structures that appear identical to traditional 1-WL algorithms.
Tracking Paths, Cycles, and Flows
If lifting a graph into a complex is a structural solution, an alternative algorithmic solution is to track how information traverses the graph. While a static neighborhood looks identical regardless of whether it belongs to a tree or a cycle, the behavior of a walk or a flow through those structures is completely different.
Consider a random walk. If a graph contains a cycle, a random walk will frequently return to its origin or generate specific repeating sequences. Jan Tönshoff et al. leverage this intuition in Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing by abandoning neighborhood aggregation entirely in favor of 1D convolutions over random walks. Because sequence-based processing inherently preserves the order of traversal, it provides a fundamentally different lens for perceiving graph topology that breaks out of the standard WL hierarchy. This concept is extended to higher-order structures by Florian Frantzen et al. in Learning From Simplicial Data Based on Random Walks and 1D Convolutions, where random walks are sampled across simplices to capture topological patterns that traditional message passing misses.
Another way to track paths is to maintain node identities during message passing. In Building powerful and equivariant graph neural networks with structural message-passing, Clement Vignac et al. introduce matrix-based messages that track node identities. By knowing exactly where a message originated and where it has traveled, the framework can explicitly count walks and paths, allowing it to detect cycles without requiring computationally heavy higher-order tensors.
We can also use algebraic topology to explicitly encode the cycle space. Zuoyu Yan et al. introduce CycleNet in Cycle Invariant Positional Encoding for Graph Representation Learning, utilizing Hodge theory and orthogonal projectors to encode the specific role each edge plays within the graph's cycle space. This allows the model to distinguish non-isomorphic graphs that are identical even to 3-WL and 4-WL tests. Similarly, Yun Young Choi et al. propose the Topology-Informed Graph Transformer, which integrates clique adjacency matrices and dual-path message passing to inject cycle awareness directly into attention mechanisms.
Even the physical constraints of information flow can reveal topology. Pascal Plettenberg et al. demonstrate in Flow-Attentional Graph Neural Networks that architecturally enforcing Kirchhoff’s conservation laws—forcing messages to split and conserve mass across branches—makes the model highly sensitive to the specific branching factors and connectivity of the graph, separating structures that standard attention mechanisms conflate.
Global Shape via Persistent Homology
While local and structural enhancements help capture nearby cycles, they struggle with global, macro-level shape properties—such as a massive loop that spans across an entire graph. To capture multi-scale global structures, researchers turn to persistent homology (PH).
Imagine growing a solid ball around every node in a graph. As the radius of these balls increases, they begin to overlap, forming continuous shapes. During this process, topological features like holes (cycles) will appear ("birth") and eventually fill in and disappear ("death"). Recording the birth and death of these features across multiple scales yields a coordinate-free signature of the graph's global shape, known as a persistence diagram.
Max Horn et al. integrate this into deep learning with TOGL (Topological Graph Neural Networks), a differentiable layer that computes persistent homology on the fly. By explicitly encoding global shape information, the architecture bypasses the theoretical limitations of local message passing.
The mathematical foundation of this approach is rigorously mapped out by Rubén Ballester et al. in On the Expressivity of Persistent Homology in Graph Learning. They prove that persistent homology is at least as expressive as the Weisfeiler-Lehman hierarchy, and strictly more expressive in scenarios where global topological features are completely invisible to local WL neighborhood tests.
Subgraph Modeling and Expressive Pooling
A final avenue for boosting expressivity involves modifying the graph's architecture through explicit subgraph modeling or structural downsampling.
Instead of relying on standard neighborhood aggregation, Xuexin Chen et al. propose the Motif Graph Neural Network (MGNN). MGNN explicitly extracts small subgraphs (motifs), distills unique features through a redundancy minimization operator, and combines them injectively to ensure no structural information is lost during learning.
When a graph needs to be coarsened, pooling layers are traditionally designed purely for computational efficiency. However, Veronica Lachi et al. prove in Expressive Pooling for Graph Neural Networks that node selection during pooling can actively increase expressive power. By selecting nodes based on whether they belong to higher-order structural motifs like cliques or cycles, the coarsened graph can preserve topological features that would otherwise be erased. This concept is put into practice by Jonas Jürß et al. in Everybody Needs a Little HELP: Explaining Graphs via Hierarchical Concepts, which integrates connected component analysis into the pooling process to identify global topological differences that are completely equivalent under standard 1-WL tests.
Remarkably, even simple architectural modifications can simulate higher-order reasoning. Xin Liu et al. show in Boosting Graph Structure Learning with Dummy Nodes that adding a single "dummy node" connected to every vertex creates a lossless transformation. This universal hub allows standard message passing to simulate higher-order WL tests, dramatically expanding the network's capacity to distinguish complex topological patterns. Having this high representational capacity is vital for complex downstream tasks; for instance, Karolis Martinkus et al. demonstrate in Diffusion Models for Graphs Benefit From Discrete State Spaces that provably powerful graph networks are necessary to accurately predict clean graph structures from noisy inputs in generative diffusion models.
Key Foundational Work
Motif Graph Neural Network (2021) — contributed 1 concept elements to this direction.
Building powerful and equivariant graph neural networks with structural message-passing (2020) — contributed 1 concept elements to this direction.
Weisfeiler and Lehman Go Cellular: CW Networks (2021) — contributed 1 concept elements to this direction.