Transformers over Directed Acyclic Graphs
Authors: Yuankai Luo
Veronika Thost
Lei Shi
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Transformers
Graph Classification
Node Classification
Scalability
TL;DR: We propose a simple and intuitive framework that adapts (graph) transformers to directed acyclic graphs and show that it is effective across a variety of tasks in terms of both quality and efficiency.

Abstract: Transformer models have recently gained popularity in graph representation learning as they have the potential to learn complex relationships beyond the ones captured by regular graph neural networks.
The main research question is how to inject the structural bias of graphs into the transformer architecture,
and several proposals have been made for undirected molecular graphs and, recently, also for larger network graphs.
In this paper, we study transformers over directed acyclic graphs (DAGs) and propose architecture adaptations tailored to DAGs: 
(1) An attention mechanism that is considerably more efficient than the regular quadratic complexity of transformers and at the same time faithfully captures the DAG structure, and (2) a positional encoding of the DAG's partial order, complementing the former.
We rigorously evaluate our approach over various types of tasks, ranging from classifying source code graphs to nodes in citation networks, and show that it is effective in two important aspects: in making graph transformers generally outperform graph neural networks tailored to DAGs and in improving SOTA graph transformer performance in terms of both quality and efficiency.

Transformers over Directed Acyclic Graphs
Yuankai Luo Beihang University Luoykebuaa edu.cn
Veronika Thost
Lei Shi* Beihang University
MIT-IBM Watson AT Lab, IBM Research veronika aeronika.thostee 1.m. com
leishi Leishi@buaa edu. cn
Abstract
Transformer models have recently gained popularity in graph representation learn- ing as they have the potential to learn complex relationships beyond the ones captured by regular graph neural networks. The main research question is how to inject the structural bias of graphs into the transformer architecture, and several proposals have been made for undirected molecular graphs and, recently, also for larger network graphs. In this paper, we study transformers over directed acyclic graphs (DAGs) and propose architecture adaptations tailored to DAGs: (1) An attention mechanism that is considerably more efficient than the regular quadratic complexity of transformers and at the same time faithfully captures the DAG struc- ture, and (2) positional encoding of the DAG's partial order, complementing the former. We rigorously evaluate our approach over various types of tasks, ranging from classifying source code graphs to nodes in citation networks, and show that it is effective in two important aspects: in making graph transformers generally outperform graph neural networks tailored to DAGS and in improving SOTA graph transformer performance in terms of both quality and efficiency.
Introduction
Graph-structured data is ubiquitous in various disciplines Gilmer et al. 2017 Zitik al. 2018
Goohalll et al., 2020 and hence graph representation learning has the potential to provide huge impact. There are various types of graph neural networks (GNNs), the majority of which is based on so-called message- message-passing scheme where node representations are computed iteratively by aggregating the embeddings neighbor nodes [Gimerr al.) (017). Yet, this mechanism in its basic form has limited expressivity [Xu et al.) 2018 and research is focusing extensions.
Transformer models have recently gained popularity in graph learning as they have the potential to learn complex relationships beyond the ones captured by regular GNNs, in a different way [Dwivedi and Bresson 2020 Kreuzer al. 2021]. Technically, they can be considered as graph neural networks operating on fully-connected computational graphs, decoupled from the input graphs. The main research question in this context is how inject the structural bias of the given input graphs (i.e., which nodes are actually connected) into the transformer architecture by adapting their attention and positional encoding appropriately. Several promising proposals have been made encode undirected molecular graphs (Ying et al. 2021 Ross et al. [022]] and recent works take into account the scalability challenge [Dwivedi et al.
2022 also over larger network graphs [Rampášek et
2022 Chen et al. 2022b].
"Corresonniig author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Xx
MatMul
SoftMax
X10
X1
Scale
MatMul
24
X1c
Inear
Linear
Linear
X1x
calcufate
To calculate alleniion
Node Featura
Postional
Figure Overview of DAG attention. A mask matrix restricts the receptive field of the nade under consideration nodes are directly reachable the DAG. Our positional encoding (right), additionally captures its position as its depth in the DAG.
We focus on directed acyclic graphs (DAGs), which are of special interest across various domains; examples include parsing results of source code (Allamanis et al., 2018), logical formulas [Crouse et al. 2019]. and conversational emotion recognition [Shen et al. [021]] as well as probabilistic graphical models and neural architectures [Zhang et al., 2018 2019 Knyazev et al. [021]. In a DAG, the edges define partial order over the nodes. This partial order represents additional strong inductive bias, which offers itself to be integrated into the models.
In fact, various kinds of neural networks tailored to DAG structures have been proposed over the years; from early descriptions of recursive neural networks over DAGs (Sperduti and Starita 1997 Frasconi et al., 1998). which have pointed out a similarity to sequence learning. to more recent works, such as DAG-RNI GNN (Shuai al., 2016). DAG-LSTM [Crouse al. 2019]. D- D-V [Zhang et aall,2011 [019). and DAGNN (Thost and Chen 2021]. The latter models focus on encoding the entire DAG; in a nutshell, they compute embedding DAG nodes in an asynchronous way, given by the partial order, and thereafter aggregating the final node representations into one for the DAG. This procedure yields state-of-ther terms of quality, but its asynchronous nature leads to comparatively (to regular GNNs) very slow runtime performance. The more parallel computation of transformers would seem make them more suitable models and [Dong et al. 2022 have recently proposed one such model, PACE, which shows convincing performance terms of both quality and efficiency.
message-passing fashion by iterating over the
performance in
In this paper, we focus on transformers over DAGs more generally, motivated by the highly flexible, parallel, and expressive nature of their computation. In particular, their success in sequence learning opens up the question how they can be tailored to DAGs, which are essentially sequential graphs. Based on the above-mentioned insights in DAG learning, we propose straightforward and efficient DAG attention framework, which effectively biases any transformer towards DAGs.
As outlined in Figure I we (1) adapt the attention mechanism by restricting the receptive field of each node to its predecessor and successor nodes that faithfully captures the DAG structure in terms of its reachability relation and at the same time gets considerably more efficient than the regular quadratic complexity; and (2) employ the positional encoding in a complementary way, to further bias the computation towards the DAG topology, by explicitly encoding the node depth.
We show that the attention not restricted effectively, even it seems so technically. Moreover, we draw connection to the random walk theory.
We rigorously evaluate our proposal in ablation studies and show that successfully improves different kinds of baseline transformers, from vanilla transformers (Vaswani et al.) 2017] to state- of-the-art graph transformers [Wu al.) 2021 Chen et al. 2022a Rampášek et al.) 2022 Wu et al. 2022], ]. over various types of DAG data. Our experiments range from classifying source code graphs to nodes citation networks, and even go far beyond related works' problem scope.
Most importantly, our proposal is proven effective in two important aspects; in making graph

---

transformers generally outperform graph neural networks tailored to DAGs and in improving SOTA graph transformer perforrmn in terms of both quality and efficiency.
Finally, our DAG attention framework can be implemented in two possible and rather straightfor- ward ways, either on top of existing transformer models, or based on message-passinnn pasaing GNNs. Our implementation is available at https//ggghbbb.omm//lUgyyyDDDDDp
2 Background and Related Works
Directed Acyelic Graphs. We refer to a graph as tuple G = (V, X),, with node set V, edge set E - Vx x V, and node features X E Raxd with each row representing the feature vector of one node, with number of nodes n and feature dimension d, the features of node are denoted by T. E RR. directed acyclic graph (DAG) is a directed graph without directed cycles. For a DAG G, we can define a unique strong partial order & the node set V, such that, for all pairs of nodes u, & V if and only if there is a directed path from u. to v. We define the reachability relation & over a DAG based on that partial order. That is, u & if and only if is reachable from u; further, if u & v. then u is called a predecessor of v, and v is successor of u. All nodes without predecessors are source nodes, and all nodes without successors are sink nodes. We further define restricted form of reachability & with u S v if and only if there is directed path of length at most l from u to e. The depth of a node V is defined below. The depth of a DAG the maximum depth over its nodes.
V,
depth(v)= = -
-(1+ 1+
if v is source node otherwise
max depth(u) (U,))E
Message- Passing Graph Neural Networks. Most modern graph neural networks (GNNs) are or can be formulated in terms of the message-passing architecture, framework proposed in [Gilmer et al. 20017]. In that architecture, node representations are computed iteratively by aggregating the embeddings of their neighbor nodes (i.e., the messages), and a final graph representation can be obtained by aggregating the node embeddings. Yet, in its basic form, this mechanism has limited expressivity [Xu et al. 2018 and graph neural networks remain an active research area. Notable works we compare to include the graph convolutional network (GCN) (Kipf and Welling 2017].
a very early, basic architecture; the graph attention network (GAT) Veličković et al. 2018
aggregating the neighbor node embeddings using attention; the graph isomorphism network (GIN)
[Xu et al. 2018), which integrates extra MLP layers into message passing for increased expressivity; and the principal neighbourhood aggregation (PNA) model [Corso et al. 2020). , recent proposal focusing on adapting the aggregation mechanism to the node under consideration (e.g., scaling based on its degree). For broader overview of the field, we refer the reader to (Wu et al. 2020).
Transformers on Graphs. Transformer models [Vaswani et al. 2017 have gained popularity in graph learning they have the potential to learn complex relationships beyond the ones captured by regular GNNs and in a different way. The architecture is composed of two main parts: a self- attention module and feed- forward neural network, each followed by residual connection with a normalization layer. Formally, the matrices W E Raxxx, WK Rdddx and Wv [ddx to the corresponding representations for query (Q), key (K), and value (V), and is described as follows:
projects the input node features X using three
Q XWQ, K XWK, -=WV,
QK"
Attention (X) softmax
V.
(1)
vdx
Over graphs, we focus on computing node instead of token embeddings (recall Figure I). Technically, transformers can be considered as message-passing GNNs operating on fully-connected computational graphs, decoupled from the input graphs. The main research question in the context of graphs is how to inject the structural bias of the given input graphs by adapting their attention and by adding extensions to the original features, via so-called positional encodings (PEs). Graph Transformer [Dwivedi and Bresson| 2020) represents an early work using Laplacian eigenvectors as positional encodings, and various extensions and other models have been proposed since then [Min et al. 2022]. For instance, [Mialon et al. 202T] proposed a relative PE [Shaw et al., 2018] by means of kernels graphs to bias the self-attention calculation. Notably, GraphTrans [Wu al. 2021
3

---

was the first hybrid architecture, using stack of message- messagg-passing GNN layers before the regular transformer layers. Finally, [Chen et al. 2022a] have reformulated the self-attention mechanism as a kernel smoother as shown below and incorporated structure information into their structure-aware transformer (SAT) architecture by extracting a subgraph representation rooted each node before attention computation:
(Zv,
Attention (Zx)
Σ
EwEv Ki (Wu f (ou) V V,
(2)
NEV
with f(x) = Wvv, and non-symmetric exp. kernel k:
in vanilla transformer H (xx x') = exp ( (p(x)) Wo. pp (())))))))) (0()) = GNNG((2 in SAT
vdk
where (5.) is the dot product Rd and GNNG(x: is arbitrary GNN model. Most of the aforementioned works focus on the classification of smaller graphs, such as molecules; yet, recently, GraphGPS (Rampášek et al. 2022] is also considering larger graphs and the area is focusing on the development of scalable models; for instance, Nodeformer [Wu et al. [022] is designed to address the issue of scalability and expressivity node classification. Altogether, the transformer architecture
opens new and promising avenues for graph representation learning, beyond message-passing GNNs.
Neural Networks over DAGs. The additional strong inductive bias present in DAGs has motivated researchers to formulate special neural architectures tailored to this kind of graphs (Sperduti and
Starita
1997. Frascomi et al., 1998]. Various types of models have been proposed over the years in
many different application areas. There are works in the context of syntactic graphs, (Tai et al. [2055]
Shuai et al. 2016] logical formulas [Crouse al., [219], source code representations [[Allamanis]
ct al. 2018] and neural architectures (Zhang et al. 2018 2019 Knyazev et al. [021]. We particularly
compare the most recent proposals S-VAE and D-VAE [Zhang al. [019]] ; and to DAGNN from
(Thost and Chen 2021], who also showed that using attention for neighbor node aggregation is
beneficial in several DAG tasks.
While the models can be formulated in terms of the message- -aasgiin framework (Thost and Chen 2021]. their processing is special for GNNs: they compute graph embedding by iterating over the DAG nodes in an asynchronous way, given by the partial order, and starting from the source nodes (or the other way around, from the sink nodes). That is, the messages passed along the partial order of the DAG and, at any point during computation, capture the information of the subgraph consisting of all the predecessors of the node currently under consideration. Thereafter, final graph representations can be obtained by aggregating the embeddings of all sink nodes. In contrast to regular message-passing GNNs, these customized works for DAGs usually focus on encoding graphs (i.e., instead of nodes or edges, which are other common GNN targets) and pass messages over the entire graph, while regular GNNs consider fixed radius usually rather small around each node and essentially obtain a neighborhood embedding. Furthermore, the nature of the proposed architectures shows that recurrent techniques have proven especially useful, analogy to learning over sequences. In summary, these DAG models are elegant and effective, yielding state-of-the-an results, but their asynchronous nature leads to very slow and practically inhibitive performance compared to regular GNNs.
Transformers over DAGs. We are aware of only few proposals for transformers tailored to DAGs. HHang et al. 2022 developed a Directed Acyelic Transfomer in the context of machine translation order to simultaneously capture multiple translations within the decoded DAG, but the model's s encoder is a vanilla transformer. [Kotnis et al.] 202T] proposed BIQE, which leverages the depth of nodes in DAG paths as positional encodings, with a specific focus on answering complex queries in knowledge graphs. [Gagrani et al. 2022) proposed Topoformer, which is also an encoder-decoder model but has been developed for finding optimal topological orders in DAGs. Since the study entirely focuses on the latter goal (e.g., in terms of training objective and evaluation) it is very specific and different from our more general study. The DAG encoder itself is also rather different in that it uses a Laplacian PE, as it is used with regular graph transformers; and more complex attention mechanism, which does not only model the reachability but also several other relations over the graph. Closest to our method is PACE [Dong et al. 2022). which similarly focuses on modeling the sequential nature of DAGs inside a transformer model and independently of specific application in mind. However, (I) it applies a rather complex, node-specific positional encoding, whereas our PE only distinguishes

---

node depth; (2) the attention is based on the directed transitive closure, while we use reachability and show that this provides better quality; and (3) it's implemented using regular transformers, with runtime complexity (()V)sd). while we propose much more efficient and scalable implementation based on message passing. Altogether, our proposal simpler and considerably more efficient. In addition, we do not propose a single model but framework which can be flexibly applied top of existing graph transformers and thus complement any custom, graph-specific transformer and adapt it to DAGs.
3 Transformers for Directed Acyclic Graphs
Transformers have revolutionized deep learning, in particular sequence learning, and yield promising performance over graphs. Furthermore, we posit that their benefits actually match well the above- mentioned shortcomings of DAG neural networks. Therefore we developed a graph transformer framework tailored to DAGs. See Figure T for an overview.
3.1 Attention based on DAG Reachability
In contrast to regular graphs, the partial order in DAGs creates particular relations between connected nodes, in the sense that a given node's 's predecessors and successors are most likely more important to than other graph nodes. Note that this intuition is also captured in the processing DAG neural networks. Hence the reachability relation suggests itself to be exploited in our architecture. We apply restrict the receptive field of nodes during attention to their predecessors and successors in the graph. Vaaswani et al.) [017] already mentioned the possibility to use restricted attention in order to reduce complexity and, indeed, our proposal does not only yield an architecture which is biased towards the DAG structure, but additionally a considerably more efficient model.
While graphs to classify are usually of manageable size, graph learning in general may face much larger ones. For this reason, we formulate our model in more general way, based on bounded reachability relation, representing the receptive field of each node: (& {(u, v) E
{(V, u) E }. We adapt Equation (2) for our reachabilliy-bane attention (DAGRA):
AttentionDAG (Irv)
Σ WE (w)
(Ivy Tu) EweNa(o) K (Ie, Rwn) (IN), Vu
The number & represents a hyperparameter and can be chosen according the data. In our ablation study (see Section 4. k oo yielded best performance consistently. Observe that this choice of k oo is still very different from both regular GNNs, which usually considerably restrict and regular transformers (Eq. [T. whose receptive field is not restricted at all (i.e., in terms of reachability).
3.2 Positional Encodings based on DAG Depth
As outlined in Section 2 positional encodings have been recognized as important and proven effective for incorporating graph structure into transformers. Observe that the sequential nature of DAGs makes them possess special position information, the depth of node within the DAG. We propose include this knowledge in the form of directed acyelic graph positional encodings (DAGPE) as follows, exactly as suggested for the original transformer architecture (Vaswani al. 2017
(e sin depth(u)
(.(0220+1) = cos depth
10000 2
11000
where d is the node feature dimension and the index the dimension under consideration.
DAG Attention. We obtain the following model, combining DAGRA and DAGPE, for v E V:
K (x + PF Fu + PFN)) K (xx + PE., Zw PE.)
Attention (xv)
Σ
(zu).
Σ
(3)
3EN2(e) wENe(())
Our attention incorporates both similarity of node features and of node depths. We argue that these are the most critical aspects of DAGs and our evaluation will show their impact and general effectiveness. In particular, note that most kinds of DAG data (e.g., citation networks) do not require us distinguishing between predecessor or successor nodes of same depth.
5

---

3.3 Expressive Power of DAG Attention
Technically, we restrict the attention reachable nodes and, in this way, obtain considerable efficiency gains. Yet, our architecture is tailored to the special DAG structure, and we can show that this design offers similar expressivity to regular transformers.
is important to note that in our framework, all nodes directly communicate with at least one source node (i.e., node without predecessors) by the DAG structure. This is specifically the case because do not restrict the radius l of the receptive field, but consider A = oc. Hence, 2 layers are always enough to establish communication beyond any nodes that have common source node. Observe that this is often the case in practice; especially in DAG classification, many kinds of DAGs contain only single source node (e.g., ogbg-code2 Hu et al.
2020) and NA /Zhang al. (2019))
For DAGs with m source nodes we need 2m layers for full communication, if we assume the DAG to be connected. In the latter case, every pair of source nodes has common successor through which communication can happen. Further, comnectedness is a reasonable assumption, otherwise communication is likely not needed in most scenarios.
3.4 Theoretical Intuition
We have shown that our architecture's bias emphasizes DAG relationships while re-directing the remaining relationships in the regular transformer's full attention matrix though the source nodes. This can also be shown to be in line with random walk theory. we draw a connection to PageRank BBinn 1998 Gasteiger a.. Specifically, we consider a PageRank variant that takes the root node into account- personalized PageRank. We define the root node r via the teleport vector igs which is one-hot indicator vector. The personalized PageRank can be obtained for node æ using the recurrent equation ((,) = (1 (1-a) A.. +aúz. with teleport (or restart) probability a E (0. 1]. Solving this equation, we obtain: ( = ah - (1 (x) Arw) - where Arw AD-1 with and D being the adjacency and the degree matrix, respectively [Gasteiger et al.). We invert the directions of the edges in G' to create reverse DAG G. We can show that, for every node x, only nodes not reachable from x (i.e..) y & No (x)) will satisfy that TT(())[v] + ne (iz) (the y-th element of To (iz) )) equals O. The proof is provided in Appendix A. This means that for the random walk's ' limit
distribution, the probability of nodes that are not reachable from x
3.5 Implementation
We describe two ways of implementing our model, especially DAGRA, based upon transformers and message-passing GNNs, respectively.
Masked Attention for Transformers. As shown in Figure I we can implement DAG attention in very straightforward fashion using a mask that masks out node pairs based on the DAG reachability relation as follows (compare to Equation (T), with the attention mask M being defined as symmetric matrix over node pairs (v, u) e V...
QKT vdx
if E Nx(u) +M| V, M(v = {2 -oo otherwise.
Attention (X) = softmax
While this masking represents a simple technique to extend and bias existing transformer models to DAGs, the resulting architecture does not benefit from the restricted node set to be considered, leading to unnecessary, costly matrix operations during attention calculation. Moreover, it consumes ((IV)2) of additional memory to store M. Thus, the runtime complexity per layer is still (((V(2d) for the vanilla transformer and may be even higher, depending on the underlying transformer.
we propose to follow the message-passing scheme; that is, for a node v, we compute (x(v)) and only aggregate messages from the nodes in that set to compute the DAG attention. For the latter aggregation, we can use readily available frameworks, such as PyG Fey and Lenssen 2019]. We analyze the complexity of this proposal.
DAG Attention using Message Passing, Based on the formulation in Equation

---

Table I: Statistics of the datasets used.
ogbg-code2
NA
Self-citation
Cora
Citeseer
Pubmed
# graphs
452,741
19,020
1,000
1
Avg # nodes
125.2
8.0
59.1
2,708
3,327
19717
Avg noc
9.78
7.00
4.30
20.88
5.33
60.56
3.6 Computational Complexity
Clearly, the time complexity of the proposed model is lower than that of the standard transformer. We consider two computation steps:
Computing DAG Reachability. To obtain Ng. compute the transitive closure of E for each node in the graph using breadth-firs ffistt search starting at the node and iteratively expanding N₂ based on E. Hence, the overall complexity of this step is O(EE) [V)). Observe that, during training, we consider this step as pre-processing since it only has to be run once, in the very beginning.
The matrix product QK of self-attention has a cost O( which is quadratic the number of nodes in G, and hence especially critical for large graphs. Yet, for our DAG attention, only aggregate messages from reachable nodes. Therefore, the time complexity of reachability relation attention is O([V] x ny X d), where T& is the average size of Ng. In the worst case, we have 7 [V| but assume that n& << [V] in general. Especially for sparse graphs, the complexity gets significantly lower, i... O(IV) x deg x d), where deg is the average node degree.
DAG Attention.
Finally, observe that directed rooted trees represent special kind of DAGs broadly domains, such as abstract syntax trees of source code [Allamanis et al. 2018). For them, the runtime of DAG attention scales almost linearly, as illustrated in the following theorem.
across
Theorem 1. In directed rooted tree T, the runtime of DAG attention is O((V) x k: x A+ x d), where A + is the maximal outdegree of When k = co, the runtime of DAG attention is O(VI x depth(() x A d).
The proof is provided in Appendix A. Note that when A is small, d constant and depth(() is Ollog [V]), the runtime of DAG attention is almost linear in [V]. Indeed, we observed this on the ogbg-code2 dataset in our experiments.
4
Evaluation
We evaluate our proposed architecture on several datasets, comparing competitive baselines. Ablation studies also provide more insight into the composition of our model. Primarily, the following questions are investigated:
Does DAG attention have the expected effects and improves existing graph transformers both in terms of quality and efficiency?
Is DAG bias encoded through both DAGRA & DAGPE, and how does DAGPE compare to others?
How does the size of the receptive field the main difference between regular GNNs and trans- formers affect the performance?
4.1 Experiment Setting
Datasets. Table shows the diversity of the datasets we used; see Appendix B for full details.
ogbg-code2 (Hu et al. 2020). A large dataset of ASTs derived from Python methods. The node features are syntax tokens. The multi-task classification task to predict the first 5 tokens of the function name.
NA Zhang et al. 2019 A dataset with much smaller graphs, containing neural architecture DAGs generated by the ENAS software. Each node's features represent certain neural network component type. The (regression) task is to predict the architecture performance on C10.R-10.
Self-citation ARCC 2021 Luo et al. 2023). Fach DAG in the academic self-citation represents Each paper has two node attributes: the
scholar's s academic self-citation network ARC 2021

---

Table 2: Code graph classification ogbg-code2. The baseline results were taken from OGB leaderboard.
Table Node classification results for the self- citation dataset; AP (%) and ROC-AUC (%).
Model
Valid F1 (8)
Test F1 (18)
Timetepoch)
Model
APT 1
ROC-AUCT 1
GIN
13.7 = 0.2
14.9 = 0.2
181s
GIN
57.7 = 1.8
79.7 = 0.2
14.0 - 0.2
0.2
GCN
79,9 02
GIN-Viruul
14,4 0.3
15.8
02
155s
GIN-Virtual
57,4
79.5 i 0.4
GCN- Virtual
14.6 + 0.1
16.0
+ 0.2
198s
GCN-Visual
58.9 0:2
80.0 0.1
GAT
14.4 -
15.7
134s
GAT
55.3
77.9
PNA
14.5 0.3
15.7 = 0.3
427s
PNA
6..4
81.0
DAGNN
16
17:5
6018s
DAGNN
61.2.1066
81.0
PACE
16.3
17.8 0.2
2410s
PACE
52.1 1.8
75.9
Transformer
15.5 +: 0.2
16.7
1817s
Transformer
56.8 +: 1,8
78.7 0.3
DAG+Transformer
17.4 0.1
18.8 + 0.2
591s
DAG+ Transfornerr
63.8 = 0.8
82.2 0.5
GraphTrans
16.6
18,3 =:
1117s
GraphGPS
61
81.3 =
DAG-GraphTrans
17.0 1: 0.2
18.7 0.2
526s
DAG-GraphGPS
63.5 1:
80.8 0.5
GraphCPP
17.4 + 0.2
18.9 + 0.2
1919s
SAT
59.8 + 1.7
79.8 + 0.7
DAG+GraphGPS
17.6
19.3
DAG+SAT
80.6 0.7
SAT (SOTA)
17.7 +: 0.2
19.4 +: 0.3
2437s
NodeFormer
39.6 4:
69.4 0.3
DAG+SAT
18.5
20.2
681s
DAG=NodcFormer
64.9 1:
81.7
publication year and total citation count (excluding the papers whose citation category is to be inferred). Here we consider the node-level task of predicting whether paper is highly-cited or not as a proxy for its impact.
Cora, Citeseer, Pubmed (Sen al. 2008 Established, medium-sized citation graphs. Only for our method, we removed a small number of cyclic citation links to make them DAGs.
Baselines. We chose two basic message-passing GNNs, GCN and GIN; extensions of these models using a virtual node connected to all other graph nodes; the graph attention network GAT, as it showed especially good performance in [Thost and Chen
2021: MixHop [Abu-El-Haija 2019], LDS-GNN [Faaceschhi et al. 2019]. J. IDGL [Chen et al. 2020 and PNA, as more recent GNN proposals. In terms of transformer models, we considered vanilla Transformer (TF), Graph Transformer (GT), GraphTrans, SAT, GraphGPS and NodeFormer which achieved statc-of-the. art performance (SOTA). Lastly, we consider neural networks tailored DAGs: S-VAE, D-VAE,
al.)
DAGNN and the current SOTA, PACE. For more detailed descriptions, see Section 2
DAG+ Models. We implemented DAG attention on top of vanilla Transformer, GraphTrans, SAT, GraphGPS and NodeFormer only (1) modifying their self-attention module by restricting attention in terms of reachability and (2) using DAGPE instead of the original one. We note that there various alternatives for the latter (e.g.. concatenation etc.), therefore we opted for the most simple solution which, at the same time, provides very direct comparison. Moreover, on ogbg-codee code2 we did not use any PE since [Chen et al. 2022a] showed that they do not make real impact and we observed the same in preliminary experiments. For fair comparisons, we use the same hyperparameters (including the number of layers, batch size, hidden dimension etc.) and readout as bascline transformers. Given one of the baseline transformers M, we denote the modified model using DAG attention by DAG+M. Unless explicitly specified otherwise, we chose & Do in all experiments. Full details on the experimental setup and hyperparameters are provided the Appendix B.
4.2 Results and Discussion
Overall Performance, Tables 2 and 5 First, observe that the results are very consistent, although the datasets differ greatly size. DAG sizes, DAG shape (e.g., in ogbg-code2 we have trees), and nature of data (c.g., node features). The passsng GNNs represent standardized baselines but do reach the performance of networks tailored DAGs, such as DAGNN. Note that the latter is however comparatively bad on the node-level task. This can be explained by its processing. computes node representations in the order of the partial order, and hence the representations of nodes in the beginning of the order contain only few information about the entire graph. Intuitively, transformers should be able to capture this information, but the transformers we tested do neither perform better, not even the ones tailored to graphs. This shows that they are missing information captured by those message-pase passsng neural networks that were tailored to DAGs. The results clearly show that DAG attention is successful in providing good improvements, over the best graph
8

---

Table 4: Node classification accuracy The baseline results were taken from [Wu et al. 2022].
Table 5: Regression. Predictive performance of latent representations over NA.
Model
Cora
Citeseer
Pubmed
Model
RMSE 4
Pearson 1 1
GCN GAT
87,06 + 0.34
75.75 + 0.37
88, + 0.14
GCN
0.482 = 0.005
0.871 + 0.001
86.85 : 0.30
75.92
= 0.26
86.90 + 0.22
S.VAE
0.521 = 0.002
0.847 :: 0.001
MixHop
87,59 1 0.52
73.64
1: 0.73
89.32 1 0:25
D-VAE
0.375 = 0.003
0.924 1 0.001
IDGL
87,88 +: 0.34
74.32
+: 0.51
89.22 + 0.14
DAGNN
0.264 + 0.004
0.964 + 0.001
LDS-GNN
67,82 0.62
75.22
+: 0.25
OOM
PACE
0.254 0.002
0.964 + 0.001
PACE
79.47 = 0.63
73.65
= 1,23
OOM
Transformer
0.285 = 0.004
0.957 + 0.001
Transformer
75.92 4: 0.86
72.23 +: 1.06
OOM
GT
0.275 = 0:003
0.961 +: 0.001
DAG-Transfrmerr
87,80 1: 0.53
74.42 1: 0.22
89.01 +: 0.13
DAG-Transformer
0.253 =: 0.002
0,966 1: 0.001
SAT
75.18 + 0.62
74.88 + 0.73
0OM 89.17 + 0.15
GraphCPS
0.306 =: 0.004
0.950 + 0.001
DAG+SAT
87.48 0.37
76.64 + 0.36
GGG-GraphGPS
0.267 = 0.005
0.964 + 0.001
NodeFoomeer
88,80 +: 0.26
76.33 + 0.59
89.32 + 0.25
SAT
0.298 + 0.005
0.952 + 0.001
DAG=NodeFormer
90.49 0.17
78.24 +: 0.33
89.44 0.24
DAG+SAT
0.262
0.964
Table 6: Ablation results.
ogbg-code2
NA
Self-citation
Ablation
Valid Fl
Test Fl
RMSE +
Pearson's
AP
ROC-AUC
DAG+TF
0.1731 + 0.0014
0.1895 + 0.0144
0,253 0.002
0.966 = 0.001
0.088
0.822 0.005
(-) DAGRA
0,1546 1 0.0018
0,1670 + 0.0015
0,284 :: 0.003
0.957 = 0.001
0,573
0.011
0,790 0.003
(-) DAGPE
0.1739 1: 0.0013
0.1879 1 0.0015
0.263 :: 0.002
0.963 :: 0.001
0.594
0.028
0.782 0.018
(+) RWPE
0,267 0.003
0.962 0.001
0.628 0.014
0.819 0.010
(+) LapPE
0.271 + 0.002
0.961 = 0.001
0.609 0.017
0.786 1 0015
(+) SPD atn
2021
0.1749 + 0.0111
00017
0.006
0.823 0.004
(+) Edge Direction
0,1751 + 0.0018
0,1870 + 0.0021
0.636
0.015
0.817 + 0.005
0.1546 :: 0.0018
0.1670 1 0.0015
0.285 :: 0.004
0.957 = 0.001
0.018 0.568
0.787 0.003
DAG+SAT
0,1821 # 0.0015
0,1982 + 0.0010
0,262 + 0.004
0.964 = 0.001
0.627 + 0.015
0.806 0.007
DAGRA
U.1773 0.0023
0.0028
0.292
0,003
0.954 0.001
0.012
(-) DAGPE
0,1846 + 0.0010
0,2018 + 0.0021
0.282 + 0.002
0.958 = 0.001
0.623 0.014
0.806 + 0.005
(+) SPD Ving al 2021
0.1851 + 0.0008
0.1991 + 0.0088
0.016
0.810 0.006
(+) Edge Direction
0,1839 1 0.0014
0.1978
1 0.0028
0.623 0,013
0.804 1 0.007
SAT
0.1773 4: 0.0023
0.1937 + 0.0028
0.298 4: 0.003
0.952 0.001
0.598 0.017
0.798 0.007
transformer SAT and even better ones over vanilla Transformer. On ogbg-code2, the improvement is smaller for GraphTrans and SAT. However, this benchmark task is heavily dependent on other features (e.g., language understanding) and hence presents a special challenge; in this regard, the NA and self-citation datasets contain "cleaner" graphs. It is interesting to see that our framework lifts the transformers from below the level of DAGNN to above, in terms of all metrics, over these two datasets. Lastly, we observe that the PACE transformer tailored to DAGs is similarly outperformed by our simpler, but more effective technique. Nevertheless, the overall conclusion holds in general: Over all datasets, our DAG attention makes the transformers outperform (1) the original transformers and (2) the neural networks tailored to DAGs. This shows that the DAG-specific bias provided by DAG attention is the right bias. We investigated this in more detail in our ablation experiments.
Ablation Study, Table 6 Recall that our DAG attention is composed of the reachability- attention (DAGRA) and DAGPE modules. To justify this design, (1) our ablation studies removing DAGRA and DAGPE individually confirm the impact of both modules: (2) we also experimented
with replacing DAGPE with LapPE [Dwivedi and Bresson] 2020] and the wandom-walk-ie based RWPE (Dwivedi et al. 2021] to show that the DAG-specific nature our PE is of advantage; (3) we experi- mented with adding attention bias which captures the graph structure more directly (e.g., shortest-pati Ying et al. [222]] and edge directionality). although they are implicit in DAGPE; interestingly, the more direct representation does not make noticeable difference. For ease of comparison and inter- pretation (i.e., in terms of magnitude), we also provide the baseline transformer results. Overall, can be observed that our DAG attention yields highly consistent performance improvements, although occasionally the advantage is less pronounced. This shows that our architecture design provides the right bias on top of (graph) transformers, which makes the improved models better fit for DAGs.
Impact of Size of Receptive Field NE-
(1) Average Ti Table 1 Compared to the often only two to three hops considered in message- passing GNNs, our = oo might seem unrealistic, However, as we show in the table, for two of our three and very different datasets, we have that nxx is much smaller than the worst case size [V] NA
9

---

Table 7: Impact of different & on DAG attention, over ogbg-code2.
Test Fl score
Avg ng
Av Time Egoch (3)
DAG+TF
DAG+SAT
1.97
0.1724 0.002
0.1533
0,0108
3.91
0.1800 1 0.0033
0.1918
0,0010
3
5.69
0.1842
0.0006
0.1934
0,0009
7.16
0.1849
0,021
0.1975
0.0019
5
8.29
0.1856
0,0200
0.2000
0,0005
9.01
0.1869
0.0020
0.2000
0,0015
7
9.40
0.1869
0,019
0.2004
0:0014
9.60
0.1875
+ 0.0088
0.2005
0,0010
9.78
0.1879
0.0155
0.201 8 0:0021
Figure Average training time per epoch for various À over oghg-code2, log scale.
represents a special case because the graphs are very small so that we can always find directed path through them that contains all nodes; however, given that [V] is generally small, the exception of the rule Tlo << [V] is not critical here. (2) Performance for Varying Table 7 Figure We ran our model for different ogbg-code2, based upon vanilla Transformer and SAT. We find that incorporating reachable node information leads to small but constant improvements performance & increases. This confirms our intuition about the importance of predecessors and successors in DAGs, and is in line with related works suggesting to iteratively aggregate the DAGs along the partial order.
Figure depicts the training time per epoch. It is easy to see that our framework reduces computation time considerably. For example, even the most time-consuming DAG+SAT requires 10 minutes per epoch, compared to 40 minutes for SAT and 100 minutes for DAGNN on the same GPU type. Since SAT and DAGNN represent the best-performing models among the transformers and, respectively, message-passing GNNs, and DAG attention yields qualitative improvements over both.
5
Conclusions
Based on the insights from graph neural networks and models for directed acyelic graphs, we have developed transformer model biased towards DAGs, which allows for incorporating the main characteristic DAGs their partial order into any transformer architecture, by encoding the reachability relation and positions resulting from it. Our architecture is simple and universal demonstrated in our experiments. Most importantly, it provides an effective extension improving existing graph transformers over DAGs. While framework has successfully lifted existing (graph) transformers to the level of the state-of-the-art neural networks tailored to DAGs, our experiments show that there is still room for improvement. There is variety of challenging tasks many different kinds of DAGs, which are not fully solved yet; for instance, to tackle the challenge of reasoning over source code graphs, the models will probably need better language understanding. Hence DAG representation learning remains interesting for research, and our work provides an important contribution closing the gap between transformers and other DAG neural networks.
Limitations. Our study is very general, but we found only a limited number of DAG datasets. We tried to resolve this by creating new ones (from the established citation datasets), yet we acknowledge that there still room for extension. Further, there are likely specific types of DAGs which benefit from more customized modeling. Yet, our study is intended to address general adaptivity to DAGs.
Broader Impact. Transformers have been popular in artificial intelligence, and is expected that they also gain importance in graph learning. We hope to provide tiny piece to the advancement of the area. Our framework is rather abstract, but simplicity, efficiency, and universality make practically usable; and we demonstrate good performance variety of data.
10

---

Acknowledgments
We extend our gratitude to Yicheng Pan for his invaluable assistance with the computational com- plexity analysis. We also express appreciation to all the anonymous reviewers for their insightful and constructive feedback. This work was supported by National Key R&D Program of China (201YYE33500700) NSFC Grant 62172026, National Social Science Fund of China 22&2D153, the Fundamental Research Funds for the Central Universities and SKLSDE.
References
The acl anthology reference corpus. https:/accammhooogy.orrg Nov. 2021.
Sami Abu-El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard. Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):1-37, 2018.
Uri Alon, Shaked Brody, Omer Levy, and Eran Yahav. code2seq: Generating sequences from structured representations of code. arXiv preprint arXiv:1808.01 014800000000, 2018.
Sergey Brin. The pagerank citation ranking: bringing order to the web. Proceedings of ASIS, 1998, 18:161-172, 1998.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pages 3469-3489. PMLR, 2022a.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs arXiv preprint arXiv:2206.044: 04910, 2022b.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33: 19314-19326, 2020.
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:13260-121 2020.
Maxwell Crouse, Ibrahim Abdelaziz, Cristina Cornelio, Veronika Thost, Lingfei Wu, Kenneth Forbus, and Achille Fokoue. Improving graph neural network representations of logical formulae with subgraph pooling. arXiv preprint arXiv:1911.060 19099944,1 2019.
Zehao Dong, Muhan Zhang, Fuhai Li, and Yixin Chen. Pace: A parallelizable computation encoder for directed acyclic graphs. In International Conference on Machine Learning, pages 5360-5377. PMLR, 2022.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021.
Vijay Prakash Dwivedi, Ladislav Rampákek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. arXiv preprint arXiv:2206.088 164, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint ar Xiv: 1903, 1903.02488, 2019.

---

Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In International conference on machine learning, pages 1972-1982. PMLR, 2019.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. IEEE transactions on Neural Networks, 9()):688-2)7 786, 1998.
Scott Freitas and Yuxiao Dong. A large-scale database for graph representation learning. Advances in neural information processing systems, 2021.
Mukul Gagrami, Corrado Rainone, Yang Yang. Harris Teague, Wonseok Jeon, Roberto Bondesan, Herke van Hoof, Christopher Lott, Weiliang Zeng, and Piero Zappi. Neural topological ordering for computation graphs. Advances Neural Information Processing Systems, 35:17327-17339,
2022.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations.
Simon Geisler, Yujia Li, Daniel Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. arXiv preprint arXiv:2302.00049 2023.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
Weihua Hu, Matthias Fey, 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 11-12133, 2020.
Fei Huang, Tianhua Tao, Hao Zhou, Lei Li, and Minlie Huang. On the learning of non-autoregressive transformers. In International Conference on Machine Learning, pages 9356-9376. PMLR, 2022.
Scohyun Kim, Jinman Zhao, Yuchi Tian, and Satish Chandra. Code prediction by feeding trees to transformers. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pages 150-162. IEEE, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openreview.nell
forum
Boris Knyazev, Michal Drozdzal, Graham W Taylor, and Adriana Romero Soriano. Parameter prediction for unseen deep architectures. Advances in Neural Information Processing Systems, 34: 29433-2944 2021.
Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4968-4977, 2021.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournaau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 14421668--2129 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv: 03983, 2016.
Yuankai Luo, Lei Shi, Mufan Xu, Yuwen Ji, Fengli Xiao, Chunming Hu, and Zhiguang Shan, Impact- oriented contextual scholar profiling using self-citation graphs. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 4572-4583, 2023.
Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral-based graph convolutional network for directed graphs. arXiv preprint wtX.vv11977089900 2019.
12

---

Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667 2021.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.0843 2022.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pages 225-228. IEEE, 2018.
Han Peng, Ge Li, Yunfei Zhao, and Zhi Jin. Rethinking positional encoding in transformer for code representation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3204-3214, 2022.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International conference on machine learning, pages 4095-4104.
PMLR, 2018.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205. 12454, 2022.
Jerret Ross, Brian Belgodere, Vijil Chenthamarakshan, Inkit Padhi, Youssef Mrouch, and Payel Das. Molformer: Large scale chemical language representations capture molecular structure and properties. 2022.
Alvaro Manchez-Gonzalee Jonathan Godwin, Tobias Pfaff, Rex Ying. Jure Leskovee, and Peter W. Battaglia. Learning to simulate complex physics with graph networks. CoRR, abs/2002.09405,, 2020. URL htt.atpp//aaiii.rrr//////2222200
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification network data. Al magazine, 29(3):93-93, 2008
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. arXiv preprint arXiv: /803.02/55.5 2018
Weizhou Shen, Siyue Wu, Yunyi Yang, and Xiaojun Quan. Directed acyclic graph network for conversational emotion recognition. arXiv preprint arXiv:2105.12907, 2021.
Bing Shuai, Zhen Zuo, Bing Wang, and Gang Wang. Dag-recurrent neural networks for scene labeling. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3620-3629, 2016.
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. Advances in neural information processing systems, 18, 2005.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3):714-735, 1997.
Zeyu Sun, Qihao Zhu, Yingfei Xiong, Yican Sun, Lili Mou, and Lu Zhang. Treegen: A tree- bree-baedd transformer architecture for code generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages
2020.
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 1556-15565 1566, 2015.
Veronika Thost and Jie Chen. Directed acyclic graph neural networks. Internationaa Conference on Learning Representations, 2021. URL http://wwwwweeeeeee/////m/ddddda
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. Advances neural information processing systems, 33:17907-17913 2020.
13

---

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401, 2022.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. In The Eleventh Interna- tional Conference on Learning Representations, 2023. URL hutps://ppeneeeew.ettffommm
j6zUzrapY3L
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13666133 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances Neural Information Processing Systems, 34:28877-28888, 2021.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetorrks for neural architecture search. arXiv preprint arXiv: 111..05799 2018
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: A variational autoencoder for directed acyclic graphs. Advances in Neural Information Processing Systems, 32, 2019.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. Magnet: neural network for directed graphs. Advances in neural information processing systems, 34: 17703-270015 2021.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinform., 34(13)i457-i466, 2018
Daniel Zügner, Tobias Kirschstein, Michele Catasta, Jure Leskovee, and Stephan Günnemann. laanuuage-agnosiee representation learning of source code from structure and context. In Interna- tional Conference on Learning Representations.
14

---

A Proofs
Theoretical Intuition of DAG Attention
Proof. Personalized PageRank is defined as (6( (1 ar) Arw + oizz Through rear- rangement, we obtain: (I, (1 a)Arw ATG
aiz. Now prove that (In (1 A is an invertible matrix. The matrix is invertible iff the determinant det(L, (1 Arw)) * 0, which is the case iff' det(Arw In) # O, ie., iff T-o is not an eigenvalue of Arw- This value is always larger than since the teleport probability E (0, 1]. However, the largest eigen- value of the row-stochastic matrix Arw is 1, as can be proven using the Gershgorin circle theorem. Hence, I-a cannot be an eigenvalue and (In- - (1 Arw) is invertible matrix. So obtain Because the spectral radius (largest eigenvalue) matrix (1 Arr is less than 1, from the Neumann series theorem, we obtain
To( = a(In - (1
(1- a))
Σ (r))
Σ (1--))AD=)) m==
Because D is a diagonal matrix and a is a constant, they do not affect whether an element in the matrix is O or not. Therefore, we only need to discuss >m A Because A is the adjacency matrix of the DAG G, in this matrix, iff there is not a directed path from x to (x & y), we deduce that (Em=o ATH [z. y] O. This leads us the conclusion that Tg (1x)(g) O.
We invert the directions of the edges G to create a reverse DAG G. We can also obtain that, iff & y, then (+=)) = 0.
Therefore, for every node x, only nodes y that y & (1) will satisfy that To (1> + ae (tz) [vl equals O.
Theorem In directed rooted tree T (V,E) with the number of nodes [V, the runtime of DAG attention is O(VV x h x A d), where A is the maximum out degree of the T and d is feature dimension. When oc, the runtime of DAG attention O(V) x E A+ d), where the depth T.
Proof. In DAG attention, for each node v, we need calculate the attention to (v), whose runtime is upper bounded by (v)) x d). So the runtime of DAG attention is linear in the sum of the sizes of receptive fields E [N)]. We only need to show that Evev [N)(v)] [V] x A+. When & oc, Evev (N) < [V] x x A+.
Next, we prove this theorem for the case of k- = oc. For bounded k the proof is similar. We prove by induction on the depth l of T.
We assume that A > 2, since when A 1, is l-ary tree, Evev |
[V] x l A+.
For the basis step, when é = 0, T' only has one node. So EVEV
= -
For the inductive step, assume that Σvev NN [x)) < V x x + holds when E > O. Consider a tree Thew of depth f + 1 whose root is denoted by Then the sub-trees whose roots are the children of r have depth at most f. Let be the number of these sub-trees, 8 & A+, and V. be the node set of the i-th sub-tree. Since the number of reachability relations with involved is 2([ 1), we have
(v))
NEV
(x))+++(([V)) 11)
RE
VE
[ x E A +... + |VG] x ex A +2(V -
E (V + 1))
A (V - + ([VI-
((+1)XAA |
15

---

Table The statistics of academic self-citation dataset.
Min
Avg
Max
# nodes
30
59
296
DAG depth
5
21
Node degree
0
1.8
83
This completes the proof of Theorem 2 for the case of l: oc.
B
Experimental Details
B.1
Computing Environment
Our implementation is based on PyG (Fey and Lenssen 2019]. All reported results are averaged over 10 runs using different random seeds. The experiments conducted with two RTX 3090 GPUs.
B.2
Dataset Details
We provide details of the datasets used in our experiments, including ogbg-code2 [Hu et al.) 2020). Neural architectures (NA) [Zhang et al. 2019]. Self-citation, Cora, Citeseer and Pubmed [Sen et al. 2008).
2020 is a dataset containing 452,741 Python method definitions extracted from thousands of popular Github repositories. It is made up of Abstract Syntax Trees as DAGs where the task is to correctly classify the sub-tokens that comprise the method name. The min/avg/max numbers of nodes in the graphs are 11/125/36123, respectively. We the standard evaluation metric (FI score) and splits provided by [Hu et al. 2020).
ogbg-code2. ogbg-code2 (uu et al.
Neural architectures (NA). This dataset is created in the context of neural architecture search. It contains 19,020 neural architectures generated from the ENAS software [Pham et al. 20188. Each neural architecture has layers (i.c., nodes) sampled from 6 different types of components, plus an input and output layer. The input node vectors are one-hot encodings of the component types. The weight-sharing accuracy [Pham et al. 2018 (a proxy of the true accuracy) on CIFAR-10 (Krizhessky et al. 22099] is taken as performance measure. Since it is regression task, the metrics are RMSE and Pearson's 's r. We use the splits as used in (Thost and Chen 2021]. Details about the generation process can be found in (Zhang et al., (2019).
Self-citation. The academic self-citation dataset is directed acyelic graph, representing the scholar's academic self-citation network on the natural language processing (NLP) field extracted from ACL Anthology Reference Corpus [ARC] [02T]. This dataset contains 1000 academic self-citation networks from scholars ranked top- 1000 by number of papers. In self-citation networks, cach node is a paper of this scholar and each directed edge indicates that one paper is cited by another one. Each graph node includes two quantitative attributes: the publication year, the paper's total citation count. The task is to predict missing citation counts given existing citation counts. Specifically, for each scholar self-citation network, randomly select 10% of its papers and drop their citation counts, and the node-level task is to predict whether a paper which misses its citation count is highly-cited or not. In Computer Science, Engineering, and Mathematies, for papers in ISI (Web of science database) listed journals that are 10 years old, around 20 citations gets in the top 10%. So we consider papers with citation count greater than or equal to 20 as highly-cited papers. As the class balance is skewed (only 27.2% of data is positive), we use the Average Precision (AP) and ROC-AUC as the evaluation metries. We randomly split the dataset into 80% training. 10% valid and 10% test sets. The statistics is shown in Table [
2008]. These three datasets are commonly used citation networks for evaluating models on node classification tasks. These datasets are medium-sene networks (with 2K-20K nodes) and the goal classify the topics of documents (instances) based on input features of each instance (bag-of-words, representation of dlccuments) and graph structure (citation links). For the baselines, the citation links are treated as undirected edges [Wu et al. 2022 and each document has class label. Only for our method, we treated citation links as directed edges and removed a small number of cyclic citation links to make them DAGs, We use the same evaluation metric (classification accuracy) and splits provided by NodeFormer [u et al. 2022
Cora, Citeseer and Pubmed (Sen
16

---

Table Hyperparameteer search different datasets.
Hyperparameter
NA
Self-citation
Cora, Citeseer and Pubmed
# Layers
[
[2, 3, 4, 5]
{2, 3, 4, 5]
Hidden dimensions
{32,128)
(32. 64, 128]
[16, 32, 64, 128) 0.0
Dropout
0.2
{0.1, 0.2, 0.5)
Learning rate # Epochs Weight decay
1e-3
[le-4, 5-e4, 1e-3, Se-3)
fle-3, 1e-2) 1000
100
[50, 100)
None
lc-6
5e-3
# Attention heads
12, 4)
12, 4, 8)
{2, 4|
Table 10: Number of parameters for DAG+ models.
Model
ogbg-code2
NA
Self-citation
Cora
Citeseer
Pubmed
DAG=Transformer
127,06k
399k
478k 710k
291k
404k
14k
DAG+SAT
149,53k
631k
276k
165k
14k
B.3 Hyperparameters and Reproducibility
ogbg-code2. We implemented DAG attention vanilla Transformer, GraphTrans, GraphGPS and SAT that we only modify the self-attention module to DAG attention module. And we do not use any PE well baselines because it makes very little performance improvement (Chen al. 2022a] For fair comparisons, we use the same hyperparameters (including training schedule, optimizer, number layers, batch size, hidden dimension etc.) as baseline models for all of our four versions. NA. We train the transformer-bace based baselines (vanilla Transformer, GraphGPS and SAT) in front of DAGNN (Thott and Chen 2021]. For SAT, we the 3-subtree GNN extractor (GIN). For GraphGPS, we use GatedGCN as GPS-MPNN and vanilla Transformer as GPS-GlobAttn. And we implement DAG attention on those respectively. We follow the exact training settings of DAGNN (Thost and Chen 2021]. Then we also train sparse Gaussian process (SGP) [Snelson and Ghahramami [0055 with learning rate of 4c-4, a epochs number 200 as the predictive model to evaluate the performance of the latent representations. The transformer- based hyperparameters are summarized in Table 9 other hyperparameters are the same as those of DAGNN (Thost and Chen [02T].
All
Self-citation. We implement DAG attention on the vanilla Transformer, GraphGPS, SAT and NodeFormer. In general, we perform a hyperparameter search to produce the results for our model and baselines. The hyperparameters on the academic self-citation dataset are summarized in Table g where # Attention heads is tuned for transformer-basee models. For SAT, we conduct positional encodings search on LapPE-8, RWPE-20 or None, and we use the 3-subtree GNN extractor (GIN). For GraphGPS, we use GatedGCN as GPS-MPNN and vanilla Transformer as GPS-GlobAttn. The other poper-parmmetrs for NodeFormer are the default parameters in their public code. In all experiments, we use the validation set to select the best typerparameters.. All our models and basclines are trained with the AdamW optimizer [Loshchilov and Hutter 2016) and use the cross-entropy loss this classification task. The learning rate scheduler is the cosine scheduler Loshchilov and Hutter (016)) Cora, Citeseer and Pubmed. We implement DAG attention the vanilla Transformer, SAT and NodeFoomerr. Only for Pubmed, we choose the size of the receptive field A = 2 (otherwise k = oo). And we perform hyperparameter search produce the results for our model and those transformer- based baselines in Table 9 We follow all other training setting and hyperparameters of NodeFormer [Wu et al. 2022 For SAT, use the 1-subtree GNN extractor (GCN).
In Table 10 we report the number of parameters for DAG+ models using the hyperparameters selected from Table
C Model Visualization
Here, we demonstrate that the DAG transformer also provides interpretability compared to the traditional Transformer model. We trained Tra+frrarrrmmer and a Transformer model on self-citation graph, and compared the attention scores between the selected node and other nodes
17

---

learned by both models. Figure visualizes the results. In the leftmost graph, the darker blue of the nodes represents higher number of citations. For the selected node v, DAG attention only puts attention weights the nodes that have citation relations with it (N)( whereas classic self-attention focuses on nodes that are almost unrelated to v. More focus on these core nodes makes the DAG model less influenced by other patterns and thus leads to improved performance.
Self-citation graph
DAG attn
Transformer attn
0.14
AA
0.10
0.15
0.06
0.010
0.04
0.005
0.02
0.00
0.000
Figure 3; Attention visualization DAG+ Transformer and the Transformer on self-citation. The figure shows
the attention weights node the red box learned by DAG attention the classic self-attention.
D Additional Results
D.1 Semi-supervised Node Classification
We test model three citation networks Cora, Citeseer and Pubmed. We implement DAG attention on LlFFormer-aWWe Wu et al. [2023). Table [1 reports the testing accuracy. This show that our framework likely increases both quality and runtime here as well.
Table 11: Node classification accuracy The baseline results were taken from [Wu et al. 2023
Model
Cora
Citeseer
Pubmed
Accuracy
Time (s)
Accuracy
Time (s)
Accuracy
Time (s)
NodeFormer
83.4 +
73.0 +3.0
81.5 +
DIFFORMER-a
84.1 0.6
14.21
75.7 0
8.48
80.5 + 12
1013.31
DAG DIFFORMER
85.1 0.
10.96
76.2 +
7.01
81.6 +
84.15
D.2 MalNet-Tiny
Here consider MalNet-Tine MalNet-Tiny (Freitas and Dong 202 is subset of MalNet which consists of function call graphs (FCGs) obtained from Android APKs. This subset includes 5,000 graphs with maximum of 5,000 nodes, originating from benign software 4 malware types. The FCGs do not have any original node or edge features. The benchmark version of this dataset usually employs Local Degree Profile as the set of node features. And the objective is to predict the type of software solely based on the structure.
Note that did not do any hyperparameter tuning. Further, we implemented DAG attention top of GraphGPS by only modifying the self-attention module, switching to DAG attention. As shown in Table 12 Our DAG+GraphGPS achieves a test accuracy of 93.45% while only requiring 20 seconds per epoch. This demonstrates the quality and efficiency of DAG attention.
E
Further Related Works
Neural Networks on Directed Graphs. Most works we found focus on adapting the Laplacian:
Ma et al. 2019 construct directed Laplacian matrix improve the propagation model by using identities that involve the random walk matrix and its stationary distribution. [Monti et al., 2018 consider several different symmetric Laplacian matrices corresponding to local directed graph motifs.
18

---

Table 12: Graph classification MalNee-Tiny.
Model
Accuracy (%)
Time(epoch)
GraphGPS
92.64 + 0.78
46s
DAG+GraphGPS
93.45 0.41
20s
Moreover, DiGCN [Togg al. 2020 is based on directed Laplacian with PageRank matrix to learn multi-scale features and [Zhang et al. 2021] proposed MagNet, a GNN for directed graphs based the Magnetic Laplacian. The latter has been recently integrated into Transformers in the form of a positional encoding [Gesserr et al. 2023]. Note that this improves predictive performance in directed graphs, but does impact the (quadratic) complexity of self-attention.
Transformers over Trees. Observe that trees are special in that they are a particular, more restricted type of DAGs. [Sun et al.] [020) proposed TreeGen, tree-based Transformer that combines grammar rules and tree structure using a tree reader. However, focuses program-speciffe information. In addition, there are some methods of leveraging tree paths and integrating them into the self-attention module. [Alon et al. 2018 used AST to represent source code snippet. They considered pairwise paths between leaf nodes, representing them as sequences of the leaf and non-leaf nodes in AST. [Kim et al.. 2021] used another type of path that goes from the leaf nodes up to the AST root by traversing its ancestors. [üügner et al.] presented Code Transformer, which combines distances computed on ASTs and context of source code in the self-attention. Specifically, it utilizes four different paths reason about ASTs relative positions. Furthermore, [Peng et al., 2022) designed new directed tree Transformer position encoding for each node based two-dimensional description of tree structures. contrast to these works, we shift our focus toward more general DAGs, use a very simple and intuitive PE, and also adapt the receptive field of the attention.
not directly relevant to our work as
19


Reviews:
[{"review_id": "akntF9b9cL", "reviewer": "Reviewer_U6X8", "summary": "The paper proposing a new Transformer-based graph neural network for directed graphs (DAGs) that restricts the receptive field size of self-attention and adds depth-based node embeddings to improve learning from DAGs. The resulted model is more efficient than previous Graph Transformer models and at the same time more effective in different DAG tasks as shown in many experiments.", "questions": "See Weaknesses above.\n\nI'm looking forward to the author's response and will be willing to update my score.", "limitations": "Limitations are discussed, which is appreciated. L344 says that \"we found only a limited number of DAG datasets\", so one suggestion would be to use a dataset of DAGs introduced in [B].", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of learning from DAGs is interesting and important. Improving Transformers for this problem is a reasonable direction.\n2. The introduced improvements are simple, but effective.\n3. Computational complexity analysis in Section 3.5 is a nice addition.\n4. Experiments are overall convincing.\n5. The paper is easy to follow and presented well.", "weaknesses": "While I enjoyed reading the paper, the paper needs to address the following weaknesses:\n\n1. The paper is missing related works [A, B], which seem to be doing exactly the same as DAGNN by proposing what they call GatedGNN. Therefore, citing DAGNN but not citing A/B can be misleading for readers. \n\n2. Papers [C, D] are also related and it would be nice to discuss them as well. Given their recent appearance it's not necessary to empirically compare to them (although it would make the paper stronger), but they should be discussed. In particular, [C] is solving the same ogbg-code2 task, but achieves much better performance, can the authors discuss why? [D] is proposing a Transformer-based [40] graph model for DAGs and also add node depth-based PE embeddings similar to those in this submission + degree-based embeddings based on [40] (which could further improve the results in this submission). Given these papers, L122: \"to the best of our knowledge, transformers have not been studied particularly in the context of DAGs\" should be rephrased.\n\n3. The DAGRA component of the method does not seem to leverage two important sources of information: (1) the direction of edges -- node predecessors and successors are treated equally based on L163-164; (2) the shortest path distance between nodes -- the mask is equal to 0 or −∞ in L203.  Even though the DAGPE embeddings can help to recover this information, leveraging (1) and (2) seems very natural and could improve results by better distinguishing certain DAG structures. In related papers using Transformers for undirected/directed graphs, (1) and (2) are leveraged. For example, in [C] the forward and backward edges are treated separately, and in [40], [C], the shortest path distance is used in masking.\n\n3. Section 3.3's conclusion is not very clear. Is this section trying to say that all nodes will eventually communicate with each other if enough layers and/or large k are used? Please elaborate/rephrase.\n\n4. Results on ogbg-code2 in Table 6 are a bit confusing, because at first it looks like DAG+TF/SAT are using DAGPE, but from the text it sounds like DAGPE is not used. I think it would be more clear to report both results, with DAGPE and without it, even if the latter is better so that the Table does not have blank entries.\n\n**Minor issues:**\n\n- \"partial order\" - wouldn't it be more appropriate to use \"topological order\" that is often used in DAG context (e.g. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.topological_sort.html and [A, B])? \"partial order\" seems to be more relevant to sets.\n\n-  In Tables, bolding results per pair makes sense, but baseline's top performance should be highlighted too. Also, the overall top performance across all rows can be underlined (or highlighted in some other way).\n\n- In Fig. 3, it's hard to conclude that DAG+Nodeformer separate classes better, so I don't think this visualization is helpful in the main text.\n\n- All equations should be numbered so that reviewers and readers can refer to them easily.\n\n- L130: \"in more important fields than\" - it's a quite subjective statement\n- L154: \"[a] given node’s predecessors\"\n- L169: \"regular transformers (e.g., Eq. 2)\" - Eq. 1?\n- L168: \"still very different\" - please elaborate how is it different given that k=∞ is the best\n\n*References:*\n\n- [A] Graph HyperNetworks for Neural Architecture Search. ICLR 2019.\n- [B] Parameter Prediction for Unseen Deep Architectures. NeurIPS 2021.\n- [C] Can We Scale Transformers to Predict Parameters of Diverse ImageNet Models? ICML 2023.\n- [D] Transformers Meet Directed Graphs. ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for the very detailed feedback!** \n\nQ4 raises an important point which we address in the global reply. We also added some of the discussion below to the paper since it covers interesting aspects. For results on additional datasets, please see the reply to WzDZ, Q2. We sincerely thank you for giving us the opptunity to improve the score and are happy to answer further questions if needed.\n\n\n**Q1 Related Works**\n\nThank you for sharing these related works. We added discussion about them to the paper. \n\n**Q2 Recent Related Works**\n\nWe have noticed a potential mix-up in the citations of [C] and [D] since \"[C] Can We Scale Transformers ...\" does not address the ogbg-code2 task. We found [D] on arxiv in spring and checked out the code, yet:\n- They did not use the data as it is suggested by the OGB benchmark but adapted the graph construction (e.g., making it more succinct by removing redundancy). This likely also addresses the question why they reach such good performance in parts.\n- They did not employ the OGB evaluator.\n- They do not provide the new datasets they constructed on GitHub, making a proper comparison with their work challenging.\n\nFor these reasons, we refrained from directly comparing to [D] since this seems not straightforward and beyond the focus of our study.\n\nWe updated L122 and also the related works section.\n\n**Q3 On Incorporating Graph Structure Differently**\n\nWe intended to design our framework in the most simple and efficient way, in order to ease usability, and therefore decided to focus on the main characteristics of DAGs. \n\nWhile there may be features that can improve our framework in certain scenarios, we will likely never obtain an exhaustive model; several other graph features have been shown powerful (e.g., sibling distances [1]) and others will be shown useful in the future. Nevertheless, when applying our model to [40], we consider the shortest path distance, and applying it to [C], we can take into account the direction of edges. And of course, we can combine them if needed in a specific context.\n\nThat said, it is an interesting question, in how far such features actually increase performance, since they are implicitely covered by the PE. The below results over ogbg-code2 and self-citation seem to suggest that our simple DAG PE is surprisingly strong, as the impact of (1) edge directionality and (2) shortest path distances is limited here.\n\n|                         | ogbg-code2              |                         | self-citation         |                       |\n| ----------------------- | ----------------------- | ----------------------- | --------------------- | --------------------- |\n|                         | Valid F1 score          | Test F1 score           | AP                    | ROC-AUC               |\n| DAG+transformer         | **0.1739 $\\pm$ 0.0013** | **0.1879 $\\pm$ 0.0015** | **0.638 $\\pm$ 0.008** | **0.822 $\\pm$ 0.005** |\n| DAG+transformer+(1)     | 0.1751 $\\pm$ 0.0018     | 0.1870 $\\pm$ 0.0021     | 0.636 $\\pm$ 0.015     | 0.817 $\\pm$ 0.005     |\n| DAG+transformer+(2)     | 0.1749 $\\pm$ 0.0011     | 0.1881 $\\pm$ 0.0017     | 0.639 $\\pm$ 0.006     | 0.823 $\\pm$ 0.004     |\n| DAG+transformer+(1)+(2) | 0.1750 $\\pm$ 0.0017     | 0.1884 $\\pm$ 0.0012     | 0.637 $\\pm$ 0.005     | 0.821 $\\pm$ 0.004     |\n| DAG+SAT                 | **0.1846 $\\pm$ 0.0010** | **0.2018 $\\pm$ 0.0021** | **0.627 $\\pm$ 0.015** | **0.806 $\\pm$ 0.007** |\n| DAG+SAT+(1)             | 0.1839 $\\pm$ 0.0014     | 0.1978 $\\pm$ 0.0028     | 0.623 $\\pm$ 0.013     | 0.804 $\\pm$ 0.007     |\n| DAG+SAT+(2)             | 0.1851 $\\pm$ 0.0008     | 0.1991 $\\pm$ 0.0018     | 0.627 $\\pm$ 0.016     | 0.810 $\\pm$ 0.006     |\n| DAG+SAT+(1)+(2)         | 0.1852 $\\pm$ 0.0013     | 0.1986 $\\pm$ 0.0019     | 0.628 $\\pm$ 0.007     | 0.811 $\\pm$ 0.005     |\n\n\n\n**Q5 Additional ogbg-code2 Results**\n\nThis is a fair point, we revised the table as follows.\n\n\n   |           | Valid F1 score      | Test F1 score       |\n   | --------- | ------------------- | ------------------- |\n   | DAG+TF    | 0.1731 $\\pm$ 0.0014 | 0.1895 $\\pm$ 0.0014 |\n   | (-) DAGPE | 0.1739 $\\pm$ 0.0013 | 0.1879 $\\pm$ 0.0015 |\n   | DAG+SAT   | 0.1821 $\\pm$ 0.0013 | 0.1982 $\\pm$ 0.0010 |\n   | (-) DAGPE | 0.1846 $\\pm$ 0.0010 | 0.2018 $\\pm$ 0.0021 |\n\n**Q6 Minor Issues** \n\nThank you for checking on that level of detail! We updated the paper accordingly.\n\nRegarding $k=\\infty$, note that this setting still strongly decreases the complexity compared to regular transformers, since only the reachable nodes are considered for attention. However, given the special DAG structure, this likely does not decrease the effective attention. A detailed discussion on the power of our attention is given in the global reply.\n\n----------------------\n[1] Zügner et al. “Language-Agnostic Representation Learning of Source Code from Structure and Context.” ICLR 2020."}, {"review_id": "eOOdTmcrfn", "reviewer": "Reviewer_Qc5n", "summary": "The paper proposed a new approach for DAG representation learning using transformer. The representation learning on DGA is significant as DAG can be adapted into many real-world problems, which is also explained in the paper. In addition, the DAG can be formed into a sequence of nodes so that it is naturally to think about using transformers to model. The paper conducted comprehensive experiments to support its claim.", "questions": "See weakness.", "limitations": "Limitations have been discussed by the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper utilizes transformer to achieve representation learning on DAG, which is natural. Although transformer has been used on graphs, they are mostly for undirected graphs. \n\nThe paper tells the story in an easy-to-read way. It also conducts extensive experiments to show the superior performance of the proposed model.\n\nThe task the paper wants to solve is significant in that DAG can be naturally adapted to many real-world applications. This has also been discussed in the apper.", "weaknesses": "(1) It seems that there is one paper that does the same thing [1]. I think this paper should at least be discussed in the paper.\n(2) I was wondering why some models in Table 2 and Table 2 are not present in Table 4 and Table 5, such as PNA, DGANN.\n(3) Will the choice of the root node affect the final results? \n\n[1] Dong et al., PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphs. 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for the constructive comments!** \n\n\nWe indeed missed the PACE paper, please see the global reply for a detailed discussion and experimental results. Overall, the comparison to this transformer tailored to DAGs highlights the effectiveness of our simpler and more general proposal: PACE is already outperformed by vanilla Transformer+DAG. \n\nWe also clarified the below points in the paper.\n\n**Q2 Choice of Baselines**\n\nSince we used well-known datasets, we mostly resorted to the models usually reported with those, or in other DAG-specific papers. We did not run those by ourselves, but are happy to add some if you have recommendations. DAGNN specifically is hard to be run - if it runs at all - on the larger datasets since it is very expensive (e.g., it takes days for the ogbg-code2 experiments). This is also why we (and also the PACE paper) put such emphasis onto efficiency.\n   \n**Q3 Root Nodes are Given**\n\nThe term \"root node\" refers to the source nodes, i.e., nodes without predecessors. These are fixed, that is, they are given with the datset and do not represent architecture choices or parameters. Hence they do not affect the results."}, {"review_id": "EJ117s5XmU", "reviewer": "Reviewer_WzDZ", "summary": "This paper adapts transformers to directed acyclic graphs. It restricts the receptive field of each node to its predecessor and successor nodes so that it faithfully captures the DAG structure. It also incorporates positional encodings based on the node depth. Extensive experiments show that it can improve performance of different kinds of baseline transformers.", "questions": "1. The authors mentioned that they used the same hyperparameters as baseline transformers. Does this include learning rate, weight decay and dropout? If so, one only needs to integrate the proposed module without searching any hyperparameters (as long as $k$ is large enough) and can immediately facilitate an enhancement in performance.\n2. See weakness 1.\n", "limitations": "Most limitations have been addressed. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is efficient and versatile. It can improve performance of a broad spectrum of transformers.\n2. The problem of adapting transformers to DAGs is under-explored.\n3. The analysis and experimental results regarding $k$ is surprising and inspiring.", "weaknesses": "1. The datasets used in this paper are rather small. As efficiency and versatility are two key advantages claimed by the paper, can the authors include experimental results on larger graphs, like ogbn datasets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for the thoughtful comments!**\n\nThese are interesting points that highlight our contibution, and we included them into the paper.\n\n**Q1 No Hyperparameter Tuning**\n\nWe indeed used the same hyperparameters as the baseline transformers, which include learning rate, weight decay, and dropout. Extensive experiments showed that integrating our proposed module without the need for hyperparameter search can lead to an immediate improvement in performance, and hence considerably ease usability.\n\n**Q2 Larger Datasets**\n\nSo far, we focused on datasets which were considered with models tailored to DAGs or transformers in the past. Due to the limited time in the rebuttal period, we report only some numbers here, but we will conduct further experiments and also consider other transformers.\n\n**ogbn-arxiv, Citation Data.** We removed a small number of cyclic citation links to create DAGs, used the official splits, averaged over 5 runs, and compared vanilla Transformer to similarly proven GNNs. The results demonstrate that we can adapt the transformers to large graphs and achieve competitive results. \n\n\n   | Methods    | GCN              | GraphSAGE        | GPRGNN           | Transformer | DAG+Transformer  |\n   | ---------- | ---------------- | ---------------- | ---------------- | ----------- | ---------------- |\n   | ogbn-arxiv | 71.72 $\\pm$ 0.45 | 71.46 $\\pm$ 0.26 | 70.90 $\\pm$ 0.23 | OOM         | 71.53 $\\pm$ 0.34 |\n\n\n**MalNet-Tiny, Function Call Graphs (FCGs)[1].** 5k graphs with max. 5k nodes, originating from benign software or 4 malware types, these 5 types are to be predicted. We use the very same setting as GraphGPS, which employs the Local Degree Profile as the set of node features, and added DAG attention on top of GraphGPS by only modifying the self-attention module, switching it to DAG attention. Note that we did not do any hyperparameter tuning. DAG+GraphGPS achieves a slightly better test accuracy while only requiring 20 seconds per epoch. This confirms the quality and efficiency of DAG attention.\n\n| Model            | Accuracy (%)         | Time(epoch) |\n| ---------------- | -------------------- | ----------- |\n| GraphGPS         | 92.64 $\\pm$ 0.78     | 46s         |\n| **DAG+GraphGPS** | **93.45 $\\pm$ 0.41** | **20s**     |\n\n-----------------------------------\n   [1] Freitas, et al. \"A large-scale database for graph representation learning.\" NeurIPS 2021"}, {"review_id": "ExKiT7xOiu", "reviewer": "Reviewer_xj5i", "summary": "The paper proposes an attention mechanism for directed acyclic graphs. Specifically the reachability to/from nodes is considered for a given node and the unreachable nodes are masked out. The authors use this attention mechanism in existing graph transformers for undirected graphs. Further the paper also proposes a new PE for directed graphs that considers the maximum depth of the node from the root nodes. The method is evaluated over source code and citation datasets and authors show it improves existing transformer performance.", "questions": "1. Regarding limiting the receptive field of the transformer, the method selects nodes up to path length k. But a principle question arises about “How to select k?”. Can the authors comment on a more principled way of selecting k rather than keeping it a heuristic or a dataset dependent parameter?\n2. In table 6, the results for the base transformer model and proposed method without DAGRA are the same in ogbg-code2. Is this because no PE is used and the rest of the architecture remains the same? \n3. Do the authors see any issues in learning with the proposed attention mechanism that is restricted to reachable nodes? For example if the label of a child node depends on sibling nodes but those are not reachable and the transformer used is of single layer. The same issue may arise with more layers etc. if there exists label dependence on non-reachable nodes. This is where the fundamental strength of the transformer lies over GNN that it doesn't need to wait over many layers for the information to be propagated. But with the proposed modification this property is lost. Can the proposed framework be adapted to handle such cases?\n", "limitations": "Limitations of the method have been addressed in the paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. The method achieves state of the art results when induced in transformer architectures on datasets used\n2. Method is claimed to be parallelizable and results in faster training compared to asynchronous methods\n", "weaknesses": "1. Regarding limiting the receptive field of the transformer, the method selects nodes up to path length k. But a principle question arises about “How to select k?”. As of now it seems to be a heuristic or a dataset dependent parameter, which limits the novelty of the work as it is straightforward to apply attention in the top k hop reachable nodes in order to induce some notion of structure in the transformer.\n2. Considering that the method only limits the attention to reachable nodes and uses topological depth as PE in existing methods the novelty and contribution seems limited.\n3. The proposed attention mechanism that is restricted to reachable nodes, may suffer from learning issues when a node label depends on non-reachable nodes. For example if the label of a child node depends on sibling nodes but those are not reachable and the transformer used is of single layer. The same issue may arise with more layers etc. if there exists label dependence on farther non-reachable nodes. This is where the fundamental strength of the transformer lies over GNN that it doesn't need to wait over many layers for the information to be propagated. But with the proposed modification this property is lost.\n\nMissing Citations:\n1. https://proceedings.mlr.press/v162/dong22b.html\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for the constructive comments!**\n\nWe indeed missed to discuss the rather important Q3 in the paper and detail the actual power of our DAG attention in the global reply. There we also add details about the comparison to the reference mentioned. We are sorry for the confusion caused by the missing explanation and hope that our contributions are clearer now.\n\nPlease let us know if there are any questions left! \n\n\n**Q1 Clarification: Receptive Field** \n\nNote that we generally recommend $k=\\infty$ (line 273), which means we consider all nodes related via the reachability relationship. This is a reasonable choice given our theoretical analysis, based on the proven random walks, and has also shown best performance in all our experiments. In fact, observe that our framework distinguishes itself in that it is easy to use, requiring no hyperparameter selection or tuning (see also WzDZ, Q1). \n\n**Q2 Setting over ogbg-code2**\n\nYes, in ogbg-code2, no PE is used, the rest of the architecture remains the same. Similar to the transformer baselines we used, we did not see improvement with PE; see also lines 268-270 in the paper. We hypothesize that this is related to the underlying transformer and also the data, since there is a work using a PE [1], but they consider textual information beyond the graph recommended in the benchmark.\n\n[1] Zügner et al. \"Language-Agnostic Representation Learning of Source Code from Structure and Context.\" ICLR 2020."}]

Author rebuttal:
**We thank all reviewers for the very fair, detailed, and constructive feedback!**

We are sorry for the unnecessary confusion caused by missing **explanation about the power of our DAG attention** and hope that the below details clarify our contribution. Since the scores are borderline overall, we would appreciate if the reviewers consider that. We are happy to provide additional information if needed. 

We also provide a **detailed comparison to a very related paper we missed, but which overall highlights the potential impact** of our work.

------------

**G1 Power of DAG Attention** 

Technically, we restrict the attention to reachable nodes and, in this way, obtain considerable efficiency gains. Yet, our architecture is tailored to the special DAG structure, and we can show that this design offers similar expressivity to regular transformers.

It is important to note that in our framework *all* nodes directly communicate with at least one source node (i.e., node without predecessors) by the DAG structure. This is specifically the case because we set $k=\infty$. Hence, *2 layers are always enough to establish communication beyond any two nodes that have a common source node*. Furthermore, especially DAG classification datasets usually contain DAGs with a single source node (e.g., ogbg-code2 and NA).

For *DAGs with $m$ source nodes we need $2m$ layers for full communication*, if we assume the DAG to be connected. In the latter case, every pair of source nodes has a common successor through which communication can happen. Further, connectedness is a reasonable assumption, otherwise communication is likely not needed in most scenarios. Our empirical results demonstrate that our design likely does not limit expressivity on many, also large datasets.

The source nodes may seem to represent a certain kind of bottlenecks since, essentially, our architecture's bias emphasizes DAG relationships while re-directing the remaining relationships in the regular Transformer's full attention matrix. But Sec. 3.3 shows that the *importance of relationships we model is in line with well-known random walk theory*, and our qualitative performance increases also demonstrate that putting more emphasis on DAG relationships can be beneficial in a variety of use cases.

---------------

**G2 Comparison to PACE [1]** 

As two reviewers noted, we missed a very related transformer architecture tailored to DAGs, PACE, published at ICML 2022. Interestingly, the comparison serves well to highlight our contribution:
- Most importantly, *PACE is one specific model* whereas we propose a framework which can be flexibly used with any transformer.
- Specifically, *PACE uses a more complex PE* and its attention is *based only on the directed transitive closure*. In contrast, we use reachability, which also accounts for data where reverse relationships are critical.
- PACE injectively maps DAGs to sequences of node embeddings and then processes them as a sequence in a masked transformer. The mask restricts the attention, with an intention similar to our restricted attention. Yet, *the model still has the usual quadratic complexity* of transformers, while we propose an implementation based on message passing GNNs that exploits our novel attention to reduce complexity.
- Further, PACE is limited in applicability, as the masked transformer *fails to consider edge attributes* of graphs, while our framework preserves all graph information.
- Our framework's simple design also seems to be more effective empirically: *even in combination with vanilla Transformer, we obtain better results*. Given the simplicity of our model, we especially see considerable efficiency gains.
    |                 | ogbg-code2       |                  |             | self-citation    |                   | Cora               | Citeseer            | Pubmed             |
    | --------------- | ---------------- | ---------------- | ----------- | ---------------- | ----------------- | ------------------ | ------------------- | ------------------ |
    |                 | Valid F1 score   | Test F1 score    | Time(epoch) | AP               | ROC-AUC           | Accuracy           | Accuracy            | Accuracy           |
    | PACE            | 16.3$\pm$0.3     | 17.8$\pm$0.2     | 2410s       | 52.1$\pm$1.8     | 75.9$\pm$0.7      | 79.47$\pm$0.63     | 73.65$\pm$1.23      | OOM                |
    | DAG+Transformer | **17.4$\pm$0.1** | **18.8$\pm$0.2** | **591s**    | **63.8$\pm$0.8** | **82.2$\pm$75.9** | **87.80$\pm$0.53** | **74.42$\pm$0.22** | **89.01$\pm$0.13** |

[1] PACE: A parallelizable computation encoder for directed acyclic graphs, ICML 2022.

------------------------------

**G3 Novelty and Contribution**

We hope that the above details resolve the doubts about our contributions. 
- We propose a simple, easy to use architecture, which tailors any transformer to DAGs.
- It is proven effective over a wide range of well-known benchmarks. 
- In particular, it makes various baseline transformers we tested competitive to or outperform proven neural networks which were designed for DAGs.
- The qualitative performance is complemented by  considerable gains in efficiency, which is impressive for transformers in general but also in comparison to existing DAG architectures, such as DAGNN.

Meta-review: Three of the reviewers scored the paper with a "weak accept." Their reasons were that the proposed approach is interesting, new, and addresses an important problem. They also valued the experimental results as convincing. The three weaknesses listed by the only reviewer who tended towards rejecting the paper were essentially all identical and addressed the reachability of nodes of the method and the choice of k. Due to the more detailed reviews of the other reviewers, I recommend accepting the paper. In case the paper gets accepted, I would ask the authors to incorporate the related work mentioned by the reviewers. In addition, I am aware of prior work https://arxiv.org/abs/2004.02596 that uses the depth of a node in paths (the order of nodes) of a DAG as positional encoding in a transformer, so is conceptionally quite similar to the proposed positional encoding. The focus here is on knowledge graphs and approximate query answering, so different enough application and problem but still methodologically related.
Decision: Accept (poster)