Learnable Graph Convolutional Attention Networks
Authors: Adrián Javaloy
Pablo Sanchez Martin
Amit Levi
Isabel Valera
Venue: ICLR 2023 poster (2023)
Keywords: GNN
GCN
GAT

Abstract: Existing Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighbor- ing nodes, or by applying a non-uniform score (attending) to the features. Recent works have shown the strengths and weaknesses of the resulting GNN architectures, respectively, GCNs and GATs. In this work, we aim at exploiting the strengths of both approaches to their full extent. To this end, we first introduce the graph convolutional attention layer (CAT), which relies on convolutions to compute the attention scores. Unfortunately, as in the case of GCNs and GATs, we show that there exists no clear winner between the three—neither theoretically nor in practice—as their performance directly depends on the nature of the data (i.e., of the graph and features). This result brings us to the main contribution of our work, the learnable graph convolutional attention network (L-CAT): a GNN architecture that automatically interpolates between GCN, GAT and CAT in each layer, by adding only two scalar parameters. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide range of datasets, and resulting in a more robust model that reduces the need of cross-validating.

Published as a conference paper at ICLR 2023
LEARNABLE GRAPH CONVOLUTIONAL ATTENTION NETWORKS
Adrián Javaloy 1. Pablo Sánchez-Martin 1.2, Amit Levi
Isabel Valera 1,4
1 Depaarmeent of Computer Science of Saarland University, Saarbrücken, Germany Max Planck Institute for Intelligent Systems, Tübingen, Germany 3 HHuawei Noah's Ark Lab, Montreal, Canada MMx Planck Institule for Soflware Systems, Saarbrücken, Germany
ABSTRACT
Existing Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighboring nodes, by applying non-uniform score (attending) to the features. Recent works have shown the strengths and weaknessos of the resulting GNN architectures, respectively, GCNs and GATs. In this work, we aim al exploiting the strengths of both approaches to their full extent. To this end, we first. intuee the graph convolutional atlention layer (CAT), which relies on convolutions to compute the attention scores. Unfortunately, in the case of GCNs and GAT's, we show that there exists no clear winner between the three-neither theoretically nor in practice- as their performance directly depends on the nature of the data (i.c., of the graph and features). This result brings us to the main contribution of our work, the learnable graph convolutional attention network (L-CAT): a GNN architecture that automatically interpolates between GCN, GAT and CAT in each layer, by adding two scalar parameters. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide range of datasets, and resulting in a more robust model that reduces the need of cross-validating.
INTRODUCTION
In recent years, Graph Neural Networks (GNNs) (Scarselli et al., 2008) have become ubiqui- tous in machine learning, emerging as the standard approach in many settings, For example, they have been successfully applied for tasks such as topic prediction in citation networks (Sen et al., 2008); molecule prediction (Gilmer et al., 2017); and link prediction in recommender systems (Wu et al., 2020a). These applications typically make use of messag--passing GNNs (Gilmer et al., 2017), whose idea is fairly simple: in each layer, nodes are updated by aggregating the information (messages) coming from their neighboring nodes.
Depending on how this aggregation is implemented, we can define different types of GNN lay- ers. Two important and widely adopted layers are graph convolutional networks (GCNs) (Kipf & Welling, 2017), which uniformly average the neighboring information; and graph attention networks (GATs) (Velickovic et al., 2018), which instead perform a weighted average, based on attention score between receiver and sender nodes. More recently, number of works have shown the strengths and limitations of both approaches from a theoretical (Fountoulakis et al., 2022; Baranwal et al., 2021; 2022), and empirical (Knyazev et al., 2019) point of view. These results show that their performance depends on the nature of the data at hand (i.e., the graph and the features), thus the standard approach is to select between GCNs and GAT's via computationally demanding coossvalidatiin.
In this work, we aim to exploit the benefits of both convolution and attention operations in the design of GNN architectures. To this end, we first introduce novel graph convolutional attention layer (CAT), which extends existing attention layers by taking the convolvod
"Equal contribution. Correspondence to: (ajavaloy, sanchez) @cs. andd.de

---

Published as a conference paper at ICLR 2023
features imputs of the score function. Following (Fountoulakis et al., 2022), we rely on a contextual stochastic block model to theoretically compare GCN, GAT, and CAT architectures. Our analysis shows that, unfortunately, free lunch exists among these three GNN architectures since their performance, as expected, is fully data-dependent.
This motivates the main contribution of the paper, the learnable graph convolutional ottention network (L-CAT): a novel GNN which, in cach layer, automatically interpolates between the three operations by introducing only two scalar parameters. As result, L-CAT able to learn the proper operation to apply at each layer, thus combining different layer lypes in the same GNN architecture while overcoming the need cross- pooss-vlldatte-ae process that was prohibitively expensive prior to this work. Our extensive empirical analysis demonstrates the capabilities of T-CAT on wide range of datasets, outperforming existing baseline GNNs in terms of both performance, and robustness to input noise and network initialization.
2 PRELIMINARIES
Assume as input an undirected graph G= EV, where V= [m] denotes the set of vertices of the graph, and E S V x V the set of edges. Each node i E [n] is represented by d-dimensional feature vector X; E R4, and the goal is to produce a set of predictions {ú:) To this end, messago-passing GNN layer yields representation h; TRd for each node i, by collecting and aggregating the information from cach of its neighbors into a single message; and using the aggregated message to update its representation from the previous layer, h; E Rdd For the purposes of this work, we can define this operation as the following:
h = f(h() where h
del Σ
Mi Wohj.
(1)
JEN,
where N is the set of neighbors of node i (including i), W. E Rd'xd xd learnable matrix, an elementwise function, and "/y E [0, 1] are coefficients such that Σ, Mii = 1 for each node i.
Let the input features be h = X,, and h4 = ÿ; the predictions, then we can readily define a message-passingg GNN (Gilmer et al., 2017) as a sequence of L layers as defined above. Depending the way the coefficients "hy are computed, we identify different GNN flavors.
Graph convolutional networks (GCNs) (Kipf & Welling, 2017) are simple yet effective. In short, GCNs compute the average of the messages, i.e., they assign the same coefficient Ty = N/| to every neighbor: h = f(h)) where h4 def
Σ Wohy. JEN;
(2)
Nº1
Graph attention networks take different approach. Instead of assigning fixed value to each coefficient "ij they compute it as a function of the sender and receiver nodes. A general formulation for these models can be written as follows:
= f(!)) where h def En Woh, and
Yo def
exp (sp(W// (hi h2))
(3)
EIEN exp (h, hz))
JEN:
Here, (hh,, h def aWW h, Wih,,) known as the score function (or atlention architecture), and provides a score value between the messages h, and h, (or more generally, between learnable mapping of the messages). From these scores, the (attention) coefficients are obtained by normalizing them, such that E, 7i- = 1. We can find in the literature different attention layers and, throughout this work, we focus on the original GAT (Velickovic et al., 2018) and its extension GATv2 (Brody et al., 2022):
GAT: (h,, h2) LeakyRelu (aT [Wyh.l Wahyl)
(4)
GATv2: (h,, hy) = a LeakyRelu (W,h4 + Wahy)
(5)
where the learnable parameters are now the attention vector a; and the matrices Wg. Wk, and W.. Following previous work (Velickovic et al., 2018; Brody et al., 2022), we assume that these matrices coupled, i.e., W,, Wt W.. Note that the difference between the
2

---

Published as a conference paper at ICLR 2023
two layers lies in the position of the vector by taking it out of the nonlinearity, Brody et al. (2022) increased the expressiveness of GATv2. Now, the product of a and a weight matrix does not collapse into another vector. More importantly, the addition of two different attention layers will help us show the versatility of the proposed models later in $6.
3 PREVIOUS WORK
In recent years, there has been surge of research in GNNs. Here, discuss other GNN models, attention mechanisms, and the recent findings on the limitations of GCNs and GATs.
The literature GNNs is extensive (Wu et al., 2020b; Hamilton et al., 201 7a; Battaglia. et al., 2018; Loe et al., 2019), and more abstract definitions of a message-passingg GNN are possible, leading other lines of work trying different ways to compute messages, aggregate them, or update the final message (Hamilton et al., 2017b; Xu et al., 2019; Corso et al., 2020). Alternatively, another line of work fully abandons message- passing, working instead with higher-order interactions (Morris et al., 2019). While some of this work is orthogonal- or directly applicable- the proposed model, in the main paper we focus on convolutional and attention graph layers, as they are the most widely used (and cited) as of today.
While we consider the original GAT (Velickovic et al., 2018) and GATv2 (Brody et al., 2022), our work can be directly applied to any attention model that sticks to the formulation in Eq. 3. For example, some works propose different metrics for the score function, like the dot-product (Brody et al., 2022), cosine similarity (Thekumparampil et al., 2018), or combination of various functions (Kim & Oh, 2021). Other works introduce transformer- based mechanisms (Vaswani et al., 2017) based on positional encoding (Dwivedi & Bresson, 2020; Kreuzer et al., 2021) or on the set transformer (Wang et al., 2021a). Finally, there also exist attention approaches designed for specific type of graphs, such relational (Yun et al., 2019; Busbridge et al., 2019) or heterogeneous graphs (Wang et al., 2019b; Hu et al., 2020b).
3.1 ON THE LIMITATIONS OF GCN AND GAT NETWORKS
a simple stochastic block model, showing that, when the graph is neither too sparse nor noisy, applying one layer of graph convolution increases the regime in which the data is linearly separable. However, this result is highly sensitive to the graph structure, as convolutions essentially collapse the data to the same value in the presence of enough noise. More recently, Fountoulakis et al. (2022) showed that GAT is able to remedy the above issue, and provides perfect node separability regardless of the noise level in the graph. However, classical argument (see Anderson (2003) states that in this particular setting a linear classifier already achieves perfect separability. These works, in summary, showed scenarios for which GCNs can be beneficial in the absence of noise, and that GAT can outperform GCNs in other scenarios, leaving open the question of which archilecture preferable in terms of performance.
Baranwal et al. (2021) studied classification
CONVOLVED ATTENTION: BENEFITS AND HURDLES
In this section, we propose to combine attention with convolutto operations. To motivate it, we complement the results of Fountoulakis et al. (2022), providing a synthetic dalaset for which any 1-layer GCN fails, but 1-layer GAT does not. Thus, proving clear distinction between GAT and GCN layers. Besides, we show that convolution helps GAT as long as the graph noise is reasonable. The proofs for the two statements in this section appear in Appendix A and follow similar arguments as in Fountoulakis et al. (2022).
This dataset is based on the contextual stochastic block model (CSBM) (Deshpande et al., 2018). Let Ei,...,E,, En be iid. uniform samples from {-1,0, 13. Let C = [j E [n] E = k} for ls E 0,
13. We set the feature vector X ~ ~N((E I. o²) where μ E Rd o R, and
IE {0, 1)axd is the identity matrix. For given pair p, E [0, 1] consider the stochastic adjacency matrix A E (0. 1 defined as follows: for i.j E [n] in the same class (intra-edge). we set aij ~ Ber(p): for i in different classes (inter-edge), set ai Ber(g). We denote
'Ber()) denote the Bernoulli distribution.
3

---

Published as a conference paper at ICLR 2023
by A) CSBM P, M4 o²) sample obtained according to the above random process. Our task is then to distinguish (or separate) nodes from Co vs. C-1
Note that, in general, it is impossible to separate Co from C-1UC, with linear classifier and, using one convolutional layer is detrimental for node classification on the CSBM:2 although the convolution brings the means closer and shrinks the variance, the geometric structure of the problem does not change. On the other hand, we prove that GAT is ablc to achieve perfect node separability when the graph not too sparse:
Theorem 1. Suppose that p. g = 2[log" n/n) and ||l| = w(a Vlg Then, there exists choice of attention architecture v such that, with probability at least on()) over the data (X, A) ~ CSBM(n, P: o²), GAT separates nodes Co from C
Moreover, we show using methods from Baranwal et al. (2021), that the above classification threshold ||||| can be improved when the graph noise is reasonable. Specifically, by applying convolution prior to the allention score, the variance of the data is greatly reduced, and if the graph is not too noisy, the operation dramatically lowers the bound in Thm. 1. We exploit this insight by introducing the graph convolutional attention layer (CAT):
1 |N7
Vh, a: (Wh;; Wh₂) where h
Σ he, CEN;
(6)
where h; are the convolved features of the neighborhood of node i. As we show now, CAT improves over GAT by combining convolutions with attention, when the graph noise is low.
Corollary 2. Suppose p, 2(log" n/n) and || 2 w (ov 1p++20)oog m(p-q)"
Then, there is a choice attention architecture v such that CAT separates nodes Cu from C1 CUC-1, with probability at least 1 - o(1) over the data (X, A) ~ CSBM(n, p, q, o²).
The above proposition shows that under the CSBM data model, convolving prior attention changes the regime for perfect node separability by factor of lp - gl/n/(p 24). This is desirable when 1p - 1pp-ll// ////n//p + 2q) > 1, since the regime for perfect classification increased. Otherwise, applying convolution prior to attention reduces the regime for perfect separability. Therefore, it is not always clear whether convolving prior to attention is beneficial.
L-CAT: LEARNING TO INTERPOLATE
From the previous analysis, can conclude that it is hard to know a priori whether attention, convolution, or convolved attention, will perform the best. In this section, we argue that this issue be casily overcome by learning to interpolate between the three.
First, note that GCN and GAT only differ in that GCN weighs all neighbors equally (Eq. 2) and, the more similar the allention scores are (Eq. 3), the more uniform the coefficients Tij are. Thus, we can interpolate between GCN and GAT by introducing a learnable parameter. Similarly, the formulation of GAT (Eq. 3) and CAT (Eq. 6) differ in the convolution within the score, which can be interpolated with another learnable parameter.
Following this observation, we propose the learnable convolutional aftention layer (L-CAT), which can be formulated as an attention layer with the following score:
(h;, h2y) A1 aWW,, Wh;) where h h: + A2 EIEN, he
(7)
+ Ag|NN
where Åι, A2 E [0, 1]. As mentioned before, this formulation lets L-CAT learn to interpolate between GCN (A1 = 0), GAT (A1 = and X2 = 0), and CAT (A1 = 1 and X =
L-CAT enables a number of non-trivial benefits. Not only it switch between existing layers, but it also learns the amount of attention necessary for each use-case. Moreover, by
We note that this problem be easily solved by two layers of GCN (Baranwal al., 2022).
4

---

Published as a conference paper at ICLR 2023
GCN
|||110011
||,||-4.3
9-0.1
9-0.3
100
100
100
Accuracy (%)
75
80
25
50
60
0.2
0.4
0.4
10
10 10
10
Figure 1: Synthetic data results. The left-most plots show accuracy as we vary the noise level q for |||||| = 0.1 and | 4.3. The right-most plots show the accuracy we change the norm of the means || for q = 0.1 and q = 0.3. We use two vertical lines to present the classification threshold stated in Thm. (solid line) and Cor. (dashed line).
comprising the three layers in single learnable formulation, it removes the necessity of cross-valddtiing the type of layer, as their performance data-dependent (see $$3.1 and 4). Remarkably, it allows to easily combine different layer types within the same architecture.
While we focus on GCN, L-CAT can be easily used with other GNN architectures such as PNA (Corso al., 2020) and GCNII (Chen et al., 2020), as L-CAT interpolates between two different adjacency matrices. For further details and results, refer to App. F.
6 EXPERIMENTS
In this section, we first validate our theoretical findings on synthetic data ($6.1). Then, show through various node classification tasks that (L-)CAT is as competitive as the baseline models ($6.2). Lastly, we move to more demanding scenarios from the Open Graph Benchmark (Hu et al., 2020a), demonstrating that T-CAT is a alternative to its baseline methods ($6.3) that reduces the need of cross-validating without giving up on performance. Refer Apps. to F for details and additional results. The code to reproduce the experiments can be found at https://githhi: com/
flexible and robust
6.1 SYNTHETIC DATA
First, we empirically validate theoretical results (Thm. 1 and Cor. 2). We aim to better understand the behavior of each layer as the properties of the data change, i.e, the noise level q (proportion of inter-edges) and the distance between the means of consecutive classes ||ll We provide extra results and additional experiments in App. B.
Experimental setup. As data model, we use the proposed CSBM (see $4) with n 10000, p 0.5, 0.1, and parameters are set as described in App. A. We conduct two experiments to assess the sensitivity to structural noise. First, we vary the noise level q between and 0.5, leaving the mean vector za fixed. We test two values of ||||| the first corresponds to the easy regime (I|el 100r 22rg2ooogn log n) where classes are far apart; and the sccond correspond
n/ (5 log" (n)). All results
averaged over 50 runs, and
the hard regime (l] = σ) where clusters are close. In the second experiment we instead sweep ||l||| in the range /a/20, 200 /2 log n.,, covering the transition from hard (small || to casy (large [[al]]) settings. Here, we fix to 0.1 (low noise) and 0.3 (high noise). In both cases, we compare the behavior of 1-layer GAT and CAT, and include GCN the baseline.
The two left-most plots of Fig. show node classification performance for the hard and easy regimes, respectively, as we vary the noise level q. In the hard regime, we observe that GAT is unable to achieve separation for any value of q, whereas CAT achieves perfect classification when q small enough. This exemplifies the advantage of CAT over GAT as stated in Cor. 2. When the distance between the means is large enough, we see that GAT achieves perfect results independently of q, as stated in Thm. In contrast, when CAT fails to satisfy the condition in Cor. 2 (as we increase q), it achieves inferior performance.
Results.
The right-most part of Fig. shows the results when we fix q and sweep |||||| In these two plots, we can appreciate the transition in the accuracy of both GAT and CAT as function of ||]]] We observe that GAT achieves perfect accuracy when the distance between the means satisfies the condition in Thm. 1 (solid vertical line in Fig. 1). Moreover, can see
5

---

Published as a conference paper at ICLR 2023
Test accuracy (%) of the considered models for different datasets (sorted by their average node degree), and averaged over ten runs. Bold numbers are statistically different to their baseline model (a 0.05). Best average performance is underlined.
Table 1:
Dataset
A Amczon Computers
Amazon Photo
GitHub
Paoebook PagePage
Conuthor Physica
TwitchEN
Avg. Deg.
35.76
31.13
15.33
15.22
14.38
10.91
GCN
90.59 + 0.36
95.13 0.57
84.13
0.44
94.76 + 0.19
96.36 + 0.10
57.83
1.13
GAT
89.59
0.61
94.02
0.66
83.31
0.18
94.16 + 0.48
96.36 + 0.10
57.59
1.20
CAT
90.58 0.40
94.77
0.47
84.11
0.66
94.71 + 0.30
96.40 + 0.10
58.09
1.61
L-CAT
90.34 + 0.47
94.93 = 0.37
84.05 = 0.70
94.81 + 0.25
96.35 = 0.10
57.88
2.07
GATv2
89.49
0.53
93.47
0.62
82.92 0.45
93.44 1 0.30
96.24 1 0.19
57.70
1.17
CATV2
90.44 + 0.46
94.81 + 0.55
84.10 = 0.88
94.27 + 0.31
96.34
+ 0.12
57.99
2.02
L-CATV2
90.33 + 0.44
94.79 + 0.61
84.31 1 0.59
94.44 t 0.39
96.29
+ 0.13
57.89
1.53
the improvement CAT obtains over GAT. Indoed, when |||||| satisfics the conditions of Cor. 2 (dashed vertical line in Fig. 1), the classification threshold improved. As we increase q we see that the gap between the two vertical lines decreases, which means that the improvement of CAT over GAT decreases as q increments, exactly as stated Cor.
6.2 REAL DATA
We study now the performance of the proposed models in a comprehensive set of real-world experiments, in order to gain further insights of the scttings in which they excel. Spocifically, we found CAT and L-CAT to outperform their basclines as the average node degree increases. For a detailed description of the datasets and additional results, refer Apps. C, and F.
Models. We consider as baselines simple GCN layer (Kipf & Welling, 2017), the original GAT layer (Velickovic al., 2018) and its recent extension, GATv2 (Brody et al., 2022). Based on the two attention models, we consider their CAT and L-CAT extensions. To ensure fair comparisons, all layers use the same number of parameters and implementation.
Datasets. We consider six node classification datasets. The Facebook GitHlub/ TwitchEN datasets involve social-networt graphs (Rozemberczki et al., 2021), whose nodes represent ver- ified seeees/dvvelooes/steeee streamerss: and where the task is to predict the topic/ language-use of the node. The Coauthor Physics dataset (Shchur et al., 2018) represents a co-authorship network whose nodes represent authors, and the task is to infer their main research field. The Amazon datasets represent two product-iimilarty graphs (Shchur et al., 2018), where each node product, and the task is to infer its category.
topic/expertise/ eexprrtsee/ explicit-
Experimental setup. To ensure the best results, we cross-validate all optimizaaiion-reltee hyperparameters for each model using GraphGym (You et al., 2020). All models use four GNN layers with hidden size of 32, and thus have an equal number of parameters. For evaluation, we take the vest-validation configuration during training, and report test-set performance. For further details, refer to App. D.
Results are presented in Table In contrast with $6.1, we here find GCN to be a strong contender, reinforcing its viability in real-world data despite its simplicity. We observe both CAT and L-CAT not only holding up the performance with respect to their basclines models for all datasets, but in most cases also improving the test accuracy in statistically significant manner. These results validate the effectiveness of CAT as GNN layer, and show the viability of L-CAT as drop-in replacement, achieving good results on all datasets.
As explained in $4, CAT differs from a usual GAT in that
the score is computed with respect to the convolved features. Intuitively, this means that CAT should excel in those settings where nodes are better connected, allowing CAT to extract more information from their neighborhoods. Indeod, in the
Acc. Improvement (%)
0.5
inset figure we can observe the improvement in accuracy of CAT with respect lo ils baseline model, as a function of the
-0.5
average node degree of the dataset, and the linear regression fit of these results (dashed line). This plot includes all datasets
Average node degree

---

Published as a conference paper at ICLR 2023
Table 2: Test performance of the considered models on four OGB datasets, averaged over five runs. Bold numbers are statistically different to their bascline model (a = 0.05). Best average performance underlined. Left table: accuracy (%); right table: AUC-ROC (%).
Dataset
arziv
products
mag
proteins
GCN
71.58 0.20
74.12 1.20
32.77
0.36
80.10 0.55
GAT
71.58 + 0.16
78.53 + 0.91
32.15 + 0.31
79.08 1.47
CAT
72.14 = 0.21
77.38 = 0.36
31.98 + 0.46
73.26 = 1.65
L-CAT
71.99 + 0.08
77.19 + 1.11
32.47 + 0.38
79.63 + 0.71
GATv2
71.73 = 0.24
76.40 + 0.71
32.76 + 0.18
78.65 + 1.44
CATv2
72.03 = 0.09
74.81 1.12
32.43 0.22
74.33 0.94
T-CATv2
71.97 + 0.22
76.37 + 0.92
32.68 + 0.50
79.07 + 0.98
(from the manuscript and App. D), and shows a positive trend between node connectivity and improved performance achieved by CAT.
6.3 OPEN GRAPH BENCHMARK
In this section, we assess the robustness of the proposed models, in order to fully understand their benefits. For further details and additional results, refer to App. E.
Datasets. We consider four datasets from the OGB suite (Hu et al., 2020a): proteins, products, erriv, and mag. Note that these datasets are significantly larger than those from $6.2 and correspond to more difficult tasks, e.g., arziv 40-class classification problem (see Table 5 in App. C for details). This makes them more suitable for the proposed analysis.
Experimental sctup. We adopt the same experimental sctup as Brody et al. (2022) for the proteins, products, and mag datasets. For the arziv dataset, use instead the example code from OGB (Hu et al., 2020a), as it yields better performance than that of Brody et al. (2022). Just in $6.2, we compare with GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018), GATv2 (Brody et al., 2022), and their CAT and L-CAT counterparts. We cross-validate the number of heads (1 and 8), and select the best-validation models during training. All models are identical except for their À values.
Results are summarized in Table 2. Here we do not observe clear preferred baseline: GCN performs really well in proteins and meg; GAT excels in products; and GATv2 does well in arzic and mag. While CAT obtains the best results on arziv, its performance on proteins and products is significantly worse than the baseline model. Presumably, an excessive amount of inter-edges could explain why convolving the features prior to computing the score is harmful, as seen in $6.1. As we explore in $6.3.2, however, CAT improves over its baseline for most proteins scenarios, specially with a single head. In stark contrast, L-CAT performs remarkably well, improving the baseline models in all datasets but products- even on those in which CAT fails demonstrating the adaptability of L-CAT to different scenarios.
To better understand the training dynamics of the models, we plot in Fig, 2a the test accuracy of GCN and the GATv2 models during training on the arziv dataset. Interestingly, despite all models obtaining similar final results, CATu2 and L-CATe2 drastically improved their convergence speed and stability with respect to GATv2, matching that of GCN. To understand the behavior of L-CATv2, Fig. 2b shows the evolution of the À parameters. We observe that, to achieve these results, I-CATv2 converged to a GNN network that combines three types of layers: the first layer is a CATv2 layer, taking advantage of the neighboring information; the second layer is a quasi-GCN layer, in which scores are almost uniform and some neighboring information is still used in the score computation; and the third layer is & pure GCN layer, in which all scores are uniformly distributed. It is important to remark that these dynamics are fairly consistent, L-CATv2 reached the same À values over all five runs.
7

---

Published as a conference paper at ICLR 2023
ArXiv
ArXiv L-CATV2
70
Test accuracy
0.8
L2
0.6
L3
GCN
40
GATv2
0.4
30
CATv2
0.2
20
200
300
400
500
250
Epoch
Epoch
(a) Test accuracy,
(b) Evolution of λ1,A2.
Figure 2: Behavior of GCN and GATv2-based models during training on the arzie dataset. (a) CAT and L-CAT converge quicker and more stably than their baseline model. (b) L-CAT consistently converges to the same architecture: CAT -CNuas- network.
6.3.1 ROBUSTNESS TO NOISE
One intrinsic aspect of real world data is the existence of noise. In this section, explore the robustness of the proposed models to different levels of noise, i.e. we attempt to simulate scenarios where there exist measurement inaccuracies in the input features and edges.
Experimental setup. We consider the arziv dataset, and the same experimental setup
$6.3. We conduct two experiments. First, we introduce to the node features additive noise of the form (0, I0), and consider different. levels of noise, a E {0, 0.25, 0.5, 0.75, 1}. Then, as in (Brody et al., 2022), we simulate edge noise by adding fake edges with probability Bern(p) for 0.1. 0.2, 0.3, 0.4, 0.5}.
Feature noise
72
GCN
accuracy
Test accuracy
70
68
CAT
L-CAT
64
Results are shown in the inset figures for feature (top) and edge noise (bottom), summariking the performance of all models over five runs and two numbers of heads (1 and 8). Baseline attention models quite sensitive to feature noise, but are more robust to edge noise, as they can drop inter- class edges (see $3.1). GCNs, expected, are instead more robust to feature noise, but suffer more in the presence of edge noise. In concordance with the synthetic experiments (sce $&4 and 6.1), CAT is able to leverage convolutions a reduutio-oeductin technique, reducing the variance and improving its robustness to feature noise. Remarkably, L- CAT proves to be the most robust for both lypes of noise: by adapting the amount of attention used in each layer, it outperforms existing methods and reduces the variance.
60
0.00
0.25
0.50
0.75
1.00
(o)
noise
72
GON
71
GAT
Test sccupp
L-CAT
69
68
66
0.3
0.4
Naise (p)
6.3.2 ROBUSTNESS TO NETWORK INTTIALIZATION
Another important aspect for real-world applications is robustness to network initialization, ie., the ability to obtain satisfying performance independently of the initial parameters. Otherwise, a practitioner can waste lots of resources trying initilizations or, even worse, give on a model just because they did not try the initial parameters that yield great results.
Experimental setup. We follow once again the same setup for proteins as in $6.3. We consider two different network initializations. The first one, uniform, uses uniform Glorot initilization (Glorot & Bengio, 2010) with a gain of 1, which is the standard initialization used throughout this work. The second one, normal, uses instead normal Glorot initializa- tion (Glorot & Bengio, 2010) with a gain of V2. This is the initialization employed on the original GATv2 paper (Brody et al., 2022) exclusively for the proteins dataset.
Results segregated by number of heads are shown in Table 3, while the results for GCN appear in the inset table. These results show that the baseline models perform poorly on the
8

---

Published as a conference paper at ICLR 2023
Table 3: Test AUC-ROC (%) on the proteins dataset for attention models with two different network initializations (see $6.3.2), using head (top) and 8 heads (bottom).
GAT
CAT
L-CAT
GATv2
CATv2
L-CATv2
uniform
59.73
3.61
64.32
2.33
77.77 + 1.28
59.85 + 2.73
64.32 +: 2.33
79.08 + 0.95
normal
66.38 = 6.94
73.26 = 1.65
78.06 + 1.25
09.13 = 8.48
74.33 = 0.94
79.07 = 0.98
wniform
72.23
2.86
73.60
+ 1.14
78.85 + 1.57
75.21 + 1.61
74.16 + 1.30
78.77 + 0.97
normal
79.08 +: 1.47
74.67 + 1.15
79.63
+ 0.71
78.65 + 1.44
73.40
+ 0.56
79.30 + 0.49
average
69.36 1: 8.52
73.93 +: 1.35
78.58 4: 1.48
70:71 +: 8.70 71.55 1: 4.34
79.05 1: 0.91
uniform
uniform A2
normal A
normal
heads
0.75
Value
0.50
0.00
++
1
3
5
6
1
5
5
Layer
Layer
Layer
Layer
Figure 3: Distribution of λι, A2 on proteins dataset for L-CAT across initializations.
uniform initialization. However, this is somewhat alleviated when using 8 heads in the atten- tion models. Moreover, all baselines significantly improve with normal initialization, being GCN the best model, and attention models obtaining % accuracy on average with heads. Compared to the baselines, CAT does good job and improves the performance in all cases except for normal with 8 heads. Remarkably, L-CAT consistently obtains high accuracy in all scenarios and runs. To emphasize consistency, bottom row shows the average accuracy
GCN
uniform
61.08 + 2.56
normal
80.10 1 0.53
runs, showing that L-CAT clearly more robust to parameter inilialiaiiinn than competing models.
average 70.59 10.21
To understand this performance, inspect the distribution of A2 for T-CAT in Fig. 3. Here, we can spot few interesting patterns. Consistently, the first and last layers are always GCNs, while the inner layers progressively admit less attention. Second, the number of heads affects the amount of attention allowed in the network; the more heads, the more expressive the layer tends to be, and more attention is permitted. Third, L-CAT adapts to the initialization used: in uniform, it allows more allention in the second layer; in normal, it allows more allention in the score inputs. These results consolidate the flexibility of L-CAT.
CONCLUSIONS AND FUTURE WORK
In this work, we studied how to combine the strengths of convolution and attention layers in GNNs. We proposed CAT, which computes attention with respect to the convolved features, and analysed its benefits and limitations on new synthetic dataset. This analysis revealed different regimes where one model preferred over the others, reinforcing the idea that selecting between GCNs, GAT', and now CATs, is difficult task. For this reason, proposed IL-CTT, a model which interpolates between the three via two learnable paramoters. Extensive experimental results demonstrated the effectiveness of L-CAT, yiclding great results while being more robust than other methods. As a result, L-CAT proved to be a viable drop-in replacement that removes the need to cross-validate the layer type.
We strongly believe learnable interpolation can get us a long way, and we hope L-CAT to motivate and exciting work. Specially, we eager to see L-CAT in real applications, and thus finding out what combining different GNN layers across a model (without the hurdle of cross-valie validating all layer combinations) can lead to in the real-world.

---

Published as a conference paper at ICLR 2023
ETHIC STATEMENT
Given the nature of this work, we do not see any direct ethical concerns. On the contrary, L-CAT eases the application of GNNs to the practitioner, and removes the need of cross- validating the layer type, which can potentially benefit other arcas and applications, as GNNs have already proven.
REPRODUCIBILITY STATEMENT
For the theoretical results, we describe the data model used in $4, and provide all the detailed proofs in App. A. For the experimental results, we include in the supplementary material the necessary code and scripts required to reproduce our experiments, and all required datasots are freely available. Complete details about the experimental setup can be found in Apps. B, and E, and we report in our results the mean and standard deviation computed using five trials or more. In addition, we highlight in bold the results that statistically significant. Moreover, we include details computational resources used for the all sets experiments in App. B, App. D and App. E.
ACKNOWLEDGEMENTS
We would like to thank Batuhan Koyuncu, Jonas Klesen, Miriam Rateike, and Maryam Meghdadi for helpful feedback and discussions. Pablo Sánchez Martín thanks the German Research Foundation through the Cluster of Excellence "Machine Learning - New Perspectives for Science", EXC 2064/1, project number 390727645 for generous funding support. The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS- IS) for supporting Pablo Sánchez Martín.
REFERENCES
T.W. Anderson. An introduction to multivariate statistical analysis. John Wiley & Sons, 2003. (page 3)
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 1rXiv:1607.06450 2016. URL https:
-060000 (page 30)
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-oo-distribution generalization. In International Conference on Machine Learning (ICML). PMLR, 2021. (page 1, 3, 4, 16)
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in deep networks. arXiv preprinl arxi 099297, 2022. URL https: http::////xv///aaaaaaa /bs// 2204.09297. (page 1, 4)
Peter W Battaglia, Jossica Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXi preprint arxiv:1866 01261,, 2018. URL
(page 3)
K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016. URL http:// sanikvaarma.rr//ooolaaeee http://rr...oooaaaaaaa//////aaaa /XtX///////////orrr///ra/ html. (page 27)
Alcksandar Bojchevski and Stephan Günneemann. Deep gaussian embodding of graphs: Unsupervised inductive learning via ranking. In 6th International Conference on Learning Representations, ICLR 2018, Voncouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttps://peereet http///pppeeeeeeeeeeee/ee wttp:riwwwwetetttteiiiei ZZZKJ-OW. (page 27)
10

---

Published as a conference paper at ICLR 2023
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations (ICLR), 2022. (page 2, 3, 6, 7, 8, 30, 31)
Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla. Relational graph attention networks. ariie preprint aiv: 1eeo:.994..01110 2019. URL abs/1904.05811. (page 3)
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Con- ference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1725-1735. PMLR, 2020. URL (page 5, 32, 35)
http://pprocedings..rr htt.:/dddd.g.m.....pr/es////1/. https//vv119cheeeeeeee
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velick- ovic. Principal neighbourhood aggregation for graph nets. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (ods.), Advances in Neural Information Processing Systems 33: Annual Confer- ence Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: //ppee/e/oocccceosseeeeo wtwpceeedding..euriiis.ee www.imee.cciiiieooo wwtpcc/pppp////////eapaa (icaa22551166322222000000777/333 Aasrroatee-bbttta..tttt... (page 3, 5, 32, 33, 34)
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contex- tual stochastic block models. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (ods.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Infor- malion Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1590-86022 2018. URL https: 0aa1///8EEE000111111114444440000 Att.122--bbttaatt.thha. (page 3)
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv prepriml arXiv:2012.000 09699, 2020. URL https://arzxvvoor// /bbs/ 2012.09699. (page 3)
Matthias Fey and Jan E. Lensson. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. (page 28,
29)
Kimon Fountoulakis, Amit Levi, Shenghao Yang. Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. arviv preprint arxi::202. 13060, 2022. URL https: wwwpii..oggabb////eee 13060. (page 1, 2, 3, 16, 18, 20)
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, 1CML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1262-1272. PMLR, 2017. URL http://procedding....rr (page 1, 2)
htt///////llll gilmer aalmmer1aahhin htmml.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. Tn International Conference on Artificial Intelligence and Statistics (ATSTATS), 2010. (page 8)
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40, 2017a. (page 3)
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learn- ing on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017b. URL https: wwwpooeedding.nuuraae. httprppp.cc/ppppp////////oaaea ht/ppppe/201///ash// BadcddaSeeaaaskccfbbbbaaaaaaa htt.r///aeeeea--aaaaattt.t..aaa Abstract.htm.. (page 3)
11

---

Published as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Delving deep into rectifiers Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pp- 1026-1034 TEFE Computer Society, 2015. doi: 10.1109/ICCV 2015.123. URL. (page 28)
http:///....r//001100////////
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. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin (eds.), Advances in Newral Information Processing Systems 39: Annual Conference on Newral Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020a. URL https: / http:///e/ooeeigg.eeua.. www.ggg..nrriis.c....oo. http/pppp//2220000 //a0h// 1b60041145c65722227778888 oosta (page 5, 7, 27, 30)
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Yennun Huang, Irwin King, Tan Liu, and Maarten van Steen (eds.), WWW '20: The Web Conference 2020, Toipei, Taiwan, April 20-24, 2020, pp. 2704 2710. ACM / 2020b. doi: 04.144/333662333388000 URL http:://doi.org/10..11 /3t////0.111153342553333333 3380007 (page 3)
IW3C2,
Sergey Toffe and Christian Szegedy. Batch normalization: Accelcrating deep network training by reducing internal covariate shift. In Francis R. Bach and David M. Blei (cds.), Proceedings of the 32nd Indernational Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 448 188-456.10 JMLR.org, 2015. URL attp://pproceedings. mlr wwtppeerreeseeeeeeeeeeee htmll. (page 28, 30)
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations (ICLR), 2021. (page 3)
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (ods.), 3rd International Conference on Learning Representations, ICLR 2015, Son Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL /tap:///axivv...// www../ggg///a../........oooa faba//412.660 29880. (page 26, 28, 30)
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Representations, ICLR 2017, Toulon, Frunce, April 24-26, 2017, Conference Track Proceedings. OpenReview.nee 2017. URL https:// http::///ppeeeeeeeee/eomme sett/fooouniiddSJ4aaaaaa
(page 1, 2, 6, 7, 31, 32)
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and generalization in graph neural networks In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (ods.). Advances in Newral Informalion. Processing Systems 32: Annuull Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, 2019. URL https: https: http:/iiinnnnnipp...ceppeeeeeeee (page 1)
BC, Canada, pp.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral allention. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021. (page 3)
John Boaz Lee, Ryan A Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyee Koh. Attention models in graphs: A survey. ACM Transactions on Knowledge Discovery from Data (TKDD), 13, 2019. (page 3)
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 The Thirty- Third AAAI Conference 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth A AATT Symposium on Educational Advances in Artificial Intelligence,
Artificial Intelligence, AAAI
12

---

Published as a conference paper at ICLR 2023
EAAI 2019, Honolubu, Hawaii, USA, January 27 February 1, 2019, pp. 4602-4609. AAAI Press, 2019. doi: 10.1609/aame 1anni. URL https://aoi.org/ aaai faai.v33100.33014600 (page 3)
P. Rigollet and J.-C. Hütter. High dimensional statistics. Lecture notes for course 18S997, 813:814, 2015. (page 21)
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complez Networks, 2021. (page 6, 26)
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfar- dini. The graph neural network model. IEEE transactions neural networks, 20, 2008. (page 1)
Prithviraj Sen, Galileo Namata, Mustala Bilgic, Lise Geloor, Brian Galligher, and Tina Eliassi-Rar Rad. Collective classification in network data. Al magazine, 29(3), 2008. (page 1)
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arX.v:1811.0586, 2018. URL https://arxiv.orgt
(page 26, 27)
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhut- dinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):1929-19555 2014. (page 28, 30)
Kiran K Thokumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:180S 1803.03735, 2018. URL (page 3)
http://aaxxv..ogab///////sa/ httpb////83.033777 03735.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008, 2017. URL https: wtw.oceeddings.euuisss..oom 2017 h017/hash/3fftt 2ttea///2555e22444444eeee11aa000 c4535aaa1aa445aaaaa Abstract html. (page 3)
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.ned 2018. URL httpp:// http///rreeeeeeee/eeotm/t/// rJXMpikCZ. (page 1, 2, 3, 6, 7, 31)
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural networks. In International Joint Conference on Arlificial Intelligence (IJCAT), 2021a. (page 3)
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Sludies, 2020. (page 27)
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: graph-centric, highly- perfo-ppeformant package for graph neural networks. arXiv preprint 1909: 01315, 2019a. URL https: h http:://axxxvoorreeeoo 1909.01315. (page 29)
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. Heterogeneous graph attention network. In Ling Liu, Ryen W. White, Amin Mantrach, Fabrizio Silvestri, Julian J. McAuley, Ricardo Bacza- Yates, and Leila Zia (eds.), The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 18-17, 2019, pp. 2032-2032. ACM, 2019b. doi: /11145/330555..00 3313562. URL https:/ /tte:://doooorgg/ 10. ht0.///3305588333353535 (page 3)
13

---

Published as a conference paper at ICLR 2023
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXie:2103. 18355, 2021b. URL attps://arxiv.orr
abs/2103.13355. http://rww...rraaa////111113333 (page 32)
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey. ACM Compuling Surveys (CSUR), 2020a. (page 1)
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, 32, 2020b. (page 3)
Keyulu Xu, Weihua. Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph ncural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
(page 3, 32)
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph emboddings. In Maria-Florina Balcan and Kilian Q. Weinberger (ods.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedinggs, pp. 40 48. JMLR.org, 2016. URL http://prrcceedngs..rr www.mmlrr....ee.p.. vanga16.html. (page 27)
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020. (page 6, 27)
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. Graph transformer networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' d'Acché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Newral Information Processing Systems 32: Anmual Conference Neural Informa- lion Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11960 11970- 2019. URL https: https:///roceeeee ippproeeeings.neurrreer wttp://wwe.ppp.ppppee////// cc/paaprr2011/
hath:/96eeeeeabber7777707005555b Abstract html. (page 3)
14

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Theoretical results
16
A.1 A hard example for GCN
16
A.2 A solution for GAT and CAT
17
B Synthetic experiments
23
B.1 Other experiments
25
Dataset description
26
D Real data experiments
27
D.1 Experimental details
27
D.2 Additional results...
28
E Open Graph Benchmark experiments
29
E.1 Experimental details
29
E.2 Additional results.
30
F Extending L-CAT to other GNN models
32
F.1 PNA experiments
32
F.2 GCNII experiments
34
15

---

Published as a conference paper at ICLR 2023
A THEORETICAL RESULTS
A.1 A HARD EXAMPLE FOR GCN
In this subsection, we present dataset and classification task for which GCN performs poorly. Note that we follow the similar techniques and notation as (Fountoulakis et al., 2022), described in the main paper.
We recall our data model. Fix n, d E N and let Ei...., En be ii.d uniformly sampled from {-1,0,1). Let C [j [n] E k} for & E (,1,0,1) For each index i [nx]. we set the feature vector X, E Rd as X; N(E μ., I.I.-o o²), where
R E R and I E {0, 1jaxd is the identity matrix. For a given pair P.q E [o. [] we consider the stochastic adjacency matrix A E (0, 1)mxn defined as follows. For i,j [ni in the same class, set aıj ~ Ber(p)) and if i are in different classes, we set Oaj ~ Ber(z). We let D E Rax" be a diagonal matrix containing the degrees the vertices. We denote by (X, A) ~ CSBM(n, p. M, a sample obtained according to the above random process.
The task we wish to solve is classifying Co vs C-1UCH. Namely, we want our model ip to satisfy (xX,)) < 0 if and only if E Co. Morcover, note that the posed problem is not linearly clossifiable.
To this end, start by stating assumption on the choice of parameters. This assumption is necessary to achieve degree concentration the graph.
Assumption 1. p.q M(ogg n/n).
We now show the distribution of the convolved features. The following lemma can be easily obtained using the techniques in Baranwal et al. (2021).
Lemma 3. Fix p. q satisfying Assumption 1. With probability least o(1) over A and {s:t
p-q n. (D- ~ N (er ci p+ 29
d²
[
n(p 2q)
To prove the above lemma, we need the following definition of our high probability event.
Definition 1. We define the even & as the intersection of the following events over A and (s:)::
1. E, is the event that |ol = 3 + OVVn |Ci| = 5/ + OVVnlog and |C-1| = O(Vn log
2. Eg is the event that for each i E [n), D x(p+2g) 1 1
10 Vlogn
3. E3 is the event that for each i E [n] and k E f-1, 1,.
D
(1
10 / log n 10 Vlggn
if TiiCG Ct
NN =
p+24
Da
q
if i C₂
p-24
The following lemma is a direct application of Chernoff bound and union bound.
Lemma 4. With probability at least 1 - 1/poly(n) the event E holds.
Proof of Lemma 3. By applying Lemma 4, and conditioned on E, for any e [n]
1 X
1
(D D-'A
X,
Σ x
Σ
D JeN,
D JEN:
JEN,nCa
JEN,nC,
Using the definition of & and properties of Gaussian distributions the lemma follows.
16

---

Published as a conference paper at ICLR 2023
Lemma shows that essentially, the convolution reduced the variance and moved the means closer, but the structure of the problem stayed exactly the same. Therefore, one layer of GCN cannot separate Co from C-1 UC, with high probability.
A.2 A SOLUTION FOR GAT AND CAT
In what follows, we show that GAT is able handle the above classification task easily when the distance between the means is large enough. Then, show how the additional convolution on the inputs to the score function improves the regime of perfect classification when the graph is not too noisy. Our main technical lemma considers specific attention architecture and characterize the attention scores for our data model.
Lemma 5. Suppose that p.q satisfy Assumption || (ovlogn), fix the Leaky constant 3 E 10 and R E R. Then, there exists a choice of attention architecture T such that with probability at least (n) over the data (X, ~ CSBM(n, p. n, o²) the following holds.
10 [1] (1))
fije Oj ff
- 22 p 21)
22R|
if J C-1
10R3||
[0RBB|pp]((111 (1]
HiEC-1jj
(X,,
[a][ [[1]-13)(==(0))
if Co. jeC
[a]][[1 100--116 =1)))
if Co JEC-1
|Al - (()())
if DiECr,jC
if 1ieC-1, jE Co
2R []](1=
if Cj
Proof. We consider ansatz the following two layer architecture V.
-3/27
-1
- 3/2
2
1
3/2
2
def
11
def
-
b def
- 3/2
def
R
||44||
1/2
1
- 1/2
1/2
[-1
0
1/2
where R > 0 is an arbitrary scaling parameter. The output of the attention model defined
as
(XX X,) LeakyRellu
S
X;
+ b)
i
T
Let. Aij
def S.
w T'
X
E TR& and note that for each element. E [8] of Aij, we have that
A A))x
X; +
S X, + b. Note that the random variable (Aiy); is distributed
as follows:
N (( + S μ - b, |S,2)
if
- S + b., |S 12)02)
N N( " μ bi, || 1300
ifie Ce,
N )
b.,
S 1
(Di)) ~
N NS μ b,, S 2o?
if jo.jel,
N ( + b,, || 12)
if CeC
N (S μ b., 1822)
ifie jeC
N (- 1 b., || 22
ifi
N (b,, S 1022
i, e
17

---

Published as a conference paper at ICLR 2023
Therefore, for fixed i,j E [n]2 we have that the entries of ij are distributed as follows (where we use N as abbreviation for the Gaussian (xx y))
[ 141
N -mull
N اياا
N اواا
Not
Noa lill
No
Not T
for i,j E C₁,
1
2
N
N4 الاا
N
No ا1ll
N
No²
N
for i,j E Ch
ا
Iull
[N
No 1وا
No
N
No
اليل
for i.j C1 x C-1,
N4 3lpl
A 7ilell
A lel
N
Iill
N
Illll
No
N
lill
for i,j E C-1 x Cí,
Hall
N4a²
Squll
N
14
الuاl
N Hel
N
N
Hell
No²
slull
for i,j E Co x C1.
N 3
Iull
2
N
No1
No
N
N
for i.j E Co x C-11
Am1
Iull
Nio2
stull
2 lul
No2
lal
N
Iull
No
No
for i,j C1 x Co.
N Iull
?
اللاl
Nop Lal
No
No
1all
No I
for i,j C-1 X Co.
N
N
2 -
N
2 Meel
N
N
N
N
for i.j Cj.
lint
Iell
Next, we will use the following lemma regarding Leaky Relu concentration.
Lemma 6 (Lemma A.6 in Fountoulakis et al. (2022)). Fix N, and let 21, ......; 2g be jointly Gaussian random variables with marginals z; NN4,, of). There exists an absolute constant C > 0 such that with probability at least (1), we have
LeakyRelu(z)) = LeakyRelu (Ja) + Co. Vogg for all i E [s].
Using Lemma 6 with the assumption on ||ب||| and a union bound, we have that with probability at least on (1), LeakyRelu( Ayy) ) is (up to + o(1))
|+ll 2
78 yell
gell
m
sell
||
3,81 plll
3. |ael|
for ú, E C?,
2
1111|
3.9 الll
3 plll
3 141
3,9
||sl||
|
for i,j E C²
3.9 |لما||
3.11 p4
|elll
7
3.9
seell
3.9 |xel|
for i,j E Ci C-1,
2
2
3.9 الم|
3/
7
3,9 pell
3.91
for i,j E CC1 Ci,
2
9|1pe|1
5.91|
5.9
3,8
for i,j E Co C1,
2
2
2
2
5:81 |a||
8 [ell
3.8 //41
for i,j E Co C-1
2
2
2
2
2
5. الll
الم
e 0l|pa||
pll 2
for i,j E C₁ Co.
2
2
2
2
2
5,81 |=||
8
| 2
9 |all 2
||||||| 2
3,8 ||اا||
for i,j E C-1 Co.
2
2
2
2
3/9 AA
3, 3
3,8 اl||
8 mll
8 plll
for i,j E C2.
2
2
2
2
18

---

Published as a conference paper at ICLR 2023
Then,
10
e
+ d(1))
ifi,e
-2 (1
HiECC,jECE
ii
p LeakyRelu(A (g))
I1la -1- =11)
Co,
||a]| -113)(1++00)
| (1 =)))
HiECI,jEC.
|Al - (1)
ifiEC_1, jE
2R3 [4] o(1)
ifije
and the proof is complete.
Next we will define our high probability event.
Definition 2. E' def ENE,, where Ex is the event that for a fixed E Rd, all E [m] satisfy ww' X; - Eiw" X.] I
The following lemma is obtained by using Lemma 4 with standard Gaussian concentration and a union bound.
Lemma 7. With probability at least 1 1/poly(n) event E' holds.
Corollary 8. Suppose that p. q satisfy Assumption 1, || = w(ovlogn) and fix E R. Then, there exists choice of attention architecture such that with probability (1) over (A, X) ~ CSBM(n, P, q, 14, d²) it holds that
3
(1 + (())
iři,j E C CFUC if E C-1 Ci ifi, CL1 x CC
(1)) ng exp((0(((|a())) eexp(=((R)Al)))
Yi
3
otherwise
where R is a parameter of the architecture.
Proof. The proof immediate. First applying the ansatz from Lemma with B 1/25. Lemma 7 and union bound. Using the definition of My concludes the proof.
Next, we prove Thm. that the model distinguish nodes from Co for any choice of p.g satisfying Assumption 1. We restate the theorem for convince.
Theorem 9 (Formal restatement Thm. 1). Suppose that p. satisfy Assumption and || www n).. Then, there exists choice of attention architecture Vi such that with probability at least 1 - (1) over the data (X,A) ~ CSBM(n, P, 14, o²), the estimator
2 def Σ
Tii w T X, =b where v 1/llal/, b = 11
JEN.
satisfies è; < O if and only i Co.
Proof. Let be the architecture from Cor, and let satisfy R a w(1). We will compute the mean and variance of the estimator 2; conditioned on E.. Suppose that i Co. By using Cor. 8, Definition and our assumption on || and R, we have
3 ((p(-)(R))))), exp( exp(-O(Rl)aa) ((R] = nn(p + 2q) np
1
max
ng
19

---

Published as a conference paper at ICLR 2023
and therefore
E : 3
E
Σ
Σ
Yey T E'
1,(-110,1) JENiNCe
BlICo N:. E'
(1 + o()) 100
logn
np
E E4]
(1] + 10 log m)
n(p + -24)
||
E||C_in E
(-11u + 100 logn)
nnp + +24)
2
|0 2 (1))
By similar reasoning we have that for E
2 E' = السا (1 o(1))
Next, we claim that for cach i E [r] the random variable é; given E' is sub- Gaussian with small nub-Gaussian constant compared the above expectation. The following lemma straightforward adaptation of Lemina A.11 in Fountoulakis et al. (2022), and we provide ils proof for completeness.
Lemma 10. Conditioned on E", the random variables ( are sub-Gaussian with parameter d² if Co UC1 and 0; =0 o otherwise.
o3 00
Proof. Fix E [n], and write X; = eiju + og: where 9i ~ (O La), and E; denotes the class membership. Consider á as function of g = [9] o g2 o gnl Rnd where denotes vertical concatenation. Namely, consider the function
i = f() def Σ (g) w0 (E + ogj) - ||/1// i E [n]]
JEN.
Since g (O, Ind); proving that à; given E' is sub Gaussian for each E [n], reduces to showing that the function fi Innd + IR is Lipschitz over E S Rnn defined by E' and the relation X, = =,p+ogg That is, def {g E Rnd |wo gil I 10 Vi E [n]]- Specifically, we show that conditioning on the event E' (which restricts g E E), the Lipschitz constant
for E C and L,, = O otherwise, and hence Lf. of ft satisfies LG, = hp proving the claim.
First note that event g' induce a transformation which transforms isotropic Gaussians to truncated Gaussians vectors. Similarly to Fountoulakis et al. (2022), transformation can be obtained by a push-forward mapping whose Lipschitz constant is
show that this
② = M(b) def [T(01), (..)....., T(U,)))
(8)
where T(x) def क h-1((1 2c) (xx c) for = (0-10
To compute the Lipschitz constant of filg) for i [n], let us denote X = [X X2 o...o ox and consider the function
def Σ (X) i 'x,,, i [n]
JEN,
Let us assumee without loss of generality that Co (the cases for i E Ci and E CLi are obtained identically). Conditioning on the event E', which imposes the restriction that X E where
E
def
x
E Rnd
X - Eipal & Llooloonn, e [mi]
20

---

Published as a conference paper at ICLR 2023
Conditioning E' (which restricts X,X' E), using Cor. 8 and recalling that R satisfies 12 = w1)) we get
(xx))
12
w (X, - X3) +
. 600008011l (X, -X,)
3 ((Illl))) 10 10(''
(X, - x;)
JEN,CC np
u
JENiNC
JEN,OC-1
- (1
3
if N:nG ifjENNnG i N
3
3
(X X')
2)) (10))(++000))))))) +())
mp
jEIn]
(1 [1 (1))
j N I if E Ninc_1 if $ N;
3
expl (00
|| |X-X'll
exp - (1
SEIN
3 np
(1 + o(1))|| 122
3
V np + o(1)) |X 1
This shows the Lipschitz constant of f(( over É satisfies Lj, = = ( On the other hand, by vicwing X as a function of g, it straightforward to see that the function h(g): Rnd Rnd defined by h(g) def ((g) has Lipschitz constant Ln o, as
[h(g) h(g') ||2 |e + og (Ef + ag') 1l ollg 12
Therefore, since S((g) j((h(g)) and g E E if and only if X E,, we have that, conditioning on E", the function d;- fi(g) is Lipschitz continuous with Lipschitz constant L,, -,j, TA =
O /mp
Since g (0, Ind), we know that à is sub-Gaussian with sub-Gaussian constant
x² = D 0 e² up
The following lemma will be used for bounding the misclassification probability.
Lemma 11 (Rigollet & Hütter (2015)). Let I1,..., In be sub-Gaussian random variables with the same mean and nab-Gaussian parameter σ². Then,
E
max (x; E/æ:I) < <ō (E(M)
Moreover, for any t t>0 0
t²
Pr
(x; E (x.)) t [E(M)
max
< 2n exp
20
We bound the probability of misclassification
Pr
max 3; iECD
0 Pr
max dz / [+E(i:]] IECo
for t [[ عالعا (1 + o()). By Lemma 10, picking θ lovlog Col and applying
Lemma 11 implies that the above probability is 1/poly(nt.
We drop the (1)) in the first line of the computation for compactness and notation.
21

---

Published as a conference paper at ICLR 2023
Similarly for class C₁ U C-1
have that the misclassificction probability is (-0;) 200
Pr
min iEC,UC-1
2, s 0
Pr
max iEC;UC-1
(-f:) = = Pr
jECTUC-
Pr
max iECIUC-1
-f - E(á+]
for t E(ēy]. Picking t = (ovlog |C1 UC-1l) and applying Lemma 11 and union bound over the misclassification probabilities of both classes conclude the proof of the corollary. O
Combining Thm. with Lemma 3, we immediately get Cor. 2 which we restate below.
Corollary 12. Suppose p. 2loog n/n) and ||||| 2 (ov
[p+ 2g) log
n(p-91= Then, there
choice of attention architecture y such that, with probability at least o(1) over the data (X, A) ~ CSBM(n, μ, o²); CAT separates nodes Co from C1 U-1-
22

---

Published as a conference paper at ICLR 2023
B SYNTHETIC EXPERIMENTS
In this section, we present the complete results for the synthetic data experiments of $6.1. First, we describe the parameterization we use for the 1-layer GCN, GAT, and CAT models; then, we verify the behavior of the normalized score function (7x;) matches that of the theory presented in Cor. 8. In particular, we visualize the average of the following three groups of gammas (Fig. 4):
Gammas Vij included in i,j C U Cf- Solid lines.
Gammas Vy included in i.j C-1 x C1. Dashed lines.
The rest of gammas. Dotted lines.
For completeness, we also include the empirical results that validate Thm. and Cor. 2, which were discussed already in $6.1.
Experimental setup. We assume the following parametrization for the l-layer GCN, GAT, and CAT:
h1
Σ Yes We R x,
-C- -Cl1lal1/2
JEN:
where N; are the set of neighbors of node Xj are the features of node j obtained from the CSBM described in $4, and h are the logits of the prediction of node i. Note that for GCN we have Yi [N7 Otherwise, we consider the following parameterization of the score function V:
exp (Vi(h; ht)) Tij ΣKENT exp( Vi (h;, hx))
where
(10)
vi (h, h2) dof TT LeakyRellu (s.
W his th h
+b)
(11)
For these experiments, we define the parameters w S, and r as the proofs in App.
- 3/2
-1
- 3/2
2
-1
3/2
2
W
def
p
S
def
- 1
I 0
,
der
- 3/22
1/22
-110o|
r def
R
(12)
- 2
1/2
1/2
where > and > are arbitrary scaling parameters. Both C and and input to the score function are set different for each of the models, indicated in Table 4. Tn particular, we set R Tall for both GAT and CAT such that: i) all Ky are distinguishable as decrease ||a||: and ii) we avoid numerical instabilities in the implementattin when ||d||| in order to obtain "iy (see Cor. 8), as the exponential
computing the exponential of under/overflow overrlow issues. As for C, we set C -= 1 for GAT and of small or large values leads to under/
C- -00-g)/ 4)/(p (p- + 2q) for CAT such that we counteract the fact that the distance between classes shrink as increase see Lemma 3:
Regarding the data model, we set (as described in $6.1) n = 10000, p = 0.5, o 0.1, and = n (5 (n)).. We set the slope of the LeakyReLU activation to 3 = 1/5 for the GAT and = 0.01 for CAT, such that the proof of Cor. 8 is valid. As described in the main paper, to assess the sensitivity to structural noise, we present the complete results for two sets of experiments. First, vary the noise level q between and 0.5, fixing the mean vector μ.. We test two values of ||||| the first corresponds to the easy regime ([]и] = 10 10o R 4.3) where classes are far apart; and the second correspond to the hard regime (I|m]) = o 0.1)
23

---

Published as a conference paper at ICLR 2023
Table Parameters for the synthetic experiments.
Model
C
R
h;
GCN
GAT
X;
CAT
P-q p422
ΣKEN;
Xx
GON
CAT
|0.1
|| =4.3
ç=0.1
G=0.
100
100
Accuracy
25
80
75
50
60
0.4
0.2
10
10
10
10
....
7-1-1
GAT
GAT
GAT
GAT
0.006
0.006
0.0010
0.006
0.004
714
0.002
0.0005
0.002
0.002
0.000
0.000
0.0000
0.2
0.4
0.2
0.4
10
10
10-1
||
CAT
CAT
0.0010
0.002
7112
0.0005
0.000
0.2
10
10
10a
9
11pl
11
Figure 4: Synthetic data results. On the top row, we show the node classification, and in the following two rows show the Yi values for GAT and CAT respectively. In the two left-most figures, we show how the results vary with the noise level g for || = 0.1 and show how the results vary with the norm of the means ||ا||| for q = 0.1 and = 0.3. We use two vertical lines to present the classification threshold stated in Thm. (solid line) and Cor. 2 (dashed line).
|||||| = 4.3. In the two right-most figures,
where the distance between the clusters is small. In the second experiment we modify instead the distance between the mcans, sweeping || in the range [a/20, 20 22 which corresponds
[0.005, 8.58), and thus covering the transition from the hard setting (small ||лl]] to the casy one (large [|]]]). In these experiments, we fix g to 0.1 (low noise) and 0.3 (high noise).
Results are summarized in Fig. 4. The top row contains the node classification performance for each of the models (i.e., Fig. 1), the next two rows contain the "i values for GAT and CAT respectively. The two left-most columns of Fig. 4 show the results for the hard and easy regimes, respectively, as we vary the noise level q. the hard regime, we observe that GAT is unable to achieve separation for any value of g, whereas CAT achieves perfect classification when q is small enough. The gamma plots help shed some light on this question. For GAT, we observe that the gammas represented with the dotted and solid lines collapse for any value of q (see middle plot), while this does not happen for CAT when the noise level is low (see bottom plot). This exemplifies the advantage of CAT Cor. 2. When the distance between the means is large enough, we see that GAT achieves perfect results independently of g, stated in Thm. We also observe that, in this case,
GAT stated in
24

---

Published as a conference paper at ICLR 2023
GCN
GAT
CAT
L-CAT
|1.1
||
q-0.3
100
100
100
Acouracy
75
50
50
0.2
0.4
0.2
0.4
10
10
10-
10*
||d|
1Pll
A
L-CAT
L-CAT
L-CAT
L-CAT
1.0
0.5
0.0
0.0
10
10
|PI| 10
||ll
Figure 5: Synthetic data results learning C, A and Ag. On the top row, we show the node classification accuracy, and in the bottom row show the learned values of λι and A2 for L-CAT. In the two left-most figures, we show how the results vary with the noise level q for |||||| = 0.1 and || 4.3. In the two right-most figures, we show how the results vary with the norm the means || for 9 = 0.1 and q = 0.3. We use two vertical lines to present the classification threshold stated in Thm. (solid line) and Cor. (dashed line).
the gammas represented with the dotted and solid lines do not collapse for any value of q. In contrast, as we increase q: CAT fails satisfy the condition in Cor. 2, and therefore achieves inferior performance. We note that the low performance is due to the fact that all gammas collapse to the same value for large noise levels.
For the second set of experiments (two right-most columns of Fig. 1), where we fix q and sweep ||ا|| we observe that, for both values of q, there exists a transition in the accuracy of both GAT and CAT as function of ||a|]]. As shown in the main manuscript, GAT achieves perfect accuracy when the distance between the means satisfies the condition in Thm. the improvement CAT obtains over
(solid vertical line in Fig. 1). Morcover, we GAT. Indeed, when || satisfies the conditions of Cor. 2 (dashed vertical line in Fig. 1), the classification threshold is improved. As we increase q, we see that the gap between the two vertical lines decreases, which means that the improvement decreases as q increments, exactly as stated in Cor. 2. This transition from the hard regime the easy regime is also observed in the gamma plots: we observe the largest difference in value between the different groups of lambdas for values of ||ب||| that satisfy the condition in Thm. (that to the right of the vertical lines).
B.1 OTHER EXPERIMENTS
In the following, we extend the results for the synthetic data presented above. In particular, we aim to evaluate if L-CAT is able to achieve top performance regardless of the scenario. That is, we want to evaluate if L-CAT consistently performs at least as good as the best- performing model. We change the fixed-parameter setting of the previous section and, instead, we evaluate the performance of GCN, GAT, CAT and L-CAT when we learn the model-dependent parameters.
Experimental sctup. We assume the same parametrization for the 1-layer GCN, GAT and CAT described in Eq. 9 and Eq. 11. For L-CAT, we add the parameters ê and X2, as indicated in Eq. 7. We fix the parameters shared among the models, that is, w; S, b, r, and now learn C
R, with the values indicated in Eq. 12. Different from previous experiments, and, for L-CAT, we also learn a1 and A2. We choose to fix part the parameters (instead of learning them all) to keep the problem similar as possible to the theoretical analysis provided in 54 and App. A. If we instead learn all the parameters, it takes a single dimension
25

---

Published as a conference paper at ICLR 2023
of the features to be (close to) linearly separable to find solution that achieves a similar performance regardless of the model, which hinders the analysis. This is a consequence of the probabilistic nature of the features. One way of solving this issue would be to make n big enough. Instead, we opt to have a fixed n and reduce the degrees of freedom of the models by fixing the parameters shared across all models. The rest of the experimental setup matches the one from App. B. Additionally, we use the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 0.05, and we train for 100.
Results are summarized in Fig. 5. The top row contains the node classification performance for every model, while the bottom row contains the learned values of x1 (solid line) and d2 (dashed line) with L-CAT. The two left- left-most columns of Fig. 5 show the results for the hard and easy regimes, respectively, as we vary the noise level q. In the hard regime, we see rather noisy results. Still, the behaviour is similar to that of Fig. 4: the performance of CAT degrades as we increase q. We also observe that, on average, CAT outperforms GAT. Tn this case, we observe that L-CAT achieves similar performance by inspecting the learned values of lambda in the bottom row. We observe that A and Ag 2 0.5 on average for all values of q. This indicates that L-CAT is closer to CAT than to GAT. When the distance between the means is large enough (i.c., ||||| = 4.3), we see that GAT achieves perfect results independently of q while the performance of CAT deteriorates with large values of q, the same trend as in Fig. 4. Remarkably, we observe that L-CAT also achieves perfect results independently of q. If we inspect the lambda values, we first see that À = for all q, thus the interpolation happens between CAT and GAT, Looking at the values of '2 we observe that, for small values of q, X2 is pretty noisy, which is expected since any solution achieves perfect performance. Interestingly, we have that A2 = 0 for large values of g. with negligible variance. This indicates that L-CAT learns that must behave like GAT in order to perform well.
CAT, which can be explained
For the second set of experiments (two right-most columns of Fig. 5), we fix q and sweep ||l||| like we did in Fig. 4. Here, we observe a similar trend: for both values of q, there exists a transition in the accuracy of both GAT and CAT as a function of || Yet once again, we observe that L-CAT consistently achieves similar performance to the best-performing model in every situation.
C DATASET DESCRIPTION
We present further details about the datasets used in our experiments, summarized in Table 5. All datasets are undirected (or transformed to undirected otherwise) and transductive.
The upper rows of the table refer to datasets used in $6.2 taken from the PyTorch Geometric framework.* The following paragraphs present a short description of such datasets.
Amazon Computers & Photos are datasets taken from Shchur et al. (2018), in which nodes represent products, and edges indicate that the products are usually bought together. The node features task is to predict the category of the products.
Bag of Words (BoW) representation of the product reviews. The
Hub is dataset introduced in Rozemberezki et al. (2021), in which nodes correspond to developers, and edges indicate mutual follow relationship. Node features are embeddings extracted from the developer's starred repositories and profile information (e.g., location or employer). The task is to infer whether a node relates to web or machine learning development.
Pagioooe is a dataset introduced in Rozemberezki et al. (2021), where nodes are Facebook pages, and edges imply mutual likes between the pages. Nodes features are text embeddings extracted from the pages' description. The task consist on identifying the page's category.
TwitchEN is a dataset introduced in Rozemberezki et al. (2021). Here, nodes correspond to Twitch gamers, and links reveal mutual friendship. Node features are an embedding of
26

---

Published as a conference paper at ICLR 2023
games liked, location, and streaming habits. The task is to infer if a gamer uses explicit content.
Coauthor Physics & CS datasets introduced in Shehur et al. (2018). In this case, nodes represent authors which are connected with an edge if they have co-authored a paper. Node features BoW representations of the keywords of the author's papers. The task consist on mapping cach author to their corrosponding field of study.
DBLP is dataset introduced in Bojchevski & Günnemaan (2018) that represents citation network. In this datasel, nodes represent, papers and edges correspond to citations. Node features are BoW representations of the keywords of the papers. The task is to predict the research area of the papers.
PubMed, Cora & CiteSeer are citation networks introduced in Yang et al. (2016). Nodes represent documents, and edges refer to citations between the documents. .Nod features are BoW representations of the documents. The task is to infer the topic of the documents.
The bottom rows of Table 5 refer to the datasets from Open Graph Benchmark (OGB) (Hu et al., 2020a) 5 used in $6.3. We include short description of them in the paragraphs below.
ogbn-arxiv is a citation network of computer science papers in arXiv (Wang et al., 2020). Nodes represent papers, and directed edges refer citations among them. Node features are embeddings of the title and abstract of the papers. The task is to predict the rescarch area of the nodes.
ogbn-products contains a co-purchasing network (Bhatia et al., 2016). Nodes represent products, and links are present whenever two products are bought together. Node features are embeddings of BoW representation of the product description. The task is to infer the category of the products.
ogbn-mag is heterogeneous network formed from subgraph of the Microsoft Academic Graph (MAG) (Wang et al., 2020). Nodes can belong to one of these four types: authors, papers, institutions and fields of study. Moreover, directed edges belong to one of the following categories: "author is affiliated with an institution," " "author has written a paper," " "paper cites paper," " and "paper belongs to research area." " Only nodes that are papers contain node features, which are a text embedding of the document content. The task is to predict the venue of the nodes that are papers.
ogbn-proteins is network whose nodes represent proteins and edges indicate different types of associations among them. This dataset does not contain node features. The tasks are to predict multiple protein functions, each of them being binary classification problem.
D REAL DATA EXPERIMENTS
D.1 EXPERIMENTAL DETAILS
Computational resources. We used CPU cores to run this set of experiments. In particular, for each trial, we used CPU cores and up to G6GB of memory. We ran the experiments in parallel using a shared cluster with 10000 CPU cores approximately.
General experimental setup. As mentioned in $6.2, we repeat all experiments 10 times, which correspond to 10 different random initialization of the parameters of the GNNs. In all cases, we choose the model parameters with the best validation performance during training. In order to run the experiments and collect the results, we used the GraphGym framework (You et al., 2020), which includes the data processing and loading of the dat asets, as well as the evaluation and collection of the results. We split the datasets in 70 % training, 15 % validation, and 15 % test.
We cross-validate the number of message- pasnngggppsinggggg layers in the network (2,3,4) well the learning rate (10.01, 0.005)). Then, we report the results of the best validation error among the 4 possible combinations. However, in practice we found the best performance always to
27

---

Published as a conference paper at ICLR 2023
Table 5: Dataset statistics. On the top part of the table, we show the datasets used in $6.2. On the bottom part of the table, we show the datascts used in $6.3.
Avg. degree
#Node feats.
#Edge feats.
Name
Nodes
Edges
#Takks
Task Type
AmazonComp.
13.752
191,722
35.76
767
1
10-class clf.
AmazonPhoto
7,650
238,162
31.13
745
1
8-class clf.
GitHub
37,700
578,006
15.33
128
1
Binary elf.
FacebookP.
22,470
342,004
15.22
128
4-class elf.
CoauthorPh.
34,493
495,924
14.38
8415
1
5-class elf.
TwitchEN
7,126
77,774
10.91
128
1
Binary clf.
CoauthorCS
18,333
163,788
8.93
6805
15-class clf.
DBLP
17,716
105,734
5.97
1639
4-class elf.
PubMed
19,717
88,648
4.50
500
3-class elf.
Cora
2,708
10,556
3.90
1433
7-class clf.
CiteSeer
3,327
9,104
2.74
3703
1
6-class elf.
ogbn-arxiv
169,343
1,166,243
6.89
128
1
40-class clf.
ogbn-products
.29
223,718,280
50.52
100
1
47-class clf.
ogbn-mag
1,939,743
21,111,007
18.61
128
1
349-class elf.
ogbn- beon-proteins
132,534
79,122,504
597.00
112
Multi-task
use messago-passingg layers, and thus the only difference in configuration lies in the learning ratc.
We use residual connections between the GNN layers, 4 heads in the attention models, and the Parametric ReLU (PReLU) (He et al., 2015) as the nonlinear activation function. We do not use batch normalization (TolTe & Szegedy, 2015), nor dropout (Srivaslava et al., 2014). We use the Adam optimizer (Kingma learning-rane rate scheduler with y 0.998. We train all the models for 2500 epochs. Importantly, we do not use weight decay, since this will bias the solution towards a1 = and X2 =
Ba, 2015) with
(0.9, 0.999), and an exponential
We use the Pytorch Geometric (Fey & Lenssen, 2019) implementation of L-CAT for all exper- iments, switching between models by properly by sctting A1 and Az. We parametrize x and A as prcepparaeeter in log-space that pass through sigmoid function-iee sigmoid(10*) such that they are constrained to the unit interval, and they are learned quickly.
D.2 ADDITIONAL RESULTS
Table 6 shows the results presented in the main paper (with the addition of dense feed- forward network), while Table 7 presents the results for the remaining datasets, with smaller average degroe.
we focus on Table 7, we observe that all models perform equally well, yet in a few cases CAT and L-CAT significantly better than the baselines e.g., L-CATv2 in CoouthorCS, or L-CAT in Cora. Following a similar discussion as the one presented in the main paper, these results indicates that. L-CAT achieves similar better performance than baseline models and thus, should be the preferred architecture.
Competitive performance without the graph. We also include in Tables 6 and 7 the performance of a feed-forward network, referred to as Dense (first row). Note that the only data available to this model the node features, and thus no graph information is provided. Therefore, we should expect a significant drop in performance, which indeed happens for some datasets such as Amazon Computers (*e 7% drop), FocebookPagePPage (* 20% drop), DBLP (z 9% drop) and Cora. (> 14% drop). Still, we found that for other commonly used datasets the performance similar, e.g., Coauthor Physics and PubMed; or is even better CoauthorCS. Those results manifest the importance of proper benchmarking, and of carefully considering the datasets used to evaluate GNN models.
28

---

Published as a conference paper at ICLR 2023
Table Test accuracy (%) of the considered convolution and attention models for different datascts (sorted by their average node degree), and averaged over ten runs. Bold numbers are statistically different to their basclinc model (a 0.05). Best average performance is underlined.
Dataset
Amason Computers 35.76
Amason Photo
Gitlfab
Facebook PagePage
Coauthor Physica 14.38
TwitchEN
Avg. Deg.
31.13
16.33
15.22
10.91
Dense
83.73 1 0.34
91.74
0.46
81.21
0.30
75.89 1 0.66
95.41 1 0.14
56.26
1.74
GCN
90.59
95.13
0.57
84.13
0.44
94.76
0.19
96.36 + 0.10
57.83
1.13
GAT
89.59
94.02
0.66
83.31
0.18
94.16 1: 0.48
96.36 1 0.10
57.50
1.20
CAT
90.58
0.40 90.34
0.47 94.93
94.77
84.11
0.66
94.71 + 0.30
96.40
0.10
58.09
I-CAT
0.47
0.37
84.05
1 0.70
94.81 t: 0.25
96.35 1: 0.10
57.88
2.07
GATv2
89.49
0.53
93.47
0.62
82.92 0.45
93.44 + 0.30
96.24 0.19
57.70
1.17
CATv2
90.44
0.46
94.81
0.55
84.10 0.88
94.27 + 0.31
96.34 + 0.12
57.99
2.02
L-CATV2
90.33 + 0.44
94.79
0.61
84.31 = 0.59
94.44 = 0.39
96.29 + 0.13
57.89 1.53
Table 7: Test accuracy (%) of the considered convolution and attention models for different
datasets (sorted by their average node degree), and averaged over ten runs. Bold numbers are statistically different to their bascline model (a = 0.05). Best average performance is underlined.
Dataset
CoauthorCS 8.93
DBLP 5.97
PubMed 4.5
Cora
CiteSeer 2.74
Avg. Deg.
3.9
Dense
94.88 + 0.21
75.46
0.27
88.13 + 0.33
72.75
1.72 86.68 0.78
73.02 + 1.01
GON
93.85 + 0.23
84.18 + 0.40
88.50 + 0.18
75.76 + 1.09
GAT
93.80 + 0.38
84.15 + 0.39
88.62 + 0.18
85.95 + 0.95
75.40 + 1.43
CAT
93.70 + 0.31
84.10 0.29
88.58 + 0.25
85.85 0.79
75.64 + 0.91
L-CAT
93.65 + 0.23
84.13 + 0.26
88.45 + 0.32
86.66 + 0.87
75.04 + 1.12
GATv2
93.19 + 0.64
84.33 0.18
88.52 + 0.27
85.65 1.01
75.14 + 1.20
CATv2
93.51 + 0.34
84.15 0.41
88.54 + 0.29
85.50 0.94
74.68 + 1.30
L-CATv2
93.65 = 0.20
84.31 0.31
88.48 + 0.24
85.75 0.72
75.04 + 1.30
E OPEN GRAPH BENCHMARK EXPERIMENTS
E.1 EXPERIMENTAL DETAILS
Computational resources. For this set of experiments, we had at our disposal a set of 16 Tesla V100-SXM GPUs with 160 CPU cores, shared among the rest of the department.
Statistical significance. For each CAT and L-CAT model, we highlight, significant improve- ments according to two-sided paired t-test (a 0.05), with respect its corresponding baseline model. For example, for L-CATv2 with 8 heads we perform the test with respect to GATv2 with 8 hcads.
General experimental setup. As mentioned in $6.3, we repeat all experiments with OGB datasets 5 times. In all cases, we choose the model parameters with the best validation performance during training. Moreover, when we show the results without specifying the number of heads, we take the model with the best validation error among the two models with and heads.
We use the same implementation of L-CAT for all experiments, switching between models by properly setting A and X2. Experiments on arziv, mag, products use version of L-CAT implemented in Pytorch Geometric (Fey & Lenssen, 2019). Experiments on proteins use a version of L-CAT implemented in DGL (Wang et al., 2019a). We parametrize ê₁ and x as free-parametes in log-space that pass through a sigmoid function -isionn--e,,..----- sigmoid(10"). such that they are constrained to the unit interval, and they learned quickly.
29

---

Published as a conference paper at ICLR 2023
ArXiv. As described in $6.3, use the example code from the OGB framework (Hu et al., 2020a). The network is composed of 3 GNN layers with a hidden size of 128. We use batch normalization (loffe & Szegedy, 2015) and dropout (Srivastava et al., 2014) of 0.5 between the GNN layers, and Adam (Kingma & Ba, 2015) with a learning rate of 0.01. We use the ReL activation function. For the initial experiments, we train for 1500 epochs, while we train for 500 epochs for the noise experiments in $6.3.1. This is justified given the convergence plots in Fig. 2.
MAG. We adapted the official code from (Brody et al., 2022). The network is composed of 2 layers with 128 hidden channels. This time, we use layer normalization (Ba et al., 2016) and a dropout of 0.5 between the layers. Again, we use ReLU as the activation function, and add residual connections to the network. As with arriv, we use Adam (Kingma & Ba, 2015) with learning rate 0.01. We set a batch size of 20000 and train for 100 epochs.
Products. We use the same sctup as (Brody et al., 2022), with a network of 3 GNN layers and 128 hidden dimensions. We apply residual connections once again, with dropout (Srivastava. et al., 2014) of 0.5 between layers. This time, we use ELU as the activation function. The batch size is set to 256. Adam (Kingına & Ba, 2015) is again the optimizer in use, this time with a learning rate of 0.001. We train for 100 epochs, although we apply early stopping whenever the validation accuracy stops increasing for more than 10 epochs. Note the training split of this dataset only contains % of the data.
has 6 GNN layers of hidden size 64. Dropout (Srivastava et al., 2014) is set to 0.25 between layers, with an input dropout of 0.1. At the beginning of the network, we place linear layer followed by a ReLU aclivation to encode the nodes, and a linear layer at the end of the network to predict the class. Moreover, we use batch normalization (Ioffe & Szegedy, 2015) between layers and ReLU as the activation function. We train the model for 1200 epochs at most, with early stopping after not improving for 10 epochs.
Protcins. We follow once more the sctup of (Brody et al., 2022). The network
E.2 ADDITIONAL RESULTS
We show Tables to 10 the results the main paper for the arzic, mag, products datascts, respectively, without selecting the best configuration for each type of model. That is, we show the results for both number of heads. Note that we already show the full table of results for the protein datasets in the main paper (Table 3). All the trends discussed the main paper hold.
Table 8: Test accuracy on the arziv dataset for attention models using 1 head and 8 heads.
GON
GAT
CAT
L-CAT
GATv2
CATv2
L-CATv2
1h 8h
71.58 + 0.19
71.58 + 0.15
72.04 + 0.20
72.00 + 0.11
71.70 + 0.14
72.02 + 0.08
71.96 + 0.21
71.63 + 0.11
72.14 0.20
71.98 + 0.08
71.72 + 0.24
71.76 0.14
71.91 + 0.16
Table 9: Test accuracy on the may dataset for attention models using 1 head and 8 heads.
GON
GAT
CAT
L-ATT
GATv2
CATv2
L-CATv2
1h 8h
32.77 1 0.36
32.35 1. 0.24
31.98 1: 0.46
32.47 1. 0.38
32.76 1 0.18
32.43 1 0.22
32.68
0.50
32.15 + 0.31
31.58
0.22
32.49 + 0.21
32.85 + 0.21
32.34 0.18
32.38 + 0.28
Table 10: Test accuracy on the products dataset for attention models using head and 8 heads.
GCN
GAT
CAT
L-CAT
GATv2
CATv2
L-CATv2
1h 8h
74.12
1.20
78.53 + 0.91
77.38
0.36
77.19 + 1.11
73.81 + 0.39
74.81
1.12
76.37 + 0.92
78.23 + 0.25
76.63
1.15
76.56 + 0.45
76.40 + 0.71
75.20
0.92
74.70 + 0.28
Extrapolation ablation study. Due to page constraints, these results were not added to the main paper. Here, we study two questions. First, how important are A and Xe in the formulation of L-CAT (Fq. 7)? For the sake of completeness, the second question
30

---

Published as a conference paper at ICLR 2023
attempt to answer here is whether can obtain similar performance by just interpolating between GCN and GAT (fixing Xg = 0)? Note that we theoretically showed in $$4 and 6.1 that CAT fills up gap between GCN and GAT, making it preferable in certain settings.
To this end, we repeat the experiments for network-inttializtton initialization robustness in $6.3.2, since they showed to be the best ones to tell apart the performance across models. We include three additional models: GCN-GAT, which interpolates between GCN and GAT (or GATv2) by learning Å and fixing X2 0; CAT-À, which interpolates between GCN and CAT by learning λ and fixing A = 1; and CAT-X2, which interpolates between GAT and CAT by learning X2 and fixing \1 = 1.
Results using GAT and shown in Table 11, and using GATv2 in Table 12. We can observe that GCN-GAT obtains results in between GCN and GAT for all settings, despite being able to interpolate between both layers in cach of the six layers of the network. Regarding learning X1 and X2, we can observe that there is a clear difference between learning boths (L-CAT), and learning single one. For both attention models, CAT-Ai obtains better results than CAT-A2 in all settings, but uniform with 8 heads. Still, the results of both variants are substantially worse than those of L-CAT in all cases, demonslraling the imporlance of learning to interpolate between the three layer types.
Table 11: Test accuracy on the proteins dataset for GCN (Kipf & Welling, 2017) and GAT (Velickovic et al., 2018) attention models using two network initializations, and two numbers of heads (1 and 8).
GCN
GCN-GAT
GAT
CAT
LCAT
CAT-A1
CAT-Aa
unsform initialization
1h 61.08 2.86
70.44 1.56
69.73 + 4.04
74.19 + 0.72
77.77 + 1.44
71.97
3.78
73.55
1.36 72.76
72.23
3.20
73.60 1.27
78.85
1.76
76.43
normaal Initialization
1h 80.10 = 0.61
66.51 + 3.23
66. 38
+ 7.76
73.26 + 1.84
78.06
+ 1.40
76.77
1.91
73.39 + 1.25
69.93
1.93
79.08
1.64
74.67 1.29
79.63
0.79
78.86 + 1.07
73.32 1.15
Table 12: Test accuracy on the proteins dataset for GCN (Kipf & Welling, 2017) and GATv2 (Brody et al., 2022) attention models using two network initializations, and two numbers of heads (1 and 8).
GCN
GCN-GATY2
GATv2
CATv2
1AT22
CATv2-Aj
C.TV2-12
unsform initialiaation
1h 61.08 2.86
69.69
1.59 69.94
59.85 + 3.05
61.32 2.61
79.08 + 1.06 78.77
63.21 + 1.35
73.41
0.34 73.96 +
75.21 1.80
74.16 1.45
1.09
77.61
normal initialization
1h
80.10 0.61
68.51 + 1.63
69. 13
+ 9.18
71.33 + 1.06
79.07 # 1.09
78.11 # 0.93
74.07 + 1.17
68.71
1.96
78.65 1.61
73.40 0.62
79.30 0.55
78.76 1.41
73.22 0.77
31

---

Published as a conference paper at ICLR 2023
F EXTENDING L-CAT TO OTHER GNN MODELS
Due to their simplicity and popularity, in the manuscript we focus on the simplest form of GCNs, as described in $2 However, we consider important to remark that L-CAT can be effortless extended to a large range of existing GNN models. A more general formulation of message- message-passing GNN layer than the one given in Eq. 1 is the following:
h = f(h,) where h/g def
M hs;
(13)
JEN;
where by is scalar value, + refers to any permutation invariant operation-o.g. sum, mean, maximum, or minimum operalions and M is the message operator, which can be parameterized, and produces a message based on the sender and receiver representations. This formulation comprises most GNN architectures present in the current literature. For example:
GCN (Kipf & Welling, 2017): M I;EN; By W.h,, where 3i = |Nşl as consider the main paper, or Ti- Va,d, where d4 is the number of neighbors of node (including self-loops), if we consider the symmetric normalized adjacency matrix instead.
GIN (Xu et al., 2019): hy (1 2)fuh + EJEN, figh with 9tz 1.
PNA (Corso et al., 2020): hy DENN: Mr (h, hy; where Fi = 1, M is an multi-layer perceptron, and + is set of permutation invariant operations, e.g.: +
[u, a, max, min].
GCNII (Chen et al., 2020): h1 ah (1 a) EjEn; Righs) (11 ((1-)) +, where, and a, 11. just as in the GCN case, Pig- = va
In all the models above, the values Ty are taken from the adjacency matrix A (whose entries are 1 if there exists an edge between nodes and j, and 0 otherwise), or a matrix derived from it, e.g., the symmetric normalized adjacency matrix.
Note that the attention coefficients ky defined in Eq. 3 can be understood as an attention- equivalent of the adjacency matrix. Indeed, by defining Aott matrix whose entries are | one can obtain a row-stochastic matrix that can substitute the adjacency matrix of any GNN model. This technique to generalize attention models to GNN variants more complex than GCN has been successfully applied in prior literature (Wang et al., 2021b).
With this new interpretation of attention-modes the interpolation performed by L-CAT (see Eq. 7) can similarly be re-interpreted. Indeed, L-CAT learns to interpolate between the adjacency matrix A, and an attention-based adjacency matrix Aatt which can be produced by cither GAT (Eq. 3) or CAT (Eq. 6), depending on the value of X2.
F.1 PNA EXPERIMENTS
In Tables 13 and 14, we show the results for the datasets described in App. C -ssinn L-CAT and CAT in conjunction with the PNA model (Corso et al., 2020). First, we note that standard PNA works quite well in most cases. Second, if we focus on Table 13, we observe that the standard attention models (i.e., PNAGAT and PNAGATv2) perform significantly worse than the other approaches, in particular on datasets with large average degree, e-g., on Amazon Computers. Finally, we observe that the L-CAT models (i.c., L-PNACAT and L-PNACATv2) drastically improve the performance of their attention counterparts and achieve similar performance the PNA model, with lower performance the Gitffub and Facebook datasets and higher performance on Cora and CiteSeer.
To keep the same number of parameters, we reuse the PNA weights to compute the attention scores (W,- = Wx = W.). However, this could be detrimental, as the role of W, is completely different from that of W, and W.. Tables 15 and 16 show the same experiments as before, but using different parameters to compute the keys and queries (i.c., W = W. # W.). We
32

---

Published as a conference paper at ICLR 2023
observe that the increase of parameters generally helps both CAT and L-CAT models, now outperform the base PNA model in some settings.
Table 13: Test accuracy (%) of the PNA (Corso et al., 2020) models for different datasets (sorted by average node degree), averaged over ten runs. Bold numbers statistically different to their baseline model (a = 0.05). Best average performance is underlined.
Dataset
Amazon Compaters
Amazon Ploto
Gitilub
Facebook PagePage
Cocuthor Plysies
TwitchEN
Avg. Deg.
35.76
31.13
15.33
15.2 22.22
14.38
10.91
PNA
86.51
1.22
93.23 = 0.65
82.33 + 0.51
94.28 + 0.34
96.09 + 0.14
59.25 + 1.19
PNAGAT
57.59 + 10.19
74.78 = 8.74
72.77 = 2.06
71.49
11.23
96.05 + 0.25
51.22 +:2 3.02
PNACAT
81.48 + 3.81
91.73
+ 1.24
75.55 + 3.33
93.10
+ 0.41
96.16 + 0.15
59.11 1.94
LPNACAT
86.45
92.76
78.74
93.59
96.24 0.13
PNAGATY2
36.93 4.07
60.13
- 4.81
73.93
+ 1.89
58.91
+: 3.42
95.61
+ 0.29
54.45 + 1.60
PNACAT
79.08 + 2.62
88.61
+ 3.24
75.11
+ 2.79
92.77
+ 0.50
96.06
0.18
56.72 2.43
LPNACAT
85.10 4 1.70
92.19
+ 0.55
79.79
1.40
93.54
0.36
96.03
0.19
58.19 1.53
Table 14: Test accuracy (%) of the PNA (Corso et al., 2020) models for different datascts (sorted by average node degrec), averaged over ten runs. Bold numbers are statistically different to their baseline model (a = 0.05). Best average performance is underlined.
Dataset
CowuthorCS 8.93
DBLP 5.97
PubMed 4.5
Cora 3.9
CiteSeer
Avg. Deg,
2.74
PNA
93.30 + 0.31
83.37 + 0.32
88.37 = 0.73
84.94 + 1.19
73.92 + 0.97
PNAGAT
92.46 0.95
83.42 + 0.39
88.40 + 0.33
84.67 1 0.69
74.64 1 0.82
PNACAT
92.90 1 0.24
83.35 1 0.40
88.24 = 0.30
85.58 1 1.00
74.94 1 1.68
L-PNACAT
93.11 1 0.24
83.21 1 0.55
88.22 + 0.40
85.77 1 1.01
75.08 1 1.05
PNAGATV2
90.14 1 0.82
83.37 1 0.34
88.14 1 0.45
85.04 1 0.86
74.50 1 1.18
PNACATv2
92.78 0.27
83.22 + 0.38
88.28 0.30
85.41 0.98
74.42 + 1.11
LPNACATT22
98.02 0.37
83.54 - 0.65
88.23 = 0.58
85.48 = 0.98
74.76 = 1.57
Table 15: Test accuracy (%) of the PNA (Corso et al., 2020) extended models with W W: + Wa for different datasets, averaged over ten runs. Bold nunbers are statistically different to their baseline model (a = 0.05). Best average performance is underlined.
Amazon Computers
Amazon Photo
Gitfib
Pacebook PagePage
Conuthor Physies
TwitchEN
Avg. Deg.
35.76
31.13
15.33
15.22
14.38
10.91
PNA
86.51
1.22
93.23
0.65
82.33
0.51
94.28
0.34
96.09
0.14
59.25
PNAGAT
48.65
19.25
68.01
20.32
72.97 + 1.07
70.17
12.02
96.02
0.34
53.27
2.54
PNACAT
83.45 = 2.60
91.62
- 1.30
76.35 + 2.71
93.31 = 0.55
96.22 = 0.13
59.23
+ 2.25
L-PNACAT
2.50
PNAGATV2
39.19 + 1.09
62.19 + 11.30
73.97 + 1.67
63.00 = 1.95
95.83 = 0.36
55.21 1.05
PNACATv2
81.20
3.63
91.32
1 0.80
74.37
+: 2.18
92.98 0.36
96.14
0.16
56.21
: 2.01
PNACATV22
86.22
0.83
92.98
0.89
79.78
2.48
0.37 93.44
0.12 96.13
60.26 1.25
33

---

Published as a conference paper at ICLR 2023
Table 16: Test accuracy (%) of the PNA (Corso et al., 2020) extended models with Wg WE # W. for different datascts, averaged over ten runs. Bold numbers are statistically different their bascline model (a = 0.05). Best average performance is underlined.
Dataset
CoarthorCS
DBLP 5.97
PubMed 4.5
Cor
CiteSeer
Avg. Deg.
8.93
3.9
2.74
PNA
93.30 + 0.31
83.37 = 0.32
88.37 + 0.73
84.94 + 1.19
73.92 + 0.97
PNAGAT
92.50
0.46
83.22
0.45
88.43 0.29
84.89 1.15
75.76 1.29
PNAGAT
92.97
0.47
83.28 = 0.59
88.27 + 0.43
85.09 + 0.70
75.41 1.51
PNAGAT
93.17 + 0.30
83.50 = 0.29
88.54 + 0.45
85.63 = 0.92
75.22 + 1.12
PNAGATv2
90.00 1.01
83.40 0.48
88.14 + 0.31
85.16 0.91
76.14 1.33
PNAGATV2
92.74 0.20
83.05 0.49
88.38 + 0.31
85.21 + 0.83
75.80 1.26
PNAGATv2
93.02 + 0.30
83.24 = 0.44
88.28 + 0.35
85.04 + 0.94
75.80 + 1.19
Table 17: Test accuracy (%) of the GCNII (Chen et al., 2020) models for different datasets, averaged over ten runs, Bold numbers are statistically different their baseline model (a 0.05). Best average performance is underlined.
Dataset
Amazon Computers
Amazon Photo
GitHub
Pacebook PagelPage 15.22
Conuher Plysics
TwitchEEN
Avg. Deg.
35.76
31.13
15.33
14.38
10.91
GONH
90.82
0.20
95.51 + 0.48
84.11 + 0.76
94.03 + 0.30
96.58
0.11
60.94 + 1.66
GONICAT
89.04 + 0.87
91.71 + 0.57
82.34 + 0.61
91.18 + 0.82
96.69
0.13
57.76 + 1.76
GONICAT
89.83
0.42
95.31
0.25
83.15 + 0.51
93.25 + 0.37
96.69
0.09
60.51
1.12
L-GONIICAT
90.03
0.42
95.23
0.39
83.50
0.57
93.71 + 0.33
96.87
0.14
61.14
1.64
GCNTIGATV2
81.26 + 2.80
89.23 + 5.30
81.23 + 0.45
83.82 = 1.24
96.14
0.28
56.25 + 1.56
CONIICATY2
89.59 + 0.45
95.03
0.55
82.45 + 0.30
92.55 + 0.52
96.50 + 0.09
59.04 + 1.49
L.GONIÇATI2
0.48
83.05
93.68
0.11
F.2 GCNII EXPERIMENTS
Similarly, we have run the experiments from $6.2, this time combining GCNII (Chen et al., 2020) with GAT, CAT, and T-CAT explained above. Results shown in Tables 17 and 18, in which we can observe that the baseline model obtains the best results so far in the manuscript (in comparison with both GCN and PNA). And just as before, we observe again that CAT and L-CAT always improve with respect to their base models, staying on par with the bascline GNCII model and, somctimes, even outperforming the bascline model on average (c.g., Coauthor Physics, TwitchEN). As with the experiments for PNA, Tables 19 and shows the results when the attention matrices are diffferent from the value matrix (W, W + W.). We can similarly observe that most of the results are improved with the additional parameters, beating the baseline model in different datasets.
Table 18: Test accuracy (%) of the GCNII (Chen et al., 2020) models for different datasets, averaged over ten runs. Bold numbers are statistically different to their bascline model (a 0.05). Best average performance underlined.
Dataset
ConuthorCS 8.93
DBLP 5.97
PubMed 4.5
Cora 3.9
CiteSeer 2.74
Avg. Deg.
GCNIT
95.36 + 0.18
83.86 + 0.14
89.05 + 0.28
86.49 + 0.79
76.46 + 0.71
GCNIIGAT
95.32 0.27
83.45 0.60
88.24 + 0.34
85.72
1.05
75.78
0.77
GCNIICAT
95.12 + 0.25
83.86 + 0.23
88.65 = 0.40
85.51
= 0.95
76.60 + 0.50
L-GCNIICAT
95.30 + 0.29
83.76 + 0.26
88.72 + 0.35
85.48
+ 0.96
76.76 + 0.51
GCNIIGATY2
93.37
0.73
83.70 + 0.42
88.49 + 0.34
85.82
1.35
75.98 0.71
GCNIICATV2
95.01 0.32
83.93 + 0.36
88.60 - 0.27
85.72
1.03
76.62 0.63
L-GCNICCTI22
95.29 1 0.23
83.93 + 0.41
89.12 1:2 0.35
85.73 - 0.88
76.22 = 0.98
34

---

Published as a conference paper at ICLR 2023
Table 19: Test accuracy (%) of the GCNII (Chen et al., 2020) extended models with Wg W& o W. for different datasets, averaged over ten runs. Bold numbers statistically different to their bascline model (a = 0.05). Best average performance is underlined.
Dalaset
Amazon Computers
Amazon Photo
GaHuu
Pacebook PagePage
Conuthor Plyseca
TwitchEN
Avg. Deg.
35.76
31.13
15.33
15.
14.38
10.91
GCNII
90.82 +: 0.20
95.51 + 0.48
84.11 +: 0.76
94.03 : 0.30
96.58
0.11
60.94 +: 1.66
GONIGAT
89.24
0.59
94.66
+ 0.59
82.45
+ 0.65
90.90 + 0.71
96.90
0.16
58. 12 +: 2.02
GONICAT
0.37
0.31
0.07
59.60
L-GCNTICTT
90.35 + 0.46
95.53
0.35
83.48
0.47
93.63 + 0.39
96.80
0.09
60.77
2.15
GCNIIGATV2
85.70 + 2.58
91.21 + 2,13
81.43
+ 0.39
84.59 = 0.79
96.35
0.20
55.23 +: 2.15
GONUCATV2
0.67
82.50
93.04
0.40
96.35
V.
90.24 0.32
95.53
0.28
83.34 + 0.45
93.67 + 0.47
0.14 96.73
60.65 1.13
Table 20: Test accuracy (%) of the GCNIT (Chen et al., 2020) extended models with
W We f W, for different datasets, averaged over ten runs. Bold numbers statistically different to their baseline model (a = 0.05). Best average performance is underlined.
Dataset
CouuthorCS 8.93
DBLP
PubMed 4.5
Cora
CiteSeer
Avg. Deg.
5.97
3.9
2.74
GCNTI
95.36 = 0.18
83.86 + 0.14
89.05 + 0.28
86.19 + 0.79
76.46 + 01.1
GCNTIGAT
95.36 + 0.20
83.60 + 0.32
88.33 + 0.35
85.26 + 1.19
76.30
0.78
GONTICAT
95.20 + 0.12
83.89 + 0.29
88.45
+ 0.29
86.44 + 1.22
76.70 + 0.60
L-GCNICCAT
95.47 = 0.16
83.70 + 0.40
88.08 + 0.47
86.02 + 1.43
76.54 + 0.59
GCNIIGATV2
93.97 0.57
83.67 + 0.21
88.21 + 0.16
85.28 + 1.11
76.58 0.64
GCNTICATY2
95.05 1 0.33
83.78 +
88.35
+ 0.34
86.49
0.90
75.28 0.84
L-GNNIICAT22
95.45 1 0.18
83.86 1
0.32 88.06
86.49
76.80 0.42
35


Reviews:
[{"review_id": "oryOk8Tta-c", "reviewer": "Reviewer_UgAb", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Combining Graph Convolutional Networks (GCNs) with Graph Attention Trees (GATs), the authors propose a novel architecture for Graph Neural Networks, Learnable Convolutional Attention Layer (L-CAT).\n\n\nIn order to bridge the gap between the graph convolutional layer, the graph attention layer, and the graph convolutional attention layer, this paper introduces a new layer type for graph neural networks.\n\n\nThey add two scalar parameters per layer and learn them along with the other parameters in an end-to-end fashion. Inspiring theoretical conclusions based on prior work are presented, and the authors' suggested strategy is experimentally validated. ", "summary_of_the_review": "I recommend to accept the paper.", "strength_and_weaknesses": "- The overall quality of the writing and organization of the work is quite high. \n\n- The background of the study and the significance of the contribution are laid out in great detail. \n\n- The second and third parts (preliminaries and limitations of GCN and GAT) offer an insightful summary of GNNs. \n\n- Findings from theory are addressed, and they are also confirmed by empirical research.\n\n- In general, improving graph neural networks by interpolating across different layer types using parameters that can be learned in an end-to-end manner seems promising.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UJiRbadp-26", "reviewer": "Reviewer_CSVs", "summary": "", "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": "", "summary_of_the_paper": "This manuscript focuses on the problem of learning better aggregation attention. The motivation comes from the observation that there is no clear winner of the existing three aggregation methods, including native GCN and GAT. The authors propose a new CAT aggregation method and merge it with GCN and GAT. The proposed method is evaluated on several standard datasets to show its effectiveness.", "summary_of_the_review": "In short, the main concerns of this manuscript are two parts: the insufficient evaluation and the limited novetly.", "strength_and_weaknesses": "Strength\n\n1, The motivation that different data may need different aggregation makes sense.\n\n2, The analysis of the evaluation of $\\lambda_1$ and $\\lambda_2$ is interesting.\n\nWeaknesses\n\n1, The comparison is insufficient. Only two methods are compared on most of the datasets: GCN and GAT. The weak comparison makes it hard to support the effectiveness of the proposed method.\n\n2, The novelty is limited. The core idea of the proposed method is to integrate several different aggregation strategies. There are already several research works along this line like the sampling method proposed in [1]. \n\n3, In terms of technical detail, it seems that the proposed method is designed only for native GCN and GAT. It is hard to generalize the proposed method to other kinds of aggregations. It is more like another new aggregation scheme, which limits the contribution.\n\nOther issues:\n\nThe highlights of Table.2 are improper.  E.g. the GCN performs the best on proteins while the L-CATv2 is highlighted.\n\n[1] Meta-Aggregator: Learning to Aggregate for 1-bit Graph Neural Networks, ICCV 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": "Not applicable"}, "extra_text": {}}, {"review_id": "Mt3S-ChcxhT", "reviewer": "Reviewer_kUTn", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes graph Convolutional Attention Networks (CAT) to exploit the advantages of Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs). Further, the authors design Learnable graph Convolutional Attention Networks (L-CAT), which softly selects GCNs, GATs, and CAT. The paper presents theoretical analysis of CAT and conduct node classification tasks using ten datasets.", "summary_of_the_review": "Overall, I think this paper is marginally over the acceptance threshold. The paper demonstrates the effectiveness of their methods through theoretical analysis. ", "strength_and_weaknesses": "**Strengths**\n\n(1) This paper shows the effectiveness of proposed methods with theoretical analysis. \n\n(2) The proposed CAT shows consistently good performance across datasets.\n\n(3) Experiments on synthetic datasets prove the CAT’s effectiveness compared to GCNs and GATs. \n\n**Weakness** \n\n(1) The formulation GCNs is different from the formulation proposed in [1] on undirected graphs. Since the datasets used in experiments are undirected graph, it is more appropriate to use $\\tilde{D}^{-1/2}\\tilde{A}\\tilde{D}^{-1/2}$.\n\n************************Additional Questions************************\n\n(1) I wonder the performance of GCN, GAT, and CAT when using more than 1 layer on the synthetic dataset.\n\n---\n\n[1] Fountoulakis, Kimon, et al. \"Graph Attention Retrospective.\" arXiv 2022.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster