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

Sep 8, 2026

Topology-induced Operators Reveal Complementary Graph Representations without Training

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.

Meng Qin, Jinqiang Cui, Hongwei Zheng +2

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

Ask PDF

Feb 26, 2026

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

Edge classification on directed dynamic graphs is critical for understanding evolving user-item interactions and behavioral patterns in recommender systems and social platforms. Existing dynamic graph architectures typically process these interactions using shared parameters for nodes with semantically distinct roles, including source, destination, query, and neighbor. While abundant supervision in tasks such as link prediction provides sufficient gradient signal for models to implicitly deduce role semantics and overcome this conflation, there are often far fewer labels available for edge classification. We hypothesize that in such regimes, the ability of models to implicitly separate roles is restricted, degrading downstream performance. To empirically investigate this relationship, we introduce an experimental framework for sequence-based models that explicitly disentangles functional roles using targeted embeddings and an asymmetric pretraining objective. By providing architectural priors for these roles, the framework serves as an evaluative vehicle to isolate and measure the resulting performance delta across a range of label budgets. Our empirical evaluation demonstrates that this explicit role disentanglement yields substantial and consistent relative performance gains over baselines. Furthermore, representational analyses reveal that the mechanism by which the framework provides these benefits is a bifurcation of source and destination latent spaces that improves linear separability.

Tyler Bonnet, Marek Rei

Imperial College London

Graph Representation Learning Self-Supervised Pre-Training Dynamic Graph Learning Graph Transformer

Ask PDF

Apr 10, 2026

NOMAD: Generating Embeddings for Massive Distributed Graphs

Successful machine learning on graphs or networks requires embeddings that not only represent nodes and edges as low-dimensional vectors but also preserve the graph structure. Established methods for generating embeddings require flexible exploration of the entire graph through repeated use of random walks that capture graph structure with samples of nodes and edges. These methods create scalability challenges for massive graphs with millions-to-billions of edges because single-node solutions have inadequate memory and processing capabilities. We present NOMAD, a distributed-memory graph embedding framework using the Message Passing Interface (MPI) for distributed graphs. NOMAD implements proximity-based models proposed in the widely popular LINE (Large-scale Information Network Embedding) algorithm. We propose several practical trade-offs to improve the scalability and communication overheads confronted by irregular and distributed graph embedding methods, catering to massive-scale graphs arising in web and science domains. NOMAD demonstrates median speedups of 10/100x on CPU-based NERSC Perlmutter cluster relative to the popular reference implementations of multi-threaded LINE and node2vec, 35-76x over distributed PBG, and competitive embedding quality relative to LINE, node2vec, and GraphVite, while yielding 12-370x end-to-end speedups on real-world graphs.

Aishwarya Sarkar, Sayan Ghosh, Nathan R. Tallent +1

Graph Embedding

Ask PDF

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