Transformers over Directed Acyclic Graphs
This work addresses the challenge of incorporating structural bias into transformers for DAGs, which is incremental as it builds on existing graph transformer research.
The paper tackled the problem of adapting transformer models for directed acyclic graphs (DAGs) by proposing an efficient attention mechanism and positional encoding, resulting in improved performance over graph neural networks and state-of-the-art graph transformers in tasks like classifying source code graphs and citation networks.
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.