Diffusing Graph Attention
Authors: Daniel Glickman
Eran Yahav
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Transformer
graph neural networks
transformers
long-range context

Abstract: The dominant paradigm for machine learning on graphs uses Message Passing Graph Neural Networks~(MP-GNNs), in which node representations are updated by aggregating information in their local neighborhood. Recently, there have been increasingly more attempts to adapt the Transformer architecture to graphs in an effort to solve some known limitations of MP-GNN. A challenging aspect of designing Graph Transformers is integrating the arbitrary graph structure into the architecture. We propose \emph{Graph Diffuser}~(GD) to address this challenge. GD learns to extract structural and positional relationships between distant nodes in the graph, which it then uses to direct the Transformer's attention and node representation. We demonstrate that existing GNNs and Graph Transformers struggle to capture long-range interactions and how Graph Diffuser does so while admitting intuitive visualizations. Experiments on eight benchmarks show Graph Diffuser to be a highly competitive model, outperforming the state-of-the-art in a diverse set of domains.

Under review as a conference paper at ICLR 2023
DIFFUSING GRAPH ATTENTION
Anonymous authors Paper under double-blind review
ABSTRACT
The dominant paradigm for machine learning on graphs uses Message Passing Graph Neural Networks MMP-GNNs), in which node representations are updated by aggregating information in their local neighborhood. Recently, there have been increasingly more attempts to adapt the Transformer architecture graphs an effort to solve some known limitations of MP-GNN. A challenging aspect of de- signing Graph Transformers architecture. We propose Graph Diffiuse (GD) to address this challenge. GD learns to extract structural and positional relationships between distant nodes the graph, which it then uses to direct the Transformer's attention and node repre- sentation. We demonstrate that existing GNNs and Graph Transformers struggle capture long-range interactions and how Graph Diffuser does while admitting intuitive visualizations. Experiments on eight benchmarks show Graph Diffuser be highly competitive model, outperforming the state-of-the-art in a diverse set of domains.
integrating the arbitrary graph structure into the
INTRODUCTION
Graph Neural Networks have seen increasing popularity as a versatile tool for graph representation learning, with applications in wide variety of domains such as protein design re.g..Ingraahan et al.
(2019) and drug development (e.g.. [Gaudelet et al. (2020). The majority of Graph Neural Net- works (GNNs) operate by stacking multiple local message passing layers Gilmer et al. (2017). 7) in which nodes update their representation by aggregating information from their immediate neigh- bors Li et al. ( Kipf & Welling (2017); Hamilton et al. (2017): Veličković et al. (2018); Wu
ct al. 2019a
Xu ct al. (019bb).
In recent years, several limitations of GNNs have been observed by the community. These include under-reaching Barceló et al. (2020), over-smoothing Ww et al. (2020) and over-squashing Alon
& Yahav (2021) Topping al. (2022). Over-smoothing manifests node representations of well- connected nodes become indistinguishable after sufficiently many layers, and over-squashing occurs when distant nodes do communicate effectively due to the exponentially growing amount of messages that must get compressed into fixed-sized vector. Even prior to the formalization of these limitations, was clear that going beyond local aggregation is essential for certain problems Atwood & Towsley 2016); Klicpera et al. (2019).
Since their first appearance for natural language processing, Transformers have been applied to do- mains such as computer vision Han et al. (2022)) robotic control Kurin et al. (2020), and biological sequence modeling/River
(ision(Han
al. (2021) with great success. They improve previous models' expressiv- ity and efficiency by replacing local inductive biases with the global communication of the attention mechanism. Following this trend, the Transformer has been studied extensively in recent years as way to combat the issues mentioned above with GNNs. Graph Transformers (GTs) usually integrate the input into the architecture by encoding node structural and positional information as features or by modulating the attention between nodes based their relationships within the graph. How- ever, given the arbitrary structure graphs, incorporating the input into the Transformer remains a challenging aspect in designing GTs, and so far, there has been universal solution.
We propose a simple architecture for incorporating structural data into the Transformer, Graph Dif- fuser (GD). The intuition that guides us is that while the aggregation scheme of GNNs is limited, the

---

Under review as a conference paper at ICLR 2023
propagation of information along the graph structure provides valuable inductive bias for learning on graphs.
Figure I shows overview of our approach. We start with the graph structure (as shown the left) and construct Virtual Edges (middle) that capture the propagation of information between nodes at multiple propagation steps. This allows approach zoom out of the local message passing and relates distant nodes that do not have direct connection the original graph. We then use the virtual edges to direct the transformer attention (shown the right) and node representations.
0.1
B
B
0.4
0.3
0.7
D
D
Stack & Edge-Wiis FFN
Edge-Wise projection
0.3
0.7
O.
O
0.1 0.2 033
0.4
Figure 1: Illustration of our positional attention, focusing node B. Information propagation from multiple propagation steps is combined to create Virtual Edges(colored) between distant nodes, which then direct the Transformer's attention each layer.
In the following sections, we first show that existing GNNs and Graph Transformers struggle to model long-range interactions using a seemingly trivial problem. We follow by defining Graph Diffuser and then show how it solves the same problem. Finally, demonstrate the effectiveness of our approach on eight benchmarks spanning multiple domains by showing it outperforms state- of of-the-art art with hyperparameter tuning.
RELATED WORK
Message Passing Graph Neural Networks (MP-GNNs) MP-GNNs Gori al. (2005); Scarselli jet al. (2008) have been the predominant method for graph representation learning recent years, and have been applied to wide variety of domains (c.g.. Kosaraju et al. (219); Nathani et al.
(2019) : Wang et al. (2019); Huang & Carley] (2019); Yang et al. (2020): Ma et al. (2020): Wu et al.
2020 : Zhang et al. (2020). MP-GNNss update node representation by stacking multiple layers in
which each node aggregates information from its local neighborhooq Li et al. (2016); Kipf & Welling
(2017) Veličković al. (2018): Wu al. (2019a); Xu al. (2019b); Hamilton al. (2017); Xu
ct al. (2019a). However, as mentioned above, they suffer from under-reaching Barceló et al. (2020), over-smoothing Wu et al. (2020) and over-squashing Alon Yahav (202T): Topping et 2022
Several works have addressed the problem of over squashin..... Gilmer et al. (2017) add "virtual edges" to shorten long distances, and Scarselli et al. (2008) add "supersource nodes" None of these
works, however, integrate such virtual nodes or edges into the Transformer. Another line of work uses the attention mechanism Veličković al. (20T8): Brody al. (2022) to dynamically propagate information in the graph rather than use the original adjacency matrix Laplacian.
Graph Transformers (GTs) Considering their successes in natural language understand- ing Vaswani et al. (2017): Kalyan et al. computer vision d' A'Ascoli al. (202I): Han et al.
2002g; Guo et al. (2021). robotic control Kurin et al. (2020) and a variety of other domains, there have been numerous attempts to apply Transformers graphs. These works add positional encod- ing as node features, similar to the encoding in Vaswani et al. (2017), ) or use relative positioning to bias the attention between nodes, similar to Shaw al. (2018) Others combine Transformer with
2

---

Under review as a conference paper at ICLR 2023
local MP-GNN models by interleaving Rampäšek et al.
(2022) stacking them Jain et al. 202
much in the same way the Transformers were stacked on top of CNNs in computer vision Carion
et al. (020). Early Graph Transformer works Dwivedi & Bresson (2020) used the graph Laplacian eigenvectors as the node positional encoding (PE) to provide a sense of nodes' location in the input graph. Kreueer al. (202T) significantly improved this idea by using invariant aggregation for the eigenvectors. Since then, there have been many recent works constructing PE from the Lapla- cian Lim et al. (2022): Beaini al. (202I): Wang al. (2022); Lim al. (2022), well other structural or positional information such as the node degree Ying et al. (2021) and random- wall SE Dwivedi al. (2022a). Relative positioning was applied with great success on large molecular
benchmark by Graphormer Ying et al. (2021): ) (Shi et al. (2022) by using pair-wise graph distances to direct the Transformer's attention. Further, GraphiT|MMaal Miaaon et al. (2021) used relative positions between nodes derived from the random walk kernel to bias the attention but heuristically chose single random walk length. In contrast, Graph Diffuser learns to combine multiple distances. Since then, various works(e.g SAT Chen et al. (2022), applied the graph structure as soft bias to the attention. However, all of the works above use the original adjacency matrix Laplacian to learn positional relative encoding, unlike this work that learns the adjacency matrix using node and edge features.
et al. (202I). GRPE et (2022)
Diffusion Diffusion and other distance measures
used before increase the expressivity of MP-GNNs Li et al. (2020b), replace the local message passing scheme( Atwood & TTowley (2016);
Wu al. (2019b]; Klicpera al. (2019; 2018)) or modulate the Transformers attention Mialon al. (2021). None of these works, however, combines information from multiple different propagation steps.
To the best of our knowledge, this work is the first Graph Transformer to: (1) learn to construct new adjacency matrix using node and edge features generate positional or relative encoding, and (2) learn to combine information propagation over multiple different propagation steps in an end-to-end manner.
example of 5 5 grid. Nodes colored in out of 20 colors. The goal is to predict, in the same row or column have the same color. For example, node 23, at the bottom row, has only single node (node 20) that has the same color(green) and is in the same row column with node 23. Therefore, its label 1. The label for node 6 is 2, since matches with nodes 21.
node, how many other nodes
2
2
3
0
2
3
4
7
5
8
5
6
9
|
12
X
10
13
11
12
15
16
17
19
15
16
17
18
19
15
16
17
18
19
21
22
24
21
22
28
24
Position Attention
Content Attention
(b) Visualization of the position and content attention our trained model gives node 23 in the input graph shown in [a] The model learns to pay attention nodes in same row and column using positional attention and to nodes of the same color using content attention. Their element-wise product selects only the relevant nodes for solving the task.
Figure 2: An example of 2D Grid Histogram Counting with 5 grid. 2a shows the original graph. shows the attention patterns our model learns for node 23 the graph.
3

---

Under review as a conference paper at ICLR 2023
3
WHY DO WE NEED ANOTHER GRAPH TRANSFORMER?
Given the successful application of Transformers to other domains and the flurry of recent Graph Transformers, it is natural to ask why is there need for another Graph Transformer?
To illustrate the difficulties of current GNNs and Graph Transformers in modeling interactions in graph, we use simple synthetic node classification task. Counting the frequencies of tokens in sequence is an elementary task that Weiss et al. (202I) showed the original Transformer could easily solve. We propose a simple extension of this task to graphs: In Grid Histogram Counting (Figure 2) we generate N x M grids with randomly colored nodes and ask models to predict, for each node, how many other nodes in the same row or column have the same color. This is contrived problem but illustrates many real-world problems' needs. Solving it requires far away nodes to communicate, and the communication should consider both the nodes' content (color) and relation within the graph (being in the same row column).
This is straightforward generalization of the 1D sequential problem that Transformer easily solves to 2D graph. However, as show in Section 5.1.2 it defeats all existing GNN and Graph Transformer techniques, while Graph Diffuser succeeds.
GRAPH DIFFUSER
Feed Forward
Mlutt--Hadd Attention
Positional Attention
Content Attention
Stack Edge-Wiss FFN
Edge Wise Projections
Weighted Adjacency
Feed Forward
Multi-Head Attention
Positional Attention
Content Attention
E
Figure 3: An illustration of Graph Diffuser with 2 Transformer layers. Virtual Edges created by combining multiple powers of the weighted adjacency matrix(left). Virtual Edges modulate each of the Transformers attention layers(right). Virtuul Edges are added to the Transformer input as positional encoding(bottom right)
We now describe our approach for taking a graph G A) with node embeddings matrix X and edges A and processing it using the Transformer, which usually takes only a single matrix X as input. Our approach consists of 2 stages, illustrated in the left and right halves of Figure First, GD embeds the structural relations between distant nodes in what we refer to as Virtual Edges. Then, the Transformer processes the nodes while using the virtual edges direct the computation different layers.
4.1 VIRTUAL EDGES
Virtual Edges are high-dimensional representations constructed between distant nodes in the graph. They contain rich information the structural and positional relationships.
4

---

Under review as a conference paper at ICLR 2023
4.1.1 POWERS OF THE ADIACENCY MATRIX
To consider relations between distant nodes, the first step broadening the receptive field on which the architecture operates. In a row-normalized adjacency matrix A, A,, corresponds to the proba- bility of getting from node node j in le step random walk. We stack different powers of into 3 dimensional tensor E E Raxaxk
E = [||
(1)
where k is the number of stacks and denotes stacking matrices along the 3ed dimension and is the identity matrix.
Multiplication by the adjacency matrix closely related to the aggregation scheme MP-GNNS) Xu al. (2018), however, considering multiple powers of the matrix once, we zoom out of the local Message Passing paradigm and discover information that GNNs may not detect. Virtual Edges contain structural information such as nodes are on an odd length cycle, can distinguish many non-isomorphic graphs, and cover many distance measures such as shortest distance and generalized PageRank et al. 2020b).
4.1.2 EDGE- WISE FREEDFO NETWORK
In order to mix information between different propagation steps and extract meaningful structural relations, each stack is processed by fully connected edge-wise feed-forward network. Each layer consists of hidden layer with batch norm, ReLU activation, and a residual connection.
Edge- Fi (F,)) (B
(2)
Eij- Edge-FFN(EE)) +
(3)
The Edge- Wise FFN consists of 2 such layers and we apply batch norm on the input, before the first layer. This network is applied once, before any of the Transformers layers.
4.1.3 WEIGHTED ADIACENCY
Rather than using the original adjacency matrix in equation 1 we found it beneficial to learn new adjacency matrix using the node and edge features.
As Re.UU Wi))
(4)
Aij normalize(a (A.g))
(5)
Where means contacting vectors, a is the sigmoid function and noramlize means 11 row normal- ization. Tn Rd, 6xj E Rdeagr, W, E R[2d+deage) and W2 E R2dx1, If there are no edge features, we use only the nodes. This aligns with existing approaches such GAT (Veličković et al. 20018 : Brody et al. (2022)) ), which find beneficial to dynamically learn a new adjacency matrix.
4.2 INTEGRATING WITH THE TRANSFORMER
Most Graph Transformers use the graph structure to either alter the node's representations or to affect the attention mechanism itself. Graph Diffuser combines the 2 approaches. In the input layer, Self-Virtua Edges are added to the node representation as positional encoding, and each attention layer, the Virtual Edges are reduced to an attention matrix that is combined with the standard dot- product attention.
4.2.1 ATTENTION
At each of the Transformer attention layers, we linearly project each virtual edge Eiy separately to get the positional attention score between i and j.
Position
Att
E.g W,
(6)
Omitting bias for elearity
5

---

Under review as a conference paper at ICLR 2023
We then combine the positional attention and the content(dot-producc) attention scores and apply row-wise normalization.
QK?
Content
Att
Vd t/
Att normalize(erp( Att
Content
④ a (Att Position)
(8)
Where a is the sigmoid function and @ means element-wise multiplication. In multi-head attention with h heads, the projection in equation G done times.
equation 8 can be viewed as scaling the content attention coefficients based on the positional atten- tion. As we will see in the next section, separating the attention based on content and positions and then combining them seems to assist with learning meaningful connections in the data and provides a natural visualization mechanism.
4.3 POSITIONAL ENCODING
Self- Virtual-Edges. Ea, are Virtual Edges between node itself. They contain important struc- tural information. such as whether the node is part of an odd length cycle and the degrees of adjacent nodes. We project Self- Firtual-Edger the node's representation dimensionality and add them as positional encoding.
X; = X; + Relu Relu(E, Wpe)
Where W pe Rlexd
Self-walks were shown (Dwivedi et al. (2022a) to be an effective positional encoding. Adding such features to the node representations allows the Transformer structural information in all of its layers, including the feed-forward network.
EXPERIMENTS
5.1 GRID HISTOGRAM COUNTING
5.1.1 SETUP
We generate 10k grids of size x k, where & E {10, 12, 13) with node colors uniformly from set of 20 colors, and split them into 8k/1k/1k train/valid/test sets. The task is cast node multi-class classification task, where each node representation is used to predict the number of other nodes in the same row or column with the same color, illustrated in Figure 2a More details in Appendix A.I
5.1.2 RESULTS
Table I: Grid Histogram Counting average accuracy and s.d over 10 different seeds. GNN-> Transformer refers Transformer blocks stacked top of GNN (Jain al. (2021)) and GNN Transformer refers to combining Transformer and GNN blocks in the same layer (Rampášek
al. )022
Model
Accuracy f
Parameters
GNN
0.4832 +0.003
68k
Transformer
0.44 +0.003
53k
Transforme++RWPE
0.4797 =0.0044
53k
Transformer+SinNNee
0.488 +0.003
72k
GNN
+ Transforner
0,4795 +0.003
44k
GNN
RWWP
0.534 +000043
86k
Graph Diffuser position only
0.6073 +0.011
34k
Graph Diffuser
0.9755 + 0.025
43k

---

Under review as a conference paper at ICLR 2023
Table shows the results. First, we observe that the vanilla Transformer, which easily solves the histogram task over sequential input, fails here and performs the worst. This is not surprising as the Transformer is oblivious to the graph structure. Next, we observe that RWPE/Dwivedi et al. (2022a), a popular positional embedding technique, improves very slightly over the base Transformer. This may be because RWPE is unable to detect symmetries in the graph. Nodes 0,4,20 and 24 in the ample illustrated in Figure 2a will all get the same embedding by RWPE. Adding SignNet[Lim et al. (022), theoretically expressive positional embedding technique based on the graph eigenvectors, does not yield much improvement either. This may indicate difficulties learning useful embeddings in eigenvectors based techniques. The GNN baseline, which in theory can solve the task, achieves 0.483 accuracy. This may be due to the over-squashing phenomenon. Indeed in 10 x 10 grid, passing information between opposing nodes the same row will require 9 message passing layers to deliver a single message that has been "squashed" with nearly 90k other messages. Next, we observe that using only positional anteentionwithhutt dot- dot-product attention) performs the second best while having the least parameters. Finally, Graph Diffuser nearly solves the task entirely by com- bining both positional and content attention. Looking at Figure 2b we can see the model learns to use the different attention mechanisms in an intuitive way, with content attention detecting nodes in the same color and position attention detecting nodes in the same row or column.
5.2 BENCUMARKING GRAPH DIFFUSER
Throughout our experiments, we take an existing Graph Transformer architecture and use it "as is" as our Transformer module without doing any hyper-paramest search. That is, we take graph Transformer with the same hyperparameters used by the original work and only add our positional at- tention and encoding P For of the datasets, ZINC, OGBG- NGBGG-molpeha, molpeha. poa.code2). PCQM-Contace and PCQM4Mv2, we use the very competitive GPS [Rampášek et al. (2022) as the Transformer model. For the LRGB benchmarks, Peptides-func and Peptides-struct, there are no official GPS hyperparameters, and we use Transformer with the authors' bascline hyperparameters and CLS token added to the input. For a detailed hyperparameters report, see Table and
5.2.1 RESULTS
We evaluate our model on 8 datasets overall and compare our results with those of popular MP- GNNs, Graph Transformers and other recent state-of-the-art models. Graph Diffuser exceeds SOTA in 6 of them and achieves very competitive results in the rest. All results for the comparison methods are taken from the original paper or their official leaderboards.
ZINC Dwivedi et al. (2020a) is molecular regression dataset, where the value to be predicted is the molecule's constrained solubility. Table Table[]show shows the results, where we exceed SOTA results by a substitutional margin.
Open Graph Benchmark Hu et al. 2020) is a highly competitive benchmark with a variety of datasets. We evaluate GD on three graph-level prediction tasks from different domains and report the results at Table 3 OGBG-MOLPCBA is a multi-task binary classification dataset containing 438k molecules, and the task is to predict the activity/inactiiity of 128 properties. Here we rank the second highest and the first among all GNN or Transformer architectures. OGBG-PPA consists of protein-protein interaction networks of different species, where the task is predicting the category of species the network is from. The previously highest-ranking model is GPS, and adding our positional attention and encoding it proves to be efficient strategy that reaches a new state-of- the-art. OGBG-CODE2 contains Abstract Syntax Trees(ASTs) of Python methods, and models are tasked with predicting the methods' names. The average distance between nodes in this dataset is larger than that of any other dataset in our experiments, which can explain why Graph Transformers variations dominate its leaderboards. Since positional encoding was not found to be significant by the previous three highest ranking models in this dataset, and considering the large improvement of our model over GPS, it seems that positional attention brings significant benefits in this benchmark, which allows us to reach new state-of-the-art, OGB-LSC PCQM4Mv21 Hu et al. (2021) is large- scale molecular dataset with over 3.7M graphs. Here, our results are similar to GPS, which ranks highest among Graph Transformers variations. Our results lag behind only GEM-2 Liu et al. 2002) which was designed specifically for modeling molecular interactions.
We remove any positional encoding used by the original work.

---

Under review as a conference paper at ICLR 2023
Table 2: MAE for the ZINC dataset from Dwivedi
2020b).
Model
MAE 4
GCN & We Winling
2017
0.367 = 0.011
GIN XN er al. 2019a
0.526 0.051
GAT Velicović et 2018
0.384 0.007
Ga Bresson & Laurent 2017
Dwivedi et al 2020h
0.282 * 0.015
GatedGCN-LSPE DD Dwivedi al 2022
0.090 + 0.001
CRaW] Toenshoff et al. (022T
0.085 0.004
GIN-AK+ZZaa et ala 2024
0.080 0.001
SAN Kreuzer et al (2021)
0.139 + 0.006
Graphoomer Ving al. 2021
0.122 0.006
K-Suberaph SAT Chien e A.
2022
0.094 0.008
GPS Rampášck et al. 2022
0.070 0.004
Graph Diffuser(ours)
0.0683 0.002
Long Range Graph Benchmark Dwivedi et al. (2022b) is recently proposed dataset specifically designed to evaluate models on their ability to capture long- range interactions. We are the first, other than the author's 's baselines, evaluate our model on these datasets and currently rank first in all of them. Peptides-func and Peptides-struct are multi-label graph classification and regression datasets containing 15.5k Peptides molecular graphs. They are particular interest since the molecules in them consist of many more nodes, average, than the other molecular datasets in our experiments. As we can see Table adding our positional attention and encoding outperforms both RWSE and LapPE encodings. PCQM-Contact is molecular dataset with edge prediction task of predicting two atoms interact. Our results are reported in Table 6
Table 3:
Test results in OGB graph-level benchmarks Hu et al. (2020). Pre-trained or ensemble models are not included. Bold:first, Underlined:
oghg-molpcha
oghg-ppa
ogbg-code2
Model
Avg. Precision
Accuracy f
score t
GCN-virtual node Kipf & Welling (017))
0.2424 + 0.0034
0.6857 = 0.0061 0.7037 + 0.0107
0.1595 # 0,0018
GiN+virrual node Xu cl al. 2019a)
0.2703 + 0.0023
0.1581 + 0.0026 0.1570 + 0.0032
PNA CNrrCorso et al. (020)
0,2838 + 0.0035
GIN-AKFiZlan Zhao èl 2022
0.2930 + 0.0044
DeeperGCN Li al 20200
0.2781 + 0.0038
0.0772
DGN Beaini er al 2021
0.2885 1 0.0030
CRaW] Toenshol al. (2021)
0.2986 + 0.0025
ExpC Yang et al. 2022
0.2342 + 0.0029
0.7976 # 0.0072
SAN Kreuzer et al. (2021)
0,2765 + 0.0042 0.2761 + 0.0029
Graph Trans (GCN- Vintual Jain al. 2021
0.1830 + 0.0024
K- SuSrrree SAT Chen et (2022)
0.7522 + 0.0056 0.8015 + 0.0033
0.1937 + 0.0028
GPS Rampašek еt al. 2022
0.2907 + 0.0028
0,1894 + 0.0024
Graph Ditfuser
0.2931 + 0.0034
0.8133 # 0.0057
0.1941 # 0.0914
Table 4: Evaluation on PCQM4Mv2 Hu al. 2021).
Since the test labels are private, 150k examples from the train set as our validation and the validation set is treated as the test set.
Model
MAE J
Param.
GCN G & Welling 2017)
0.1379
2.0M
GCN-virual
0.1153
4.9M
GIN Xu et al. 2019a
0.1195
3.8M
GiN-virtua
0.1083
6.7M
GRPE et al. 2022
0.0890
46.2M
RGT Hussain e all 2021
0.0869
89,3M
Graphirmet Shi el di 2202
0.0864
48.
GP$ Rampásck al.
0.0858
19.4M
GEM et 2022
0.0806
32.0M
Graph Diffuser(ours)
0.0867
20.3M
8

---

Under review as a conference paper at ICLR 2023
Table 5: 2022b
Evaluation on the recently suggested Peptides-fune and Peptides-struct
Dwivedi al.
Peptides-func
Peptides-struct
Model
Params.
f
MAE 4
GCN
508k
0.5930=000022
0.3496=0.0013
GINE
476k
0.5498:10.0079
0.5547=0.0055
GatedGCN
509k
0.5864=0.0077
0.3420=0.0013
GatedGCN+RWSE
506k
0.6069=10.0035
0.3357=0.0006
Transforme++I LapPF:
488k
0.6326+0000126
0.2529
SAN+LapPE
493k
0.638410.0121
0.2683=0.0043
SAN+RWSE
500k
0.6439=10.0075
0.2545=0.0012
Graph Diffuser
509k
0.665110.001
0.2461=0.001
Table 6: Comparison with the baselines in the PCQM-Contan dataset.
Model
# Params.
Hits f
Hits@3 f
Hits @ 10 f
MRR
GINE
517k
0.1337+0.0013
0.3642++0.003
0.8147+0.0062
0.3180-0.0027
GCN
504k
0.3791110.0004 0.132111.0000
0.825611.00006
0.3234-0.0006
GatedGCN
527k
0.127910.0018
0.3783-10.0044
0.8433:10.0011
0.3218=0.0011
GatedGCN+RRSS
524k
0.1288++00001
0.3808++000006
0.8517++00005
0.3242=000008
Transformer+LapPH
502k
0.1221110.0011
0.3079.1..033
0.85171100003
0.3174-0.0020
SAN+LapPE
499k
0.1355=0.00117
0.4004+:00002
0.8478+0.0044
0.3350=0.0003
SAN+RWSE
509k
0.1312::000166
0.403011000008
0.8550+10.0024
0.3341=000006
Graph Diffuser(ours)
521k
0.1369+
0.0012
0.4053
0.0011
0.8592 0.0007
0.3388+ 0.0011
CONCLUSION
In this work, introduced simple and effective architecture for machine learning graphs, Graph Diffuser. Using a controlled example, we demonstrated its effectiveness in modeling long- range interactions while providing better interpretability. We then showed that this translates to real-world problems by evaluating GD on eight benchmarks from multiple domains. With minimal hyperparameter tuning, Graph Diffuser achieves a new state-of-the-art on most datasets and reaches very competitive results on the rest.
In the future, we plan integrate Graph Diffuser with other promising Graph Transformer compo- sitions, such as Transformers stacked on top of GNNs. Another area of interest is amplifying virtual edges, for example, by considering paths between nodes rather than just information propagation.
Limitations Our architecture integrates with the Transformer and consequently suffers from the quadratic memory complexity of the attention mechanism, which can restrict its applicability to larger graphs.
REPRODUCIBILI STATEMENT The authors support and advocate the principles of open science and reproducible research. We describe Graph Diffuser in detail in the text and figures and mention all relevant hyperparameters to reproduce our experiments the appendix. Moreover, we will release code as open-souree with clear instructions on how to reproduce all of our results, as well as how to extend our model and apply it to new datasets.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference Learning Representations, 2021. URL https::////// https://openrevi ew net. forum? iowrrummmiiiie 1000=1000000002220
James Atwood and Don Towsley. Diffusion--oonvllttinnn neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016. 2016.

---

Under review as a conference paper at ICLR 2023
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. URL
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748- 758. PMLR, 2021.
Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arXiv: 2017.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations, 2022. URL BRLLLtttsss//peeneeeee..ec
or
7C1
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and
Sergey Zagoruyko. End-to-end object detection with transformers, 2020. URL https:
Dexiong Chen, Leslie O' Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. arXiv:2202.03036, 2022.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 01132600-3271,, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00900 000922 2020a.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003.00982 2020b.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark, 2022b. URL /RKL/tttps/://xxwvoorr
abs/ 2206. 08164
Stéphane d' A'Ascoli, Hugo Touvron, Matthew L Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. In Inter- national Conference on Machine Learning, pp.
PMLR, 2021.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Thomas Gaudelet, Ben Day, Arian R. Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy B. R. Hayter, Richard Vickers, Charles Roberts, Jian Tang, David Roblin, Tom L. Blun- dell, Michael M. Bronstein, and Jake P. Khylor-KKigg, Utilising graph machine learning within drug discovery and development, 2020. URL https: /tctts://arxiv... org/ abs/ 2012200222222 05716
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1263-1272 JMLR. org, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 734-734, IEEE, 2005.
Jianyuan Guo, Kai Han, Han Wu, Chang Xu, Yehui Tang, Chunjing Xu, and Yunhe Wang. CMT: Convolutional neural networks meet vision transformers. arXiv:2107.06266 2021.
10

---

Under review as a conference paper at ICLR 2023
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey vision transformer. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
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. 34th Conference on Neural Information Processing Systems, 2020.
Weihua Hu, Matthias Fey. Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB- LSC: A large-scale challenge for machine learning on graphs. In 35th Conference on Neural Information Processing Systems: Datasets and Benchmarks Track, 2021.
Binxuan Huang and Kathleen M Carley. Syntax-aware aspect level sentiment classification with graph attention networks. In Proceedings of the 2019 Conference on Empirical Methods Nat- ural Language Processing and the 9th International Joint Conference on Natural Language Pro- cessing (EMNLP-IJCNLP), pp. 5472-5480, 2019.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Edge- adge-augmented graph transformers: Global self-attention is enough for graphs. arXiv:2108.03348, 2021.
John Ingraham, Vikas K. Garg, Regina Barzilay, and Tommi Jaakkola. Generative models for graph- based protein design, 2019.
Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34, 2021.
Katikapalli Subramanyam Kalyan, Ajit Rajasekharan, and Sivanesan Sangeetha. Ammus: A survey of transformer-basee pretrained models in natural language processing. 108.v:2/08.05542 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffiusion Improves Graph Learning. Curran Associates Inc., Red Hook, NY, USA, 2019.
Vinect Kosaraju, Amir Sadeghian, Roberto Martin-Martin, Ian Reid, Hamid Rezatofighi, and Silvio Savarese. Social-bigat: Multimodal trajectory forecasting using bicycle-ge -an and graph attention networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-But E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019. URL URL/htttts://p/oeeeeeii http://rcccceiiinn...eeeiii..pp. www.inen.i...mm http://c....ppppp/////////////// (G336444cc07772233333-3P-88
pdf
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Infor-
mation Processing Systems, 2021.
Vitaly Kurin, Maximilian Igl, Tim Rocktäschel, Wendelin Boehmer, and Shimon Whiteson. My body is a cage: the role of morphology in graph-based incompatible control. CoRR, abs/2010.01856, 2020.
wwwpaliv..rga/a//////0/ http:///bb/221..0000 01856
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, 2020a. https:: //arxvv.vvv//v/////a//aaa/aaaai/ org/ hatg//bs//ie attpaabs/..///////// 07739
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 14-4465-4478 2020b.
11

---

Under review as a conference paper at ICLR 2023
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra. Haggai Maron, and Ste- fanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202.13013 2022.
Lihang Liu, Donglong He, Xiaomin Fang, Shanzhuo Zhang, Fan Wang, Jingzhou He, and Hua Wu. Gem-2: Next generation molecular property prediction network with many-body and full-range interaction modeling, 2022. URL httt::tp:://ee /ttp/aaaiiivv... wtg.gb/////aaaaaa.
abs/ 22088 05863
Nianzu Ma, Sahisnu Mazumder, Hao Wang, and Bing Liu. aaare dependency-basee deep graph attention network for comparative preference classification. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 5782-5788, 2020.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT:: Encoding graph structure in transformers. arXiv:2106.0566h 2021.
Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention-base em- beddings for relation prediction in knowledge graphs. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4714--10-0 4710-4723, 2019.
Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung won Hwang. GRPE: Rela- tive positional encoding for graph transformer. arXiv:2201..22787, 2022.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. arXiv:2205. 12454, 2022.
Alexander Rives, Joshua Meier, Tom Sereu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C. Lawrence Zitnick, Jerry Ma, and Rob Fergus. Biological structure and function emerge from scaling unsupervised learning to 250 millionn protein sequences. Proc. Nail. Acad. Sci. USA, 1 11((15)e20162391 18, 2021. URL 39118
2016. 62
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2008.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. CoRR, abs/ 180.00253,, 2018. URL
wtt.://////.........//// 02155
Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo. Chang Liu, Di He, and Tie- Yan Liu. Benchmarking graphormer large-scale molecular modeling datasets. 2001v:2203.04810. 2022.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1 convolu- tions on random walks. arXiv:2102.08786, 2021.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations, 2022. URL httpppss//ppeeeeeeew....
Bronstein.
orum?id (eumm?dd7Ummjp JRm
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances Neural Infor- mation Processing Systems, pp. 6000-6010, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
12

---

Under review as a conference paper at ICLR 2023
Haorui Wang. Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representa- tions, 2022.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 2022-2032, 2019.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers, 2021. URL https:
//axxiv.org/ab//2000 06981
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference machine learning, pp- 6861-6871. PMLR, 2019a.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks, 2019b. URL htt.thh/s///xiiii orgg ab
8/1902. 07153
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp. 5453-5462, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference on Learning Representations, 2019b. URL https:
//openreview. wwt.://ttttommdityaaeaaa A5Km
Mingqi Yang, Renjian Wang, Yanming Shen, Heng Qi, and Baocai Yin. Breaking the expression bottleneck of graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Yiding Yang, Jiayan Qiu, Mingli Song, Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, 2021.
Jiaxuan You, Rex Ying, and Jure Leskovee. Design space for graph neural networks. In Advances in Neural Information Processing Systems, 2020.
Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In International Conference on Learning Representations, 2020. URL http
s: s://openreview net.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
A APPENDIX
A.1 IMPLEMENTATION DETAILS FOR THE GRID HISTOGRAM COUNTING TASK
We generate 10k graphs and split them into Sk/lk/Ik train/val/test sets. Each grid is of size 10 x k where k (10, 11, 12, 13). Node colors are drawn uniformly from set of 20 colors. We search
13

---

Under review as a conference paper at ICLR 2023
over learning rates in (3c-4, 4, repeat each experiment with ten different random seeds and report the average and standard deviation of the best configuration. All models have a hidden dimension of 32. We use GatedGCN GNN modules, and four attention heads in Transformer modules. Transformer models use six layers, GNN N + Trans transformet former uses 3 GNN layers and Transformer layers. GNNS model has 12 layers to avoid underreaching. For Graph Diffuser, found layers sufficient. We use 0.2 dropout for GNN's modules and 0.5 dropout for attention. For the Diffuser model, we found no need for dropout.
A.2 THE EFFECTS OF GD ON GRAPH TRANSFORMER VARIATIONS
We Conducted simplified experiment to see the effects of GD when used as out-of-the-box addition to different Transformer compositions, with no hyperparameter tuning. We evaluated Transformer variations: Transformer, Transformer layers stacked top of GNN layers (GNN - Transformer), and Transformer interleaved with GNN the same layer GNN | Transformer). For each variation, evaluate the unmodified architecture with no positional embedding positional attention, the architecture with our positional encoding and attention added, but not learning the adjacency matrix(+ Graph Diffuser), and one learn new weighted adjacency matrix(+ Weighted Adjacency), as described in Section 4.1.3 The results are in Table
The effects of our architecture on different Graph Transformers. Adding positional en- coding and attention improves all Transformer baselines. Learning weighted adjacency improves
Table 7:
combinations, but not the vanilla Transformer.
OGBG-PPA
ZINC
Model
Accuracy
MAF
Trunsformer
0.09483
0.7043
+ Graph Diffuser
0.7676
0.152
Weighted Adjacency
0.7750
0.1611
GNN - Transformer
0.3896
0.2068
+ Graph Diffuser
0,4954
0.1225
Weighted Adjacency
0.6372
0.1160
GNN Transformer
0.6793
0.1516
+ Gruph Diffuser
0.7866
0,0880
Weighted Adjacency
0.7931
0.08671
A.3 COMPUTATION ENVIRONMENT RESOURCES
Our implementation is based on the excellent open source Graph GPS implementation? which it self it based on Pyg and GraphGym Fey Lenssen (2019); You et al. (2020). We use machine ogbg-
with 24GB NVIDIA A10G GPU with 32GB or 64GB RAM for the larger datasets(ogbg- code2.PCQM4Mv22, and shared cluster equipped with NVIDIA TITAN Xp for the other datasets.
14

---

Under review as a conference paper at ICLR 2023
Table 8: Graph Diffuser hyperparameters for the OGB benchmarks.
Hyperparameter
ogbg-molpcba
ogbg-ppa
ogbg-code2
ZINC
Transformer/GPS Layers
3
4
10
Edge- Wise FFN Layers
2
2
2
number of stacks(k)
16
10
20
16
MP-NN
GatedGCN
GatedGCN
GatedGCN
GINE
Hidden dim
384
256
256
64
Transformer FFN multiplier
x2
x4
Attention Heads
4
8
4
Dropout
0.2
0.1
0.2
Attention dropout
0.5
0.5
0.5
0.5
Graph pooling
mean
mean
mean
sum
Batch size
512
32
32
Learning Rate
0.0005
0.0003
0.0001
0.001
Epochs
100
200
30
2000
Warmup epochs
5
10
2
50
Weight decay
1e
1e
1 5
Parameters
10646k
3050k
13912k
443h:
Table 9: Hyperparameters for ZINC and the LRGB datasets.
Hyperparameter Transformer/GPS Layers
ZINC
PCQM-Contact
Peptides-func
Peptides-struct
10
4
4
Edge Wise FFN Layers
2
2
2
2
number of stacks(k)
16
16
16
16
MP-NN
GINE
GatedGCN
Hidden dim
64
92
112
112
Transformer FFN multiplier
x2
x2
x2
Attention Heads
4
4
4
4
Dropout
0.
0.
Attention dropout
0.5
0.5
0.5
0.5
Graph pooling
sum
sum
CLS
CLS
Batch size
32
128
128
128
Learning Rate
0.001
0.0003
0.0003
0.0003
Epochs
2000
200
200
200
Warmup epochs
50
10
10
10
Weight decay
1c
0
0
Parameters
443k
5034
5094
509%:
15


Reviews:
[{"review_id": "hEXUacktldx", "reviewer": "Reviewer_6mkR", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper combines the graph diffusion with graph transformer models by updating the positional attention score with the edge representations attained from applying the MLP on top of the tensor for the diffusing operation. The proposed method performs favorably against other state of art models on real-world benchmark datasets. Particularly, the proposed method is able to solve the grid-histogram counting problem that other graph transformer fail to solve.", "summary_of_the_review": "The paper proposed a new variant of graph transformer by encoding the graph diffusion tensor as edge features and feed into the positional attention score. The proposed model empirically performs well on benchmark dataset. However, the technical novelty is limited as it is quite incremental. ", "strength_and_weaknesses": "Strength:\n1. The proposed method performs favorably on benchmarks datasets.\n2. The method is effective but is also quite simple in term of implementing it.\n3. The counter example of the 2-d grid histogram counting problem for graph transformer is interesting as all state of the art model fail to solve it.\n\nWeakness:\n1. The technical contribution is incremental. Graph diffusion (both in discrete and the ODE form) has been studied and applied in the domain of graph neutral network. While adding graph diffusion to the positional attention is new, it is a trivial extension. [1][2][3]\n2. While it is surprising that most graph transformer could not solve the grid based counting problem, this problem itself in the context of graph can be easily solved by diffusion matrix itself if node color is expressed as node feature with one-hot encoding. \n\n\n[1] https://papers.nips.cc/paper/2019/hash/23c894276a2c5a16470e6a31f4618d73-Abstract.html\n[2] https://aclanthology.org/2021.emnlp-main.642.pdf\n[3] https://openreview.net/forum?id=EMxu-dzvJk", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "djnw1weNmeJ", "reviewer": "Reviewer_NF2T", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper demonstrates a method called graph transformer on better integrating graph structures. The paper conducts a brief description on how there techniques is composed of and propose various of analysis on the effectiveness of graph diffuser on established benchmark.", "summary_of_the_review": "My major concern of the paper is the leak of literature reviews. The paper should involve more methods regarding to graph transformers and compare the performance with them to show the advantages of the proposed work.", "strength_and_weaknesses": "Strength:\n1. The paper presents two novel design for a graph transformer, the graph diffuser and context attention. \n2. The paper provides many experiments in different datasets to demonstrate the performance of their approach. \n3. The detail description of the experimental setup is also useful in understanding the benchmarks.\n\nWeakness:\n1. The authors should add more literature review. By googling \"graph transformer\", there is a survey [1] on arXiv that mentioned various methods regarding graph transformer. But some of those methods are not reviewed by the authors. Also, the experiments should include more baselines.\n2. When use weighted adjacency, the model does not leverage any information from original adjacency.\n3. More ablation study are needed to reveal the importance of each component. For example, context attention only, context attention + weighted adj, context attention + diffuser + weighted adj, and so on. \n\n[1] Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., ... & Rong, Y. (2022). Transformer for Graphs: An Overview from Architecture Perspective. arXiv preprint arXiv:2202.08455. (https://arxiv.org/abs/2202.08455)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ja9wQyvhOrB", "reviewer": "Reviewer_1vG8", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "In this work, the authors propose a new way to learn positional encoding in Graph Transformers by extracting relationships between distant nodes in the graph. To evaluate the proposed approach, the authors design a simple graph task, Grid Histogram Counting, as well as use several benchmark datasets.", "summary_of_the_review": "Overall, the proposed method solves the limitation of modeling long-range interactions in the current Graph Transformers. However, the novelty of the proposed method is limited given several existing related works. The effectiveness of the proposed method is not so significant on several benchmarks. The paper can be improved with more clear descriptions and illustrations. ", "strength_and_weaknesses": "Pros:\nThe experiments can effectively show the performance of the proposed method.\n\nCons:\n1. There are existing works [1, 2] about incorporating graph diffusion in attention-based GNN that are not covered in this work. Besides, in the Related Work section, the subsection \"Diffusion\" might be revised to \"Diffusion in Graph\" to avoid any ambiguity with \"Diffusion Models\". \n2. The improvement on many benchmarks is limited compared to the standard deviations.\n3. The models in Table 1 are not well described in the main context. For example, the settings of \"GNN →Transformer\" and \"GNN | Transformer+RWPE\" can be briefly mentioned in 5.1.1. Moreover, the necessity of designing \"GNN →Transformer\" and \"GNN | Transformer+RWPE\" for comparison is not clear.\n4. About the figure drawing: Figure 1 is a little hard to understand since it contains terms like \"Edge-Wise FFN/projection\" and unclear attention maps that are only described in the latter sections. The Transformer architecture in Figure 3 is not well drawn. The Positional Attention module is even partly outside the Multi-Head Attention module.\n\n[1] Wang, Guangtao, Rex Ying, Jing Huang, and Jure Leskovec. \"Multi-hop attention graph neural network.\" arXiv preprint arXiv:2009.14332 (2020).\n\n[2] Liu, Yonghao, Renchu Guan, Fausto Giunchiglia, Yanchun Liang, and Xiaoyue Feng. \"Deep attention diffusion graph neural networks for text classification.\" In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8142-8152. 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AQmVDeuLzdN", "reviewer": "Reviewer_6Q8a", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper proposes a new Graph Transformer architecture, Graph Diffuser, to incorporate structural information in graphs, particularly the long-range interactions. Specifically, Graph Diffuser first generates a dense adjacency matrix from the node and edge features, then obtains the virtual edge features by feeding the concatenation of k random walk matrices (computed from the generated adjacency matrix) through a feed-forward neural network. The produced virtual edge features are then used both for positional encoding (by taking the self virtual edges) and modifying the attention matrix directly. Experiments over both a synthetic task and 8 benchmarks are performed to show the performance improvements.", "summary_of_the_review": "Overall, the paper has limited novelty and contribution. The major novel contribution is improving long-distance interaction modeling by generating a dense adjacency matrix from node and edge features. But generating features between all pairs of nodes is inherently not scalable and even more expensive than the already expensive attention matrix.", "strength_and_weaknesses": "Strength\n- The method is motivated by the failure of current architectures over a synthetic task. The proposed method brings significant improvement to it.\n-  The method demonstrates empirical gains over some datasets, mostly on ones that requires capturing long-range interactions\n\nWeaknesses\n- Some important parts of the paper are confusing, mostly due to the ordering of the sections and the phrases:\n    - It is not clear to me what \"learn to combine information propagation over multiple different propagation steps in an\nend-to-end manner\" means. What are the \"multiple different propagation steps\"?\n    - The use of the phrase \"virtual edge\" is somewhat confusing. Based on the later formulas, it seems these virtual edges are essentially generated features between all pair of nodes (based on 4.1), and replace the original edges/edge features. But the phrase itself and Figure 1 makes it seem like the virtual edges are added to the original set of edges.  \n- Some of the statements seem to be over-claimed:\n    - \"However, given the arbitrary structure of graphs, incorporating the input into the Transformer remains a challenging aspect in designing GTs, and so far, there has been no universal solution. We propose a simple architecture for incorporating structural data into the Transformer, Graph Diffuser (GD)...\" It should be clarified that a lot of the current graph transformers designs are expressive enough incorporate arbitrary structure of graphs (e.g. Graphormer, GRAPHGPS, etc) and showed strong results. The authors should narrow down the claim to improving the modeling of long-range interaction.\n    - \"this work is the first Graph Transformer to [...] learn to combine information propagation over multiple different propagation steps in an end-to-end manner.\" It is not particularly clear to me what this statement means, but seems this is referring to feeding stacked random walk matrices through feed-forward neural networks in 4.1.2. I believe this has already been mentioned in GRAPHGPS and GraphiT (i.e. Relative PE using random walks).\n- The first step of learning a dense adjacency matrix could be very expensive for large graphs.\n- The empirical gain on ZINC and most of the OGB datasets seem quite small compared to the variance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject