Disobeying Directions:  Switching Random Walk Filters for Unsupervised Node Embedding Learning on Directed Graphs
Authors: Ciwan Ceylan
Kambiz Ghoorchian
Danica Kragic
Venue: Accepted by TMLR ()

Abstract: Unsupervised learning of node embeddings for directed graphs (digraphs) requires careful handling to ensure unbiased modelling. This paper addresses two key challenges: (1) the obstruction of information propagation in random walk and message-passing methods due to local sinks, and (2) the representation of multiple multi-step directed neighbourhoods, arising from the distinction between in- and out-neighbours. These challenges are interconnected—local sinks can be mitigated by treating the graph as undirected, but this comes at the cost of discarding all directional information. We make two main contributions to unsupervised embedding learning for digraphs. First, we introduce ReachNEs (Reachability Node Embeddings), a general framework for analysing embedding models and diagnosing local sink behaviour on digraphs. ReachNEs defines the reachability filter, a matrix polynomial over normalized adjacency matrices that captures multi-step, direction-sensitive proximity. It unifies the analysis of message-passing and random walk models, making its insights applicable across a wide range of embedding methods. Second, we propose DirSwitch, a novel embedding model that resolves both local sink bias and neighbourhood multiplicity via switching random walks. These walks use directed edges for local steps, preserving directional structure, then switch to undirected edges for long-range transitions, enabling escape from local sinks and improving information dispersal. Empirical results on node classification benchmarks demonstrate that DirSwitch consistently outperforms state-of-the-art unsupervised digraph proximity embedding methods, and also serves as a flexible digraph extension for self-supervised graph neural networks.

Published in Transactions on Machine Learning Research (06/2025)
Disobeying Directions: Switching Random Walk Filters for Unsupervised Node Embedding Learning on Directed Graphs
Ciwan Ceylan
ciwan@kth.se
Division of Robotics, Perception and Learning KTH Rogal Institute of Technology
Kambiz Ghoorchian
kambiz. kambit..hooorchiinnsec.. com
SEB Croup
Danica Kragic
dani@kth.cm
Division of Robotics, Perception and Learning KTH Royal Institute of Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= Rmgg
Abstract
Unsupervised learning of node embeddings for directed graphs (digraphs) requires careful handling to ensure unbiased modelling. This paper addresses two key challenges: (1) the obstruction of information propagation in random walk and message-passing methods due to local sinks, and (2) the representation of multiple multi-step directed neighbourhoods, arising from the distinction between in- and out-neighbours. These challenges are intercon- nected-loca sinks can be mitigated by treating the graph undirected, but this comes at the cost of discarding all directional information. We make two main contributions to unsupervised embedding learning for digraphs. First, we introduce ReachNEs (Reachability Node Embeddings), a general framework for analysing embedding models and diagnosing local sink behaviour on digraphs. ReachNEs defines the reachability filter, a matrix polynomial over normalized adjacency matrices that captures multi-step, direction-sensitive proximity, It unifies the analysis of message-passing and random walk models, making its insights applicable across wide range of embedding methods. Second, we propose DirSwitch, novel embedding model that resolves both local sink bias and neighbourhood multiplicity via switching random walks. These walks use directed edges for local steps, preserving directional structure, then switch to undirected edges for long-range transitions, enabling escape from local sinks and improving information dispersal. Empirical results on node classification benchmarks demonstrate that DirSwitch consistently perperfsms state-of-the-art unsupervised digraph proximity embedding methods, and also serves as flexible digraph extension for self-supervised graph neural networks.
1 Introduction
Directed graphs (digraphs) and node embeddings are both essential modelling tools for graph data. Digraphs are ubiquitous for describing networks with asymmetric relationships, such as citation networks (McCallum et al., 2000), online dating platforms (Takac & Zabovsky, 2012), financial transactions (Fire & Guestrin, 2020), brain connectomes (Winding et al., 2023), and the Internet (Faloutsos et al., 1999). Similarly, node embeddings are key to solving machine learning and data mining tasks on graphs, including node classification (Hou et al., 2023), node clustering (Wang el al., 2017b), graph alignment (Heimann et. al., 2018), and link prediction (Virinchi & Saladi, 2023). Despite their combined prevalence, the field of unsupervised embedding learning for digraphs remains under-cxplored. Most rescarch has focused on undirected graphs and (semi-)superrisee learning, even though task-specific labelled data is often scarce (Hu et al., 2020b).
Embedding modelling for digraphs presents several challenges. A primary requirement is the ability to capture the asymmetric nature of digraphs. Conventional spectral-basod approaches fall short, as asymmetric matrices do not admit eigendecomposition (Zhang al., 2021b). As result, it common practice to treat digraphs undirected, thereby discarding important relational information (Rossi et al., 2023).

---

Published in Transactions on Machine Learning Research (06/2025)
(a) Undirected,
(b) Default, 00
(c) Reverse, II
(d) Out-In, DI
(e) In-Out, IO
Figure 1: Visualization of local sinks and neighbourhood multiplicity. Each digraph shows a valid dcfinition of the 2-step neighbourhood of node 1, highlighted in black. Note that each directed neighbourhood is unique, carrying independent information. (a) uses undirected edges, resulting in the maximum number of reachable nodes at the expense of the digraph structure. (b) shows the neighbourhood using the default, outgoing edge directions. The local sink, node 2, obstructs the information flow, so the neighbourhood consists of a single node. In (c), the reverse, incoming edges are followed, and (d) and (e) use mixed edge directions. (d) uses outgoing odges for the first step and incoming edges for the second, and vice versa for (c).
Recent research on digraph node embeddings has focused on adapting random walk and message-passe passing approaches to capture digraph asymmetry (Zhou et al., 2017; Khosla et al., 2020; Tong et al., 2020; Zhang et al., 2021b; Virinchi & Saladi, 2023; Rossi et al., 2023). These approaches rely on information propagation between nodes to generate embeddings that represent the connectivity of multi-step node neighbourhoods. To account for digraph asymmetry, these models separate propagation along outgoing (default) edges from reverse (incoming) edges, creating two sets of paired node embeddings.
While these models address digraph asymmetry, other challenges have been overlooked. This work tackles two such challenges: local sinks and neighbourhood multiplicity, visualized in Figure 1. The unidirectionality of digraph edges means information flows in only one direction. As a result, digraphs contain local sinks, i.e,, nodes without outgoing edges. As shown in Figure 1b, these sinks obstruct information propagation and hinder exploration of multi-step neighbourhoods. This leads to a disproportionale influence of sink nodes, resulting in biased embedding models. For instance, in Figure 1b, node 1 only sees the sink node (node 2).
As highlighted in Figure 1, the multi-step neighbourhood in digraphs is not uniquely defined. This multiplic- ity arises from the fact that each node has two distinct sets of neighbours: out-neighbours and in-neighbours. When multi-step neighbourhoods are considered, this multiplicity is exponentially amplified, as each node can have up to 2" distinct r-step neighbourhoods. The challenge for unsupervised node embedding models is to represent this multitude of distinct neighbourhoods as accurately as possible, since it is generally unknown a priori which neighbourhoods are key for solving downstream tasks.
In this work, we present two key contributions to address the challenges of unsupervised embedding learn- ing for digraphs: (1) ReachNEs (Reachability Node Embeddings), unifying framework for analysing node embedding models, and (2) DirSwitch, flexible approach for mitigating the issues of local sinks and neigh- bourhood multiplicity, applicable to both random walk and message-passing embedding models."
ReachNEs a mathematical framework designed to study and analyse the challenges of digraph node em- bedding modelling. Flexibility and analytical tractability are prioritizod in its design. To achieve this, ReachNEs is built around the reachabilily graph filler, matrix computed as a polynomial of normalized adjacency matrices, capturing asymmetric node proximity through multi-step random walk transition prob- abilities between node pairs in the graph.
The reachability matrix unifies random walk and message- passigg--asingggggg embedding models. To generate random walk-based proximity embeddings (Zhou et al., 2017: Zhu et al., 2021a), matrix factorization is used to decom- pose the reachability matrix into low-dimensional factors. Conversely, the reachability matrix can serve as a neighbourhood smoothing filter to produce linear message-pasee peessgg-passing embeddings (Wu et al., 2019). This versa- tility makes the insights drawn from ReachNFs analysis applicable to a wide range of embedding techniques.
The ReachNEs framework is also flexible with respect to modelling different neighbourhood scales, supporting multi-scale embeddings, which are crucial in the unsupervised setting (Rozemberczki et al., 2021). This control is provided by the coefficients of the reachability matrix's defining polynomial, which are interpreted as random walk length probabilities.
'Qur source code: http:////t.....ccccce/oo/oaoa//e
2

---

Published in Transactions on Machine Learning Research (06/2025)
(a) Input graph
(b) Default edge directions
(d) Node embeddings
Random walk filters
(c) DirSwitch-1
Figure 2: A qualitative illustration of DirSwitch. (a): The Cora-ML citation graph, with nodes coloured by class label (for visualization purposes only; not used in the model). (b) and (c): Random walk transition probabilitics from specific initialization node. The graph in (b) shows the default edge dircctions, while the graphs in (c) employ our DirSwitch-1 approach. DirSwitch-1 performs one directed step using either default (left) or reverse (right) edge directions, followed by undirected transitions. (d): UMAP (Sainburg et al., 2021) visualizations of the resulting node embeddings. The DinSwitch-1 embedding space better reflects the spatial ground truth class separation, demonstrating its improved neighbourhood smoothing on digraphs.
We use ReachNEs to quantify the effects of local sinks on information flow and to mathematically character- ize the multiplicity of distinct directed neighbourhoods in digraphs. This analysis reveals a tension between these two issues. The local sink problem can be easily resolved by treating digraphs as undirected, allowing information flow freely within each weakly connected component. However, this comes the cost of losing the distinction between directed neighbourhoods, reducing the expressivity of the embedding model. There- fore, we seek model that address local sinks while preserving the capture of directed neighbourhoods.
Our second contribution, DirSwitch, achieves this balance. The core idea of DirSwitch is to decouple local, short-range random walk behaviour from global, long-range behaviour. Specifically, DirSwitch preserves local edge direction expressivity by performing directed random walks in the initial steps. It then switches treating the graph as undirected, allowing information to propagate freely and escape local sinks. The effectiveness of this approach is illustrated in Figure
We empirically evaluate DirSwitch both within and beyond the ReachNEs framework. First, verify the that DirSwitch both improves information propagation on digraphs compared to fully directed approaches, without comprimisign the representation of local neighbourhood multiplicity.
We then demonstrate that this results in higher-quality embeddings and increased effectiveness by bench- marking DirSwitch on standard node classification benchmark datasets. Compared ReachNEs models that do not distinguish between local and global random walk bchaviours, DirSwitch cither achieves the highest accuracy performs within one standard deviation of the best result across all datasets. This holds true for both the random walk-based proximity embedding setting and the message-passing setting, Importantly, DirSwitch performs well on both homophilic and heterophilic datascts (Zhu et al., 2020). This is desirable as it implies a broad applicability of the DirSwitch in real-world unsupervised settings where the validity of a homophily assumption is in question (Wang et al., 2023).
To further assess DirSwitch's practical effectiveness, we evaluate against recent statc-of-tho-art digraph methods. On six proximity embedding benchmarks without node attributes, DirSwitch achieves the highest accuracy all datasets except one, where it performs within one standard deviation of the best.
3

---

Published in Transactions on Machine Learning Research (06/2025)
For message-passiinn embeddings, we apply DirSwitch as digraph extension of the GraphSAGE graph neural network (GNN) model (Hamilton et al., 2017) and integrate it with self-supervised loss functions, which have previously been limited to undirected graphs (Zhang et al., 2021a; Hou et al., 2023). This demonstrates how insights from ReachNEs can be leveraged to enhance embedding models more broadly. As a bascline, we use the recent digraph GNN extension by Rossi al. (2023), designed for supervised learning. Again, DirSwitch achieves higher accuracy on all but one dataset, underscoring the need for additional considerations when modelling digraphs in the unsupervised setting.
2 ReachNEs: Reachability Node Embeddings
This section introduces the ReachNEs framework for learning and analysing node embeddings in digraphs. It consists of two components: the baccabilitty graph filter, which represents multi-step node relations, and reduction methods, which extract emboddings. Section 2.1 derives reachability filters from random walks, while Section 2.2 describes the walk length distributions that determine the filter's smoothing properties. Finally, Section 2.3 presents reduction methods that unify message-passingg and proximity- embeddings.
2.1 The random walk reachability filter
Let = (N, M) be a directed, potentially weighted graph without self-loops, where N is the set of nodes and M is the set of edges. The graph has |N] nodes and = |M] edges. The adjacency matrix A E Ruxx is defined as follows, along with the out-degree and in-degree of a node j:
W g- if (i. e M. 0 otherwise,
Ar.
dego Σ Ak
degr (i)
Σ A
(1)
Here, Wjni E IR20 is a nonnegative weight associated with the edge (j, Note that the columns of A correspond to out-neiglbourhoods, while the rows correspond to in-neigbbourhoods.
We treat undirected graphs as a special case the above definitions, where Ar, Ay, for all edges in M. Consoquently, a digraph can be transformed into its corresponding undirected graph by adding the reverse edge (j. i) to MI for every edge (i,j) E M,, forming the edge set Mlundir. In terms of the adjacency matrix, this symmetrization is achieved by summing A and its transpose AT, Aundir A+
Next, we define three maddom walk normalized adjacency matrices, denoted as Ao, AI, and Au, which we collectively refer to as A, E [0,1]=xn Each of these matrices is column-stochastic matrix (Horn & Johnson, 2012, Ch. 8.7) and serves as a random walk state transition matrix. Specifically, given a probability state vector (*)) E [0, 1]", where (())) represents the probability of random walker being at node i after k steps, the state vector after k- + 1 steps is computed as (k+1)) = (A)
Each normalized adjacency matrix defines different random walk behaviour with respect to the edge directions. For Ag, a random walker follows the default edge directions, transitioning from a node to its neighbours along outgoing edges. Conversely, transitions using A₁ follow the reverse edge directions, meaning the walker traverses incoming edges. For Au, the edges are treated as undirected, allowing the random walker to move across both outgoing and incoming edges. These behaviours are formally defined follows:
i j and dega (j) = 0,
if j and degr(j) = 0,
Aos.j
Ang
Aig (e
othiiiise,
Aga dege(T)
otherwise,
if and deg(j) = O, deg(i) =
Aus,j
Aundick,
Aundictd deg(7)
otherwise,
1=1
To ensure column stochasticity, diagonal elements are set to 1 for nodes without legal edges to follow. Such nodes are referred to as sink nodes, as random walker gets stuck on these nodes. For digraphs without sink nodes, the above definitions can be expressed compactly in matrix form:
Ag = A
A = ATD1
Au = Aundie D-1
where Do, D1, and D diagonal matrices of the respective node degrees.
4

---

Published in Transactions on Machine Learning Research (06/2025)
Each A, describe immediate neighbourhoods, which can be extended to capture multi-step connectivity through matrix powers. Specifically, the jth column of the power matrix A encodes the transition prob- abilities of random walk of length & initialized at node j. This follows directly from the state transition formula p(++)) = A.p(A). Accordingly, we denote clement (t, of A as P(j - a[k), representing the probability of transitioning from node j to node in exactly steps.
Each matrix power A provides a snapshot of transition probabilities at a specific walk length k. However, any fixed & inherently restricts the description of node neighbourhoods and introduces potential biases. For example, setting k might fail to capture immediate neighbours if no 2-step paths exist between them, resulting in zero transition probabilities for such nodes.
To mitigale the bias and sensitivity introduced by single walk lengths, we instead impose a probability distribution over the walk length: (x(k). Using this distribution, the node transition probabilities are computed by marginalizing over the walk length. This leads to the definition of the reachability matrir R Raxn, where each element Raj represents the probability of transitioning from node j to node i, with the walk length sampled from Px(k):
R(A.: P+)
P.(K)A A==
(A.((A.)P)) = P(j ip = P.. ~ i.R:).
(2)
R=0
Figure 3a shows an example the reachability matrix P() using the U.S. political blogs graph (Adamic & Glance, 2005). Each column represents the transition probabilities from random walk starting at the corresponding node. The two prominent blocks reflect the political alignments in the dataset. Figure 3b visualizes one such column vector, overlaid a ridiculogram of the graph. The separation wet the two political communities appears clearly as two clusters.
2.2 Walk length distributions
As defined in Equation 2, the walk length distribution (a(k) controls the weighting of each adjacency power A thereby shaping the filter's smoothing behaviour. While ReachNEs is compatible with any such distribution, in this work we focus on four commonly used ones: geometric, binomial, Poisson, and uniform.
Table lists the corresponding probability mass functions (pmfs), each paramcterized by the expected walk length E[P.]. Figure 3c visualizes the pmfs for 5 2. We briefly describe each distribution below; further analysis appears in Appendix C.
The geometric distribution is central to the PageRank algorithm (Page et al., 1999), where a - denotes the probability of continuing a walk, and 1 - a the restart probability. It is monotonically decreasing for all 7, and remains mode-centred at k = 0, even as it flattens with increasing т. Owing to PageRank's influence, the geometric distribution widely used in embedding methods (Zhou et al., 2017; Yan et al., 2024).
The binomial distribution has finite maximum walk length K, where a & denotes the probability of stepping, and 1 the probability of remaining in place. As discussed in Appendix C.5, this distribution naturally arises when self-loops are added to graphs, common practice in graph convolutional networks (Kipf & Welling, 2017; Wu et al., 2019).
Table 1: Overview of the studied random walk length distributions (k; where l represents the walk length variable. Each distribution is parameterized by the average walk length т. For readability, use a as substitution variable in the geometric and binomial distributions. The binomial distribution includes an additional parameter, K, representing the maximum walk length. Distribution plots are shown in Figure 3c.
NAME
GEOMETRIC
BINOMIAL
POISSON
UNIFORM
ABDREVIATION
Geom
Binom
Pois
U
if & [0,27]. otherwise
Po(k:)
(1 a)a',
(1) a)
k a
2T +
++1
K
R
5

---

Published in Transactions on Machine Learning Research (06/2025)
Prob. funetion. Pa(k)
Geumetratk r -
Prob. mass funetion, Pw(k)
Binoentk: r 20
0.3
Poissonfte -)
0.3
Unafornde
0.2
0.2
0.1
0.0
5
101112
0.0 3 6 9100112
Walk length, &
Walk length, &
(a) A reachability matrix (b) One reachability vector
Walk length distributions
Figure 3: (a) The reachability matrix R(Ay; Pois(T = 2)) for the Polblogs graph. Each column encodes the transition probabilities of a random walk starting at. the corresponding node. (b) A single column of R visualized on a ridiculogram of the graph, illustrating the locality of the reachability distribution. (c) The four walk length distributions used in this work, evaluated at т 2: Geometric, Poisson, Binomial, and Uniform. These distributions weight the contribution of different walk lengths in the computation of R.
In the limit K + oc, the binomial distribution converges to the Poisson distribution. The Poisson distribution has been used in structural embedding methods (Donnat et al., 2018; Zhu et al., 2021a; Ceylan et al., 2022) and connects reachability to heat diffusion on graphs.
Unlike the geometric distribution, both the binomial and Poisson distributions tend toward non-informative filters т 0o. Their modes shift with 5, cmphasizing larger k values, which leads to over-smoothing: columns of R become nearly uniform, reducing embedding discrininability. This effect, analysed in detail in Appendix C, plays a key role in interpreting some of our experimental results.
Finally, the uniform distribution widely used in node embodding models, as it naturally arises from common negative sampling schemes (Perowzi et al., 2014; Qiu et al., 2018; Chanpuriya & Musco, 2020).
2.3 Reachability reduction into node embeddings
To complete the ReachNEs framework, the pairwise multi-step relationships encoded in the reachability matrix R must be transformed into node embeddings. We refer to these transformations as reduction methods, as they reduce the n x n matrix R into lower-dimensional embedding matrix Z E Ra*p,
The reduction method serves two main purposes. First, it projects nodes into a lower-dimensional space improving computational efficiency for downstream tasks and alleviating the curse of dimensionality (Hastie et al., 2009, Ch. 2.5). Second, the choice of reduction method encodes specific equivalence relation- ships into the embeddings (Zhu et al., 2021a). We explore two reduction approaches: proximity embeddings and messago-passing embeddings, which capture structural and automorphic equivalence respectively.
(p<n)
n), <),,
2.3.1 Proximity embedding reduction and structural equivalence
Proximity embeddings capture mutual node connectivity and closeness, and are often referred to positional embeddings in the context of undirected graphs (Zhu et al., 2021a). However, the asymmetric nature of digraphs makes the concept of "position" in a symmetric, Euclidean sense inappropriate. Instead, we define node proximity asymmetrically using the reachability matrix R(A.;; Po), where the element Ra,j quantifies the closeness of node j to node The walk length distribution P, controls the resolution of this proximity.
To derive proximity embeddings from R, we employ Singular Value Decomposition (SVD) (Golub & Van Loan, 2013, Ch. 2.4), widely used technique in proximity embedding methods (Qiu et. al., 2018; Zhu et al., 2021a). Let U, E, VT R) represent the SVD of R, and let U..qq Engags and V..g denote the g-truncation of U, Σ, and V, respectively, where q = p/2. The proximity embeddings are then defined as:
Z Zu
Zv| E R2X24
Zu U..00 V Eigin g2x9,
Zv V.Na V Eiqin E Rax9
(3)
6

---

Published in Transactions on Machine Learning Research (06/2025)
The proximity embeddings capture node proximity in two key ways. First, the inner product of the left and right embeddings approximates the reachability matrix: R R Zu = U D.. Second, the Euclidean distance between embeddings in Z reflects the overlap of multi-step neighbourhoods. The latter is particularly important for downstream tasks such as chustering, where embodding distances are often utilized.
The following equality (derived in Appendix A.3) formalizes the relationship between reachability similarity and embedding distance:
Z,.) V R R2, + IR - R., 12 -
2 2'
Σ =
Σ Engo4
0 Egg:a
(4)
The left-hand side measures the difference between rows and columns of R for nodes i and j, quantifying the overlap of their multi-step neighbourhoods. The right-hand side represents the distance between their respective proximity embeddings in Z. This equivalence implics that, for S trank two nodes have identical embeddings in Z if and only if their multi-step neighbourhoods perfectly overlap.
This property is particularly valuable for distance- basedd downstream tasks. However, its validity relies on the first term in the definition of R in Equation 2, i.e., Po(k = 0) being zero. This term introduces constant, nam-negbbbortooddeeeeddee
contribution that prevents structurally equivalent nodes from having identical embeddings. To address this, compute R for proximity embeddings using shifted walk- length distribution; meaning that the coefficients in Equation 2 are replaced with (k- using P=(-1) 0.
Another modification to the definition of R is the application of the elementwise thresholding function ((R,,) = Iog(max(nRR... 1)) before performing the SVD. This contrast-enhancing function amplifies the difference between clements where Ri.j < 1 and those where Riz E n. logn This type of contrast enhancement has been shown yield practical benefits for undirected graphs (Qiu al., 2018; Chanpuriya & Musco, 2020; Zhu al., 2021a), and we find that these advantages extend to digraphs as well.
Structural equivalence. Two nodes and j are structurally equivalent if they have identical in- and out- neighbours, i.e., A.: = Aj. and A. A., (Borgatti & Everett, 1992). In undirected graphs, this implies that structurally equivalent nodes are at most two steps apart, highlighting the close connection between structural equivalence and node proximity.
Proximity ReachNEs embeddings preserve this equivalence under mild conditions. If nodes i and are structurally equivalent and have nonzero in- and out-degrees, and if the walk length distribution satisfies PA = 0) = 0, then Z, Zy. holds as long q S (a) The reason is straightforward: structural equivalence implies that the i-th and j-th rows and columns of A are identical for all k 2 1, and thus also in R = Σ<>1 (A). It follows from Equation 4 that the embeddings must be equal, since the diagonal elements of E are positive under the assumption g S rank(R).
An exception occurs for sink nodes. When a node lacks outgoing edges, the normalization of Ao sets the corresponding diagonal entry to 1, violating the condition that A.i. A.j.- As a result, structurally equivalent sink nodes (with identical incoming edges) can receive different embeddings. The same issue applics under A for nodes without incoming edges.
This limitation is shared by many sandom-walk-based proximity embeddings (Perozzi et al., 2014; Grover & Leskovec, 2016; Zhou et al., 2017; Qiu et al., 2018; Khosla et al., 2020). A simple workaround to assign the zero vector to all zero-degree sink nodes in post-processing. Whether this improves downstream performance remains an open research question.
2.3.2 Message-passing embedding reduction and automorphic equivalence
Pressage-passing embedding reduction requires an initial set of node representations, i.e., a matrix of node attribute voctors X E Radd These attributes typically supplement the graph structure, such as text embed- dings of paper abstracts citation graphs (Hu al., 2020a). Alternatively, X may consist of graph-derived properties, such node degrees local clustering coefficients.
7

---

Published in Transactions on Machine Learning Research (06/2025)
The ReachNEs message-passinng embeddings smoothed versions of the node attribute vectors, with the columns of the reachability matrix R defining the multi-step smoothing filter over each node's local neigh- bourhood. Thus, initial d-dimensional message-passing embeddings are straightforwardly obtained via the matrix multiplication Z X. To further reduce the dimensionality to p dimensions, techniques like PCA (Murphy, 2012, Ch. 12.2) can be applied, yielding the embeddings Z (C)(
Message-passing is commonly used in the context of graph neural networks (Gilmer et al., 2017). In typical descriptions, each node receives messages from its neighbours in the form of embedding vectors, which are aggregated and then used to update its own embedding representation. Given this, may not be immediately clear how the linear model R relates to message-passing
Connection to message-passing.
To establish this connection, we expand R X by bringing the transpose inside the sum of Equation 2:
80 R
2
Σ (c())AA)
Σ k=0
Pa( (At)
Σ
Po(k)
(5)
Next, we let H X and z (o( and express the sum in Equation as an iterative algorithm:
(k- Z(k) - (()
(
For k E (1,
(6)
This iterative formulation connects directly to message-passing. To clarify the connection, consider the update (k) (H-H( for the undirected random walk matrix. Assuming no sink nodes and uniform edge weights for simplicity, the process can be expressed as:
AJH D- Amdi
[A] deg(i)
Σ
Hig
j.J.)EMaadr
The right-hand side describes meon neighbourhood aggregation, where messages (represented by H) are averaged over a node's immediate neighbours. This mirrors the aggregation function used in GraphSAGE (Hamilton et al., 2017, Alg. 1). Similarly, AJ and AT aggregate messages over outgoing and incoming neighbourhoods, respectively, in the directed GraphSAGE extension proposed by Rossi et al. (2023). Full mathematical expressions for the directed case are provided in Appendix A.2.
Automorphic equivalence. Two nodes i and j are antomorphically equivalent if there cxists a permu- tation matrix P, E 10,1 such that A = P.APT and Paj,; 1. Intuitively, this means that i and are indistinguishable in terms of all graph-theoretic properties, such as degree, centrality, and clustering coefficients, and differ only in their labels. Automorphic equivalence is implied by structural equivalence, but not vice versa. Notably, automorphically equivalent nodes can be arbitrarily far apart in the graph, or even belong to disconnected components.
Message-passing ReachNEs preserves automorphic equivalence, provided that the node attributes are also invariant under the automorphism. Specifically, if X P.X, which holds whenever X consists of graph- derived features, then the embeddings satisfy Z Z. In this case, automorphically equivalent nodes receive identical mossage-passing embeddings. A proof and further discussion are provided in Appendix B.
3 Local sinks and directed neighbourhood multiplicity
In this section, we use the ReachNEs framework to study local sinks and neighbourhood multiplicity, We ex- amine how local sinks obstruct information propagation and quantify their effects using entropy. We formal- ize the multiplicity of directed neighbourhoods within ReachNEs and discuss its implications for embedding model expressivity. Finally, we explore how expressivity can be improved through embedding concatenation.
8

---

Published in Transactions on Machine Learning Research (06/2025)
(a) Cora-ML. Left: Default (0), Right: Undirected (U) (b) Fly Larva. Left: Default (0), Right: Undirected (U)
Figure 4: Visualization of transition probability accumulation local sinks. Node size and colour indicate the magnitude of reachability, with black denoting zero. (a) shows the Cora-ML citation graph using default directed edges (0, left) and undirected edges (U, right). In the directed case, reachability is concentrated in small set of sink nodes, whereas the undirected version yields more uniform coverage of the multi-step neighbourhood. (b) shows similar behaviour for the Fly Larva dataset: reachability under 0 accumulates disproportionately in sinks, while U promotes broader dispersal.
3.1 Local sink analysis
As seen in Section 2, the elements of the reachability matrix R represent random walk transition probabilities, with each column describing a smoothing over multi-step neighbourhoods for a given node. However, local sinks in digraphs can significantly disrupt this smoothing process.
As highlighted in Figure 1b, local sinks are nodes, or small sets of nodes, without directed paths to the rest of the graph. Random walks initiated at sink nodes remain trapped, preventing them from gathering additional neighbourhood information. Moreover, transition probabilities of walks starting at other nodes tend to accumulate in sinks, as random walkers can enter but cannot escape. This accumulation disproportionately amplifies the influence of sink nodes on the reachability filter, introducing bias into the embedding model.
Figure illustrates these effects using ridiculograms of real- world graphs. In Figure 4a the Cora-ML citation graph shows strong accumulation in sink nodes when using default edge directions, i.e. R(Ao)), while the undirected variant, i.c., R(As), achieves broader coverage shows a similar pattern in the denser Fly Larva brain connectome (Winding el al., 2023).
the multi-step neighbourhood. Figure 4b
The columns of the reachability matrix reflect how local sinks restrict information propagation. Consider a node j, whose random walk probabilities are given by the column R. If j is a sink node, or if its transition probabilities are largely absorbed by a sink, the reachability will be concentrated in a few nonzero values R a property we refer as low dispersal. Conversely, high dispersal indicates that probabilities are more evenly distributed across j's multi-step neighbourhood.
This notion of dispersal is naturally captured by Shannon entropy (Cover & Thooas, 2005, Ch. 2.1). We define the reachability entropy of node j as H Rt) = E Ri, log, Ri.. Entropy is always non- non-negative, reaching zero when all probability is concentrated in a single node. Conversely, it attains its maximum value, log, n, when probabilities are uniformly distributed across all n nodes. Thus, higher entropy corresponds to reduced bias toward sink nodes and improved dispersal.
In Figure 5, we plot the entropy for the Cora-ML and Fly Larva graphs. The y-axes represent entropy, H(j; while the x-axes correspond to nodes j, sorted by entropy values. We use P. Pois(T), with each coloured line representing distinct 7 value. The dashed line indicates the entropy of the asymptotic reachability matrix as + xo for the undirected graph (see Appendix C.1).
Transitioning from the directed to the undirected graph yields a notable increase in entropy for Cora-ML (cf. Figure and Figure 5b), reflecting improved dispersal in the absence of sink nodes. The effect of the neigh- bourhood scale parameter 7 also differs: in the undirected case, entropy grows steadily toward its asymptotic limit, while in the directed case, it eventually declines as probability mass accumulates in sink nodes.
9

---

Published in Transactions on Machine Learning Research (06/2025)
2
6
8
10
12
Rig xx deg(E)
10.0
10.0
10.0
Entropy
7.5
Eatropy
Entropy
7.0
Eatropy
7.5
5.0
5.0
5.0
5.0
2,5
2.5
6.0
0.0
0.0
0.0
0.0
L.
10
0.0
0.5
10
000
035
10
033
0.5
Proportion of nodes
Propoction of nodes
Proportion aodes
Proportion of nodes
(a) Cora-ML, 0
(b) Cora-ML, U
(c) Fly Larva, 0
(d) Fly Larva, U
Figure 5: Reachability under P.- = Pois(T), using Ao and Ag. The x-axes correspond to nodes sorted
by their entropy value. The colours represent various values of т. The black dashed line indicates the entropy of a reachability distribution proportional to the node degrees, which corresponds to the limiting and uninformative distribution as 7 - xo. See Appendix C.1 for further details.
For the Fly Larva graph, entropy differences between the directed and undirected cases are smaller, as expected given the graph's higher density. Still, entropy is consistently higher in the undirected case, with the largest gap appearing at the highest т, as reachability in the directed graph again concentrates in sinks.
It is important note that high dispersal alone does not guarantee embedding quality. This becomes evident when considering that maximum entropy is achieved when Ra, 1 meaning smoothing is performed uni- formly across the graph. While this maximizes dispersal, it renders the embeddings uninformative. Instead, dispersal must be complemented by another key property, which we discuss in the next section: expressivity.
3.2 Embedding model expressivity and neighbourhood multiplicity
As discussed in Section 2.3, ReachNEs respects node equivalence under mild conditions: proximity ReachNEs yields identical embeddings for structurally equivalent nodes, and automorphically equivalent ones. However, this alone is not sufficient for producing high-quality embeddings. We also require model erpressivily, which we define as the ability to dislinguish nonequivalend nodes.
ReachNEs does for
A fully expressive model would assign identical embeddings to equivalent nodes, and distinct embeddings to nonoquivalent ones. Achieving this for automorphic equivalence is particularly challenging; in fact, any model that perfectly encodes automorphic equivalence would effectively solve the graph isomorphism problem (Grohe & Schweitzer, 2020). The expressivity of messagg-passing models is therefore an active area of research (Xu et al., 2019; Morris et al., 2019) (see Section 5.4 for further discussion).
Structural equivalence is simpler to handle. Since structurally equivalent nodes have identical rows and columns in the adjacency matrix A, one can construct a fully expressive, albeit impractical, embedding matrix by concatenating A and its transpose: Z = [A AT]. This model captures structural distinctions perfectly but ignores multi-step relationships and produces a prohibitively large embedding space. Consequently, expressivity remains key concern for proximity ReachNEs, as both the random-walk smoothing in R and the information loss from SVD reduction can limit the model's ability to distinguish between nonequivalent nodes.
Model expressivity is especially important for digraphs due to the existence of weighhourhood multiplicily. As illustrated in Figure 1, the neighbourhood of a node in a digraph is not uniquely defined. At each step of a random walk, the walker can follow either incoming or outgoing odges, leading to 2 possible neighbourhoods for a walk of length K. Embedding models that fail to capture the distinctions among these directed neighbourhoods inherently suffer from reduced expressivity.
We formalize this idca using truncated K-step reachability matrix. Let the edge orientation specifier be string o of length K, where each character or {U, I} indicates whether the I-th step uses undirected, outgoing, or incoming edges, respectively. Given a specifier a, the corresponding reachability matrix is:
K Σ Po(k)
(AK).A σ) = -Po(
I
Am
AA.., I=1
Ao, = Ao, ... A...A
(8)
[=1
10

---

Published in Transactions on Machine Learning Research (06/2025)
Like the reachability definition in Equation 2, the matrix R (A; is column-stochastie transition matrix, provided that P. is properly normalized over K steps. It captures transition probabilities for multi- directional random walks defined by the edge orientation specifier a. For instance, o = OIO corresponds to walks that follow outgoing, then incoming, then outgoing edges. Our definition also allows walk steps over undirected edges (U), which will be relevant for defining DirSwitch in Section 4.
Equation defines how to compute multi-directional reachability matrices, but it remains to determine how best to incorporate them into node embeddings. A widely used and effective strategy for this purpose is embedding concatenation (Jin et al., 2019; Corso et al., 2020). This approach involves extracting multiple sets of embeddings that capture different structural aspects of the graph, c.g., 2 E Re*0 and Z Raxps, and combining them into a joint embedding space, Z ( Z (2) E (x Concatenation is particularly advantageous in unsupervised settings, as it ensures that all constituent embeddings contribute to the final representation.
Concatenation is particularly popular for producing mulli-scale embeddings (Rozemberezki et al., 2021). The goal of multi-scale embeddings is to represent the inherent hierarchical structure of real-world graphs (Newman, 2018, Ch. 14.7.2) by concatenating embeddings that capture different neighbourhood scales. The ReachNEs framework enables this by incorporating multiple walk length distributions, P.. For example, using Pa (2) = Geom(T = 1) and P, (2(2) = Pois(T = 3) results in two reachability matrices, R(P.(1) and R(P, (2),, which focus on immediate and 3-step neighbourhoods, respectively.
The same principle extends to directed neighbourhoods. By concatenating embeddings generated from different edge direction specifiers a, we obtain multi-directional embeddings. This approach can be further combined with multi-scale embeddings to jointly encode both aspects of graph structure.
However, key limitation of embedding concatenation is that the embedding dimensionality, p, grows with each additional concatenation. This increase be rapid, given the exponential number of distinct directed neighbourhoods and their possible combinations with multi-scale embeddings. Excessively high dimension- ality leads to increased memory and computational costs, as well as potential issues related to the curse of dimensionality. Therefore, it is beneficial to pair concatenation with dimensionality reduction techniques, such as PCA (Murphy, 2012, Ch. 12.2).
4 DirSwitch: Switching reachability filters
The previous section highlights a dual challenge in digraph embedding modelling. Local sinks obstruct information propagation, leading to embeddings biased toward sink nodes. This issue can be easily mitigated by treating the digraph as undirected, effectively ignoring edge directions. However, this approach reduces model expressivity by discarding information about the multiplicity of directed neighbourhoods.
To address these intertwined issues, we propose switching random walks. The key idea is to generate multi- directional embeddings by following directed edges for the first steps of a random walk, thereby capturing local directed neighbourhood structure. After r steps, the graph is treated as undirected, allowing the walk to escape sinks and achieve broader dispersal.
We name this approach DinSwitch. To formally define the DirSwitch model, we introduce a shorthand notation for the edge direction specifier a. For a K-step random walk, we define a as a string of length ++ 1, where K. The final character, ar+1, determines the direction for the last K-r steps of the walk.
Rewriting Equation 8 using this notation and taking the limit K + co, obtain:
00
R(A; .) P. P II A.,
Σ k=r+1
A A
(9)
1=1
In this formulation, a DirSwitch model is characterized by the first r letters in a being either or I, representing directed walk steps, while the final character, dr+1, is set to U, ensuring undirected propagation for the remaining steps.
11

---

Published in Transactions on Machine Learning Research (06/2025)
The switch to undirected edges addresses the issue of local sinks, but it remains necessary to incorporate representations of different directed neighbourhoods. To achieve this, we use the multi-directional concate- nation approach described in Section 3.2. For a given value of T, we define the DirSwitch-r embedding model as the concatenation of all 2" possible configurations of a a sequence of length r + ending with 0r+1 = U. For example, DirSwitch-1 concatenates embeddings using a = DU and o IU, while DirSwitch-2 uses a E (DOU, OIU, IOU, IIU), and so on for any DirSwitch-r model.
As bascline in our experiments, MultiDir-1 uses 0 and I, while MultiDir-2 includes all two-step combinations E (0, I0, I], and so on, covering all 2" possible r-step direction sequences. Unlike DirSwitch, however, MultiDir does not transition to undirected edges after the specified sequence. Instead, the walk continues in the last specified direction. For example, with K total steps and o = OI, the walk takes one step in the 0 direction, one in the I direction, and then continues the remaining K steps in the direction.
define MultiDir-r using the same notation as above. Specifically,
As noted in Section 3.2, multi-iirectional concatenation can be combined with multi-scale concatenation to improve embedding quality. However, this combination exhibits diminishing returns: using r steps of directionality with walk length distributions for fixed embedding dimension p means that each (o, P.)- P. dimensions. We discuss these diminishing returns further in Appendix A.6, where
pair contributes only 2"s we also present a practical guide to DirSwitch-r hyperparameter selection based on our experiments and experience, Additionally, increasing r and s raises computational costs, which we analyse in Appendix A.5.
5
Related Work
5.1 Relation to node embedding and graph learning frameworks
The ReachNEs framework is built around the reachability matrix, interpreted as random walk transition probabilities, and two embedding reduction strategies: matrix decomposition and message passing. Similar ideas appear throughout the graph learning literature. Below, we highlight key connections and distinctions.
Sampled random walks. The use of random walks for proximity-based emboddings was popularized by Perozzi et al. (2014) and Grover & Leskovee (2016), who combined sampled walks with negative sam- Sling-originally introduced for word embeddings (Mikolov et al., 2013). As shown by Qiu et al. (2018), these methods asymptotically approximate a matrix factorization of log(R) b, where log is applied elementwise, b is constant, and R is the random walk transition probability matrix, as in ReachNEs.
This suggests that sampled walk models and proximity ReachNEs converge to similar embeddings in the limit of infinite samples. However, in practice sampling is expensive, and only a small fraction of possible walks and non-edges are used. As a result, sampled random walk models and proximity ReachNEs typically yield different embeddings in finite regimes.
Additionally, sampled walk methods usually rely on a single walk length distribution; commonly uniform, though Zhou et al. (2017) use the geometric distribution. In contrast, ReachNEs supports multiple walk length distributions, enabling multi-scale embeddings.
Proximity matrix reduction. Extending the idea of proximity emboddings via matrix decomposition, Zhu et al. (2021a) introduced the PhUSION framework. Like ReachNEs, PhUSION generates embeddings by applying reduction functions to node proximity matrix, and can encode either structural or automorphic equivalence depending on the chosen reduction. We compare this aspect of the two frameworks in Section 5.2.
In other aspects, PhUSION differs from ReachNEs in two key ways. First, it is restricted to undirected graphs. Second, interprets the proximity matrix through the lens of matrix functions (Higham, 2008), treating the scalars (k) in Equation 2 as Taylor cocfficients rather than probabilitics. While this perspective is mathematically more general, it limits analysability. For example, our analysis of reachability entropy in Section 3.1 depends on interpreting R as transition probability matrix.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Graph convolutional filters. Like matrix functions, graph convolutional filters generalize the reachability matrix (Defferrard et al., 2016; Tsufi et al., 2024). They are defined and applied similarly to message- message-passing ReachNEs, also assuming the presence of initial node features X. However, the series coefficients, Pa(k) in Equation 2, can take arbitrary real values, making random walk interpretations generally inapplicable.
Instead, convolutional filters are viewed as extensions of classical convolutions to graphs and are typically analysed using spectral methods based on eigenfunctions (Bronstein al., 2017). Since asymmetric matrices lack a standard eigendecomposition, spectral analysis becomes difficult on digraphs, and most rescarch in this area focuses undirected graphs (Zhang et al., 2021b). In contrast, ReachNEs defines R purely through ran- dom walk probabilities, making the framework naturally applicable to both directed and undirected graphs.
Message-passing graph neural networks. The dominant paradigm in node embedding learning is crssage-passinng graph neural networks (GNNs) (Gilmer et al., 2017). GNNs are typically nonlinear and pa- rameterized, requiring training via non-convex optimization. While this complicates their analysis compared to ReachNEs, their overall algorithmic structure is similar. In fact, only minor modifications to Equation 6 are needed to recover the GraphSAGE encoder (Hamilton et al., 2017). We exploit this connection in Scction 6.5 to show how our results extend to the sclf-supervised GNN sctting.
Interestingly, the binomial walk length distribution in ReachNEs is related to the self-loops added convo- lutional GNNs (Kipf& & Welling, 2017; Wu al., 2019). We explore this connection further in Appendix C.5.
Graph kernels. While many embedding methods implicitly rely on walk length distributions, few works explicitly analyse or compare their effects as we do. In contrast, the graph kernel literature, particularly random walk kernels, has explored related formulations, including both geometric and Poisson walk longth distributions (Vishwanathan al., 2010). However, since graph kernels are designed for graph-level com- parison rather than node-level tasks, it remains open question which insights transfer to ReachNEs.
5.2 Structural and automorphic equivalence
Recent work has highlighted the distinction between embedding models that capture structural versus auto- morphic node equivalence (Jin et al., 2021; Zhu et al., 2021a; Yan al., 2024). Models targeting structural equivalence are often called positional embeddings, while those targeting automorphic equivalence are referred to structural embeddings. The terminology is admittedly confusing, as the term structural is used in two different senses.
ReachNEss draws inspiration from the PhUSION framework (Zhu et al., 2021a), which also produces both positional and structural embeddings by applying different reduction methods to a node proximity matrix (analogous to our reachability matrix). For positional embeddings, both ReachNEs and PhUSTON use SVD reduction. However, PhUSION assumes undirected graphs and retains only the left singular vectors U, while ReachNEs concatenates both U and V to handle directed graphs.
For structural embeddings, PhUSION applies the permulation-invarian empirical characteristic function to each column of R. following the approach introduced by Donnat et al. (2018). In contrast, ReachNEs uses message-passing reduction, aligning more directly with the message-passing GNN literature.
Finally, while some argue that positional and structural embeddings represent fundamentally different ob- jectives (Rossi et al., 2020), Srinivasan & Ribeiro (2020) established a statistical equivalence between them. However, the practical consequences of this result remain an open question.
5.3 Digraph models
Research on message-passing embedding models, particularly GNNs, has primarily focused on undirected graphs (Rossi et al., 2023). This is espocially true in unsupervised and self-supervised learning, where recent tate--of-theaar models remain constrained undirected graphs (Hassani & Khasahmadi, 2020; Thakoor et al., 2022; Zhang et al., 2021a; Hou et al., 2023).
13

---

Published in Transactions on Machine Learning Research (06/2025)
For (semi-)superviise) learning, Rossi et al. (2023) proposed digraph extensions for common GNN embedding encoders. Unlike DirSwitch, which uses concatenation to preserve the contribut ions of different directed neighbourhoods in distinct embedding components, Rossi et al. (2023) employs parameterized mixing of these components. This approach requires the model to Iearn how to extract and preserve relevant information from multi-directional neighbourhoods. However, this filtering process is more challenging in unsupervised settings due to the weaker learning signal.
In contrast, rescarch on unsupervised proximity embeddings for digraphs has progressed further than its message-passingg counterpart. The models HOPE (Ou et al., 2016), APP (Zhou et al., 2017), and NERD (Khosla et al., 2020) follow similar approach to ReachNEs and DirSwitch, leveraging random walks and matrix factorization of proximity matrices. However, none of these models explicitly address local sinks and neighbourhood multiplicity, which are the primary focus of our work.
Additionally, there are several notable algorithmic differences. Both HOPE and APP use the geometric walk length distribution, while NERD employs the uniform distribution. In contrast, ReachNEs treats the choice of distribution a parameter. NERD also introduces alternating walks, where edge direction specifiers IOIO.... While this pattern may help
switch between outgoing and incoming edges (e.g., OIOI... random walks escape some sinks, restricting the model to only these sequences introduces bias by excluding other directed neighbourhood definitions.
Furthermore, HOPE utilizes partial and generalized SVD (Hochstenbach, 2009) for matrix factorization, whereas ReachNEs employs the more scalable single-pass SVD (Yu et al., 2017). Both APP and NERD rely on Monte Carlo sampling of random walks and implicit matrix factorization via gradient descent and negative sampling, while ReachNEs directly computes the reachability matrix using matrix multiplication.
Finally, DGGAN (Zhu et al., 2021b) and BLADE (Virinchi & Saladi, 2023) are unsupervised digraph embed- ding methods that incorporate neural networks. While neither explicitly addresses the issue of local sinks, BLADE follows an embodding mixing strategy similar to Rossi et al. (2023), where a GNN is responsible for filtering information from distinct directed neighbourhoods.
5.4 Expressivity of message- vessage-passing models
The expressivity of message-passing models is a central topic in graph representation learning due to its connection with the graph isomorphism problem (Grohe & Schweitzer, 2020). Li & Leskovec (2022, Def. 5.5) offers a formal definition, characterizing model expressivity as the ability to produce distinct representations for non-isomorphic graphs. While their formulation is mathematically rigorous, our definition in Section 3.2 captures the same core idea in a more intuitive manner, with a focus on node equivalence rather than full graph isomorphism.
The foundational works of Xu al. (2019) and Morris et al. (2019) relate the expressivity of message- message-passing graph neural networks (MP-GNNs) to the Weisfeiler-Leman (WL) colour refinement algorithm (Grohe et al., 2021), an iterative method used to test graph isomorphism. Rossi et al. (2023) extended these results to digraphs by incorporating both in- and out-neighbourhoods in the message-passing process, in a manner analogous to our MultiDir and DirSwitch approaches.
These studies demonstrate that the expressive power of MP-GNNs is upper-bounded by the WT. algorithm. This also applics to message-passing ReachNEs, which can be viewed as lincar MP-GNN. Morcover, they show that MP-GNNs can match the expressivily of the WL test if their message aggregation functions are sufficiently flexible- specifically, if they can form injective mappings from multisets to vectors, mimicking the WL hashing mechanism. These assumptions, however, do not hold for ReachNEs, which is linear and parameterized solely through scalar-valued walk length distributions.
The use of flexible, non-linear aggregation functions is well-suited to the supervised, end-to-end learning context studied by Xu et al. (2019), Morris et al. (2019), and Rossi al. (2023), where parameters can be optimized to task-specific objectives. In contrast, the unsupervised setting considered in this work demands greater interpretability and analytical tractability, especially for downstream tasks such anomaly detection.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Table 2: Graph statistics for the datascts. The colurns report the number of nodes (n) and edges (m), the median out- and in-degrees (|degol: [degr]), the number of weakly and strongly connected components (#CC and #SCC), the global clustering coefficient (Cş), and the average path length ((path)) computed on the undirected version of the graph. Additionally, when available, we list the number of node attributes (d), the number of node label classes (| and the homophily coefficient of the undirected graph (hv). The final column specifies the graph type. We use the shorthand notation with K=10 and M=100 for large values.
DATASET
772
dego
degg
# CC
# SCC
Cg
(ppth)
|8|
hg
TYPE
ARXIV
170K
1.2M
4
141K
0.017
128
0.64
CITATION
BRXIV-YEAR
170K
1.2M
4
1
141K
0.017
5.7
128
0.29
CITATION
CITESERR
4.2K
5.4K
1
515
4209
0.084
7.4
602
0.96
CITATION
COCrTE
44K
20K
2
652
44K
0.081
5.5
15
0.42
CITATION
CORA
20K
65K
2
364
16K
0.14
6.2
8710
70
0.59
CITATION
CORA-ML3
3K
8.4K
2
61
2603
0.12
5.3
2879
7
0.82
CITATION
CORA (SUBELJ)
23K
92K
3
1
18K
0.12
5.8
70
0.56
CITATION
ENRON
7.9K
142K
3
7
58
861
0.16
3.1
ΕMAIL
EU-EMAIL
1K
25K
14
17
20
203
0.29
2.6
42
0.47
EMAIL
FLY LARVA
3K
116K
33
33
5
136
0.30
2.7
93
0.14
CONNECTOME
POLBLOGS
1.5K
19K
4
268
688
0.25
2.7
0.91
HYPERLINK
POKEC
1.6M
31M
8
1
326K
0.058
65
0.43
DATING
PUBMED
20K
44K
0
1
20K
0.054
6.4
0.79
CITATION
ROMAN EMPINE
23K
33K
1
1
23K
0.28
2.4K
300
18
0.05
TEXT
SNAP PATENTS?
2.9M
14M
3
181K
2.9M
0.066
0.22
CITATION
WIKIVOTE
7K
103K
2
24
5816
0.14
3.2
VOTING
HU ET AL. (2020x)
LIM ET ML. (2021)
"BOCHHESKI GÜNNEMANN (2018)
KKOOSA ISE AL. (2020)
Kuur & YANG (2004)
YIN AL. (2017)
WINDING (2023)
ADAMIC GLANCE (2005)
LESKOVEC AL, (2010)
In this regard, our work aligns more closely with Jin et al. (2019) and Corso al. (2020), who emphasize embedding concatenation as strategy for increasing expressivity. While their approaches combine em- beddings from different aggregation operators (c.g., mcan, max, sum), instead concatenate embeddings derived from multiple edge directions and walk length distributions. This preserves both interpretability and theoretical clarity, as each component of the embedding retains well-defined meaning grounded in random-walk semantics.
6 Experiments
Our experiments focus on evaluating DirSwitch and are divided into three parts. First, we validate that DirSwitch mitigates low dispersal caused by local sinks in digraphs (Section 6.1) while preserving the ability to represent directed neighbourhoods (Section 6.2). Second, in Section 6.3, we demonstrate that these improvements lead to higher-quality embeddings by evaluating DirSwitch combination with ReachNEs on node classification benchmark datasets.
Third, we evaluate DirSwitch's practical effectiveness by comparing it to recent digraph embedding models node classification benchmarks. Specifically, first assess DirSwitch with ReachNEs proximity embed- dings against state-of-the-ate unsupervised digraph proximity embedding approaches (Section 6.4). Then, in Section 6.5, we demonstrate DirSwitch's flexibility by applying it beyond the ReachNEs franework. We ex- tend self-supervised GNNs to digraphs using ReachNEs and compare this approach to the method proposed by Rossi et al. (2023), which generalizes GNNs to digraphs in the semi-supervised setting.
Our experiments use the graph learning datascts summarized in Table 2, which span diverse range of graph types and properties, including variations in densily, connectivity, and node attributes. Unless otherwise specified, we compute truncated reachability using K = 12 steps. All experiments were conducted in a Google Cloud environment with Nvidia L4 24GB GPU, 32 vCPUs @ 2.20GHz, and 128GB of memory.
6.1 Improving dispersal
To verify that DirSwitch mitigates local sinks and improves dispersal, we mcasure the reachability entropy H(j; R) -E Ri,j log, Ri, (see Section 3.1) for various reachability matrices R(P σ).. Specifically,
15

---

Published in Transactions on Machine Learning Research (06/2025)
U
OI
OIO
OU
OIU
OIOU
10.0
7,0
7.5
Entropy
Entropy
Entropy
Eatropy
5.0
6.0
2.5
0.0
0.0
0.25
100
0.00
0.25
0.50
Proportion modes
Proportion of modes
Proportion modes
Proportion of modes
10.0
10.0
Eatropy
Eatsogy
Eatropy
Eatropy
5.0
5.0
5.0
2.7
2.5
2.5
0.0
0,00
0.25
0.50
0.75
1000
0.00
0.25
0,50
0.75
1,00
0.0
0.5
10
0.3
0.5
Proportion of modes
Proportion of nodes
Proportion ofdes
Proportion of nodes
(a) Cora-ML
(b) Arxiv
(c) Wikivoles
(d) Fly Larva
Figure 6: Neighbourhood dispersal evaluation for four graphs, measured via reachability entropy,
Ei= R log, Rij, computed for each node and sorted. Each curve corresponds to different edge direc- tion specifier a,, with the top row showing results for (k; = Pois(T 2) (local dispersal) and the bottom row for U(T 5) (long-range dispersal). DirSwitch variants (e.g., DU, DIU, OIDU) demonstrate high dispersal, comparable to U, while purely directed specifiers (0, OI, 010) exhibit lower entropy due to sink effects.
compare DirSwitch edge direction specifiers a E (OU, OIU, 0IOU} against MultiDir specifiers o E {0, OI, orо} and purely undirected edges, o We use two walk length distributions: Pois(r 2), which highlights short-range differences, and U(T 5), which captures long-range behaviour.
Figure 6 presents results for four representative graphs, with additional datasets provided in Appendix E. The top row shows results for Pois(r= = 2), while the bottom row corresponds to U(T = 5).
The entropy associated with DinSwitch specifiers closely approaches that of undirected edges, which consis- tently achieve the highest entropy due to the absence of sinks. This outcome is both expected and desirable, highlighting how the switch to undirected edges mitigates the dispersal- limiting effects of local sinks.
These effects are most pronounced for long-range walks using U(T 5). shown in the bottom row. Tn Figures 6a, 6b, and 6c, there is significant entropy gap between the DirSwitch curves and the MultiDir curves (0, OI, 0IO). The Cora-ML, Arxiv, and Wikivote graphs are sparsely connected (sce Table 2), Icading to increased reachability concentration in local sinks and lower entropy. In contrast, the densely connected Fly Larva graph in Figure 6d exhibits a less pronounced but still noticeable entropy difference.
For local smoothing with Pois(r 2) (top row), the entropy increase for DirSwitch over and 0I0 is visible but small. This is because alternating 0- and I-steps allows short-range walkers to partially escape sinks. Moreover, observe discernible gap between and the DirSwitch directions. This gap reflects the reduced dispersal caused by using edge directions in the initial steps of DirSwitch random walks. As walk length increases, both effects vanish as the undirected regime of DirSwitch dominates, as seen in the bottom row.
6.2 Directed neighbourhood expressivity
We use node embedding graph alignment (Heimann et al., 2018) to verify that DirSwitch can represent the diversity of directed neighborhoods. Graph alignment is generalized version of the graph isomorphism problem, where nodes in two graphs are matched based on structural similarity (Skitsas et al., 2023).
Following the embedding benchmark protocols of Heimann et al. (2018) and Jin et al. (2021), we construct a second graph G2- (N, M2) from a given graph 91 (N, M,) by removing 15% of the edges from M,, and randomly permuting the node indices. Node embeddings then computed for both graphs and each node
16

---

Published in Transactions on Machine Learning Research (06/2025)
Undizected
Default
MultiDie-1
MuliiDie22
MultiDie-
DirSwitche-
DirSwitch-2
DirSwitch-3
0.8
0.4
0.6
Hiss00
Hibigg
Hisaat
Hibsaa
0..4
0.4
0.2
0.2
0.2
15
7- avg num walk steps
arg. num. walk steps
7- ang. num. walk steps
avg. num. steps
(a) Cora-ML, Geom(T)
(b) Cora-ML, Pois(T)
(c) Flylarva, Geom
(d) Flylarva, Pois(T)
0.6
0.6
Hite01
0.4
Hitaga
0.1
Hiseet
0.2
0.0
arg num. walk steps
avg. num. walk steps
avg. num steps
ang. num, walk steps
(e) EU-Email, Grom(r)
(f) BU-Emiil, Pois(T)
(g) WWikivotes, Geom(r)
(b) Wikivotes, Pois(r)
Figure 7: Evaluation of edge direction expressivity for four graphs using the geometric, Geom(r), and Poisson, Pois(T), walk length distributions. The y-axes represent graph alignment. accuracy under 15% edge removal, while the x-axes correspond to the average walk length. The curve colours and styles denote different sets of edge direction specifiers, a.
in O2 is matched to a node in G1 based on the shortest Euclidean distance between embeddings. This process is repeated five times with different random seeds.
The graph alignment task benefits significantly from embedding expressivity, particularly the ability to distinguish distinet directed neighbourhoods, as this reduces the risk of erroneous matches. However, for matching to be feasible, embeddings must also capture local graph structure that generalizes across separate graph components. To achieve this, we use ReachNEs message- message-passing embeddings combined with node attributes derived from graph structure, including out- and in-degrees and the four digraph local clustering coefficients- out, in, cycle, and middleman as defined by Fagiolo (2007).
We compare the multi-dircctional DirSwitch-r against MultiDir-r for I 3, well as undirected (a U) and default directed (o 0) edges. To account for the influence of walk length distribution on embedding expressivity, we evaluate both P. = Geom(T) and P. = Pois(r) for E 20, using reachability truncation of K = 30 steps.
Figure 7 presents results for four datasets, with values along the x-axes and graph alignment accuracy on the y-axes. Additional results for other datasets and walk length distributions are provided in Appendix F. DirSwitch-r and MultiDir-r achieve comparable accuracies for each r, with accuracy increasing as r grows. This similarity is expected, both methods use concatenation to represent 2" directed neighbourhoods.
A closer comparison reveals that DirSwitch-r consistently outperforms MultiDir-r, provided is not too large. This improvement stems from DirSwitch mitigating sink bias. When reachability is concentrated in small node sets, embeddings become overly sensitive to edge removal, as this can then radically change the reachability distribution. This sensitivity reduces the alignment accuracy. By alleviating this bias, DirSwitch provides more robust representations.
For the same reason, the undirected edges perform better than the default directed edges. However, overall, both these singl-nnighbourhoodd baselines achieve the lowest overall accuracies due to their inability to capture directed neighbourhood multiplicity.
Another notable observation is the impact of the walk length distribution (T(.). In all cases, accuracy collapses as + 0, corresponding to the use of node attributes without smoothing. Additionally, for the Poisson distribution, accuracy decreases as increases, whereas for the geometric distribution, it plateaus. This behaviour aligns with the expected asymptotic properties of both distributions.
17

---

Published in Transactions on Machine Learning Research (06/2025)
Table 3: Abbreviations used when reporting results for multi-scale reachability embeddings. Visualizations are available in Figure 11 in the Appendix.
ABSREVIATION
GBoM
Poss
GZoM-U
BINox-33
GBOM-4
DISTRIBUTOON, P. GBoM
=)
Possikr
Geom(k:r = 1).
B 1), Binomn(- - 2 2).
Geonal - 1:7 2), Geean/k - 2.r 3). Geazi/k 3:
Geven(k; = 1),
Ulk 1:r
Binoea(k =
In short, as increases, the mode of Pois(r) shifts continuously, emphasizing long-range walks over local smoothing. This results in less distinguishable embeddings and lower alignment accuracy. In contrast, the geometric distribution maintains local neighbourhood smoothing, preventing significant accuracy drops at higher values. See Appendix C for further details.
The difference between Pois and Geom is also evident the comparison belween DirSwitch-r and MultiDir-r. With the geometric distribution, DirSwitch consistently achieves higher alignment accuracy across varying T values, discussed above. However, for the Poisson distribution, DirSwitch's 's accuracy declines more rapidly than that of MultiDir as increases in some datasets. For instance, this effect is observed for DirSwitch-3 and MultiDir-3 in Figures 7b and 7d.
This bohaviour stems from the shifting mode of Pois. In the limit T - oc, DirSwitch embeddings converge to identical representations within a weakly connected component. In contrast, MultiDir embeddings retain finer granularity, as equivalence groups the directed case remain more distinct, see our discussion the end of Appendix C.1. This explains why MultiDir can surpass DirSwitch in alignment accuracy at large 7 values.
6.3 DirSwitch embedding quality evaluation
In this section, we demonstrate that DirSwitch's increased dispersal and multi-directionality lead to higher-quality embeddings. To assess this, we use node classification as representative downstream task, comparing ReachNEs embeddings generated with DirSwitch-r, MultiDir-r, undirected edges (U), and default directed edges (0).
Setup Table 2 lists the node classification benchmark datasets. For datasets with node attributes, we evaluate message-passing ReachNEs, while for those without attributes, we use proximity ReachNEs.
Node embeddings are computed in a fully unsupervised manner, after which a logistic regression classifier is trained on frozen embeddings. We employ 3x repeated 5-fold cross-validation strategy to obtain mean performance and standard deviations.
To assess the impact of both multi-directional and multi-scale concatenation, we include both single- and multi-scale embeddings in our analysis. Table 3 details the walk length distributions used for single- and multi-scale embeddings. We consider two single-scale distributions and three multi-scalc distributions, incor- porating two, three, and four scales, respectively. The embedding dimensions are set to p = 1024 and p = 512.
Results Overview Table 4 reports classification accuracies for message-passngg ReachNE's using datasets with node attributes, while Table 6 presents results for proximity ReachNEs for datasets without attributes, both using p= 1024. Across all datasets and embedding types, DirSwitch-r consistently achieves the highest accuracies or performs within one to two standard deviations of the best results. In the tables, we highlight the best results for each scale in bold blue and results within one standard deviation in light blue. The consistent top performance of DirSwitch across datasets and multi-scale choices underscores its superior embedding quality compared to non-switching approaches. Similar trends are observed for p = 512, with further analysis provided in Appendix G.
A notable trend is that 0 (default) yields some of the lowest accuracies across all datasets and scales, as highlighted in orange. This suggests that embedding quality improves both by using undirected edges (U) and by concatenating o = I embeddings, as done in MultiDir-1. These results further support the claim that mitigating local sinks and capturing different directed neighbourhoods enhances embedding quality.
Next, we conduct a deeper analysis of these results. To facilitate this, we use the relative accuracy improve- ments in Tables 5 and 7. These values represent the highest accuracy in each row of Tables 4 and 6, relative to the accuracy of the default. For default edge directions themselves, absolute accuracy values are reported.
18

---

Published in Transactions on Machine Learning Research (06/2025)
Table 4: Node classification accuracy for message-passing ReachNEs with p= 1024 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. Each entry reports the mean accuracy and standard deviation. Bold blue highlights the highest accuracy in each column, with light blue indicating results within one standard deviation of the best. Similarly, bold orange denotes the lowest accuracy, and light orange represents values within one standard deviation of the worst.
EDGE DIRECTIONS
ARXIV GROM-U BINOM-3
ARXIV YEAR
GROM
Pois
GBÖM-4
GEOm
Pois
GROM-Z
BINOM-3
GROM-4
DEFAULT
55.0=0.2
42.440.8
55.540.3
54.2+0.2
55.4
36.5.0.3
35.4+0.6
36.7=0.2
37.8402
38.220.2
UNDIRECTED
61.6.0.2
64.910.3
67.0.10.2
69.8...2
69.1....2
36.41...2
36.5.0.2
37.110.2
37.610.3
38.3.0.3
MULTIDIR-1
59.840.3
59.410.3
60.2
60.5=0.2
60.3
37.0.0.3
35.3.0.8
38.1
39.3
39. 39.740.3
MULTIDIR22
61.240.3
65.2 65.3+0.3
2.3.3
64.9=0.3
65.3++.3
38.5=0.3
37.9+0.4
40.9+0.2
42.0+0.2
41.7#00.
MULTIDIR-3
61.5#0.
65 05.5+0.3
65.9+0.3
65.9=033
65.7+0.3
40.0+0.3
40. 40.6
42.3+0.2
43.2+0.3
42,4+0.3
DIRSWITCH-1
61.540.3
67.3 65.910.2
69.7
68. 0..33
38.220.3
37.810.2
39.9403
40.2
41.5::0.2
DIRSwIrCH-2
61.540.3
65.8
66.91:033
69.6=0.3
68.41.0.
39.5 39.620.2
41.4
41.940.3
42.410.2
DIRSWITCH-3
61.5+0.3
65.8+0.3
66. 7:0.3
69. 09.0=0.3
0.0.3
40.0=0.3
40.9=0.4
42.4+0.3
43.3+0.3
43.3#0.3
Eag DIRICTSOOSS
Cosx-ML
Crueum
COBA
Grow
Pors
GROM-7
BIxos-33
GEoM-4]
GROm
Pois
Gros-N
BrNOM-3
Grok-4
GROM
Poss
GRoM-31
BINOM-
GROM-1
DESAULT
31.5e10
85.812.4
46.1a2
38.432.
63.233.
07.6a20
00.5.1.9
60.8.2.7
70.032.
72.9-2.1
52.4:0.0
51.220.7
57.6
09.3.0.7
60.2:0.8
UNDRRECTED
$1.221.0
41.032a
54.5217
72.1
76.1a18
76.22118
83.7a14
72.6218
68.0g1.7
89 00.0
59 42.4
64.9208
67.5
69 69.33077
60.0207
MurnDinn1
15.1
63:2158
66 06:0a91
72.2551
75.4
80.1120
80.8
73.8218
78.6417
81.0a16
64. 44.3
65.819.5
65.3210
64.8210
MULTDDIR 2
71.3e16
71.1+23
78.4214
79.8e2.1
82.3+14
79.4
78.4=12
84.3e14
85.0+13
86.0+14
07.1400
68 4507
67.849.9
66.5409
68.0en9
MacriDu-3
78.9:19
80.031.
84.0a14
88.9514
84.5113
84.773.77
87.2012
87.0
87.3
87.5a12
66.7aua
08.5gn9
68.819.
65.3110
64.4209
DreSwircH-1
56.9220
67.5424
72
62.3430
73.0a11
76.5219
91-4208
91.3=1.5
69.510.
10.1
69.7.08
DisSwircH 2
71.6s18
72.4224
80.7810
84.3516
84.421a
80.4a13
85.1=14
88.0#1.0
90.9e1.
90.1510
67.3.0.4
68 08.950.7
68.9599.5
09.0
88.0en7
DisSweren-3
79.1
80.6.1.4
84.0.1.5 86.611.6 85.711.4
84.7113
88.0...
87.7
80.610.
88.6113
66.4108
68.7gn8 07.0198
67.1a04
00.6109
EDGB DIRECTSONS
ROMAN EMPRRE
POkee
SNAP PATESTS
Guous
Paus
Grons-4
BIsOM-3
GLoMs-4
Gzus
Poss
Grost-4/
BLNOM-3
GroX-44
Guos
Poss
GuoM-4
G
DEPAULT
69.3500
32.5304
66 5300
51.250.6
67.250.8
[80.100
59.0.0a
61.750.
60.7aou
65.4.0.
35.7.0.
41.7501
39.259.1
42,2502
UNDMEETED
667.200.
46.030.7
70.9au7
66:9208
70.0a9.4
00.3300
50.6gms
62.0g13
02.3a9.
71.7:0.1
30.8
29.920.1
81.880.1
33.2:0.1
34.7.0.4
MarnDmm11
71.8a0
42.0a05
66.7.0.8
09.936.
61.350.3
00.1201
62.221
61.7a9.
67.3an1
43.9gn
45.7a9.1
47.8an2
46.9enz
Murmiim-2
71.9165
60.4107
71.1105
65.2166
75.6164
61.619.
61.1201
03.21
63.01991
09:1101
45.2101
46.5108
46.810.
49.8.0.2
48.1100
MucriDin33
73.120.6
68.0204
73.7207
60.2s07
76.050.
61.8
63.5=0.0
64.820.1
64.850.1
70.7
45.0a0.1
10.1
47.459.1
49.8507
46.5
DusSwrruu-1
73.028
58.419.
72.4a03
67.5285
74.616.
61.210.3
00.3.00
62.8211
02.8199
70.0am3
40.8an1
40.8gm1
42.7193
48.8am1
44.8203
DreSwrren-2
72.0265
62.81077
74.2305
70.8100
70.410.7
61.419.
00:0.0
03.5g01
64.1491
71.5201
46.6.201
1200
46.810.1
47.2100
47.6204
DIRSWErCH 3
72.8e00
67.9990.
75.1s0.0
72.580.
76.450.
61.6s9..
02.7
64.7 64.453.
70.3
46.3en.
30.8
49.2+0.1
49.4
48.8
Table 5: Relative improvements in node classification accuracy for muessage-passing ReachNEs with p- 1024. The values reflect the maximum accuracy for per row and dataset in Table 4. The top row displays absolute accuracies for the default edge directions, with standard deviations expressed as percentages. The subsequent rows present the relative improvements compared to the top row. The table is structured with the four homophilic datasets on the left and the four heterophilic datasets on the right.
EDGE DIRECTIONS CLR CITESEER
CORA
ArXIV
RoMaN EMPIRE|
ARXIV YEAR
PоKKс
SNAP PATENTS
DEFAULT
63.213.4%
72.9
60.2+1.1%
55.540.68 6%%
69.3+0.9%
38. 38.222.8%
65.420.4%
43.140.4%
UNDIRECTED
+20.5%
+22.0%
+ +15.5%
+25.8%
+2.2%
+0.2%
+9.5%
-19.3%
MULTIDIR-1
+19.4%
+11.1%
+9.2%
+9.0%
+3.5%
+3.9%
+2.8%
+ +11.0%
MULTIDIR-2
+30.3%
+ +18.0%
+ 13.5%
+ +17.7%
+8.9%
+9.9%
+ +5.6%
+ +15.6%
MULTIDI--3
+33.7%
+20.0%
+ +3.6%
+ +18.9%
+9.6%
+ 12.9%
+8.0%
+ +15.6%
DIRSWIrCH-1
+30.3%
+25.4%
+16.3%
+25.7%
+7.5%
+8.5%
+6.9%
+4.1%
DIRSWITCH-2
+33.6%
+24.7%
+ 14.5%
+25.4%
+10.2%
+ 10.9%
+9.3%
+ +11.7%
DIRSWITCH-3
+35.7%
+22.9%
+ +14.0%
+24.5%
+10.2%
+ +13.4%
+7.5%
+17.9%
Homophilic vs heterophilic datasets for message-passing embeddings The node classification datascts Table 2 exhibit varying levels of homophily (Zhu et al., 2020), i.c., the tendency of nodes with the same class label to connect. The homophily level is quantified in the by column, representing the average fraction of node's neighbours that share its label (Rossi et al., 2023, Eq. 1).
19

---

Published in Transactions on Machine Learning Research (06/2025)
Table 6: Node classification accuracy for proximity ReachNEs with p = 1024 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. The values denote average accuracies with standard deviations. Bold blue highlights the best results in cach column, with light blue indicating results within one standard deviation. Similarly, bold orange marks the worst results, with light orange showing values within one standard devia- tion of the lowest performance.
EDGE DURECTSONS
FLY LARVA
E.U EU-EA
POLBLOGS
GEOM
GEOX
BIxOM
GEOM-4
Pois
GEOX
GEOX 4
GBoM
Poss
GBoM
BINOM-
GBoM
DISWOLT
42.212.0
45.2.1.0
49.0...a
49.6.1.7
60.1.2.0|
3033
36.6
64.01..
66.0.224
06.0.aa
61.8
70.2
78.012.77
79.1
82.0124
UNDARECTED
45.0e17
50,0a20
60/7a2.
54.6817
55,4
29.8.8.0
35.409.7
57,2655
70.6625
72 568.
64 44.4888
76,8e20
79.1
64,3222
85,7e10
Murriba-1
47.3116
49.111.
60:811
51.119
02.011
50.2113
00:7137
08. 18.1
72.211
78.5130
78.7126
74.7286
83.611.
85.2117
86.7121
Murribin22
50.3
50.7ana
62.4
54.2580
63.6
66.8-533
60. 5..5
74.9250
75.2278
74.7and
63-4ana
844451
68.222.
68 6
50.2215
MurnDDm-3
51.8126
6266133
63.8181
53.6118
63.011-5
73.5134
74.2.9.4
74.9.93
73.1133
70.4129
88.0.1.7
88,0190
59.2114
89.7.1.5
89.81..
DieSwircH 1
48.8e17
51.0+1
50.8424
55.8+17
55.8+2.
30.9+a13
59.8e87
70.5es1
74.8+25
75.6=2.4
75 15.6+24
75.3e22
85.5+22.
86 86.6#221
80.2+22
DusSwercur22
30.3117
61.9222
64.1315
56.752.0
28.2.1.9
00.842777
09 Mas
74.6s29
70.7:2.5
74.8223
83.8222
85.2217
88. 88.4122
87.1221
89.7a16
DreSwrrem-3
52.411.7
62.811.6
56.621.8
556611
65.611.
73.3194
73.8
76.812.
72.2139
70.6198
87.011
88.411.6
80.4114
87.1190
50.8115
Eaxr DURUCTIONSS
CoCrm
PolMEn
COBa (SUBLL)
Groo
Pors
GEmx-Z
Bixow-3
GroM-4
GROM
Pois
Gross-//
BrVoM-3
Grox-4
GRou
Poss
GRoM-E
BINOM-
Grou-4
DESWORT
38.660.4
39.030.4
99.9
39.850.4
40.250.0
72.490.7
72.6.0.7
7d.3ens
70.1807
72.0ia0d
08.2.0.7
58.261.0 09.009. 09.2400
30.3en
UNDRECTED
45.32n0
45.830.6
46 46.030-
47.9206
47.630.
88199aos
82.2.00
82.21.0
82.4300
82.2.0.0
65.7.0.7
66.020.
66.750.7
07.1
07.02..
MarnDm-11 1
39.8ens
40.0iau.
40.8ena
41.3506
41,3660
72.950.0
72.7:0.8
71.5=0.7
78.7.0.7
58,3=0a
38.3
MurmDDn-2
42.5106
43.2105
43.9106
45.0106
45.016.5
77.8198
77.4.07
77.0.06
76.3194
70-7109
61.3108
61.5107
61.71966
61.6107
61.8108
ManniDm-s
43:2en5
44.7am.
44.6ana
48.4204
46.129.5
79.399
78.75m6
78.0a0
77.7au6
61.62n4
62.1207
02.429.7
02.2207
02.5207
DreSwrren-1
45.310.4
45.9300
46.920.5
48.410.4
47.950.
81.659.77
81.0200
82.0
62.3896
81.0a07
65 25.2207
65.7ans
66.0 0an.
66.4307
68.4207
DiSSwIrcH
44.9ass
45.929.
46,
88.8an8
48.3e06
18.000.4
$1.859.7
81.8007
81.8
81.953.
81.120a
64.0900
64.7208
65.1
65.64na
65.4+07
DiaSweren-3
43.8285
45.120.5
45.8an5
48.3205
47.5193
81.3208
81.4g06
80.9gKT
81.220.7
80.4206
61
81.8
62.9gns
G3.1
64.4108
63.92n9
We observe distinct differences between homophilic and heterophilic datasets in the messago-passingg results in Table 5. The three homophilic datasets Cora-ML, Citeseer, and Cora (leftmost in the table) experience 15 26% accuracy improvement when using undirected edges. In contrast, the heterophilic Roman Empire and Arxiv Year datasets show no significant improvement over default directions, while Snap Patents exhibits a 19% accuracy drop. Pokec is a partial exception, where undirected edges yield benefits with Gcom-4, a case analysed in Appendix G.
On the other hand, heterophilic datasets such as Arxiv Year and Snap Patents see substantial accuracy gains increases in DirSwitch-r and MultiDir-r. For instance, DirSwitch-3 improves accuracy by +17.9% on Snap Patents, compared to +4.1% for DirSwitch-1. Meanwhile, in homophilic dalasels, DirSwitch's accuracy remains stable across different r values.
Together, these results indicate that multi-directional representations are more important for heterophilic datasets, whereas using undirected edges is beneficial in homophilic cases. These findings align with prior obsorvations supervised graph neural networks for digraphs (Rossi et al., 2023).
This contrasting behaviour can be explained through the lens of reachability. In homophilic datasets, nodes with the same label tend to cluster locally. Removing edge directions improves dispersal and promotes local smoothing, resulting in more similar embeddings for same-label nodes and improved classification performance. This effect is illustrated in Figure 2.
In heterophilic graphs, however, capturing local connectivity patterns that repeat across different regions is essential for distinguishing node roles. Here, multi-dircctional approaches play a crucial role, as discard- ing edge direction information can introduce spurious similarities between nodes with distinct, direction- dependent neighbourhoods.
Sparse vs dense graphs for proximity embeddings We next analyse classification accuracies for proximity embeddings in Table 7, observing distinct trends based on graph density. Denser graphs (Fly Larva, EU-Fmmill, and Polblogs) benefit more from multi-directional emboddings, whereas sparser graphs (CoCite, Pubmed, and Cora (subeli)) achieve higher accuracies when dispersal is increased using undirected edges. For instance, the sparse CoCite graph improves by 19% with undirected edges, with similar 20% improvement
20

---

Published in Transactions on Machine Learning Research (06/2025)
Table 7: Relative improvements in node classification accuracy for proximity ReachNEs with p == 1024. The values reflect the maximum accuracy for per row and dataset in Table 6. The top row displays absolute accuracies for the default edge directions, with standard deviations expressed percentages. The subsequent rows present the relative improvements compared to the top row. The table is structured with the three denser graphs on the left and the three sparser graphs on the right.
EDGE DIRECTIONS
FLY LARVA
EU-EMAIL
POLBLOGS
||
COCITE
PUBMED
CORA (SUBELJ)
DEFAULT
50. 13..9%
66.014.8%
82.012.9%
40.211.2%
73.31100%
59.3.11.%
UNDIRECTED
+10.6%
+9.8%
+4.5%
+19.0%
+12.4%
+13.2%
MULTIDIR-1
+3.9%
+11.3%
+5.8%
+2.7%
+0.8%
-1.0%
MulrIDm-2
+8.2%
+14.0%
+88.8%
+11.9%
+6.1%
+4.3%
MULrIDIr-3
+7.5%
+13.4%
+9.5%
+15.5%
+8.2%
+5.4%
DIRSwrrcu11
+11.5%
+14.5%
+5.6%
+20.2%
+ +1233%
+12.1%
DIRSwircH22
+13.2%
+14.7%
+9.4%
+20.2%
+11.7%
+10.7%
DIRSwIrCH33
+11.1%
+14.0%
+9.5%
+20.2%
+11.0%
+8.6%
for each DirSwitch model. Conversely, the dense Polblogs graph gains only 4.5% from undirected edges but 9.5% boost with DirSwitch-3.
This difference between dense and sparse graphs can be explained by reachability entropy. Even with purely directed edges, entropy remains high for the dense Fly Larva graph (see Figure 6d), indicating that local sinks do not significantly hinder dispersal. A similar pattern observed for EU-Email and Polblogs in Appendix E, explaining why undirected edges provide less benefit in these graphs.
Instead, increasing embedding distinguishability by representing directed neighbourhoods becomes more important. Comparing default edges and DirSwitch-1 in Table 6, we observe significant accuracy gains when transitioning from single-scale to multi-scale walk length distributions. For example, Polblogs achieves only 61% accuracy with single-scale Geom but improves to 82% with multi-scale Geom-4. Conversely, sparser datasets show only minor improvements with multi-scale embeddings, with dispersal remaining the primary factor influencing embedding quality.
Further analysis Additional discussion of these results is provided in Appendix G, where we examine the accuracy improvements from multi-scale embeddings, the diminishing returns of repeated concatenation and perform further analysis of the results for the Pokec dataset. We also present evaluation results using unsupervised community detection as an alternative to node classification.
6.4 Comparison to state-of-the-ard digraph proximity embeddings
We compare DirSwitch with proximity ReachNEs embeddings against state-of-the-art unsupervised digraph proximity embedding approaches discussed in Section 5.3. Hyperparameters for each model are optimized via cross-validation grid search, with the search grids and best values reported in Appendix D.2.
Table 8: Node classification accuracics for proximity node embodding models. Bold indicate the top accuracy, and results within standard deviation, for each dataset. Average and standard deviations are calculated over 3x repeated 5-fold cross validations, and 5 different random seeds.
MODEL.
FlylaRvA
EU-EMAIL
POLBLOGS
CoCITE
PUBMED
CORA (SUBELJ)
HOPE
35.8 + 1.9
49.3
83.2 3.1
30.4 1.2
65.3 0.9
34.0 0.8
APp
42.8 2.3
76.3 2.8
88.9 + 1.7
46.7 + 0.5
81.2 0.6
65.6 1 0.7
NERD3
40.3 2.2
71.3 3.2
89.4 1 1.7
28.1
76.5 1 0.7
45.7 1 0.6
DGGAN"
16.5 16.5+1 1.4
11.7 2.5
54.6 2.9
17.
41.5 0.9
6.2 0.3
BLADE
49.2 2.2
66.7 3.0
89.3 1.9
24.2 0.5
60.2 1.2
27.7 + 1.0
DIRSWITCH
56.8
75.6 2.7
1.7
48.3 1 0.5
82.2 0.6
66.6 - 0.7
Ou AL. (2016)
ZBoU AL. (2017)
KHOSLA (2020)
ZZu AL. (2021B)
ViRINom & SALADI (2023)
21

---

Published in Transactions on Machine Learning Research (06/2025)
Table 9: Node classification accuracy for self-supervised GraphSAGE embeddings using training via Graph- MAEv2 and CCA-SSG losses. Bold indicate the top accuracy for each dataset. Average and standard deviations are calculated over 3x repeated 5-fold cross validations and different seeds.
(a) GraphMAEv2
EDCE DIRECTIONS
HOMAN EMPIRE
ARXIV YEAR
POxEC
SNAP PATENTS
CORA-ML
CITESEER
CoRA
ARXIV
DEFAULT
66. 09:9079
11.49
61.62=0.20
45.68
79. 79.61#1.76
80.1341.28
39.48:2.61
59.81
UNDIRECTED
68.
40.08
65.99
83.0077000
86.03+1.42
90.71=0.02
68.54=0.74
70.49=0.28
RossI ET (2023)
46.38
$7.93
01.3410.28
81.8843.94
87.5342.00
34.35:444442
65.53340.52
DIRSWIrCH-1
76
41.28
67.16.0034
1900000
85.7911.48
89,
68
09.95-10.21
DIRSWITCH-3
7..90=0.78
46.65
67.57
57.99.0.21
85.24+1.77
86.6741.06
66.31#0.80
68. 00.00.22
(b) CCA-SSG
EDCE DIRECTIONS
HOMAN EMPIRE
ARxIV YEAR
PoxEc
SNAP PATENTS
CORA-ML
CIteseer
CoRA
ARxIV
DEFAULT
45.01
58.07=0.27
46.37=0.25
61.70+3
69.72+
39.70+0.91
36.731
UNDIRECTED
53, 23.45
35.82=0.25
60.38=0.74
82.64+1.59
80.71#1.06
32.
45.9331116
RossI (2023)
53.7440075
46.8320.41
60.54:0.50
65.55=0.28
60.44:2291
64.64:2.41
31.28#22.21
34.9240.54
DIRSWIrCH-1
2.2.76
45.19
66, 200000
=4000
12.00=11776
77.35+22.68
32.70#1.28
61. 61.63##0.38
DIRSWIrCH-3
66.39-1.22 1.24
52.64:00.50
87.25:t0.21
64.08=0.19
82.27
85.26
61.07:00.80
63..8=00.30
Following hyperparameter tuning, test accuracy is evaluated using the best hyperparameter setting on new 3x repeated 5-fold CV splits, with five different random seeds per model. We use the official implementations for all baselines except BLADE, which we reimplement as its source code is not publicly available.
Table presents the average test accuracies and standard deviations for each proximity embedding dataset. DirSwitch consistently achieves the highest average accuracy across datasets performs within one standard deviation of the best model (EU-Email). Notably, DirSwitch outperforms competing approaches by signif- icant margin on Fly Larva, achieving 57% accuracy compared to 49% for BLADE. These results highlight DinSwitch's Is ability to leverage both multi-directional and multi-scale emboddings while avoiding local sinks, distinguishing from prior proximity embedding models.
6.5 Applying DirSwitch to self-supervised message- message-passing graph neural networks
DirSwitch is not limited to the ReachNEs framework and can also be applied to message-passing graph neural networks (GNNs). The most natural integration is with the GraphSAGE model (Hamilton et al., 2017), given its struetural similarity to ReachNEs. By defining H 7 = X, we represent the DisSwicch-GrapphAAE.. model using the following iterative formulation, analogous to Equation 6:
((k) = (+H( ((k) = w((-)) + H
For h: E (1,2,....
(10)
The key differences are the weight matrices Wi and W2, which replace the walk length probability coeffi- cients, and the non-linear activation function a.
For training the weight matrices, we employ self-supervised learning, the current stato-of-the-art approach for unsupervised GNN training. These loss functions typically combine reconstruction and contrastive learning objectives. In our experiments, and CCA-SSG (Zhang et al., 2021a). We adopt the default hyperparameters for both loss functions and optimizers, as recommended by the original implementations. We train DirSwitch-1 and DirSwitch-3 models but exclude DirSwitch-2 due to the high computational cost of GNN training.
two recent and efficient methods: GraphMAEv2 (Hou et al., 2023)
As basclines, we compare against GraphSAGE with default (0) and undirected (U) edges, as well as the digraph extension of GraphSAGE proposed by Rossi al. (2023). Like DirSwitch, Rossi et al. (2023) incorporates multi-directional neighbourhoods but does not include switch to undirected edges.
22

---

Published in Transactions on Machine Learning Research (06/2025)
Unlike ReachNEs, GNNs typically use a small mumber of aggregation steps to balance computational ef- ficiency and mitigate over-smoothing (Chen et al., 2020). We set K = aggregation steps, following the default in GraphMAEx2 (Hou et al., 2023).
Table 9 presents the results for GraphMAEv2 and CCA-SSG. As observed in the ReachNEs experiments (Section 6.3), performance varies qualitatively between heterophilic and homophilic datasets, with undirected edges generally performing better in homophilic cases. This is particularly evident in Cora, where DirSwitch and undirected edges significantly outperform both the default edges and Rossi et al. (2023).
The only dataset where Rossi et al. (2023) surpasses DirSwitch in accuracy is Snap Patents. As shown in Table 5, using undirected edges causes a substantial accuracy drop for Snap Patents in ReachNEs, and the same trend is observed with GraphSAGE.
7 Limitations and future work
This work addresses two key challenges in digraph embedding: the cispersal-bbstructing effects of local sinks and the need for expressive embeddings that capture multiple directed neighbourhoods. A limitation of our approach is its reliance on embedding concatenation to achieve both multi-directionality and multi-scale representation, which incurs notable computational overhead. While our results suggest. that few directed neighbourhoods and scales are often sufficient due to the typically short characteristic path lengths of real- world networks (Watts & Strogatz, 1998)- work is needed to better quantify diminishing returns and to explore more efficient alternatives to concatenation. Additionally, other structural properties of digraphs, such as the role of cycles and self-loops, may be equally important and deserve further investigation.
For tractability, our analysis considered graphs with a single type of supplementary information: node attributes. In reality, graphs are often far more complex, incorporating multiple edge types, attributed edges (as knowledge graphs (Wang et al., 2017a)), or temporal dynamics where edges evolve over time. While we expect the DirSwitch principle, i.e., separating short-range and long-range behaviours, generalize to these cases, addressing expressivity in multi-modal graphs will likely require specialized techniques beyond our current concatenation approach.
Another limitation lies in the embedding reduction methods explored. We focused on two widely used techniques: node altribute smoothing for message-passing embeddings and SVD for proximity embeddings. However, other reduction methods, such as structural embeddings, remain unexplored in our analysis. In- vestigating how local sinks and multi-diroctional emboddings affect alternative roduction techniques is an important avenue for future research, especially since much of the existing work on structural embeddings is limited to undirected graphs (Donnat et al., 2018; Zhu et al., 2021a; Jin et al., 2021).
Finally, while our benchmark evaluation demonstrates DirSwitch's effectiveness, its real-world utility in unsupervised tasks such as node clustering or anomaly detection remains underexplored. These tasks of- ten lack well-defined ground-truth labels, making evaluation challenging and necessitating further research. Expanding DirSwitch to these domains presents exciting opportunities for future work.
8 Conclusion
In this paper, we analysed unsupervised node embedding learning on digraphs through our reachabillty- random walk filter framework, ReachNEs. Our analysis identified two key challenges: local sinks obstruct information propagation, while embeddings must also represent directed neighbourhoods to be expressive.
To address these issues, we introduced DirSwitch. By decoupling local and global smoothing, DirSwitch preserves fine-gra grained directed structure through multi-directional embedding concatenation, while treating the graph as undirected for long-range interactions to mitigate the impact of local sinks.
We retenstrated that DirSwitch significantly enhances embedding quality, achieving higher accuracy on standard node classification benchmarks. Additionally, we showcased its practical effectiveness by outper- forming stato-of-thee-rt unsupervisod proximity embedding models. Finally, we highlighted DirSwitch's 's broad applicability by using it to generalize self-supervised graph neural networks to digraphs, illustrating its flexibility across different embedding paradigms.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We would also like to thank Petra Poklukar, Marcus Klasson, Aniss Medbouhi, and Miguel Vasco for their valuable feedback and support in improving this paper.
References
Lada A. Adamic and Natalic Glance. The Political Blogosphere and the 2004 U.S. Election: Divided They Blog. In LinkKDD 10,, pp. 06-43, 2005. URL https: http:///ooooro....1//// 100...115111111 /tth//113422..111 11342777..
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In SODA '07, pp. 1027-1035, 2007. URL https://dl. acm. wttp:o///t......////////// 0tw../555//13333..8 1283494.
Albert-T.ás26 Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, 286(5433): 509 512, 1999. URL
http://ciiieee..r////aaaaa////// 1126/science. 283.2439........ 5439.509.
science. org/doi/abs////
Alcksandar Bojchevski and Stephan Günnemann. Deep Gaussian Embodding of Graphs: Unsupervised In-
ductive Learning via Ranking. In ICLR'18, 2018. URL http://pppaarrreeeeeettttoorrr/p
Stephen P. Borgatti and Martin G. Everett. Notions of Position in Social Network Analysis. Sociological methodology, 22:1 15, 1992. URL https://dof htt:///di.oor///////// 2307 /770911.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometrie Deep Learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017. URL
https://doi. orgo 10. 1109/MSP. 2017 2693418.
Ciwan Ceylan, Kambiz Ghoorchian, and Danica Kragic, Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphs, 2022. URL http:::///oo..o/11.44445833 arXiv.
2207.10149.
Sudhanshu Chanpuriya and Cameron Musco. Infinitewalk: Deep Network Embeddings as Laplacian Embed- dings with Nonlinearity. In KDD'2, 20, pp. 2225-133, 2020. URL https://doi... www..ogg///../ 1145/33948/ 3403185.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. AAAI22,, 34(04))3438-388 3445,,445 2020. URL bttps://ddi.org/// wr.//0. 1609/aaai. v34104.5747.
Fan R.K. Chung. Spectral graph theory. Number 92 in Regional conference series in mathematics. American org/ 10.. h3000/cms/099
Mathematical Society, 1997. URL
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovie. Principal Neighbourhood Aggregation for Graph Nets. In NewrIPS'20 20, 2020. URL https: /ttp::///ooooo//////1100 48550/arXiv. 1885///////....//......... 2004. 2004.05718.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Ltd, 2nd edition, 2005. URL https://doi. http://di..ogg//g// 100//0000000///7778888
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In NeurIPS'16, 2016. URL attps://proceedings newrips.errrccccc pdf..
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning Structural Node Embeddings Via Diffusion Wavelets. In KDD'18, pp. 1320-1329, 2018. URL https://doi org/ /0. 1145/3219911. 3220025.
Giorgio Fagiolo. Clustering in complex directed networks. Physical Review E, 76(2), 2007. URL https: aedoi.org/11 11133//1sse....1.... 76. 026107.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. ACM SIGCOMM Computer Commanication Review, 29(4):251-22) 262, 1999. URL https://doi. org/10.1145/316199 3166229.
Matthias Fey and Jan F. Lenssen. Fast Graph Representation Learning with PyTorch Geometric. In ICL.R Workshop on Representation Learning on Graphs and Manifolds, 2019. URL BtR.ttts::/dde org/10..///. 488550 MrXiv.1903. 19422.
Michael Fire and Carlos Guestrin. The risc and fall of network stars: Analyzing 2.5 million graphs to reveal how high-degree vertices emerge over time. Information Processing and Management: an International Journal, (2), 2020. URL /tstpp://do..ee
1016/j ipm. 00....0..0....
Justin Gilmer, Samnel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. In ICML'17, pp. 1263-1272 2017. URL. https://proceedingg mlr. press/v70/ press//70/g.1Imr117a. http://mmmmmaaaaaama.a html.
Gene H. Golub and Charles F. Van Loan. Matriz Computations. Johns Hopkins University Press, 4th edition, 2013. URL https://epubl siam. http:////oooo...11/.......
Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, 63 (11):128 134, 2020. URL https://doi.org: wwt.oo///...../...... 111/337773///
Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. In An Introduction to Lifted Probabilsttcc Inference. The MIT Press, 08 2021. URL https://doi.org org/10/ 10. 7ttp:///tprees/1155555551 00..8.0000000220.
Aditya Grover and Jure Leskovee. node2vec: Scalable Feature Learning for Networks. In KDD'16, pp. 855-864, 2016. URL https://doi.org: 100...114/299977 2939754.
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding Structure with Randomness: Proba-
bilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53(2):217-288, 2011. URL
Brian C. Hall. The Matrix Exponential. In Lie Groups, Lie Algebras, and Representations. Springer Cham, 2015. URL
319-13467-3.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NewrIPS'17, volume 30, 2017. URL
48550/aaXiiv... wtt.:.77..0221111 02216.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive Multi- View Representation Learning Graphs. In TCML 20, pp. 4116-4126, 2020. URL https://proceeddng:: mlr http.pereee//111//saaan/000
http://ppoeeeegggg....rrressss/p html.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Flements of Slatistical Learning. Springer New York, 2nd edition, 2009. URL
Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation Learning Based Graph Alignment. In CIKM'18, pp. 117-126, 2018. URL https://doi.org//// 1145/3269206 3271788.
Nicholas J. Higham. Functions of Matrices. Society for Industrial and Applied Mathematics, 2008. URL https://doi. http:///dooooog//.... 1137711
Michiel F. Hochstenbach. A Jacobi-Daviin type method for the generalized singular value problem. Linear Algebra and its Applications, 431(3):471 1874477-7777- 2009. URL attps://dos http:////ii..og/0.111/////////// ,la. 2009. 03. 003.
Roger A. Horn and Charles R. Johnson. Matrir Analysis. Cambridge University Press, 2nd edition, 2012.
URL attps://dot: http:////o.oor//..111o/ brg/100.111/97711199222
Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. GraphMAE2: A Decoding-Enhanen Enhanced Masked Superviid Graph Learner. In WwW'23, pp. 737-746, 2023. URL /ttp::////oi.or//0.... htt.a////r.....11/335/000..000
ottp: 358333777777..
25

---

Published in Transactions on Machine Learning Research (06/2025)
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Teskovec. Open Graph Benchmark: Datasets for Machine Learning Graphs. In NewrIPS pp. 22118 22133, 2020a. URL https://doi... org/10 /85.0///r2...200000 200.. 00005.00687.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for Pre-training Graph Neural Networks. In ICLR 20, 2020b. URL https://openreete net////wwweeeeeeeeeeee....ee
Ferrm?id-HJIwwA.
Elvin Isufi, Fernando Gama, David I Shuman, and Santiago Segarra. Graph Filters for Signal Processing and Machine Learning Graphs. IEEE Transactions Signal Processing, 72:4745 4788,, 2024. URL https://dol org/ 1////0.110000 1109/TSP..P.. 2024. 3349788.
Di Jin, Ryan A. Rossi, Eunyee Koh, Sungchul Kim, Amup Rao, and Danai Koutra. Latent Network Sum- marization: Bridging Network Embedding and Summarization. In KDD'19, pp. 987-997, 2019. URL https://doi.. htw./oi..rgggg// 2org/1..// /ttgg/...1.///////....... 1145/3292500 33339999 3330992.
Junchen Jin, Mark Heimann, Di Jin, and Danai Koutra. Toward Understanding and Evaluating Structural
Node Embeddings. ACM TKDD, 16(3), 2021. URL http:///ddo..or11.114111////
Megha Khosla, Jurck Lconhardt, Wolfgang Nejdl, and Avishok Anand. Node Reprosentation Learning for Directed Graphs. ECML PKDD 2019, pp. 395 411, 2020. URL https://doi. htt.ddi..og/1...0077770.
978-3- 978-3-030-4555 0-0-3-000-441----2220 8_240-8_2.
Thomas N. Kipf and Max Welling. Semi-supervised Classification with Graph Convolutional Networks. Tn ICLR'17. OpenReview, 2017. URL
Bryan Klimt and Yiming Yang. The Enron Corpus: A New Dataset for Email Classification Research. Tn ECML'0, 04, Springer Berlin Heidelberg, 2004. URL https://doi. 1000:00000000000---0000--1----10
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix Factorization Techniques for Recommender Systems. Computer, 42(8):30 37, 2009. URL https://doi. http://......g/.1...1////.....00 .263.
Jure Leskovee, Daniel Huttenlocher, and Jon Kleinberg. Signed Networks in Social Media. In CHT'10, 2010.
URL https://doi 0rg/10./// http:/1..1111/// 1145/1753326 1753532.
Pan Li and Jure Leskovec. The Exprcssive Power of Graph Neural Networks. Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao (eds.), Gruph Neural Networks: Foundations, Frontiers, and Ayplications, chapter 5. Springer Singapore, 1st edition, 2022. URL attps://don www.oorgg/.o...... 100011007/777880000000 9778-988--65 1811-16-605---5
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang. Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large Scale Learning on Non-Hommphilous Graphs: New Benchmarks and Strong Simple Methods.
NeurlPSS21, 2021. URL https: //ppnreviee. wwt.///ooruureeeeeeeeeetto
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the con- struction of internet portals with machine learning. Information Retrieval, 3:127 163, 2000. URL https:://doi.or//000/ 1023/A/ 1009953814988.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed Representations of Words and Phrases and their Compositionality. In NewrIPS'13, 2013. URL https://proceeding: pdf.
neurips.cc/ http:/ppp...aappppro//////////aa
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher- Graph Neural Networks. In AAAP'19,
2019. URL https://doi... www.oo......ooooooooooooo..oo... 1009/ www..1........... 33014602.
Kevin P. Murphy. Machine Learning: A Probabilistic Perspective.
MIT press, 2012. URL https:
mit.
Mark Newman. Networks. Oxford university press, 2nd edition, 2018. URL https:///ol. ott...oog/10.003//
080/997201988000000000000000
26

---

Published in Transactions on Machine Learning Research (06/2025)
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric Transitivity Preserving Graph Embedding. In KDD'6 pp. 1105-1114, 2016. URL https://doi. 11/////1...0 2.0.1145/233967.22000 29397511
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web, Technical Report 1999-66, Stanford InfoLab, 1999. URL http://ilpubs. stanford. edu: 8090/422/.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Parformance Deep Learning Library. NewrIPS'19, pp. 8024-8088 8035, 2019. URL https: //dl. acm. org. /dti//ooi/.... 5555/545453/7777 3455008.
Bryan Perozii, Rami AI-Rfou, and Steven Skiena. DeepWalk: online learning of social representations. In KDD'14, pp. 701-710. Association for Computing Machinery, 2014. URL https: org/10 1145/ 2623330 2623732.
Kaare Brandt Petersen and Michael Syskind Pedersen. The Matrix Cookbook, 2012. URL compute. dtu. dk/
ppbbs/274-ffl111 htmm..
html. Version 20121115.
Jiezhoug Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and Node2vec. In WSDM'18, pp. 459-467, 2018. URL https://doi.org:: org./io.org/0/// 10. 100.1115/15555..111111
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. Edge Directionality Improves Learning on Heterophilic Graphs. In LoG '2, 2023.
URL /ttp:::://doo..r////// http://i...rr/11..4/////////////
48550/arXiv. 2305. 10498.
Ryan A. Rossi, Di Jin, Sungchul Kim, Nesreen K. Ahmed, Danai Koutra, and John Boaz Lee. On Proximity and Structural Role-Based Embeddings in Networks: Misconceptions, Techniques, and Applications. ACM TKDD, 14(5), 2020. URL https://doi: org/10. 1145/3397191
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Journal of Complez Networks, 922,, 2021. URL https: //t:://doiio org. /0/ 11t.//....1111// 10t.1//////mm///aaa///..
Tim Sainburg, Leland MeInnes, and Timothy Q Gentner. Parametric UMAP Embeddings for Representation and Semisupervised learning. Neural Computation, 33(11)22881-2907, 2021. URL attps://dol org/10. 1162/neco__ 011434
Konslantinos Skitsas, Karol Orlowski, Judith Hermanns, Davide Mottin, and Panagiotis Karras. Com- prehensive Evaluation of Algorithms for Unrestricted Graph Alignment. In EDBT'23, 2023. URL
(0o..o0//11.4.7///eet5. 48786/edbt. 21.
Balasubramaniam Srinivasan and Bruno Ribciro. On the equivalence between positional node embeddings and structural graph representations. In ICLR 200 2020. URL http://pppneeveeeeeeeeeeeeeeeeee SJxzFySKWH.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 6, 2012. URL https: //amap.stanford stw.ford...oo.. wet.rddddddddaaaa///aaa sachu/dat//soc-aaaa Poceco.oo...tlll
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Remi Munos, Petar Veličkovié, and Michal Valko. Large-Scale Representation Learning on Graphs via Bootstrapping. In ICLR 22, 2022. URL nttps://dol org/ 10. 48550/arXiv. 2151.06514.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Roscnblum, and Andrew Lim. Digraph Inception Convolutional Networks. In NeurIPS'20, volume 33, pp. 17907-17918, 2020. URL https://
www.eediinnnneurissccom http://sss.....c...o/o.ooooaaaan
27

---

Published in Transactions on Machine Learning Research (06/2025)
J. J. Peter Veerman and Robert Lyons. A Primer Laplacian Dynamics in Directed Graphs, 2020. URL https://doi.. arrg10..4855/ar/kk 2002. 02605.
Srinivas Virinchi and Anoop Saladi. BLADE: Biased Neighborhood Sampling based Graph Neural Network for Directed Graphs. In WSDM 23, pp. 42 50, 2023. URL httpp://di htwp///dd.cc.ac//////c//////o acm. 0rr.//0//000...1115555577 1145/3539777 3570430.
S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph Kernels. Journal of Machine Learning Research, 11(40):1201-1244 1242, 2010. URL http://jmlr papprs/vi// vishwanathan httm..
Uhrike von Luxburg. A tutorial on spectral clustering, Statistics and computing, 17(4):395 416, 2007. URL https://doi.. oaa.l..rggg... 10. 10001000010222000000000000
Haonan Wang, Jieyu Zhang, Qi Zhu, Wei Huang, Kenji Kawaguchi, and Xiaokui Xiao. Single-Pass Con- trastive Learning Can Work for Both Homophilic and Heterophilic Graph. Transaclions on Machine Learning Research, 2023. URL
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge Graph Embedding: A Survey of Approaches and Applications. IEEE Transactions on Knowledge and Data Engineering, 29(12):2724-2748, 2017a. URL
bttps::/ddo..rg///
1109/TKDE. 2017 2754499.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community Preserving Network Embedding. AAAI11, 35(1), 2017b. URL //ojs://ojs aaai org/ perg/indxx.. http//innxxxpp/.iiaeeeee php/AAAT/arttcll/ view/10488.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world" networks. Nature, 393(6684): 140-442, jun 1998. ISSN 1476-4687. doi: 10. 10.1038/30918 URL https://ww. nature. cww/ anticesil 30918.
Michael Winding, Benjamin D. Pedigo, Christopher L. Barnes, Heather G. Patsolic, Youngser Park, Tom Kazimiers, Akira Fushiki, Ingrid V. Andrade, Avinash Khandelwal, Javier Galdes-Aleman Feng Li, Na- dine Randel, Elizabeth Barsotti, Ana Correia, Richard D. Fetter, Volker Hartenstein, Carey E. Priebe, Joshua T. Vogelstein, Albert Cardona, and Marta Zlatic, The connectome of an insect brain. Science, 379 (6636), 2023. URL attps://don org/10. 1126/science a3933333
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying Graph Convolutional Networks. In ICML 19, pp. 6861 6861-6871, 2019. URL https://doi /ttp///oi..or/10.44885/5/5/ arXiv. 1ww..1902..... 17153.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? International Conference on Learning Representations, ICLR'19. OpenReview.nee 2019. URL https:
//openreview.o / http://ootooiididrrr.......
Yuchen Yan, Yongyi Hu, Qinghai Zhou, Lihui Liu, Zhichen Zeng, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, and Hanghang Tong. PaCEr: Network Embedding From Positional to Structural. WWW'24, pp. 2485-2496. Association for Computing Machinery, 2024. URL https://dol org/10. 10.
1145/558933..36555
Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local Higher-Order Graph Clustering, In KDD'12 17, pp. 555-564, 2017. URL btttps///oo..oo 1tt///...1///397998333 /00.//99999933.00669.. 3098069.
Wenjian Yu, Yu Gu, Jian Li, Shenghua Liu, and Yaohang Li. Single- PCA of Large High- Dimensional Data. In IJCA'17, pp. 3350 3356, 2017. URL attps:///of itt.://a............/........... 2067/468.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Yu Philip. From Canonical Correlation Analysis Self-supervised Graph Neural Networks. In NewrIPS'11, 2021a. URL https://doi. org.l.rr......// 48550/ arXiv. 2148.12484.
28

---

Published in Transactions on Machine Learning Research (06/2025)
Xitong Zhang, Yixuan Hc, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. MagNet: A Neural Network for Directed Graphs. In NewrIPS'21, volume 34, pp. 27003-27000 2021b. URL https://doi.
4rg/10.48550/ara arxiv. 22022. 11391.
Chang Zhou, Yugiong Liu, Xiaofei Liu, Zhongyi Liu, and Jun Gao. Scalable Graph Embedding for Asym- metric Proximity. AAAI'7, 31(1), 2017. URL https://doli org/10 1809/ 13111.10877
Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node Proximity is All You Need: Unified Structural and Positional Node and Graph Embodding. In SDM'21, pp. 163-171, 2021a. URL https://doi.org
10. 1011117//11 / 97811119771111111111 19.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond Homophily Graph Neural Networks: Current Limitations and Effective Designs. In 200rIPS'20, 2020. URL https://doi org/10. 10. 48550///2....2200 2006. 11468.
Shijie Zhu, Jianxin Li, Hao Peng, Senzhang Wang, and Lifang He. Adversarial Directed Graph Embedding, A AAAI 22, 3574):4741 4748, 2021b. URL https://doi.or: / /aa9///aa..... aaaii.33i5. v3515.16605.
29

---

Published in Transactions on Machine Learning Research (06/2025)
A Additional details on ReachNEs and DirSwitch
A.1 Verification of column stochasticity of the random walk normalized adjacency matrices
In Section 2.1, we defined the random walk normalized adjacency matrices follows:
1
if i = j and dego(i) = 0, he
i- and degr(i) 0,
Aos.j
AIi.
Aig (3)
Asi (3)
otherwise,
if = and deg(j) = O,
Auij
Aundiri. deg(i)
otherwise.
These definitions ensure that each matrix is column stochastic, meaning that each column sums to one. We verify this property below:
if dego(j) = 0
if dego (j) = 0
Aokj
Ek=1 And
if dego(j) > 0
digg(i)
if dego (j) > 0
1,
dego(s)
deg. (i)
if degz(f) =0
if degr (j) = 0 if deg, (/) > 1,
AreJ
Ek=z Aj.
if deg.()) (j) >
(e) deg.(r)
1=1
degi(i)
if deg(j) =
if deg(j) 0
ADke
Ek Aundirk.j
deg(j) >
deg())
if deg(j) 1.
de
deg
A.2 ressage-passingg embeddings for directed edges
In Section 2.3.2, we highlighted the connection between the reachability message-passingg reduction using R(Au) and the undirected message-passing graph neural network GraphSAGE (Hamilton et al., 2017) in Equation 7. Here, we present the corresponding formulas for directed cases:
AJ DD AH
[
Σ
Ao HJ, dego(i) Σ H jilLstM
(11)
f=1
1
AiH DI AH,
Σ
A A1 Hj: degr(i)
ΣH
H
(12)
FUJEMM
Note that in Equation 11, messages aggregated over outgoing edges of node meaning that they flow op- posite to edge directions. Conversely, in Equation 12, messages are aggregated along the incoming, following the edge directions.
A.3 Proximity embeddings and structural equivalence
We extend Section 2.3.1 by deriving Equation which relates the distances between reachability vectors in to distances between embedding vectors in Z [Zu Zv]. For convenience, we restate the equation:
Σ Σng
Ra. R3a112 RRR,. R. 122
Zi. 2,
5
(13)
2
Σ Egg.g
Assuming rank(Fr R) = 9, the n smallest singular values vanish, leading to:
U...g v Eig.oy V.rgVE.ge " Zu Zu
R U. Un. E.g.
30

---

Published in Transactions on Machine Learning Research (06/2025)
We can then express each row of R as the inner product between the corresponding row in Zu and Zv, and similarly, each column of R can be expressed as the inner product between row in Zv and Zu:
R Zui Zv.
R Zu (Zvi.)"
We now derive Equation 13, using the simplified notation U
U 1,1g. Σ = E.g.g and V Vaggi
R R2:112 + ||R,, - R2 Zui ZV Zu Z 11 + (Zv Zu (Zv v.:.:) 1
(14)
(Zui: Zu,,) 21
Zz (Zv )
(15)
(Zui: Z.s.) VEVT
| UVE Σ (Zvi: zvz
(16)
2
(Zui: ZUi V
+ ||
Σ Zvvi: Zv v.:) 112
(17)
Ek,t (Zu Zu,,,)² +
Di,k (Zv i, z,zx)²
(18)
k=
2g
Ei (Zi,k - -zg,x?
(19)
k=1
ZZi - Zg.i) V 2
(20)
The transition from Equation 16 to Equation 17 follows from the orthogonality of U and V, ie., UTU = 1 and VIV I
A.4 Computational complexity of ReachNEs
In this section, we discuss the time and memory complexity of ReachNEs and how to efficiently implement it for embedding learning on large graphs. The primary computational bottleneck is the n x n reachability matrix R, which generally dense. Storing R explicitly infeasible for even moderately large graphs for instance, a graph with one million nodes would require over 3TB of memory.
For message- paaigge-pasinggggge embeddings, the iterative algorithm described in Equation 6 offers practical way to bypass the need to store R explicitly, For convenience, we restate it below:
(k) (+-1) (()) 2(k-) + (*)
For k E (1,2....).
}.
H H = X, Z = Po)
(21)
Rather than computing R in full and multiplying it with the node feature matrix X E Raxd this iterative formulation directly constructs the embedding matrix ( RT X through sequential summation. This re- duces the memory complexity from quadratic to linear, specifically O(nd-m), where nd accounts for the em- bedding matrices (k) and (1), and m is the number of non-zero entries in the sparse adjacency matrix A.,
The time complexity of the iterative message-passing algorithm in Equation 21 is O(Kmd+ + Knd), where md arises from the sparse-dense matrix multiplication (k-1),,, and nd comes from the embedding summation update. Both operations are efficiently supported by existing GPU libraries (Paszke et al., 2019; Fey & Lenssen, 2019), making the method highly practical in large-scale settings.
By contrast, proximity ReachNEs presents greater memory challenges. Both standard and randomized SVD methods (Halko et al., 2011) require multiple passes over all elements of the input matrix, which is problem- atic since storing R in memory is intractable, and recomputing it on-the-fly is computationally prohibitive.
To address this, we adopt the single-pass rendomized SVD (SP-rSVD) algorithm proposed by Yu et al. (2017). SP-rSVD follows the general structure of randomized SVD (ISVD) (Halko al., 2011), but avoids multiple passes over the input. First, the reachability matrix R is projected into lower-dimensional subspace via
31

---

Published in Transactions on Machine Learning Research (06/2025)
random matrix R Rnxp to compute G RΩ. Then, G is used as proxy to approximate the left singular subspace of R.
Unlike standard rSVD, SP-rSVD also computes a second projection F = R E RPxp in the same pass, enabling accurate SVD approximation without re-accessing R. Once and are computed, the remaining SVD steps proceed efficiently on these compressed matrices. We refer the reader to the original paper by Yu al. (2017) for implementation details and theoretical guarantees.
To compute G and F efficiently in single pass sequential sunmation strategy described in Equation 21. In particular, single row of R can be obtained by setting X = musi yielding R = R
R, combine the SP-rSVD algorithm with the
RTInn Inch where n. is the ith column on I,-
Using this approach, the matrices G and F can be constructed incrementally, as shown in Equation 22, starting with initializations G Onxp and F Onxpi
For i .1......,.]. Compute R. via Equation 21 with X Inii
g R
(22)
G -g
F = F+ F+RRA R..
In practice, it is advantageous to process multiple rows of R in parallel batches to maximize GPU throughput Letting b denote the batch size, the memory complexity of the algorithm becomes Onnp + nb + m), where is the number of non-zero entries in the adjacency matrix.
The total time complexity of proximity ReachNE's is O(nm + n²p + np²). The first term, nm, accounts for computing all rows of R using sparse matrix multiplications. The n²p term arises from evaluating the remaining steps in Equation 22, and up² corresponds to the final SVD step in SP-rVV after computing G and (Yu et al., 2017).
To accelerate this process, our implementation leverages the PyTorch framework, with built-in support for both single- and multi-GPU environments. A further advantage over the original MATLAB implementation of SP-rVV is PyTorch's support for automatic differentiation, which opens up new research directions for self-supervised proximity embedding methods based on differentiable reachability matrices.
A.5
Computational complexity of DirSwitch and time results
A.5.1
Computational complexity
We begin by analysing the time and space complexity of DirSwitch-r, followed by empirical run time mea- surements of our GPU-accelerated implementation.
The computational complexity of DirSwitch depends on the following variables:
n: number of nodes.
m: number of edges.
p: embedding dimensionality.
r: number of multi-directional steps.
number of walk length distributions.
K: number of walk steps (i.c., reachability terms).
b: batch size used in SP-SVD (proximity version only; see Section A.4).
d: number of node features (message-passing version only).
32

---

Published in Transactions on Machine Learning Research (06/2025)
We separately analyse the complexity of proximity and message- passging variants. We begin with the message- passing version, which is simpler due to the absence of batching.
passing DirSwitch. Message-passing DirSwitch-r is implemented using the algorithm in Equa- tion 6, which performs K sparse-dense matrix multiplications ions, each with time complexity ((md). This results in an overall cost of O(Kmd) per walk.
Each resulting n d matrix is then reduced to P dimensions using PCA via SVD, with time complexity ((nd)) (Golub & Van Loan, 2013, Ch. 5.5.6). This reduction is performed for all s 2" combinations of walk length distributions and directed neighbourhoods, resulting in a total time complexity of (s2" (ss2"(Kmdd (Kmd+nd²)),
22"
In terms of space complexity, we must store the m nonzero entries of the normalized adjacency matrix, the intermediate 8 reachability representations of shape n x d, and the final embedding matrix Z E R Our implementation computes the s multi-scale walks in parallel using tensors of shape 8 x n x d, while the 2" directed neighbourhoods are processed sequentially. The resulting space complexity is O( + snd + np).
Proximity DirSwitch. Proximity DirSwitch-r is implemented using the algorithm in Equation 22. As- suming a batch size b, the algorithm runs in E iterations. Each iteration computes a slice of the reachability matrix via K sparse-dense matrix multiplications with cost ((Kmb), followed by projection onto & E R"xp and the computation of F, both requiring O(bmp). Repeating for all batches yiclds a total cost of O(Kmn + n²p)).
After constructing the sketch matrices, SP-rSV computes the final embeddings in time ((pp²) (Yu et al., 2017), which is negligible when p < n. As with message-passing DirSwitch, this process is repeated for all 2-2" combinations of walk length distributions and edge direction patterns, resulting in total time complexity [Ks2"(Kmnn+ n))
In terms of space, the algorithm requires storage of the m edges, one n x b slice of the reachability matrix at time, and the n x p matrices Ω G, and F used by SP-rSVD. Our implementation stores copies of Q one per walk length distribution, computed in parallel. The total space complexity is O(snp + snb + m).
Discussion. The use of SP-rSVD assumes p < n, and its numerical accuracy may degrade as p approaches n. For small graphs, we recommend computing the full reachability matrix directly and applying SVD without batching. This yields a time complexity of Os22" (Kmn (mmm++2) +n²)) and space complexity of O(sn? + m)).
While SP-rVV helps improve the scalability of proximity DirSwitch-r by mitigating memory usage (see Section A.4), the method still incurs quadratic time cost in In contrast, message-passing DirSwitch-r has linear time complexity in n, making it more scalable for large graphs
A potential alternative to improve proximity scalability is a hybrid approach: apply SVD to the sparse adjacency matrix to generate initial proximity embeddings, then use these as node attributes a message- passing DirSwitch-r model. Investigating the effectiveness and scalability of this hybrid method is a promising direction for future work.
A.5.2 Run time results
To evaluate practical run times, we conducted a small-scale scalability experiment. We generated synthetic
undirected graphs using the Barabási-Alher model (Barabési & Albert, 1999), with an average degree of 2. We then measured the run time of DirSwitch while varying one paramcter at time n, r, 8, p, or d-while keeping the others fixed. For proximity DirSwitch, we fixed n 216 65,536, = 2, 3, and p = 256. For pressage-passing DirSwitch, we used n 200 1,048,576, 2, 3, p 512, and d = 128. Each experiment was repeated three times.
We tested proximity DirSwitch on three computational enviromments in Google Cloud: (i) 2 Nvidia L4 (24GB) GPUs, 24 vCPUs @ 2.20GHz, and 96GB RAM; (ii) 1 Nvidia L4 (24GB) GPU, 16 vCPUs @ 2.20GHz, and 64GB RAM; and (iii) CPU-only with 16 vCPUs @ 2.20GHz and 64GB RAM. These are denoted as GPU-2, GPU-1, and CPU-0, respectively. As our current implementation of poessago-psssing DirSwitch does not support multi-GPU computation, we only evaluated it in the GPU-1 and CPU-0 environments.
33

---

Published in Transactions on Machine Learning Research (06/2025)
CPU-0
GPU-1
GPU-2
Run tiae (6)
Run time (s)
Run Co)
time
2'
Num. nodes,
Num multi-irretional steps,
Num. acales,
Nom. embedding dimensions, p
(a) Graph size
(b) Muti-direction
(c) Muti-scale
(d) Emb. dim.
Figure 8: Scalability results for proximity DirSwitch-r. Each subfigure plots run time (in seconds) against key parameter in the DirSwitch time complexity. Markers indicate the mean over three runs, with shaded areas showing standard deviation. Line colour and style correspond to the number of GPUs used: 0, 1, or 2.
CPU-0
GPU-1
Run Lime (6) -5
Run time (4)
time
time
21
Num. nodes, n
Num. multi directional steps,
Num. scales, s
Num. node features, d
(a) Graph size
(b) Muti-direction
(c) Muti-scale
(d) Node altributes
Figure 9: Scalability results for message-paseee DirSwitch-r. Each subfigure plots run time (in seconds) against key parameter in the DirSwitch time complexity. Markers show the mean over three runs; shaded areas indicate standard deviation. Line colour and style correspond the number of GPUs used: or 1.
Figures 8 and 9 show the average run times for proximity and message-passing DirSwitch, respectively, with line colours indicating the compute environment. These results clearly demonstrate the advantage GPU acceleration, as both models run significantly faster on GPU than on CPU. For proximity DirSwitch, CPU runtimes were prohibitively slow at n 2 and we therefore aborted those runs hence the missing data points. Although multi-GPU setups introduce some overhead, they become advantageous for larger graphs.
Most trends align with theoretical expectations. Figure 8a confirms the quadratic time complexity in n for proximity DirSwitch, while Figure 9a shows linear scaling for the message-passie passing variant. The exponential growth in the number of directed neighbourhoods, 2", is reflected in the roughly exponential growth in run times shown in Figures 8b and 9b. In Figures 8c and 9c, we observe sublinear growth in run time with respect to 8, due to parallelization across the multi-scale computations.
One unexpected result appears in Figure 8d: the run time of proximity DirSwitch remains largely unaffected by the embedding dimensionality p. This is counterintuitive, n²p term. However, this term is dominated in practice by the Kmn cost of computing reachability. A similar pattern is observed in Figure 9d, where run time increases linearly with d for message paasgggppssing Enswitch-indicane
the theoretical time complexity includes
that the Kmd term outweighs the nd? term. These findings suggest that optimizing the reachability computation the most promising avenue for improving the overall efficiency of DirSwitch.
Tables 10 and 11 report measured run times for the experiments in Section 6.3. These were run on varying computational environments, runtimes may differ slightly across datasets. We only report results for the slowest datasets. On the others, runtime typically falls between 1-3 seconds.
The results confirm the trends observed in the scalability experiments. Since the implementation paral- lelizes over the number of scales (s) while computing different direction sequences (r) sequentially, r has a significantly greater impact on runtime than s.
The Cora datasets yield the longest runtimes, primarily because they contain the largest number of node features (d = 8710;
Table 2).
34

---

Published in Transactions on Machine Learning Research (06/2025)
Table 10: Emnbedding computation duration for message-passinn ReachNEs with p = 1024 embedding di- mensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers.
EDGE DIRECTIONS
CORA-ML
CORA GEOM-M
GEOM Pois
GEOM-L BINOM-3 GEOM-4
GEOM
Pois
BINOM-3
GEOM-4
DEFAULT
28
28
4s
6s
88
1M 248
1M 258
2M 49s
5M 33s
6M 28
UNDIRECTED
2s
4s
4s
1M 23s
1M 24s
2M 49s
4M 26s
5M 408
MULT-DI-11
38
48
8s
138
17s
2M 478
2M 498
5M 368
9M 43s
11M 368
MULTiDIR-2
78
78
168
278
358
5M 338
5M 378
11M 108
19M 138
22M 56s
MULTIDIn33
19s
19s
438
1M
1M 30s
10M 548
11M 25
21M 578
37M
118
44M 488
DIRSWIFCH-1 1
38
38
88
148
188
2M 478
2M 478
5M 358
8M
528
11M 188
DIRSwIrcH22
7s
78
178
29s
388
5M 358
5M 378
11M 108
17M
58s
22M 40s
DIRSwIreH-3
148
158
338
598
1M 158
11M 68
11M 138
22M 168
36M
148
45M 218
EDGE DIRECTIONS
Pokzс GEOM-Z BINOM-3 GEOм-4]
SNAP-PATENTS
GвOM
Pois
Pois
GROM-U BINOM-3 GEOM-d
DEFAULT
18s
22s
23s
218
218
26s
268
43s
578
568
UNDIRECTED
22s
188
19s
218
21s
318
378
428
538
1M 39s
MULTIDIR-1
44s
448
478
578
1M 38
59s
1M 24g
2M 88
2M 458
2M 2s
MULTIDu-2
1M 48s
1M
308
1M 548
1M 41s
1M 468
1M 58s
1M 598
4M 57s
27s
7M 348
MULrDDu-3
4M 10s
4M
118
4M 218
378
4M 488
4M 565
4M 568
6M 398
23s
9x1 528
DIRSwIrCH-1
34s
438
46s
48s
428
1M 54s
1M 1s
1M 238
2M 538
3M 348
DIRSwIrCH-2
IM 268
1M
228
1M 288
1M 178
1M 228
2M 48
2M 28
5M 78
3M 598
7M 538
DIRSwIrCH-3
2M 548 2M 548
3M Os
3M
88
3M
26s
6M 328
7M 18s
5M 20s
11M 408
8M 15s
Table 11: Embedding computation duration for proximity ReachNEs with p 1024 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers.
EDGE DIREUTIONS
COCITE
PUBMED
CoRa (stUEL))
GEOн Pois GEOM-Z BINOM-3 GBose-4
Geom
Pois
GEOM-L BINOM-3 GEOM-1
GEoM
Pois
GEOM-L BINOM- GEOM-1
DEFAULT
3s
48
1s
1s
1s
1s
28
UNDIRECTRO
18
MOLrDDB-1
6s
98
11s
1s
2s
1s
1s
2s
2s
38
MunriDm-2
128
12s
158
198
228
38
38
38
48
58
68
MouriDu-3
378
378
57s
Is
17s
1M
37s
7s
78
10s
148
18s
10s
10s
158
218
26s
DiRSwrren-1
88
88
108
13s
158
28
28
38
48
48
28
28
28
38
38
DisSwrren-2
148
158
19s
25s
28s
35
38
48
68
78
38
39
48
68
78
DIRSWITCH-3
478
538
68
98
Finally, Table 12 shows the run times of the models used in the node classification benchmark in Sec- tion 6.4. DirSwitch ranks among the fastest methods, alongside BLADE and NERD. Note that graph size and hyperparameter settings vary across these results.
A.6 Guide to hyperparameter selection for DirSwitch
DirSwilch-r embeddings are governed by four key hyperparameters: the embedding dimensionality p, the multi-directional neighbourhood radius r, the number of embedding scales s, and the choice of walk length distributions Pa(k;:) Each of these influences both embedding quality and computational cost. This section offers practical guidelines for selecting these hyperparameters, based on our experimental findings and experience with DirSwitch.
Walk length distribution. We begin with the walk length distribution Pa(k - ():T), where 4, denotes an offsct. For singlo-scale sctup (s 1), we recommend using Pois(k: 1,; 7 = 2), with 1, = 0 for message- passing and to for proximity embeddings, as explained in Section 2.3.1. This setting emphasizes the k = and k 2 neighbourhoods, which typically offer the most structural diversity, while still incorporating
35

---

Published in Transactions on Machine Learning Research (06/2025)
Table 12: Embodding computation duration for proximity node embedding models. Average and standard deviations are computed using 5 random seeds.
MODEL
FLY LARVA
EU-EMAIL
POLBLOGS
COCITE
PUBMED
CORA (SUBELJ)
HOPE!
588
98
78
41M 478
10M 46s
4M 45s
APP
15s
38
1s
8M 41s
1M 54s
2M 14s
NERD*
9s
288
48
12s
188
11s
DGGAN
29M 10s
6M
19s
2M
24s
1n 33M
7M 25s
51M 47s
BLADE"
1s
1s
238
11s
21s
DIRSWITCH
677MS
287MS
2M 31s
368
34s
Ou ET AL. (2016) Zuoo (2017)
KHOSLA AL. (2020)
Zuu (2021u)
VVRINCI SALADI (2023)
information from = 0, 3, and (see Figure 1la). Moreover, our graph alignment results suggest that T R 2 tends to correspond to peak expressivity (see Figures 7 and 15). Lower values of risk overly localized embeddings, while higher values may lead to over-smoothing.
When using multiple distributions (s 1), it is important to avoid excessive overlap between them, as this leads to redundant embedding dimensions. We find that Geometric distributions with small T and varying offsets are particularly effective, as they place their modes at distinct distances from the source node. This configuration performed especially well on the Pokee dataset (Section G).
As a general rule for 3, we recommend the following family of walk distributions:
[Geom(k - -;; = + 0.5s;) 8; E
8 1]].
(23)
For 8 = 2, preferable to combine one short-range and one long-range distribution, such as Geom (A; T 2) and Pois(k- 2: 3).
Expressivity and computation trade-offs. We now discuss the parameters p, r, and s, which govern the trade-off between model expressivity and computational cost. Increasing any of these parameters typically enhances embedding expressivity and improves downstream task performance, as demonstrated in Section 6.
However, this comes at the cost of increased computation, as analysed in Section A.5.
Notably, increasing r and s leads to diminishing returns for two key reasons. First, larger values result in embeddings that capture increasingly broader neighbourhoods. Since most real-world graphs exhibit the small-world property (Watts & Strogatz, 1998) i..., short diameters and small average path lengths (sce Table la-lerger neighbourhoods quickly converge to covering the full graph, reducing the embeddings' ability to distinguish local structure.
Our graph aligument experiments support this: using the Poisson distribution, the most discriminative and noiso-robust embeddings arise from walks of to steps (see Figures 7 and 15). We therefore recommend keeping and the support of the walk length distribution within 5-6 sleps, unless the graph's 's structure specifically warrants longer ranges. Nonetheless, further research is needed quantify these diminishing returns and understand how they vary across graph types and downstream tasks.
A second source of diminishing returns arises from the constraint of fixed embedding dimensionality p. Since DirSwitch-r concatenates embeddings across s scales and 2" directed neighbourhoods, each (a,Px) pair contributes only s2 dimensions. If or are set too high relative to each component becomes overly compressed, degrading the overall embedding quality.
P
Inercasing P generally improves expressivity, but also raises computational demands. In particular, ex- cessive values may exceed GPU memory limits, forcing computations to fall back to CPUs significantly increasing run time, shown in Section A.5.
Based on our experimental findings with 512 in Section G, where we observed diminishing returns, we recommend ensuring p 2 32s2" as a practical guideline. For instance, with 1024, we suggest. = 3 and s = 3 or s = 4, which matches the best-performing models in Section 6.3. If hardware permits, r, and s can be increased proportionally while respecting the p 2 32s2" rule. For resourco-constrainel settings, we recommend multi-directionality and multi-scale expressivity.
1, s 2, and p = 256 as an efficient configuration that still benefits from both
36

---

Published in Transactions on Machine Learning Research (06/2025)
①
2
7
8
5
6
3
4
9
Figure 10: Illustration of structural and automorphic node equivalence. Nodes with the same colour (c.g.. nodes and 3) are structurally equivalent, meaning they share identical connections the same set of nodes. Nodes with the same shape (e.g-, nodes 2, 4, 7, and 9) automorphically equivalent, meaning they indistinguishable based solely on graph structure without node labels.
B Message-passing embeddings and automorphic node equivalence
This section provides additional detail automorphic node equivalence and proves that message-passing ReachNEs embeddings assign identical representations to automorphic nodes.
Figure 10 illustrates both structural and automorphic node equivalence. Nodes with the same colour are structurally equivalent, while nodes with the same shape are automorphically equivalent. As shown, struc- tural equivalence always implies automorphic equivalence, but not vice versa. Figure 10 also highlights how structural equivalence implics node proximity, whereas automorphically equivalent nodes can be far apart, such nodes and 10. In fact, automorphie nodes can even exist in separale weakly connected components.
To prove that peessag-passingg ReachNEs embeddings preserve automorphic equivalence, malizing the definition. Let N + N be a permutation of the node set in a graph g = (N, MI), and let Pa E {0, 1 denote the corresponding permutation matrix, where (+(+(i), i) = for all i, and all other entries are zero. An automorphism any such permutation π that preserves the edge structure the graph, i.c., (i,7) E M = (T(i), T()) M.. Equivalently, this condition holds if the adjacency matrix satisfics A P. ATT. Two nodes i and j are automorphically equivalent if there exists an automorphism such that (ii) i..,, P= 1.
begin by for-
Next, prove that ressage-passing ReachNEs produces identical embeddings for automorphic nodes, i.e., P.Z = Z, under the node attribute equivalence assumption, X = P,,, which is guaranteed if X consists of graph-derived features.
We start by showing R P.R.T. x. To see this, note that by the definition of automorphism, we have A PT The same holds for the normalized adjacency matrices, As PT, and their powers,
A P.A.P.. This follows from:
II A.
| PI. P.A.: A., PIP A, PT
P A PT.
Since the reachability matrix R is sum of power matrices, see Equation 8, it follows that R is also invariant under automorphism R P.RP.
To complete the proof, recall that Z = RR represents message-passing embeddings (see Section 2.3.2).
We then simply insert = P,RPP and X P,X:
= P I, X-P,RIPIPX- R 2.
P.P.
R
Unlike messago-passinn ReachNEs, proximity emboddings are obtained via SVD reduction, a global operation that does not necessarily preserve automorphism invariance. Thus, it is generally the case for proximity embeddings that P,Z + Z. A formal proof for undirected graphs is provided by Zhu et al. (2021a).
37

---

Published in Transactions on Machine Learning Research (06/2025)
C Asymptotic behaviour of random walk length distributions
This section expands the analysis in Section 2.2, focusing the asymptotic behaviour of different random walk length distributions and their implications for the reachability matrix R as 7 - oc.
We begin with the Poisson distribution, deriving its associated diffusion differential equation and estab- lishing its well-known connection the normalized Laplacian. Next, we derive a similar equation for the geometric distribution, demonstrating that, unlike the Poisson case, does not necessarily converge a non-informative stationary distribution
xc.
We then examine the relationships between distributions in the K-truncated setting, proving that:
(A.;U(T)); -> xC, R ()) (A.; Binom(r)) - (A.; Pois(T)), as K - xc.
R(K) (A.; Geom(T)) (
Finally, we highlight the relation between the binomial distribution and random walks on graphs with self- loops added at each node.
C.1 The Poisson Distribution
We now establish the identity:
Pois(r)) = =
(24)
where L. = I, - A, is the normalized graph Laplacian.
Starting from the definition in Equation 2, we rewrite the reachability matrix as:
R(A.:Pois(T))
A A.
using properties of the matrix exponential (Hall, 2015).
Next, we show that for an initial probability distribution (0)) [0, 1]", the solution:
p(T) R(A., Pois(T))p
(25)
satisfies the differential equation:
dp L.p(T).
(26)
dr
Proof. From Equation 24, we recall that:
R(A,, Pois(T)) Tb.
Setting r = 0 gives R(A., Pois(O)) = In, ensuring that the initial condition is satisfied:
p(0) = (0)
Differentiating Equation 25 with respect to 7:
dp(r)
d e - b. '0 = -Le ttbpp)) - LL.((T).
dr dr
Thus, p(T) satisfies the differential equation required.
The differential relation in Equation 26 useful for analysing the dynamics of R(A., Pois(7)) with respect to 7, allowing to establish its asymptotic behavior.
38

---

Published in Transactions on Machine Learning Research (06/2025)
Focusing first the undirected case, the cigenvalue multiplicity of in the normalized Laplacian Ly equals the number of weakly connected components in the graph (Chung, 1997; von Luxburg, 2007). The corre- sponding eigenvectors u take values:
deg(t)
U4
EkEoC) deg(k)
for each node within weakly connected component C()). These eigenvectors are the only stationary solutions to Equation 26, all other eigenvalues of Lu are strictly positive.
Thus, as + oo, the reachability matrix converges to:
deg(i)
R(,,, Pois( + Ekeec) deg(k)
(27)
Importantly, all nodes within the same weakly connected component have identical asymptotic reachability values, making them indistinguishable under the Poisson walk length distribution for undirected graphs. Consequently, downstream tasks relying on embedding distinguishability, such graph alignment, are ex-
pected to degrade as т increases. This effect was also observed in Figures 7d and 7b.
The above analysis provides a good first-order approximation of the Poisson distribution's behaviour on digraphs. However, precise theoretical analysis using Lp and L1 is more involved and beyond the scope of this paper. Instead, refer to Veerman Lyons (2020) for valuable insights. Specifically, the multiplicity of the eigenvalue 0 corresponds to the number of reaches in the graph (Veerman & Lyons, 2020, Thcorem overlap. Consequently, the eigenvectors
4.6). Unlike weakly connected components, multiple reaches exhibit more complex structure (Veerman & Lyons, 2020, Theorem 5.1), and nodes within reach do not necessarily converge to the same reachability vector as + oo.
C.2 The geometric distribution
We now analyse the asymptotic behavior of walk lengths following the geometric distribution. We start with the parameterization a E [0, 1), related to by a = 1 so that as T - oc, we have a + 1.
As before, we express the reachability matrix as a matrix function:
R(A.; Geom(a)) (1 a)
A = (1 - aa) - -
(28)
A=
Substituting I and simplifying, obtain:
1
R(A.; Geom(7))
In 1 A
1+T
= (In + T[I - A.))
-In+ -b.
Using this identity, we show that p(T) R(A,; Geom(T) (p)) satisfies the differential equation:
dp(T) - (I, + +T.) L,P(T), p(0) (
(29)
dr
Proof. The initial condition is satisfied since R(A.; Geom(O)) In, so p(0) (0), To compute the deriva-
tive dp(r) dr we apply the matrix inversion derivative rule (Petersen & Pedersen, 2012, Sec. 2.2):
dp(r) d dr dr
(In, + +L. ()))
- (In + L.)) L, (In +T.) (0)
=- = Tb.)) L.P(T).
39

---

Published in Transactions on Machine Learning Research (06/2025)
Thus, the differential equation is verified.
The differential equation in Equation 29 offers insight into the similarities and differences between the dynamics of the geometric and Poisson distributions. Both equalions contain the lerm L.p(T), implying that any stationary distribution under Poisson dynamics is also stationary for the geometric case. However, the presence of the prefactor (I, + +L.) in Equation 29 suggests that this stationary distribution may not be reached under geometric dynamics.
To understand this, let À be an eigenvalue of L. Then T+rx is an eigenvalue of (I, +TL+) For any À > O, we see that 147ī + 0 as T - co. Consequently, many eigenvectors will yield near-zero gradients as 7 increases, effectively stalling the dynamics.
As a result, p()) is likely bocome "stuck" before converging the non-informative stationary distribution that characterizes Poisson dynamics. This phenomenon is also observed empirically in Figures and 7, where both dispersal entropy and graph alignment accuracy exhibit this same saturation effect.
C.3 Relation between the geometric and the uniform distribution
An interesting asymptotic behavior of the geometric distribution is that its K-truncation approaches the uniform distribution as co, equivalently, + 1.
To demonstrate this, we begin with the expression for the K-truncated reachability of the geometric distri- bution using the a parameterization:
(1 (1-a) Σ A
A R R(K) R (A.; Geom(a)) = Z(a, K)
(30)
k=0
where Z(a, K") is the normalization factor required due to the truncation.
Next, we reparameterize using a, yielding:
K
(R()
E
Σ
(1 -
A
A
(31)
7(e, K)
k=0
We can compute the normalization factor Z(e, K) as:
K
1 1- K+1
Z(e, K) = Σ e1
1 8) K+1 k)+1)
= 1 (1 8)
As e 0, we can use the approximation (1- - +)* = ke + O(s2) for both Z(e, K) and the summands Equation 31 show that R(K) (A,)(A;;)) approaches the reachability matrix under the uniform distribution:
lim (k) (A.;8)
lim - (K + 1)E
kE)
+0
K
1
lim
kA
K + k=0
K +
k=0
K
A
K k=0
C.4 Relation between the binomial and the Poisson distribution
The final asymptotic behavior we highlight is that the reachability under the binomial walk length distribu- tion, (A.; (rnom(r)), approaches that of the Poisson distribution A.A.; Pois(r)) as K -
40

---

Published in Transactions on Machine Learning Research (06/2025)
We begin by expressing R (A.; Binom(r)) matrix function using the Binomial Theorem:
K
K-k &
R( (A.; Binom((T)
A
k=0
-(1 K
In
K A.)
I L.)
Next, perform the substitution K,
K and as we take the limit Kr + 00, we obtain:
The =e -
lim Ko000
In
L. K
Pois())-
(32)
Here, we recover the matrix exponential using its limit definition (Hall, 2015), which, together with Equa- tion 24, proves the asymplotic equality to the Poisson-based reachability.
C.5 Relation between the binomial distribution and self-loops
Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) popularized the common pre-processing step of adding self-loops to each nodo, a practice that has since been widely adopted in self-supervised GNN methods (Wu et al., 2019; Zhang al., 2021a; Thakoor al., 2022). As discussed in Section 2.2, there a close connection between the binomial walk length distribution and graphs with added self-loops, which we explore in this section.
This connection becomes evident when we consider the random surfer interpretation of the binomial dis- tribution. In this view, a random walker makes total of K decisions. At each step, the walker moves to a neighbouring node with probability a, or remains at its current node (i.c., performs a sclf-loop) with probability - a. The probability of taking exactly l steps to neighbouring nodes (and K - self-loops) then follows the binomial distribution:
Po(k;a)= (K)
K (1 a)k=*
The corresponding reachability matrix is given by:
K
K (1)(
R (A,; Binom(a))
(1 (1- a) A.
(33)
k=
We can rewrite this expression using the Binomial Theorem and the fact that the diagonal matrix (1 a. commutes with any matrix under multiplication:
K (1 a) K AA
R(K)(A, (inom(a))
k
K
K
(1 a) K- - K k A
k
k=
K
Σ
((1 (11-)Inn) K- (aA.)*
k
k=o
= ((1 I, + aA.)*
AK
41

---

Published in Transactions on Machine Learning Research (06/2025)
Here, we define A.+ = (1-a) aA, self-loop enhanced normalized adjacency matrix. We see that the binomial reachability matrix is simply the Kthh power of A.+-
This matrix consists of two parts: a diagonal component (1 a)) representing the probability of staying at the current node (i.e., self-loops), and a weighted adjacency component aA,, representing the transition probabilities to neighbouring nodes.
A very similar construction arises in message-passingg models that explicitly add self-loops. In what follows, formalize this for random walks using the outgoing edge transition matrix Ao- The analysis extends directly to the incoming edge matrix A₃ and the undirected matrix Au.
First, let S = A In be the adjacency matrix with added self-loops, and let Do. Do + In denote the corresponding out-degree matrix. Then, the normalized transition matrix for the self-loop-enhancee enhanced graph is given by 50 = S-
We decompose So into two components: So Po + P-,, where Po diag(S)) (So) contains the self-loop (stay- in-place) probabilities, and P-, contains the off- off-diagonal transition probabilities to neighbouring nodes.
This structure closcly mirrors that of A.+ = (1 - + aA.. In both cases, the stay-in-place behavior is captured by a diagonal matrix- Py for So and (1 In for A.4-while while the remaining transitions are modelled via P-, and aA., respectively.
Consequently, the Kth power of Sp produces a matrix polynomial with binomial coefficients, analogous to the binomial reachability matrix in Equation 33. This observation aligns with practice: in a K-step linear GCN, node embeddings are computed as Z (SK) (Wu et al., 2019), which matches the message-passing form of the binomial reachability matrix ((()(A,, Binom(a)) A described in Section 2.3.2.
Thus, both approaches share the same underlying random surfer interpretation and exhibit similar mathe- matical structures. However, there is one key difference: in the binomial reachability model, the stay-in-place probability uniform across all nodes, controlled by the scalar (1 a)). . contrast, for GCNs with added self-loops, the stay-in-place probability varies by node and is given by Po: where Poi, 1+deg.(ty This mcans that nodes with lower out-degree have higher probability of remaining in placo.
Whether this degree-dependent behavior improves embedding quality is ultimately an empirical question and may depend on the characteristics of the graph and the downstream task.
Additional experiment setup information
D.1 Single- and multi-scale ReachNEs embedding distributions
This section provides further details related the experimental setup described in Section 6. Figure 11 shows the random walk length distributions used in the ReachNEs experiments, as listed in Table 3.
The first. plot, Figure 11a, displays the two single-scale distributions, referred to Geom and Pois. The Geom distribution corresponds to Geom(k; = 1), emphasizing the node itself (A 0) and short-range walks (1 2 steps). In contrast, Pois uses Pois(k; = 2), which down-weights self-loops and focuses on medium range neighbourhoods (2-4 steps).
The Geom-l sctting creates two-scale embeddings by combining two distributions designed to capture both short- and medium-range structure. The first is Geom 1) (same in Geom), while the second is the shifted uniform distribution U(k - 1: 2), which excludes the k term and concentrates probability mass over h E 5].
The Binom-3 and Geom-4 settings are multi-scale distributions designed to capture short-, medium-, and long-range reachability. Binom-3 is inspired by Gaussian mixture models (Murphy, 2012, Ch. 11.2.1) and
combines three binomial components: Binom = 1) centred at = 0, Binom 2; = 1) centred
k 2, and Binom(k 5; 1) centred at h 5. To account for the increasing range, we increase the parameter 7 for longer walks, thereby widening the support of the distribution.
42

---

Published in Transactions on Machine Learning Research (06/2025)
0.5
11.5
0.5
01.
Prob, mas function, Pilk
Grometric(k; = 1)
Proh mass function, Pw(())
Grometric(é; + = 1)
Prob. funetion. Pw(k)
Ninom/e r
Prob mass function, Pollk)
Grometrack; = 1)
Polssonjk:
Unifornté 1: 2
Binom// 2.r
0.4
0.4
0.4
0.4
Binomik - 5
Grometrice -,7
Geometnack -3,
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.1
0.1
0.1
0.1
0.0
2 4 6 17789900 101112
0.0
5 6 901112
0.0
1 2 3 901112
0.0
6
101112
Walk length, &
Walk length,
Walk length,
Walk length,
(a) Geom and Pois
(b) Geom-I
(c) Binom-3
(d) Geom-4
Figure 11: Plots of the walk length distributions P. listed in Table 3. (a) show the two distributions used to create single-scale ReachNEs emboddings, while (b), (c) and (d) show the distributions used for multi-scale embeddings, with 2, 3 and 4 components respectively.
In contrast, Geom-4 uses four geometric components with progressively increasing mode and tail width: Geom(k; 1), Goom 1; r 2), Gcom(k 2; 3), and Gcom(k 3; 4). Unlike Binom-3, these distributions are not centred on long-range steps but exhibit heavy lails, meaning they still provide smoothing over distant nodes. The advantage of Geom-4 is that it places distinct modes over steps & E {0, 2, a range where most node-distinguishing information typically resides. This focus on short- and mid-range steps aligns with the goal of preserving local structure while retaining some long-range awareness.
D.2 Hyperparameters for proximity embedding comparison
Table 13 shows the hyperparameter search grids for each digraph proximity method compared in Section 6.4. For all models, we tune the number of embedding dimensions using E [64, 1024]. Note that for HOPE, we report halved values, the implementation internally doubles the embedding size.
For DirSwitch-r, tune both the number of directed steps and the choice of walk length distributions P.. For the other baselines, we tune their respective hyperparameters that influence proximity scale. These include:
the B parameter for HOPE,
the number of walk steps and jump factor for APP,
the number of walk steps for NERD,
the number of layers for BLADE.
We also tune selected rearted hyperparameters: the number of sampled walks for NERD, the loss trade-off parameter À for DGGAN, and the learning rate and number epochs for BLADD..
With this setup, the total grid sizes approximately comparable across methods. DirSwitch uses 75 different hyperparameter combinations. Among the baselines, APP and BLADE have the largest grids, with 120 and 300 combinations respectively. DGGAN has the smallest grid (45 combinations). as it is significantly more computationally expensive to train, making extensive tuning infeasible.
The best- perfoorrfn hyperparameter settings for each model and dataset, based on cross-validatte accuracy, are listed Table 14. For DirSwitch-r, we observe that multi-scale enbeddings with three or four components consistently yield the best results, aligning with prior findings on the benefits of multi-scale embedding strategies (Rozemberczki et al., 2021).
43

---

Published in Transactions on Machine Learning Research (06/2025)
Table 13: Hyperparameter grids used for the comparison of proximity embedding models in Section 6.4.
MODEL
HYPERPARAMETER
VALUES
EMB. DIM p
64, 128, 256, 512, 1024
DIRSWITCH--
r
1, 2, 3
P2
GEOM, PoIs, GEOM-U, BINOM-3, GEOм-4
B
0.001, 0.01, 0.1, 0.2, 0.35, 0.5, 0.65, 0.8, 0.9, 1.0
HОРE
EMB. DIM. P
32, 64, 128, 256, 512
EMB. DIM. P
64, 128, 256, 512, 1024
APP
JUMP PACTOR
0.1, 0.25, 0.5, 0.75
WALK STEPS
2, 3, 4, 5, 6 7
EMB. DIM. p
64, 128, 256, 512, 1024
NERD
NUM. SAMPLES
2,
WALK STEPS
2, 3, 4, 5, 6
EMB. DIM. p
64, 128, 256, 512, 1024
DGGAN
À
5F-06, 1E-05, 5F-05
LEARNING RATE
5F-05, 0.0001, 0.0005
EMB. DIM. P
64, 128, 256, 512, 1024
LEARNING RATE
0.0001, 0.001, 0.01
BLADE
NUM. EPOCHS
10, 30, 50, 100
NUM. LAYERS
2, 3, 4, 5, 6
Table 14: The best hyperparameter values for each proximity embodding model and datasct.
MouRL
For LARA
CU-EMAIL
POLIUDGS
CoCmr
Poiseo
Cona (suucu))
DoM. 256
DIM P
TIM P
178
BIM
1003
Ram.
1021
DISWITCK
P, GRous-
Brsoss-3
Besoec-3
Pg
Brooas-3
Breous-3
P. BISOAL-5
Dot p
DIA.
Est..
Fun.
Fum.
WALK
WaLk
Eat. 206
Esto.
250
Evm.
Nusa.
Near.
Nusa
New.
WaEk
WALK
206
128
Esm.
DOGAN
Co-06
10:00
15.05
0a-05
Do-00
LEAINING
LEARNING
5E-06
6p-06
Eun. sas.
1024
Eum. noz
1024
Ham. ni4.
512
Eun. rez.
1024
Eum.
1024
Eun.
1024
BLADE
LEARNING 0.0001
Nrs 29oces
10
LOcaNING
Now. FeocHs
0.0001
LeaRKiNG
NoM. kinerria
0.001
LEARNING
Nes. seorms
0.0001
10
LEMIKING
Nrx: rinoos
10
Nou. smorws
30
0.0001
Nuw LAVeRS
Nev. LAVERS
NoM.. L.vesa
Nivu. LAvrss
Now. Lovees
NoM. rarrss
44

---

Published in Transactions on Machine Learning Research (06/2025)
6
8
10
12
Rag xc deg(i)
10-
10
7.0
Eatroyy
Entropy
Entropy
5.0
5.0
2.5
2.5
0.0
0.0
0
0.0
005
010
01.5
13
0.00
0.255
(1.50
0.25
1.00
0.00
0.25
0..00
0.75
1.00
Proportion of nodes
Proportion of nodes
Proportion of nodes
Proportion nodes
(a) CiteSeer, 0
(b) CiteSeer, U
(c) Enron, 0
(d) Enron, U
7.5
7,5
Eutrpy
Patrapy
Entrapy
Entropy
6.0
2.5
2.5
3.0
0.0
0.00
0.25
1.50
0.75
1.00
0.00
0.25
0.50
0.25
100
0,000
0.25
0.30
0.75
1000
000
0.25
0,50
0,25
1.00
Proportion of andes
Proportion of nodes
Propoction of nodes
Proportion of modes
(e) EU-Email, 0
(f) EU-Email, U
(g) Polblogs, 0
(b) Polblogs, U
10.0
10.0
Entropy
10
Entropy
Entropy
7,0
Entropy
7.5
2.5
25-
0
0.0
0.0
0.30
0.25
0.50
0.75
100
0.0
0.5
1.0
0.0
0.5
1.0
0.3
0.5
1.0
Propoction of podes
Proportion of modes
Proportion of modes
Proportion of nodes
(1 Roman Empire, 0
(i) Roman Empire, U
(k) Wikivotes, 0
(I) Wikivotes, U
Figure 12: Reachability under P. = Pois(T), using As and Au- The x-axes correspond to nodes sorted by their entropy value. The colours represent various values of T. The black dashed line indicates the entropy of a reachability distribution proportional to the node degrees, which corresponds to the limiting and uninformative distribution as T + co. See Appendix C.1 for further details.
E
Additional analysis of local sinks and dispersal
This section provides additional analysis of local sinks and reachability dispersal for graph datasets not included in the main paper due to space constraints. As before, we use reachability entropy to quantify dispersal. Recall that the reachability entropy of node j is defined as:
H(j; R)
Σ Ra, log2 Ri.j.
(34)
where Ra, is the (i,j)-th element of the reachability matrix R(P,, computed under walk length distri- bution P. and edge direction specifier a.
Figure 12 complements Figure 5 by presenting results for six additional datasets, using the Poisson walk length distribution P, = Pois(T). Each coloured curve corresponds to a different value of т. The figure focuses on comparing the dispersal effects of default directed edges (a = 0) versus undirected edges (a = U).
Consistent with the examples in Section 3.1, we observe substantial entropy gains when using undirected edges on sparse and moderately dense graphs. For example, the sparse CiteSeer graph shows a pronounced increase in entropy, while medium-density graphs such as Enron, Polblogs, and Wikivotes also exhibit clear improvements. These gains become more pronounced at larger T values, as reachability under directed edges increasingly concentrates in local sinks.
In contrast, the dense EU-Email graph, with an average node degree of 25, shows only minor differences be- tween the directed and undirected cases. While small increases in entropy are still visible (cf. Figure 12c and 12f), the graph's 's high density mitigates sink formation and enables more uniform information propagation.
45

---

Published in Transactions on Machine Learning Research (06/2025)
Figure 13 extends Figure 6 by presenting results for cleven additional datasets. We again use Px Pois(T 2) to model short-range walks and P. u(( 5) for longer-range behaviour.
The figure compares DirSwitch edge direction specifiers with those of MultiDir. The results closely follow the trends observed in Figure 5, with DirSwitch consistently achieving higher entropy than Multiirresspciilly under the long-range distribution P. ((T). As before, the differences are most pronounced on sparse graphs including Arxiv, CoCite, Pubmed, and Snap Patents.
The Roman Empire graph constitutes a counterexample to the trends described above. As shown in Fig- ure 12i and 12j, there is virtually no difference in entropy between = 0 and o U, despite the graph's 'ss sparsity. In fact, close inspection reveals that entropy is slightly lower for the undirected case, particularly for large values of r. This effect is even more pronounced in Figure 13j, where o = 0 yields the highest entropy under the uniform walk length distribution. This is the only dataset where such behaviour is observed.
To understand this counterintuitive result, we must examine the specific structural properties of the Ro- man Empire graph. As shown in Table 2, this graph stands out with an unusually long average path length around 2400 steps. The underlying reason is its chain-like topology: the graph primarily consists of a long linear sequence of nodes, where cach node typically has an in-degree and out-degree of onc. Occa- sionally, nodes branch off from the main chain and later reconnect.
Figure 14 visualizes a subgraph of the Roman Empire graph, clearly illustrating this structure. It also highlights why entropy may decrease in the undirected case. The node colours represent reachability values from the same starting node under a = on the left, and a = on the right, both using the uniform walk length distribution. As shown in Figure 14a, reachability in the directed case is spread more uniformly along the chain. In contrast, Figure 14b shows that the undirected case concentrates reachability around the starting node.
This is a consequence of the chain structure: in the directed case, random walks proceed almost exclusively forward along the chain. In the undirected case, however, each step introduces a 33 50% chance of stepping backward. This backward drift increases the likelihood of returning to or remaining near the starting node, reducing entropy.
F
Additional graph alignment results
Figure 15 presents graph alignment results for three additional datasets, complementing the four datasets shown in Figure 7. As in the main paper, the y-axes indicate graph alignment accuracy, while the x-axes show values of r. The top row corresponds to P. = Geom(T), and the bottom row to P. = Pois(r).
The results in Figure 15 are consistent with the findings from the main paper. For both DirSwitch-r and MultiDir-r, alignment accuracy increases with r, reflecting the benefit of reprosenting larger number of di- rected neighbourhoods. In contrast, models using 0 and o U consistently achieve the lowest accuracies, as they lack the capacity to capture multiple directed neighbourhoods. DirSwitch-r generally outperforms MultiDir-r, highlighting that mitigating the effects of local sinks contributes to improved alignment accuracy.
We again observe the distinct behaviours of the Poisson and geometric walk length distributions: increasing 7 tends to degrade accuracy under Pois(r), whereas accuracy plateaus under Goom(T), as previously discussed.
A notable exception is the Pubmed dataset, where DirSwitch-r with P. Pois(T) reaches peak accuracy around Re 9, indicating that relatively large receptive field is required for optimal performance. This contrasts with the other datasets, which generally attain their highest accuracy for < 5.
This behaviour can be altributed to the structure of the Pubmed graph. As shown in Table 2, Pubmed has a very sparse local structure-its median out-degree is O, and its median in-degree is 1 meaning that the short-range neighbourhoods of many nodes are nearly indistinguishable. Additionally, Pubmed exhibits the longest average path length among the alignment datasets. These factors necessitate a broader receptive field to generate more expressive and distinguishable embeddings.
46

---

Published in Transactions on Machine Learning Research (06/2025)
OI
OIO
OU
OIU
OIOU
10.0
10
7.0
Eatropy
Eatroyy
latropy
Entropy
2.5
01.00
0,75
1.0
0.25
10.00
0.75
1.0
0.0
0,50
0.75
1.00
nodes
Proportion of nodes
Propertion of nodes
Propartion of nodes
7.5
Ttonopy
Eatropy
Eatroyy
Tranopy
0.0
0000
0.75
0.500
0.25
1.00
0.00
0.25
0.90
0.75
1.00
0.03
0.75
0.50
0.75
1.00
0.0
0.5
Propartion of modes
Propertion of modea
Proportion of modes
Proportion of nodes
(a) Arxiv
(b) CiteSeer
(c) CoCite
(d) Cora
10.0
10.0
7.5
Entropy
Entropy
Entropy
Entrapy
5.0
11.0
0.0
000
8.5
300
11.5
10
0.50
01.35
01.50
0.75
1.00
0.00
0.25
0.30
0.25
1.00
Proportion of nodes
Proportion of nodes
Proportics Blon of nodes
Propartion of nodes
10.0
Entropy
Eatropy
Entropy
Earrm
5.0
2.5
01.30
0225
1.00
12,00
1.75
1.00
12255 1.00
Proportion modes
Proportion of nodes
Proportion of nodes
Proportion modes
(e) Cora (Subelj)
(f) Enron
(g) Polblogs
(h) Pokec
Lattopy
Entropy
Entropy
0.00
100
0.500
100
B250 Proportion modes
L00
Proportion modes
Propartion of nodes
10.0
Intropy
7.5
Entrupy
Entrapy
2.5
0.0
0.0
0.55
1B
11.00
11.25
11.00
0,20
1.00
0.00
0.25
0.50
00.05
1.00
Proportion of nodes
Propartion of nodes
Proportion of modes
(i) Pubmed
(i) Roman Empire
(k) Snap Patents
Figure 13: Neighbourhood dispersal evaluation for 11 graphs, measured via reachability entropy, Σn R,, log, Rig, computed for each node and sorted. Each curve corresponds to diffcrent odge dircc- tion specifier o, with the top row showing results for 7k; Pois(T 2) (local dispersal) and the bottom row for U(T 5) (long-range dispersal). DirSwitch variants (e.g.. OU, DIU, OIOV) demonstrate high dispersal, comparable to U. while purely directed specifiers (0, OI, 0I0) exhibit lower entropy due to sink effects.
47

---

Published in Transactions on Machine Learning Research (06/2025)
(a) Roman Empire,
(b) Roman Empire, U
Figure 14: Both figures show the same subgraph of the Roman Empire graph. The node colours reflect the reachability vector for the same node under the uniform walk length distribution. (a) uses default directed edges (a = 0) while (b) uses undirected edge (a = U).
Undirected
Default
MultiDie11
MultiDir-2
MultiDie-3
DirSwitch-1
DirSwitch-3
0.6
0.3
Hite@1
0..4
Hits@@
0.4
Hits@a1
0.2
0.2
0.2
0.1
0.0
avg. walk steps
avg. num. walk steps
avy. walk steps
Enron, Geom(()
(b) Polblogs, Geom(T)
(c) Pubmed, Geom(T)
0.4
0.6
0.6
0.3
Hits@11
0.4
Hitss@1
liit@@1
0.2
0.2
0.2-
0.1
0.0
0.0 0
0.0
10
15
T avg. num. walk steps
avg. num. walk steps
7 avg. num. walk steps
(d) Enron Pois(T)
(e) Polblogs, Pois(T)
(f) Pubmed, Pois(7)
Figure 15: Evaluation of edge direction expressivity for four graphs using the geometric, Geom(7), and Poisson, Pois(7), walk length distributions. The y-axes represent graph alignment accuracy under 15% edge removal, while the x-axes correspond r, the average walk length. The curve colours and styles denote
different sets of edge direction specifiers,
48

---

Published in Transactions on Machine Learning Research (06/2025)
G
Additional DirSwitch embedding quality evaluation
This section provides further analysis and discussion of the results presented in Soction 6.3, focusing on the benefits of multi-scale embeddinggs, the limitations introduced by fixed embedding dimensionality and the presence of 2-step homophiliy in the Pokec dataset.
Multi-scale embeddings and diminishing returns. The results in Tables 4 and 6 offer clear evidence of the benefits of multi-scale embeddings. Across all datasets, observe at least moderate improvements when transitioning from single-scale to multi-scale walk length distributions, with several datasets exhibiting sub- stantial accuracy gains. For instance, on Cora-ML, the classification accuracy for undirected embeddings in- creases from 31% to 76%; on Citeseer, from 76% to 89%; and on Cora, from 59% to 69% when switching from Geom to Geom-4. These results highlight the importance of embedding expressivity in unsupervised learning.
Similar trends are observed for proximity embeddings in Table 6. For example, FU-Fmmail improves from 30% to 72%, and Polblogs from 64% to 85% under the same change in walk length distributions.
However, the benefits of multi-scale embeddings diminish as the mumber of multi-directional neighbourhoods increases, particularly for MultiDir-r and DirSwitch-r. In Cora-ML, for example, DirSwitch-1 improves from 57% to 82% when switching from Geom to Geom-4, whereas DirSwitch-3 shows a more modest improvement from 79% to 86%.
This trend is even more pronounced in the results for p = 512 embedding dimensions (Tables 16 and 18). In these cases, increasing both the number of multi-directional neighbourhoods and the mumber of scales can lead to accuracy degradation. For example, in Table 16, the accuracy for Cora declines as increases and when using Binom-3 or Geom-4. A similar pattern is observed for EU-Fmail in Table 18.
This behaviour arises from the diminishing returns of combining milti-directional and multi-scale embeddings via concatenation under fixed dimensionality constraints. As described in Section 4, the total embedding dimension p must be divided among all combinations of direction specifiers and walk length distributions. When p is fixed, increasing the number of concatenated components reduces the dimensionality available for each, limiting their expressivity. As result, performance gains plateau at p 1024 and begin to decline p 512.
While increasing p can help alleviate this issue by allowing more capacity for embedding components, this approach has practical limitations. Larger embeddings require more memory and computational resources, and may introduce challenges such as overfitting or the curse of dimensionality in downstream tasks. Future work is needed to explore more efficient ways to compress and integrate multi-directional and multi-scale information into compact. embeddings without sacrificing expressivily.
Homophily in the Pokec dataset. As noted the main paper, the classification results for the Pokec dataset in Table 4 exhibit behaviour that diverges from other heterophilic datasets. In particular, we observe notable accuracy increase when using Geom-4, especially for undirected edges: accuracy rises from 62% with Binom-3 to 72% with Geom-4. While Pokec typically follows the heterophilic trend whndeehere undirected embeddings underperform compared to DirSwitch-r and MultiDir-r-his pattern is reversed for Geom-4.
To understand this, we need to examine the structural properties of the Pokec dataset. Pokec is an online Slovak social network, with nodes representing users and labels corresponding to reported gender. As reported by Lim et al. (2021), who curated this benchmark, the graph heterophilic at the 1-step level due to the predominance of heterosexual connections. This is reflected in low 1-step homophily score of 0.43.
However, the homophily increases significantly at the 2-step level, rising to 0.61. This indicates that while direct connections tend to be between users of different genders, the extended 2-step neighbourhoods are more gender- honndeeoo.mmg..euuu.. In such cases, undirected smoothing becomes more effective, especially when the embedding method emphasizes these mid-range neighbourhoods.
This precisely what the Gcom-4 distribution achieves. As seen in Figure 11d, one of its components is Geom 2; r = 3), which emphasizes 2-step neighbourhoods more than the other multi-scale distributions. This focus on 2-step structure explains the performance gain observed with Geom-4 and undirected edges.
49

---

Published in Transactions on Machine Learning Research (06/2025)
Table 15: Further investigation into the Pokec dataset. The walk length distributions are single-scale indi- cator distributions that place the entire probability mass on a single valule.
(a) p 512
(b) p 1024
EDGE DIRECTIONS
12=0
1
1
1x=5
EDGE DIRECTIONS
1;=0
1x=1
1k=2
1
DEFAULT
61.410.1
63.01o.1
63.2
62.5=0.1
DEFAULT
61. 01..1
63.020.
63. 13.1
62.5
UNDIRECTED
61.4+001
63.0a0.1
69.9
66.2=011
UNDIRECTED
61.4.0.1
63.0
69. 69.9+o.
66.2
MULTIDm--1
61.410.1
63.410.1
65.310.1
63.3
MULTIDuR-1
61.410.1
63.4
65.310.
63.310.1
MULTIDIR-2
61.4+0.1
63.4
68.0+0.1
63.9=0.1
MULTIDIR-2
61.4
63.4
68.0+0.1
63.9+0.1
DISSwIrcH-1
61.4+n.1
63.4
68. 040.1
66.3=0.1
DIRSwIrCH-1
61.4
63.4
68 08.00oo.1
66.3
DIRSwIrCH-2
61.420.1
63.420.1
68.020.1
66. 100.1
DIRSWIrCH-2
61.420.1
63.420.1
68. 08.020.1
66. 1
DIRSWITCH-3
61.4+u..
60.7.0.1
67. 100.1
63.5=a.1
DIRSWITCH-3
61.4+0.1
63.4=m.
68.0so.1
65.9+0.3
To further validate this interpretation, we conduct an additional experiment using indicator walk length distributions that place all probability mass on a single step length:
{1 if
P. = 1==
(35)
otherwise
This isolates the effect of cach specific neighbourhood scalc. The results, shown in Table 15, confirm that 2-step neighbourhoods (1x=2) yield the highest accuracy for undirected edges. In contrast, no similar perfor- mance gain is observed for directed edges (Default), reinforcing the notion that the combination of undirected smoothing and mid-range reachability key to improved performance on Pokec.
Beyond explaining this anomaly, the analysis highlights a broader point: spectrum. The optimal embedding strategy may vary across this
homophily and heterophily are
not binary properties but exist spectrum, and models tailored exclusively for one end may perform poorly on datasets lying in the middle, This underscores the utility of DirSwitch, which we have shown to perform consistently well across both homophilic and heterophilic settings.
Unsupervised community detection. Our evaluation of DirSwitch in Section 6.3 focused on node classification, which offers a convenient and objective metric: classification accuracy.
In contrast, evaluating unsupervised downstream tasks is more challenging, as these tasks often lack single 'correct' solution. For example, many valid groupings of nodes can exist in a graph, yet only one such grouping is typically labelled for evaluation. Similar issues arise other unsupervised tasks such as anomaly detection. As result, these evaluations often require more nuanced analysis.
Nevertheless, since DirSwitch intended for unsupervised embedding learning, it is important to assess its performance on unsupervised tasks well. We therefore include a community detection benchmark. For this, we use the same proximity node classification datasets from Section 6.3, treating the node labels ground-truth communities. We apply k-means clustering (Arthur & Vassilvitskii, 2007) to the embeddings, setting the number of clusters equal to the number of labelled communities. Performance is reported using normalized mutual information (NMI), averaged over 10 runs with different random seeds to compute mean and standard deviation.
Tables 20 and 21 present the community detection results for DirSwitch-r with p 512 and p 1024, respectively. The findings mirror those from the node classification experiments: DirSwitch-r generally performs well across datasets, while the sparse citation graphs (CoCite, Pubmed, and Cora (subelj)) tend to benefit from fully undirected edge orientation.
Results on the Polblogs dataset are particularly noteworthy due to their large standard deviations. This reflects the challenge of evaluating unsupervised tasks: we interpret these fluctuations as evidence that multiple valid community structures exist, with k-means sometimes recovering the one aligned with the labels, and sometimes converging to alternative.
50

---

Published in Transactions on Machine Learning Research (06/2025)
Table 16: Node classification accuracy for message-passnng ReachNESs with p = 512 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. Each entry reports the mean accuracy and standard deviation. Bold blue highlights the highest accuracy in each column, with light blue indicating results within one standard deviation of the best. Similarly, bold orange denotes the lowest accuracy, and light orange represents values within one standard deviation of the worst.
EDGE DIRECTIONS
ARXIV GROM-UI
ARXIV YEAR GROM-Z
GROM
Pois
BINOM-3
GBÖM-4
GEOm
Pois
BINOM-3
GROM-4
DEFAULT
55.0=0.2
42.440.4
55.440.2
54.2+0.2
55.4+0.2
36.5.u.3
35 35.240.6
36.7=0.2
37.8403
38.220.3
UNDIRECTED
61.6.0.22
64.910.
67.0.10.2
69.8...2
69.1...22
36.5....
36.5.0.2
37.110.2
37.610.3
38.3.0.2
MULTIDIR-1
59.840.3
59.410.3
60.110.3
60.2.0.3
60.010.3
37.0
35.1
38.1
39.110.2
39.41003
MULTIDIR22
61.2+0.3
65. 65.3+0.3
65. 1
64.4=0.3
64.6+0.3
38.6=0.3
38. 0..00
40.520.
41.1+0.
41.0#t 11.03
MULTIDIR-3
60.9#0.3
65 55.3
65.3+0.3
64.7=0.3
39.7+0.3 64.1+0.2
40 10.2.0.3
41.4=0.3
42.1+0.3
41.3#00.
DIRSWITCH-1
61.54.0.3
65.9
67.3
69.5=0.2
68.610.3
38.220.2
37.8+0.2
39.940.
39.810.3
41.2+:03
DIRSwIrCH-2
61.540.3
65.740.2
66.74:0.3
67.8 68.9-0.3
39.5 39.620.3
40.9403
41.1
41.5.0..3
DIRSWITCH-3
60. 60.8
65.6+0.3
65.9+0.3
67.7=0.3
66.3+0.3
39.6=0.3
40.5=0.3
41.4+0.2
42.1+0.2
42.2#0.3
Eag DIRICTSOOSS
Coox-ML
Crueun
COBA
Grow
Pors
GROM-2
Baxos-33
GEoM-4|
GRom
Pois
GroseN
BrNOM-3
GroM-4
GROM
Poss
GRoM-31
BINOM-
GROM-4
DESAULT
50.6.3.1
01.913.
64/232.0
70.6e1.5
78.631.7
70.7a1.
08.4.22
74.1
76.891.9
78.2:1.0
07.420.7
54.1.0.8
60.7.o.s
60.9:0.a
61.1ano
UNDRRECTED
60.4225
68.1ana
73.8a1a
82:2s1a
63.7614
86 6
87.0
93.9g0.
02.8211
64 1.0007
68 1207
60.210.
10.1
70.0
MurnDinn1
68.5284
67.5194
75 75.2an6
77.2689
79.4
76.121
75-4
80.7210
81.9a1
65.5207
64.8209
65.3a11
63.5a10
62.7500
MULTDDIR 2
79.1+1.7
78.8+14
62.7510
80.1814
84.3e12
83.9eL.
85.1=17
86.0=14
85.8e15
86.8+12
06.7
68. 1509
66.249.9
64.5+10
63.6e11
MacriDu-3
88.1115
88.611.7
80.2a1.
84.8315
84.7354
80.2a1.
88.0
87.0g15
87.1
87.2a03
05.0aus
07.2510
64.421.0
02.0a11
61.1:0.
DreSwircH-1
72.9:10
73.752.
81.3219
85.0
85.2a1a
62.821.
4:13
89.281.8
91.5e99
90.7a11
67.520.9
69.320.7
19.9
00.2210
68.4
DisSwircH 2
79.5=20
80.8411
84.1810
85.7519
85.7
85.3et1
88.8-0.9
88.4m11
90.0a1.
88.8+13
80.7ana
68 Gens
67.4
07.4
85.8en7
DisSweren-3
82.8113
83.511.4
86.3:1.0 86.1
85.711.4
85.411..
88.2.11
87.1
88.410s
87.5
64.9103
07.1gn0 64.51099
64.7209
02.2106
EDGB DIRECTSONS
ROMAN EMPRRE
POKEe
SNAP PATESTS
Guous
Paus
Grons-44
BIsOM-3
GLOMS-4
Gzus
Pois
Gross-4
BINOM-3
GroX-44
Guosa
Poss
GuoM-4
BINOL-3
G
DEPAULT
69.3500
32.2500
67.0s0.8
49.95.0.
69.6s0.e
[80.3a0.1
59.0.0a
61.850.1
60.7a0.
Sa0.
35.0
41.7a01
39.1
40.8
10.9
UNDMEETED
667.410.
47,030a
69:3au7
6d.7sae
70.0g9.7
00.3300
59:4gm4
62.0g13
02.3a9.
71.7:0.1
30.8
29.920.0
81.7700
W2.7.0.1
39.910.4
MarnDmm11
70.1a08
40.7a9.
68.8aa
59.Gen8
71.646.
61.250.3
00.2:09
62.3
61.7a9.
67.3
40.9ana
43.4205
43.929..
46.7am1
46.2cm0
Murmiim-2
71.6106
63.2107
72.0108
68.7188
75.6167
61.619.
01:2103
03.21
62.7199
42.9.100
44.0101
45.3100
47.4100
45.0101
MucriDin33
72.020.
69.129.5
73.0200
67.4507
72,540.4
61.8
63.5
63.1
62.3e).)
62. 4502
44.2
47.2
45.250.0
46.4
44.8
DusSwrruu-1
716628
67.1199
73.8au5
09.2107
75.316.7
61.210.3
00.4gm0
62.8211
02.8199
69.3ano
40.7ano
40..8m11
40.4193
41.6am1
42.7gm44
D
71.9265
65.61877
74.720.4
70.610.7
110.
61.619.1
00:0.00
63.510.1
63.0.0..
69.9.1 1
44.2.00
00.0
44.720.
44.9100
45.2200
DIRSwIrCH 3
7188as
60.1
74.3a0a
70.1
72.750.5
61.6ss..
02.7
62.9
62.1
62.0=0.1
44.4=0.1
48.8c0.1
46.3+0.1
46.9a02
46.9
Lastly, we compare DirSwitch-r against the state-of-the-art proximity embedding methods from Section 6.4. We reuse the same hyperparameterss as in the node classification setting, without performing additional tuning (sce Section D.2).
The results are shown in Table 22. DirSwitch and APP (Zhou et al., 2017) achieve the best overall perfor- mance. APP obtains higher NMI scores on EU-Email, CoCite, and Pubmed, while DirSwitch performs best on Fly Larva. The methods are lied on Cora (subelj). As before, we do not consider Polblogs due to its high variance.
As discussed in Section 5, APP is a sampled random walk method that asymptotically performs the same matrix decomposition as proximity DirSwitch with o 0 and P. Geom(r). Tt is therefore noteworthy that APP outperforms DirSwitch in some cases.
One possible explanation explanation is that the hyperparameters-tuune
for node classification sineiiccatiommaayyy may happen to favour APP in the community detection setting. Another plausible explanation is that APP benefits from random walk sampling itself. Similar effects have been observed in recommendation systems, where sampling- based matrix factorization often outperforms direct SVD due to reduced overfitting (Koren et al., 2009). Further research is needed to better understand the relationship between the sampled factorization in APP and the explicit decomposition used in proximity ReachNEs.
51

---

Published in Transactions on Machine Learning Research (06/2025)
Table 17: Relative improvements in node classification accuracy for message-pasiing ReachNEs with 512. The values reflect the maximum accuracy for per row and dataset in Table 16. The top row displays absolute accuracies for the default edge directions, with standard deviations expressed as percentages. The subsequent rows present the relative improvements compared to the top row. The table structured with the four homophilic datasets on the left and the four heterophilic datasets on the right.
EDGE DIRECTIONS
CORA-ML CITESEER
CORA
ARXIV
RoMAN EMPIRE
ARXIV YEAR
POKEс
[SAP-PATTENTS
DEFAULT
93.5+2.9%
78. 22.6%%
61. 61.1+133%
55.4+0.5%
69.64a.9%
38.2++0.%
65.5=0.4%
41.7+0.2%
UNDIRECTED
+13.9%
+20.1%
+14.6%
+25.9%
+0.7%
+0.3%
+9.5%
-18.8%
MELrIDIR-I
+8.1%
+6.0%
+7.1%
+8.7%
+2.8%
+3.1%
+2.8%
+ 12.0%
MULrDDi-22
+ +14.8%
10.8%
+ +1..4%
+17.8%
+8.5%
+7.8%
+3.8%
+ +3.7%
MULrIDR-3
+ 16.00%
+12.6%
+9.9%
+ +18.2%
+5.0%
+ -10.4%
-3.1%
+ +13.1%
DIRSwIrCH-1
+ 16.0%
+17.0%
+ 13.3%
+25.4%
+8.3%
+7.9%
+6.8%
+2.4%
DIRSwIrcH-2
+16.7%
+15.2%
+ +12.2%
+24.3%
+9.4%
+8.7%
+6.8%
+ +10.4%
DIRSWITCH-3
+17.3%
+13.1%
+9.8%
+22.1%
+6.8%
+10.5%
-3.9%
+17.1%
Table 18: Node classification accuracy for proximity ReachNEs with p = 512 embedding dimensions. Columns correspond different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. The values denote average accuracies with standard deviations. Bold blue highlights the best results in each column, with light blue indicating results within one standard deviation. Similarly, bold orange marks the worst results, with light orange showing values within one standard devia- tion of the lowest performance.
EDGB DIRECTSONS
PIYLABNA
EU EMAIL
POLBLOGS
Guoma
Pous
Guona-Z
BINos-3
Groms-
Gxuss
Poss
Gross-ff
BExou--3
Grox-4
Goom
Poss
Gaou-M
BINON-3
Guou-4
DISAOLT
46.311..
46 1,24
48.831.8
49.2:3.0
49.8
40.1.a.3
66.6.a.s
64.2.3.5
088511
70-4236
71.7a2.7
74.7222
82.613
86.0.2.1
86.611.
UNIRRECTED
47.8820
50.4a1.
53 03.0200
55.
64.9538
50.3a3.
58 0as
70.1
75.3827
75.8c2a
77.0
70.2607
85.6811
87.422
$7.0210
MusziDu-11
48.5219
48.522
61.4223
52.5219
62.02ta
65.4210
07.0281
78.7031
763511
78.7227
81.7ata
8t.1221
86.4110
87.7a17
88.4217
MurriDin22
51.8193
61.41177
63.2219
52.769a
52.7491
74.0297
74.5297
76.2184
72.6139
70-4
87.9
57.6217
69.1211
89.2114
50.6116
M
53.4519
53.5e2.1
63.7819
54.0a10
54.7et
73.052.3
75.3e8.0
70.0e26
66.4614
63.622.7
89.0s1.4
89.5e18
80.8218
69.5220
80 80.2
DreSwircH-1 1
50.0e25
51.5k117
54.2317
58.185.1
65.4
66.4833
69.5284
74.9220
75.7523
75.4224
63.7422
84.1s18
88.342.1
87 07.5420
80.7e16
DusSwercn 2
52.4=21
02,8422
50.2=2.0
50.9321
05.5e1a
73.8822
74.0sa
74.9c27
72.6822
70.1527
87.0a22
$8.3e20
89.5e1.
87.8
90.0:1.
DisSwrren-3
74.6
70.5130
68.213.
63.9134
88.8117
$9.4116
89-711
CoRa (SUBELI)
Grow
Pous
Gross
Birosu-3
GEoss-
Gzos
Pois
Geoz i
Busoas-3
Groz- 4
Gaou
Pos
Gaost
BIxOx-3
Gaost
DESAULT
37.600..
38.2.0.6
98.950.a
38.050.5
9ss.a
71.250.7
71.0c0.7
71.3et6
70.760.7
69.9an
Sana
55.8ens
56.489.
56.5ana
St.Senu
UNDRECTED
44.720.
45.7.0.
46.4gm.
47.7106
47.3185
81.5100
81.8.n0
81.8100
82.1,00
81.5gn0
65.1gn.
65.72n.
100.
06.42n.
66.31..7
MurnDin:1 1
38.8e08
39.380.
40:0aans
40.1
40.3e00
71.5806
71.lenn
70.260.7
68 23..
08.4=0.8
55.5e0.7
35.620.9
55.5e0.7
55,3=0.7
55.3
MunnDDu-2
41.5106
42.3185
44.0105
76.0.07
74.4194
74.1ind
68-1207
58.6g4
68.7107
58.9107
MurriDinSS
42.3805
43.230.
44.3305
45.9g04
45.6193
78.3204
78.0207
77.0207
76.785.
76.0207
58.8100
50.3g00
59.040.7
58.8410
50.7g08
DraSwrren-1
44.3105
45.430.4
46 23..2655.
47.8265
47.310.4
81.1
81.3206
81.2206
81.6494
80.6107
63-42o4
64.2g07
64.6199
65 65-3107
05.0207
DiRSwITCH
48.0s0.4
80.5e00
80.961.7
61.1200
62.4807
DuaSwrzeu-3
41.8e05
45.5a0.5
44.5ana
47.1sa5
46.3.03
80.1.0.7
80.4
80.0cRT
79.500
78.65077
58.0lan7
59.Gen7
60.119.5
61.0imm
61.2en8
52

---

Published in Transactions on Machine Learning Research (06/2025)
Table 19: Relative improvements in node classification accuracy for proximity ReachNEs with p 512. The values reflect the maximum accuracy for per row and dataset in Table 18. The top row displays absolute accuracies for the default edge directions, with standard deviations expressed as percentages. The subsequent rows present the relative improvements compared to the top row. The table is structured with the three denser graphs on the left and the three sparser graphs on the right.
EDGE DIRECTIONS FLYLARVA
EU-EMAIL
POLBLOGS
COCITE
PUBMED
CORA (SUBELJ)
DEFAULT
49.8+4.1%
70.4+188
85.6+2.6%
38.9+14%%
71.3%
56.5+1.4%
UNDIRECTED
+10.7%
+7.8%
+2.0%
+22.4%
+15.1%
+17.7%
MULTIDIR-1
+5.4%
+4.9%
+3.2%
+3.5%
+0.3%
-1.5%
MULTIDIR-2
-6.8%
+6.8%
+4.6%
+13.1%
+6.9%
+4.4%
MULrIDIR-3
99.8
+7.1%
+4.8%
+17.8%
+9.8%
+5.8%
DIRSwrrcH-1
+12.8%
+7.6%
+4.8%
+22.9%
+14.3%
+15.6%
DIRSWIrCH-2
+12.4%
+6.5%
+5.1%
+23.2%
+13.5%
+13.4%
DIRSWITCH-3
+12.8%
+6.4%
+5.1%
+20.9%
+12.7%
+8.3%
Table 20: Community detection normalized mutual information (NMI) scores for proximity ReachNEs with p 512 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. The values denote average NMI with standard deviations. Bold blue highlights the best results in each column, with light blue indicating results within standard deviation. Similarly, bold orange marks the worst results, with light orange showing values within one standard deviation of the lowest performance.
EDGE DERECTIONS
FLY LARNA
BU-
POLBLOGS
GRor
Poss
Gaoss &
Dovost 3 Gaoss
Geom
Poss
Gaom di
Deros 3 Gaoss 4
Gros
Pos
GBox 2
Divox 3
Gaom
DEFAULT
54.2e0.5
55.080.4
55.760.4
56.16004
56.250.a
51.65a.0
60.7e33
59.7a1a
61.2010
61.3ena
5.8811.0
11.3535.
15.1e17a
10.3918.4
18.1e18.7
54.010
66.129
50.6103
67.7.63
57.730
6444g1
05.811
64.5210
05.310
16.92/76
25.7215
28.2g/66
30.1g120
Mmnr-D-ll
35.3205
66.019.4
50.0an5
58.7.65
57.2303
57.0
60.4g1
01.921
63.0211
03.1200
25 25.82:48
35.0:103
50.8100
34.6g
38.7
MoluDDi-2
56.4in4
57.1
57.
$7.3
58.0293
61,8s12
65.0e14
65.1
65.1en6
64.259.4
40.2
47.14108
44.7=15a
41.5a44
45.82103
Mour-Du-33
57.0206
58.4204
57.8
66.5285
27.02:66
DmnSwrrca-1
35.520s
58 68.6
57.2203
2:0.1
58.239.
30.8a23
64.0g14
65.02111
64 0200
65.81sa
17.5e.as
23 8218
$1.22179
25.72:61
DisSwerca 2
36.4
57
2e0.
58.0ans
58 9:5.4
59.0a9.3
62,8513
60.0e1.
65.820.8
65.3e0.5
64.7693
23.0m:546
30.2sm03
32.8e18.1
29 29.5s:75
29. 8asta
DisSwrrcH
57.1204
57.8 58.920.5
59.260.3
59.820.4
64.020.0
66.729.
05.0ee0.
60.4ens
50.3e99
27.3s.0.5
45.4m
32.9220
29.3e.63
Smms
Faan DIRECTIOOS]
CoCmm
Pomarn BexOM-3
CoBa (SUuEL))
GEoM
Pors
GEoN-22
Bisos-33
GEOM-4
GROM
Pois
GEose-
GEOX-4
GBOM
Poss
GBos--5
BINOM-
GBos
DISAOLE
14.912.
10.741.7
17.031.6
17.113.8
17.2:33
2.7.0a
2.7.3.0
2.7.3.0
2.420.6
2.611.
91.4214
31.8888
32.2507
33.7an7
30.35n6
UNDRRECTED
20.42111
2
20.0a10
28.0806
26.780a
11.06411
15:4:2.0
17.769.4
21.0240
20.6:a.0
43.220.4
45.920.4
46.820.4
49.820.2
48.610.3
MunnDDm11
18.7008
1733n8
17.9am7
18.7368
4.5814
4.6614
4.96344
5.1a1.
31.
81.720.
$1.910.
03.0.0.7
32.41..5
MurmiDmn22
18.1107
19.2104
20.1207
22.6106
22.416.4
5.7414
6.2113
6.611
7.74144
7.5210
35.810
36.4108
35.61007
36.2105
35.7107
Manzimms
18.109
20.2199
21.6104
23.9187
23.5164
6.912
8.0221
$2115
9.611.7
8.1gms
36.8au7
38.5gn5
37.7105
37.8105
38.12n6
DiRSwITcH
27.8
12.058.
21.3a15
18.7a80
43.0a0.
45.3e00
DusSwrrcu-1 2
19.7612
21.3e.
24.0s1.a
29.650.7
27.7
8.8432
12.1=24
11.8e24
19.054.
15.3e5a
41 11.9404
40.1
44.749.5
47.9
48.5end
DisSwrren-3
18.5109
21.111.
23.9111
29.3167
28.010.5
8.9133
11.0.25
10.5131
17.3119
13.6133
38.5105
41.7105
41.7.0.1
44.61003
43.6103
53

---

Published in Transactions on Machine Learning Research (06/2025)
Table 21: Community detection normalized mutual information (NMI) scores for proximity ReachNEs with = 1024 embedding dimensions. Columns correspond to different datasets and multi-scale walk length distributions, while rows represent various edge direction specifiers. The values denote average NMT with standard deviations. Bold blue highlights the best results in cach column, with light blue indicating results within one standard deviation. Similarly, bold orange marks the worst results, with light orange showing values within one standard deviation of the lowest performance.
EncE DnremTio
FLy LAROA
FII-RMAIL
POLBLDOS
GROM
Poss
Goow--
BINOSE-3
Goou-4
GROM
Poss
GRöM-M
BRNos-3
GROM-4
GROM
Poss
Gooxc
DINOX-3
GaoM-4
52.950.
55.0s0.4
55/6e0.4
55/7a0.4
59.1
60.0ssa
62de1a 60.5as.0
11:1418.
13.8e37.0
16.4:184
12:4a18a
UNDMECTED
06.7
55.9a0a
67.5g84
57.5203
50.2326
63.5g33
61.811
63.8gn
64.610.
11:8::5
25.0g197
26.01168
22.3
28. 28.4
MenrDDm-1
54.4an5
66.4894
50.9a04
06. 36.5.84
56.8194
51.0.41
61.5117
02.1a11
62.0.10
63.011a
20:3
29.6.337
28.0115a
36.3a:56
88.2.143
Mrna-Dm-2
57.0304
63-1g15
$3.8191.7
MonarDm-3
36.3185
67-1193
57.6103
67.7.6.1
58.3104
61.9115
65.811.0
05.7,00
65.5.05
64.3104
28 2813
48.8137a
41.7:1844
48.5111.3
45.02154
Diswerems
54.7,04
06:213.1
58.7.00
57 8.03
57.9103
53.6153
64.5g11
05.0113
64.7g11
05.011.3
11:22:41
22 22.0
23.91159
29 29.51/60
25 11
DisSwrrcH22
55.8in4
58 Ginl
57.3
Seaut
58.5499
59.5213
63.3e13
64.7tu
65.0gns
65.749.
18.2z.45
23.2
S1/7aia
27 27.92.69
DrsSwrrcs-5
65.7g11
65.2.05
31.92187
27.72170
EDGB DIRECTIONS
CoCTr
PORMED
CORA (SUBELI)
Grow-2
Bioow33
Grow-4
Grow
Grow-I/
BrxoM-3
Grow-4
Goou
Grow-Y
BIso-33
Grou-4
DEPAULT
14.7es.0
17.1413
15.7627
17.4818
10.7aa.7
2,7.0.0
2,5e100
2.8411
2,4:0.9
2.3.0.0
30.5e1.
30.951.4
31.700
33.8a07
30.3en0
UNDmECTED
20.011.3
22.7.00
23-4211
27.6108
26.2114
10.819
15.0_3.
16.513.
21.114
20.0.2.7
42.9.n.
45.61n.5
46.419.1
49.8..0.
49.01..4
17.0606
5.641a
5.4818
31.5e11
32.6:0.7
ManriDm-2
18:2105
19.318
20.1au7
22.8105
22.110.
5:1a17
68812
64431
7.2123
7.121.
36.7.08
37.0gns
36.219.7
37.1
36.4166
MurnDm-3
19.2e69
20.0a0.
21.020
24.1500
23.456.
6.6814
7.2514
8.1818
10.7817
8.8318
38.8ana
39.8
39,34.3
39.4203
38.92n4
DreSwrren-1
19.3:13
21.6109
2
27.6210
26.811
11.1240
14:3300
15.5236
21.7aa2
19:6133
42.7a05
15.1
46.410.1
10.7an3
48.4103
DiRSwircH 2
19.3e10
21.1#10
23.6208
28.6e112
27.5+12
10.3+18
13.2s82
13.9=25
21.2+4.1
17.5#89
42.450.1
44.6204
45.5+9.3
49.3:02
47 47.8=02
DisSwercu-i
19.3:12
21.0s1.
25.6s1.3
29.4:0.6
27.510.6
10.8c24
11.3a26
19.2513
14.3a5.
40.9an
41.3cm
44.1
47.8a0.
46.2cn0
Table 22: Community detection normalized mutual information (NMI) scores for proximity node em- bodding models. Bold indicate the top NMI scores, and results within one standard deviation, for cach dataset. Average and standard deviations are calculated over 10 different k-means initialisaions, and 5 different random seeds for the embedding models.
MODEL
FLY LARVA
EU-EMAHL
POLBLOGS
CoCITe
PURMED
CoRa (SURELJ)
HOPE!
46.3 + 0.8
19.9 + 0.5
9.4 1.3
2.3 0.4
0.4 +.2
12.4 1.1
APP
54.9 0.4
68.7 + 1.0
41.0 + 12.9
31.7 0.6
23.9 + 0.2
50.0 + 0.3
N
50.8 0.4
50.0 1.5
15.1 16.4
3.3
4.9 1.944. 4.6
22.0 +
DGGAN
0.7
21.1 0.4
1.4 0.0
3.6=0.0
0.1
4.2 0.0
BLADE*
54.3 + 0.8
42.5
19.6
4.1 0.6
0.4
9.3 0.6
DIRSWITCH
59.6 0.7
65.0 + 0.7
26.8 + 16.4
27.8 0.9
21.6 3.8
49.7 + 0.3
Ou ET AL. (2016)
ZHou ET AL. (2017)
KHoSla ET AL. (2020)
ZHu ET AL. (2021B)
VIRINCHI & SALADI (2023)
54


Reviews:
[{"review_id": "Jt0YCUPIOa", "reviewer": "Reviewer_fMrB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n* **Clear Motivation:** The paper clearly articulates the challenges of local sinks and neighborhood multiplicity in digraphs. The ReachNEs framework provides a mathematically sound and unifying perspective on random-walk and message-passing embeddings, offering analytical tractability.\n* **Intuitive Filter Design:** The core idea of DirSwitch—decoupling local directed steps from global undirected steps—is a simple and effective solution. It directly targets sink-induced bias while preserving essential local directional information, which is a key challenge in digraph representation learning.\n* **Insightful Analysis:** The paper offers valuable analyses of its results, such as the differing behavior of models on homophilic versus heterophilic graphs and the influence of graph densit. \n\n**Weaknesses:**\n\n* **Computational Complexity and Scalability of DirSwitch-r:** The DirSwitch-r model concatenates $2^r$ embedding components. While effective, the exponential growth in the number of components with $r$ raises concerns about computational and memory costs, especially when the base embedding dimension $p/(2^r s)$ becomes very small for a fixed $p$ or when $r$ is large. The paper acknowledges diminishing returns but could further detail these practical scalability limits.\n* **Hyperparameter Sensitivity and Guidance:** The choice of the switch parameter $r$, the walk length distribution $P_w(k)$ (e.g., Geometric, Poisson) and its parameters (e.g., $\\tau$), and the embedding dimension $p$ significantly impacts performance. The paper demonstrates these effects empirically but offers limited prescriptive guidance for selecting these crucial hyperparameters for new datasets beyond grid search.\n* **Limited Scope of Downstream Unsupervised Tasks:** The evaluation primarily focuses on node classification (often using labels in a downstream supervised classifier, though embeddings are learned unsupervisedly) and graph alignment. The utility of DirSwitch embeddings in purely unsupervised downstream tasks like community detection, anomaly detection, or link prediction in digraphs remains largely unexplored future work.\n* **Impact of Finite Walk Truncation:** While the reachability matrix $R$ is theoretically defined with infinite sums, experiments often use truncated walks (e.g., $K=12$). The potential discrepancy between theoretical asymptotic analyses of $P_w(k)$  and the practical effects of this truncation could be more explicitly discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1.  **ReachNEs: A Unifying Reachability Framework**\n    The authors introduce Reachability Node Embeddings (ReachNEs), a general framework for analyzing and developing node embeddings on digraphs. \n\n2.  **DirSwitch: Switching Random Walks to Mitigate Sink Bias and Represent Neighborhood Multiplicity**\n    To specifically address the \"local sink\" problem (nodes without outgoing edges obstructing information flow) and the challenge of representing multiple distinct directed neighborhoods in digraphs, the paper proposes DirSwitch. \n\n3.  **Comprehensive Empirical Validation**\n    The authors conduct extensive experiments on up to 14 node classification benchmark datasets.\n\n4.  **Extension to Self-Supervised GNNs**\n    The paper also showcases the flexibility of the DirSwitch concept by applying it as a digraph extension to self-supervised message-passing Graph Neural Networks (GNNs), such as GraphSAGE.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* **Essential: Enhanced Complexity Analysis for DirSwitch-r:**\n    * **Change:** Provide a more explicit analysis of the computational time and memory complexity specifically for the DirSwitch-r model, considering the $2^r$ factor for component generation and concatenation. This could be in the main text or prominently in an appendix. Empirical runtime profiling on some of the larger datasets for different values of $r$ would also be highly valuable.\n   \n* **Essential: Guidelines for Hyperparameter Selection:**\n    * **Change:** Add a dedicated subsection (or expand an existing one, perhaps in the appendix with clear signposting from the main text) discussing the sensitivity to key hyperparameters like $r$, the choice of $P_w(k)$ and its parameters (e.g., $\\tau$), and the embedding dimension $p$. This section should ideally offer some practical advice, rules of thumb, or default recommendations based on the authors' extensive experiments, and discuss the computational versus performance trade-offs.\n    \n\n* **Recommended: Exploration of at Least One Additional Unsupervised Downstream Task:**\n    * **Change:** If feasible within a revision timeframe, include experimental results on at least one additional, purely unsupervised downstream task, such as node clustering or link prediction for directed edges.\n\n* **Optional: Metric for Directionality Preservation:**\n    * **Change:** Consider discussing the possibility of a metric to quantify how much essential local directional information is preserved by the initial $r$ directed steps, or conversely, what type of directional information might be lost at longer ranges. This is more of a suggestion for future thought/work.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iOtbSkqVh0", "reviewer": "Reviewer_8Lg8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The paper is exceptionally clear and pedagogical.\n- The presented method is very flexible and easy to understand.\n- It allows fine-grained control over the way that directed edges are considered, without separating the out- and in-neighborhoods entirely or needing to learn their respective contributions.\n- The numerical experiments are thorough and convincing. They cover embeddings with or without node features on a wide variety of benchmarks.\n- Whenever some instances do not behave like the rest (e.g. the Roman Empire graph), the authors provide additional details on their individual structure and properties to explain these exceptions.\n\n## Weaknesses\n\n- Due to the thoughtful exposition with lots of context, it is sometimes hard to discern novel contributions from previously-explored ideas.\n- The difference between DirSwitch-$r$ and MultiDir-$r$ is not clear enough.\n- Unlike the local sink effect, the correct expression of multiple neighborhood structures is never quantified directly", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes new ways to leverage directed edges for unsupervised graph learning. While most node embedding techniques focus on undirected graphs, directed graphs require more involved approaches due to the asymmetric propagation of information. In particular, local sinks (nodes without out-neighbors) and diverse multi-step neighborhood structures (dependent on the direction of each step) are digraph-specific phenomena which must be taken into account.\n\nThe authors first introduce Reachability Node Embeddings (ReachNEs), a variant of linearized Graph Convolutional Networks (GCNs) where embeddings stem from a power series of adjacency matrices. Each term in the series corresponds to a number of propagation steps $k$, and the associated coefficient is given by a distribution on the length of the random walk. Crucially, the adjacency matrices considered can be either out-adjacencies, in-adjacencies or undirected adjacencies, and mixing is encouraged. The final embeddings are then obtained using either matrix factorization (in the absence of node features) or message-passing (in the presence of node features).\n\nThen, they explain how ReachNEs shed light on the importance of local sinks, and how they enable multiple neighborhood structures to be considered. Local sinks give rise to low-entropy reachability distributions, which are often mitigated by undirected propagation. To go beyond one-hop neighborhoods, one can make the embeddings multi-directional (by concatenating outputs of different sequences of transition matrices) and multi-scale (by concatenating outputs of random walk distributions with different parameters).\n\nThese considerations lead to the proposal of DirSwitch, an embedding generator which starts the random walk with a few directed steps (in or out) before switching to undirected propagation for the remaining layers. Numerical experiments demonstrate the ability of DirSwitch to tackle local sinks while preserving multiple neighborhood structures. The quality of the resulting embeddings is better or comparable to state-of-the-art alternatives.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Major changes\n\n- Wherever necessary, clarify which ideas were present in the existing literature. Some locations where this would be useful:\n  - The use of random walk length distributions for convolution filters\n  - The connection between proximity (resp. message-passing) and structural (resp. automorphic) equivalences\n\n> As a baseline for our experiments, we define MultiDir-r similarly to DirSwitch-r, but without the switch to undirected edges.\n\n- Explain the difference between DirSwitch-$r$ and MultiDir-$r$: the sentence above is not clear enough. What happens instead of the switch to undirected edges? Does the last direction in $\\sigma$ get repeated forever? Or does the sequence just stop there, keeping a length of $r < K$? \n\n> Ideally, embeddings should retain all relevant graph information, allowing them to be used independently and efficiently for downstream tasks without requiring access to the full graph. We refer to an embedding model’s ability to preserve graph information as its expressivity.\n\n- Can the expressivity of DirSwitch be evaluated in a more formal way? The evaluations on the graph alignment problem are empirical in nature, a suitable theoretical counterpart might be the Weisfeiler-Lehman test. Rossi et al. (2023) compared their Dir-GNN to a directed variant of WL, which may be relevant here too? _Note: this is a more demanding addition than the other ones in my review and thus I don't regard it as necessary for acceptance, it is mainly driven by curiosity._\n\n## Minor questions\n\n> [P7] Another modification to the definition of R is the application of the elementwise thresholding function\n\n- Does the $1/\\log n$ threshold have any special significance here?\n\n> [P13]  Unless otherwise specified, we compute truncated reachability using K = 12 steps.\n\n- Is this consistent with the graph diameters in the datasets?\n\n> [P15] To achieve this, we use ReachNEs message-passing embeddings combined with node attributes derived from graph structure, including out- and in-degrees and the four digraph local clustering coefficients defined by Fagiolo (2007).\n\n- Please give a list of the node attributes you used.\n\n> [P16] Figure 7\n\n- In Figure 7 and others like it, the comparison between DirSwitch-$r$ and MultiDir-$r$ is difficult because the pairs of models don't have the same color or the same markers. Is there a way to make it visually more obvious which pairs go together?\n\n> [P16] In the limit $\\tau \\to \\infty$, DirSwitch embeddings converge to identical representations within a weakly connected component. In contrast, MultiDir embeddings retain finer granularity, as equivalence groups in the directed case remain more distinct.\n\n- Why is that the case?\n\n> [P17] Table 4\n\n- Why are tables 4 and 6 separated? What dictated such a split between the datasets?\n\n## Typos and notation\n\n> [P2] For instance, in Figure 1b, node 1 only receives information from the sink node (node 2).\n\n- Nodes reversed?\n\n> [P30] Unlike standard rSVD, SP-rSVD also computes a second projection $H = R^T G \\in \\mathbb{R}^{n \\times p}$ in the same pass\n\n- $H$ is already used for the embeddings, this might be confusing for readers.", "broader_impact_concerns": "Nothing to mention here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CNfOEdJn7v", "reviewer": "Reviewer_DJyF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n1. The studied problem is important and fundamental to graph embedding, as the graph structural properties are relevant to all downstream embedding and learning models. \n2. The paper is written in a clear way that facilitates understanding. I can easily follow the main ideas and arguments of the paper. \n3. The experimental results are very extensive. The experiments cover 14 datasets, some of which are very large scale (>1M nodes). They also cover datasets with various properties, including both homophilic and heterophilic, dense and sparse. \n\n# Weaknesses\n1. One major weakness of this paper is that the paper seems unnecessarily long. It would be better if the authors can use more concise writings, especially Sections 1-3. For example, some background information (e.g. Table 1) can be made simpler. \n2. Some concepts in this paper are introduced vaguely and with no concrete definitions. This causes confusion when reading this paper. For example:\n\n    -  I find the first several paragraphs in Section 2.3 confusing. The authors say that \"proximity embeddings capture structural equivalence, where embedding similarity reflects spatial closeness; ...message passing embeddings represent automorphic equivalence, emphasizing local connectivity patterns and allowing for similarity between distant nodes\". There are multiple points of confusion there. First, the difference between 'structural equivalence' and 'automorphic equivalence' can be better illustrated. Second, 'structural equivalence', from my understanding, should indicate the equivalence of a node's local structures, which should be more related to 'allowing for similarity between distant nodes' used to describe message-passing embeddings. Similarly, 'spatial closeness' should also be more related to 'local connectivity patterns', also used to describe message passing embeddings. Therefore, these descriptions lead to a lot of confusion, and it is important that the authors clarify that. \n    -   In Section 3.2, the term 'expressivity' is not formally/strictly defined. The authors use node alignment in the experiments, but that is only one notion of 'expressivity'. The authors should better introduce more about 'expressivity', such as a definition, or some examples. \n\n3. Some figures in this paper are not clearly visible. For example, unnecessary nodes in Figure 1 can be removed to highlight the main ones. Figure 2 is so dense that readers cannot very clearly capture its implications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the topic of directed graph (digraph) embedding. It focuses on two main phenomena: local sinks and expressivity. This work shows that directed graphs suffer from local sinks and thus have biased information propagation on sink nodes, while also having difficulty in expressing the multiple directed neighborhoods. The authors propose ReachNE to analyze both phenomena. In addition, the authors propose DirSwitch to strike a balance between both challenges. Extensive experimental results show the existence of the challenges and the effectiveness of the proposed DirSwitch.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see 'Weaknesses'.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)