Learning Conjoint Attentions for Graph Neural Nets
Authors: Tiantian He
Yew-Soon Ong
L Bai
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph neural networks
graph attentions

Abstract: In this paper, we present Conjoint Attentions (CAs), a class of novel learning-to-attend strategies for graph neural networks (GNNs). Besides considering the layer-wise node features propagated within the GNN, CAs can additionally incorporate various structural interventions, such as node cluster embedding, and higher-order structural correlations that can be learned outside of GNN, when computing attention scores. The node features that are regarded as significant by the conjoint criteria are therefore more likely to be propagated in the GNN. Given the novel Conjoint Attention strategies, we then propose Graph conjoint attention networks (CATs) that can learn representations embedded with significant latent features deemed by the Conjoint Attentions. Besides, we theoretically validate the discriminative capacity of CATs.  CATs utilizing the proposed Conjoint Attention strategies have been extensively tested in well-established benchmarking datasets and comprehensively compared with state-of-the-art baselines. The obtained notable performance demonstrates the effectiveness of the proposed Conjoint Attentions.

Learning Conjoint Attentions for Graph Neural Nets
Tiantian He Yew-Soon Ong! Lu Bai
Agency for Science, Technology and Research (A*STAR)
DDSAIR, Nanyang Technological University [He_ Mie_Tiantia, Bai Lu (aippeiipc.aaeeeee a-star edu..redu..a. sg, Ong_ Reg_Yew_rr Yes__ee_SSoone _Soonhh......... a-star aa-star.edu.sg {t (tiantian, he, bailu, asysong (aaysngg@enti @ntu. edu.
Abstract
In this paper, we present Conjoint Attentions (CAs), a class of novel learning- to-attend strategies for graph neural networks (GNNs). Besides considering the layer-wise node features propagated within the GNN, CAs can additionally in- corporate various structural interventions, such node cluster embedding, and higher-order structural correlations that can be learned outside of GNN, when computing attention scores. The node features that are regarded as significant by the conjoint criteria are therefore more likely to be propagated in the GNN, Given the novel Conjoint Attention strategies, then propose Graph conjoint attention networks (CATss) that can learn representations embedded with significant latent features deemed by the Conjoint Attentions. Besides, we theoretically validate the discriminative capacity of CATs. CATs utilizing the proposed Conjoint At- tention strategies have been extensively tested in well-established benchmarking datasets and comprehensively compared with state-of-the-art baselines. The ob- tained notable performance demonstrates the effectiveness of the proposed Conjoint Attentions.
Introduction
Graph neural networks (GNNs) have shown much success in the learning graph structured data. Amongst these noteworthy GNNs, tlaeet GNNs 33 have drawn increasing interest lately, and have been applied to solve plethora of real-world problems competently, including node
classification
17 33
image segmentation 35 and social recommendations (30].
Empirical attention mechanisms adopted by GNNs aim leverage the node features (node embed- dings) to compute the normalized correlations between pairs of nodes that are observed to connect. Treating normalized correlations (attention scores/coefficients) pairs, attention-baa based GNN typically performs weighted sum of node features which are subse- quently propagated to higher layers. Compared with other GNNs, especially those that aggregate node features with predefined strategies [T] 17 19, attention-base GNNs provide a dynamical way for feature aggregation, which enables highly correlated features from neighboring nodes to be propagated in the multi-layer neural architecture. Representations that embed with multi-layer correlated features are consequently learned by attention-based GNNs, and can be used for various downstream tasks.
the relative weights between node
Though effective, present empirical graph attention has several shortcomings when aggregating node features. First, the computation of attention coefficients is limited solely to the correlations of internal factors, i.e., layer-wise node features within the neural nets. External factors such as cluster structure and higher-order structural similarities, which comprise heterogeneous node-node relevance have remained underexplored be positively incorporated into the computation of more purposeful attention scores. Second, the empirical attention heavily leaning on the node features may cause
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

over-fitting in the training stage of neural nets [4]. The predictive power of attention- based GNNs is consequently limited.
To overcome the mentioned challenges, in this paper, we propose a class of generic graph attention mechanisms, dubbed here Conjoint Attentions (CAs). Given CAs, we construct Graph conjoint attention networks (CATs) for different downstream analytical tasks. Different from previous graph attentions, CAs are able to flexibly compute the attention coefficients by not solely relying on layer- wise node embeddings, but also allowing the incorporation of purposeful interventions brought by factors external to the neural net, e.g., node cluster embeddings. With this, CAT' are able to learn representations from features that are found as significant by diverse criteria, thus increasing the corresponding predictive power. The main contributions of the paper are summarized as follows.
We propose Conjoint Attentions (CAs) for GNNs. Different from popular graph attentions that rely solely on node features, CAs are able to incorporate heterogeneous learnable factors that can be internal and/or external to the neural net to compute purposeful and more appropriate attention coefficients. The learning capability and hence performance of CA-based GNNs is thereby enhanced with the proposed novel attention mechanisms.
For the first time, theoretically analyze the expressive power of graph attention lay- ers considering heterogeneous factors for node feature aggregation, and the discriminant capacity of such attention layers, i.e., CA layers is validated.
Given CA layers, we build and demonstrate the potential of Graph conjoint attention networks (CATs) for various learning tasks. The proposed CATs are comprehensively investigated established and extensive benchmarking datasets with comparison studies to a number of state-of-the-ann baselines. The notable results obtained are presented to verify and validate the effectiivness of the newly proposed attention mechanisms.
2 Related works
To effectively learn low-dimensional representations in graph structured data, many GNNs have been proposed to date. According to the ways through which GNNs define the layer-wise operators for feature aggregation, GNNs can generally be categorized as spectral or spatial [38).
Spectral - layer-wise function for feature aggregation in spectral GNNs is defined according
to the spectral representation of the graph. For example, Spectral CNN B constructs the convolution layer based on the dign-ddecopoosition of graph Laplacian in the Fourier domain. However, such layer is computationally demanding. To reduce such computational burden, several approaches adopting the convolution operators which are based on simplified or approximate spectral graph theory have been proposed. First, parameterized filters with smooth coefficients are introduced for Spectral CNN to incorporate spatially localized nodes in the graph [1]. Chebyshev expansion 7 is then introduced to approximate graph Laplacian rather than directly performing eigen gegen-dcommositionn Finally, the graph convolution filter is further simplified by only considering first or higher order of connected neighbors [17 37,,
so to make the convolution layer more computationally efficient.
Spatial GN contrast, spatial GNNs define the convolution operators for feature aggregation by directly making use of local structural properties of the central node. The essence of spatial GNNs consequently lies in designing an appropriate function for aggregating the effect brought by the features of candidate neighbors selected based on appropriate sampling strategy. To achieve this, it sometimes requires to learn a weight matrix that accords to the node degree [8], utilize the power of transition matrix to preserve neighbor importance 1
[8 19 42). extract the normalized neighbors
24], or sample a fixed number of neighbors 13
As representative spatial GNNs, attention-based GNNs (GATs) 12 33] have shown promising performances on various learning tasks. What makes them effective in graph learning result of adopting the attention mechanism, which has been successfully used in machine reading and translation [5] 122. and video processing [40), to compute the node-feature- feature-based attention scores between central node and its one-hop neighbors (including the central node itself). Then, attention- based GNNs use the attention scores to obtain a weighted aggregation of node features which are subsequently propagated to the next layer. As result, those neighbors possessing similar features may then induce greater impact on the center node, and meaningful representations can be inferred by GATs, Having investigated previous efforts to graph neural networks, we observe that the computation

---

of empirical graph attentions heavily relies on layer-wise node features, while other factors, e.g.. structural properties that can be learned outside of neural net, have otherwise been overlooked. This motivates us in proposing novel attention mechanisms in this paper to alleviate the shortcomings of existing attention-base graph neural networks.
3 Graph conjoint attention networks
In this section, we elaborate the proposed Conjoint Attention mechanisms, which are the comerstones for building layers of novel attention-based graph neural networks. Mathematical preliminaries and notations used in the paper are firstly illustrated. Then, how to construct neural layers utilizing various Conjoint Attention mechanisms are introduced. Given the formulated Conjoint Attention layers, we finally construct the Graph conjoint attention networks (CATs).
3.1 Notations and preliminaries
Throughout this paper, assume graph G {V, E} containing N nodes, |E] edges, and C classes (C < N) to which the nodes belong, where V and E respectively represent the node and edge set. We use A E {0, LJNNXN and X R x represent graph adjacency matrix and input node feature matrix, respectively. AA denotes the union of node and its one-hop neighbors. W and (h!h...... denote the weight matrix and features (embeddings) of node i at Ith layer of CATs, respectively, and h is set be the input feature, i.e., X. For the nodes in Ni. their possible feature vectors form multiset Mj = (S;, j4)., where S. = {81,...., Sn) is the ground set of M, which contains the distinct elements existing in M, and nr : S - N is the multiplicity function indicating the frequency of occurrence of each distinct in M,.
3.2 Structural interventions for Conjoint Attentions
As aforementioned, the proposed Conjoint Attentions are able to make use of factors that are either internal or external to the neural net to compute new attention coefficients. Internal factors refer the layer-wise node embeddings in the GNN. While, the external factors include various parameters that can be learned outside of the graph neural net and can potentially be used to compute the attention scores. Taking the from cognitive science, where contextual interventions have been identified as effective external factors that may improve the attention and cognitive abilities [16], here we refer these external structural properties structural interventions henceforth for the computing of attention coefficients. Next, we propose a simple but effective way for CAs to capture diverse structural interventions external to the GNNs. Let Cij be some structural intervention between ith and jth node in the graph. It can be obtained with the following generic generating function:
Cij arg min V (o(C).) Yoj), ((C),s
(I)
where (-(-) represents distance function and <6-) stands for operator transforming C to the same dimensionality of Y. Given the generic generating function in Eq. it is known that many effective paradigms for learning latent features can be used for the subsequent computation of Conjoint Attentions, if the prior feature matrix Y is appropriately provided. Taking A as the prior feature matrix, in this paper, we consider two generation processes that can capture two unique forms of structural interventions. Let VD()) be the euclidean distance, when of (C)) = VVT we have:
sy.
Cij arg min (A,, VV!) VV?,
where we use an --y matrix V to approximate C to reduce the computational burden. As shows in Eq. (2). Ctj attempts acquire the structural correlation pertaining to node cluster embeddings, based on matrix factorization (MF). A higher Cıý learned by Eq. 2 means a pair of
nodes are very likely to belong to the same cluster. If (CC), E, VVT Ai ij. we have:
Cij = arg min(A VV
Σ EVVAA,
(3)
As shown in Eq. 33. Cij is the coefficient of self self-expressiveness (SC) which may describe the global relation between node i and j. A higher Cūj inferred by Eq. means the global structure
3

---

Conjaicl Altertions for
Implitd direction
4g
neightor aggregation
Expirit divectin
normalization
sollmax,
softmax
Sj
O 0000
O000 Wh
Strutural Interventinn Gevevalion
Wh
Wh
Figure I: Graphical illustration of the Conjoint Attention layer used in CATs. Left: CA mechanism using Implicit direction strategy (CAT-I), Right: CA mechanism using Explicit direction strategy (CAT-E). Both two mechanisms consider learnable structural interventions.
of node can be better represented by that of node j. and consequently this pair of nodes are more structurally correlated. It is known that both aforementioned properties have not been considered previously by empirical graph attention mechanisms. We believe considering either of them as structural interventions for the Conjoint Attentions could lead to better attention scores for feature aggregation. Note that other types of may also be feasible for the proposed attention mechanisms, as long as they are able capture meaningful property which is not already possessed within the node embeddings of the GNN.
3.3 Conjoint Attention layer
Having obtained a proper C, we present next the Conjoint Attention layer, which is the core module for building CATs and will used in our experimental study. Different from the attention layers considered in other GNNs, the attention layer proposed here adopts novel attention mechanisms, ie.. Conjoint Attentions. is known that empirical graph attentions solely concern the correlations pertaining to the internal factors, e.g., node embeddings locating in each layer of the neural net. How those diverse forms of relevance, e.g., the correlation in terms of node cluster embeddings and self-expressiveensss may affect the representation learning is therefore yet to be investigated in previous works. Besides utilizing the correlations pertaining to node embeddings, the proposed Conjoint Attentions take into additional considerations the structural interventions brought by diverse node-node relevance, which is learned outside of the neural network. As a result, each Conjoint Attention layer may pay more attentions to the similar embeddings of neighbors, well as to the ones that share other forms relevance with the central node. Node representations possessing heterogeneous forms of relevance can be learned by the CATs.
Given set of node features (h/) each hy RP', the Conjoint Attention layer maps them into D dimensional space (h(-1) i...... according to the correlations of node features and aforementioned structural interventions. The contextual correlation between two connected nodes, say v, and Uj is firstly obtained. To do so, we directly adopt the feature-based attention mechanism considered by existing graph attention networks (GAT) [33:
exp(LeakyRel..(a" (W'h) || ))
fij = E exp(LeakyReLU(a' (W'h)) || Wh))))
where ā E 1220'++ is a vector of parameters of the feedforward layer, || stands for the concatenation function, and W is D x D' parameter matrix for feature mapping. Given Eq. (4). the proposed CA layer captures the feature correlations between connected nodes (first-order neighbors) by computing the similarities w.r.t. node features mapped to next layer.
As mentioned, determining the attention scores solely based on node features internal to GNN may result overlooking other important factors. To overcome this issue, the proposed CA layer attempts to learn the structural interventions described in Section 3.2) and presents the additional

---

new information for computing the attention scores. Given any learnable parameter Cty (structural intervention) between two nodes, CA layer additionally obtains a supplementary correlation as follows:
Sij exp (Cg)
(5)
ΣREA; exp (C.s)
Given fiy and Sij. propose two different strategies to compute the Conjoint Attention scores, aiming at allowing CATs to depend on the structural intervention at different levels. The first mechanism is referred here Implicit direction. It aims at computing the attention scores whose relative significance between structural and feature correlations can be automatically acquired. To do so, each CA layer introduces learnable parameters, 95 and gs. to determine the relative significance between feature and structural correlations and they can be obtained as follows:
exp(gs)
exp (gx)
rf exp (g.) + exp (gg) exp (g.) + exp (gy)*
where y' orry ryy represents the normalized significance related different types of correlations. Given them, CAT then computes the attention score based on Implicit direction strategy:
rf fiz + 85j
aij ExEN, (ry- fik rr Stk
ry fy + S8jj
Given the attention mechanism shown in Eq. 7 Ony attempts to capture the weighted mean attention in terms of the various node-node correlations, which are the ones internal or external to the GNN, Compared with the attention mechanism solely based on features of one-hop neighbors, oij computed by Eq. ( may be adapted according to the implicit impact brought by different structural interven- tions, e-g., correlations pertaining node cluster embeddings and self-expressiveness coefficients. Moreover, the relative significance r' can also be automatically inferred through the back propagation process. More smooth and appropriate attention scores can thereby be computed by the CA layer for learning meaningful representations,
To enhance the impact of structural intervention, the CA layer has another strategy, named here as Explicit direction, to compute attention scores between neighbors. Given fiy and Sij, the attention scores obtained via the Explicit direction strategy is defined as follows:
Sij 883
Oriy ΣREN, fik
(8)
Compared with Eq. (7). Sty explicitly influences the magnitude of fiy. so that those node pairs which are irrelevant terms of Ct will never be assigned with high attention weights. Based on Explicit direction strategy, the CA layer becomes more structurally dependent when performing message passing to the higher layers in the neural architecture.
Having obtained the Conjoint Attention scores, the CA layer is now able to compute a linear combination of features corresponding to each node and its neighbors output, which will be either propagated to the higher layer, or be used as the final representations for subsequent learning tasks. The described output features be computed as follows:
h = (as + e
1 Wi
w'
Σ a. W'n
(9)
jEA..jj'
where E (0, is learnable parameter that improves the expressive capability of the proposed CA layer.
3.4 Construction of Graph conjoint attention networks (CATs)
In Fig. the Conjoint Attention layers that use the attention mechanisms proposed in this paper are graphically illustrated. We are now able to construct Graph conjoint attention networks (CATs) using a particular number of CA layers proposed. In practice, we also adopt the multi-head attention strategy 32 to stabilize the learning process. CATs may either concatenate the node features from multiple hidden layers the input for next layer, or compute the average of node features obtained by multiple units of output layers as the final node representations. For the details on implementing multi-head attention in graph neural networks, the reader is referred to (33.
5

---

4 Theoretical analysis
Study the expressive power of various GNNs has drawn much attention in the recent. It concers whether a given GNN can distinguish different structures where vertices possessing various vectorized features. It has been found that what the neighborhood aggregation functions of all message-passing Seisfeiler-Lehmall test (1-WL test), which is
GNNs aim at are analogous to the 1-dimensional injective and iteratively operated in the Ceisfeiler-Lehmanr algorithm [6 41 4 does. As result, all mressage-passingg GNNs are as most powerful as the 1-WL test [4]] The theoretical validation of the expressive power of given GNN thereby lies in whether those adopted aggreation/readout
functions are homogeneous to the 1-WL test.
One may naturally be interested in whether the expressive power of the proposed CAT layers is as powerful as the 1-WL test, which can distinguish all different graph structures. To do so, we firstly show that neighborhood aggregation function (Eq- ( without the term for improving expressive capability (i.e.. 1 Wh, in Eq. (9) still fails to discriminate some graph structures possessing [N3]
certain topological properties. Then, by integrating the term of improving expressive capability, all the proposed CA layers are able to distinguish all those graph structures that cannot be discriminated previously.
For the function of neighborhood aggregation solely utilizing the strategy shown in Eq. we have the following theorem pointing out the conditions under which the aggregation function fails to distinguish different structures.
Theorem 1 Assume the feature space X is countable and the aggregation function using the weights computed by Eq. 17) is represented as h(c, X) = E (gzg(()) where is the feature of center node, X E X is multiset containing the feature vectors from nodes in N₁. g(.) is a function for mapping inpul feature X, and Oez is the weight between g(c) and g(r). For all g and the strategy in Eq. 17). h(a,, X1) h(c2, X2) if and only is = C2. X1 (S, X2 12,, and Ey=r.yeX, Jay Ey=z.yeX, Seau = q d.yyx Sc29 - - -y= Selyb for E S. In other words, h will map different multisets into the same embedding iff the multisets have same central node feature, same underlying set, and the difference in feature- basuee scores is proportional (Fe) ) to the opposite of that in the weights corresponding the structural interventions.
and
We leave the proof of all the theorems and corollaries in the appendix. For the aggregation function utilizing the strategy shown in Eq. (8) we have the following theorem indicating the structures which cannot be correctly distinguished.
Theorem 2 Under the same assumptions shown in Theorem 7 for all 9 and the stralegy in Eq. B) ((1,,))) = h(e2, X2) if and only if C1 = Cz X, {1. X2 = {S, 12),, and E Φ( (Cezg) for q > 0 and x E S, where vb(.) is an function for mapping values to Rt In other words, h will map different multisets into the same embedding iff the multisets have same central node feature, same node features whose corresponding mapped structural interventions are proportional.
4. Σ wEx, (CCeja)= =
Theorems and indicate that the CA layers may still fail to distinguish some structures, if they exclude the improving term shown in Eq. (9) However, GNNs utilizing Eqs. (7) (8) can still be more expressively powerful than classical GATs. As node features and structural interventions are heterogeneous, intuitively, structures satisfying the stated conditions should be infrequent. This may well explain why those GNNs concerning including external factors, e.g., some structural properties into the computation of attention coefficients may experimentally perform better than GAT'. However, when distinct multisets with corresponding propertics meet the conditions mentioned in Theorems []] and the attention mechanisms solely based Eqs. 7 or 8 cannot correctly distinguish such multisets. Thus, GNNs only utilizing Eqs. (7) or (8) as the feature aggregation function fail to reach the upper bound of expressive power of all messsgge-passing GNNs, i.e., the 1-WL test.
However, we are able to readily improve the expressive power of CATs to meet the condition of the 1-WL test by slightly modifying the aggregation function as Eq. (9) shows. Then, the newly obtained Conjoint Attention scores can be used to aggregate the node features passed to the higher layers. Next, we prove that the proposed Conjoint Attention mechanisms (Eqs. 7 reach the upper bound of message-passing GNNs via showing they can distinguish those structures possessing the properties mentioned in Theorems I and 2

---

Corollary Let T be the attention-based aggregator shown in Eq. (9) that considers one of the strategies in Eq. 7 or (8) and operates on a multiset H H. where H. is a node feature space mapped from the countable inpul feature space X. A H exists so that utilizing attention-bused aggregator shown in Eq. 9. T can distinguish all different multisets aggregation that it previously cannot discriminate.
Based on the performed analysis, the expressive power of CATs is theoretically stronger than state-of- the-art attention-based GNNs, e.g., GATs 33
Experiments and analysis 5
In this section, we evaluate the proposed Graph conjoint attention networks against a variety of state-of-the-art and popular baselines, on widely used network datasets.
5.1 Experimental set-up
Baselines for comparison- To validate the effectiveness of the proposed CAT's, we compare them with number of state-of-the-arr baselines, including Arma filter GNN (ARMA) [2] Simplified graph
convolutional Networks (SGC) [37]. Personalized Pagerank GNN (APPNP) [8], Graph attention
networks (GAT) [33], Jumping knowledge networks (JKNet) 42). Graph convolutional networks
(GCN) 17 GraphSAGE [33. Mixture model CNN (MoNet) 23 and Graph isomorphism network
(GIN) 41 As GAT can alternatively consider graph structure by augmenting original node features (i.e.. X) with structural properties, we use prevalent methods for network embedding, including k-eigenvectors of graph Laplacian (k>Lap) (26), Deepwalk [25]. and Matrix factorization- -based network embedding (NetMF) [26] to learn structural node representations and concatenate them with X as the input feature of GAT. Thus, three variants of GAT, i.e., GAT-k-Lap GAT-Deep, and GAT-NetMF are additionally constructed as compared baselines. Based on the experimental results previously reported, these baselines may represent the most advanced techniques for learning in graph structured data.
Testing datasets-Five widely-used network datasets, which are Cora, Cite, Pubmed 21 28 Coau- thorCS [29], and OGB-Arxiv [5], are used in our experiments. Cora, Cite, and Pubmed are three classical network datasets for validating the effectiveness of GNNs. However, it is recently found that these three datasets sometimes may not effectively validate the predictive power of different graph learning approaches, due the relatively small data size and data leakage [15 29] Thus, more massive datasets having better data quality have been proposed to evaluate the performance of different approaches [9] [5). In our experiment, we additionally use CoauthorCS and OGB-Arxiv as testing datasets. The details of all benchmarking sets can be checked in the appendix.
Evaluation and experimental settings-Two learning tasks, semi-supervised node classification and semi-supervised node clustering are considered in our experiments. For the training paradigms of both two learning tasks, we closely follow the experimental scenarios established in the related works 15 17 33, 43 For the testing phase of different approaches, we use the test splits that are publicly available for classification tasks, and all nodes for clustering tasks. The effectiveness of all methods is validated through evaluating the classified nodes using Accuracy. In the training stage, construct the two-layer network structure (i.e., one hidden layer possessed) for all the baselines and different versions of CAT's In each set of testing data, all approaches are run ten times to obtain the statistically steady performance. As for other details related to experimental settings, we leave them in the appendix.
5.2 Results node classification
The results on cenissuper node classification are summarized in Table As the table shows, CATs utilizing different attention strategies generally perform better than any other baseline all the testing datasets. Specifically, CAT utilizing Implicit direction (CAT-I-MF and CAT-I-SC) performs better than all the compared baselines in all the five datasets. CAT utilizing Explicit direction (CAT- E-MF and CAT-E-SC) is better than other compared baselines in four datasets out of five, except the case of CoauthorCS. In that dataset, CAT-E ranks the second-best when compared with other baselines.
7

---

Table I: Average Accuracy semi-supervissd node classification. Bold fonts mean CAT obtains better performance than any other baseline.
Cora
Cite
Pubmed
CoauthorCS
OGB-Arxiv
MoNet
81.96 + 0.50
64.22 = 0.16
79.78 + 0.33
91.96 + 0.75
47.71 + 0.27
GCN
81.42 0.19
7
09.660.33
91.44
71.78
GraphSAGE
81.12 0.41
71.06
79.04
93.06
19.07
JKNet
78.34 +
65.88
0.01
79.8
8.06
64.91 +: 0.01
APPNP
82.80 + 0.32
72.38 + 0.50
82.62
89.16
63.16
SGC
81.90 0.01
71.40 0.01
+ 0.04
93.60+0000
61.06 0.09
ARMA
80.06
70.00
76.46
86.28
0.17
GIN
81.58 0.62
66.90
80.76 0.33
93.03
64.02 0.18
GAT
83.84 0.61
1 1.36=0.44
81.50
92.80
72.39 0.07
GAT-A-Lap
14.10:00 0.24
71.18 - 0.52
82.56
72.47 + 0.06
GAT-NetMF
84.44 0.19
:.16
81.90
0.27
72.42 + 0.08
GAT-Deep
83.68 + 0.67
69.70
+ 0.57
80.13
+.117
72.79 + 0.09
CAT-I-MF
85.38 0.16
73.22
0.19
83.90
93.74
72.89
0.06
CAT-I-SC
85.50 + 0.22
73.18 + 0.22
84.28 + 0.20
93.70 0.11
72.85
+ 0.04
CAT-E-MP
85.56 0.19
73.24
0.21
83.60 + 0.17
93.40+0..1
72.81
0.09
CAT-E-SC
85.40 + 0.36
73.02 = 0.24
84.02 + 0.24
03.30
72.83 + 0.11
Table 2: Average Accuracy on semi- suni-supervised node clustering. Bold fonts mean CAT obtains better performance than any other baseline.
Cora
Cite
Pubmed
CoauthorCS
OGB-Arxiv
MoNet
79.42 + 0.86
63.07 = 0.11
79.39 + 0.61
88.75 + 0.54
53.08 + 0.15
GCN
74.25 + 0.13
6
77.83 - 0.75
8 73.50 9.51
75.02 0.07
GraphSAGE
78.46 = 0.56
6.10
79.52 1.13
JKNet
75.95 0.01
65.12
79.52 +
86.66:
71.28 + 0.01
APPNP
79.93 0.82
70.55 0.85
82.81 0.32
85.93
69.73 0.67
SGC
79.38 0.02
69.71
0.02
81.64 + 0.01
90.13
71.09 +0.37
ARMA
77.70 0.99
68.38 0.87
84.72
69.24 0.12
GIN
78.25 + 0.46
67.83 0.15
79.31
$9.97
63.85 + 0.18
GAT
11.390.1.
69.20
80.88 0.33
90.09
76.04
GAT-K-Lap
80.66 + 0.31
69.56 0.34
$1.59
0.118
76.21 0.06
GAT-NeMM
81.75 + 0.26
68.96 1 0.21
81.74
0.22
76.06 0.07
GAT-Deep
81.08 + 0.41
68.27 + 0.06
80.55
0.11
0.22
76.91 + 0.15
CAT-I-ME
82.17
0.11
71.15 0.12
8 0.07
+
90.26+0.23
77.72 + 0.07
CAT-I-SC
82.26
0.13
71.17
0.15
82.86 + 0.07
90.29 0.21
77.01
+ 0.16
CAT-E-ME
81.98
0.19
71.21
0.12
82.40
+ 0.08
+
76.93 + 0.16
CAT-E-SC
82.01 0.24
71.11 0.24
82.61 1 0.14
89.72
76.98 + 0.08
5.3 Results on node clustering
Node clustering can more challenging as all the nodes containing various potential structures in the graph are used in the testing phase. The results obtained show that CATs still performs robustly when compared with other baselines on this challenging task. As Table 2 shows, the Implicir direction strategy utilized by CAT other compared baselines in all the datasets. As for CAT utilizing Explicit direction, it ranks best on three datasets out of five. While the remaining two datasets, Pubmed and CoauthorCS, the performance CAT-E is competitive to the best. Based on the robust performance shown in Tables [ CAT is observed be one of the most effective GNNs for various graph learning tasks.
still ensure the proposed neural architecture outperform
and 2
5.4 Ablation study
To further investigate whether the proposed CA mechanisms are effective in improving the predictive power of CATs, we compared the performance CAs with that obtained by attention mechanisms considering various factors. Specifically, we let GAT computes attention coefficients using either

---

Clareitation Arc
10
Figure 2: Performance comparison on computing attention scores using different factors
structural interventions, i.e., node-node correlations pertaining to node cluster embeddings (MF in Eq. (2 and self-representation coefficients (SC in Eq. (3). or node features (Eq.44) F). Then GAT utilizing different attention strategies used to perform node classification and clustering tasks all the testing datasets. The performance comparisons between CAT' and GAT utilizing the aforementioned attentions have been summarized Fig. 2 As the figure shows, on both classification and clustering tasks, the proposed CA mechanisms perform statistically better than other attention strategies utilized by GAT. is also observed that the consideration of structural attentions (SC and MF) may also improve the performance of attention-bra -baeed GNNs. Such results thus experimentally agree with and validates our theoretical analysis in Section
6 Discussions
In this section, some further discussions that may provide better understandings to the proposed attention mechanisms are presented.
6.1 Comparisons between CATs and GATs with augmented node features
Besides the proposed Conjoint Attention mechanisms, directly concatenating input node features and structural embeddings [I] 25 27 31 is another effective way to make current GNNs more structural bias. In our experiments, it is shown that the learning performance have improved in most datasets when GAT uses the concatenation of original node features and various structural embeddings. However, in most datasets, such performance improvement is not as significant as that obtained by CATs, Different from directly concatenating the original node input features and structural embeddings for learning node representations, CAT's provide a smooth means to compute attention coefficients that jointly consider the diverse relevance regarding to both layer-wise node embeddings and external factors, like the structural interventions pertaining to the correlations generated by the node cluster embeddings considered in this paper. As a result, CATs can learn node representations from those nodes that are heterogeneously relevant and attain notable learning performance on all the testing datasets.
6.2 Potential limitations of the proposed approach
Although the proposed Conjoint Attentions are very effective in improving the learning performance of attention-base GNNs, they may also have possible shortcomings. First, the predictive power of the proposed CATs may be determined by the quality of the structural interventions. As the proposed Conjoint Attentions attempt to compute attention scores considering heterogeneous factors, their performance might be negatively affected by those contaminated ones. However, some potential methods may mitigate the side-effect brought by possible false/noisy external factors. One is to utilize adversarial learning modules 20 to alleviate the model vulnerability to external contamination. The other method is to consider learning effective factors from multiple data sources (i.e., multi-view). In previous works (39], multi-view learning has shown to be effective even when some view of data contaminated.

---

Second, both space and time complexity of the proposed Conjoint Attentions can be higher than the empirical attention-based GNNs, e.g., GAT. Thus, how select simple but effective strategy for capturing the interventions is crucial for the proposed Conjoint Attentions. In our experiments, we recorded the memory consumption of CATs when performing different learning tasks all the testing datasets and the corresponding results are provided in the appendix. We find that some simple learning paradigms, c.g., matrix factorization (Eq. (2) in the manuscript) can ensure CATs to outperform other baselines, while the space and time complexity does not increase much when compared with GATs. As for the SC strategy, its space complexity is relatively high, if it uses a single-batch optimization method. Therefore, more efficient optimization methods should be considered when CATs use SC to learn Ctj-
Third, the expressive power of the proposed Conjoint Attention-basee GNNs reaches the upper bound of the 1-WI. test in the countable feature space, but such discriminative capacity may not be always held by CAT's in the uncountable feature space. Previous works have proved that the expressive power of a simplex function for feature aggregation in a GNN can surely reach the upper bound of the 1-WL test only in countable feature space, multiple categories of functions for feature aggregations are required to maintain the expressive power of a GNN when the feature space is uncountable [6]. As all Conjoint Attentions belong to one category of function, i.e., mean aggregator, in this paper, we perform the theoretical analysis on the expressive power of CATs assuming the feature space is countable. Ideally, the expressive power of CATs can be further improved in uncountable space, if the proposed Conjoint Attentions are appropriately combined with other types of feature aggregators.
7 Conclusion
In this paper, we have proposed a class of novel attention strategies, known as Conjoint Attentions (CAs) to construct Graph conjoint attention networks (CAT's. Different from empirical graph atten- tions, CAs offer flexible incorporation of both layer-wise node features and structural interventions that can be learned outside of the GNN to compute appropriate weights for feature aggregation. Besides, the expressive power of CATs is theoretically validated to reach the upper bound of all message-passing GNNs. The proposed CAT's have been compared with a number of prevalent approaches in different learning tasks. The obtained notable results verify the CAT'' model ef- fectiveness. In future, we will further improve the effectiveness of CATs the following ways. First, besides node cluster embeddings and sxfresxpressssssssss more structural interventions will be explored to compute more compelling attention coefficients for node representation learning. Sccond, appropriate adversarial strategies to reduce model vulnerability to contaminated factors that are used for computing attention scores will be considered. Last but not the least, the proposed Conjoint Attentions will be extended to learn node representations in multi-view context and heterogeneous graph data.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their constructive comments and suggestions. This work is supported in part by the Data Science & Artificial Intelligence Research Center (DSAIR), Nanyang Technological University. and in part by Agency for Science, Technology and Research (A *TAAR).
References
[1] James Atwood and Don Towsley. Diffusion-convoluuie neural networks. In Advances in neural information processing systems, pages 1993-2001, 2016.
[2] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[3] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
10

---

[4] Julian Busch, Jiaxing Pi, and Thomas Seidl. Pushnet: Efficient and adaptive neural message passing. arXiv preprint arXiv:2003.02223: 2020.
[5] Jianpeng Cheng, Li Dong, and Mirella Lapata. Long short-term memory-networks for machine reading. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pages 551 551-561, 2016.
[6] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.057/16 2020.
[7] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pages 3844-3852, 2016.
[8] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances neural information processing systems, pages 2224- 2232, 2015.
[9] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.0098; 2020.
[10] Ehsan Elhamifar and Rene Vidal. Sparse subspace clustering: Algorithm, theory, and appli- cations. IEEE transactions on pattern analysis and machine intelligence, 35(11):2775-22 -7882, 2013.
[11] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and datu mining, pages 855-864, 2016.
[12] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, et al. Hyperbolic attention networks. In International Conference on Learning Representations, 2018.
[13] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[14] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structured data, arXiv preprint 1066:::0000055111 2015.
[15] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066 2020.
[16] Emily A Jones and Edward G Carr. Joint attention in children with autism: Theory and intervention. Focus on autism and other developmental disabilities, 19(1):13-26, 2004.
[17] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[18] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank.
[19] Johannes Klicpera, Stefan Weißenherger, and Stephan Günnnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, pages 13354-13366, 2019.
[20] Daniel Lowd and Christopher Meek. Adversarial learning. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 641-647, 2005.
[21] Qing Lu and Lise Getoor. Link-based classification. In Proceedings of the Twentieth In- ternational Conference on International Conference on Machine Learning, pages 496-503, 2003.

---

[22] Minh- Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention- based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1412-1421, 2015.
[23] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5115-5124, 2017.
[24] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pages 2014-2023, 2023, 2016.
[25] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[26] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459-467, 2018.
[27] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vee: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 385-394, 2017.
[28] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008
[29] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojehevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 11..v.88/..05868, 2018.
[30] Weiping Song, Zhiping Xiao, Yifan Wang, Laurent Charlin, Ming Zhang, and Jian Tang. Session-based social recommendation via dynamic graph attention networks. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 555-563, 2019.
[31] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077, 2015.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz. Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 1998-6008 2017.
[33] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[34] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large bargin-based constraints. arXiv preprint 11X1v:1910.11945,0000
[35] Lei Wang, Yuchun Huang, Yaolin Hou, Shenman Zhang, and Jie Shan. Graph attention convolution for point cloud semantic segmentation. In Proceedings of the IEEESCVF Conference on Computer Vision and Pattern Recognition, pages 10296-10305, 2019.
[36] Weisfeiler and A Leman. The reduction of a graph to canonical form and the algebgra which appears therein. NTI, Series, 2, 1968.
[37] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu,, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[38] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
12

---

[39] Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning. arXiv preprint arXiv:1304.5634 2013.
[40] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. International conference on machine learning, pages
2015.
[41] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:
2018.
[42] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462. PMLR, 2018.
[43] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[44] Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In International Conference Learning Representations, 2020.
[45] Shuo Zhang and Lei Xie. Improving attention mechanism in graph neural networks via cardinality preservation. In IJCA:: proceedings of the conference, volume 2020, page 1395. NIH Public Access, 2020.
13


Reviews:
[{"review_id": "ieWEE7aBe7", "reviewer": "Reviewer_zBg1", "summary": "The authors propose Graph ConJoint Attention Networks (CATs) as a mechanism for explicitly incorporating structural information in the GATs attention mechanism.\n\nCATs separately learn an \"enlightenment\" attention matrix which exploits structural correlations between the vertices (based on the adjacency matrix).\n\nSuch a matrix is then recombined with the attention matrix computed by vanilla GATs, yielding updated attentional coefficients which empirically improve on GATs on several benchmark datasets, and can be proven (with small modifications) to satisfy the equivalence with the 1-WL test, which also answers a somewhat-open question on GATs' expressive power.", "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": "Overall, I found the work's theoretical contribution to be impressive, and the comparisons to baseline approaches to be relevant.\n\nI believe that the work is worthy of acceptance, but I would like to see a few more experiments, comparisons and clarity improvements before giving a higher score.\n\nSpecifically, the proposed structural attention is one way of injecting structural information into the attentive mechanism, but is not the only one. Many prior works, that e.g. take the top/bottom-k eigenvectors of the Graph Laplacian, or a structural embedding vector such as DeepWalk/node2vec/struct2vec/LINE, could be meaningful baselines. This is especially given that recently a deep connection between such works and matrix factorisation has been uncovered (see NetMF; Qiu et al., 2017).\n\nCould the authors compute these additional features, and include a GAT baseline that takes them in concatenated alongside the usual node features? This will strengthen the claim about the impact of the proposed CAT mechanism.\n\nI found the paper at times very unclear and difficult to follow. The second sentence in the abstract for example:\n\n\"Different from previous graph attentions computing weights for feature aggregation solely bestowing layer-wise node features propagated inside GNN, CAs are capable of adaptively leveraging heterogeneous learnable factors either inside or outside of GNNs to compute attention scores.\"\n\nIt is very unclear what the authors want to say in this sentence, and in either case it would be better splitting it into multiple.\n\nLastly, I disagree with using the term \"enlightenment\" to refer to graph-structural features. They are very commonly used in many other established papers (e.g. see the ones I referred to above) and there is no need to overload a new term to illustrate the same (or very similar) concept.\n\nI invite the authors to carefully rewrite some parts of the paper in light of the comment above, to make it easier to follow.\n\n==== UPDATE Post-rebuttal: \nThe authors have carefully responded to my comments and included new experiments that further elucidate the gains of their method. With faith that they will rewrite their paper to be more clear, and avoid overloading existing terms, I will upgrade my score to a 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Pbt9jOOk4s", "reviewer": "Reviewer_vEEu", "summary": "This paper aims to establish a new type of attention mechanism for GNNs. Authors propose an attention mechanism which can utilize structural interactions between nodes instead of focusing only on given node features. Given the new attention authors use it create Conjoint Graph Attention Networks to solve node classification and node clustering tasks. \n\nAuthors first calculate an external ( w.r.t GNNs ) information matrix and propose two forms in this paper based on Matrix Factorization and Coefficient of Self-Expresiveness. The *Conjoint Attention* layer then calculates two types of attention, using external information matrix and using the node features ( any attention mechanism can be used here, authors use attention mechanism similar to GAT ). Two strategies are used to combine the different attentions calculated in previous step, Implicit and Explicit. Weighted aggregation is used to get the final node embeddings, with an addition of a correction factor. \n\nExperimentation is conducted of several publicly available datasets, and comparisons to several baselines are included which gives a good idea of the expressive power of the proposed attention mechanism. ", "questions": "", "limitations": "", "rating": 7, "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": "- Authors propose to use the structural graph properties in addition to node features, to calculate separate attention scores. The motivation behind this type of attention is well established. \n- Thorough experimental analysis is done to establish the advantage of using the proposed attention mechanism. \n- The writing of the paper is okay but can be improved by giving examples at several places. For instance, authors talk about \" heterogeneous learnable factors either inside or outside GNNs \" starting from Abstract of the paper but it is only introduced in the method section. Please provide simple examples in order to make the method more approachable. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Questions and Comments\n- In Section 3.2, please define the matrix V and how is it defined. \n- It is stated in the paper that external information matrix C can be calculated based on any interaction between nodes which is useful in node classification tasks which have some textual data available for each nodes. In such cases, I would assume that using conjoint attention principle to calculate an attention score between texts of two nodes will be useful in the final task. Would you consider including such an experiment in the paper? \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IS_FxCNP7F3", "reviewer": "Reviewer_dyaY", "summary": "This paper presents an extension of Graph Attention Networks (GAT) termed Conjoint Attention Networks (CAT). The attention mechanism presented in this paper combines the attention mechanism from GAT, computed from the node embeddings, with an extra attention mechanism that captures structural information too.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths\n+ The authors perform an experimental evaluation on a variety of graph datasets for two different tasks.\n+ The authors do a theoretical analysis of their proposed method.\n\nWeaknesses\n- The main weakness of the paper is that it is not clear what is the motivation for CATs, and why the different methods for computing $\\mathbf{C}_{ij}$ are chosen:\n\n  - First of all, the authors mention that their attention mechanism can leverage “factors either inside or outside of GNNs” (Abstract, line 5). It isn’t clear what that means. What are factors inside the GNN? I assume deep node embeddings? What are the factors outside the GNN?\n\n  - In the introduction (line 36), the authors mention that “previous graph attention mechanisms are incapable of learning effective attention scores when heterogeneous relevance is given”. What is “heterogeneous relevance”? It isn’t explained in the paper. Why are other attention mechanisms unable to learn effective attention scores? Why are CATs better in this aspect?\n\n  - Again, in the introduction (line 41) the authors say that CATs are flexible to compute attention scores not only relying on the layer node features, but also leveraging “information possibly outside of the neural networks”. What is that information?\n\n  - Section 3 should explain clearly what are CATs and their motivation. While the formulation of CATs is well explained, the choice of the conjoint attention scores $\\mathbf{C}_{ij}$ and its motivation is unclear. In section 3.1 the authors explain that conjoint attentions can capture “enlightenment outside of GNNs”. Again, it isn’t clear what that means. The authors use the word “enlightenment” to refer to the information that the proposed attention mechanism can use, but it isn’t clear what that means.\n\n  - In Equations (2) and (3) it seems that $C_{ij}$ is capturing structural information from the adjacency matrix of the graph, but that isn’t explained.\n\n  - In the experiments the authors evaluate the MF and SC variants of their method, introduced in Equations (2) and (3), but they don’t explain much about their motivation. What is the difference between them? They seem to get similar experimental results, why?\n\n\nAdditional Questions:\n* In Section 5.4 the authors say that the “external enlightenment C” is learnable, and that it can be simultaneously learned during the training of CATs. But why is it learnable? Does it have any learning parameters? Why can’t it be computed before training?\n* In Figure 3, it appears that the value of $\\lambda$ doesn’t have an effect, why is that the case? It isn’t explained. What should be the behaviour of $\\mathbf{C}_{ij}$ as $\\lambda$ increases (or decreases)?\n* What are the different attention factors compared in Figure 2? What is the difference between SC and I-SC?\n\nTo summarize, the method seems to perform well, and the authors do a good evaluation in different datasets, but it is not clear why this method should work better than GATs. The authors keep mentioning \"enlightenment\", a concept that is not explained. The clarity of the paper and the quality of the explanations should improve in order to be accepted.\n\n\n### Post Rebuttal:\nThe authors have answered my questions and have agreed to improve the clarity of the paper, which was my main concern. Because of that, I raise my score to a 7, assuming that the authors will improve the clarity of the paper in its final version.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper doesn’t seem to have any obvious societal impact. The authors address the limitations of their method in the Appendix.", "review_text": "", "extra_scores": {"ethical_concerns": "This paper does not present ethical issues.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "AQ4Zn8m-ah", "reviewer": "Reviewer_wBgV", "summary": "This paper proposes a new technique for augmenting Graph Attentions with information other than node feature embedding in GNNs. The Conjoint Attentions (CAs) proposed in this paper parametrize the similarity hints between nodes, such as adjacency matrix, in the form of matrix factorization, and modify the attention weight \\alpha calculated by ordinary graph attention.\nThis paper shows that CAs (with additional learnable parameters to the self-link terms) have theoretically higher expressive power than existing GNNs such as GAT.\nExperimental results show that the proposed CAs have higher generalization performance than several existing GNNs on five representative datasets.\n", "questions": "", "limitations": "", "rating": 7, "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": "## Originality: \nTraditional graph Attentions are solely controlled by the similarity of node feature embedding. As far as I know, this paper is the first attempt to identify this problem: a unique and valuable problem proposal. \nAlso, the idea of adding a new control term to the existing attention in the form of Eqs.(7-9) is new, at least in my knowledge of GNN research. I find it interesting \n\nHowever, it is a pity that only the adjacency matrix is studied as enlightenment. ``A'' could be said to be information inside the graph data, depending on how a reader looks at it. I think the paper would be strengthened more if there were examples of information that is clearly outside the graph data.\n\n## Quality: \nI could not find any technically obvious mistakes in this paper. However, I need to confess I cannot follow the proofs of theorems. \n\nMany related studies often include Graph Isomorphism Network (GIN[33]) as one of the most expressive GNNs for comparison. In my experience, GIN does not necessarily have the numerically highest generalization performance, but additional comparisons are definitely desirable to support the high expressive power shown in Section 4. \nNotice: I believe that the value of this paper would not change significantly even if CATs do not perform better than GIN. \n\n## Clarity: \nI could not understand the main ideas of this paper on the first reading. \nOne reason is that (i)  concrete examples of ``other possible enlightenment'' (first appear in introduction L32) and (ii) explanation of how they help attention are not explained even roughly until section 3 (L115, 147). \nIdeally, I would like the introduction to be augmented so that the readers can have some intuitions about the outline of the proposed method at the introduction stage (I don't mean that it should be shown in equations explicitly). It is difficult for me to understand the intention of the equations at the first sight unless some intuitions are provided beforehand. \n\nIn Figure 3, I'm happy to see that the result is robust to hyperparameter \\lambda choices. \nBut I think this figure can be moved to an appendix. As a reader, I can read as much information in the text of L308-312 alone as in figure 3. I would like to see additional experiments and/or discussion to limitation, future works in the main manuscript instead. \n\n## Significance: \nThe experimental results show high test generalization performance of the proposed CAs, as expected from the theoretical conclusions, and I think these results support the claims of the paper well. \nAs mentioned in the Originality section, I think the paper would be more significant if there are additional examples that incorporate information from outside the graph. However, I think it is an important finding that just using the adjacency matrix to control attention in this way can improve GNN performance.\n\nSection 4 proves that the expressive power is stronger than GAT, etc... This increases the significance of the paper.\n\nThe formulation of the proposed CA is simple enough to be fully understood when looking at Eqs. (5-9), which I think adds to the value of this paper.\n\n## after feedbacks\nI found the author feedback informative, yielding better understanding. I keep the original positive score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I felt that there was not much discussion about the limitation of the proposed method (though some are discussed in the appendix). Personally, I'm interested in the following questions: \n- Is there any other typical and useful outside enlightenment other than the adjacency matrix?\n- If there are multiple enlightenments, how should we weigh them? Which one should be selected?\n- If the enlightenment is adversarial (e.g., false or noisy), how can we detect or mitigate the performance degradation?\n", "review_text": "", "extra_scores": {"ethical_concerns": "No specific concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is general consensus among the reviewers that the paper should be accepted.

The authors made extensive effort to answer reviewer comments and provide additional empirical results.

We expect the authors to implements all clarity improvements, as requested by the reviewers.

Figure 1 looks pixelized, it should be converted to vector graphics.
Decision: Accept (Poster)