Standard Graph Neural Networks (GNNs) typically rely on Message Passing, where nodes aggregate features from their immediate neighbors. While effective, this paradigm has a fundamental "blind spot": it struggles to distinguish between different local structural shapes. A node in the center of a tight-knit triangle and a node in the middle of a loose chain might look identical to a message-passing model if their neighbors have similar features.
To fix this, researchers have developed a technique that strips away specific node identities to focus purely on the "shape" of the graph. By representing local neighborhoods as Anonymous Walks, models can capture complex topological motifs—like cliques, cycles, and stars—independently of the specific entities involved.
The Intuition: Identity vs. Role
Imagine walking through a city. If you record your path using street names ("Main St," "Oak St," "Main St"), your record is tied to a specific location. If you instead record your path using the order in which you discovered each street ("Street 1," "Street 2," "Street 1"), you create a template. This template—the Anonymous Walk—describes a specific movement pattern: you went somewhere new, then returned to where you started.
In graph learning, Sergey Ivanov and Evgeny Burnaev formalized this in Anonymous Walk Embeddings (AWE). They proposed replacing global node identifiers with an index representing the node's first appearance in a sequence. For example, a walk across nodes $A \rightarrow B \rightarrow A \rightarrow C$ becomes the anonymous sequence $1 \rightarrow 2 \rightarrow 1 \rightarrow 3$.
This simple transformation provides two massive advantages:
- Isomorphism Invariance: Two identical graph structures will produce the same set of anonymous walks, regardless of how the nodes are labeled.
- Structural Awareness: The distribution of these walks acts as a fingerprint for local topology. A high frequency of the pattern $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ directly indicates the presence of triangles.
Capturing Local "Topics" and Shapes
Building on this, Yilun Jin and Guojie Song introduced GraLSP (2019, 2020), which incorporates these anonymous patterns directly into the GNN aggregation process. Instead of just averaging neighbor features, the model "sees" the geometric shape of the neighborhood.
This approach was extended in GraphSTONE (Qingqing Long et al., 2020), which treats these structural patterns like "topics" in a document. Just as a document is a distribution of words, a node's structural identity is a distribution of anonymous walks. This allows the model to recognize recurring motifs—like the specific connectivity of a molecule or a social clique—without needing to perform expensive subgraph isomorphism tests.
From Transductive to Inductive Learning
One of the most significant breakthroughs of anonymous walks is their ability to handle Inductive Learning—making predictions on nodes or graphs the model has never seen before.
Traditional models often struggle when moving from a training graph to a test graph because the node IDs change. However, as Ali Behrouz and Margo I. Seltzer demonstrate in ADMire, by focusing exclusively on the structural and temporal patterns of sampled paths, a model can generalize to entirely new subjects (such as new patients in a brain activity study).
This concept is central to the development of Knowledge Graph Foundation Models like Flock (Jinwoo Kim et al., 2025). By anonymizing both entities and relations into discovery-order sequences, Flock can perform "zero-shot" link prediction. It can predict a relationship in a graph it has never seen, involving entities it wasn't trained on, simply by recognizing that the structural role of the entities matches patterns it learned elsewhere.
Surpassing the Limits of Message Passing
Theoretically, anonymous walks offer a path out of the "expressivity ceiling" of standard GNNs. Most GNNs are limited by the 1-Weisfeiler-Lehman (1-WL) test, meaning they cannot distinguish certain non-isomorphic graphs.
However, architectures like GSKN (Long et al., 2021) and RUM (Yuanqing Wang and Kyunghyun Cho, 2024) prove that using anonymous walks allows models to be provably more powerful than the 1-WL test. Because these walks can capture cycles and local diameters that message passing misses, they are more robust to noise and less prone to "over-smoothing"—the tendency of GNNs to make all node representations look the same after a few layers.
Graphs as Sequences for LLMs
The most recent shift in this field involves treating these anonymous sequences as a "language" that can be read by standard sequence models like Transformers or Large Language Models (LLMs).
In Revisiting Random Walks for Learning on Graphs, Jinwoo Kim and colleagues show that simply anonymizing walk records allows general-purpose sequence models to process graph structures effectively. This removes the need for specialized equivariant architectures. Similarly, ReaL-TG fine-tunes LLMs to predict future links by representing nodes as anonymous numerical identifiers, forcing the model to develop generalizable reasoning about how things connect, rather than memorizing who is connecting.