summaries: The central part of the paper is the design of a learned positional encoding (LPE) that can be used in graph transformers in a similar way the positional encoding is used in text transformers. The authors propose to use eigenvalues and eigenfunctions to encode node positions in a graph, and demonstrate how to incorporate them into a transformer model that achieves high expressivity. The architectural choices are based on the theoretical introduction in which some concepts are borrowed from physics, such as the analogy to electric potential between nodes. The LPE is designed to address five principles that were overlooked by different methods. The authors also implement a new model, Spectral Attention Network (SAN), that utilizes the LPE resulting from the theoretical findings. The experimental results confirm the efficacy of the method. This paper presents an interesting idea on designing a novel graph transformer with learning positional encoding by a spectral attention network (SAN) using the full Laplacian spectrum. Three theoretical limitations from previous efforts are overcome by this spectral attention, namely WL test and universality, over-squashing and physical interactions. Experimental results on four standard datasets demonstrate the effectiveness of the proposed SAN. This paper proposes a learned position encoding mechanism which can fully make use of the eigenvalues and eigenvectors information from the graph Laplacian. The learned position encoding is then concatenated with the embedded node feature. In addition, the edge feature is also served as an input feature in order to completely leverage the graph structural information. Also, by fully connecting the graph, it helps tackle the common over-squashing problem in many GNNs. The paper also proposes an alternative version of attention so that real edges and added edges are taken into account separately when computing the attention. Eventually, the paper empirically tests the performance of the proposed model on real graph datasets. This work proposes a transformer designed for graph structured data. As opposed to GNNs, the transformer allows non-neighboring nodes to communicate. To avoid loosing information on the structure of the graph, the transformer needs some form of structure encoding of the nodes, a non trivial problem for graphs. A common PE scheme consists in using the spectrum of the graphs Laplacian but, as detailed by the authors, this raises some issues. The authors propose an improved positional encoding circumventing these problems and demonstrate that a fully connected transformer is competitive with GNNs on four datasets.
abstractText: In recent years, the Transformer architecture has proven to be very successful in sequence processing, but its application to other data structures, such as graphs, has remained limited due to the difficulty of properly defining positions. Here, we present the Spectral Attention Network (SAN), which uses a learned positional encoding (LPE) that can take advantage of the full Laplacian spectrum to learn the position of each node in a given graph. This LPE is then added to the node features of the graph and passed to a fully-connected Transformer. By leveraging the full spectrum of the Laplacian, our model is theoretically powerful in distinguishing graphs, and can better detect similar sub-structures from their resonance. Further, by fully connecting the graph, the Transformer does not suffer from over-squashing, an information bottleneck of most GNNs, and enables better modeling of physical phenomenons such as heat transfer and electric interaction. When tested empirically on a set of 4 standard datasets, our model performs on par or better than state-of-theart GNNs, and outperforms any attention-based model by a wide margin, becoming the first fully-connected architecture to perform well on graph benchmarks.
authors.name: Devin Kreuzer
authors.name: Dominique Beaini
authors.name: William L. Hamilton
references.authors: Uri Alon Eran Yahav
references.title: On the bottleneck of graph neural networks and its practical implications
references.authors: Dominique Beaini Sofiane Achiche Alexandre Duperré Maxime Raison
references.title: Deep green function convolution for improving saliency in convolutional neural networks
references.venue: The Visual Computer,
references.authors: Dominique Beaini Saro Passaro Vincent Létourneau William L. Hamilton Gabriele Corso Pietro Liò
references.title: Directional graph networks
references.authors: Xavier Bresson Thomas Laurent
references.title: Residual gated graph convnets
references.venue: arXiv preprint arXiv:1711.07553,
references.authors: Michael M. Bronstein Joan Bruna Yann LeCun Arthur Szlam Pierre Vandergheynst
references.title: Geometric deep learning: going beyond euclidean data
references.venue: IEEE Signal Processing Magazine,
references.authors: F. Cajori
references.title: A History of Mathematics
references.venue: AMS Chelsea Publishing Series. AMS Chelsea,
references.authors: Heng Chang Yu Rong Tingyang Xu Wenbing Huang Somayeh Sojoudi Junzhou Huang Wenwu Zhu
references.title: Spectral graph attention
references.authors: Fan Chung S.T. Yau
references.title: Discrete green’s functions
references.venue: Journal of Combinatorial Theory, Series A,
references.authors: Ronald R. Coifman Stéphane Lafon
references.title: Special Issue: Diffusion Maps and Wavelets
references.venue: Diffusion maps. Applied and Computational Harmonic Analysis,
references.authors: Gabriele Corso Luca Cavalleri Dominique Beaini Pietro Liò Petar
references.title: Veličković. Principal neighbourhood aggregation for graph nets
references.venue: arXiv preprint arXiv:2004.05718,
references.authors: Luca Cosmo Mikhail Panine Arianna Rampini Maks Ovsjanikov Michael M. Bronstein Emanuele Rodola
references.title: Isospectralization, or how to hear shape, style, and correspondence
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Yushun Dong Kaize Ding Brian Jalaian Shuiwang Ji Jundong Li
references.title: Graph neural networks with adaptive frequency response
references.venue: filter. CoRR,
references.authors: Vijay Prakash Dwivedi Xavier Bresson
references.title: A generalization of transformer networks to graphs, 2020
references.authors: Vijay Prakash Dwivedi Chaitanya K Joshi Thomas Laurent Yoshua Bengio Xavier Bresson
references.title: Benchmarking graph neural networks
references.venue: arXiv preprint arXiv:2003.00982,
references.authors: Richard Phillips Feynman Robert Benjamin Leighton Matthew Sands
references.title: The Feynman lectures on physics; New millennium ed
references.venue: Basic Books,
references.authors: Justin Gilmer Samuel S Schoenholz Patrick F Riley Oriol Vinyals George E Dahl
references.title: Neural message passing for quantum chemistry
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Will Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In Advances in neural information processing systems,
references.authors: William L. Hamilton
references.title: Graph Representation Learning
references.authors: Sepp Hochreiter Jürgen Schmidhuber
references.title: Long short-term memory
references.venue: Neural computation,
references.authors: Weihua Hu Matthias Fey Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta Jure Leskovec
references.title: Open graph benchmark: Datasets for machine learning on graphs
references.authors: Wengong Jin Regina Barzilay Tommi Jaakkola
references.title: Junction tree variational autoencoder for molecular graph generation
references.authors: Mark Kac
references.title: Can one hear the shape of a drum
references.venue: The American Mathematical Monthly,
references.authors: Anees Kazi Luca Cosmo Nassir Navab Michael Bronstein
references.title: Differentiable graph module (dgm) graph convolutional networks
references.venue: arXiv preprint arXiv:2002.04999,
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: arXiv preprint arXiv:1609.02907,
references.authors: B. Levy
references.title: Laplace-beltrami eigenfunctions towards an algorithm that "understands" geometry
references.venue: In IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06),
references.authors: Pan Li Yanbang Wang Hongwei Wang Jure Leskovec
references.title: Distance encoding: Design provably more powerful neural networks for graph representation learning, 2020
references.authors: Haggai Maron Heli Ben-Hamu Hadar Serviansky Yaron Lipman
references.title: Provably powerful graph networks
references.venue: arXiv preprint arXiv:1905.11136,
references.authors: Christopher Morris Martin Ritzert Matthias Fey William L Hamilton Jan Eric Lenssen Gaurav Rattan Martin Grohe
references.title: Weisfeiler and leman go neural: Higher-order graph neural networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga Adam Lerer
references.title: Automatic differentiation in pytorch
references.authors: Joshua Schrier
references.title: Can one hear the shape of a molecule (from its coulomb matrix eigenvalues)
references.venue: Journal of Chemical Information and Modeling,
references.authors: Yi Tay Mostafa Dehghani Dara Bahri Donald Metzler
references.title: Efficient transformers: A survey, 2020
references.authors: Edwin R. van Dam Willem H. Haemers
references.title: Which graphs are determined by their spectrum
references.venue: Linear Algebra and its Applications,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N. Gomez Lukasz Kaiser Illia Polosukhin
references.title: Attention is all you
references.venue: need. CoRR,
references.authors: Minjie Wang Da Zheng Zihao Ye Quan Gan Mufei Li Xiang Song Jinjing Zhou Chao Ma Lingfan Yu Yu Gai Tianjun Xiao Tong He George Karypis Jinyang Li Zheng Zhang
references.title: Deep graph library: A graph-centric, highly-performant package for graph neural networks
references.venue: arXiv preprint arXiv:1909.01315,
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks
references.venue: arXiv preprint arXiv:1810.00826,
references.authors: Chulhee Yun Srinadh Bhojanapalli Ankit Singh Rawat Sashank J. Reddi Sanjiv Kumar
references.title: Are transformers universal approximators of sequence-to-sequence functions
references.authors: Chulhee Yun Yin-Wen Chang Srinadh Bhojanapalli Ankit Singh Rawat Sashank J. Reddi Sanjiv Kumar
references.title: $o(n)$ connections are expressive enough: Universal approximability of sparse transformers
sections.heading: 1 Introduction
sections.text: The prevailing strategy for graph neural networks (GNNs) has been to directly encode graph structure structure through a sparse message-passing process [17, 19]. In this approach, vector messages are iteratively passed between nodes that are connected in the graph. Multiple instantiations of this message-passing paradigm have been proposed, differing in the architectural details of the message-passing apparatus (see [19] for a review).
  However, there is a growing recognition that the message-passing paradigm has inherent limitations. The expressive power of message passing appears inexorably bounded by the Weisfeiler-Lehman isomorphism hierarchy [29, 30, 39]. Message-passing GNNs are known to suffer from pathologies, such
  ∗Equal contribution.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  as oversmoothing, due to their repeated aggregation of local information [19], and over-squashing, due to the exponential blow-up in computation paths as the model depth increases [1].
  As a result, there is a growing interest in deep learning techniques that encode graph structure as a soft inductive bias, rather than as a hard-coded aspect of message passing [14, 24]. A central issue with message-passing paradigm is that input graph structure is encoded by restricting the structure of the model’s computation graph, inherently limiting its flexibility. This reminds us of how early recurrent neural networks (RNNs) encoded sequential structure via their computation graph—a strategy that leads to well-known pathologies such as the inability to model long-range dependencies [20].
  There is a growing trend across deep learning towards more flexible architectures, which avoid strict and structural inductive biases. Most notably, the exceptionally successful Transformer architecture removes any structural inductive bias by encoding the structure via soft inductive biases, such as positional encodings [36]. In the context of GNNs, the self-attention mechanism of a Transformer can be viewed as passing messages between all nodes, regardless of the input graph connectivity.
  Prior work has proposed to use attention in GNNs in different ways. First, the GAT model [37] proposed local attention on pairs of nodes that allows a learnable convolutional kernel. The GTN work [42] has improved on the GAT for node and link predictions while keeping a similar architecture, while other message-passing approaches have used enhancing spectral features [8, 13] . More recently, the GT model [14] was proposed as a generalization of Transformers to graphs, where they experimented with sparse and full graph attention while providing low-frequency eigenvectors of the Laplacian as positional encodings.
  In this work, we offer a principled investigation of how Transformer architectures can be applied in graph representation learning. Our primary contribution is the development of novel and powerful learnable positional encoding methods, which are rooted in spectral graph theory. Our positional encoding technique — and the resulting spectral attention network (SAN) architecture — addresses key theoretical limitations in prior graph Transformer work [14] and provably exceeds the expressive power of standard message-passing GNNs. We show that full Transformer-style attention provides consistent empirical gains compared to an equivalent sparse message-passing model, and we demonstrate that our SAN architecture is competitive with or exceeding the state-of-the-art on several well-known graph benchmarks. An overview of the entire method is presented in Figure 1, with a link to the code here: https://github.com/DevinKreuzer/SAN.
sections.heading: 2 Theoretical Motivations
sections.text: There can be a significant loss in structural information if naively generalizing Transformers to graphs. To preserve this information as well as local connectivity, previous studies [37, 14] have proposed to use the eigenfunctions of their Laplacian as positional encodings. Taking this idea further by using the full expressivity of eigenfunctions as positional encodings, we can propose a principled way of understanding graph structures using their spectra. The advantages of our methods compared to previous studies [37, 14] are shown in Table 1.
sections.heading: 2.1 Absolute and relative positional encoding with eigenfunctions
sections.text: The notion of positional encodings (PEs) in graphs is not a trivial concept, as there exists no canonical way of ordering nodes or defining axes. In this section, we investigate how eigenfunctions of the Laplacian can be used to define absolute and relative PEs in graphs, to measure physical interactions between nodes, and to enable ”hearing” of specific sub-structures - similar to how the sound of a drum can reveal its structure.
sections.heading: 2.1.1 Eigenvectors equate to sine functions over graphs
sections.text: In the Transformer architecture, a fundamental aspect is the use of sine and cosine functions as PEs for sequences [36]. However, sinusoids cannot be clearly defined for arbitrary graphs, since there is no clear notion of position along an axis. Instead, their equivalent is given by the eigenvectors φ of the graph Laplacian L. Indeed, in a Euclidean space, the Laplacian (or Laplace) operator corresponds to the divergence of the gradient and its eigenfunctions are sine/cosine functions, with the squared frequencies corresponding to the eigenvalues (we sometimes interchange the two notions from here on). Hence, in the graph domain, the eigenvectors of the graph Laplacian are the natural equivalent of sine functions, and this intuition was employed in multiple recent works which use the eigenvectors as PEs for GNNs [15], for directional flows [4] and for Transformers [14].
  Being equivalent to sine functions, we naturally find that the Fourier Transform of a function F [f ] applied to a graph gives F [f ](λi) = 〈f,φi〉, where the eigenvalue is considered as a position in the Fourier domain of that graph [6]. Thus, the eigenvectors are best viewed as vectors positioned on the axis of eigenvalues rather than components of a matrix as illustrated in Figure 2.
sections.heading: 2.1.2 What do eigenfunctions tell us about relative positions?
sections.text: In addition to being the analog of sine functions, the eigenvectors of the Laplacian also hold important information about the physics of a system and can reveal distance metrics. This is not surprising as
  the Laplacian is a fundamental operator in physics and is notably used in Maxwell’s equations [16] and the heat diffusion [6].
  In electromagnetic theory, the (pseudo)inverse of the Laplacian, known in mathematics as the Green’s function of the Laplacian [9], represents the electrostatic potential of a given charge. In a graph, the same concept uses the pseudo-inverse of the LaplacianG and can be computed by its eigenfunctions. See equation 1 , where G(j1, j2) is the electric potential between nodes j1 and j2, φ̂i and λ̂i are the i-th eigenvectors and eigenvalues of the symmetric LaplacianD −1 2 LD −1 2 , andD is the degree
  matrix, and φ̂i,j the j-th row of the vector.
  G(j1, j2) = d 1 2 j1 d −1 2 j2 ∑ i>0 (φ̂i,j1φ̂i,j2) 2 λ̂i (1)
  Further, the original solution of the heat equation given by Fourier relied on a sum of sines/cosines known as a Fourier series [7]. As eigenvectors of the Laplacian are the analogue of these functions in graphs, we find similar solutions. Knowing that heat kernels are correlated to random walks [6, 4], we use the interaction between two heat kernels to define in equation 2 the diffusion distance dD between nodes j1, j2 [6, 10]. Similarly, the biharmonic distance dB was proposed as a better measure of distances [28]. Here we use the eigenfunctions of the regular Laplacian L.
  d2D(j1, j2) = ∑ k>0 e−2tλi(φi,j1 − φi,j2)2 , d2B(j1, j2) = ∑ i>0 (φi,j1 − φi,j2)2 λ2i (2)
  There are a few things to note from these equations. Firstly, they highlight the importance of pairing eigenvectors and their corresponding eigenvalues when supplying information about relative positions in a graph. Secondly, we notice that the product of eigenvectors is proportional to the electrostatic interaction, while the subtraction is proportional to the diffusion and biharmonic distances. Lastly, there is a consistent pattern across all 3 equations: smaller frequencies/eigenvalues are more heavily weighted when determining distances between nodes.
sections.heading: 2.1.3 Hearing the shape of a graph and its sub-structures
sections.text: Another well-known property of eigenvalues is how they can be used to discriminate between different graph structures and sub-structures, as they can be interpreted as the frequencies of resonance of the graph. This led to the famous question about whether we can hear the shape of a drum from its eigenvalues [23], with the same questions also applying to geometric objects [12] and 3D molecules [33]. Various success was found with the eigenfunctions being used for partial functional correspondence [32], algorithmic understanding geometries [26], and style correspondence [12]. Examples of eigenvectors for molecular graphs are presented in Figure 3.
  2.2 Laplace Eigenfunctions etiquette
  In Euclidean space and sequences, using sinusoids as PEs is trivial: we can simply select a set of frequencies, compute the sinusoids, and add or concatenate them to the input embeddings, as is done in the original Transformer [36]. However, in arbitrary graphs, reproducing these steps is not as simple since each graph has a unique set of eigenfunctions. In the following section, we present key principles from spectral graph theory to consider when constructing PEs for graphs, most of which have been overlooked by prior methods. They include normalization, the importance of the eigenvalues and their multiplicities, the number of eigenvectors being variable, and sign ambiguities. Our LPE architectures, presented in section 3, aim to address them.
  Normalization. Given an eigenvalue of the Laplacian, there is an associated eigenspace of dimension greater than 1. To make use of this information in our model, a single eigenvector has to be chosen. In our work, we use the L2 normalization since it is compatible with the definition of the Green’s function (1). Thus, we will always chose eigenvectors φ such that 〈φ,φ〉 = 1. Eigenvalues. Another fundamental aspect is that the eigenvalue associated with each eigenvector supplies valuable information. An ordering of the eigenvectors based on their eigenvalue works in sequences since the frequencies are pre-determined. However, this assumption does not work in graphs since the eigenvalues in their spectrum can vary. For example, in Figure 3, we observe how an ordering would miss the fact that both molecules resonate at λ = 1 in different ways.
  Multiplicities. Another important problem with choosing eigenfunctions is the possibility of a high multiplicity of the eigenvalues, i.e. when an eigenvalue appears as a root of the characteristic polynomial more than once. In this case, the associated eigenspace may have dimension 2 or more as we can generate a valid eigenvector from any linear combination of eigenvectors with the same eigenvalue. This further complicates the problem of choosing eigenvectors for algorithmic computations and highlights the importance of having a model that can handle this ambiguity.
  Variable number of eigenvectors. A graphGi can have at mostNi linearly independent eigenvectors with Ni being its number of nodes. Most importantly, Ni can vary across all Gi in the dataset. Prior work [14] elected to select a fixed number k eigenvectors for each graph, where k ≤ Ni,∀i. This produces a major bottleneck when the smallest graphs have significantly fewer nodes than the largest graphs in the dataset since a very small proportion of eigenvectors will be used for large graphs. This inevitably causes loss of information and motivates the need for a model which constructs fixed PEs of dimension k, where k does not depend on the number of eigenvectors in the graph.
  Sign invariance. As noted earlier, there is a sign ambiguity with the eigenvectors. With the sign of φ being independent of its normalization, we are left with a total of 2k possible combination of signs when choosing k eigenvectors of a graph. Previous work has proposed to do data augmentation by randomly flipping the sign of the eigenvectors [4, 15, 14], and although it can work when k is small, it becomes intractable for large k.
sections.heading: 2.3 Learning with Eigenfunctions
sections.text: Learning generalizable information from eigenfunctions is fundamental to their succesful usage. Here we detail important points that support it is possible to do so if done correctly.
  Similar graphs have similar spectra. Thus, we can expect the network to transfer patterns across graphs through the similarity of their spectra. In fact, spectral graph theory tells us that the lowest and largest non-zero eigenvalues are both linked to the geometry of the graph (algebraic connectivity and spectral radius).
  Eigenspaces contain geometric information. Spectral graph theory has studied the geometric and physical properties of graphs from their Laplacian eigenfunctions in depth. Developing a method that can use the full spectrum of a graph makes it theoretically possible capture this information. It us thus important to capture differences between the full eigenspaces instead of minor differences between specific eigenvalues or eigenvectors from graph to graph.
  Learned positions are relative within graphs. Eigenspaces are used to understand the relationship between nodes within graphs, not across them. Proposed models should therefore only compare the eigenfunctions of nodes within graphs.
sections.heading: 3 Model Architecture
sections.text: In this section, we propose an elegant architecture that can use the eigenfunctions as PEs while addressing the concerns raised in section 2.2. Our Spectral Attention Network (SAN) model inputs eigenfunctions of a graph and projects them into a learned positional encoding (LPE) of fixed size. The LPE allows the network to use up to the entire Laplace spectrum of each graph, learn how the frequencies interact, and decide which are most important for the given task.
  We propose a two-step learning process summarized earlier in Figure 1. The first step, depicted by blocks (c-d-e) in the figure, applies a Transformer over the eigenfunctions of each node to generate an LPE matrix for each graph. The LPE is then concatenated to the node embeddings (blocks g-h), before being passed to the Graph Transformer (block i). If the task involves graph classification or regression, the final node embeddings are subsequently passed to a final pooling layer.
sections.heading: 3.1 LPE Transformer Over Nodes
sections.text: Using Laplace encodings as node features is ubiquitous in the literature concerning the topic. Here, we propose a method for learning node PEs motivated by the principles from section 2.2. The idea of our LPE is inspired by Figure 2, where the eigenvectors φ are represented as a non-uniform sequence with the eigenvalue λ being the position on the frequency axis. With this representation, Transformers are a natural choice for processing them and generating a fixed-size PE.
  The proposed LPE architecture is presented in Figure 4. First, we create an embedding matrix of size 2 × m for each node j by concatenating the m-lowest eigenvalues with their associated eigenvectors. Here, m is a hyper-parameter for the maximum number of eigenvectors to compute and is analog to the variable-length sequence for a standard Transformer. For graphs where m > N , a masked-padding is simply added. Note that to capture the entire spectrum of all graphs, one can simply select m such that it is equal to the maximum number of nodes a graph has in the dataset. A linear layer is then applied on the dimension of size 2 to generate new embeddings of size k. A Transformer Encoder then computes self-attention on the sequence of length m and hidden dimension k. Finally, a sum pooling reduces the sequence into a fixed k-dimensional node embedding.
  The LPE model addresses key limitations of previous graph Transformers and is aligned with the first four etiquettes presented in section 2.2. By concatenating the eigenvalues with the normalized eigenvector, this model directly addresses the first three etiquettes. Namely, it normalizes the eigenvectors, pairs eigenvectors with their eigenvalues and treats the number of eigenvectors as a variable. Furthermore, the model is aware of multiplicities and has the potential to linearly combine or ignore some of the repeated eigenvalues.
  However, this method still does not address the limitation that the sign of the pre-computed eigenvectors is arbitrary. To combat this issue, we randomly flip the sign of the pre-computed eigenvectors during training as employed by previous work [15, 14], to promote invariance to the sign ambiguity.
sections.heading: 3.2 LPE Transformer Over Edges
sections.text: Here we present an alternative formulation for Laplace encodings. This method addresses the same issues as the LPE over nodes, but also resolves the eigenvector sign ambiguity. Instead of encoding absolute positions as node features, the idea is to consider relative positions encoded as edge features.
  Inspired by the physical interactions introduced in 1 and 2, we can take a pair of nodes (j1, j2) and obtain sign-invariant operators using the absolute subtraction |φi,j1 − φi,j2 | and the product φi,j1φi,j2 . These operators acknowledge that the sign of φi,j1 at a given node j1 is not important, but that the relative sign between nodes j1 and j2 is important. One might argue that we could directly compute the deterministic values from equations (1, 2) as edge features instead. However, our goal is to construct models that can learn which frequencies to emphasize and are not biased towards the lower frequencies — despite lower frequencies being useful in many tasks.
  This approach is only presented thoroughly in appendix A, since it suffers from a major computational bottleneck compared to the LPE over nodes. In fact, for a fully-connected graph, there are N times more edges than nodes, thus the computation complexity is O(m2N2), or O(N4) considering all eigenfunctions. The same limitation also affects memory and prevents the use of large batch sizes.
sections.heading: 3.3 Main Graph Transformer
sections.text: Our attention mechanism in the main Transformer is based on previous work [14], which attempts to repurpose the original Transformer to graphs by considering the graph structure and improving attention estimates with edge feature embeddings.
  In the following, note that hli is the i-th node’s features at the l-th layer, and eij is the edge feature embedding between nodes i and j. Our model employs multi-head attention over all nodes:
  ĥl+1i = O l h
  Hn
  k=1 ( ∑ j∈V wk,lij V k,lhlj) (3)
  where Olh ∈ Rd×d, V k,l ∈ Rdk×d, H denotes the number of heads, L the number of layers, and f concatenation. Note that d is the hidden dimension, while dk is the dimension of a head ( dH = dk).
  A key addition from our work is the design of an architecture that performs full-graph attention while preserving local connectivity with edge features via two sets of attention mechanisms: one for nodes connected by real edges in the sparse graph and one for nodes connected by added edges in the fully-connected graph. The attention weights wk,lij in equation 3 at layer l and head k are given by:
  ŵk,lij =  Q1,k,lhli◦K 1,k,lhlj◦E 1,k,leij√ dk if i and j are connected in sparse graph Q2,k,lhli◦K 2,k,lhlj◦E
  2,k,leij√ dk
  otherwise
   (4)
  wk,lij =  1 1+γ · softmax( ∑ dk ŵk,lij ) if i and j are connected in sparse graph
  γ 1+γ · softmax( ∑ dk ŵk,lij ) otherwise  (5) where ◦ denotes element-wise multiplication and Q1,k,l, Q2,k,l, K1,k,l, K2,k,l, E1,k,l, E2,k,l ∈ Rdk×d. γ ∈ R+ is a hyperparameter which tunes the amount of bias towards full-graph attention, allowing flexibility of the model to different datasets and tasks where the necessity to capture longrange dependencies may vary. Note that softmax outputs are clamped between−5 and 5 for numerical stability and that the keys, queries and edge projections are different for pairs of connected nodes (Q1,K1,E1) and disconnected nodes (Q2,K2,E2).
  A multi-layer perceptron (MLP) with residual connections and normalization layers are then applied to update representations, in the same fashion as the GT method [14]. ˆ̂ hl+1 = Norm(hli + ĥ l+1 i ), ˆ̂ ĥl+1i =W l 2ReLU(W l 1 ˆ̂ hl+1i ), h l+1 i = Norm( ˆ̂ hl+1 + ˆ̂ ĥl+1i ) (6)
  with the weight matrices W l1 ∈ R2d×d, W l2 ∈ Rd×2d. Edge representations are not updated as it adds complexity with little to no performance gain. Bias terms are omitted for presentation.
sections.heading: 3.4 Limitations
sections.text: The first limitation of the node-wise LPE, and noted in Table 1 is the lack of sign invariance of the model. A random sign-flip of an eigenvector can produce different outputs for the LPE, meaning
  that the model needs to learn a representation invariant to these flips. We resolve this issue with the edge-wise LPE proposed in 3.2, but it comes at a computational cost.
  Another limitation of the approach is the computational complexity of the LPE being O(m2N), or O(N3) if considering all eigenfunctions. Further, as nodes are batched in the LPE, the total memory on the GPU will be num_params * num_nodes_in_batch instead of num_params * batch_size. Although this is limiting, the LPE is not parameter hungry, with k usually kept around 16. Most of the model’s parameters are in the Main Graph Transformer of complexity O(N2).
  Despite Transformers having increased complexity, they managed to revolutionalize the NLP community. We argue that to shift away from the message-passing paradigm and generalize Transformers to graphs, it is natural to expect higher computational complexities. This is exacerbated by sequences being much simpler to understand than graphs due to their linear structure. Future work could overcome this by using variations of Transformers that scale linearly or logarithmically [34].
sections.heading: 3.5 Theoretical properties of the architecture
sections.text: Due to the full connectivity, it is trivial that our model does not suffer from the same limitations in expressivity as its convolutional/message-passing counterpart.
  WL test and universality. The DGN paper [4] showed that using the eigenvector φ1 is enough to distinguish some non-isomorphic graphs indistinguishable by the 1-WL test.
  Given that our model uses the full set of eigenfunctions, and given enough parameters, our model can distinguish any pair of non-isomorphic graphs and is more powerful than any WL test in that regard. However, this does not solve the graph isomorphism problem in polynomial time; it only approximates a solution, and the number of parameters required is unknown and possibly non-polynomial. In appendix C, we present a proof of our statement, and discuss why the WL test is not well suited to study the expressivity of graph Transformers due to their universality.
  Reduced over-squashing. Over-squashing represents the difficulty of a graph neural network to pass information to distant neighbours due to the exponential blow-up in computational paths [1].
  For the fully-connected network, it is trivial to see that over-squashing is non-existent since there are direct paths between distant nodes.
  Physical interactions. Another point to consider is the ability of the network to learn physical interactions between nodes. This is especially important when the graph models physical, chemical, or biological structures, but can also help understanding pixel interaction in images [2, 3]. Here, we argue that our SAN model, which uses the Laplace spectrum more effectively, can learn to mimic the physical interactions presented in section 2.1.2. This contrasts with the convolutional approach that requires deep layers for the receptive field to capture long-distance interactions. It also contrasts with the GT model [14], which does not use eigenvalues or enough eigenfunctions to properly model physical interactions in early layers. However, due to the lack of sign-invariance in the proposed node-wise LPE, it is difficult to learn these interactions accurately. The edge-wise LPE (section 3.2) could be better suited for the problem, but it suffers from higher computational complexity.
sections.heading: 4 Experimental Results
sections.text: The model is implemented in PyTorch [31] and DGL [38] and tested on established benchmarks from [15] and [21] provided under MIT license. Specifically, we applied our method on ZINC, PATTERN, CLUSTER, MolHIV and MolPCBA, while following their respective training protocols with minor changes, as detailed in the appendix B.1. The computation time and hardware is provided in appendix B.4.
  We first conducted an ablation study to fairly compare the benefits of using full attention and/or the node LPE. We then took the best-performing model, tuned some of its hyperparameters, and matched it up against the current state-of-the-art methods. Since we use a similar attention mechanism, our code was developed on top of the code from the GT paper [14], provided under the MIT license.
sections.heading: 4.1 Sparse vs. Full Attention
sections.text: To study the effect of incorporating full attention, we present an ablation study of the γ parameter in Figure 5. We remind readers that γ is used in equation 5 to balance between sparse and full attention. Setting γ = 0 strictly enables sparse attention, while γ = 1 does not bias the model in any direction.
  It is apparent that molecular datasets, namely ZINC and MOLHIV, benefit less from full attention, with the best parameter being log γ ∈ (−7,−5). On the other hand, the larger SBM datasets (PATTERN and CLUSTER) benefit from a higher γ value. This can be explained by the fact that molecular graphs rely more on understanding local structures such as the presence of rings and specific bonds, especially in the artificial task from ZINC which relies on counting these specific patterns [15]. Furthermore, molecules are generally smaller than SBMs. As a result, we would expect less need for full attention, as information between distant nodes can be propagated with few iterations of even sparse attention. We also expect molecules to have fewer multiplicities, thus reducing the space of eigenvectors. Lastly, the performance gains in using full attention on the CLUSTER dataset can be attributed to it being a semi-supervised task, where some nodes within each graph are assigned their true labels. With full attention, every node receives information from the labeled nodes at each iteration, reinforcing confidence about the community they belong to.
  In Figure 6, we present another ablation study to measure the impact of the node LPE in both the sparse and full architectures. We observe that the proposed node-wise LPE contributes significantly to the performance for molecular tasks (ZINC and MOLHIV), and believe that it can be attributed to the detection of substructures (see Figure 3). For PATTERN and CLUSTER, the improvement is modest as the tasks are simple clustering [15]. Previous work even found that the optimal number of eigenvectors to construct PE for PATTERN is only 2 [14].
sections.heading: 4.2 Comparison to the state-of-the-art
sections.text: When comparing to the state-of-the-art (SOTA) models in the literature in Figure 7, we observe that our SAN model consistently performs better on all synthetic datasets from [15], highlighting the strong expressive power of the model. On the MolHIV dataset, the performance on the test set is slightly lower than the SOTA. However, the model performs better on the validation set (85.30%) in comparison to PNA (84.25%) and DGN (84.70%). This can be attributed to a well-known issue with this dataset: the validation and test metrics have low correlation. In our experiments, we found higher test results with lower validation scores when restricting the number of epochs. Here, we also included results on the MolPCBA dataset, where we witnessed competitive results as well.
  Other top-performing models, namely PNA [11] and DGN [4], use a message-passing approach [17] with multiple aggregators. When compared to attention-based models, SAN consistently outperforms the SOTA by a wide margin. To the best of our knowledge, SAN is the first fully-connected model to perform well on graph tasks, as is evident by the poor performance of the GT (full) model.
sections.heading: 5 Conclusion
sections.text: In summary, we presented the SAN model for graph neural networks, a new Transformer-based architecture that is aware of the Laplace spectrum of a given graph from the learned positional encodings. The model was shown to perform on par or better than the SOTA on multiple benchmarks and outperforms other Attention-based models by a large margin. As is often the case with Transformers, the current model suffers from a computational bottleneck, and we leave it for future work to implement variations of Transformers that scale linearly or logarithmically. This will enable the edge-wise LPE presented in appendix A, a theoretically more powerful version of the SAN model.
  Societal Impact. The presented work is focused on theoretical and methodological improvements to graph neural networks, so there are limited direct societal impacts. However, indirect negative impacts could be caused by malicious applications developed using the algorithm. One such example is the tracking of people on social media by representing their interaction as graphs, thus predicting and influencing their behavior towards an external goal. It also has an environmental impact due to the greater energy use that arises from the computational cost O(m2N +N2) being larger than standard message passing or convolutional approaches of O(E).
  Funding Disclosure.
  Devin Kreuzer is supported by an NSERC grant.
title: Rethinking Graph Transformers with Spectral Attention