Graph Joint Attention Networks
Authors: Tiantian He
Lu Bai
Yew-Soon Ong
Venue:  (2021)
Keywords: Graph attention networks
Joint attention mechanism
Graph transductive learning

Abstract: Graph attention networks (GATs) have been recognized as powerful tools for learning in graph structured data. However, how to enable the attention mechanisms in GATs to smoothly consider both structural and feature information is still very challenging. In this paper, we propose Graph Joint Attention Networks (JATs) to address the aforementioned challenge. Different from previous attention-based graph neural networks (GNNs), JATs adopt novel joint attention mechanisms which can automatically determine the relative significance between node features and structural coefficients learned from graph subspace, when computing the attention scores. Therefore, representations concerning more structural properties can be inferred by JATs.
Besides, we theoretically analyze the expressive power of JATs and further propose an improved strategy for the joint attention mechanisms that enables JATs to reach the upper bound of expressive power which every message-passing GNN can ultimately achieve, i.e., 1-WL test. JATs can thereby be seen as most powerful message-passing GNNs. The proposed neural architecture has been extensively tested on widely used benchmarking datasets, including Cora, Cite, and Pubmed and has been compared with state-of-the-art GNNs for node classification tasks. Experimental results show that JATs achieve state-of-the-art performance on all the testing datasets.

Under review as a conference paper at ICLR 2021
GRAPH JOINT ATTENTION NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph attention networks (GATs) have been recognized as powerful tools for learning in graph structured data. However, how to enable the attention mech- anisms GATs smoothly consider both structural and feature information is still very challenging. In this paper, we propose Graph Joint Attention Net- works (JAT') to address the aforementioned challenge. Different from previous attention-ban based graph neural networks (GNNs), JAT's adopt novel joint attention mechanisms which can automatically determine the relative significance between node features and structural coefficients learned from graph subspace, when com- puting the attention scores. Therefore, representations concerning more structural properties can be inferred by JAT'. Besides, we thcoretically analyze the expres- sive power of JAT's and further propose an improved strategy for the joint attention mechanisms that enables JAT's reach the upper bound of expressive power which every gressage-passingg GNN can ultimately achieve, i.e., 1-WL. test. JATs can thereby be seen as most powerful message-passing GNNs. The proposed neural architecture has been extensively tested on widely used benchmarking datasets, including Cora, Cite, Pubmed, and OGBN-Arxiv, and has been compared with state-of-the thetheert art GNNs for node classification tasks. Experimental results show that JATs achieve ttateof-thhe-r performance on all the testing datasets.
INTRODUCTION
Many real-world data can be modeled as a graph, where set of nodes (vertices), edges, and bag-of- words features respectively represent data instances, instance-instance interrelationships, and con- tents characterizing the nodes. For example, scientific articles in research domain can be modeled as graph, where nodes, edges, and node features respectively represent published articles, citations, and index information of the articles. Besides, social network users and interacted biological units can also be similarly represented as graphs possessing different structural and descriptive informa- tion. As graph data are widely available and they are related to various analytical tasks, learning in graphs has been a hot-spot in machine learning community.
There have been number of approaches proposed to effectively learn in graph structured data. Amongst them, graph convolutional networks (GCNs) have shown to be powerful in learning low- dimensional representations for various subsequent analytical tasks. Different from those empirical convolutional neural networks (CNNs) which have achieved a great success in learning in image, vision, and natural language data (Krizhevsky al. 2012; Xu et al. 2014). and whose convolu- tion operators are always defined to process grid-like data structure, GCNs attempt to formulate convolution operators aggregating the node features according to the observed graph structure, and learn the information propagation through different neural architectures. Meaningful representations which capture discriminative node features as well as intricate graph structure can thereby be learned by GCNs. There have been several sophisticated GCNs proposed in the recent. According to the ways through which GCNs make use of graph topology to define convolution operators for feature aggregation, GCNs can generally be categorized as spectral, and spatial ones (Wu al. 2020).
Spectral GCNs define the convolutional layer for aggregating neighbor features based on the spectral representation of the graph. For example, Spectral CNN (Bruna al. 2013) constructs the convo- lution layer based on the deseppeccooooiiionn of graph Laplacian in the Fourier domain. However, such layer is computationally demanding. Aiming to reduce such computational burden, several approaches adopting the convolution operators which are based on simplified/aprxximmae spectral graph theory are proposed. First, parameterized filters with smooth coefficients are introduced for

---

Under review as a conference paper at ICLR 2021
Spectral CNN to allow it to consider spatially localized nodes in the graph (Henaff et al. 2015). Chebyshev expansion is then introduced in (Defterrard et al. 2016) to approximate graph Laplacian rather than directly perform seeen-cccomoottionn of it. Finally, the graph convolution filter is further
simplified by only considering connected neighbors of each node (Kipf & Welling 2017) s0 as to further make spectral GCNs computationally efficient.
In contrast, spatial GCNs define the convolution operators for feature aggregation directly making use of local structural properties of the central node. The key of spatial GCNs is consequently how to design an appropriate function for aggregating the effect brought by the features of candidate neighbors selected according to a proper sampling strategy. To achieve this, sometimes requires to learn weight matrix according to node degree (Duvenaud et al.] (2015), utilize the power of transition matrix to preserve the neighbor importance (Atwood Towsley (0166] [Busch et a 2020 Klicpera et al., 2019), extract the normalized neighbors (Niepert et al. 2016), or sample a fixed number of neighbors (Hamilton et al.) 2017 Zhang et al., 2020).
As representative spatial GCN, Graph attention network (GAT) Veličković et al. 2018 Zhang al. 2020) has shown a promising performance various graph learning tasks. What makes GATs effective in learning graph representations is they adopt the attention mechanism, which has been successfully used in machine reading and translation (Luong et al., 2015 Cheng et al.. 2016). and video processing (Xu et al. 2013). to compute the node-fcature-base scores) between a central node and its one-hop neighbors (including the central node itself). Then, GATs utilize the attention scores obtain weighted aggregation of node features which are prop- agated to the next layer. As a result, those neighbors possessing similar features may impact more on the center node, and meaningful representations can be inferred by GATs.
attention weights (attention
Although GAT's have been experimentally verified as powerful tools for various graph learning tasks, they still confront several challenges. First, for attention- based GNNs, appropriate attention mech- anisms which can automatically identify the relative significance between the graph structure and node features are not many. As a result, most current attention mechanisms for GATs cannot ef- fectively capture the joint effect brought by the underlying graph structure and node features for seamlessly impacting the cessaaee-assingg in the neural architecture. Second, whether the expres- sive power of GNNs adopting the attention mechanisms which can effectively acquire the aforemen- tioned joint effect may reach the upper bound of message-ppssingg GNNs has not been theoretically investigated. To address the mentioned challenges, in this paper, we propose novel attention based GNNs, dubbed Graph Joint Attention Networks (JATs). Different from previous works, the atten- tion mechanisms adopted by JAT's able automatically capture the relative significance between structural coefficient learned from graph topology, and node features, so that higher attention scores may be learned by those neighbors which topologically and contextually correlated. JATs consequently able to smoothly adjust attention scores according to the contemporary structure and node features, and truly capture the joint attention on structural and contextual information prop- agated in the neural network. Besides, we theoretically analyze the expressive power of JAT's and further propose an improved strategy which enables JATs distinguish all distinct graph structures as I 1-dimensional Weisfeiler-Lehman test (1-WL test) does. This means JAT's can reach the upper bound w.r.t. expressive power which all message-passinng GNNs can ultimately achieve. JAT's have been extensively tested on four widely used datasets, i.e., Cora, Citeseer, Pubmed, and OGBN- Arxiv, and have been compared with a number of strong baselines. The experimental results show that JATs achieve the state-of-the-ar ofetth-rttttttto performance.
The rest of the paper is organized as follows. In Section we elaborate the proposed JATs, and compare JAT's with other GNNs. In Section B we prove the limitation w.r.t. expressive power of the joint attention mechanisms presented in Section 2 A strategy is then proposed to improve JATs to reach the upper bound of expressive power which all message-passing GNNs can most achieve. The comprehensive experiments which are used to validate the effectiveness of JAT's are presented in Section[4] Finally, we summarize the contributions of the paper and propose future works potentially improving JATs.
JOINT ATTENTION SIEETIOO-BBSEDD GRAPH NEURAL NETWORKS
In this section, we elaborate the proposed JATs. Mathematical preliminaries and notations used in the paper are firstly illustrated. How JATs learn the structural coefficients which are used in the
2

---

Under review as a conference paper at ICLR 2021
joint attention mechanisms is then introduced. Following that, the joint attention layer, which is the cornerstone of JATs is elaborated. At last, we compare the proposed JATs with their counterparts.
2.1 NOTATIONS AND PRELIMINARIES
Throughout this paper, we assume a graph G = {V, E} containing N nodes, |E] edges, where V and respectively represent the node and edge set. We use A E {0, 1, and X E RNxD to represent graph adjacency matrix and node feature matrix, respectively. Mr denotes the union of node and its one-hop neighbors. W and (h:)a=1,.... denote the weight matrix and features of node at /th layer of JATs, respectively, and h" is set to be the input feature, i.c., X. For the nodes in NV, their possible feature vectors form a multiset M, (4), where S; {s (..,...3,) is the (4),,
ground set of M; which contains the distinct elements existing in M,, and μ4: : S - N is the multiplicity function indicating the frequency of occurrence of each distinct in Mt.
2.2 LEARNING STRUCTURAL COEFFICIENTS FROM GRAPH SUBSPACE
well known that topology is the corner stone of the graph. How to utilize such structural in- formation compute the attention scores naturally has profound impact on the performance of attention-based GNNs. Empirical attention based GNNs, e.g., GAT, compute the attention scores be- tween connected neighbors only using node features, but overlook the structural correlation between pairwise nodes. To allow attention-based GNNs to capture the higher-order structures in the graph, we propose JAT's to learn the topological coefficients from the graph subspace. Inspired by subspace clustering (Elhamifar & Vidal 2013), we may formulate the learning of structural coefficients as follows. Given N nodes in the graph drawn from multiple linear subspaces {S+ (S=). K. one can represent a node in subpace as linear combination of other nodes. If each row in A is treated as the structural information of each node, one can simply represent it using other nodes (other rows in A) as one equation, i.e., A,, A, A, where C denotes the structural coefficient matrix A is used. It has been shown in previous works (Ji et al. 2014) that under the assumption the subsapces independent, by minimizing certain norm of C, C may have block diagonal structure (after finite permutations). In other words, Cú * O if and only if two nodes, 2 and v are in the same subspace. So, can utilize C to learn the structural correlations between neighbors in the graph. And the above learning task can be formulated as the following optimization problem:
minimize ||C||p subject A CA, C.+ O.
where ||.1|p stands for a certain matrix norm, and the zero constraint on the diagonal of C may prevent trivial solutions when ||-IIp is the norm considering sparsity. To make the data corruption explainable, the equality constraint in Eq. I is often relaxed as a regularization term and the leamning of structural coefficients can be reformulated as follows:
minimize ||C||p + A|| - I/ subject to C 0.
(2)
By rewriting Eq. 2 we may reveal why subspace learning is effective in capturing the structural correlations between pairwise nodes. Mathematically, Eq. (2) is equivalent to the following node- wise minimization problem:
minimize
El
+ A, - CA subject to C;; = 0.
(3)
As CA2;; equal to E3 CijA,, and C₁ 0. one may easily find that minimizing Eq. (3) equivalent to search for the optimal linear combination of other nodes that can be used to reconstruct the ith node in the graph. As result, C; is high when A i.e., the global structure of jihh node (rather than the local bias (Gong et al., 2018), is similar to A. By minimizing Eq. (2), one may identify those nodes which are in the same graph subspace, and the structural correlations between neighboring nodes can therefore be inferred directly. As the above learning problem can be effectively solved via gradient descent, JATs can optimize Eq. (2) together with the training of the neural architecture. Also, we use / norm for C to force JATs to learn sparse structural coefficients.
2.3 JOINT ATTENTION LAYER
Having made the structural coefficients available, are now presenting joint attention layer, which is the core module for building JATs and will be used in our experiments. Different from the at- tention layers utilized by other GNNs, the joint attention layer in the proposed framework adopts
3

---

Under review as a conference paper at ICLR 2021
0000
00oc
0000
Figure 1: Graphical illustration of the joint attention mechanisms used in each layer of JAT'. Left: Joint attention mechanism using Implicit direction strategy. Right: Joint attention mechanism using Explicit direction strategy. Both two mechanisms consider structural coefficients learned from graph adjacency.
novel attention mechanisms, which may automatically identify the relative significance between in- put features and structural information. Appropriate attention scores between central node and its neighbors can be obtained and meaningful representations can be inferred by JATs.
Given a set of node features (h/ each hy E RP', the joint attention layer JATs is to map them into D dimensional space {h: [+1 Ji=1....., according to the correlations of input features and graph topology. JAT first attempts to compute the contextual correlation between two connected nodes, say v; and 0;. To do so, we directly adopt the naature-based attention mechanism utilized by previous GATs (Veličković et al. 2018):
exp(LeakyReLU((a' (W'h)) || fyj ΣKEN, exp(LeakyReLLU()) (W'h)) || Wh)))))
W'
where ā E |2 function, and W Ft+1, x Fl variable matrix for feature mapping. Based on Eq. (4). JAT may capture the feature correlations between connected nodes (first-order neighbors) by computing the similarities w.r.t. features mapped to next layer.
is vector of parameters of the feedforward layer, || stands for the concatenation
However, determining the attention scores solely based node features leads GNN overlook the structural information hidden in the graph. To overcome this issue, we propose JAT to learn the structural coefficients mentioned Section 2.2 and utilize the novel joint attention mechanisms to appropriately compute the attention scores. Given learnable structural coefficient, Cit between two nodes, JAT obtains the structural correlation as follows:
exp (Ct))
Sij ΣLENS exp (Cas)
(5)
Given fiy and 8ij. JAT has two strategies (attention mechanisms) to compute the final attention scores. The first mechanism is dubbed Implicit direction. aims at computing the attention scores whose relative significance between structural and feature correlations can be automatically ac- quired, To do so, for each layer of the neural network, JAT introduces two learnable parameters, 9 and ga to determine the relative significance between structure and feature correlations and it can be obtained as follows:
exp (gr)
exp (ga)
exp (g=) + exp (gr) exp (g.) + exp (gy)
where r, or ry represents the normalized significance related to structure or node features. Given them, JAT is able to compute the attention score based on Implicit direction strategy:
TT fig + Sy
aij ExeN (rs- Sah + Hr 88k]
Tf fuj + Sij.
Given the attention mechanism shown in Eq. (7). as attempts to capture the weighted mean atten- tion in terms of structural and feature correlations between neighbors. Compared with the attention
4

---

Under review as a conference paper at ICLR 2021
mechanism solely based features of one-hop neighbors, ag computed by Eq. may be softly adjusted according to the implicit impact brought by the structural coefficients. Moreover, the rel- also be automatically inferred by JAT it is involved into the back propa- gation process. More smooth and appropriate attention scores can thereby be computed by JAT for learning meaningful representations.
ative significance
To enhance the structural impact, JAT has another strategy, named as Explicit direction, to compute attention scores between neighbors. Given fúj and 8ij, the attention scores obtained via Explicit direction strategy is defined as follows:
fij 8tj
aij EREN, fa Sik
Compared with Eq. 77. the structural coefficient explicitly influences the magnitude of Jij. so that those node pairs which are structurally irrelevant are impossible to assign with high attention weights. Utilizing Explicit direction strategy, JAT becomes more structure dependent when perform- ing message passing in its neural architecture.
Having obtained the attention scores, JAT is now able to compute linear combination of features corresponding to each node and its neighbors as the layer-wise output, which will be either propa- gated the higher layer, or be used the final representations for subsequent learning tasks. The mentioned output features can be computed as follows:
h 1++
Σ JEN.
aiyy Wh'
In Fig. D the joint attention mechanisms proposed in this paper are graphically illustrated. And we may use a particular number of joint attention layers utilizing the proposed attention mechanisms to construct JATs. In practice, we also adopt the multi-head attention strategy (Vaswani et al. (017)) to stabilize the learning process. JAT's either concatenate the node features from multiple hidden layers as the input for next layer, compute the average of node features obtained by multiple units of output layers as the final node representations. The details on how to implement multi-head attention in graph neural networks can be checked in (Veličković et al. 2018
2.4 COMPARISON RELATED GRAPH NEURAL NETWORKS
Based on the structure of the introduced joint attention layer, it is found that Graph Joint Attention Networks are quite different from previous related neural architectures and have several advantages.
When compared with spectral based GNNs, the proposed JAT' provide a dynamic way to update layer-wise representations. In each layer, the updating function for node representation prevalent spectral GNNs, can generally be formulated as h = o(jENN Ai hy W), where represents a static matrix/tensor, which can be constructed according to graph normalization (Kipf & Welling 2017]. graph diffusion (Klicpera al. 2019 Busch et al., 2020), so as to preserve particular spectral properties of graph structure. As it shows, the message passing in spectral GNNs is defined according to the static matrix/tensor preserving structural properties. In contrast, JATs compute the attention score (O:j) for each pair of neighbors based on structural coefficient and node features, which naturally leads each layer the neural network to pay more attention those node pairs sharing similar structures and features. Higher-order representations concerning such analogous neighbors in the graph can therefore be learned by JATs.
When compared with spatial GNNs, especially those attention based ones (Veličković et al., 2018 Zhang et al. 2020). JATs adopt adaptive attention mechanisms which smoothly determine the rela- live significance between graph structure and node features, to compute more appropriate attention scores for representation learning. Compared with GAT's (Veličković et al., 2018), JATs are able to compute attention scores for first order neighbors according to both structural coefficients and node features, so that the attention-based message passing considers more structural information. JATs are also different from those spatial GNNs which update node representations via sampling fixed size of neighbors. For example, to reduce the computational demand, GraphSAGE (Hamilton et al. 2017) performs the task of graph representation learning via max pooling. Another attention based framework, ADSF (Zhang et al., (020)) also takes into consideration structural information when computing attention scores. However, ADSF cannot infer the relative significance between
5

---

Under review as a conference paper at ICLR 2021
the utilized topological information and node features, and ADSF considers the best k neighbors for computing attention scores. Unlike JATs, such spatial GNNs sampling neighbors for representation updating cannot fully utilize the structural information provided by proximal nodes in the graph. Due to the flexibility of the proposed attention mechanisms, JAT's can be readily combined with any paradigm which can learn the topological correlations, just like the structural coefficients used in this paper. This property enhances the applicability of the proposed JATs.
3 MORE EXPRESSIVELY POWERFUL JATS
Study on the expressive power of various GNNs has drawn much attention in the recent. It concerns whether given GNN can distinguish different structures where vertices possessing various vector- ized features. It has been found that what the neighborhood aggregation functions, or readout opera- tors of all message-passing GNNs, including GCNs, GATs, and other related aim what I-dimensional Weisfeiler-Lehmer test (1-WL test), which is injective and iteratively operated in Weisfeiler-Lehman algorithm (Weisfeiler & Leman 1968, Xu et al. 2018 Zhang & Xie 2020), does. In other words, both aggregation/readouu functions in prassage-passinng GNNs and I-WL test attempt to distinguish structures which are different in some ways. As result, all message-paseen GNNs are most powerful as 1-WL test (Xu et al. 2018). The theoretical validation of the expres- sive power of given GNN thereby lies in whether those adopted aggreation/readot functions are homogeneous to 1-WL test.
analogous to
Having the effective framework evaluating the expressive power of given message-passing GNN, one may naturally be interested in whether the proposed JATs can distinguish all different graph structures as 1-WL test does. As we mainly consider node classification tasks, in this section, we investigate the expressive power of the neighborhood aggregation function concerning the joint at- tention mechanisms in Eqs. (7) and (8). We firstly show that the neighborhood aggregation function utilized by JATs still fails to discriminate some graph structures possessing certain topological prop- erties. Then, we propose simple but effective strategy for the joint attention mechanisms to enable JATs to successfully distinguish all those graph structures that previously cannot be discriminated.
For the neighborhood aggregation utilizing the attention mechanism shown in Eq. 7., we have the following theorem pointing out the conditions under which the aggregation function fails to distinguish different structures.
Theorem Assume the feature space X countable and the aggregation function concerns the attention mechanism in Eq. 7 is represented as x)c =x (x), where is the feature of center node, X E & is a multiset containing the feature vectors from nodes in No. g(-) is function for mapping input feature X, and asn is the attention score between ((c) and f(x). For all and the
joint attention mechanism in Eq. (7). (((c,X)) hlcc, X2) and only if ci 02, Xi =1, p X2 = (2), and) Σ Seiy -E Jeau a/ Sezy - - Secub. for q = It and x E S. In other words, h will map different multiset into the same embedding iff the multisets have same central node feature, same underlying set, and the difference in feature-bast attention scores is proportional (-e) the opposite of that attention weights corresponding to structural coefficients.
We leave the proof of all the theorems and corollaries in the appendix. For the aggregation function utilizing the attention mechanism 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 and the joint atlention mechanism in Eq. (8), h(c1,X1) = h(c2, X2) if and only if c1 = C2. X, = ( u1), }. X₂ = (S. (2), and q. Σx= of Ce(z) ( E Øl (e for q 0 x E S, where o6-) is an function for mapping values to RR+ In other words, h will map different multiset into the same embedding iff the multisets have same central node feature, same node features whose corresponding mapped structural coefficients are proportional.
Theorems I and indicate that the joint attention mechanisms may still fail to distinguish some graph structures, although the aggregation functions adopting the joint attention mechanisms may be more expressively powerful than empirical GATs. As node features and graph structure

---

Under review as a conference paper at ICLR 2021
heterogeneous, intuitively, sub-structures satisfying the mentioned conditions should be infrequent. This may well explain why those attention- based GNNs concerning including structural factors into the computation of attention scores may experimentally perform better than GATs. However, when distinct multisets with corresponding structural properties meet the conditions mentioned in Theorems [ and 2] the joint attention mechanisms in Eqs. 7 and (8) cannot correctly distinguish such multisets. Thus, JATs fail to reach the upper bound of expressive power of all message-passing GNNs, i... 1-WL test.
However, we are able to readily improve the expressive power of JAT's to meet the condition of 1- WL test by slightly modifying the joint attention mechanisms. The modified attention mechanisms are defined as follows:
aij ai t
JEN,j+ +i j j=i,e 0,
Oij 1
(10)
aayte
DVT
where Oiy is the attention weight obtained by either Eq. or 8 Then, the newly obtained attention scores can be used to aggregate the node features passed to the higher layers. Next, we prove that such improved attention mechanisms reach the upper bound of message-passing GNNs via showing they can distinguish those structures possessing the properties mentioned in Theorems T [
Corollary Let T be the attention- based aggregator shown in Eq. p that considers the attention mechanism in Eq. 77) or (8) and operates on a multiset H E H. where H is a node feature space mapped from the countable input feature space X. A exists so that utilizing 0zş in Eq. (TO). 'T can distinguish all different multisets in aggregation that it previously cannot discriminate.
Based on Eq. 10). one may use original JATs to perform different classification tasks in graph data by setting message-passing GNNs when is set as positive value. Theoretically, the expressive power of JAT' is stronger than state-of-the-ard iitention-baser GNNs, e.g. GAT's (Veličković et al. 2018). and ADSF (Zhang al. 2020). It should be noted that, all the theoretical validations presented in this paper assume the input feature space is countable. The general framework for validating GNNs' expressive power in the uncountable feature space can be checked in (Corso et al. 2020
O. The expressive power of JATs can immediately reach the upper bound of
EXPERIMENTS AND ANALYSIS
In this section, we evaluate the proposed Graph Joint Attention Networks (JAT') against a variety of prevalent baselines, on widely used network datasets.
4.1 EXPERIMENTAL SET-UP
To validate the effectiveness of JATs, we compare them with number of state-of-the baselines, including Gaussian fields and harmonic functions (GF) (Zhu et al.] (003)), Manifold regularization (Mani-reg) (Belkin et al. 2006), Deepwalk (Perozzi al. 2014), Semi-supervised graph embedding (Planetoid) (Yang et al. 2016), Node2Vec (Grover & Leskovec (016),, Graph convolutional net-
works (GCN) Kipp & Welling 2017). GCN with Chebyshev filters (Chebyshev) (Defferrard al.] 2016), GrephSAGE (Hamilton el al. 2017). mixture model CNN (MoNet) (Monti et al. 2017)). Graph attention networks (GAT) (Veličković al., (018), Bayesian GCN (BGCN) (Hasanzadeh et al. 2020), and Adaptive structural fingerprints (ADSF) (Zhang et al., 2020). Based on the exper- imental results previously reported, these baselines may represent the most advanced techniques for
learning in graph structured data.
Four widely-used document networks, which are Cora, Citeseer, Pubmed (Lu & Getoor 2003 Sen
et al, 2008), and OGBN-Arxiv (Hu et al.) 2020), are used in our experiments. Cora, Citeseer, and Pubmed are three classical network datasets for validating the effectiveness of GNNs. However, is recently found that these three datasets sometimes may not effectively validate the predictive power of different graph learning approaches, due to the relatively small data size and data leakage (Shchur et al., 2018 Hu et al. 2020). Thus, more massive datasets having better data quality have been proposed to evaluate the performance of different approaches (Hu et al.) 2020 Dwivedi et al. 20200). To effectively test JATs, additionally use OGBN-Arxiv, which is available in the Open graph
7

---

Under review as a conference paper at ICLR 2021
Table Average Accuracy on classical document networks
Approaches
Cora
Citeseer
Pubmed
GF (Zhu et al.
2003
68.0%
45.3%
63.0%
Man--eeg (Bel et al.
2006
59.5%
60.1%
70.7%
Deepwalk Peroozzi ct al.
2014)
67.2%
43.2%
65.3%
Planetoid Yang al. 20T6)
75.7%
64.7%
77.2%
Chebyshev (Detterrard et al.
2016
81.2%
69.8%
74.4%
GCN (Kipf & Welling 2017
81.5%
70.3%
79.0%
MoNet (Monti et al.] (217)
81.7%
78.8%
GAT (Velćčković al. (2018)
83.0%
72.5%
79.0%
BGCN Hasanzadeh ct al. (2020)
82.2%
70.0%
ADSF Zhang et al. 2020
84.7%
73.8%
79.4%
JAT-E
85.5
73.8%10.4%
82.0
JAT-I
85.8 %
74.3%0.4%
82.8100.4%
Table 2: Average Accuracy OGBN-Arxiv
Accuracy (%)
Approaches
Train
Validation
Test
MLP
63.6%
57.7%
55.5%
Node2Vec (Grover & Leskovec 2016)
76.4%
71.3%
70.1%
GCN (Kipf & Welling 2017
78.9%
73.0%
71.7%
GraphSAGE (Hamilton et al. 2017)
82.3%
72.8%
71.5%
JAT-B
81.3%
73.8 %
72.6:1.0.06%
JAT-I
81.2+001
73.4--0.08%%
72.9-10.22%
benchmark database, as one of the testing datasets. The effectiveness of all methods validated via allowing them to perform semi-supervised node classification (transductive learning) in all the benchmarking sets and the classified nodes are evaluated using Accuracy (M icro-Fi). To compare JATs impartially with other baselines, related works Yang et al., 2016 Kipf & Welling 2017 Veličković et al. [018 Hu et al., 2020). We leave the details of testing datasets and experimental scenarios in appendix due to space limitation.
closely follow the experimental paradigms used in the
4.2 RESULTS ON NODE CLASSIFICATION
We obtain the average classification accuracy over 10 runs of JAT's and compare it with other state- of-the-art approaches. The corresponding results are summarized Table I and 2 As the tables show, JATs utilizing two different joint attention mechanisms outperform all the basclines on all the four testing datasets. Specifically, the average Accuracy on node classification obtained by JAT-I (JAT using Implicit direction strategy) achieves 85.8%, 74.3%, 82.8% and 72.9% on Cora, Citeseer, Pubmed, and OGBN-Arxiv, respectively. The presented experimental results demonstrate that the proposed method is one of the most effective GNNs for learning in graph structured data.
4.3 ABLATION STUDY
Besides testing the performance of transductive learning in network data, we further investi- gate how different settings of JAT' may impact their performance. Specifically, we first in- vestigate how JAT' perform when different values of are used. The sensitivity test on = [10- 10 10 10 1001 1,1.5 10] is plotted in Fig. 2 (a) and (b). As the figures depict, both two versions of JATs perform robustly when < 1 and the improved strategy shown Eq. (10) may datasets, e.g., Pubmed. Thus, recommend set 1 for both two versions of JATs. Such setting may ensure JATs leverage the joint attention mechanisms as well as preserve the expressive power, when classifying nodes in graph structured data.
boost the performance of JATs in
Then, to further investigate whether the strategy of automatically determining the relative signifi- cance between feature and structural attention (Eqs. (6) and (7)) may truly improve the performance
8

---

Under review as a conference paper at ICLR 2021
Table 3: Performance comparison on JATs using different structural information. C, or SSL means JAT uses Cosine or Jaccard similarity to compute the structural correlations for attention score computation, or only uses structural coefficents to compute attention scores.
Different versions of JATs
Cora
Citeseer
Pubmed
OGBN-Arxiv
JAT-EC
85.3=0.1%
73.41:0.3%
80.0=1.19%
72.4:00.2%
JAT-IC
84.7=t03%%
03.3%+0.3%
79.7=0.3%
72.5+
JAT-EJ
85.2++.1%%
73.2+:0.4%
79.8=0.2%
72.6+:0.2%
JAT-IJ
85.1=:02%%
73.8:10.1%
79.410.1%
72.41:011%
JAT-SSL
85.8 +0.4%
73.1%%0.7%
81.0-10.6%
72.4:10.07%
JAT-E
85.5 0.4%
1..4%
82.0-10.3%
72.6 0.06
JAT-I
85.8 0.5%
7.44%
82,8 + 0.4%
72.9+0.2%
on transductive learning, compare JAT-I with GAT, ADSF, and JAT utilizing the attention strategy shown in Eq. (7) but setting ry T, 0.5 (JAT-I w/o ad). As Fig. (c) shows, JAT-I can out- perform all the baselines on the used testing datasets, including Cora, Citesser, and Pubmed. When compared with JAT-I w/o ad, JAT-I can significantly improve the performance on semi-supervised node classification on all the used datasets, at 95% confidence level. The strategy of automatic de- termination adopted by JAT's is therefore effective in learning node representation for the subsequent predictive tasks.
Finally, we further test the effectiveness of the proposed joint attention mechanisms by replacing the structural coefficients (C) with other effective strategies. Specifically, we use Cosine and Jaccard similarity measures compute the structural correlations for connected node pairs and then let JAT utilize them to compute attentions scores for the network training. Besides, we also allow one version of the JATs (JAT-SSL) only use the structural coefficients learned via minimizing Eq. (2) to compute the attention scores in the training stage. The corresponding results are summarized in Table As the table shows, JAT still performs robustly when using simple measures, e.g.,
Cosine and Jaccard similarity to obtain node-node structural correlations, although its performance not better than the original versions of JAT. Given the results shown in Table it is found that the proposed joint attention mechanisms are effective in learning node representations. The JAT framework can therefore be readily combined with many effective approaches which can infer node- node structural correlations, such as network embedding (Grover & Leskovec) 2016 Armandpour
al. 2019 and deep structural learning (Monti et al. 2017) for effective representation learning.
Cora: Cite Pubmed
IIGAT MADGF JATT without JATT
Accurncy (8)
Accuracy R5
Accuracy
80
70
10
10
16th
10
Cora
Cite
Pubmed
(a) JAT-I
(b) JAT-E
(c) JAT-I with/without ad
Figure Sensitivity test on and automatic determination of S/F significance
CONCLUSION
In this paper, we propose novel attention-based GNNs, dubbed Graph Joint Attention Networks (JATs). Different from previous related approaches, JATs adopt novel joint attention mechanisms that can smoothly infer the relative significance between graph structure and node features, so that structural properties and node features are appropriately preserved in node representations, Besides, the expressive power of JATs is theoretically analyzed and the improved strategy to ensure JATs to be most powerful masssae--assingg GNNs is also proposed. In future, will further improve the effectiveness of JATs by considering different structural properties hidden in the network data and explore JATs' applicability by using them in multi-view and heterogeneous network data.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mohammadreza Armandpour, Patrick Ding, Jianhua Huang, and Xia Hu. Robust negative sam- pling for network embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3191-3198 2019.
James Atwood and Don Towsley. Diffusion-convoluttinaa neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-24532 2006.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1rXiv:1312.6200 2013.
Julian Busch, Jiaxing Pi, and Thomas Seidl. Pushnet: Efficient and adaptive neural message passing. arXiv preprini arXiv:2003.022 022222 2020.
Yaoming Cai, Zijia Zhang. Zhihua Cai, Xiaobo Liu, Xinwei Jiang, and Qin Yan. Graph convo- lutional subspace clustering: A robust subspace clustering framework for hyperspectral image. arXiv preprint arXiv:2004. 10476, 2020.
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, pp. 551-561, 2016.
Gabriele Corso, Luca Cavalleri. Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004. 05718, 2020.
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, pp. 1844-3852. 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Espuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-222233 2232,232, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Ehsan Elhamifar and Rene Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE transactions on pattern analysis and machine intelligence, 35(11):2765-278. 2013.
Chengyue Gong, He, Xu Tan, Tao Qin, Liwei Wang, and Tie-Yan Liu. Frage: Frequency-agnostic word representation. In Advances in neural information processing systems, pp. 1334-1345, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. In International conference on machine learning, 2020.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv: arXiv:/506.00 1506.05 163, 2015.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint 20t::200050008887 2020.
10

---

Under review as a conference paper at ICLR 2021
Pan Ji, Mathieu Salzmann, and Hongdong Li. Efficient dense subspace clustering. In IEEE Winter Conference on Applications of Computer Vision, pp. 461-468. IEEE, 2014.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 14X2::1412.6800 6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 13354- 13366, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Qing Lu and Lise Getoor. Link-based classification. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pp. 496-503, 2003.
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, pp- 1412-1421,
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, pp. 5115- 5124, 2017.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Bryan Perozzi, Rami AI-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, pp. 701-710, 2014.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figuciredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 385-394, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad. Collective classification in network data. Al magazine, 29(3):33-93, 2008.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint
2018
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Weisfeiler and A Leman. The reduction of graph canonical form and the algebgra which appears therein. NTI. Series, 2, 1968.
Zonghan WI, 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.
11

---

Under review as a conference paper at ICLR 2021
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 2015.
attention. In International conference machine learning, pp.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 1rXiv:1810.00826 2018.
Li Xu, Jimmy SJ Ren, Ce Liu, and Jiaya Jia. Deep convolutional neural network for image decon- volution. Advances in neural information processing systems, pp. 1790-17999 1790- 2014.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40 48. PMLR, 2016.
Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In International Conference on Learning Representations, 2020.
Shuo Zhang and Lei Xie. Improving attention mechanism in graph neural networks via cardinal- ity preservation. In IJCAI: proceedings of the conference, volume 2020, pp. 1395. NIH Public Access, 2020.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Sumi-super learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
12

---

Under review as a conference paper at ICLR 2021
A
PROOF OF THEOREM
To prove Theorem
| we need to consider the two directions of the iff conditions Zhhng & Xie
2020). If given ei C22 Si S2, and Zy=x,yex, Sely Soy=-ym fozv y'yy=a.ve X2 Se2y Iz, for the aggregation function utilizing the joint attention mechanism Ey Zy=m.yEx Seigl for q = ry"
shown in Eq. 7 we have:
MG, Xi) Σ aczg(0)) xEX,
aee =T far T's S0,s
(11)
exp (Me,.)
exp (Co,z)
fax= = Exex, exp (Mapp)
80, Exex, exp (Craa)
where ma represents the feature similarity between and æ. Given Eq. we may directly derive (1c and X2):
M1), = Σ
(c)g(z)=
Σ Iry fer + Seua] g(x)
zEX1
xEX1
(12)
h(c2, X2) = Σ
Oc)=g(x)
Σ xEX2
Iyy fea + tra Seze] g(x)
xEX2
Considering C1 = 02, S S2, and Σy= few Ey=nwex, Seru = q Ex S0z Eyn, Sogy) for Ez we directly derive h(c,, X1) = M(2,, X2).
If given h(c,, X1) Mc2, X2), able to prove that the conditions mentioned in the theorem are necessary by showing contradictions occur when they are not satisfied. If h(c2, X2), have:
h(c,, X1) X2)
Σ bry far + Sesa] g(x) - Eiry
Iry fer + ro sezal g((z) = 0
(13)
x
xEX,
Firstly, assuming Si # S2, for any g(-), thereby have:
h(c1, - h2c2
Σ1 Σ
Irs Sal +r. 8e19
ISS g=r,
Σ
bry Sel TTa Secull g(z)
yo
(14)
Σ
Σ
Sey + r. Sesgl g(x)
zES (229 ExE,,,
Σ
Σ
bry Seay + rs sezal g(x) =
zES,
yE
As Eq.
14 holds for any g()), we may define another function g'()) follows:
g(z) g'xx), for E S1 S.
g(z) = g'(x) 1, for E Si \ S2
(15)
g(z) g'(x) + 1, for x E S2 \ S
13

---

Under review as a conference paper at ICLR 2021
If Eq.
14) holds, also have:
X1) h1(22, X2)
El Σ
by fay + ro Servl
zESInSa w=N.NEX.
Σ
bry Sex + rs :82a0l (2(2)
y=
Σ
Σ
Iry - Sery tr scvul g(xx)
rE Say=n.yEXi
E
Σ
bry foa + rr sozul g'(x)
SE y=x.yEx2
(16)
EL byg. ferv +Ts Scyvl
RESINSA=II.JEN
E byy Sezu + Se2pll g(Ø)
Σ
Σ
bry Sel + ro sc,ul [g(x) - 1]
zES 1.0
Σ
E
byy feay + re Sezal [g(x) +1]
zE82 y X2
As Eq. 14 equals Eq. (16). we have:
ΣEM
Σ lry felv + ro Serus +
Σ
Σ
bry ferv + + Sezg] 0
(17)
#ES NES
#E
y=I,yEX;
Obviously, the above equation does not hold the terms in the summation operator positive.
Thus, S * S2 is not true. We may now assume S = S2 = Eliminating the irrational terms in
Eq. 14), have:
Σ1E (yy Sey + servl
Σ
Iry Saay + rs :egvll g(x) = 0
(18)
xE9, y=2.
g=r,yEX2
Thus we know each term in the summation equals zero:
Σ Iry Say Ts Scav]
Σ
Iry Sezy + 802g.
(19)
yE
V=R
As structural coefficients and node feature similarity are heterogeneous, we may assume Σ, n.yx X2 Ts Bogy Ey Ya Sogy. Eq, 19) can simplified and rewritten as:
(1(x) exp (Mozw) ExEs, Σ NEX exp (Mczz)
(20)
(2 exp (Megæ) Exes, Ey=nveX, exp (Mazz)
obvious that LHS of Eq. 20 rational number. However, the RHS of Eq. 20) can be an irrational number. We may consider S = {s, so} and assume
= We may also assume
the feature similarity between central node and others follows:
meiz for x E S
(21)
Megs 1, Mazso
Consider x = we have:
(1(s)
XX
(22)
(2(ss)
X₂
- n
where n stands for the number of so in X2. It is obvious that the above equality does not hold as the RHS an irrational number, while LHS is rational number. Thus Ci C2 is false. Given Ci C2+ Eq. 19) can be rewritten as:
Σ VX
rf Sav
Σ y=
rf Segy
Σ V=RwE
Σ y=
Ts Segy =0
(23)
14

---

Under review as a conference paper at ICLR 2021
To ensure above equation holds, have:
Σ feu E
Sewr Po Σ Beay
Σ Seryl
(24)
rs y=r.yEX;
D=R.yEX1
VE
y=a.yE
Further denoting Ia q, we have Ey=oNeX, feN Ey=r Seay g1 Seay Ey=eweX, Scig.
B PROOF OF THEOREM
To prove Theorem 2 we can follow the procedure which is used to prove Theorem | If given = C2. S1 S2, and q Ey=z,yex, o(Cery) Ey= ((Co.g), for > 0, may directly replace o(+) using exp(.). For the aggregation function using the joint attention mechanism in Eq. we have:
Ma,, Xi) = E Oaaz(())
mEX;
ac = fer: Spez
(25)
ExeX X, Segz Boga
exp (Me,w)
exp (Co,z)
See Exex, exp (Majr)
Sega
Erex, exp (Crar)
where Mayr represents the feature similarity between and Given Eq. derive h(11,X)) and X2):
25
we may directly
Jez 861
h(c1 Σ (c)a(())=
Σ
gg(z))
xEX; Σ
DEx, fax Se1x
xEX1
(26)
Jeez Sega 1 g((x)
h(c2, Σ
dezn((x)=
Σ
EvEXo Seex 8824
xEX2
Given 8₁ S2 and =C2, h(22, X2) can be rewritten as:
Seyu Ey=r,yEx, Sezy
X() = Σ
gg)(z)
zE82 Exes, fer Ey=owex, 8ozy
E Eyen,yExs Eyex, exp exp (Cezu) Eyex, exp (Mazy]
exp (Mogz)
exp (Cou)
g(x)
(27)
exp (megr)
exp (Cegy)
zES;
2xe82 Evex, vex, exp
Ey=z,yeXa Evex, exp (Crzu)
exp (Mez²) E Σy=r,EE,, exp (Ceyy)
g(x)
Eres, exp (Magz) Ey exp Cozy)
ZES,
Given q Exex, exp(Cerx) Ey=r Co Eq. (2 equivalent to:
q exp (Megæ) Ey exp (Ceiy)
Xo) = Σ
Eaes, q eexp (Meza) Eynn exp (Co,v) 9(x)
(28)
zES1
Considering C1 = C2, we have 1((11, X1) = h(22, X²).
If given h(c1, X1) h(c2, X2), able prove the conditions mentioned in the the- orem are necessary by showing contradictions occur when they are not satisfied. If h(c1, X1) h(c2,, X2), have:
X1) (2)2, =
Σ xex,
faxx SE5T
g(x) Σ xxX,
ferr Sexr lg(()) -1.
(29)
Erex, Sag S01z
E N2 Sogn Sogz
15

---

Under review as a conference paper at ICLR 2021
Firstly, assuming S1 # S2, for any g(-), we thereby have:
exp (Meru) Ex=Z,DEX, exp (Cor))
X1), h(c2, X2)
Σ
Exes, exp (Mexs DymONEE exp (cpp)
2ES nS
(m)g)) Ey=r. yy e exp (Cogy)
g(z)
Exese exp (Moze) EyEn exp (Cesy)
(30)
exp (Marr E L exp (Crrg)
Laes exp (Mozz) E Ey=a.eex, exp (Cayy) ((())
zES1 S
exp (Mazz) E EyER.EEX, exp (Co.u)
Σ SE
Emres, exp (Mogz) Ey=n,eex, X exp (Cozy) g(x)) =0
As Eq. 30 holds for any g(-), we may define another function g'(-) as shown in Eq. holds, we also have:
15
If Eq.
30
cxp (Meru) Ey exp (Co.v)
h(e,, - h2c2, =
LIES exp (Morr) Ey N.x, exp (Co
zES
(xpe)) Ey Ey exp (Cozg)
g'(x)
Exes, exp (Mozn) E Lg=I,EE,, exp (Crzn)
exp (Meaa) E Ly=DNEE exp (Cav)
Σ
gxxx)
Exes, exp (Merz) E DY=B.EEX, exp (Cery)
#ES1 (/2
exp (Mega) Ey X2 exp (Crzy)
(()))
9 (z)
EeEs, exp (Mazz) Σ Eyerieex exp (Ceay)
(31)
exp (Mozæ) En y JyN., exp (CoLv)
=ESinSa Eres, exp (MaIz) E Σy=rnEE exp (Cery)
exp (Mezz) E EyEnNEX, MEX, exp (Cewy
g(x)
Exes, exp (Meza) E EyEryEX, exp (Copy)
exp (Nexz) E Ey=RWEX, exp (Co,))
[g(x)) - 1]
Zxes; exp (Marz) E Ey=r,yEx, X, exp (C..))
xES1 1/52
exp (Mega) Ey=rieex exp (Cezy)
Σ
Less, exp (Mez)) E Eyzrieex exp (Ceny) 1 [g(x)) + 1] = 0
2E8 S
As Eq.
30
equals Eq.
31. we have:
(mp))) E Eymn,eE exp (Ce,y)
Σ
Σ Exes, exp (Mazz) Σ Ey=R.EEX, exp (CeLy)
zES, 1.2,
(32)
exp (Meza) E Ey=r,eEX, exp (Cozy)
Σ
Exes, exp (Mozz) E Ey=n. exp (Cezy)
#ESASS
Obviously, the above equation does not hold as softmax function is positive. Thus, S1 / S2 is not true. We may now assume S = S2 S. Eliminating the irrational terms in Eq. (30p, we have:
exp (Maiz) Ey X, exp (C..y
s,,, Exes, exp (Mezz) Σ Eyerneex exp (Cery)
(33)
exp (Mozr) Ey=a.vex, exp (Cowy Exes, exp (Megz) E Ex=nyeX, exp (Cegy) g(x) 0
16

---

Under review as a conference paper at ICLR 2021
Thus know each term in the summation equals zero:
exp (Meiæ) E EyEn,EE exp (Ce.y)
exp (Meza) E y exp (Cezg)
E Exes, exp (Maza) E Ey=nyex, exp (Cey) Er exp (Meza) 2y= exp (Cezy) -0
(34)
Eq. (34) is equivalent to:
E Eyer.eex, exp (Ca.y)
exp (Meza)
E ExES, exp (Mera) ) E Zy=z,yEX DE exp (Cray)
(35)
Ey=r,eex, exp (Ceay) exp (Meiæ) ExEs, exp (Mezw) Zy=z, exp (Ceyy)
We may consider S {8, 8o} and assume 6i similarity between central node and others as follows:
80. C2
s. We may also assume the feature
Maz = 1, x E S
(36)
Mczs 1, Mcz00
Consider we have:
ExEx, exp (Cere)
elc EeEx, exp (Cers) + &Zeoex, exp (Ce
(37)
Σxex, exp (Cozs)
ele Leex, exp (Cozs) e
<<> Eeeex exp (Co2so)
As the learning of C is independent of feature mapping. and the computation attention coeff- cients, exp (Cez) can be any positive value. By setting the exponential values in the above equation
as a, which is a positive value. We have (1
- Similar with Eq. (2 C1 # C2 is not
X11
ua(a)
true. Since e = C2 = c, Eq. (35) can be rewritten as:
Σy=rwex, exp (Cey) Emes; exp (Mox) Ey=n exp (Cey) const > 0.
(38)
Eyer.vex, exp (Cay) Exes, exp (mxx) Ey= exp (Cay)
By setting const as 1 and exp (Cay) ((Cog) we have 11 E &(Coy) Eymr (Coy).
C PROOF OF COROLLARY
For any two distinct multisets X1 and X2 that cannot be distinguished by T. according to Theorem 1, we denote X1 = (S, X2 = (S, p2). e S. We also assume E Ey=ryee fay - Ey=a.vex, fezy
q q (yy=nnvx Sazg - EE Seyyl for q When using the attention mechanism in Eq. ( for the aggregation function, it is easy to verify Exex, aazi(x))
ry
ExEX, acn When using the improved mechanism shown in Eq. (0)).
we have ExEx, acef(x) - -EEEX, fxx = ( Thyy (ae where |Xyl = [i.. and [X2] [/ Since |X1| * |X2], 1221.TEE Exex, (er - ExEx, (xx) & O. meaning the improved joint attention mechanism can distinguish those distinct multiset which T fails to distinguish. Sim- ilarly, can prove the aggregation function using the improved attention mechanism concerning Eq. (8) also can distinguish those distinct multisets which T fails to distinguish.
D DETAILED EXPERIMENTE SET-UP AND ADDITIONAL TESTS
In this section, how the experiments used to validate the effectiveness of the proposed JATs are set up introduced with more details.
D.1 DATASET DESCRIPTION
Four document networks, which are Cora, Citeseer, Pubmed (Lu & Getoor 2003 Sen et al. 2008 and OGBN-Arxiv (Hu et al. 2020), are used in our experiments to validate the effectiveness dif- ferent GNNs. In these four networks, vertices, edges, and vertex features represent the documents, citations between pairwise documents, and the bag-of-worde representations of the documents, re- spectively. Besides, each node in these four document networks has class label.
17

---

Under review as a conference paper at ICLR 2021
Table 4: Characteristics of the testing datasets used in our experiments
Cora
Citeseer
Pubmed
OGBN-Arxiv
N
2708
3327
19717
169343
E
5429
4732
44338
1166243
D
1433
3703
500
128
7
6
3
40
Training Nodes
140
120
60
90941
Validation Nodes
500
500
500
29799
Test Nodes
1000
1000
1000
48603
As graph transductive learning is mainly considered in our experiment to validate different ap- proaches, we set up the experiment closely following the settings in the related works (Yang et al.) 2016 Veličković et al., 2018 Hu et al. 2020). All the datasets are split into three parts: training, validation, and testing. For datasets Cora, Citeseer, and Pubmed, we use only 20 nodes per class for training, but all the feature vectors. For dataset OGBN-Arxiv, we use a practical split strategy, seg- menting the nodes which represent the academic papers, according to publication years (Hu et al. 2020). Papers published up to 2017 are in the training split. While papers published in 2018 and 2019 are used for validation and test, respectively. The performance of different approaches evaluated on the test split. The statistics of these benchmarking datasets are summarized in Table
4. where N, [F], D, and C' denote the number of vertices, edges, vertex features, and number of classes in each dataset, respectively.
D.2 EXPERIMENTAL SCENARIOS
The effectiveness of different methods is validated via allowing them to perform semi-supervised learning (transductive learning) in the aforementioned graph datasets. To compare the proposed JATs impartially with other baselines, we closely follow the experimental paradigms used in pre- vious works (Yang et al., 20166] Kipf & Welling 2017; Veličković et al., 2018 Hu et al. 2020). Specifically, only partial nodes in each class are labeled in the training stage, and all the graph data, including vertex features and edges, can be accessible for the training of neural networks. The pre- dictive ability of the approaches is validated using the nodes in the test split. Algorithm performance is evaluated using Accuracy (Micro- Fi).
For the network structure of JAT, following GAT (Veličković et al. 2018). we use a similar two- layer deep neural network to learn node representations in all the testing datasets. The first layer consists of multiple attention heads computing multiple features, followed by an exponential linear unit. In our experiment, eight attention heads are used for Cora, Citeseer, and Pubmed datasets and three attention heads are used for OGBN-Arxiv. The second layer, composed of attention heads and a softmax activation is used for node classification. For Cora, Citeseer and OGBN-Arxi,, single attention head is used, while for Pubmed, eight output attention heads are used, to compute C features. As for the dimensionality of the hidden units, also following the settings used in previous works (Veličković et al.] 2018 Hu et al. 2020). The dimension of hidden units set as 8 for Cora, Cite, and Pubmed, and is set as 256 for OGBN-Arxiv. Regularization is applied within the model to cope with the small training set sizes. During training, L2 regularization with = 0.0005 and dropout with p- 0.6 are applied for both layers' inputs when JAT is training with Cora, Citeseer, and Pubmed. In DignnAAxii dataset, the setting of A = 0 and dropout with 0.05 used.
All the networks are initialized using Glorot initialization and trained to minimize cross-entropy on the training nodes using the Adam SGD optimizer (Kingma Ba 2014). A learning rate of 0.01 is used for datasets Cora, Citeseer, and Pubmed, while that of 0.002 is used in dataset OGBN-Arxiv. As JAT requires structural coefficients to compute attention scores, Eq. our experiments, we use two different strategies to obtain optimal structural coefficients. For those datasets with small size, e.g., Cora, Citeseer, and Pubmed, Eq. (2) is optimized together with the training of the networks. In other words, loss function aggregating cross-entropy on the training nodes and structure reconstruction error Eq. (2) is used. Eq. (2) is iteratively optimized along with the training of JAT' and the structural coefficients obtained in each epoch can be used by JAT for
2 needs optimizing. In
18

---

Under review as a conference paper at ICLR 2021
the computation of attention scores. For datasets possessing huge number of nodes, e.g., OGBN- Arxiv, Eq. 2 is optimized ahead of training JATs for the purpose of dealing with limited computing resources. Under such case, the training efficiency of JAT's can be significantly improved.
90
Cora
Cite Pubmed
Cora
Cite
Pubmed
Accuracy (%)
85
Accuracy (%)
85
80
80
75
75
70
70
0.01
0.1
1.
5
10
20
50
100
0.01
0.1
1
5
10
20
50
100
B
B
(a) JAT-I
(b) JAT-E
Figure 3: Sensitivity test on B
D.3 SENSITIVITY TEST ON |
For sensitivity test on 3, which determines the relative significance of graph self-expression (Eq. ) we set B = [0.01, 1,5, 10, 20, 50, 100) and two versions of JAT to classify nodes on the three smaller datasets. The corresponding results have been plotted in Fig. 3 (a) and (b). As the figures depict, both two versions of JAT may obtain a robust performance when different settings of B are used. It is experimentally found that the variations of & have limited impact the performance of JATs. Based on the obtained results, we set 3 for JATs when they perform the tasks of sepe-supe node classification various datasets.
D.4 PERFORMANCE ON NODE-WIST IMPLICIT DIRECTION STRATEGY
As defined in Eq. (6. g and are layer-wise parameters which can capture the overall significance of graph structure and features in each layer the neural architecture. They naturally can be node- level parameters in each layer of JAT, i.e., 9if and Jis- As a result, the original Implicit direction strategy becomes node-wise Implicit direction strategy which can learn the relative significance of graph structure and features of each node when computing attention scores. And such node-wise Implicit direction strategy is defined as follows:
exp (g:r)
exp (gis) Tis exp (gie) + exp (gr))
Tif exp (gie) + exp (ghs)
(39)
Tif Súj + Tis 8ij
0ij ELEN, [ris fix + Tis stee
ray foz + ris 8ij.
where Tiy or ris represents the normalized significance related to structure or node features asso- ciated with node i. Given the node-level joint attention mechanism defined in Eq. (39). JAT also can perform the task of representation learning in graph structured data. Here we compare its per- formance on transductive learning in datasets Cora, Citeseer, and Pubmed with the original two versions JATs, i.e., JAT-I and JAT-E, The corresponding results are summarized Table 3 As the table shows, the performance of JAT utilizing the attention mechanism of node-wise Implicit direction strategy is similar to that of JAT-E. According to the presented results, node-wise Implicit direction strategy is potentially effective method through which JAT can learn meaningful repre- sentations for the subsequent predictive tasks. We will further investigate the effectiveness this new strategy in our future works.
19

---

Under review as a conference paper at ICLR 2021
Table 5: Performance comparison on JATs using different attention strategies
Different versions of JAT's
Cora
Citeseer
Pubmed
JAT-E
85.5+0.4% 85.8+0.5%
82.0=0.3% 73.8%0.4%
JAT-I
82.8+0.4% 74.340.4% 72.5+0.5%
JAT-I (node-wise)
85.4 +0.3%
82.6+0.2%
E DISCUSSIONS
In this section, we perform some detailed discussions that may help one to better understand the proposed JAT'.
E.1 MODEL COMPLEXITY
we may analyze the computational complexity of the pro- posed JATs. According to Eq. B for each node in the graph, the complexity for computing all the structural coefficients can be expressed as +NN for the worst case. However, as real graphs are always very sparse, the complexity for learning structural coefficients can be reduced to O(e² + e), where e represents average degree of the nodes. As the learning of each C,,; is independent of others, Eq. 2 can be efficiently solved via parallel distributed optimization strategies. For the computa- tion of each attention head in the graph neural network, its complexity for learning F++1 features for each node can be represented as D' + (I ) which is same the classical GAT. If there are K attention heads used, the complexity becomes ((KNDD'D' E + D)))+)). )).
Based on the descriptions in Section 2
E.2 STRUCTURAL INFORMATION FOR COMPUTING ATTENTION SCORES
In the proposed JAT', structural coefficients learned from graph subspace are used for computing tention scores and the corresponding experimental performance is robust when compared with other state-of-the-art baselines. The module for learning structural coefficients is motivated by subspace clustering (Elhamifar & Vidal, 2013) Ji et al.) 2014). which is an effective methodology for un- covering data clusters through performing the spectral analysis on the coefficient matrix (C). Such matrix is also named as aefe-xxpeessveeess matrix as it contains the coefficients which can construct a linear combination of each sample using others. Given Eq. (3). we know that the subspace learn- ing module can directly infer the node-node correlations based on the graph data and those nodes sharing similar global structures (i.e., graph connectivity) may have higher structural coefficients. Rather than performing spectral analysis C, JAT directly makes use of the coefficients in it to compute attention scores for representation learning. This may allow JAT to pay more attention on those nodes which are structurally correlated when aggregating features passed to the higher layers.
Though an effective method for structural coefficients learning, the proposed module is only one of the alternatives that be utilized by the generic framework JAT. As shown in the manuscript, C learned by the subspace learning module is different from the one learned by those methods for structural network embedding, such Deepwalk (Perozzi al., 2014), Node2Vec (Grover & Leskoved 2016), Struc2vec (Ribeiro er al. 2017), and LINE (Tang et al. 2015).. For such network embedding methods, the node-node correlation can be recovered via obtaining the inner product of node-wise representations. Given the fact that these network embedding methods also can effec- tively capture the node-node correlations, they are also effective alternatives for learning for the proposed JAT. In the ablation study, we show that JAT may perform robustly even working with simple measures, e.g., Cosine and Jaccard similarity for obtaining node-node structural correlations, which indicates the proposed joint attention mechanisms are the main reasons boosting the perfor- mance the attention- based GNNs. Thus, any measures/methoos, that may effectively capture structural relationship between pairwise nodes in the graph. including those network embedding ap- proaches and deep structural learning approach such as MoNet (Monti et al. (017) can be used by JAT capture node-node structural correlations for computing attention scores.
20

---

Under review as a conference paper at ICLR 2021
E.3 RELATION BETWEEN JAT AND APPROACHES TO NETWORK EMBEDDING AND OTHERS
Concatenating the learned structural representations and corresponding node features, effective net- work embedding approaches, such Deepwalk Perozzi al. (0014) Node2 Grover & Leskovec (2016). Struc2vec (Ribeiro et al.] 2017). and LINE (Tang et al. 2015) can also consider both struc- tural and feature information for the subsequent learning tasks. Compared with them, the proposed JAT has its unique properties for learning graph representations. Rather than directly concatenating the structural and feature vectors, JAT utilizes novel joint attention mechanisms which may automati- cally determine whether graph structure or node feature is more important, to infer low-dimensional node representations via multi-layer feature aggregation. As C is used for computing attention scores, the node representations learned by JAT are automatically implanted with meaningful struc- tural information hidden in the graph. It is seen that the strategy for automatically determining the relative significance between graph structure and vertex features and the verified expressive power distinguish the proposed JAT from other related works. Besides, for attention-base GNNs, the proposed joint attention mechanisms mation for computing attention scores. No previous mechanisms for GNNs can consider learning the relative significance between graph structure and node features for computing attentions scores. The proposed JAT is also different from those GNNs considering structural information, e.g., diffu- sion (Klicpera et al., 2019 Busch al. 2020) or GCNs for subspace clustering (Cai et al.) 2020). Those diffusion based GNNs mainly consider higher-order structural information among node pairs to formulate the functions for feature aggregation. As for GNNs for subspace clustering, their main task is to learn the self-expressive matrix, i.e., C, based on the deep neural networks and then data clusters are inferred via performing spectral analysis on the learned C. Compared with them, JAT directly makes of C and node features compute attention scores for aggregating the features passed to the higher layers. C in the proposed JAT plays an important role in obtaining appropriate feature aggregations, rather than clustering. Given the mentioned facts, the proposed JAT is novel compared with existing methods.
also novel attempts to effectively consider structural infor-
E.4 LIMITATIONS OF JAT
Though effective in predicting node labels in transductive learning tasks, the proposed JAT has some limitations to overcome in the future. First, the efficiency for learning C in the current version of JAT somewhat unsatisfying. Based on the analysis on computational complexity, JAT has to pre-train C for those massive datasets (e.g.. OGBN-Arxiv) due to the limited computing resources. More efficient techniques for capturing the node-node structural correlations can therefore be considered by JAT. Based on the results shown in the ablation studies, the proposed joint attention mechanisms ensure JAT to perform robustly as long as the used node-node correlations can effectively reveal the structural properties of the graph. Thus, those network embedding approaches and other efficient methods for deep structural learning can be combined with the generic JAT. Second, the expressive power of JATs is theoretically validated mainly in the countable feature space in this paper. In those graphs whose features are in uncountable space, the expressive power of JATs needs re-verifying fol- lowing the recent framework proposed in (Corso et al. 2020). As mentioned in (Corso al. 2020). some theorems related to the expressive power in the countable feature space might not always hold in the feature space uncountable. To the theoretical perspective, attention mechanisms which are analogously powerful in both countable and uncountable feature spaces are thereby needed by both JATs and other attention- based GNNs.
21


Reviews:
[{"review_id": "l7mzZG7gyep", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall Comments:\nCreating aggregation weight over neighbor nodes lies at the key part of graph neural networks. Generally the weights can be generated by the node structure or feature similarity. The node structure similarity provides a way to measure the correlation of a pair of nodes with a complete graph. While attention weight usually focuses on the local neighborhood, which can be easily biased by the node popularity [1, 2]. If a neighbor node with large degree, it potentially tends to have a large embedding norm. However, from complete view of graph structure, this neighbor might be a noisy node. With a given complete graph structure, we can downgrade the influence of structure bias. From this point of view, it's interesting to study whether the attention and structure weights can be complementary to each other. The key idea of this work is very easy to follow. The proposed strategy is to unify the weights generated by graph structure and node feature. Theoretical analysis shows the expressive power of  the proposed strategy. The experimental results for node classification also demonstrates its superiority comparing with state-of-the-art baselines.\n\nPresentation:\nThe presentation of this work is very clear and organized very well.\n\nQuestions:\n1. The coefficient matrix C is learned by recovering the adjacent matrix A. To some extent, it tells the correlation between a pair of nodes. Can we replace it with another correlation matrix, such as Jaccard similarity matrix where each element stands for the node similarity measured by Jaccard equation or Personalized PageRank diffusion matrix? That'd be interesting to see the influence coming from the coefficient matrix obtained by different methods.\n\n2. In Section 2.1, what is the role of the multiset M_i? It's a little difficult to understand without any background introduction in this subsection. Maybe more justification about the notations are needed to show its connection to next section.\n\nReferences:\n\n[1] Gong, Chengyue, Di He, Xu Tan, Tao Qin, Liwei Wang, and Tie-Yan Liu. Frage: Frequency-agnostic word representation. In Advances in neural information processing systems, pp. 1334-1345. 2018.\n\n[2] Armandpour, Mohammadreza, Patrick Ding, Jianhua Huang, and Xia Hu. \"Robust negative sampling for network embedding.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 3191-3198. 2019.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RZEebxFHjbR", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---- Summary\n\nThis paper proposes Graph Joint Attention Networks (JAT), which augment Graph Attention Networks (GAT) by introducing structural attention coefficients, which are combined with the feature based attention coefficients computed by GAT. The authors present two ways of incorporating the structural coefficients, namely Implicit direction and Explicit direction. The authors evaluate their proposed technique in the Cora, Citeseer and Pubmed datasets, where they improve the performance of other GNN approaches.\n\n---- Pros\n* The paper presents an interesting approach to introduce structural information when computing the attention coefficients in an attention-based GNN.\n* Good analysis of the expressive power of JAT\n* The method presented in the paper achieves state of the art results in the datasets it is evaluated with.\n\n--- Cons\n* The empirical evaluation is a bit limited, since it evaluates only with Cora, Citesser and Pubmed which have been shown to be not entirely appropriate to evaluate GNNs, in favour of better benchmarks like the ones proposed in [1] and [2].\n* It isn’t very clear exactly how the minimization of Equation 2 is done. Is it solved once for each graph or is it solved at every training iteration? The authors say that “JATs can optimize Eq. (2) together with the training of the neural architecture.” so it isn’t clear how it is done. If A is always the same for each dataset (Cora, Citeseer and Pubmed are one single graph each) why not minimize it just once before training? \n* The authors don’t mention the complexity of their approach. If JAT were to be applied to a different graph structure all the time, so A is different for each sample in a dataset consisting of multiple graphs, what would be the complexity of the method considering it has to minimize Equation 2 to obtain the matrix of coefficients C?\n* The experimental section lacks some ablation studies. For example, what if only the structural attention coefficients are used? What happens if noise is included in the adjacency matrix? What if structural coefficients are all constant? Then the model should be empirically equivalent to GAT.\n\n---- Questions\n* For very different values of $\\beta$ (ranging from 0.01 to 100), JAT seems to achieve very similar performance, a behaviour consistent across datasets. Any idea why that is the case?\n* The implicit direction mechanism is a bit unclear in the paper. What are $r_s$ and $r_f$ in Eq 6? They have not been introduced before and it isn’t clear where do the indexes $f$ and $s$ come from. I think Eq 5 would be a bit clearer if written like $$ r_i = \\frac{exp(g_i)} {\\sum_{k \\in \\\\{s,f\\\\}} exp(g_k)}, i \\in \\\\{s, f\\\\} $$ Although it is still a bit confusing, using $i$ as an index when it has been previously used to denote node indexes is confusing. \n* $g_s$ and $g_f$ are global parameters, meaning that each node structural and feature coefficients are weighted in the same way. Why not learn these parameters for each node, so that some nodes can rely more on features and other nodes can rely more on structure?\n* Could JAT work in the inductive case where the training and testing structures are different?\n\n---- Minor Comments\n\nThe font-size in the plots in Figure 2 should be increased, it would be very difficult to read if the paper was printed. \n\n---- Reason for score\n\nThe paper proposes an interesting technique to use the graph structure as well as the nodes features to compute attention coefficients, however the experiments are a bit limited, using only three small datasets and limited ablation studies. Additionally, some of the details of the paper are not clear. For these reasons, I consider the paper to be marginally below the acceptance threshold.\n\n------------ Post rebuttal update\n\nI appreciate the rebuttal made by the authors, as they have clarified my questions about the paper. It is also good that a new dataset and additional ablation experiments have been added to the paper, however, the empirical section still needs to be improved in my opinion. \nFor example, more datasets and stronger baselines could be used, and I believe the authors could do it if they had more time. Therefore, even though I mantain my score, I encourage the authors to strengthen the empirical evaluation for future submissions.\n\n---- References\n\n[1] Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., & Bresson, X. (2020). Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982.\n\n[2] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., ... & Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F_xK-MU9wn9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper discusses how to introduce some form on non-local structural information into the node representations by collating cluster similarity information from a topological subspace clustering with a classical spatial graph convolution. Both information are mediated by attentional mechanisms which also take care of mixing the topological and convolutional contributions.\n\nOn the positive side, the proposed approach seems to work well empirically, although results are limited to 3 standard benchmarks on node classifications. The community is trying to surpass the use of those 3 datasets, due to both their simplistic nature (see ogb.stanford.edu for challenging node classification benchmarks) and pitfalls in their evaluation (https://arxiv.org/pdf/1811.05868.pdf). \n\nThe paper also provides a theoretical proof of the representation power of the proposed JAT, following the consolidated approach started in the GIN paper. I am not particularly fond of these proofs as they are mostly technically correct but poorly original exercises showing that the proposed method is more or less 1-WL equivalent. In the paper, such proofs are leveraged to show a class of substructures on which the vanilla JAT model fails, providing a correction that solves the issue. Which would be fine, apart from the fact that the proposed work-around (i.e. considering neighbourhood size of each node) is standard practice in node classification tasks, where node degree is added as a node feature in input to the model (with excellent accuracy boosts). \n\nThis brings me to the big issue in the paper: originality is minor. The work is heavily based on the GAT model extended, again by a fairly standard attention-based approach, with the topological clustering information. This latter aspect is allegedly the novel part of the work, but the paper does not analyse the implications of adding such topological information in full depth. The paper is very generic in referring to it as an enabler for considering higher order structural information, without providing any insight onto the nature of such added information. To me, the introduction of subspace clustering information is somehow pushing some spectral information into the spatial convolution-based approach by GAT. In this sense, I see the proposed JAT as an attempt to trade between spatial and spectral features. In the literature there are works providing evidence on how mixing the efficient, but local, approach of spatial convolutions with the global information from spectral methods typically yields to increased predictive accuracies (see papers.nips.cc/paper/9490-diffusion-improves-graph-learning.pdf). I would have liked to read in the paper a discussion placing the proposed approach in this recent interesting literature, e.g. leveraging diffusion information (as in the paper above or https://ecai2020.eu/papers/1339_paper.pdf) or very related subspace clustering methods (https://ieeexplore.ieee.org/document/9181470).  Instead, the discussion of GNN background (Section 1) and related methods (Section 2.) is quite shallow. This is a pity (and the second major issue in the paper) and it reduces considerably the impact of the work, especially considering the scope of the ICLR conference. \n\nThere is a third issue which relates to some limitations of the approach which are more or less obfuscated in the paper. The work focuses on node classification tasks, ie. where data comprises a single network. Why is this? Is it because the method cannot handle a dataset of graphs of varying topology (e.g. as in graph classification)? Similarly, why (in Section 2.1) the model is restricted to work with only binary node features? Is this limitation purely notational or does it affect the model? The manuscript should be very clear in stating the limitations of the proposed approach, if any, and what bit of the model is possibly introducing such constraints.\n\nIn the empirical analysis, Figure 2.c should also report the confidence intervals, as I am not convinced that the difference “with and without ad” is statistically significant. \n\nThe denominator in (5) can be simplified as it is a summation over two elements.   \n\n=========== POST REBUTTAL\n\nI have really appreciated the effort placed by the Authors in their rebuttal. Here follows some considerations following rebuttal:\n* The empirical analysis has been strenghtened with the inclusion of the OGB benchmark as it provides a view of the empirical performance of JAT in the context of a challenging dataset within a standardised setup. At the same time, OGB allows direct comparison with leaderboards and results in literature that highlight how JAT performance are not (as claimed) state-of-the-art. In this sense, it is still quite unclear if there is any practical advantage with respect to GAT.\n* The revised paper version places the work much better in the context of recent related literature.\n* Also considering the point above, the novelty of the work is still borderline to me.\n\nIn summary, the work has good potential, but it is not yet ready, hence my decision to stay on the reject side. The contained originality can be made up in a future submission by providing convincing state-of-the-art performance results on challenging benchmarks, showing substantial differences from related models such as GAT. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "45ILCcPqu2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose Graph Joint Attention Networks (JATs) as a mechanism for explicitly incorporating structural information in the GATs attention mechanism. \n\nJATs separately learn a \"structural\" attention matrix which:\n\n(a) exploits structural correlations between vertices;\n(b) forces diagonal entries to be zero to avoid trivial solutions (clever!);\n(c) is regularised using the L_1 norm, to promote sparsity.\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.\n\nOverall, I found the work's theoretical contribution to be impressive. However I cannot recommend acceptance in the current form based on the theory alone, and in particular, the following three major points should be addressed by the authors before the paper is ready:\n\n- The authors only evaluate their work on the Cora/Citeseer/Pubmed citation networks, which are known to be oversaturated and unreliable as graph representation learning benchmarks (see e.g. \"Pitfalls of Graph Neural Network Evaluation\" from Shchur et al.) and should be avoided as centerpieces of evaluation. I would like to see experimental results on either OGB (Hu et al., NeurIPS'20) or Benchmarking-GNNs (Dwivedi et al.), which are two established datasets that have been around for long enough by now, and are easily accessible via existing graph learning libraries.\n- The proposed structural learning work is one way of injecting structural information into the attentive mechanism, but is not the only one. Actually, taking either:\ntop/bottom-k eigenvectors of the Graph Laplacian, or\na structural embedding method such as DeepWalk/node2vec/struct2vec/LINE, \nas additional structural features to be concatenated with node features, could yield a similar effect of exploiting structural similarities without necessitating the need for two attentional mechanisms or additional learning objectives. Also it might be interesting to contrast the method proposed here with MoNet (already cited), which only performs attention on structural features -- maybe MoNet coefficients could serve as a possible replacement for the C matrix. Could the authors compare with some of the above, either theoretically or empirically?\n- Lastly, and in relation to the previous point, I found the following claim by the authors:\n\"First, there are no appropriate attention mechanisms which can automatically identify the relative significance between the latent structure and node features while computing the attention scores.\"\nto be very strong and unlikely to be correct, especially in light of the discussion mentioned above. Also the phrase \"latent structure\" is only used there and not properly defined elsewhere, so it is unclear what the authors are referring to.\n\nI am willing to increase my score if the above were appropriately addressed. Besides this, there are a few other points that could also be quite useful to consider:\n\n- The paper follows the theoretical assumptions of the GIN paper (countable feature-spaces), and it could be interesting to also look at uncountable feature-spaces (eg real numbered features) where many of the theoretical results don't hold. See Corso, Cavalleri et al. (NeurIPS'20) \"Principal Neighbourhood Aggregation for Graph Nets\" for an overview.\n- I'm a bit concerned about the method's scalability. It seems that solving the optimisation task on C may easily invoke quadratic memory even if the underlying graph is sparse? Have the authors managed to reduce this constraint somehow, given that their method successfully ran on Pubmed? Further, some proposed approaches above (e.g. DeepWalk features or using MoNet attention to compute C) could be more scalable alternatives. Could the authors comment on this?\n- Finally, isomorphism-style setups are concerned with distinguishing entire (sub)graphs, and hence might be more directly amenable to graph classification style tasks. The authors may wish to consider some classification tasks (maybe even synthetically constructed) in order to solidify the predictive power argument of their method.\n\n==================== Post-rebuttal update:\n\nI would like to thank the authors for providing a detailed reply, which partially addresses some of my concerns. However, there are several issues in the reply and updated manuscript as provided by the authors:\n\n- The results on OGBN-arXiv are definitely useful, but there is no GAT-based baseline, which corresponds to the JAT's main comparison point. Therefore it is not possible to make strong claims about the method's effectiveness based on the following baseline choice alone.\n- The discussion of alternate structural learning approaches is not sufficiently detailed, and has no empirical backing to the authors' proposal. More experimentation is needed, in my opinion, to fully back the authors' claim of: \"However, these methods may not appropriately determine which part, i.e., structure or node features is more important in the embedding space.\"\n- Lastly, I do not find that the authors have appropriately toned down their claims in the Introduction. Most critically, the authors write: \"The experimental results show that JATs achieve the state-of-the-art performance\". A lookup of the OGBN-arXiv publicly available leaderboard demonstrates that this is not the case: https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv\n\nHaving state-of-the-art is not the most important thing, but it should not be claimed when it's not achieved.\n\nOverall I think the JAT paper has a lot of potential. For now I choose to retain my 'weak reject' recommendation, and hope the authors will take my comments into account for subsequent submissions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: One referee recommends acceptance, while three referees recommend rejection. All referees agree that augmenting GAT with structural information is an interesting direction to explore; however, they raised concerns about the empirical validation of the method, the related work covered, as well as the discussion of insights such as the method's limitations. The rebuttal addresses R2's concerns by better positioning the work w.r.t the literature and by discussing the method's potential limitations. The rebuttal also covers R1 and R3's comments on scalability and complexity of the proposed approach. However, the rebuttal only partially addresses the evaluation concerns of the reviewers. After discussion, all reviewers agree that further work should be devoted to remedy this. I agree with their assessment and hence must reject. In particular, I would strongly recommend following the referees' suggestions and consider incorporating experiments on additional OGB datasets, including a GAT-based comparison to those (and on OGB-arxiv), and eventually toning down their claims.
Decision: Reject