Transformers as Graph-to-Graph Models (2023)

Abstract: We argue that Transformers are essentially graph-to-graph models, with sequences just being a special case. Attention weights are functionally equivalent to graph edges. Our Graph-to-Graph Transformer architecture makes this ability explicit, by inputting graph edges into the attention weight computations and predicting graph edges with attention-like functions, thereby integrating explicit graphs into the latent graphs learned by pretrained Transformers. Adding iterative graph refinement provides a joint embedding of input, output, and latent graphs, allowing non-autoregressive graph prediction to optimise the complete graph without any bespoke pipeline or decoding strategy. Empirical results show that this architecture achieves state-of-the-art accuracies for modelling a variety of linguistic structures, integrating very effectively with the latent linguistic representations learned by pretraining.

## introduction computational linguists have traditionally made extensive use of structured representations to capture the regularities found in natural language. the huge success of transformers @xcite and their pre-trained large language models @xcite @xcite have brought these representations into question, since these models are able to capture even subtle generalisations about language and meaning in an end-to-end sequence-to-sequence model @xcite @xcite . this raises issues for research that still needs to model structured representations, such as work on knowledge graphs, hyperlink graphs, citation graphs, or social networks. in this paper we show that the sequence-tosequence nature of most transformer models is only a superficial characteristic; underlyingly they are in fact modelling complex structured representations. we survey versions of the transformer architecture which integrate explicit structured representations with the latent structured representations of transformers. these models can jointly embed both the explicit structures and the latent structures in a transformer's sequence-of-vectors hidden representation, and can predict explicit structures from this embedding. in the process, we highlight evidence that the latent structures of pretrained transformers already include much information about traditional linguistic structures. these transformer architectures support explicit structures which are general graphs, making them applicable to a wide range of structured representations and their integration with text. the key insight of this line of work is that attention weights and graph structure edges are effectively the same thing. linguistic structures are fundamentally an expression of locality in the interaction between different components of a representation. as @xcite argued, incorporating this information about locality in the inductive bias of a neural network means putting connections between hidden vectors if their associated components are local in the structure. in transformers @xcite , these connections are learned in the form of attention weights. thus, these attention weights are effectively the induced structure of the transformer's latent representation. however, attention weights are not explicitly part of a transformer's hidden representation. the output of a transformer encoder is a sequence of vectors, and the same is true of each lower layer of self-attention. the latent attention weights are extracted from these sequence-of-vector embeddings with learned functions of pairs of vectors. edges in explicit graphs can be predicted in the same way (from pairs of vectors), assuming that these graphs have also been embedded in the sequence of vectors. in recent years, the main innovation has been in how to embed explicit graphs in the hidden representations of transformers. in our work on this topic, we follow the above insight and input the edges of the graph into the computation of attention weights. attention weights are computed from an n × n matrix of attention scores (where n is the sequence length), so we input the label of the edge between nodes i and j into the score computation for the i,j cell of this matrix. each edge label has a learned embedding vector, which is input to the attention score function in various ways depending on the architecture. this allows the transformer to integrate the explicit graph into its own latent attention graph in flexible and powerful ways. this integrated attention graph can then determine the transformer's sequence-of-vectors embedding in the same way as standard transformers. researchers from the natural language understanding group at idiap research institute have developed this architecture for inputting and predicting graphs under the name of graph-to-graph transformer (g2gt). g2gt allows conditioning on an observed graph and predicting a target graph. for the case where a graph is only observed at training time, we not only want to predict its edges, we also want to integrate the predicted graph into the transformer embedding. this has a number of advantages, most notably the ability to jointly model all the edges of the graph. by iteratively refining the previous predicted graph, g2gt can jointly model the entire predicted graph even though the actual prediction is done independently for each edge. and this joint modelling can be done in conjunction with other explicit graphs, as well as with the transformer's induced latent graph. our work on g2g transformer has included a number of different explicit graph structures. the original methods were developed on syntactic parsing @xcite . the range of architectures was further explored for semantic role labelling @xcite and collocation recognition (espinosa anke et al., 2022). g2gt's application to coreference resolution extended the complexity of graphs to two levels of representation (mention spans and coreference chains) over an entire document, which was all modelled with iterative refinement of a single graph @xcite . current work on knowledge extraction poses further challenges, most notably the issue of tractably modelling large graphs. the code for g2gt is open-source and available for other groups to use for other graph structures (at https://github.com/idiap/g2g-transformer ). in the rest of this paper, we start with a review of related work on deep learning for graph modelling (section 2). we then present the general g2gt architecture with iterative refinement (section 3), before discussing the specific versions we have evaluated on specific tasks (section 4). we then discuss the broader implications of these results (section 5), and conclude with a discussion of future work (section 6). graph transformers. transformers @xcite , initially designed for sequence tasks, represent a viable and versatile alternative to gnns due to their intrinsic graph processing capabilities. through their self-attention mechanism, they can seamlessly capture global wide-ranging relationships, akin to handling a fully-connected graph. @xcite explicitly input relative position relations as embeddings into the attention function, thereby effectively inputting the relative position graph, instead of absolute position embeddings, to represent the sequence. generalising this explicit input strategy to arbitrary graphs @xcite has led to a general class of models which we will refer to as graph transformers (gt). ## graph-to-graph transformer architecture our graph-to-graph transformer (g2gt) architecture combines the idea of inputting graph edges into the self-attention function with the idea of predicting graph edges with an attention-like function. by encoding the graph relations into the self-attention mechanism of transformers, the model has an appropriate linguistic bias, without imposing hard restrictions. specifically, g2gt modifies the attention mechanism of transformers @xcite to input any graph. given the input sequence @xmath0,x 2 ,...,x n ), and graph relations @xmath1,x j ,l),1 ≤ i,@xmath2,@xmath3, the modified self-attention mechanism is calculated as foot_0 : to extract the explicit graph from the sequence of vectors output by the transformer, a classification module is applied to pairs of vectors and maps them into the label space l. initially, the module transforms each vector into distinct head and tail representations using dedicated projection matrices. subsequently, a classifier (linear, bilinear or mlp) is applied, to map the vector pair onto predictions over the label space. notably, each edge prediction can be computed in parallel (i.e. in a non-autoregressive manner), as predictions for each pair are independent of one another. given the discrete nature of the output, various decoding methods can be employed to impose desired constraints on the complete output graph. these can range from straightforward head-tail order constraints, to more complex decoding algorithms such as the minimum spanning tree (mst) algorithm. having an architecture which can both condition on graphs and predict graphs gives us the powerful ability to do iterative refinement of arbitrary graphs. even when graph prediction is non-autoregressive, conditioning on the previously predicted graph allows the model to capture between-edge correlations like an autoregressive model. as illustrated in figure 1 , we propose recursive non-autoregressive g2gt (rngt), et al. (2022) provide a survey of previous proposals for relative position encoding. in ongoing work, we have found that using a relation embedding vector to reweight the dimensions in standard dot-product attention works well for some applications. ## g2gt models and results this section provides a more comprehensive explanation of each alternative g2gt model we have ex-plored, along with an outline of how we've applied these models to address various graph modelling problems. the empirical success of these models demonstrate the computational adequacy of transformers for extracting and modelling graph structures which are central to the nature of language. the large further improvements gained by initialising with pretrained models demonstrates that transformer pretraining encodes information about linguistic structures in its attention mechanisms. ## discussion the empirical success of graph-to-graph transformers on modelling these various graph structures helps us understand how transformers model language. this success demonstrates that transformers are computationally adequate for modelling linguistic structures, which are central to the nature of language. the reliance of these g2gt models on using self-attention mechanisms to extract and encode these graph relations shows that self-attention is crucial to how transformers can do this modelling. the large improvements gained by initialising with pretrained models indicates that pretrained transformers are in fact using the same mechanisms to learn about this linguistic structure, but in an unsupervised fashion. these insights into pretrained transformers give us a better understanding of the current generation of large language models (llms). it is not that these models do not need linguistic structure (since their attention mechanisms do learn it); it is that these models do not need supervised learning of linguistic structure. but perhaps in a @xcite , † significant at @xmath4.05 compared to @xcite . ## conclusion and future work the graph-to-graph transformer architecture makes explicit the implicit graph processing abilities of transformers, but further research is needed to fully leverage the potential of g2gt.