Transformers Meet Directed Graphs
Transformers were originally proposed as a sequence-to-sequence model for text but have become vital for a wide range of modalities, including images, audio, video, and undirected graphs. However, transformers for directed graphs are a surprisingly underexplored topic, despite their applicability to ubiquitous domains, including source code and logic circuits. In this work, we propose two direction- and structure-aware positional encodings for directed graphs: (1) the eigenvectors of the Magnetic Laplacian - a direction-aware generalization of the combinatorial Laplacian; (2) directional random walk encodings. Empirically, we show that the extra directionality information is useful in various downstream tasks, including correctness testing of sorting networks and source code understanding. Together with a data-flow-centric graph construction, our model outperforms the prior state of the art on the Open Graph Benchmark Code2 relatively by 14.7%.
Code (1)
Tasks
graph constructionGraph Property PredictionSimilar Papers 제목 키워드 기반
Transformers over Directed Acyclic Graphs
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 q…
Graph Property PredictionGraph Representation LearningRepresentation LearningTransformers Can Learn Connectivity in Some Graphs but Not Others
Reasoning capability is essential to ensure the factual correctness of the responses of transformer-based Large Language Models (LLMs), and robust reasoning about transitive relations is instrumental in many settings, su…
Causal InferenceState Space Models over Directed Graphs
Directed graphs are ubiquitous across numerous domains, where the directionality of edges encodes critical causal dependencies. However, existing GNNs and graph Transformers tailored for directed graphs face two major ch…
Graph Neural NetworkGraph LearningWhat Are Good Positional Encodings for Directed Graphs?
Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, as they effectively capture the relative spatial relationships between nodes. Although extensive…
On Searching for Minimal Integer Representation of Undirected Graphs
Minimal and efficient graph representations are key to store, communicate, and sample the search space of graphs and networks while meeting user-defined criteria. In this paper, we investigate the feasibility of gradient…