Directed Graph Transformers
Authors: Qitong Wang
Georgios Kollias
Vasileios Kalantzis
Naoki Abe
Mohammed J Zaki
Venue: Accepted by TMLR ()

Abstract: In this paper, we address the problem of capturing graph directionality using transformers. Most existing graph transformers typically capture distances between graph nodes and do not take edge direction into account. This is a limiting assumption since many graph applications need to exploit sophisticated relationships in graph data, such as time, causality, or generic dependency constraints. We introduce a novel graph transformer architecture that explicitly takes into account the directionality between connected graph nodes. To achieve this, we make use of dual encodings to represent both potential roles, i.e., source or target, of each pair of vertices linked by a directed edge. These encodings are learned by leveraging the latent adjacency information extracted from a directional attention module, localized with $k$-hop neighborhood information. Extensive experiments on synthetic and real graph datasets show that our approach can have significant accuracy gains over previous graph transformer (GT) and graph neural network (GNN) approaches, providing state-of-the-art (SOTA) results on inherently directed graphs.

Published in Transactions on Machine Learning Research (07 (024)
Directed Graph Transformers
Qitong Wang Rensselaer Polytechnic Institute
Boungg19@rrg edu
Georgios Kollias 1BM Reseorch
gkollaaSuus.ke www.assssw.iibmmm.mm
Vasilcios Kalantzis IBM Research
ekal@ibm, com
Naoki Abe IBM Reseorch
nabe wbm. com
Mohammed J. Zaki
zaki@cs.rpie ret.e..rrppi.e.. edu
Rensselaer Polytechnic Institute
Reviewed on OpenReview: https: opt.eeveee.r...eee.emmee net/ forum? id= otTFPj2isX
Abstract
In this paper, we address the problem of capturing graph directionality using transformers. Most existing graph transformers typically capture distances between graph nodes and do not take edge direction into account. This limiting assumption since many graph applications need to exploit sophisticated relationships in graph data, such time, causality, generic dependency constraints. We introduce novel graph transformer architecture that explicitly takes into account the directionality between connected graph nodes. To achieve this, we make use of dual encodings to represent both potential roles, i.e., source target, of each pair of vertices linked by a directed edge. These encodings are learned by leveraging the latent adjacency information extracted from a directional attention module, localized with k-hop neighborhood information. Extensive experiments on synthetic and real graph datasets show that our approach can have significant accuracy gains over previous graph transformer (GT) and graph neural network (GNN) approaches, providing stato-of-the-art (SOTA) results on inherently directed graphs.
1 Introduction
Graphs are one of the most general and versatile data structures encountered in diverse application domains, ranging from biology and social nerwsrks to transportation and finance. Analyzing the graphs that arise from such applications and discovering patterns in them is of paramount importance in the associated domains. An important property of graph is whether its edges are directed not. Directed graphs are natural representations of relations including social connections, human communications, paper citations, financial transactions, Web links, and causes and effects. The statc-of-the-art methods for analyzing directed graphs use Graph Neural Networks (GNNs) to learn node and directed edge encodings for tasks like link prediction Kollias et al. 2022 Salha et al. 2019), node classification (Zhang et. al. 2021 and graph-level tasks [Baaini et al. 2021
In this paper, we address the relatively unexplored problem of analyzing directed graphs using graph trans- formers (GTs). Transformers hold the promise of enhanced performance GNNs due to their ability to

---

Published in Transactions on Machine Learning Research (07/2024)
represent entities without enforcing the inductive adjacency bias (Vaswani et al 2017 and due to their dy- namic multi-head attention mechanism, in contrast. to GNNs where the attention is hardwired in static edge weights. This flexibility of GT's comes, however, with the challenge of modeling directed graph structures. Most existing GTss focus on integrating only the graph connectivity structure into the Transformer. They do not prioritize how to reflect the directionality of graph edges in their proposed architecture. This is either because some key techniques are not applicable to directed graphs (e.g. Laplacian cigenvectors (Dwivedi & Bresson )) or the edge-direction information is encoded as static, fixed scalars (either local on/out
degrees in Ying et al. 2021 pairwise shortest path distances in (Hussain et al. 2022 Ying et al. 2021
We introduce Directed Graph Transformer (DiGT), a novel GT architecture that explicitly takes into account graph directionality. The crux of this architecture is that it incorporates both edge direction and graph connectivity structure into the standard Transformer architecture (Vaswani et al. 2017] as first-class citizens. Edge direction represented by dual encodings for each graph node capturing its potential role as either a source or target of a directod edge. Source and target encodings are learned using a multi-head directional allention module that, incorporates edge channels as bias. By interpreting attention matrices as latent adjacency matrices, our technique updates node's source vector by aggregating the target vectors of the neighbors it points to, after incorporating suitable lcarnable paramcters; similarly, node's target vector update is the aggregation of the source vectors of those neighbors pointing to it.
Although the general idea of using dual encodings at each graph node has been explored in various non- GT methods for directed graph learning, its application to the domain of GT& is novel and comes with its challenges. The main difference is that existing methods leverage and rely on the existing directed graph structure: the dual encodings are statically computed based on graph properties message passing occurs using the directed graph connectivity structure. This introduces a convolutional inductive bias: the neighborhood of a node only consists of the edges of the directed graph and cannot include latent edges which could be learned and produce more discriminative node encodings for directed graphs. In contrast, in DiGT dual node encodings are dynamically learned without using the explicit directed graph structure.
We evaluate our DiGT model architecture for directed graph classification lasks. A challenge is that publicly available directed graph benchmark datasets for this task are scarce and only capture directionality indirectly, For example, the directed graph dataset in {Hussain et al.) 2022) is derived from MNIST/CIFAN CIFAR10 images which are inherently undirected. To this end, we introduce the FlowGraph family of directed graph dalasets that explicitly relate the edge direction pattern in graphs to their classification labels. Using these new datasets, as well as existing MNIST/ MNIST/CIFARE /CIFAR10 (Hussain et al. 2022), Twitter (Leskovec & Mcauley] 2012). and Malnet-tiny (Freitas et al. 2020) datasets, we empirically demonstrate that DiGT gives significant accuracy gains for the tasks on both synthetic and real graph datasets. Our extensive experiments reveal that when edge directionality is an inherent, rather than derivative, characteristic of the instances to be classified, DiGT provides state-of-the-art (SOTA) results, outperforming graph transformer based and GNN alternatives by large margin.
2 Related work
Methods for Directed Graph Learning. Farlier works on analyzing directed graphs are based on matrix factorization techniques to learn node encodings, such as Singular Value Decomposition (SVD) of higher-order adjacency matrices exploring the directed k-hop neighborhood of a node (Ou et al., 2016). or Non-negative Matrix Factorization (NMF) (Sun et al., 2019). Another line of work focuses on analyz- ing special matrix forms of adjacency information such as the Hermitian adjacency matrix of the dirccted 2020) or learning linear combinations of powers of the directed graph adjacency
graph (Cucuringu et al.
matrix and its transpose (He et al.) 2021). More recently, GNNNs have been used (Kollias et al. 2022 Tong
et al. 2020a by Zhang et al. 2021) that operate based on messagg-passing architecture and provide higher learning flexibility due to the usage of learnable weight matrices that multiply the node encodings. Graph Attention Network (GAT) (Veličković et al. 2017 is a GNN that incorporates local sell-attention resembling a transformer.
A limitation of all the aforementioned approaches is that they critically rely on the explicit directed graph structure (adjacency matrix): (a) The k-hop neighborhood learning techniques (He et. al. 2021 Ou et al.
2

---

Published in Transactions on Machine Learning Research (07/2024)
2016 Sun et al. 2019:
Zhou et al.
2017
involve matrix factorization composition of powers of known
adjacency matrices, or random walks over the graph structure. (b) Special matrix forms of adjacency information used in (Cucuringu et al. 2020;
Tong et al. 2020a) allow directed graphs as input. (c) GNNs
in (ooliaa et al.) 2022 Salha et al. 2019 Tong et al. 2020b; Veličković et al.) 2017 Zhang et al.) 2021 are
pressage-passing models, and single or dual-node encoding messages can flow only through existing edges.
Reliance on the directed graph structure introduces inductive bias during learning: latent edges that could positively contribute to the learning problem at hand can be missed as a result. In contrast, DiGT does not rely on the directed graph structure (in effect it assumes full graph connectivity) and learns the edge weights by exchanging the dual node encodings between the nodes.
We note here that the general idea of dual node encodings has also been used in several of the above works. However, such encodings are typically computed by exploiting the directed graph structure. Applying this idea in GTs is challenging because there are no assumptions on graph structure (i.e., assuming full connectivity) and they need to be learned in dynamic manner.
Graph Transformers GT's were introduced in (Dwivedi & Bresson 2021), which proposed two inspir- ing GT architecture variants. The first variant produces only node encodings, while the second variant is augmented to also produce edge encodings. Node encodings follow the standard Transformer architec- ture (Vaswani et al. 2017), while edge encodings are updated by scaling the attention matrix. They attend only to existing neighbors (local self-attention); so a strong inductive bias is enforced. SAN (Kreuzer et al.
2021 uses learned positional encodings (LPE) to enhance the learming of graph structure. SAT (Chen al. 2022 enhances the learning by extracting k-hop subgraphs. In Graphormer (Ying et al. 2021), the attention aperture critically expands to all nodes (global self-attention). They propose adding and learning node en- codings that are functions of input and output degree cantralities (centrality encoding), and arbitrary node pairs are represented by two bias terms to the attention matrix (spatial and edge encodings). In EGT (Hus- sain et al., ) they combine ideas from (Dwivedi & Bresson (021) (separate channels for nodes and edges, scaling and gating the attention matrix) and from (Ying et al. 2021) (global self-attention, bias terms from spatial encoding, however, learned from the edge channels) to yield an ellective GT approach. Recently, hybrid models that combine graph neural networks with graph transformers have been proposed, such as GraphGPS (Rampášck et al. 2022) and Exphormer (Shirzad et al.) 2023). that attain competitive perfor- mance results, while aiming at scalability. GraphGPS is a framework for combining pluggable encodings, local message passing, and global attention modules; Exphormer introduces a sparse attention mechanism based on global virtual nodes and expander graphs. In Digraph Transformer (Digraph-T) (Geisler et al., 2023) they learn over directed graphs using Transformers, leveraging the eigenvectors of the Magnetic Laplacian matrix (Furutani et al. 2020) as position encodings, as well as directional random walks. Whereas we also use position encodings (PE), including the Magnetic Laplacian, is only a minor component of our overall architecture. Our main contribution is the integration of bidirectional allention for graph transformers.
Our DIGT approach is global self-attention transformer, learning both dual node encodings and edge encodings (dual-channel architecture). A node encoding in DiGT consists of a pair of source and target vectors that caplure the edge direction semantics. Therefore, in downstream tasks that require directionality and take node encodings as input, DiGT provides embeddings of high discriminative power. In comparison, Graphormer (Ying et al. 2021), EGT (Hussain et al., (022), and the other graph transformers (Dwivedi & Bresson 2021 Zhang et al.) 2020) produce only single-vector node embeddings that cannot differentiate the direction of edge; and, already mentioned, directed GNNs (Kollias et al., 2022 Salha. et al. 2019 Tong
et al. 2020b Veličković et al. 2017: ZZhag et al.) (022)) produce dual node embeddings that suffer from
convolutional inductive bias, that is restricted to only the given neighborhood structure.
3 Directed Graph Transformer Architecture
We now describe our directed graph transformer DiGT, whose main components are shown in Figure I DiGT uses three main ideas: dual node embeddings - for source and target representations, with a HITS- inspired (Keiinerg) 1999) aggregation combined with learnable implicit adjacency information via directed attention, as well as using k-hop neighborhood virtual edges. Table shows the notations used below. Our model contains multiple layers and multiple attention heads, but we omit these for ease of presentation.
3

---

Published in Transactions on Machine Learning Research (07/2024)
Table 1: Mathematical Notation
Notation
Meaning
Shape
Notation
Meaning
Shape
graph nodes
graph edges
Namber of sodes odges
d.d.
Dimersion of ipput mode featuze or edge featuze
Namber of beads
Diuacssoo of attention layer. d
Adjacency matric
D D73
& hop filter matrix from source target target
eneadings source targes modes
Ben, Ere
Edge features for souroe-target
D.X.R
Qs. Ks. Vs
Query, Key. Value for source zodes
dp
Ger. Grs
Gate matrix for source target target source
X
Kr. Vr Y
Query, Key. Value for target bodes
dp
Asr. Ars
sefunox for target langet-suurce Attection matrix after sufamax for source- target or sarget-souzce
Attention
Value represcutation
d,
Apr, Ars
Esy
Qy
Aur
15
Poieet & Stale
Are
Car
Vx
Grr
Poyest
Ars
Vr
7
Kr
Eys
Exz
(a) DIGT source and target at- tention head
(b) DIGT layer structure
Figure 1: The two figures show the DiGT architecture. In aa) the attention is calculated in both directions for each node. Then, in [b) softmax operation is applied on the stacking dimension to compute the importance of directionality (i.e., softmax is over the ST and TS axes). Blue nodes and arrows represent the flow of source embeddings, red nodes and arrows represent the flow of target embeddings, and purple nodes represent the operations on both source and target embeddings.
3.1 Input Layer
We represent a directed graph as G(V, B); V the set = |V| graph nodes, E'= is the set of its m = [E| directed edges. Each node i equipped with pair of vectors in Rd 1 s m: (i) vector 8; encodes i's role source, which is the same for any of the directed edges it participates in as source, and (ii) vector t; encodes i's role target.
Positional encodings play an important role in comprehending graph structures for GNNs. Traditional methods, such as the graph Laplacian, are limited to undirected graphs due to their requirements of a symmetric adjaconcy matrix. In our study, we select two techniques to overcome this limitation: Singular Value Decomposition (SVD), and the Magnetic Laplacian (Geisler et al. 2023).. We detail these two positional encoding methods in the Appendix. For a given adjacency matrix A, we denote by Ps and Pr the positional encodings for the source and target nodes, respectively. When input node features N, are available (set , 0, otherwise), the input/initial node embeddings for the DiGT model are given
S L. + (((
T= L. + (N)
(1)
where La, L, and Lf are learnable linear transformations (subscripted as for the sources, t for targets, and f for input features), and S, T Raxd To encode the edges, considering input edge features E, (set E, 0 otherwise), the input//niiial edge embeddings for the DiGT model are given as
EsT = L.((6Ac)..-......)) + Lef(E))
(
where Le is an embedding layer, Lef is a learnable linear transformation, and 6at is the shortest directed path distance from source s target t, clipped at maximum k-hops (if is not reachable from 8, we set
dat k 1). The result, Esr E Raxnxh is the matrix of h dimensional edge embeddings, and we set Ers the transpose of EsT along the first two dimensions.
4

---

Published in Transactions on Machine Learning Research (07/ (204))
3.2 DiGT Attention Layer
Inspiration: Given the dual node encodings, we need to determine the relationship between the source and farget encoding vectors of different nodes, which will be used for updates in our GT architecture. For this, we draw high-level inspiration from the HITS (Kleinberg) 1999) centrality algorithm that computes two scalar-valued hub and authority scores for each node in a directed graph a source node with a high hub score refers to (or points to) target nodes that contribute relevant information (in our case, for learning); and thus gain clevated authority scores. Consider for the moment one-dimensional or scalar source and larget node embeddingg,, 8i and 4,, which serve as the hub and authority score, respectively; we can express their relationship s, -ine tj (i.e., good hubs point to good authorities) and t, Egnn (i.e., good authoritics are pointed to by good hubs).
Generalizing to our d-dimensional source and target encoding veclors S; and t;, we could analogously write s; = E; Autt and t. = Σ, AررS,, or more compactly as AT and T = A S. Conceptually, s; and t, play the role of milti-dimensional hub and authority scores.
The key insight in DiGT is that we should not rely on the fixed adjacency matrix A; rather, we should construct an implicit adjaceney matrix, denoted A, by exploiting the atlention mechanism. A straightforward approach to compule A could be A ST However, need to make this learnable. To allow the flexibility of learning weight matrices for computing the implicit adjaccncy we use dual attention mechanisms. For the source nodes S, let
Implicit and Directed Adjacency via Attention:
Q5 S Was and similarly for the target nodes T, let
Kg S W KS
Vs s S Wvs
(3)
Ky= = WKT
=== = T Wer
(4)
where all W's E dxd, learnable weight matrices, and dp is the projection dimensionality (suitably scaled down). As shown in Figure la obtain a pair of attention matrices
ÅSt (QsKrT//0 /V
ATS (Qrks Tisssv/vV /V
That is, the attention matrix Ast treats the source nodes as queries and the target as keys to compute their similarity, and vice-versa for Ars (see Figure la
Edge Feature and Neighborhood Attention: We now allow for the edge channels to directly influence the attention by introducing the edge feature matrix, EsT E " and gate matrix, Ggr E RaxaxA which linear transformations from EsT (with added layer norms). Further, Ers and Grs are their transpose matrices, respectively.
Next, we localize the attention from node channels to the k-hop neighborhood around each node. This is implemented by masking the attention matrix along with the edge bias via element-wise product with the binary k-hop filter matriz, defined as D( {1 iff 8, S k, 0 iff 8i > k), where 8, denotes the shortest path distance from node i to node j. Thus, the attention matrices, denoted A, for this layer are given as:
À ST = ST EST) ④ D (k)
D
A = (ATS + Ers) @ D
where & and D are the filter matrices in the two directions. This way we control the attention to be within the k-hop neighbors around each node.
For any two nodes within a graph, our objective is to determine the direction of message passing between them. To achieve this, we compare the attention values in both directions. The larger of these values will indicate the predominant direction of message passing. Therefore, unlike traditional transformers that compute node importance via softmax along each row of the attention matrix,
Directional Attention:
5

---

Published in Transactions on Machine Learning Research (07/2024)
stack both Asr and Ars and compute the softmax along the stacking direction (Figure this mechanism), given
1b visualizes
AST, Ars = softmax (AT ATS).
(7)
Note that directional attention combined with the k-hop filter matrix D(A) applies a soft-thresholding for unidirectional edges, as opposed to the hard-thresholding that is typically used when masking with -00. That is, if we were to set D (k) -oo if diz > k, then information would flow only along the direction that exists, and it would ignore the opposite direction for unidirectional edges. We show conclusively in our ablation study in Section 4.3 that soft-thresholding yields better performance.
Finally, we enable the flow of information between nodes by gating their value representations prior to aggregation; this is realized as multiplication by the sigmoid function, a(), of the entrics in gate matrices, GST and Grs, resulting in
Y= ( VT) + ((ÂTs (GTs)) Vs),
(8)
where Y e Ruxd, is the value representation for one head. So, when we have h = d/dp heads, we concatenate all of them (and add layer norm) to obtain the final value reprosentation Y E Raxd for the next step. Also, the different DIGT layers do not share edge embeddings and this is also true for bias and gale matrices.
3.3 Output Layers and Prediction
After each DiGT layer, we take the combined value encoding Y, and use layer normalization and feed-forward network modules with residual connections to produce the node and edge encoding outputs for DiGT layer. These outputs become inputs for the next layer. Thus, the updated dual encodings S', T' are given as:
s' = f(=ssLys(Y))
T f(Lv((Y)),
(9)
where, Lys and LvT are two linear transformations followed by non-linear aclivation ʃ (with layer norms and residual connections). To obtain the updated edge embeddings E's E Raxaxh for the next layer, we apply a similar function on AsT as follows:
ESg = f(Le(AST))
(10)
Lastly, after the last DiGT layer processed, the encodings X = concat(S', T') are driven through some final task-specific learning modules. These are typically multilayer perceptron layers (MLP) for tasks related to node and edge learning (node classification, link prodiction), or pooling layers for graph-level lcarning (graph classification, graph regression). For the directed graph classification task, we use global average pooling our main method for producing representation/ /encoding of the whole graph; this is essentially the average of the final node encodings. We also experiment with the method of virtual nodes based pooling Hussain et al.) 2022): a clique of artificial nodes (virtual nodes) are added to each graph and connected to all its nodes (with the edge directed only from a graph node to the virtual nodes). After training, we average the concatenated source and target node embeddings of the virtual nodes and leverage the same final MLP layers for the downstream task. We examine the effects of these choices in the ablation studies.
4 Experiments
Our experiments were performed on NVIDIA V100 GPUs, with 32GB memory, using PyTorch. We provide additional experimental details in the Appendix.
4.1 Directed Graph Datasets
There are several directed datasots used previous studics, such as MNIST (LeCun & Cortes. 2005
CIFAR10 (Krizhevsky et al.] 2209), Ogbg-Codes (Hu al.] 2020), and Malnet-tiny (Freitas et al. 2020 See the Appendix for dataset statistics.

---

Published in Transactions on Machine Learning Research (07/2024)
Table 2: Randomized directionality via edge flips: Model performance
NNIST
CIFAR1O
Model
Code2
Model
Malnet-tiny
Malnet-sub
EGT
98.17 +/- 0.09
68.70
1/- 0.41
DAG DAG-Plip50
20.2 +/-
Exphormer
94.02 +/- 0.21 87.90 /- 1.65
79.71 +/- 0.37 71.51 1/- 0.45
EGT-Flip50
97.99 /- 0.09
67.28 /- 0.38
19.0 1/- 0.1
Exphormer- Plip50
Model
FlowGraph2
FloxGraph3
FlowCraph6
Twitter3
Twitter5
DiGT
98.00 +/- 0.54
74.61 +/- 1.95
46.03 +/- 0.41
93.33 +/- 0.64
86.67 +/- 0.52
DiGTT-Flip00
49.67 +/- 1.39
32.33 +/- 1.66
16.78 +/- 0.04
82.96 +/- 1.13
65.44 +/- 0.38
MNIST and CIFAR10: Hussain et al. 2022) used MNIST and CIFAR10 as collections of directed graph inputs for their graph classification lask, following the introduction of these datasets in (Dwivedi et al., 2020). They are originally collections of images (respectively, of handwritten digits and objects) and not graphs. In (Dwivedi ct al. 2020), they convert an image to a directed graph by first segmenting the original image pixels into sets of (coarser-grained) SLIC superpixels (Achanta al. 2012). Directionality in the edges then follows from the fact that if a superpixel i has fewer neighboring superpixels than one of its neighbors j. it will tend to connect to rather than the other way around (i.e., i + j will have more weight than j + i).
Malnet-tiny and Malnet-sub: Malnet-tiny provides a graph classification task for five different types of malicious software. Tt contains 5,000 graphs, and each graph contains less than 5,000 nodes. Its graph size is an obstacle for many graph transformers. We apply a filter to generate the Malnet-sub dataset: we choose the graphs with fewer than 500 nodes for training sets, and those with fewer than 2,000 nodes for both validation and test datasets. As a result, the Malnet-sub dataset contains 2,444 graphs. Malnet-sub dataset is more challenging than Malnet-tiny since forces the models to effectively generalize from smaller graphs in the training data larger, unseen graphs in the validation and testing phase:
Ogde-Code2: The Ogbg-code2 dataset a collection of Abstract Syntax Trees (ASTs) from thousands of Python method definitions extracted from 13,587 different popular repositories on GitHub. Given the AST and node features, the goal is code summarization, i.e., to predict the sub-tokens forming the method name.
4.1.1 Importance of Direction: Random Flip Test
Even though the above datasets are purported to be directed, our analysis points out a severe limitation, namely, direction plays little no role in these datasets, unfortunately.
To evaluate the role of directionality in these datasets, we designed a simple random flip test. In essence, for given edge flip probability, say 0 (c.g., 0 E (0.25, 0.5)), we flip each edge (u, v) with probability 0 during each of the training, validation and testing steps. If, even after randomizing the edge direction for fraction of the edges, a model consistently achieves accuracy comparable to that on the original dataset, this provides strong support that directionality not a crucial factor for that dataset.
Table 2 shows the results with 0 0.5 (i.e., 50% of the edges are flipped). We use EGT (Hussain et al. 2022 the MNIST and CIFAR10 graphs, Exphormer (Shirzad et al. 2023), which is the SOTA on Malnet-tine tiny, and
DAGformer [Luo] 2022), which is the top-performer on the 0gbg-Code2 leaderboard (Hu et al. 2020 We observe that despite altering the direction of almost half of the edges on MNIST, CIFAR10 and Ogbg-Codez. the results remain largely unaffected: predictive performance drops at most 0.42% for MNIST, 1.42% for CIFAR10, and 1.2% for Ogbg-Code2 in absolute terms. These tiny differences indicate that directionality is not important for those datasets. On the other hand, there is a significant performance loss on Malnet-tiny and Malnet-sub indicating the importance of directionality for these. See the Appendix for results different 0 values and other models, too.
I For example, the current state-of-the-art model, Exphormer (hirzad et 2023 achleves high accuracy of 93.38% Malnet-tiny, while its performance drops to 79.71% accuracy on Malnet-eub when constrained to 100,000 parameters.
7

---

Published in Transactions on Machine Learning Research (07 (2742)
4.1.2 Inherently Directed Datasets
Having shown that existing datasets used to evaluate directed graph transformers violate their raison d'être, we propose two classes of inherently directed graphs (see Appendix for details of dataset generation).
FlowGraph datasets: We introduce a family of directed graph datasets that explicitly relate the edge direction pattern in graphs to their classification labels. In each graph, we create multiple clusters of nodes interconnected by random edges and arrange these clusters in sequential order. For directed edges linking nodes in consecutive clusters, namely cluster and cluster 1+1, we define directional flow: set percentage f% of edges flow from cluster / to I+ while the remaining 1 - f% edges flow in the reverse direction. These directional flow percentages vary across different classes. We generate three distinct graph datasets with 2, 3, and 6 classes. Table 2 reveals that directionality is important in these datasets: FlowGraph2 experiences a 48.33% drop in performance when 50% the edges are reversed. Large drops are observed for the other FlowGraph datasets, too.
Twitter datasets: We use 973 directed ogo-networks from Twitte each corresponding to some user u (ego): the ogo-network between u's friends also referred to as alters (Leskovec & Mcaulcy 2012). If nodes Us By are in u's ego-network then follows them and if 22 follows by then there directed edge U; + by the ego-network. We introduce perturbations to each of these real ego-networks where perturbation either (i) rewiring of an existing edge, (ii) reversing of the direction of existing edge. Leveraging these perturbations, we create two distinct graph datasets: Twitter3 with 3 classes and Twitter5 with 5 classes. These classifications are based on varying percentages of perturbed edges. In Table 2 we observe significant drops in performance with 50% edge flipping: Twitter3 shows an absolute drop of 9.37%, whereas Twitter5 shows a drop of 21.23%, indicating that directionality plays an important role for these datasets.
be
4.1.3 Degree of Directionality
To further cement the role of directionality for dataset, we propose another measure the degree of directional- ity. Let SCC denote a strongly connected component. in a directed graph (a maxi- mal subset of mutually reach- able nodes). Further, given the set of m SCCs of directed Smh, define the SCC entropy of the graph as follows: F(S)
Flow2
Flow3
Flows
Twitter3
TwitterS
MNIST
Sm GG
6
CIFAR10
Malnet-sub
2
0
graph, S =
Em logp; where Pt S.l/n, i.e, the distribution of
Figure 2: SCC entropy for each class for each dataset SCC sizes. A low entropy means that most nodes are mutually reachable, and thus directionality is not expected to play a big role. On the other hand, larger SCC entropy values, with maximum value of log indicate smaller reachable components, which means that directionality is clearly important.
Figure 2 plots the SCC entropy for the different datasets; for each class, we plot the average and standard deviation We can see a very clear trend. FlowGraph classes are inherently dirccted, with larger entropies, and Twitter captures the inherent directionality of the "follow" relationship between entities, exhibiting lower entropy values. More importantly, the derived MNIST and CIFAR10 have no inherent. directedness, and their entropy values are extremely low. We will show that DiGT performs even better when direction matters, such as for FlowGraph, Twitter, and Malnet-sub.
hhtpps///saa stanford, edu/ wwt.//ata/aooooviteeeeeeeee html We da consider ogb-code2 hurther, since directionality important for this dataset, and the task code summa- rization instead classfication.
8

---

Published in Transactions on Machine Learning Research (07/2024)
Table 3: Classification accuraey of DiGT against various GNNs and GTss
Model
Flovtrapa2
FlowGroph3
Floytrapae
2uitter3
Twitser5
Haloct-sub
MIIST
CEFAR1O
GCN
Kof & Woaling
2016
57,50
4 1.27
05. 25 4:- 0.88
50,36
4/- 0.50
76.24 -/- 0.56
61.23 4.- 1.07
78.75
4 0.21
50.71 4 0.22
55.73
0.28
GAT
2311
$1.22
1.50
58.83 +/- 1.07
50.51
0.38
74. - 1.50
56.79- +/- 0.05
79.56
1.05
06.54
4.- 0.21
64.22
0.41
Galedrec
sitbeer 2015
p1.35
0.24
05.61
+ 0.01
55.22
+/- 1.31
67.49 - 0.35
05.75
+/- 1.14
80.50
1.74
00.34
4/- 0.14
61.81
-/- 0.31
Griph
Sate
0:43
05.00
+ 0.20
+/-
70:28
07:20
1402
1.73
00 4/-
0:31
0.64
1.52
2.02
4,-
Daliosli
Brseet
0.52
+:- 0.00
1.12
50:66 -/-
79.65 0.65
+:- 0.61
96.76 +/-
68.02
0.16
1.54
0.65
0.46
55.39
68.13 1.05
0.23
96.52
66.96
0.30
+:--
57.21
70.77
1.52
1.77
72.05
1-7- 1:16
56.49
73U4 1-- 1.47
72.03
1,28
58.17 1/1
Explarans Sturand
2025
+/- 0.44
72.81
4:/-
+/-- 0.50
50.76 -/--
72.72
70.71
+/-- 0.57
98.85 +/- 0.04
74.00
+//- 0.18
98 -/- 0.54
74.61
1.95
46.03 +/- 0.41
93.33 +/- 0.64
56.67 +:/- 0.52
80.78 +// 1.76
98.02 17-
07.00
4.2 Experimental Comparison
We compare DiGT with GCN (Kipf & Welling 2016), GAT (Veličković et al.
2017). ; GatedGCN (Bresson
& Laurent )017), GraphSage (Hamilton et al. 2017), and PNA (Corso et al.
2020 as the representatives
of GNNs, and with GT (Dwivedi & Bresson 2021 SAN (rreuzer et al 2021 EGT (Hussain et al. 2022).
Exphormer (Shirzad et al. 2023), and Digraph-T Geislerr et al. 2023 as the representatives of GTss. We train all the models on FlowGraph, Twitter, Malnet-sui and MNIST/ /S///CIFARR respectivcly, restricted to 100K parameters. The accuracy results are listed in Table 3 Additional details can be found in the Appendix. Our source code is available via github: https://github.com. Qitong- Wang/ Diirected-Grapeee Transformers
For MNIST and CIFAR10, which are not intrinsically directed by construction, DiGT maintains competitive performance over GT and EGT, experiencing only minor decrease in accuracy. On the other hand, we observe that for all the datasets where direction is important, DiGT outperforms existing models providing SOTA results. For instance, the FlowGraph6 dataset, DiGT outperforms the next best model EGT by 3.06% in accuracy; the performance gains against GNN alternatives are even larger. Likewise, for the Twitter5 dataset, DiGT outperforms the next. best model, GT, by over 7.12% in accuracy. Among the GNNs, PNA is the best but lags behind DiGT by a huge margin. For Malnet-sub, models that are adept at capturing local information, such as GCN and Exphormer, show good performance. In contrast, traditional transformers that focus on the whole graph-level attention, like GT and EGT face more challenges for this task. However, DiGT surpasses the next bost model, Exphormer, by 1.07% in accuracy. These results indicate that the dual attention mechanisms in DiGT can effectively learn both local and graph-level information.
4.3 Ablation Studies
We present ablation studies demonstratinng the elfectiveness of incorporating dual-vector atlention matrices and k-hop virtual edge filters. Additionally, further ablation studies regarding other architectural components of our models, such as positional encodings and virtual nodes, are detailed in the Appendix.
4.3.1 Single-Vector Node Embeddings
To study the benefit of our dual node encodings, we constrain DiGT to leverage only one vector embedding per node, and refer to this version as DiGT-OneEmb. This kind of ablation makes DiGT similar to EGT, so the expectation is to get accuracy values closer to EGT. Results in Table g confirm this intuition. On average, the ablated DiGT model scores between the reported values for DIGT (higher) and EGT (lower) and much closer those of EGT, especially in the case of Twitter datasets, e.g., 86.04 0.45 versus 0.73 in EGT for Twitter3.
Table 4: Ablation: Single- Vector Node Embeddings.
Mixial
PlouGraph2
PlowGraph3
TeitterS
TwitterS
Melnetrrahh
CTPARLO
DXGT
98:00 +/-
74.61 +/- 1.05
46.03 +/- 0.41
83.33
+/- 0.64
80.07 +/- 0.32
80.78 +/- 1.76
98.02 +/ 0.10
67.05 +/ 0.20
IiGT-On-Fub
06.75 +/- 0:41
73.67 +/- 0.85
13.81
+/- 0.62
87.50
-/- 0.50
73.00
+:-- 0.38
70.07 +/- 1:30
07.40 +/- 0.72
66.78 +/- 0.90
RCT HHuosin as all 2023
96.00 +/- 1.67
72.06 +/- 1.16
12.07
+/- 0.02
86.48
-/- 0.73
73.94 +/- 1.47
72.36 +/- 1.38
98.17 +/- 0.09
68:70 +// 0.41
9

---

Published in Transactions on Machine Learning Research (07 (224))
(a) Adjacency Matrix
(b) DiGT Attention
DIGT OneEmb Attention
Adj Matrix
Source to Target
Target Source
Single Attention
10
Columins
Coluinns
Calumis
Co Columms
20
20
20-
30
30
30
20
20 Rows
30
0
10
20 Rows
30
10
20 Rows
30
Rows
Attention Value
Figure 3: Visualization of adjacency and attention matrix for DIGT, for selected Malnet-sub graph.
Additionally, Figure dataset. Figure 3b)) provides pair of attention matrices in DIGT: the left figure shows the attention directed from the source to the target, namely AsT in Equation & and the right one depicts the attention flow from the target the source, namely Ars- Figure ((c) shows the attention for the DiGT-OneFmb variant. For all the figures, we sum up the last layer of the attention matrices from all heads and normalize the values from to 1. Brighter colors correspond to higher attention values, indicating greater importance of the information at that specific location. In summary, these figures visualize the status of the attention matrices, which are ready to be multiplied (after gating) by the values Vs.Vs.
B visually represents attention matrices for sample graph within the Malnet-sub
Traditional transformers struggle to discern critical patterns within a graph. This challenge is shown in Figure 8 (c), where the most informative neighboring node for any given source node is indicated by the brightest node in cach row. For instance, the red rectangle highlights one such pair. However, this does not necessarily imply that these two nodes are pivotal for the entirety of the figure. On the contrary, in Figure bb), the presence of bright flow within the red rectangle suggests that all these nodes crucial for the overall graph structure. The application of softmax across the stack direction of the two attention matrices enables the model to discern the relationships between cach edge and its corresponding reversed virtual edge within k-hops, and the information flow comes from the union of the original graph and its reversed counterpart.
4.3.2
k- Hop Virtual Edge Filters
Graph transformers, operating under the assumption that all nodes are interconnected, can be interpreted as adding virtual edges aronn all nodes. We introduce hyperparameterr to constrain the addition virtual edges, which has two critical functions: First, it sets the boundary for the shortest directed path distance between two nodes in Equation 2 which contributes to the edge features EST, Ers and gates GST, Grs-
Second, determines the D ST Drs virtual edge filters in Equation 6 which restrict message passing among distant nodes. Above, we demonstrated that DiGT effectively captures graph patterns and identifies key node pairs. We now present an ablation study to explore the impact of varying k the model's performance, where 'unlimited" refers to setting k = 25 sufficiently large number for the edge embedding layer Le and
(k)
not multiplying with D ST: D/3 filters in Equation 6
(k) D
Table 5: Ablation: Number of Hops
Model
Floutrapp22
Flowdrapha
FLovtraphs
Tuitter3
Testters
Halnet-sub
1011T
CIFAR1O
DIG/T
98.00 +/-
+/- 1.95
40.03 +/- 0.41
+
+/- 0.52
+/- 1.76
+/- 0.10
67.05 +/-
DiGri-hop
98.58 +/- 0.24
74.29 +/- 1.10
43.92
4- 1.83
93.90 +/- 0.08
55.97
1.30
80.53 +/- 0
97.23 +/- 0.28
64.50 +/- 0.84
DIGIT hop 3
98.00 +/ 0.54
74.61
+/- 1.95
48.03 +/- 0.41
93.33 + 0.64
86.67
+/- 0.52
80.00
+/ 0.56
98.02 +/- 0.10
67.05 +/- 0.20
DiGTT-hop
97.00
0.71
0.5
9208
0.56
65.36 +.- 0.94
06.42
//-100
92.42
+/- 1.76
+
DXCT-hhop undinsttd
56.00
4/- 0.71
71.61
+/- 1.17
44.75
1.37
32.50
0.58
86.60
1.69
78.31
4/700.4
96.62
0.45
65.00 +/- 0.10
10

---

Published in Transactions on Machine Learning Research (07 (204))
(a) Adjacency Matrix
(b) Number of Hops: 1
Adj Matrix
D2 Filter Matrix
Source to Target
Target Source
20
20
20
20
Calumns
00
80
60
60
20
60
90
20
46
60
80
20
60
Rovess
RONS
(c) Number of Hops: 3
(d) Unlimitted
2 Filter Matrix
Source to Target
Target to Source
DCj Filter Matrix
Source to Target
Terget to
Couumis 26
20
20
20
Couumss
Colunns
Columers
Columins
K0-
40
80
00
60
80
60
80
80
80
40
0
20
40 Raws
60
100
0.0
0.2
0.4
0.6
0.8
1.0
AJJention Vi ue
Figure 4: DiGT-attention matrices for a selected FlowGraph6 graph.
Figure illustrates that increase in k leads to more connections among nodes. In Figure bb, with k
the model behaves similarly to GNN. It has the ability to capture relationships beyond the adjacency matrix by using additional layers, but it is less effective than with higher values. Figure ( illustrates a scenario with no hop limitations, allowing unrestricted message passing among all nodes. We can see that the model capable of reconstructing the graph structure even under the assumption that all nodes are connected. However, the comparison in Table iillsstaate that DiGT-hop unlimited does not achieve state- of-thc-art performance
any datasets. On the other hand, the integration of filter D matricos, which inform the model about the graph's structure, effectively improve the model's performance. As seen in Figure (ic), when k == 3, the filter matrices enhance the connectivity of the original graph. Consequently, the attention matrix more accurately reflects important node relationships from the original graph and facilitates effective message passing between distant nodes. This configuration achieves the highest accuracy score on the FlowGraph6 dataset.
Table further indicates that the optimal number of hops varies with different datasets. For the Malnet-sub dataset, the highest accuracy is achieved at k 12, with significant drop when there are hop limitations. This can be attributed to the large size of Malnet-sub graphs, which can have up to 2000 nodes, and their edges are sparse. As result, a model requires a larger k compared to smaller datascts. In contrast, we choose h: = 3 for other datasets since they only contain approximately 200 nodes per graph. For datasets like FlowGraph2 and Twitter3, & = seems more effective, though these results still fall within one standard deviation compared to 3. In our experiments, we choose for the Malnet-sur dataset and k 3 for other datasets, as the default value.
4.3.3 Hard vs. Soft Thresholding for (A)
Our k-hop virtual filter matrix D (k) has been defined as D {1 6f k.O iff 6i k} where 6g denotes the shortest path distance from node i to node j. In this case, 0 means there are no existing paths among two nodes. In this ablation study, we turn our focus to variant definition, where D(6 {1 iff 8ij k, iff 6,z > }} to examine how the performance is affected when we set an extreme value for those node pairs with existing paths.
Table shows the results for DiGT and its variant, DiGT--inf. We see that on dense graphs like Twitter, the accuracy difference bet these two met is small (e-g., al most 1.57% on the Twitter5). In contrast, on sparse graphs such as FlowGraph and Malnet-sub, the DiGT-inf variant results a significant decline in performance (c.g., a 5.69% drop on Malnet-sub).
11

---

Published in Transactions on Machine Learning Research (07 (024))
(a) Adjacency Matrix
(b) DIGT Attention
(c) DIGT -inf Attention
Adj Matrix
Source to Target
Target Source
Source to Target
Target to Source
20
20
Columins
40
Coturens
40
Calunins
40
Columee
40
Colunns
40
60
60
60
40
20
40
60
80
20
80
20
40
Rows
Rows
Rows
0.0
0.2
0.4
0.6
0.8
1.0
Attention Value
Figure 5: DiGT and DiGT-inf attention matrices for a selected FlowGraph6 graph.
Table 6: Ablation: D (k)
Mudel
FlovGraph2
Flow@raph3
PlouGraphé
Tritter3
TwitterS
CIFAR10
DIGT
98.00 +/- 0.54
74.61 +/- 1.95
46.03 +/- 0.41
93.33 +/- 0.64
86,07 +/- 0.52
80.78 +/- 1.76 08.02 +/- 0.10
67.05 +/- 0.20
DIGT-iaf
+/-
09.22 +/- 0.91
+/-
91.17
+/- 75.09 +/- 93.52 +/- 0.95
00.31+-0077
To better understand the results, Table r presents an example of attention values, for a pair of nodes, before and after applying the softmax along the stack dimension our directional attention ap- proach. For an arbitrary node pair, there are three possible relationships: unconnected, bidirectional, unidirectional. Both models exhibit identical re- sults for pairs that are either unconnected or bi-directional. The divergence occurs with uni-directional connection: DiGT assigns an extreme value of -00, whereas DiGT uses 0. Consequently, DiGT--n yields a pair (1.0, 0.0) making the attention values solely dependent on one direction (in this case, from source to target). Figure illustrates this effect. In other words, for unidirectional node pairs, a hard thresholding using- -o blocks information flow completely in one direction (with the non-existent edge), whereas using soft thresholding of 0 still favors the direction that exists, but also allows flow in the opposite direction, which leads to SOTA performance of DiGT.
Table Attention Values Applying softmar
Relationship
Before softmax
After softmax
DIGT
DiGT-inf
DIGT
DiGT-inf
Unconnected
0,
-00, -00
0.5.0.5
0.5.0.5
Bi-directional
0.7,0.4
0.7,0.4
0.57, U.43
0.57, 0.43
Uni-directional
0.7,0
0.7,-
0.67, 0.33
1.0,
5 Conclusions and Future Work
In this paper, we present DIGT, novel architecture for capturing graph directionality using transformers. We empirically evaluate its classification accuracy on real and synthetic graph datasets and demonstrate its performance gains against state-of-the-art GTs and GNNs. We conduct several ablation studies to reveal the nced for a balanced treatment between local and global attention in node and edge encoding channels. Our experiments promote the view that GNNs and GTss could be complementary with the shortcomings of the former (over-smoothing, over-squashing, and limited expressiveness) mitigated by the strengths of the latter and vice versa (with scalability limitations, non-standard graph encodings for attention bias, as potential pitfalls in GTs).
In the future, to overcome the limitations of moderate-sized graph data that are imposed by the quadratic attention complexity, i.c., to scale up the attention mechanism, we plan to explore recently proposed ap- proaches expand the context (Bertsch et al. 2023 Tay al.) 2022), and study their effectiveness for directed graph datasets.
12

---

Published in Transactions on Machine Learning Research (07 (224))
References
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared to state-of-the-art superpixel methods. IEEE transactions poltern analysis and machine intelligence, 34(11):2274-233) 2282, 2012.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liö. Di- rectional graph networks. In International Conference on Machine Learning, pp. 748-754 PMLR, 2021.
Amanda Bertsch, Uri Alon, Graham Neubig, and Matthew R Gormley. Unlimiformer: Long-range trans- formers with unlimited length input. arviv preprint arXiv:2305. 01625, 2023.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint orXiv:1111.07558, 2017.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Struclure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 3469 3489. PMLR, 2022.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33: 33:13260-13271, 2020.
Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. Hermitian matrices for clustoring directed graphs: insights and applications. In International Conference Artificial Intelligence and Statistics, pp. 983 992. PMLR, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavior Bresson. Bench- marking graph neural networks. Xve preprinl orXi::2003.00983 2020.
Scolt Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph represen- tation learning. arXív preprint arXiv:2011.07682 2020.
Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama, Kunio Hato, and Masaki Aida. Graph signal processing for directed graphs based on the hermitian laplacian. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzzurg, Germany, September 16- 20, 2019, Proceedings, Part I, pp- 447-463. Springer, 2020.
Simon Geisler, Yujia Li, Daniel J Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Padu- raru. Transformers meet directed graphs. In International Conference on Machine Learning, pp. 11144 11172. PMLR, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Yixuan He, Gesine Reinert, and Mihai Cucuringu. Digrac: Digraph clustering based on flow imbalance.
arXiv preprint arXi::2106.0055 05.9944, 2021.
Weihua Hu, Matthias Fcy, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 1821223,, 2020.
Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self-attention a replacement for graph convolution. In 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
John Irwin and Brian K Shoichet. Zine free database of commercially available compounss for virtual screening. Journal of chemical information and modeling, 45(1):177-188) 2005.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint XrXio:1609 02907, 2016.
Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5): 604 112, 1999.
Georgios Kollias, Vasileios Kalantzis, Tsuyoshi Idé, Aurélic Lozano, and Naoki Abe. Directed graph auto- encoders. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), February 2022.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun and Corinna Cortes. The mnist database of handwritten digits. 2005. URL https://api. semanticscholar Oxgg/CorpuIDD:o 602882629
Jure Leskovee and Julian Mcauley. Learning to discover social circles in ego networks Advances in neural information processing systems, 25, 2012.
Yuankai Luo. Dagformer: Directed acyclic graph transformer. orXiv preprint arXiv:2210.13145 2022.
Fragkiskos Malliaros and Michalis Vazirgiannis. Clustering and community detection in directed networks: A survey. Physics reports, 533(4) (4):95 142, 2013.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105 1114, 2016.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Than Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, 35:14501 14515, 2022.
Guillaume Salha, Stratis Limnios, Romain Hennequin, Viet-Anh Tran, and Michalis Vazirgiannis. Gravity- inspired graph autoencoders for directed link prediction. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 589 1899558,,7 2019.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Ex- phormer: Sparse transformers for graphs. In International Conference on Machine Learning, 2023.
Jiankai Sun, Bortik Bandyopadhyay, Armin Bashizade, Jionggian Liang, P Sadayappan, and Srinivasan Parthasarathy. Atp: Directed graph embedding with asymmetric transitivity preservation. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 265 202,272,44 2019.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. ACM Compating Surveys, 55 (-): 2022.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. Advances in Neural Information Processing Systems, 33, 2020a.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David S Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXic:2004,139 13970, 2020b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. aixio preprint arXiv: 11900 2017.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tic- Yan Liu. Do transformers really perform badly for graph representation? Aduances in Newral Information Processing Systems, 34:28877 28888, 2021.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention needed for learning graph representations. arXiv preprint arXiv:2001.05140 2020.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. Magnet: A neural network for directed graphs. Advances in Neural Information Processing Systems, 1-27003-270114 2021.
Chang Zhou, Yugiong Liu, Xiaofei Liu, Zhongyi Liu, and Jun Gao. Scalable graph embedding for asymmetric proximity. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
15

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Appendix
A Experiment details
We test our code on node with NVIDIA V100 GPUs (32GB RAM), 20-core 2.5Ghz Intel Xeon CPU (768GB RAM), running Limux. We use Python and specifically the PyTTrrh library for implementation. Our code is available via Github:
Caanoogg-Wan/DDieeeeeCCCCCCCee Crrap Trapph-rraaTtaateeeerr
For a fair comparison, we run all models with the number of learnable parameters, around 100K with 4 layers for the graph classification tasks. We fix the batch size to 32, the number of maximum epochs to 200, and we employ grid search for tuning the learning rate E {2 x u = 0, 1, 2, 4] with u u= 10- choosing 1 = 10-4 (or = 1) for EGT and DiGT models on MNIST and CIFAR10 datasets, and f = x 10-3 (or 4) for all other datasets. We employ grid search for tuning the number of hops {1,3, 5, 10, 25); also employ grid search for normalization [no normalization, batch normalization, layer normalization) We apply similar process for other models. Table contains parameters used for DiGT.
We compare DIGT with GCN (Kipf & Welling 2016), GAT VVeicković et al. 2017 and PNA (Corso et al. 2020 as the represental Lvee of GNNs, and with GT @wiveedi & Bresson 2021] 1, SAN (Krezzr el al. 2021
EGT Hussaai et al., 2022), Exphormer (Shirzad et al. 2023). and Digraph- Transformer (Geisler et al, 2023 as the representatives of GTs. We reimplemented Digraph Transformer (Digraph-T) since we were not able to directly run their github code, despite lot of elfort debug and fix the problems encountered. We followed the same approach done in (Geisler et al.. 2023 for Digraph-T. That is, modified the SAT implementation (Chen et al,, 2022) (in Pytorch) and added the Magnetic Laplacian position encodings. Furthermore, as suggested, we also modified the SAT framework by replacing the GCN layer with three bidirectional GNN layers, using GELU instead of ReLU for the activation function, and adding dropout on the node features. We did not modify the softmax function since our datasets do not suffer from the problem of class imbalance of the special tokens.
We train all methods FlowGraph, Twitter, Malnet-sub, and MNIST/CIFARIO respectively. To conduct fair comparison, if the models provide parameter setting for similar dataset (e.g., Exphormer has a parameter setting for Malnet-tiny),
will keep the same settings and shrink the dimension of hidden layers. If the models do not provide parameter setting for a dataset, we follow the settings of DiGT, and adjust the hidden dimension. For PNA, we tried grid search over (identity, amplification, attemaation) for the scalers and {mean, max, std, var, sum} for the aggregators.
Table 8: Training Settings (default values).
FlowGraph Twitter
MNIST CIFAR
MALNETsub
Hyperparameters
Batch Size
32
32
16
Number of Epochs
200
200
200
Early Stops
10
Max Learning Rate (n)
0.008
0.0005
0.008
Number of Virtual Nodes (g)
0
0
0
Number of Layers
4
4
3
Number of Heads (h- (h=00 d/dp)
8
8
4
Node dimensionality (d)
32
32
44
Edge dimensionality (de)
32
32
32
PE dimension (r)
25
8
25
Batch normalization
True
False
True
Layer normalization
False
True
False
Number of Parameters
93,450
91,538
102,403
for FlowGraph2
for MNIST
16

---

Published in Transactions on Machine Learning Research (07 (2742)24)
B
Dataset details
Table 9 shows the datasct statistics for cach of the datascts used in our experiments.
Table 9: Datasets details: Number of graph instances G in the dataset, average number of nodes |N], average number of directed edges E and the number of graph classes ne are tabulated.
Dataset
G
Avg. |N]
Avg.
[
T
FlowGraph2
2000
114.46
150.30
2
FlowGraph3
3000
111.66
150.70
3
FlowGraph6
6000
111.40
149.93
6
Twitter3
2919
131.76
2237.55
3
Twitter5
4865
131.76
2208.79
5
MNIST
70000
70.57
564.53
10
CIFAR10
60000
117.63
941.07
10
Malnet-sub: Train
1434
84.85
126.14
5
Malnet-sub: Val/Test
1010
466.72
938.69
5
B.1 Twitter Datasets
We use 973 directed ego-networks from Twitter each corresponding to some user u (ego): the ego-nelwork is between u's friends also referred to as alters (Leskovec & Mcauley] 2012). If nodes v/. 8y are in u's ego-network then u follows them and v follows oy then there a directed edge 0; + 1y the ego- network. We introduce perturbations to each of these real ngo-networks where a perturbation can be either (i) rewiring of an existing edge (an (a,b) E F((eg(u)), where is deleted and replaced by edge (c, d) where nodes c, d are randomly selected from V (ego(u))) or (ii) reversing of the direction of an existing edge (a, b) E E(ego(u)), where it is replaced by (b, The percentage of the perturbed edges in an ego- network can be [0, 25, 50, 75, 100]%. Rewiring and reversing the direction of edges takes place with equal probabilities. So, for each of the percentages, 973 new perturbed ego-networks are generated, each labeled with the corresponding perturbation percentage. We refer to the collection of the x 973 perturbed Twitter datasets as Twitter5 labels/ / classes). Similarly, if we get 973 of them corresponding to perturbation percentages [0%, 50%, 100%), then we have the Twitter3 dataset (3 labels/classee
B.2 FlowGraph Datasets
Given the limitations of existing benchmarks, we introduce a family of directed graph datasets that explicitly relate the edge direction pattern in graphs to their classification labels. In particular, we generate graphs with their nodes organized in successive layers and then we leverage the notion of flow between the layers through directed edges: for predefined subset of layers, graphs with different aggregate flow between successive layers in the subset are assigned different labels. Our FlowGraph generator is modeled after the Directed Stochastic Block Model (DSBM) (Malliaros & Vazirgiannis 2013). Following the notation in (He et al. 2021 we organize N graph nodes into clusters and define cluster adjacencies a meta-graph adjacency matrix F, with its entries Fu marking the allowance of dirccted odges from nodes cluster k to those of cluster l. More specifically, we assume that the node clusters are arranged sequentially, 1 = 0, 1..... K (say from left. to right) and subset of its first Is K consecutive clusters define subgraph S. Tn FlowGraph we allow directed edges between nodes belonging to all clusters with the probability being small noise parameter (typically 7 0.01). Then for directed edges between nodes in successive clusters, with the source node being in a cluster in subgraph S, we set Fl,411 to a percentage 1%. These percentages are different. for different classes and depend on the number of classes ne- In our experiments, for all generated graphs we set 150, K = 10, Is = We generate graph datasets: one dataset for each of the nt, = 2, 3, 6-class cases.
htttp://snap.stanttee stanford. edw/dataaego---aeeeaaee www.oggooottttt...
17

---

Published in Transactions on Machine Learning Research (07 (07/2024)
FlowGraph3 Label 0
FlowGraph3 Label 1
FlowGraph3 Label
Figure 6: The visualization of three categories of graphs in FlowGraph3 dataset.
Figure visualizes FlowGraph3. The yellow edges are the flows from left to right, the red edges are the flows from right to left, and the green edges are noises. In all three samples, half of the edges are noise, shown with green edges. In the leftmost sample, besides the noise edges, almost all the edges have the flow from left to right; in the middle sample, 75% of the edges have the flow from left to right; whereas in the right sample, 50% of the edges have the flow from left right.
C Flipping Edge Directions
We reverse the direction of 25% and 50% of graph edges, randomly selected, and empirically evaluate the importance of directionality in all the datasets. Table 10 lists our findings. We use GAT (Veičkovoooi et al. 2017) and EGT (Hussain et al. 2022) as the representatives for graph neural networks and graph transformers. We confirm that the derived notion of edge direction in MNIST (Achanta et al. 2012) and CIFAR10 (Krizhevsky et al. 2009) is not significant: classification results from both EGT and GAT models are almost agnostic to edge direction flips in these datasets; the differences between the vanilla datasets and flipped datasets are at most 2.1%.
For the 0gbg-Code2 dataset (Hu et al. 2020), we select SAT (Chen et al. 2022) and DAGformer Luo 2022), the two top-performing models, as the baseline for testing random flips. We observe that DAGformer only exhibits a 1.2% decrease in performance when 50% of the edges in this dataset are randomly flipped. This suggests that directionality not a significant factor in this datasot.
We employ the current state-of-the-art model, Exphormer Shirzad al. 2023). examine the significance of direction in Kalnet-tiny dataset (Freitas et al. 2020). It is observed that there's 6.12% decrease in performance in the flip50 case. This gap refers to the importance of directionality in the Malnet-tiny dataset.
For FlowGraph and Twitter datasets, the labels are determined by the percentage of edge perturbations. Consequently, the directionality of these graphs plays critical role. In particular, DiGT accuracy con- sistently decreases across all FlowGraph and Twitter datasets under all edge reversal percentages. Tn increase the reversal percentage): with 25%
FlowGraph, accuracy drops sharper (and saturate of edges flipped accuracy decreases in the range of 46.25% to 28.94%: from 97.42% to 51.17% in FlowGraph2 and from 46.80% to 17.86% in FlowGraph6.
D Ablation: Positional Embeddings
We select techniques for the positional encodings: Singular Value Decomposition (SVD), and the Mag- netic Laplacian (Geisler et. al. 2023 Here the details for these two methods:
Singular Value Decomposition Given an adjacency matrix A we apply Singular Value Decomposition (SVD) to decompose it into A UEV* where U and V* orthogonal matrices and E, is diagonal matrix
18

---

Published in Transactions on Machine Learning Research (07/2024)
Table 10: Random Flips of MNIST, CIFARIO, Ogbg-Code2, Malnet-timg datasets.
Model
MIIST
CIFARIO
Model
Ogbg-Code2
Model
Malnet-tiny
Malnet-sub
GAT
95.54 +/- 0.21
64.22 +/- 0.46
SAT
19.37 +/- 0.03
Exphormer
94.02 +/- 0.21
79.71 +/- 0.37
GAT-Plb225
93.92 +/- 0.22
62.86 1/- 0.18
SAT-Flip25
18.72 +/- 0.08
Exphormer- Plip2
88.77 +/- 0.41
70.93 1/- 0.73
GAT-Plli50
93.43 +/- 0.23
62.11 +/- 0.78
SAT-Flip50
18.70 +/- 0.03
Exphormer-Plipe
87.90 +/- 1.65
71.51 0.45
EGT
98.17 +/- 0.09
68.70 +/- 0.41
DAG
20.2 +/- 0.2
EGT FCPT2
97.90 +/- 0.11
67.27
+/- 0.56
DAG- DAG-Flip25
18.9 +/- 0.2
EGT-Plip50
97.99 +/- 0.09
67.28 +/- 0.38
DAG-Flip50
19.0 +/-
Table 11: Random Flips of FlowGraph and Twitter datasets.
Model
FlowGraph2
FlowGraph3
FlowGraph6
Twitter3
Twitter5
GAT
84.92 +/- 1.90
58.83 +/- 1.47
30.31 +/- 0.28
74.59 +/- 1.59
56.79 +/- 0.05
GAT-Flip225
73.67 +/- 0.72
44.16 +/- 1.70
48.62 +/- 0.80
67.69 +/- 1.06
48.62 +/- 0.80
GAT-Flip50
51.00 +/- 3.89
33.00 +/- 2.38
17.31 +/- 0.66
65.64 +/- 1.71
44.34 +/- 2.05
DIGT
98.00 +/- 0.54
74.61 +/- 1.95
46.03 +/- 0.41
93.33 0.60.64
86.67 +/-0.52
DiGT-Flli255
$1.17+/- 1.25
33.50 +/- 0.36
17.86 +/- 0.92
89.29 +/- 0,90
77.47 +/-
DiGT-Flip50
49.67 +/-
32.33 +/- 1.66
16.78 +/- 0.04
82.96 +/- 1.13
65.44 0/3
containing singular values. After sorting the singular values in Σ, we select the top p columns (rows) from both U and V where p represents the dimensionality of our positional encodings. We utilize them as the dual positional encodings in our model for our input layer as follows where N, is input node features:
= L.
T T= L(V(VV++
(11)
Magnetic Laplacian We first compute symmetric adjacency matrix As given a directed adjacency matrix A as As = A v AT, where V denotes the 'or' operation. Then, we compute the symmetric diagonal degree matrix Dg from As. According to (Geisler et al. 2023 and (Furutani et al. 2020), we compute the magnetic Laplacian as
L= Ds As à exp(i09)
(12)
where C Hadamard product, exp is element-wise exponential, = V- θ 2 A and q 0. L is Hermitian matrix, and we can gel complex eigenvector with real and imaginary R and M components. Then, select p columns from R and M. Since we have two pairs of eigenvectors for one node, we change our input layer as the following formula:
S L. (R) + (M) ())
T= La + (12 (N)
(13)
Table 12: Ablation: Positional Embeddings.
Model
Floudrapa2
FlouGraph3
FLoutraphe
Twitter3
Twitcers
Mainat-sub
MMTeT
CIFARLO
DeGT-Muuzei
98.00
0.54
74.61 +/- 1.95
46.03 +/- 0.41
85.33 +/- 0.64
86.67 +/- 0.52
60.78 +/- 1.78
97 25
-/-
63.10 +/- 0.91
DIGT-SVD
+/-
74.55
+/- 0.69
+/- 0.55
+/- 0.79
85.94
+/- 0.25
77.12
+/-
+/- 0.10
67.05 +- 0.20
No PE
06.83 +/- 0:47
7483 +/ 1.88
16.11 +/- 0.75
91.28 +/- 0.98
65.85 +/- 0.84
80.03 +/- 3.97
97.63 0.10
65.55 +/ 1.35
Table 12 presents the comparative results of these strategies, compared with having no positional encodings. We see that Magnetic Laplacian encodings exhibit superior performance in datascts where directionality is critical factor, such as FlowGraph, Twitter, and Malnet-sub. Conversely, SVD is more effective in scenarios where directionality is less relevant, such as MNIST and CIFAR10 datasets. Consequently, DiGT follows the same stratogy to select the most suitable positional encoding method. Furthermore, the table suggests that incorporating positional encodings generally enhances learning performance, with the exception of applying SVD to the Malnet-sul dataset.
19

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
E
Ablation: Virtual Nodes
We investigate the virtual node method from (uussain et al. 2022 : adding virtnal nodes and establishing bidirectional edges between each node from the original graph and each virtual node. the output layer, aggregales the output embedding by averaging the node embeddings exclusively from the virtual nodes instead of from all nodes. However, we find that for directed graphs, is more effective to add edges from the graph to the virtual nodes only, rather than introducing bidirectional connections. Table [3 summarizes our findings for different number of virtual nodes, q e (1, 5), denoted as DiGT-VNg. Note that DiGT by default does not use virtual nodes (q 0). We observe that for FlowGraph3 dataset, DiGT-VN3 outperforms DiGT by 1.32%. For FlowGraph6 dataset, DiGT-VNI shows 0.72% improvement over DIGT. However, these differences are slight. Additionally, in other datasets, the introduction virtual nodes tends to decrease performance. Consequently, we decide not to incorporate virtual nodes in our default model due to limited benefits and potential drawbacks.
Table 13: Ablation: Virtual Nodes.
Model
PlowGraph2
FloxGraph3
FlowGraphó
TwitterS
TeitterS
Halnet-eub
MKIST
CIFAR10
DITT
96.00 +/- 0.54
74.61 +/- 1,85
46.03 +/- U.41
93.33 +/- 0.64
80.67 +/- 0.52
80.78 +/- 1.76
98.02 +/- 0.10
67.05 +/- 0.20
D:CT-VNI
97.25 -- 0.41
15.28 +/- 0.44
46,75 +/- 1.76
92.02 +/- 0.29
96.63 +/- 0.64
75.93 +/- 0.59
97.24 +/- 0.12
64.15 /- 0.46
-/
+/-
+/-
+/ 0.14
+/-
+/-
+/-
-/-
DIGT-VX
98.00 +/- 0.35
76.89
+/-
46.14 +/- 1.30
91.06 +/- 0.32
86.63 +/- 0.48
76.75 +/- 0.52
96.96 +/- 0.18
64.63 -/- 0.69
F
Ablation: Undirected Graph Datasets
Table 14: Ablation: Undirected Graph Datasets.
Model
Zinc 100K
Zinc 500K
GCN
Kipf & Welling
2016
0.459 +/- 0.006
0.367 +/- 0.011
GAT
Veličković et al. 2017
0.475 +/- 0.007
0.384 +/- 0.007
GatedGCN (Bresson & Laurent, 2017
0.375 +/- 0.003
0.282 +/- 0.015
GraphSage (Hmmilon
2017
0.468 +/- 0.003
0.398 +/- 0.002
PNA (Corso et al. 2020
0.188 +/- 0.004
0.142 +/- 0.010
EGT
Hussain et al. 2022
0.277 +/- 0.019
0.228 +/- 0.020
EGT+DO (Hussain et al.
2022
0.143 +/- 0.011
0.108 +/- 0.009
DIGT
0.213 +/- 0.031
0.134 +/- 0.039
While undirected graphs are not our primary focus, aim to demonstrate that DiGT remains highly effective such datasets. We choose to further evaluate DiGT on the Zine (Trwin & Shoichet 2005 dataset, which contains 12K undirected graphs, for the graph regression task. Table 14 reports the mean absolute error (MAE; lower better) for the Zinc dataset under two diffcrent training settings: approximately 100K parameters and 500K parameters. Notably, DiGT exhibits superior performance over GCN, GAT, GatedGCN, GraphSage, and EGT. PNA leverages multiple aggregators with degree-scalers to aggregate the neighbors' features and captures the graph structure to attain better performance, and EGT-DO integrates both EGT with secondary task of distance prediction. Nevertheless, the results indicate that DiGT is competitive for tasks based on undirected graph datasets.
G Complexity and Limitations
We designed our experiments so that we allocate the same hardware resources (GPU/CPU, amount of mem- ory) for all experiments. We also limit the number of learned weight parameters to be the same for all models, as shown in Table 15 (for Malnet-sub). The recorded training timings show that our method is very compet- itive with graph transformers: Training time for DiGT is 42s/epoch (for FlosGraph6 dataset.) and 57s /7s/epoch
20

---

Published in Transactions on Machine Learning Research (07/2024)
Table 15: Training Settings (for Malnet-sub).
DiGT
EGT
GCN
Exphormer
Number of Layers
4
4
5
Number of Heads (h = d/dp)
8
8
Node dimensionality (d)
60
72
48
Edge dimensionality (de)
48
48
Number of Parameters
102,403
107,489
105,845
113,645
(for Twitter3 dataset). In comparison: for EGT (uussan et al., 2022 (also a transformer- based architec- ture), the training time is 30</epoch (for Flo=Graph6 dataset) and 50s/epoch (for Twitter3 dataset). Train- ing time for GNNs differs significantly based their architectures. Vanilla GCN is fast, the training time is 2s/epoch (for FlowGraph6 dataset) and 3s/epoch (for Twitter3 dataset).. In contrast, for PNA (Corso al,, 2020), GCN-based architecture, the training time is 62s/epoch (Tor FlowGraph6 dataset) and 297s/epoch (for Twitter3 dataset). In general, for N nodes and d-dimensional vectors for node representations at each layer, graph transformers learn weight matrices (space complexity) with O(N²) parameters each, and graph neural networks learn weight matrices with ((d') parameters each (with both (graph) transformers and GCN producing N, d-dimensional representations for the nodes), conducting matrix-matrix multiplications respectively of (time) complexities O and O). Given that for the graph-level tasks we conduct, the graphs are relatively small (small N, comparable smaller to d), this explains the generally lavorable performance of our approach. On top of this, transformer architectures like ours, perform multiplications by splitting matrix dimension into multiple heads and conducting resulting multiplications in parallel (on GPUs).
21


Reviews:
[{"review_id": "M02LcXWUaT", "reviewer": "Reviewer_5DUg", "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 addresses an important problem of explicitly accounting for edge directionality in Transformers, which is a challenging and practical task in graph representation learning.\n* The use of dual encodings for nodes to represent their roles as sources or targets provides a more accurate and flexible representation of directed edges.\n* Empirical evaluations show that DiGT outperforms many existing graph transformer and graph neural network approaches in terms of classification accuracy on both synthetic and real graph datasets.\n\nWeaknesses:\n* The proposed method makes a very incremental improvement over [1] (considering the positional encoding of DiGT is borrowed from [1]), which indicates that DiGT is not the first GT architecture that explicitly takes into account graph directionality, and therefore hinders the novelty of this work. The authors are encouraged to include detailed analysis and comparison with [1] to support the significance of DiGT. From my perspective, without a detailed discussion of how DiGT contributes over [1] as well as thorough empirical comparisons with [1], the current claims regarding the contributions could not make sense. \n\n* The need for a balanced treatment between local and global attention in node and edge encoding channels is a kind of well-explored observations for GTs on undirected graphs [2]. Therefore, this observed pattern made by the authors is not new. Could the authors elaborate more on how this need is unique for GT towards directed graphs?\n\n* The design of each component in DiGT seems to be rather intuitive without strong motivations. It would be better for the authors to provide more detailed explanations of the effectiveness of each component design with possible theoretical groundings.\n\n\n\n[1] Transformers Meet Directed Graphs, ICML 2023 \n\n[2] Recipe for a general, powerful, scalable graph transformer, NeurIPS 2022", "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": "The paper introduces Directed Graph Transformer (DiGT), a novel transformer architecture designed to capture the directionality in graph data, which is a critical aspect often overlooked by existing graph transformers and graph neural networks. DiGT utilizes dual encodings for each node to represent its potential role as either a source or target within directed edges. This approach leverages a multi-head directional attention module that considers edge channels as bias, allowing for the dynamic representation of directed graphs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please kindly refer to the Strengths And Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eBwGcdSV5b", "reviewer": "Reviewer_NBzC", "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": "Strength:\n- an interesting idea on an important topic\n- new (synthetic or partially synthetic) datasets\n- experiments are well-designed\n\nWeaknesses/questions:\n- the presentation of the architecture is sometimes pretty confusing, especially for the GNN community (where we tend to look for \"message-passing\" equations and such. I'm guessing this is eq (8)).\n- some notations tend to be repeated for different objects, eg S and T appear everywhere\n- I don't know the role of the unnumbered equation at the bottom of page 4. Is it used somewhere in the architecture? Is such a relationship verified between S and T at some point?\n- unless I am missing something, eq (5) does not force the adjacency matrices to have nonnegative weights, wouldn't it be more intuitive? (eg using exponentials as in the original attention/GAT)\n- the efficiency of the architecture would be more discussed. Complete graphs are sometimes unreachable. The authors mention limiting to k-hops, but still manipulate complete graphs in the equation, can the overall complexity of the architecture be limited to k-hop adjacency matrices if desired? Moreover, the authors propose to learn a new adjacency matrix at each layer, in graph learning it is more usual to learn one matrix for the whole architecture, would such weight tying degrade \n- The original graph only intervenes in the input S_r and T_r? (and through eventual k-hop filtering) How are they computed? What makes them particularly \"source\" or \"target\"? If the original graph is symmetric, is the whole architecture producing symmetric adjacency matrices?\n- is the whole architecture permutation-invariant/equivariant, as this is required of all GNNs? (I think so, but might worth a check)\n- just to verify, in the experiments, the architectures you are comparing against are indeed using the oriented graph in the message passing? (such that they would be able to exploit the directionality but are not powerful enough to do so compared to yours)", "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": "In this paper, the authors propose a graph transformer architecture called DiGT, as well as synthetic datasets of graph for whom direction of edges is crucial in labelling the nodes. Based on a dual encoding mechanism, DiGT recomputes a latent directed adjacency matrix (in fact, two) between each nodes (or limited to k-hops of the original graph) at each layer.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Mostly some questions/precision, see above", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aIm45PONc7", "reviewer": "Reviewer_rHPc", "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$\\textbullet $ The topic under consideration appears to be an interesting research direction, which gains attention recently.\n\n$\\textbullet$ The rationale behind each architectural choice is well-explained. \n\n$\\textbullet$ The synthetic datasets proposed are intriguing and serve to illustrate the impact of directionality effectively. \n\nWeaknesses:\n\n$\\textbullet$ The fact that real-world datasets are not sensitive to edges flips raises concerns about the cases where directionality is mandatory to solve the underlying task.\n\n$\\textbullet$ The impact of different positional encodings (PEs) appears to be minimal and may introduce computational overhead.\n\n$\\textbullet$ Since there exist GNN models which perform, in general, better than GCN and GAT, comparing DiGT against other state-of-the-art GNN models could provide valuable insights into its performance.\n\n$\\textbullet$ Evaluating DiGT's performance on undirectional datasets and comparing its embeddings' consistency with other architectures could enhance understanding.\n\n$\\textbullet$ There exist some typos and confusing notation, X is used for input features and for the output of the model after concatenation. Moreover, some tables are too small and make it difficult to be read, e.g. Table 2.", "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 presents a graph transformer architecture that takes into account the direction of the edges between graph nodes. The proposed architecture utilizes dual encoding, positional encodings that respect the edge directionality, and k-hop filtered attention.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Compare against more powerful GNN models. \n2. Include the performance of DiGT in undirectional datasets. \n3. Fix typos and notation in order to improve clarity.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three reviewers. The overall recommendations from the reviewers were mixed, with two reviewers advocating for weak acceptance and another advocating for rejection. The reviewers raised concerns about the clarity of the presentation, e.g., the notation used in the paper is somewhat confusing. The reviewers also complained about the message passing baselines, mainly that the employed baselines are weak. In the response, the authors addressed most of the reviewers' concerns, but the manuscript has not been revised yet to account for all the reviewers' feedback. In my view, the most severe problem with this paper is that the proposed architecture is not empirically compared against [1]. It appears that the authors have made efforts to train the model proposed in [1], but they have not succeeded because of coding issues. Even though this comparison would strengthen the paper, I believe that it is not mandatory for acceptance. I am thus recommending accept with a minor revision, and I request that the final version of the manuscript carefully considers the reviewers' comments, mainly the items listed below:

- The claim that DiGT outperforms existing graph transformers by a large margin needs to either be verified by comparing against [1] or be sufficiently toned down.
- A comparison against stronger message passing models needs to be added to the manuscript.
- The presentation of the paper needs to be improved.
- A detailed discussion needs to be added in the manuscript on how DiGT differs from the method proposed in [1].
Decision: Accept (poster)