Rethinking Graph Transformers with Spectral Attention
Authors: Devin Kreuzer
Dominique Beaini
William L. Hamilton
Vincent Létourneau
Prudencio Tossou
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph neural networks
transformers
spectral theory
molecules
deep learning
graph theory

Abstract: 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 \textit{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-the-art GNNs, and outperforms any attention-based model by a wide margin, becoming the first fully-connected architecture to perform well on graph benchmarks.

Rethinking Graph Transformers with Spectral Attention
Devin Kreuzer
McGill University, Mila Montreal, Canada
devin. Devin.kreuzer@@e www.uerrruaaaaal waa.meermmmm....m11......
Dominique Beaini
William L. Hamilton McGill University, Mila Montreal, Canada
Vincent Létourneau University of Ottawa Ottawa, Canada vietour2Quottarea ca
Valence Discovery
Montreal, Canada
dem.iiigguevvllemcciiccovvrrrrr com com
whc@ic.megill.ca
Prudencio Tossou
Valence Discovery
Montreal, Canada
prudeacciofaaleeecciiccveeyy.y. com
Abstract
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 learned positional encoding (LPE) that 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 fully- 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, information bottleneck of most GNNs, and enables better modeling of physical phenomenons such as heat transfer and electric interaction. When tested empirically of 4 standard datasets, our model performs on par or better than state-of-the- art GNNs, and outperforms any attention-based model by wide margin, becoming the first fully-connected architecture to perform well on graph benchmarks.
Introduction
The prevailing strategy for graph neural networks (GNNs) has been 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 review).
However, there is growing recognition that the message-passing paradigm has inherent limitations. The expressive power of message passing appears inexorably bounded by the Weisfeiler-Lehmas iso- morphism hierarchy 29 30 39 Message-passing GNNs are known to suffer from pathologies, such
Equaal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

as oversmoothing, due to their repeated aggregation of local information [19] and over.squashing. due to the exponential blow-up computation paths as the model depth increases M.
As a result, there is a growing interest in deep learning techniques that encode graph structure as soft inductive bias, rather than as hard-coded aspect of message passing 14 [4]. A central issue with pressage-passing paradigm is that input graph structure is encoded by restricting the structure of the model's s computation graph, inherently limiting its flexibility. This reminds us 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 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 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] [3] More recently, the GT model [14] was proposed generalization of Transformers to graphs, where they experimented with sparse and full graph attention while providing fre.uenuunn cigenvectors of the Laplacian 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 [4] and provably exceeds the expressive power of standard message-passiin passing GNNs. We show that full Transformer-style attention provides consistent empirical gains compared to an equivalent sparse pressage-passingg model, and demonstrate that our SAN architecture is competitive with exceeding the state-of-ther of-the-att several well-known graph benchmarks. An overview of the entire method is presented in Figure] [ with link to the code here: https://giiii com SeammDDviiii Dewinnrreeeer/SS.....
2 Theoretical Motivations
There can be significant loss in structural information if naively generalizing Transformers to graphs. To preserve this information as well as local connectivity, previous studies [37 [4] have proposed to use the eigenfunctions of their Laplacian 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 are shown in Table
previous studies 37 4
Table Comparison of the properties of different graph Transformer models.
MODELS
GAT
GT sparse
GT full
SAN
Preserves local structure in attention
X
Uses edge features
X
X
Connects non-neighbouring nodes
X
X
Uses eigenvector- based PE for attention
X
/
Use PE with structural information Considers the ordering of the eigenvalues
X
X
X
Invariant the norm of the eigenvector
X
Considers the spectrum of eigenvalues Considers variable of eigenvectors Aware of eigenvalue multiplicities Invariant to the sign of the eigenvectors
X
AXX
XX
X
X
Presented results add full connectivity before computing the eigenvectors, thus losing the structural informa- tion of the graph.

---

Pre Pre-computed steps ((m))
Learned pasitional encoding (LPE) ((m"))
Main Transformer steps (
Compute the
Generate node-wise
(d) Generate
(a)
Input graph
(b)
(c)
(e)
Pool the LPE
mn eigenvectors
eigenvector
embedding O (NNm)
A: Adjacency
normalaed eigenwectors
A; normalzzed
eigerwalue
For node 1, generate
Use sum meon pooling the dimension of size mn the
Laplacian
of are computed and
learned positional embeddiing
W: number of nodes
sorted such that lowest eigervalue and (Pa-1
eigenvector associated to A
size
nade wise embedding
E: number of edges.
has the m-th lowest.
duy The j-th row d:
A linear layer applied, followed by layer Transtormer encoder with self attention sequence longth
The result the LPE matrix, each represents the learned positional encoding 1-th node.
Re:
each node generate
node fecturas
The complexity ((mE))
inttaa positionaa encoding (PC)
fel input edge
Node colormap
using the nu nu-first and
festures
if graph has loss than m
0: Computation
nodes, add masked padcing.
2x
xo X
complexity
au uattu acuanbas
Linear
Transformer
Graph
Ag 33
Number of features
mm--1
xm
K.k Xm
(f)
Fully connect
(s)
Input layers
(h)
Concatenate node
(i)
Apply transformer
graph
features
features ((
edge added of discornected nodes and given its own embeddinng.
Add linear layer for both the node and edge
node features from the MLP to those from the LPE.
all pairs
nodes features and edge between them. Different projections
AT
features.
used to compute attention real edges added edges.
(3)
The size of the edge embed- ding dictionary increases by
#/ x
1, the edges becomes N².
O(N)
X(1>
K'
K
Transformer
Edge features
dimension
Q'
encoders
MLP
gtt
E
Prediction
Outout d
layer
11"
Figure 1: The proposed SAN model with the node LPE, a generalization of Transformers to graphs.
2.1
Absolute and relative positional encoding with eigenfunctions
The notion of positional encodings (PEs) in graphs is not a trivial concept, as there exists no canonical way of ordering nodes defining axes. In this section, investigate how eigenfunctions of the Laplacian can be used to define absolute and relative PEs in graphs, to measure physical interactions between nodes, and enable "hearing" of specific sub-structures similar to how the sound of drum can reveal its structure.
2.1.1 Eigenvectors equate to sine functions graphs
In the Transformer architecture, a fundamental aspect is the use 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 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 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 the eigenvectors as PEs for GNNs [5], for directional flows 4 and for Transformers [14.
Being equivalent sine functions, we naturally find that the Fourier Transform of function & applied to a graph gives (f,) = (f. Φ.). where the eigenvalue is considered as position the Fourier domain of that graph (6) Thus, the eigenvectors axis of eigenvalues rather than components of a matrix as illustrated in Figure 2
best viewed vectors positioned on the
2.1.2 What do eigenfunctions tell us about relative positions?
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

---

$1
4
$3
4:
x-1
Node
Node
Node Node
Node Node
22
A
A
Ay--1
frequencles
Figure 2: a) Standard view of the eigenvectors as a matrix. b) Eigenvectors Φ; viewed vectors positionned on the axis of frequencies (eigenvalues).
the Laplacian is fundamental operator in physics and is notably used in Maxwell's equations [16 and the heat diffusion 66)
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 given charge. In a graph, the same concept uses the pscudo-inverse the Laplacian G and can be computed by its eigenfunctions. See equation - where G(),, is the electric potential between nodes f1 and j2, Ø; and X, are the i-th cigenvectors and eigenvalues of the symmetric Laplacian D LD 2 and D is the degree matrix, and di, the j-th row of the vector.
( Pi.a)² )²
(2 = d
A
$20
Further, the original solution of the heat equation given by Fourier relied on 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 66 4 we use the interaction between two heat kernels to define in equation the diffusion distance dp between nodes j1, J2 66 [0]. Similarly, the biharmonic distance dg was proposed as better measure of distances [28). Here we use the eigenfunctions of the regular Laplacian L.
( D1.52
db. = Σ
e 20h ( -Di.2)
Σ $20
(2)
X
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 graph. Secondly, we notice that the product of eigenvectors is proportional to the electrostatic interaction, while the subtraction proportional there is consistent pattern across all 3 equations: smaller frequencies/eigenvalus are more heavily weighted when determining distances between nodes.
the diffusion and biharmonic distances. Lastly,
2.1.3 Hearing the shape of graph and its sub-structures
Another well-known property of cigenvalues 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 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 [2] Examples of eigenvectors for molecular graphs are presented in Figure 3
Elgenvvector colormap
ALa
Ass
1.
Figure 3: Examples of eigenvalues X; and eigenvectors Φi for molecular graphs. The low-frequency eigenvectors Φ1, d2 spread accross the graph, while higher frequencies, such Φ14, Φ15 for the left molecule or Φ10: Φ1 for the right molecule, often resonate local structures.

---

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 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 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 is compatible with the definition of the Green's function I Thus, 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 S we observe how an ordering would miss the fact that both molecules resonate at À different ways.
Multiplicities, Another important problem with choosing eigenfunctions is the possibility of 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 model that can handle this ambiguity.
Variable number of eigenvectors. A graph G; can have at most N; linearly independent eigenvectors with N₂ being its number of nodes. Most importantly, N, can vary across all G, in the dataset. Prior work [14] elected to select a fixed number & cigenvectors for each graph, where k S. N,, Vi. This produces 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 model which constructs fixed PEs of dimension k, where & does not depend on the number of eigenvectors in the graph.
Sign invariance. As noted earlier, there is sign ambiguity with the eigenvectors. With the sign of & being independent of its normalization, we are left with a total of 2* possible combination of signs when choosing & eigenvectors of graph. Previous work has proposed to do data augmentation by and although can work when is small,
randomly flipping the sign of the eigenvectors 4 15 14, becomes intractable for large k.
2.3 Learning with Figenfunctions
Learning generalizable information from eigenfunctions is fundamental to their succesful usage. Here we detail important points that support it possible to do 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. us thus important 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
5

---

3 Model Architecture
In this section, we propose an elegant architecture that can use the eigenfunctions PEs while addressing the concerns raised in section [.2 Our Spectral Attention Network (SAN) model inputs eigenfunctions of 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 [ The first step, depicted by blocks (c-d-e) in the figure, applies a Transformer over the cigenfunctions of each node to generate an LPE matrix for each graph. The LPE is then concatenated 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 final pooling layer.
3.1 LPE Transformer Over Nodes
Using Laplace encodings 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 where the cigenvectors with the eigenvalue being the position on the frequency axis. With this representation, Transformers natural choice for processing them and generating fixed-size PE.
represented as non-unilorm sequence
The proposed LPE architecture is presented Figure First, we create an embedding matrix of size 2 x for each node by concatenating the m-lowest eigenvalues with their associated eigenvectors. Here, m 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 >> N, a masked-pare -aadding is simply added. Note that to capture the entire spectrum of all graphs, one can simply select such that it is equal to the maximum number of nodes graph has in the dataset. 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 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 etiqueties presented in section 2.2 By concatenating the eigenvalues with the normalized eigenvector, this model directly addresses the first three eliquetles. Namely, it normalizes the eigenvectors, pairs eigenvectors with their eigenvalues and treats the number eigenvectors as 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 eigenvec- tors 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.
22
Linear layer
Transformer Encoder m x
For each Node j
Sum pooling
Node-wise LPE
2 x
Number of features
Number of features It
Figure 4: Learned positional encoding (LPE) architectures, with the model being aware of the graph's 's Laplace spectrum by considering m eigenvalues and eigenvectors, where we permit m < N, with N denoting the number of nodes. Since the Transformer loops over the nodes, each node can be viewed as an element of a batch to parallelize the computation. Here oi.; is the j-th element of the eigenvector paired to the i-th lowest eigenvalue A;-
3.2 LPE Transformer Over Edges
Here 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 encoding absolute positions node features, the idea is to consider relative positions encoded edge features.

---

Inspired by the physical interactions introduced in and 2 we can take a pair of nodes (2).j2) and obtain sign-invariant operators using the absolute subtraction Φ - Qi.ja and the product @i.j Pi.ja- These operators acknowledge that the sign of Φi.j, at given node ji is not important, but that the relative sign between nodes j1 and j2 important. One might argue that we could directly compute the deterministic values from equations T 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 appendix A since 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 O(m² 2²), or O(N+) considering all eigenfunctions. The same limitation also affects memory and prevents the use of large batch sizes.
3.3 Main Graph Transformer
Our attention mechanism in the main Transformer is based 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 h is the i-th node's features at the I-th layer, and eij the edge feature embedding between nodes i and j. Our model employs multi-head attention over all nodes:
h++1 0 11 |
wij k.
where O E ddd Vk Rddxxd, H denotes the number of heads, L the number of layers, and concatenation. Note that d is the hidden dimension, while dę is the dimension of head ( dy).
key addition from our work is the design of an architecture that performs full- tull-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 ku fully-connected graph. The attention weights Wj
in equation 3 at layer / and head are given by:
if i and j are connected in sparse graph
Vdl
kl Wj
(4)
Q2th. 1.t.look2kk.1 E2th
otherwise
Vdla
1 softmax 14y
(Ed,
kil Wij
if i and are connected in sparse graph
wij
kJ
(5)
softmax (Eo, w
otherwise
where o denotes element- multiplication and QI.a.i, Q2.k., K K 2 El.k., E Rduxd_ y E IR+ is a hyperparameter which tunes the amount of bias towards full-graph attention, allowing flexibility of the model different datasets and tasks where the necessity to capture long- range 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 (Q), K1, E and disconnected nodes (Q², E*).
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].
h 1-1 Norm( + h,t1), I+1 = W (. h = Norm h + 1+1) (6)
with the weight matrices W E g2dxd, w E idx2dd Edge representations are not updated as it adds complexity with little to no performance gain. Bias terms are omitted for presentation.
3.4 Limitations
The first limitation of the node-wise LPEE, and noted in Table is the lack of sign invariance of the model. A random sign-flip of an eigenvector can produce different outputs for the LPE, meaning
7

---

that the model needs to learn a representation invariant to these flips. We resolve this issue with the edge-wise LPE proposed 3.2 but it comes at a computational cost.
Another limitation of the approach is the computational complexity of the LPE being ( N), or O(N3) if considering all eigenfunctions. Further, nodes are batched in the LPE, the total memory on the GPU will be num parm___aamss Although this is limiting, the LPE is not parameter hungry, with & usually kept around 16. Most of the model's parameters are in the Main Graph Transformer of complexity O(N2).
rum_nodes_ sasss_nn_baut ir_batch instead of nun_params
batch_size
Despite Transformers having increased complexity, they managed to revolutionalize the NLP com- munity. We argue that to shift away from the peassage-passiingg 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
3.5 Theoretical properties of the architecture
Due to the full connectivity, is trivial that our model does not suffer from the same limitations in expressivity as its convolutional/messaee-p paassessisggggiiignngggg counterpart.
WL test and universality. The DGN paper 4 showed that using the eigenvector Φ enough to distinguish some isomorpoopp graphs indistinguishable by the 1-WL test.
Given that model uses the full set of eigenfunctions, and given enough parameters, 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; only approximates a solution. and the number of parameters required is unknown and possibly non-polynomial. In appendix C we present 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 graph neural network to pass information to distant neighbours due to the exponential blow-up in computational paths [.
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 especially important when the graph models physical, chemical,
or biological structures, but can also help understanding pixel interaction in images [ 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.2 This contrasts with the convolutional approach that requires deep layers for the receptive field capture din-tiitance interactions. 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 wise IPE, 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.
4 Experimental Results
The model is implemented in PyTorch 31 and DGL (38 and tested on established benchmarks from [3] and [1 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 the appendix B.I 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 up against the current state-of-the-ar methods. Since we use a similar attention mechanism, our code was developed on top of the code from the GT paper []4, provided under the MIT license.
8

---

ZINC (Lower is better)
PATTERN (Higher Is better)
CLUSTER (Higher is better)
MOLHIV (Higher is better)
0.300
86-
Tesk MAE
0.250-
Text Test% %5-ccc
82
84-
76.5
76
0.225
Test
80
73
74
0.175
75.5
0.150
Spars by
10g
Y
10g
Figure 5: Effect of the parameter on the performance across datasets from 13 LPE. Dotted black lines indicate sparse attention, which is equivalent to setting ? Each box plot consists of 4 runs, with different seeds (except MolHIV).
21 using the Node
Model detais
ZINC
PATTERN
CLUSTER
MOLHIV
Attention
IPE
MAE
% ACC
ACC
ROC-AUC
Best
Sparse
0.267
0.032
63613 0.663
75,683 1 0.098
7346 0.71
Sparse
2.1.0
0.392 0.055
863322 0.0:9
76444
0.177
7384 1.80
Worst
Full
Node
0.157 D. 006
86. 441
0. 040
76. 691
+ 247
77.57
Figure 6: Ablation study on datasets from 15 no hyperparameter tuning other than taken from Figure For a given dataset, all models use the same hyperparameters, the hidden dimensions are adjusted to have ~ 500k learnable parameters. Mcans and uncertainties derived from four runs, with different seeds (except MolHIV).
21 for the node LPE and full graph attention, with
4.1 Sparse Full Attention
To study the effect of incorporating full attention, present ablation study of the parameter in Figure 5 We remind readers that 7 is used in equation 5oo balance between sparse and full attention. does not bias the model in any direction.
Setting 7 strictly enables sparse attention, while
apparent that molecular datasets, namely ZINC and MOLHIV, benefit less from full attention, with the best parameter being log E (-..-5). On the other hand, the larger SBM datasets (PATTERN and CLUSTER) benefit from a higher y value. This can be explained by the fact that molecular graphs rely more 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 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, reinforeing confidence about the community they belong to.
generally smaller than SBMs. As result, would
In Figure 6, we present another ablation study to measure the impact of the node LPE both the sparse 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 Previous work even found that the optimal number of eigenvectors construct PE for PATTERN is only 2 [14].
modest as the tasks are simple clustering [5]
4.2 Comparison to the state-of-the-art
When comparing the state-of-the-art (SOTA) models in the literature in Figure we observe that our SAN model consistently performs better on all synthetic datasets from [5] highlighting the strong expressive power of the model. On the MolHiV dataset, the performance on the test 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 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 well.

---

Other top- per-perfommnn models, namely PNA [ and DGN 4 use a message passing approach [T7 with multiple aggregators. When compared attention- models, SAN consistently outperforms the SOTA by wide margin. To the best of our knowledge, SAN is the first fully- fully-connected model to perform well on graph tasks, as is evident by the poor performance of the GT (full) model.
0,976
GraphSage
0.398
0.002
50.492 1 0.001
63,844
0.110
Best
GatedGCN
0,282 + 0.015
85.568
0.088
73,840
0.326
GatedGCN PE
0.214 + 0.013
86.508
0.085
76,082 + 0.196
GIN
0.526 1 0.013
05.387
0.136
64.716 + 1.553
75.58 + 1.40
22.66 0.28
PNA
0.142 + 0.010
79.05
= 1.32
28:38 0.35
DGN
79.70
: 0.0.
288 85 0.30
Attention-based
Worst
0.384
0.007
0.447
(sparse)
0.662
GT (full)
0.598 1 0.049
56.482
3.549
27.121
8.471
SAN 0.139 006
86. 581
037
76. 691 0.65
77.85
0.244
27.65 0.42
Figure 7: Comparing our tuned model on datasets from 13 against GCN 225 GraphSage [8]
Means and uncertainties derived from four runs with different seeds, except MolHIV which uses 10 runs with identical seed. The number parameters fixed to 500k for ZINC, PATTERN and CLUSTER.
GIN [39] GAT (37), GatedGCN [5], PNA (TI) and DGN
Conclusion
In summary, we presented the SAN model for graph neural networks, new Transformer-based architecture that is aware of the Laplace spectrum of given graph from the learned positional encodings. The model was shown perform on par better than the SOTA multiple benchmarks and outperforms other Attention-basel models by large margin. As is often the case with Trans- formers, 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 theoretically more powerful version of the SAN model.
edge-wise LPE presented in appendix
Societal Impact. The presented work focused on theoretical and methodological improvements to graph neural networks, there are limited direct societal impacts. However, indirect negative impacts could be caused by malicious applications developed using the algorithm. One such example 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 that arises from the computational cost ( N + N2) being larger than standard message passing or convolutional approaches of O(E).
Funding Disclosure.
Devin Kreuzer is supported by an NSERC grant.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. vrXiv:2006.05200 (cs, star], 2020.
[2] Dominique Beaini, Sofiane Achiche, Alexandre Duperré, and Maxime Raison. Deep green function convolution for improving saliency in convolutional neural networks. The Visual Computer, 37(2):227-244 2020.
[3] Dominique Beaini, Sofiane Achiche, and Maxime Raison. Improving convolutional neural networks via conservative field regularisation and integration.
10

---

[4] Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. ICML2021, 2021.
[5] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017.
[6] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
[7] F. Cajori. History of Mathematics. AMS Chelsea Publishing Series. AMS Chelsea, 1999.
[8] Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network. CoRR, abs/2003.074500 2020.
[9] Fan Chung and S, T. Yau. Discrete green's functions. Journal of Combinatorial Theory, Series
A, 91(1):191-21, 2000.
[10] Ronald Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-30, 2006. Special Issue: Diffusion Maps and Wavelets.
[11] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.057/1 18, 2020.
[12] Luca Cosmo, Mikhail Panine, Arianna Rampini, Maks Ovsjanikov, Michael M. Bronstein, and Emanuele Rodola. Isospectralization, or how to hear shape, style, and correspondence. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
[13] Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter. CoRR, 02//2104.12444 2021.
[14] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks graphs, 2020.
[15] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00990 00982, 2020.
[16) Richard Phillips Feynman, Robert Benjamin Leighton, and Matthew Sands. The Feymman lectures on physics; New millennium ed. Basic Books, New York, NY, 2010. Originally published 1963-1965.
[17] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volus 70, pages 1263-1272. JMLR. org, 2017.
[18] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[19] William L. Hamilton. Graph Representation Learning. Morgan and Claypool, 2020.
[20] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98):1773- 1997.
[21] Weihua Hu. Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.006877 2020.
[22] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. arXiv:1802. 043644434 [cs, stat], 2018.
[23] Mark Kac. Can one hear the shape of drum? The American Mathematical Monthly, 73(4):1, 1966.

---

[24] Anees Kazi, Luca Cosmo. Nassir Navab, and Michael Bronstein. Differentiable graph module (dgm) graph convolutional networks. arXiv preprint arXiv:2002.04999 2020.
[25] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.0200000 160.002907. 2016.
[26] B. Levy. Laplace-beltrami eigenfunctions towards algorithm that "understands" geometry.
In IEEE International Conference on Shape Modeling and Applications 2006 (SMI '06), pages 13-13, 2006.
[27] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning, 2020.
[28] Yaron Lipman, Raif M. Rustamov, and Thomas A. Funkhouser. Biharmonic distance. ACM Trans. Graph., 29(3), July 2010.
[29] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint 1rXhv:1905.11136. 2019.
[30] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[31] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitooo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
[32] Emanuele Rodolà, Luca Cosmo, Michael M. Bronstein, Andrea Torsello, and Daniel Cremers. Partial functional correspondence, 2015.
[33] Joshua Schrier. Can one hear the shape of a molecule (from its coulomb matrix cigenvalues)? Journal of Chemical Information and Modeling, 3804-3380-, 2020. Publisher: American Chemical Society.
[34] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, 2020.
[35] Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241-272, 2003.
[36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. CoRR, abs/l706.03766 2017.
[37] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint urXiv:/7100 10903, 2017.
(38] 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, and Zheng Zhang. Deep graph library: A graph-centric, highly-performan package for graph neural networks. arXiv preprint arXiv: 190901190900115. 2019.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1:X.v:1810000822 2018
[40] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of eoquemce-to-sequemee functions?, 2020.
[41] Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. So(n)S connections are expressive enough: Universal approximability of sparse transformers. CoRR, abs/2006.04862, 2020.
[42] Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. Graph transformer networks, 2020.
12


Reviews:
[{"review_id": "wyr5Id6bLp", "reviewer": "Reviewer_FaY8", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nS1: It is important to properly define the positions of Transformers on graph structured data.\nS2: The proposed method on using the full spectrum of Laplacian as positional encoding is simple yet effective, and the complementary theoretical analysis on the better properties brought by using spectrum is interesting and rooted in spectral graph theory.\nS3: The paper is easy to follow with a clear motivation and closely related to the NeurIPS community with comprehensive experimental analysis.\n\nWeaknesses:\n\nW1: The novel is rather limited. The idea that using the spectrum of Laplacian as positional encoding is already proposed in the GT model as the authors stated, and certain properties of SAN, such as WL test and universality and reduced over-squashing, seem like that can also be achieved by the GT model with slight change on the design of structure.\n\nW2: One important design is that SAN considers the variable # of eigenvectors by using a hyperparameter $m$. However, the choice of $m$ that splits the spectrum into two parts based on a hyper parameter seems not well-supported. In my view, the definition of low/high frequency components should at least have something to do with the actual distribution of eigenvalues, and not simply be based on a hard threshold on the eigenvalue index. This should be carefully discussed in the paper. \n\nW3: The reviews of previous works seem missing from both main paper and the Appendix. Some of the related works upon using the attention on the spectrum of Laplacian for both Transformer architecture [GTN and GT] and sparse message-passing models [1,2] should be discussed in details to demonstrate the novelty of proposed methods.\n\nW4: For experiments, why there are so many missing results for baselines on MOLHIV dataset? This makes the role of this dataset a little meaningless. By the way, the statistics of datasets are missed. I noticed that the benchmarks used for evaluation are relatively small graphs, I would be curious about how the performance is on large graphs such as social networks.\n[1] Dong, Y., Ding, K., Jalaian, B., Ji, S., & Li, J. (2021). Graph Neural Networks with Adaptive Frequency Response Filter. arXiv preprint arXiv:2104.12840.\n[2] Chang, H., Rong, Y., Xu, T., Huang, W., Sojoudi, S., Huang, J., & Zhu, W. (2020). Spectral graph attention network. arXiv preprint arXiv:2003.07450.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "vXFcThpuGqR", "reviewer": "Reviewer_kbAi", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose a novel learnable positional encoding and a new architecture, spectral attention network. The goal is to combat the problems of over-smoothing and over-squashing in graph neural networks and to increase expressivity. However, these problems are present in message passing or graph convolutional networks, and the authors do not elaborate on other graph transformers in this context in the work motivation. The correspondence between eigenvectors and sine functions is sketched in Section 2.1.1 An elegant physical explanation for the algorithmic decisions is provided. It is based on the Green's function and sheds new light on spectral graph theory and graph transformer architectures. The SAN architecture is an extension of the graph transformer proposed by Dwivedi and Bresson who also used Laplacian eigenvectors to encode node positions. However, their approach was much simpler and did not consider five principles raised by the authors of this paper -- they used $k$ smallest non-trivial vectors for each node.\n\nThe quality of the presented results is high. The performance metrics are calculated along with their error intervals based on 10 reruns of the model. The limitations of different elements of the architecture are described. The authors argue that their architecture is stronger than the Weisfeiler-Lehman isomorphism test and reduced over-squashing. However, there are some claims throughout the text that are not backed by any literature or experiments. For example in line 219: “Edge representations are not updated as it adds complexity with little to no performance gain”, or in line 254 \"SAN model, which uses the Laplace spectrum more effectively, can learn to mimic the physical interactions presented in section 2.1.2\". Is it confirmed by experiments?\n\nOverall, the paper is clearly written and easy to follow. However I have some questions about Equations 1 and 2 since this is the source of the method motivation. Should not the Green's function be symmetric? $G$ is defined as the pseudo-inverse of the graph Laplacian, which is symmetric (for an undirected graph). By the definition of the generalized inverse, the inverse of the Laplacian would be\n\\begin{equation}\nG(j_1, j_2) = \\sum_{i>0} \\frac{\\phi_{i,j_1} \\phi_{i,j_2}}{\\lambda_i},\n\\end{equation}\nbut the derivation of Equation 1 is not immediately obvious for me. In [8] we see a similar formula (Equation 13), but this corresponds to the Laplace operator $\\Delta$ which can be asymmetric, and even there the elements of $\\phi_i$ are not squared. Am I missing something that is maybe related to the electric potential that was mentioned earlier? My other comments about the equations:\n- In line 91, it probably should be said that $\\hat{\\phi}_{i,j}$ is the $j$-th **element** of the vector.\n- $d_i$ is not defined.\n- Should not the sum be over $i>0$ instead of $k>0$ in Equation 2?\n\nThe work is valuable from the perspective of the spectral graph theory research in deep learning. It can help to improve current graph transformer models. On the downside, only one graph transformer is used in the experiments. It would be interesting to see how SAN compares to the transformers that do not use the Laplacian eigenvectors as positional encoding. Additionally, in the caption of Figure 7, MoNet is mentioned as one of the architectures in the comparison, but the corresponding row is missing in the table. Another weak point of the experimental section is a relatively small range of tasks used. Maybe a task related to quantum chemistry would resonate well with the physical basis of the method.\n\nBased on my above comments, I am leaning towards the rejection, but I am willing to change my rating if all the questions are addressed during the discussion period.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and societal impacts are described in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "fl0aS8FtF6x", "reviewer": "Reviewer_M4Qn", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is one of the first suggesting that transformers equipped with structure encoding can rival with GNNs, which are the de facto architecture for graph-structured data. The paper seems sounds although some points could be clarified (see below).\n\nPros:\n- The authors carefully detail the issues related to using the spectrum of the Laplacian as node positional encoding in a transformer, making interesting observations and proposing a solution.\n- SAN performs experimentally well.\n\nCons:\n- It is claimed in the main paper (l254) that the model is able to capture long-distance interactions, but as far as I understand there are no experiments supporting this.\n- Do eigenvectors of different Laplacians (i.e of different graphs) belong to a similar space, hence can they really be \"compared\" as done in your method? What is your view on this?\n- One or two more datasets would be welcomed to better understand how does SAN compare to GNNs, for example a small scale such as NCI1 and larger scale such as OGBG-MolPCBA.\n- As mentioned by the authors, the sign flip is not avoided by the proposed method unless paying a price of $O(N^4)$ ($N$ being the number of nodes in the graph).\n\nQuestions and remarks:\n- Wouldn't have been also possible to simply pad eigenvectors of the Laplacian and project the position encodings to a new space to respectively solve the \"Variable number of eigenvectors problem\" and \"Multiplicities\" problems? \n- How is $m$ selected in practice? \n- l155: minor typo but I am not sure we can talk about the \"eigenfunction of a node\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Both are adressed by the authors.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "bLDU5m_TVUH", "reviewer": "Reviewer_rLqr", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1.\tThe innovative architecture can make use of the full spectral information, while many spectral GNNs only adopt the eigenvectors of the Laplacian. Section 2.1.2 mentions the intuitions behind using full spectral information, which come from Laplacian’s green function and node distance measures. I enjoy reading about this part.\n2.\tThe paper also summarizes some classical problems encountered by methods based on eigenfunctions. The proposed method can tackle most of them, except for the sign invariance of eigenvectors. This issue can be further solved if the edge learned position encoding is used.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tAs mentioned by the paper itself, a critical problem is the computational time complexity of the architecture, which requires $\\mathcal{O}(N^{3})$ in order to generate node-wise embedding, or even $\\mathcal{O}(N^{4})$ if the edge-wise embedding is leveraged. \n2.\tEven though the results achieved by the proposed model is impressive, I encourage the authors to also test more on other well-known graph benchmark datasets, for example the OGB dataset, which exploits a more challenging splitting procedure and is similar to real-life application, or some datasets mentioned in [1].\n\n[1] Errica, Federico, et al. \"A fair comparison of graph neural networks for graph classification.\" arXiv preprint arXiv:1912.09893 (2019).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, a learned positional encoding (LPE) based on  eigenvalues and eigenvectors information from the graph Laplacian is designed to make Transformer work better on graph data. Experimental results show that the proposed method is effective on several important tasks. Most reviewers see the technical value of the paper, and agree that using graph Laplacian in the learning of positional encoding is a good idea. On the other hand, some concerns have been raised, mainly regarding the computational complexity and the completeness of the experimental results. The authors did a good job in providing their rebuttals, and after several rounds of discussions, the reviewers came to a consensus on the positive side. As a result, my recommendation is ACCEPT as a poster.
Decision: Accept (Poster)