RoleWalk: training-free structural embeddings for directed graphs that transfer across graphs

Maixent Chenebaux

cs.LGNov 6, 2026

RoleWalk: training-free structural embeddings for directed graphs that transfer across graphs

Authors: Maixent Chenebaux

Organizations: Trickstr

Abstract

Structural role embeddings describe a node by its position in a graph - hub, bridge, periphery, member of a dense core - rather than by who its neighbours are. Existing methods either learn coordinates specific to one graph (struc2vec, Role2Vec, RESD) or read scales and normalisations from the whole graph (GraphWave, Digraphwave), so the same neighbourhood can receive different coordinates in two graphs; few read edge directions. We present RoleWalk, a training-free embedding that follows a short lazy random walk from each node and records, at each step, two distributions: that of the transition probabilities, through its characteristic function at a fixed grid of frequencies, and that of the walker's distance to its starting node. On directed graphs, walks that go forward then backward add who shares a node's targets or sources. The embedding depends only on a node's neighbourhood within a fixed radius, so its coordinates mean the same thing in every graph. We show that, without curvature, it is the kernel mean embedding of the walk's footprint, that it separates graphs that the Weisfeiler-Leman test cannot, and that pruning small probabilities comes with a per-node error certificate. Empirically, RoleWalk is competitive with the best role embeddings on five classification benchmarks at a fraction of their cost, has the highest scores on real directed roles in Wikipedia adminship, exceeds the published accuracy of Digraphwave at every noise level of its own Enron network-alignment benchmark, transfers centrality predictors to graphs four times larger better than existing inductive embeddings, hand-made features and a trained GIN, and embeds a million nodes in 20 s to 3 min on one CPU core. The code is open source (BSD license): https://github.com/kerighan/rolewalk

Figures & tables

Figure 1: Structural roles on eight houses attached to a cycle, the setting of GraphWave [ 4 ] . (a) Nodes coloured by

k

-means (

k=7

) on default RoleWalk embeddings; colours are matched to the seven true roles, and every node lands in its role’s cluster. Far-apart copies of the same position get the same coordinates. (b) First two principal components of the standardised embeddings, coloured by true role; nodes in the same role coincide exactly, and a small jitter is added to show them.

Figure 2: RoleWalk on one node

u

of Zachary’s karate club. (a) The three-step walk from

u

never leaves the ball of radius 3, drawn by onion layer (distance to

u

); node size is the probability of the walker being there after three steps. At each step

w

, RoleWalk reads two laws of the same walk, in parallel. (b) The multiset of its probabilities (grey: their location is ignored) gives the real and imaginary parts of the characteristic function

\phi^{w}_{u}

at ten frequencies (shade: magnitude, scaled per block). (c) The law of its distance to

u

, the mass in each onion layer, gives

w+1

coordinates scaled by

\lVert\Theta\rVert

	Brazil	Europe	USA	Reality-call	Actor	Time (USA)
RoleWalk	0.743	0.583	0.657	0.860	0.487	0.2 s
RoleWalk + curvature	0.741	0.596	0.666	0.860	0.485	0.2 s
struc2vec	0.705 $\pm$ .022	0.561 $\pm$ .020	0.596 $\pm$ .004	–	–	564 s
GraphWave	0.769	0.561	0.587	0.860	0.481	18 s
RESD	0.728	0.544	0.653	0.857	0.476	8 s
Role2Vec	0.476	0.366	0.562	0.844	0.399	10 s

Table 1: Role classification accuracy (mean over 50 splits; struc2vec: mean

\pm

std over 5 unseeded runs; “–”: too slow or out of memory). Time: embedding the USA network (1,190 nodes), one core.

Figure 3: Accuracy against embedding time (one core, log scale). Airports: mean of the three networks. Directed motifs: synthetic directed roles with 5% of edges rewired. wiki-RfA: task A of Table 2 . Hollow marker: degree, a trivial baseline.

	A: elected	B: 3 classes	Time
RoleWalk + curvature	0.827	0.944	7 s
RoleWalk	0.814	0.940	7 s
RoleWalk, no mixed probes	0.808	0.938	4 s
Digraphwave	0.807	0.939	360 s
ReFeX, directed	0.778	0.930	3 s
ReFeX	0.794	0.847	1 s

Table 2: Real directed roles: wiki-RfA (11,377 users). A: elected among the 3,494 candidates (accuracy). B: voter, failed candidate or admin (accuracy). Time: one core.

$p$	0	0.01	0.02	0.05	0.075	0.1
RoleWalk	0.487	0.406	0.356	0.235	0.172	0.125
characteristic function only (no layers)	0.520	0.436	0.379	0.253	0.189	0.142
without mixed probes	0.442	0.363	0.316	0.198	0.140	0.097
top- $k$ + layers, without mixed probes	0.369	0.287	0.227	0.114	0.065	0.038
layers only	0.268	0.206	0.169	0.086	0.053	0.031
Local statistics (in / out)	0.427	0.372	0.332	0.249	0.207	0.176

Table 3: Network alignment on the Enron protocol of Digraphwave [ 3 ] (directed, unweighted): top-1 accuracy of matching the internal subgraph to the full email graph, with a share

p

of random edges added; mean of 5 noise draws, the same for every row computed here (one deterministic run without noise). ∗ Published results of [ 3 ] ; our rerun of Digraphwave reproduces them (text).

	RoleWalk	Local stats	ReFeX (frozen)	RW heat CF	GIN	RWSE	GraphWave ‡	Degree
Betweenness	0.864	0.852	0.845	0.849	0.778	0.412	0.659	0.623
Closeness	0.797	0.716	0.725	0.738	0.695	0.464	0.529	0.407
Harmonic	0.861	0.778	0.788	0.806	0.756	0.517	0.597	0.460
PageRank	0.989	0.984	0.973	0.986	0.982	0.741	0.611	0.929
Clustering	0.805	0.844 †	0.813 †	0.785	0.387	0.723	0.347	0.201
$k$ -core	0.651	0.650	0.631	0.647	0.604	0.494	0.594	0.614

Table 4: Centrality transfer to graphs four times larger (Spearman). Table means average the 400 valid graph–target cells of the 60 independent pairs of graphs (20 cells with a constant

k

-core are left out); paired differences in the text first average the valid targets within each pair, then the pairs. † The clustering coefficient is itself one of the features of the local statistics and of ReFeX. ‡ Without its

1/n

factor. GIN: trained on the training graph (log-degree input).

Nodes	10k	30k	100k	300k	1M
Barabási–Albert ( $m=3$ )	0.5 s	1.8 s	8.9 s	43 s	193 s
+ curvature	0.6 s	1.9 s	11 s	52 s	247 s
Watts–Strogatz ( $k=6$ )	0.1 s	0.5 s	1.8 s	5.1 s	18 s

Table 5: Embedding time on one core (defaults:

\mathrm{tol}=10^{-4}

without budget; one run after compiling the kernel; including the conversion of the networkx graph).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

	Acc. 0%	Acc. 5%	Acc. 10%	ARI 5%	mAP 5%
RoleWalk + curvature	1.000	0.730	0.593	0.396	0.629
RoleWalk	1.000	0.728	0.588	0.373	0.615
ReFeX, directed	1.000	0.756	0.638	0.355	0.607
Digraphwave	1.000	0.717	0.575	0.292	0.539
Local statistics (in / out)	0.863	0.675	0.584	0.409	0.609
GraphWave	0.586	0.388	0.383	0.317	0.416

Appendix

Table 6: Synthetic directed roles (motifs hung from a directed cycle; 3 seeds; noise: share of edges rewired). Accuracy: logistic regression; ARI:

k

-means; mAP: retrieval.

	RoleWalk	Local stats	ReFeX (frozen)	RW heat CF	GraphWave
Betweenness	0.614	0.742	0.701	0.614	0.619
Closeness	0.720	0.618	0.597	0.599	0.490
Harmonic	0.750	0.657	0.624	0.663	0.567
PageRank	0.893	0.923	0.831	0.677	0.878
Clustering	0.639	0.959 †	0.759 †	0.539	0.040
$k$ -core	$-0.017$	0.134	0.018	$-0.065$	0.235

Appendix

Table 7: Centrality transfer under a change of generator parameter (Barabási–Albert

m=3\to 5

, powerlaw-cluster triangle probability

0.3\to 0.6

, Watts–Strogatz rewiring

0.1\to 0.3

, SBM within-block probabilities

\times 2

, random geometric radius

0.04\to 0.06

; 50 pairs). † A feature of these methods.

Graph	Setting	Time	Median	Worst	Cert. max
Barabási–Albert 50k	exact	3.8 s	0.0%	0.0%	–
	$\mathrm{tol}=10^{-4}$	3.0 s	1.3%	22.4%	188
	$\mathrm{tol}=10^{-4}$ , $\delta=0.01$	3.6 s	0.0%	0.7%	4
Directed scale-free 50k	exact	38.2 s	0.0%	0.0%	–
	$\mathrm{tol}=10^{-4}$	7.8 s	0.6%	44.9%	414
	$\mathrm{tol}=10^{-4}$ , $\delta=0.01$	43.1 s	0.0%	0.6%	3

Appendix

Table 8: Certified pruning on 50k-node graphs and wiki-RfA (one core): time, relative error of each node’s embedding against exact computation (median and worst node), and largest per-node certificate.

Graph Embedding

Graph embedding maps nodes, edges, or whole graphs into vectors that capture structure for prediction, clustering, retrieval, and analysis.

See all 54 papers

Topology-induced Operators Reveal Complementary Graph Representations without Training
Sep 8, 2026Meng Qin, Jinqiang Cui, Hongwei Zheng +2Graph Representation Learning Graph Embedding
Department of Strategic & Advanced Interdisciplinary Research, Pengcheng Laboratory (PCL), Shenzhen, Guangdong, China. · Beijing Academy of Blockchain and Edge Computing, Beijing, China. · LMIB, NLSDE, and School of Artificial Intelligence, Beihang University, Beijing, China. +1
An Analysis of Role Semantics in Directed Dynamic Graph Modeling for Edge Classification
Feb 26, 2026Tyler Bonnet, Marek ReiGraph Representation Learning Self-Supervised Pre-Training
Imperial College London
NOMAD: Generating Embeddings for Massive Distributed Graphs
Apr 10, 2026Aishwarya Sarkar, Sayan Ghosh, Nathan R. Tallent +1Graph Embedding

Sep 8, 2026J/K move · Enter open · S save

Topology-induced Operators Reveal Complementary Graph Representations without Training

Meng Qin, Jinqiang Cui, Hongwei Zheng, Weihua Li+1

Department of Strategic & Advanced Interdisciplinary Research, Pengcheng Laboratory (PCL), Shenzhen, Guangdong, China. · Beijing Academy of Blockchain and Edge Computing, Beijing, China. · LMIB, NLSDE, and School of Artificial Intelligence, Beihang University, Beijing, China.+1

Graph Representation Learning Graph Embedding Topological Representation Learning

Open paper AskPDF arXiv

Graph representation learning has largely focused on designing increasingly sophisticated models to transform graph topology into vector representations, or embeddings. However, the extent to which embedding quality depends on model learning, rather than on the underlying topological transformations, remains unclear. Here, we show that informative embeddings can be derived without complicated model design and gradient-based training. Propagating random features through implicit hierarchical structures induced by random walks and anonymous walks yields embeddings that capture node proximity and structural role, respectively. These two training-free embeddings preserve complementary aspects of graph organization and perform competitively with classic and recent methods across various node-, edge-, and graph-level tasks. They often require substantially less computation, resulting in a favorable quality-efficiency trade-off. Combining the two types of embeddings further improves inference quality of some tasks compared with using either embedding type alone. Our results suggest that informative graph embeddings can arise from carefully chosen topological transformations before any learning operation is applied.

Abstract

Graph Embedding

Explore similar work

Topology-induced Operators Reveal Complementary Graph Representations without Training

An Analysis of Role Semantics in Directed Dynamic Graph Modeling for Edge Classification

NOMAD: Generating Embeddings for Massive Distributed Graphs