01 / AI · Analysis
RoleWalk embeds one million graph nodes on a single CPU core
The question for training-free structural embeddings is less speed than whether coordinates hold across different graphs.

RoleWalk, a training-free structural embedding method for graphs, embedded one million nodes in 20 seconds to 3 minutes on one CPU core, according to author-published figures. The paper went up on arXiv on 9 Nov 2026. It said the code is open source under a BSD licence.
The paper targets a shift in coordinates. A structural embedding is a vector that describes a node by its position, such as hub, bridge or periphery, rather than by who its neighbours are. The paper said existing methods can give the same neighbourhood different coordinates in two graphs.
If the same coordinates work across graphs, a predictor built on one graph can move to another, the paper argued. That argument starts with how the coordinates are calculated.
Coordinates built from a fixed radius
According to the paper, struc2vec, Role2Vec and RESD learn coordinates tied to a single graph. GraphWave and Digraphwave read scales and normalisation values from the whole graph. Few existing methods read the direction of edges, the links between nodes.
The paper said RoleWalk starts a short random walk from each node, with a probability at each step of staying in place. It records two distributions at every step: the transition probabilities and the walker's distance to its starting node. The transition probabilities are read at a fixed grid of frequencies through a characteristic function, which moves a distribution into the frequency domain.
The embedding depends only on a node's neighbourhood within a fixed radius, so its coordinates "mean the same thing in every graph", according to the paper. On directed graphs, walks that go forward and then back add information about nodes that share targets or sources.
The paper said RoleWalk separates graphs that the Weisfeiler-Leman test cannot tell apart. That test is a standard check of whether two graphs have the same structure. Pruning small probabilities comes with an error certificate for each node.
How far the author-published figures reach
According to author-published results, RoleWalk is competitive with the best role embeddings on five classification benchmarks at a fraction of their cost. The abstract does not give the specific scores or the cost multiple.
The comparison with Digraphwave used that method's own benchmark, Enron network alignment, a task that matches the same nodes across two networks. Author-published results put RoleWalk above Digraphwave's published accuracy at every noise level. RoleWalk also had the highest scores on real directed roles in Wikipedia adminship, by the same author-published account.
The direct test of the coordinate argument was a transfer experiment for predictors of centrality, a measure of a node's importance. Moved to graphs four times larger, RoleWalk did better than existing inductive embeddings and hand-made features in author-published results. It also did better than a trained GIN, a type of graph neural network.
The paper lists the code as BSD-licensed, but the abstract does not say whether the repository reproduces the paper's figures. It also does not give the conditions that separate 20 seconds from 3 minutes. The issue the paper raises is less how fast RoleWalk runs than whether its coordinates hold from one graph to the next.