Transformers Meet Directed Graphs

Simon GeislerYujia LiDaniel J. MankowitzAli Taylan CemgilStephan GünnemannCosmin Paduraru

article2023ICML51 citations

Develops direction-aware positional encodings using Magnetic Laplacian eigenvectors and directional random walks to extend Transformers to directed graphs, significantly improving performance on source code understanding and sorting network verification.

Listen

Modern machine learning relies heavily on transformer models for complex reasoning tasks across text, images, and network data. However, existing graph transformers almost exclusively target undirected networks. When applied to directed systems—such as software source code, logical circuits, or execution workflows—current approaches either enforce artificial sequence orderings or strip away directionality through graph symmetrization. These compromises create serious vulnerabilities: linear sequences introduce vast spaces of arbitrary statement orderings, while ignoring edge directions destroys critical semantic meaning and makes models susceptible to harmless code permutations.

The article demonstrates that incorporating explicit directionality and structure-aware positional encodings into transformers substantially improves their predictive accuracy and robustness. The primary objective is to evaluate two direction-aware encoding strategies—one based on the spectral eigenvectors of the Magnetic Laplacian and another based on directional random walks—alongside a novel data-flow graph representation that eliminates artificial sequential dependencies.

The authors evaluated their approach across three benchmark domains: synthetic network distance and reachability tasks, a logic-based algorithmic correctness task involving sorting networks across varying sequence lengths, and large-scale semantic code understanding using the Open Graph Benchmark Code2 dataset comprising 450,000 Python functions. The baseline comparisons included standard sequential transformers, direction-unaware graph neural networks, and prevailing state-of-the-art structure-aware models.

The analysis produced several key findings. First, directional encodings based on the Magnetic Laplacian consistently outperformed standard undirected spectral methods across all direction-dependent benchmarks, reducing distance regression error by up to fourfold compared to singular value decomposition alternatives. Second, on the sorting network correctness task, direction-aware models generalized effectively to longer, out-of-distribution execution lengths, whereas sequence-based sinusoidal models degraded as input lengths grew. Third, combining Magnetic Laplacian encodings with a data-flow graph representation established a new state of the art on the Open Graph Benchmark Code2 dataset, delivering an F1 score improvement of 2.85 points—a 14.7% relative improvement over the prior leading baseline. Finally, the data-flow representation successfully collapsed thousands of semantically equivalent code permutations into unified graph representations, neutralizing vulnerabilities to meaningless statement reorderings.

These results demonstrate that preserving edge directionality provides significant operational advantages for software analysis, combinatorial optimization, and automated code verification. Modeling systems through data-flow directed graphs drastically shrinks the effective input search space, reducing error rates and enhancing system reliability without requiring large parameter expansions. The findings show that direction-aware encodings supply complementary structural information that enhances both pure transformer architectures and hybrid graph neural networks.

Organizations developing machine learning models for source code analysis, static program verification, or dependency workflows should transition from purely sequential or undirected graph representations to directed data-flow representations paired with direction-aware encodings. Implementation teams should choose Magnetic Laplacian encodings when global structural awareness and out-of-distribution generalization are critical, while applying directional random walks for tasks dominated by localized graph neighborhoods.

Readers should note certain limitations: the graph construction relies on static code analysis, which approximates runtime behavior on a best-effort basis and does not capture dynamic execution effects or functions with non-isolated side effects. Additionally, while the methods scale efficiently with precomputation, standard self-attention retains quadratic computational complexity relative to graph size unless paired with sparse attention mechanisms. Confidence in the empirical gains remains high, as demonstrated across controlled synthetic benchmarks and large-scale code datasets.

Department of Computer Science Google Technical University of Munich audio eigenvectors encoder-decoder structure-aware transformers directional random walk encodings Laplacian positional encodings

google-deepmind/digraph_transformer Geisler et al (2023).pdf

Paper: GraphCodeBERT: Pre-training Code Representations with Data Flow, Daya Guo et al. (2020). GraphCodeBERT introduces the data-flow representation for code that this paper adapts to directed graph transformers, clarifying the source of its code-structure approach.
Paper: Do Transformers Really Perform Badly for Graph Representation?, Chengxuan Ying et al. (2021). Graphormer establishes how structural encodings can equip transformers for graph learning, providing a direct baseline for understanding this paper’s direction-aware encodings.
Paper: Recipe for a General, Powerful, Scalable Graph Transformer, Ladislav Rampásek et al. (2022). GPS sets out a general graph-transformer framework with structural and positional encodings, helping situate this paper’s directed encodings within graph-transformer design.
Paper: Spectral Networks and Locally Connected Networks on Graphs, Joan Bruna et al. (2014). This work introduces spectral graph methods built on the graph Laplacian, providing useful mathematical grounding for the paper’s Magnetic Laplacian positional encodings.

No sufficiently relevant recommendations were found.

Cover for Transformers Meet Directed Graphs

Abstract

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%.

Topics

audio eigenvectors encoder-decoder graph construction random walk source codes weighted graph bipartite graphs connected graph digraph

Keywords

structure-aware transformers directional random walk encodings Laplacian positional encodings Magnetic eigenmaps edge directionality graph Fourier transformation graph signal processing data-flow graph topological sorts

1. Introduction
2. Sinusoidal and Laplacian Encodings
3. Directional Spectral Encodings
4. Directional Random Walks
5. Positional Encodings Playground
6. Application: Sorting Networks
7. Application: Function Name Prediction
8. Related Work
9. Conclusion
Acknowledgements
References
A. Example Graphs
B. Graph Fourier Transformation
C. Laplacians for Directed Graphs
D. Magnetic Laplacian
D.1. Influence of Potential q
D.2. Sign, Scale and Rotation
D.3. Reorder Permuted Graphs
D.4. Comparison to Singular Value Decomposition
E. Weighted Graphs
F. Overview of Our Positional Encodings
G. Experimental Setup
H. Scalability
I. Positional Encodings Playground
J. Random Walk Hyperparameter Study
K. Sorting Networks Dataset Construction
L. Sorting Networks Are Near-Sequential
M. Application: Function Name Prediction

Knowls

Knowl 1 — Magnetic Laplacian encodes directed edges through complex phase
model/method
For a directed graph with adjacency matrix $A\in\{0,1\}^{n\times n}$ , define the symmetrized adjacency $A_s=A\vee A^\top$ and its diagonal degree matrix $D_s$ . For an edge from node $u$ to node $v$ , let $\Theta^{(q)}_{u,v}=2\pi q(A_{u,v}-A_{v,u})$ , where $q\geq 0$ is a potential and $i=\sqrt{-1}$ . The Magnetic Laplacian is
$L_U^{(q)}=D_s-A_s\odot\exp(i\Theta^{(q)}),$
where $\odot$ and the exponential act elementwise. This matrix is Hermitian, so its eigenvectors are complex and form an orthogonal basis. When $q=0$ , it is the combinatorial Laplacian; for an undirected graph, it equals the combinatorial Laplacian for any finite $q$ . A one-way edge contributes a signed phase offset, while a bidirectional edge contributes no offset. Thus, the eigenvectors preserve directional information that symmetrizing a graph for the ordinary Laplacian would discard.

In the experiments, the degree-normalized form was used:
$L_N^{(q)}=I-(D_s^{-1/2}A_sD_s^{-1/2})\odot\exp(i\Theta^{(q)}).$
The potential was scaled per graph as $q=q'/d_G$ , with $d_G=\max(\min(\vec m,n),1)$ and $\vec m$ the number of one-way edges. Relative potentials $q'\in\{0.1,0.25\}$ were typical; excessively large potentials degraded performance.
Knowl 2 — Bidirectional random-walk positional encodings
model/method
For a directed graph with adjacency $A$ , the paper constructs node positional encodings from random-walk landing probabilities in both directions. Using the paper's transition-matrix convention, the forward and reverse transitions are $T=AD_{\mathrm{out}}^{-1}$ and $R=A^\top D_{\mathrm{in}}^{-1}$ , where $D_{\mathrm{out}}$ and $D_{\mathrm{in}}$ are diagonal out-degree and in-degree matrices. Self-loops are added to nodes with zero degree for the corresponding transition, preventing probability mass from disappearing at dangling nodes.

For nodes $u,v$ and a walk horizon $k$ , the pairwise feature contains the reverse and forward landing probabilities at each step:
$\zeta(v\mid u)=f_{\mathrm{rw}}^{(2)}\big[(R^k)_{v,u},\ldots,R_{v,u},T_{v,u},\ldots,(T^k)_{v,u}\big].$
Here $f_{\mathrm{rw}}^{(2)}$ is an MLP. The node-level encoding sums these pairwise embeddings over all starting nodes and transforms the sum with another MLP: $\zeta(v\mid G)=f_{\mathrm{rw}}^{(1)}\big(\sum_{u\in V}\zeta(v\mid u)\big)$ . To supply global information beyond a finite walk horizon, the pairwise features can also include forward and reverse personalized PageRank landing probabilities, with restart probability $p_r$ and $\Pi(T)=p_r(I-(1-p_r)T)^{-1}$ (and analogously for $R$ ). Finite-step walks are most useful for short-range structure; PageRank supplies longer-range information.
Knowl 3 — Data-flow graph construction for source-code functions
model/method
For function-name prediction, the paper replaces a graph representation that preserves statement order with a directed, data-flow-centric graph. It starts from the function's abstract syntax tree (AST), then adds edges that represent computational and control dependencies rather than connecting statements merely because they are adjacent in the source. Conceptually, it builds a dependency DAG within each code block and links blocks through control flow; constructs such as branches, loops, and exceptions are handled through static code analysis, so the overall graph need not be acyclic.

Edges connect computations to required inputs and represent control flow, prior writes to variables, and values from which variables were computed. Function-call relationships are also represented. For commutative Python operations, edge features avoid encoding an arbitrary operand order; noncommutative operations retain input-order information. The construction omits sequential source-token connections and unnecessary last-read edges, and masks the function name in its definition and recursive calls to prevent label leakage. This representation maps some distinct statement orderings to the same graph when the reordering preserves the computation.

Knowl 4 — Function-name prediction results on OGB Code2

data/table

On OGB Code2, the target is function-name prediction and performance is measured by F1 score. The table reports the test and validation F1 scores for sequential and data-flow graph representations, with AST-depth, random-walk, or Magnetic-Laplacian positional encodings and with or without a GNN. The reported values are averages over 10 reruns, with the error of the mean shown. In the hybrid transformer–GNN setting, changing to the proposed data-flow graph consistently improved the scores, and adding Magnetic-Laplacian encodings achieved the best result: test F1 22.22, versus 19.37 for the prior SAT result, an absolute gain of 2.85 points (14.7% relative).

Graph representation	Positional encoding	GNN	Test F1	Validation F1
Sequential	AST depth	No	$16.70\pm0.05$	$15.46\pm0.06$
Sequential	AST depth	Yes	$19.37\pm0.09$	$17.73\pm0.07$
Prior result (as reported)	–	No	$19.09\pm0.10$	$17.68\pm0.06$
Proposed baseline	–	Yes	$21.03\pm0.07$	$19.38\pm0.07$
Data-flow	AST depth	Yes	$21.61\pm0.12$	$19.79\pm0.11$
Data-flow	Random walk	No	$19.34\pm0.08$	$17.96\pm0.05$
Data-flow	Random walk	Yes	$21.82\pm0.20$	$20.03\pm0.17$
Data-flow	Magnetic Laplacian	No	$19.43\pm0.03$	$17.83\pm0.05$
Data-flow	Magnetic Laplacian	Yes	$22.22\pm0.10$	$20.44\pm0.06$

Knowl 5 — Sorting networks as directed dependency graphs
model/method
A sorting network on $p$ inputs is a sequence of comparison-exchange operations, each comparing a pair of input indices $(i,j)$ . The paper represents each comparator as a graph node, with its two indices as node features. For each index used by a comparator, it adds a directed edge from the previous comparator that used that index, if one exists. The resulting data-flow graph records which operations depend on earlier operations.

Any topological ordering of this graph corresponds to a reordered comparator program with the same effect, so the graph represents many semantically equivalent sequences without choosing one arbitrary ordering. The number of such orderings can be very large: for the compact Batcher even-odd mergesort networks studied, it exceeds one million at sequence length $p=8$ . Direction is essential: the correct length-three network with comparators $[(0,2),(0,1),(1,2)]$ and its reversed, incorrect version produce the same undirected graph. A model using only the symmetrized graph therefore cannot distinguish these cases.
Knowl 6 — Sorting-network correctness generalization
empirical result
The sorting-network task tests whether a model can predict if a comparator sequence correctly sorts all inputs. The dataset contains 800,000 training examples with sequence lengths sampled from $7$ through $11$ , validation examples of length $12$ , and test examples of lengths $13$ through $16$ . Training data are balanced between correct networks and incorrect networks made by omitting the final comparator. Validation and test data contain one-third correct networks and two-thirds incorrect networks; the latter include reversed correct sequences, making evaluation more challenging and somewhat out of distribution.

On lengths $13$ – $16$ , transformer encoders with Magnetic-Laplacian or bidirectional random-walk encodings performed comparably and substantially better than the other tested positional encodings. The ordinary combinatorial-Laplacian encodings barely exceeded a prior-based random classifier, and sinusoidal sequence encodings did not generalize well to longer lengths. Direction also helped a message-passing GNN: a direction-aware GNN performed comparably to the Magnetic-Laplacian transformer at length $13$ , but generalized somewhat worse at longer lengths. Magnetic-Laplacian encodings improved GNN generalization, whereas random-walk encodings harmed it in this setting.

Knowl 7 — Predicting graph distances and reachability with positional encodings

data/table

The positional-encoding comparison evaluates pairwise reachability and adjacency classification (F1; higher is better) and undirected and directed shortest-path-distance regression (RMSE; lower is better). It uses directed acyclic graphs and general directed Erdős–Rényi graphs, extracting the largest weakly connected component. Graph sizes are held out by split: for classification, training, validation, and test sizes are 16–17, 18–19, and 20–27 nodes; for regression they are 16–63, 64–71, and 72–83 nodes. Each node count has 400,000 training examples and 2,500 validation and test examples, and results average three reruns.

The Magnetic-Laplacian encodings are strong on directed tasks in both graph families. On general directed graphs they attain test F1 $1.00$ for reachability and adjacency and test RMSE $0.31$ for directed distance, compared with the ordinary Laplacian's $0.73$ , $0.49$ , and $2.08$ , respectively. Random-walk encodings are competitive for classification but less accurate for distance regression. The SVD baseline is strong on DAGs but less effective on general directed graphs.

Graph family	Encoding	Reachability F1 (val/test)	Adjacency F1 (val/test)	Undirected RMSE (val/test)	Directed RMSE (val/test)
DAG	Laplacian	$0.63/0.53$	$0.63/0.53$	$0.23/0.26$	$0.51/0.54$
DAG	SVD	$1.00/1.00$	$1.00/1.00$	$0.83/0.97$	$0.38/0.45$
DAG	Magnetic Laplacian	$1.00/1.00$	$1.00/1.00$	$0.22/0.25$	$0.33/0.38$
DAG	Random walk	$0.97/0.95$	$0.97/0.95$	$1.22/1.33$	$0.65/0.68$
General directed	Laplacian	$0.75/0.73$	$0.62/0.49$	$0.27/0.31$	$1.96/2.08$
General directed	SVD	$1.00/0.97$	$1.00/1.00$	$1.02/1.12$	$1.64/1.86$
General directed	Magnetic Laplacian	$1.00/1.00$	$1.00/1.00$	$0.27/0.31$	$0.93/1.06$
General directed	Random walk	$1.00/0.99$	$0.97/0.94$	$1.00/1.06$	$1.24/1.36$

Knowl 8 — Processing Magnetic-Laplacian eigenvectors for a transformer
model/method
The proposed spectral transformer uses the $k$ eigenvectors associated with the smallest eigenvalues of the degree-normalized Magnetic Laplacian; the experiments typically use $k=25$ . It stacks the real and imaginary components of each complex eigenvector and feeds the result to a positional-encoding network. The network applies LayerNorm, dropout, and self-attention independently at each graph node across that node's $k$ eigenvector embeddings. It then combines the per-node outputs and uses an MLP to match the transformer feature dimension.

Eigenvectors are normalized to remove arbitrary scale, their signs are fixed by requiring a maximum-magnitude real component to be positive, and their rotation is fixed relative to an available task-specific root node. If no such root is supplied, the method uses a source node selected from the phase of the first eigenvector. In the transformer experiments, processing eigenvectors without a sign-invariant SignNet gave better results than the tested SignNet with an elementwise MLP; for the Code2 hybrid model, SignNet with a GNN was used in the best-performing configuration.
Knowl 9 — Laplacian eigenvectors are cosine encodings on a sequence
definition
For a sequence represented as an undirected path graph with $n$ nodes, a valid set of eigenvectors of the combinatorial Laplacian has entries $\Gamma_{v,j}=\pm\cos((v+1/2)j\pi/n)$ , where $v\in\{0,\ldots,n-1\}$ indexes sequence positions and $j$ indexes the eigenvector mode. The sign is chosen consistently for each mode, but an eigenvector and its negative are both valid. This is the type-II discrete cosine transform, making Laplacian eigenvectors a graph counterpart to familiar sinusoidal or Fourier positional encodings.

Unlike position-anchored sinusoidal encodings, the arbitrary sign of a Laplacian eigenvector can make the first and last nodes indistinguishable in this representation. More generally, the ordinary combinatorial Laplacian is built from a symmetrized graph and therefore does not encode edge direction; the Magnetic Laplacian extends this spectral construction with complex phases.
Knowl 10 — Assumptions and limitations of source-code graph invariance
limitation
The source-code graph construction is intended to identify reorderings that should preserve labels for high-level tasks such as function-name prediction or correctness prediction. That invariance is task-dependent: statement reorderings can change runtime, and the paper assumes that non-class-member methods are side-effect-free for its intended reasoning tasks. Its lexicographical static analysis is best-effort and does not capture every dynamic runtime effect.

The constructed data and control dependencies also do not encode every condition needed to reconstruct a valid sequential program; for example, overwriting a variable can affect whether two blocks may be reordered. The authors regard such omitted dependencies as unnecessary for the semantic prediction target, while noting that the graph may merge more semantically equivalent programs than a graph encoding every execution dependency. Separately, eigenvector-based positional encodings are not generally permutation equivariant when eigenvalues are repeated, because eigensolvers may select different bases within the repeated-eigenvalue subspace.

Coverage note — The paper's auxiliary runtime benchmark for eigendecomposition and extended random-walk ablations are omitted because they support implementation choices but are less central than the proposed encodings, graph constructions, and downstream results.

References

1.Allamanis, M., Brockschmidt, M., and Khademi, M. Learning to Represent Programs with Graphs. In International Conference on Learning Representations, ICLR, 2018.
2.Bandeira, A. S., Singer, A., and Spielman, D. A. A Cheeger Inequality for the Graph Connection Laplacian. SIAM J. Matrix Anal. Appl., 2013.
3.Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Song, F., Ballard, A., Gilmer, J., Dahl, G., Vaswani, A., Allen, K., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M., Vinyals, O., Li, Y., and Pascanu, R. Relational inductive biases, deep learning, and graph networks, In arXiv, 2018.
4.Belkin, M. and Niyogi, P. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 2003.
5.Bieber, D., Shi, K., Maniatis, P., Sutton, C., Hellendoorn, V., Johnson, D., and Tarlow, D. A Library for Representing Python Programs as Graphs for Machine Learning, In arXiv, 2022.
6.Bojchevski, A., Klicpera, J., Perozzi, B., Kapoor, A., Blais, M., Rózemberczki, B., Lukasik, M., and Günnemann, S. Scaling Graph Neural Networks with Approximate PageRank. International Conference on Knowledge Discovery and Data Mining, KDD, 2020.
7.Brock, A., De, S., Smith, S. L., and Simonyan, K. High-Performance Large-Scale Image Recognition Without Normalization. In International Conference on Machine Learning, ICML, 2021.
8.Bronstein, M. M., Bruna, J., Cohen, T., and Velickovic, P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges, In arXiv, 2021.
9.Chen, D., O’Bray, L., and Borgwardt, K. Structure-Aware Transformer for Graph Representation Learning. International Conference on Machine Learning, ICML, 2022.
10.Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W. Evaluating Large Language Models Trained on Code, In arXiv, 2021.
11.Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking Attention with Performers. In International Conference on Learning Representations, ICLR, 2020.
12.Cummins, C., Fisches, Z. V., Ben-Nun, T., Hoefler, T., and Leather, H. ProGraML: Graph-based Deep Learning for Program Optimization and Analysis, In arXiv, 2020.
13.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Neural Information Processing Systems, NeurIPS, 2017.
14.Diao, C. and Loynd, R. Relational Attention: Generalizing Transformers for Graph-Structured Tasks, In arXiv, 2022.
15.Dwivedi, V. P. and Bresson, X. A Generalization of Transformer Networks to Graphs. Deep Learning on Graphs at AAAI Conference on Artificial Intelligence, 2021.
16.Fanuel, M., Alaíz, C. M., and Suykens, J. A. K. Magnetic eigenmaps for community detection in directed networks, In arXiv, 2016.
17.Fanuel, M., Alaíz, C. M., Fernández, , and Suykens, J. A. K. Magnetic Eigenmaps for the visualization of directed networks. Appl. Comput. Harmon. Anal., 2018.
18.Feng, Z., Guo, D., Tang, D., Duan, N., Feng, X., Gong, M., Shou, L., Qin, B., Liu, T., Jiang, D., and Zhou, M. CodeBERT: A Pre-Trained Model for Programming and Natural Languages. In Findings of the Association for Computational Linguistics: EMNLP, 2020.
19.Furutani, S., Shibahara, T., Akiyama, M., Hato, K., and Aida, M. Graph Signal Processing for Directed Graphs Based on the Hermitian Laplacian. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD, 2020.
20.Geisler, S., Sommer, J., Schuchardt, J., Bojchevski, A., and Günnemann, S. Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness. In International Conference on Learning Representations, ICLR, 2022.
21.Guo, D., Ren, S., Lu, S., Feng, Z., Tang, D., Liu, S., Zhou, L., Duan, N., Svyatkovskiy, A., Fu, S., Tufano, M., Deng, S. K., Clement, C., Drain, D., Sundaresan, N., Yin, J., Jiang, D., and Zhou, M. GraphCodeBERT: Pre-training Code Representations with Data Flow. International Conference on Learning Representations, ICLR, 2021.
22.He, Y., Perlmutter, M., Reinert, G., and Cucuringu, M. MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian. In Learning on Graphs Conference, 2022.
23.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Neural Information Processing Systems, NeurIPS, 2020.
24.Hussain, M. S., Zaki, M. J., and Subramanian, D. Global Self-Attention as a Replacement for Graph Convolution. In International Conference on Knowledge Discovery and Data Mining, KDD, 2022.
25.Jha, A. and Reddy, C. K. CodeAttack: Code-based Adversarial Attacks for Pre-Trained Programming Language Models, In arXiv, 2022.
26.Kim, J., Nguyen, T. D., Min, S., Cho, S., Lee, M., Lee, H., and Hong, S. Pure Transformers are Powerful Graph Learners. In Neural Information Processing Systems, NeurIPS, 2022.
27.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, ICLR, 2017.
28.Kitaev, N., Kaiser, , and Levskaya, A. Reformer: The Efficient Transformer. International Conference on Learning Representations, ICLR, 2020.
29.Knuth, D. E. The art of computer programming, Volume 4, Fascicle 6. Addison-Wesley series in computer science and information processing. Addison-Wesley, Reading, Mass., 1968.
30.Knuth, D. E. The art of computer programming, Volume 3. Addison-Wesley series in computer science and information processing. Addison-Wesley Pub. Co, Reading, Mass, 1973.
31.Kool, W., Hoof, H. v., and Welling, M. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, ICLR, 2019.
32.Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., and Tossou, P. Rethinking Graph Transformers with Spectral Attention. In Neural Information Processing Systems, NeurIPS, 2021.
33.Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Neural Information Processing Systems, NeurIPS, 2020.
34.Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Lago, A. D., Hubert, T., Choy, P., d’Autume, C. d. M., Babuschkin, I., Chen, X., Huang, P.-S., Welbl, J., Gowal, S., Cherepanov, A., Molloy, J., Mankowitz, D. J., Robson, E. S., Kohli, P., de Freitas, N., Kavukcuoglu, K., and Vinyals, O. Competition-Level Code Generation with AlphaCode, In arXiv, 2022.
35.Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and Basis Invariant Networks for Spectral Graph Representation Learning, In arXiv, 2022.
36.Loshchilov, I. and Hutter, F. SGDR: Stochastic gradient descent with warm restarts. International Conference on Learning Representations, ICLR, 2017.
37.Loshchilov, I. and Hutter, F. Decoupled Weight Decay Regularization. International Conference on Learning Representations, ICLR, 2019.
38.Luo, Y. DAGformer: Directed Acyclic Graph Transformer, In arXiv, 2022.
39.Marques, A. G., Segarra, S., and Mateos, G. Signal Processing on Directed Graphs: The Role of Edge Directionality When Processing and Learning From Network Data. IEEE Signal Processing Magazine, 2020.
40.Mialon, G., Chen, D., Selosse, M., and Mairal, J. GraphiT: Encoding Graph Structure in Transformers, In arXiv, 2021.
41.Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., and Rong, Y. Transformer for Graphs: An Overview from Architecture Perspective, In arXiv, 2022.
42.Müller, L., Galkin, M., Morris, C., and Rampášek, L. Attending to Graph Transformers, In arXiv, 2023.
43.OpenAI. ChatGPT: Optimizing Language Models for Dialogue. URL https://openai.com/blog/chatgpt/, 2022.
44.Page, L., Brin, S., Motwani, R., and Winograd, T. The PageRank Citation Ranking : Bringing Order to the Web. In The Web Conference, 1999.
45.Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a General, Powerful, Scalable Graph Transformer. In Neural Information Processing Systems, NeurIPS, 2022.
46.Rossi, E., Charpentier, B., Di Giovanni, F., Frasca, F., Günnemann, S., and Bronstein, M. Edge Directionality Improves Learning on Heterophilic Graphs, In arXiv, 2023.
47.Sandryhaila, A. and Moura, J. M. F. Discrete Signal Processing on Graphs. IEEE Transactions on Signal Processing, 2013.
48.Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., and Dill, D. L. Learning a SAT Solver from Single-Bit Supervision. In International Conference on Learning Representations, ICLR, 2019.
49.Sevi, H., Rilling, G., and Borgnat, P. Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets, In arXiv, 2021.
50.Singh, R., Chakraborty, A., and Manoj, B. S. Graph Fourier Transform based on Directed Laplacian, In arXiv, 2016.
51.Smith, S. W. The scientist and engineer’s guide to digital signal processing. California Technical Pub., San Diego (Calif.), 2nd edition edition, 1999. OCLC: 493473234.
52.Stevanovic, D. Research problems from the Aveiro Workshop on Graph Spectra. Linear Algebra and its Applications, 2007.
53.Strang, G. The Discrete Cosine Transform. SIAM Review, 1999.
54.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, , and Polosukhin, I. Attention is all you need. Neural Information Processing Systems, NeurIPS, 2017.
55.von Luxburg, U. A tutorial on spectral clustering. Statistics and Computing, 2007.
56.Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. In International Conference on Learning Representations, ICLR, 2022.
57.Wu, Q., Zhao, W., Li, Z., Wipf, D., and Yan, J. NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. In Neural Information Processing Systems, NeurIPS, 2022.
58.Yefet, N., Alon, U., and Yahav, E. Adversarial Examples for Models of Code. ACM Program. Lang., 2020.
59.Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do Transformers Really Perform Bad for Graph Representation? Neural Information Processing Systems, NeurIPS, 2021.
60.Zhang, X., He, Y., Brugnone, N., Perlmutter, M., and Hirn, M. MagNet: A Neural Network for Directed Graphs. In Neural Information Processing Systems, NeruIPS, 2021.

Citation

MLA

Geisler, S., et al. “Transformers Meet Directed Graphs”. International Conference on Machine Learning, vol. 202, 2023, pp. 11144–72, https://proceedings.mlr.press/v202/geisler23a.html.

APA

Geisler, S., Li, Y., Mankowitz, D. J., Cemgil, A. T., Günnemann, S., & Paduraru, C. (2023). Transformers Meet Directed Graphs. International Conference on Machine Learning, 202, 11144–11172. https://proceedings.mlr.press/v202/geisler23a.html

Chicago

Geisler, S., Y. Li, D. J. Mankowitz, A. T. Cemgil, S. Günnemann, and C. Paduraru. 2023. “Transformers Meet Directed Graphs”. International Conference on Machine Learning 202: 11144–72. https://proceedings.mlr.press/v202/geisler23a.html.

Harvard

Geisler, S. et al. (2023) “Transformers Meet Directed Graphs”, International Conference on Machine Learning. PMLR, pp. 11144–11172. Available at: https://proceedings.mlr.press/v202/geisler23a.html.

Vancouver

1. Geisler S, Li Y, Mankowitz DJ, Cemgil AT, Günnemann S, Paduraru C (2023) Transformers Meet Directed Graphs. In: International Conference on Machine Learning. PMLR, pp 11144–11172

BibTeX

@InProceedings{pmlr-v202-geisler23a,
  title = 	 {Transformers Meet Directed Graphs},
  author =       {Geisler, Simon and Li, Yujia and Mankowitz, Daniel J and Cemgil, Ali Taylan and G\"{u}nnemann, Stephan and Paduraru, Cosmin},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {11144--11172},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/geisler23a/geisler23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/geisler23a.html},
  abstract = 	 {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%.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Transformers Meet Directed Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Magnetic Laplacian encodes directed edges through complex phase

Knowl 2 — Bidirectional random-walk positional encodings

Knowl 3 — Data-flow graph construction for source-code functions

Knowl 4 — Function-name prediction results on OGB Code2

Knowl 5 — Sorting networks as directed dependency graphs

Knowl 6 — Sorting-network correctness generalization

Knowl 7 — Predicting graph distances and reachability with positional encodings

Knowl 8 — Processing Magnetic-Laplacian eigenvectors for a transformer

Knowl 9 — Laplacian eigenvectors are cosine encodings on a sequence

Knowl 10 — Assumptions and limitations of source-code graph invariance

References

Citation

BibTeX

Source Code

Access the Paper