Learning Conjoint Attentions for Graph Neural Nets
Year: 2021

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

heading: 1 Introduction
text: Graph neural networks (GNNs) have shown much success in the learning of graph structured data. Amongst these noteworthy GNNs, attention-based GNNs [33] have drawn increasing interest lately, and have been applied to solve a plethora of real-world problems competently, including node classification [17, 33], image segmentation [35], and social recommendations [30].
Empirical attention mechanisms adopted by GNNs aim to leverage the node features (node embeddings) to compute the normalized correlations between pairs of nodes that are observed to connect. Treating normalized correlations (attention scores/coefficients) as the relative weights between node pairs, attention-based GNN typically performs a weighted sum of node features which are subsequently propagated to higher layers. Compared with other GNNs, especially those that aggregate node features with predefined strategies [1, 17, 19], attention-based GNNs provide a dynamical way for feature aggregation, which enables highly correlated features from neighboring nodes to be propagated in the multi-layer neural architecture. Representations that embed with multi-layer correlated features are consequently learned by attention-based GNNs, and can be used for various downstream tasks.
Though effective, present empirical graph attention has several shortcomings when aggregating node features. First, the computation of attention coefficients is limited solely to the correlations of internal factors, i.e., layer-wise node features within the neural nets. External factors such as cluster structure and higher-order structural similarities, which comprise heterogeneous node-node relevance have remained underexplored to be positively incorporated into the computation of more purposeful attention scores. Second, the empirical attention heavily leaning on the node features may cause
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
over-fitting in the training stage of neural nets [34]. The predictive power of attention-based GNNs is consequently limited.
To overcome the mentioned challenges, in this paper, we propose a class of generic graph attention mechanisms, dubbed here as Conjoint Attentions (CAs). Given CAs, we construct Graph conjoint attention networks (CATs) for different downstream analytical tasks. Different from previous graph attentions, CAs are able to flexibly compute the attention coefficients by not solely relying on layerwise node embeddings, but also allowing the incorporation of purposeful interventions brought by factors external to the neural net, e.g., node cluster embeddings. With this, CATs are able to learn representations from features that are found as significant by diverse criteria, thus increasing the corresponding predictive power. The main contributions of the paper are summarized as follows.
• We propose Conjoint Attentions (CAs) for GNNs. Different from popular graph attentions that rely solely on node features, CAs are able to incorporate heterogeneous learnable factors that can be internal and/or external to the neural net to compute purposeful and more appropriate attention coefficients. The learning capability and hence performance of CA-based GNNs is thereby enhanced with the proposed novel attention mechanisms.
• For the first time, we theoretically analyze the expressive power of graph attention layers considering heterogeneous factors for node feature aggregation, and the discriminant capacity of such attention layers, i.e., CA layers is validated.
• Given CA layers, we build and demonstrate the potential of Graph conjoint attention networks (CATs) for various learning tasks. The proposed CATs are comprehensively investigated on established and extensive benchmarking datasets with comparison studies to a number of state-of-the-art baselines. The notable results obtained are presented to verify and validate the effectiveness of the newly proposed attention mechanisms.

heading: 2 Related works
text: To effectively learn low-dimensional representations in graph structured data, many GNNs have been proposed to date. According to the ways through which GNNs define the layer-wise operators for feature aggregation, GNNs can generally be categorized as spectral or spatial [38].
Spectral GNNs-The layer-wise function for feature aggregation in spectral GNNs is defined according to the spectral representation of the graph. For example, Spectral CNN [3] constructs the convolution layer based on the eigen-decomposition of graph Laplacian in the Fourier domain. However, such layer is computationally demanding. To reduce such computational burden, several approaches adopting the convolution operators which are based on simplified or approximate spectral graph theory have been proposed. First, parameterized filters with smooth coefficients are introduced for Spectral CNN to incorporate spatially localized nodes in the graph [14]. Chebyshev expansion [7] is then introduced to approximate graph Laplacian rather than directly performing eigen-decomposition. Finally, the graph convolution filter is further simplified by only considering first or higher order of connected neighbors [17, 37], so as to make the convolution layer more computationally efficient.
Spatial GNNs-In contrast, spatial GNNs define the convolution operators for feature aggregation by directly making use of local structural properties of the central node. The essence of spatial GNNs consequently lies in designing an appropriate function for aggregating the effect brought by the features of candidate neighbors selected based on appropriate sampling strategy. To achieve this, it sometimes requires to learn a weight matrix that accords to the node degree [8], utilize the power of transition matrix to preserve neighbor importance [1, 4, 18, 19, 42], extract the normalized neighbors [24], or sample a fixed number of neighbors [13, 44].
As representative spatial GNNs, attention-based GNNs (GATs) [12, 33] have shown promising performances on various learning tasks. What makes them effective in graph learning is a result of adopting the attention mechanism, which has been successfully used in machine reading and translation [5, 22], and video processing [40], to compute the node-feature-based attention scores between a central node and its one-hop neighbors (including the central node itself). Then, attentionbased GNNs use the attention scores to obtain a weighted aggregation of node features which are subsequently propagated to the next layer. As a result, those neighbors possessing similar features may then induce greater impact on the center node, and meaningful representations can be inferred by GATs. Having investigated previous efforts to graph neural networks, we observe that the computation
of empirical graph attentions heavily relies on layer-wise node features, while other factors, e.g., structural properties that can be learned outside of neural net, have otherwise been overlooked. This motivates us in proposing novel attention mechanisms in this paper to alleviate the shortcomings of existing attention-based graph neural networks.

heading: 3 Graph conjoint attention networks
text: In this section, we elaborate the proposed Conjoint Attention mechanisms, which are the cornerstones for building layers of novel attention-based graph neural networks. Mathematical preliminaries and notations used in the paper are firstly illustrated. Then, how to construct neural layers utilizing various Conjoint Attention mechanisms are introduced. Given the formulated Conjoint Attention layers, we finally construct the Graph conjoint attention networks (CATs).

heading: 3.1 Notations and preliminaries
text: Throughout this paper, we assume a graphG = {V,E} containingN nodes, |E| edges, and C classes (C N ) to which the nodes belong, where V and E respectively represent the node and edge set. We use A ∈ {0, 1}N×N and X ∈ RN×D to represent graph adjacency matrix and input node feature matrix, respectively. Ni denotes the union of node i and its one-hop neighbors. Wl and {hli}i=1,...N denote the weight matrix and features (embeddings) of node i at lth layer of CATs, respectively, and h0 is set to be the input feature, i.e., X. For the nodes in Ni, their possible feature vectors form a multiset Mi = (Si, µi), where Si = {s1, ...sn} is the ground set of Mi which contains the distinct elements existing in Mi, and µi : Si → N? is the multiplicity function indicating the frequency of occurrence of each distinct s in Mi.

heading: 3.2 Structural interventions for Conjoint Attentions
text: As aforementioned, the proposed Conjoint Attentions are able to make use of factors that are either internal or external to the neural net to compute new attention coefficients. Internal factors refer the layer-wise node embeddings in the GNN. While, the external factors include various parameters that can be learned outside of the graph neural net and can potentially be used to compute the attention scores. Taking the cue from cognitive science, where contextual interventions have been identified as effective external factors that may improve the attention and cognitive abilities [16], here we refer these external structural properties as structural interventions henceforth for the computing of attention coefficients. Next, we propose a simple but effective way for CAs to capture diverse structural interventions external to the GNNs. Let Cij be some structural intervention between ith and jth node in the graph. It can be obtained with the following generic generating function:
Cij = arg min φ(C)ij Ψ(φ(C)ij ,Yij), (1)
where Ψ(·) represents a distance function and φ(·) stands for an operator transforming C to the same dimensionality of Y. Given the generic generating function in Eq. (1), it is known that many effective paradigms for learning latent features can be used for the subsequent computation of Conjoint Attentions, if the prior feature matrix Y is appropriately provided. Taking A as the prior feature matrix, in this paper, we consider two generation processes that can capture two unique forms of structural interventions. Let Ψ(·) be the euclidean distance, when φ(C)ij . = VVTij , we have:
Cij = arg min VVTij
(Aij −VVTij)2, (2)
where we use an N -by-C matrix V to approximate C to reduce the computational burden. As it shows in Eq. (2), Cij attempts to acquire the structural correlation pertaining to node cluster embeddings, based on matrix factorization (MF). A higher Cij learned by Eq. (2) means a pair of nodes are very likely to belong to the same cluster. If φ(C)ij . = ∑ jVV T ijAij , we have:
Cij = arg min VVTij (Aij − ∑ j VVTijAij) 2. (3)
As shown in Eq. (3), Cij is the coefficient of self-expressiveness [10] (SC) which may describe the global relation between node i and j. A higher Cij inferred by Eq. (3) means the global structure
of node i can be better represented by that of node j, and consequently this pair of nodes are more structurally correlated. It is known that both aforementioned properties have not been considered previously by empirical graph attention mechanisms. We believe considering either of them as structural interventions for the Conjoint Attentions could lead to better attention scores for feature aggregation. Note that other types of C may also be feasible for the proposed attention mechanisms, as long as they are able to capture meaningful property which is not already possessed within the node embeddings of the GNN.

heading: 3.3 Conjoint Attention layer
text: Having obtained a proper C, we present next the Conjoint Attention layer, which is the core module for building CATs and will be used in our experimental study. Different from the attention layers considered in other GNNs, the attention layer proposed here adopts novel attention mechanisms, i.e., Conjoint Attentions. It is known that empirical graph attentions solely concern the correlations pertaining to the internal factors, e.g., node embeddings locating in each layer of the neural net. How those diverse forms of relevance, e.g., the correlation in terms of node cluster embeddings and self-expressiveness may affect the representation learning is therefore yet to be investigated in previous works. Besides utilizing the correlations pertaining to node embeddings, the proposed Conjoint Attentions now take into additional considerations the structural interventions brought by diverse node-node relevance, which is learned outside of the neural network. As a result, each Conjoint Attention layer may pay more attentions to the similar embeddings of neighbors, as well as to the ones that share other forms of relevance with the central node. Node representations possessing heterogeneous forms of relevance can now be learned by the CATs.
Given a set of node features {hli}i=1,...N , each hli ∈ RD l
, the Conjoint Attention layer maps them into Dl+1 dimensional space {hl+1i }i=1,...N , according to the correlations of node features and aforementioned structural interventions. The contextual correlation between two connected nodes, say vi and vj is firstly obtained. To do so, we directly adopt the feature-based attention mechanism considered by existing graph attention networks (GAT) [33]:
fij = exp(LeakyReLU(ãT (Wlhli ‖Wlhlj)))∑
k∈Ni exp(LeakyReLU(ã T (Wlhli ‖Wlhlk)))
, (4)
where ã ∈ R2Dl+1 is a vector of parameters of the feedforward layer, ‖ stands for the concatenation function, and Wl isDl+1×Dl parameter matrix for feature mapping. Given Eq. (4), the proposed CA layer captures the feature correlations between connected nodes (first-order neighbors) by computing the similarities w.r.t. node features mapped to next layer.
As mentioned, determining the attention scores solely based on node features internal to a GNN may result in overlooking other important factors. To overcome this issue, the proposed CA layer attempts to learn the structural interventions as described in Section 3.2, and presents the additional
new information for computing the attention scores. Given any learnable parameter Cij (structural intervention) between two nodes, CA layer additionally obtains a supplementary correlation as follows:
sij = exp (Cij)∑
k∈Ni exp (Cik) . (5)
Given fij and sij , we propose two different strategies to compute the Conjoint Attention scores, aiming at allowing CATs to depend on the structural intervention at different levels. The first mechanism is referred here as Implicit direction. It aims at computing the attention scores whose relative significance between structural and feature correlations can be automatically acquired. To do so, each CA layer introduces two learnable parameters, gf and gs, to determine the relative significance between feature and structural correlations and they can be obtained as follows:
rf = exp (gf )
exp (gs) + exp (gf ) , rs =
exp (gs)
exp (gs) + exp (gf ) , (6)
where rs or rf represents the normalized significance related to different types of correlations. Given them, CAT then computes the attention score based on Implicit direction strategy:
αij = rf · fij + rs · sij∑
k∈Ni [rf · fik + rs · sik] = rf · fij + rs · sij . (7)
Given the attention mechanism shown in Eq. (7), αij attempts to capture the weighted mean attention in terms of the various node-node correlations, which are the ones internal or external to the GNN. Compared with the attention mechanism solely based on features of one-hop neighbors, αij computed by Eq. (7) may be adapted according to the implicit impact brought by different structural interventions, e.g., correlations pertaining to node cluster embeddings and self-expressiveness coefficients. Moreover, the relative significance r can also be automatically inferred through the back propagation process. More smooth and appropriate attention scores can thereby be computed by the CA layer for learning meaningful representations.
To enhance the impact of structural intervention, the CA layer has another strategy, named here as Explicit direction, to compute attention scores between neighbors. Given fij and sij , the attention scores obtained via the Explicit direction strategy is defined as follows:
αij = fij · sij∑
k∈Ni fik · sik . (8)
Compared with Eq. (7), sij explicitly influences the magnitude of fij , so that those node pairs which are irrelevant in terms of Cij will never be assigned with high attention weights. Based on Explicit direction strategy, the CA layer becomes more structurally dependent when performing message passing to the higher layers in the neural architecture.
Having obtained the Conjoint Attention scores, the CA layer is now able to compute a linear combination of features corresponding to each node and its neighbors as output, which will be either propagated to the higher layer, or be used as the final representations for subsequent learning tasks. The described output features can be computed as follows:
hl+1i = (αii + · 1
|Ni| )Wlhli + ∑ j∈Ni,j 6=i αijW lhlj , (9)
where ∈ (0, 1) is a learnable parameter that improves the expressive capability of the proposed CA layer.

heading: 3.4 Construction of Graph conjoint attention networks (CATs)
text: In Fig. 1, the Conjoint Attention layers that use the attention mechanisms proposed in this paper are graphically illustrated. We are now able to construct Graph conjoint attention networks (CATs) using a particular number of CA layers proposed. In practice, we also adopt the multi-head attention strategy [32] to stabilize the learning process. CATs may either concatenate the node features from multiple hidden layers as the input for next layer, or compute the average of node features obtained by multiple units of output layers as the final node representations. For the details on implementing multi-head attention in graph neural networks, the reader is referred to [33].

heading: 4 Theoretical analysis
text: Study on the expressive power of various GNNs has drawn much attention in the recent. It concerns whether a given GNN can distinguish different structures where vertices possessing various vectorized features. It has been found that what the neighborhood aggregation functions of all message-passing GNNs aim at are analogous to the 1-dimensional Weisfeiler-Lehman test (1-WL test), which is injective and iteratively operated in the Weisfeiler-Lehman algorithm [36, 41, 45], does. As a result, all message-passing GNNs are as most powerful as the 1-WL test [41]. The theoretical validation of the expressive power of a given GNN thereby lies in whether those adopted aggreation/readout functions are homogeneous to the 1-WL test.
One may naturally be interested in whether the expressive power of the proposed CAT layers is as powerful as the 1-WL test, which can distinguish all different graph structures. To do so, we firstly show that neighborhood aggregation function (Eq. (9)) without the term for improving expressive capability (i.e., · 1|Ni|Wh l i in Eq. (9)) still fails to discriminate some graph structures possessing certain topological properties. Then, by integrating the term of improving expressive capability, all the proposed CA layers are able to distinguish all those graph structures that cannot be discriminated previously.
For the function of neighborhood aggregation solely utilizing the strategy shown in Eq. (7), we have the following theorem pointing out the conditions under which the aggregation function fails to distinguish different structures.
Theorem 1 Assume the feature space X is countable and the aggregation function using the weights computed by Eq. (7) is represented as h(c,X) = ∑ x∈X αcxg(x), where c is the feature of center node, X ∈ X is a multiset containing the feature vectors from nodes in Ni, g(·) is a function for mapping input feature X , and αcx is the weight between g(c) and g(x). For all g and the strategy in Eq. (7), h(c1, X1) = h(c2, X2) if and only if c1 = c2, X1 = {S, µ1}, X2 = {S, µ2}, and∑ y=x,y∈X1 fc1y − ∑ y=x,y∈X2 fc2y = q[ ∑ y=x,y∈X2 sc2y − ∑ y=x,y∈X1 sc1y], for q = rs rf
and x ∈ S. In other words, h will map different multisets into the same embedding iff the multisets have same central node feature, same underlying set, and the difference in feature-based scores is proportional ( rsrf ) to the opposite of that in the weights corresponding to the structural interventions.
We leave the proof of all the theorems and corollaries in the appendix. For the aggregation function utilizing the strategy shown in Eq. (8), we have the following theorem indicating the structures which cannot be correctly distinguished.
Theorem 2 Under the same assumptions shown in Theorem 1, for all g and the strategy in Eq. (8), h(c1, X1) = h(c2, X2) if and only if c1 = c2, X1 = {S, µ1}, X2 = {S, µ2}, and q · ∑ y=x,y∈X1 φ(Cc1x) = ∑ y=x,y∈X2 φ(Cc2y), for q > 0 and x ∈ S, where φ(·) is an function for mapping values to R+. In other words, h will map different multisets into the same embedding iff the multisets have same central node feature, same node features whose corresponding mapped structural interventions are proportional.
Theorems 1 and 2 indicate that the CA layers may still fail to distinguish some structures, if they exclude the improving term shown in Eq. (9). However, GNNs utilizing Eqs. (7) or (8) can still be more expressively powerful than classical GATs. As node features and structural interventions are heterogeneous, intuitively, structures satisfying the stated conditions should be infrequent. This may well explain why those GNNs concerning including external factors, e.g., some structural properties into the computation of attention coefficients may experimentally perform better than GATs. However, when distinct multisets with corresponding properties meet the conditions mentioned in Theorems 1 and 2, the attention mechanisms solely based on Eqs. (7) or (8) cannot correctly distinguish such multisets. Thus, GNNs only utilizing Eqs. (7) or (8) as the feature aggregation function fail to reach the upper bound of expressive power of all message-passing GNNs, i.e., the 1-WL test.
However, we are able to readily improve the expressive power of CATs to meet the condition of the 1-WL test by slightly modifying the aggregation function as Eq. (9) shows. Then, the newly obtained Conjoint Attention scores can be used to aggregate the node features passed to the higher layers. Next, we prove that the proposed Conjoint Attention mechanisms (Eqs. (7)-(9)) reach the upper bound of message-passing GNNs via showing they can distinguish those structures possessing the properties mentioned in Theorems 1 and 2.
Corollary 1 Let T be the attention-based aggregator shown in Eq. (9) that considers one of the strategies in Eq. (7) or (8) and operates on a multiset H ∈ H, where H is a node feature space mapped from the countable input feature space X . A H exists so that utilizing attention-based aggregator shown in Eq. (9), T can distinguish all different multisets in aggregation that it previously cannot discriminate.
Based on the performed analysis, the expressive power of CATs is theoretically stronger than state-ofthe-art attention-based GNNs, e.g., GATs [33].

heading: 5 Experiments and analysis
text: In this section, we evaluate the proposed Graph conjoint attention networks against a variety of state-of-the-art and popular baselines, on widely used network datasets.

heading: 5.1 Experimental set-up
text: Baselines for comparison-To validate the effectiveness of the proposed CATs, we compare them with a number of state-of-the-art baselines, including Arma filter GNN (ARMA) [2], Simplified graph convolutional Networks (SGC) [37], Personalized Pagerank GNN (APPNP) [18], Graph attention networks (GAT) [33], Jumping knowledge networks (JKNet) [42], Graph convolutional networks (GCN) [17], GraphSAGE [13], Mixture model CNN (MoNet) [23], and Graph isomorphism network (GIN) [41]. As GAT can alternatively consider graph structure by augmenting original node features (i.e., X) with structural properties, we use prevalent methods for network embedding, including k-eigenvectors of graph Laplacian (k-Lap) [26], Deepwalk [25], and Matrix factorization-based network embedding (NetMF) [26] to learn structural node representations and concatenate them with X as the input feature of GAT. Thus, three variants of GAT, i.e., GAT-k-Lap, GAT-Deep, and GAT-NetMF are additionally constructed as compared baselines. Based on the experimental results previously reported, these baselines may represent the most advanced techniques for learning in graph structured data.
Testing datasets-Five widely-used network datasets, which are Cora, Cite, Pubmed [21, 28], CoauthorCS [29], and OGB-Arxiv [15], are used in our experiments. Cora, Cite, and Pubmed are three classical network datasets for validating the effectiveness of GNNs. However, it is recently found that these three datasets sometimes may not effectively validate the predictive power of different graph learning approaches, due to the relatively small data size and data leakage [15, 29]. Thus, more massive datasets having better data quality have been proposed to evaluate the performance of different approaches [9, 15]. In our experiment, we additionally use CoauthorCS and OGB-Arxiv as testing datasets. The details of all benchmarking sets can be checked in the appendix.
Evaluation and experimental settings-Two learning tasks, semi-supervised node classification and semi-supervised node clustering are considered in our experiments. For the training paradigms of both two learning tasks, we closely follow the experimental scenarios established in the related works [15, 17, 33, 43]. For the testing phase of different approaches, we use the test splits that are publicly available for classification tasks, and all nodes for clustering tasks. The effectiveness of all methods is validated through evaluating the classified nodes using Accuracy. In the training stage, we construct the two-layer network structure (i.e., one hidden layer possessed) for all the baselines and different versions of CATs. In each set of testing data, all approaches are run ten times to obtain the statistically steady performance. As for other details related to experimental settings, we leave them in the appendix.

heading: 5.2 Results on node classification
text: The results on semi-supervised node classification are summarized in Table 1. As the table shows, CATs utilizing different attention strategies generally perform better than any other baseline in all the testing datasets. Specifically, CAT utilizing Implicit direction (CAT-I-MF and CAT-I-SC) performs better than all the compared baselines in all the five datasets. CAT utilizing Explicit direction (CATE-MF and CAT-E-SC) is better than other compared baselines in four datasets out of five, except the case of CoauthorCS. In that dataset, CAT-E ranks the second-best when compared with other baselines.

heading: 5.3 Results on node clustering
text: Node clustering can be more challenging as all the nodes containing various potential structures in the graph are used in the testing phase. The results obtained show that CATs still performs robustly when compared with other baselines on this challenging task. As Table 2 shows, the Implicit direction strategy utilized by CAT can still ensure the proposed neural architecture to outperform other compared baselines in all the datasets. As for CAT utilizing Explicit direction, it ranks best on three datasets out of five. While on the remaining two datasets, Pubmed and CoauthorCS, the performance of CAT-E is competitive to the best. Based on the robust performance shown in Tables 1 and 2, CAT is observed to be one of the most effective GNNs for various graph learning tasks.

heading: 5.4 Ablation study
text: To further investigate whether the proposed CA mechanisms are effective in improving the predictive power of CATs, we compared the performance of CAs with that obtained by attention mechanisms considering various factors. Specifically, we let GAT computes attention coefficients using either
structural interventions, i.e., node-node correlations pertaining to node cluster embeddings (MF in Eq. (2)) and self-representation coefficients (SC in Eq. (3)), or node features (Eq.(4), F). Then GAT utilizing different attention strategies is used to perform node classification and clustering tasks on all the testing datasets. The performance comparisons between CATs and GAT utilizing the aforementioned attentions have been summarized in Fig. 2. As the figure shows, on both classification and clustering tasks, the proposed CA mechanisms perform statistically better than other attention strategies utilized by GAT. It is also observed that the consideration of structural attentions (SC and MF) may also improve the performance of attention-based GNNs. Such results thus experimentally agree with and validates our theoretical analysis in Section 4.

heading: 6 Discussions
text: In this section, some further discussions that may provide better understandings to the proposed attention mechanisms are presented.

heading: 6.1 Comparisons between CATs and GATs with augmented node features
text: Besides the proposed Conjoint Attention mechanisms, directly concatenating input node features and structural embeddings [11, 25–27, 31] is another effective way to make current GNNs more structural bias. In our experiments, it is shown that the learning performance have improved in most datasets when GAT uses the concatenation of original node features and various structural embeddings. However, in most datasets, such performance improvement is not as significant as that obtained by CATs. Different from directly concatenating the original node input features and structural embeddings for learning node representations, CATs provide a smooth means to compute attention coefficients that jointly consider the diverse relevance regarding to both layer-wise node embeddings and external factors, like the structural interventions pertaining to the correlations generated by the node cluster embeddings considered in this paper. As a result, CATs can learn node representations from those nodes that are heterogeneously relevant and attain notable learning performance on all the testing datasets.

heading: 6.2 Potential limitations of the proposed approach
text: Although the proposed Conjoint Attentions are very effective in improving the learning performance of attention-based GNNs, they may also have possible shortcomings. First, the predictive power of the proposed CATs may be determined by the quality of the structural interventions. As the proposed Conjoint Attentions attempt to compute attention scores considering heterogeneous factors, their performance might be negatively affected by those contaminated ones. However, some potential methods may mitigate the side-effect brought by possible false/noisy external factors. One is to utilize adversarial learning modules [20] to alleviate the model vulnerability to external contamination. The other method is to consider learning effective factors from multiple data sources (i.e., multi-view). In previous works [39], multi-view learning has shown to be effective even when some view of data is contaminated.
Second, both space and time complexity of the proposed Conjoint Attentions can be higher than the empirical attention-based GNNs, e.g., GAT. Thus, how to select a simple but effective strategy for capturing the interventions is crucial for the proposed Conjoint Attentions. In our experiments, we recorded the memory consumption of CATs when performing different learning tasks in all the testing datasets and the corresponding results are provided in the appendix. We find that some simple learning paradigms, e.g., matrix factorization (Eq. (2) in the manuscript) can ensure CATs to outperform other baselines, while the space and time complexity does not increase much when compared with GATs. As for the SC strategy, its space complexity is relatively high, if it uses a single-batch optimization method. Therefore, more efficient optimization methods should be considered when CATs use SC to learn Cij .
Third, the expressive power of the proposed Conjoint Attention-based GNNs reaches the upper bound of the 1-WL test in the countable feature space, but such discriminative capacity may not be always held by CATs in the uncountable feature space. Previous works have proved that the expressive power of a simplex function for feature aggregation in a GNN can surely reach the upper bound of the 1-WL test only in countable feature space, multiple categories of functions for feature aggregations are required to maintain the expressive power of a GNN when the feature space is uncountable [6]. As all Conjoint Attentions belong to one category of function, i.e., mean aggregator, in this paper, we perform the theoretical analysis on the expressive power of CATs assuming the feature space is countable. Ideally, the expressive power of CATs can be further improved in uncountable space, if the proposed Conjoint Attentions are appropriately combined with other types of feature aggregators.

heading: 7 Conclusion
text: In this paper, we have proposed a class of novel attention strategies, known as Conjoint Attentions (CAs) to construct Graph conjoint attention networks (CATs). Different from empirical graph attentions, CAs offer flexible incorporation of both layer-wise node features and structural interventions that can be learned outside of the GNN to compute appropriate weights for feature aggregation. Besides, the expressive power of CATs is theoretically validated to reach the upper bound of all message-passing GNNs. The proposed CATs have been compared with a number of prevalent approaches in different learning tasks. The obtained notable results verify the CATs’ model effectiveness. In future, we will further improve the effectiveness of CATs in the following ways. First, besides node cluster embeddings and self-expressiveness, more structural interventions will be explored to compute more compelling attention coefficients for node representation learning. Second, appropriate adversarial strategies to reduce model vulnerability to contaminated factors that are used for computing attention scores will be considered. Last but not the least, the proposed Conjoint Attentions will be extended to learn node representations in multi-view context and heterogeneous graph data.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their constructive comments and suggestions. This work is supported in part by the Data Science & Artificial Intelligence Research Center (DSAIR), Nanyang Technological University, and in part by Agency for Science, Technology and Research (A*STAR).

Review summaries:
This paper proposes a new technique for augmenting Graph Attentions with information other than node feature embedding in GNNs. The Conjoint Attentions (CAs) proposed in this paper parametrize the similarity hints between nodes, such as adjacency matrix, in the form of matrix factorization, and modify the attention weight \alpha calculated by ordinary graph attention. This paper shows that CAs (with additional learnable parameters to the self-link terms) have theoretically higher expressive power than existing GNNs such as GAT. Experimental results show that the proposed CAs have higher generalization performance than several existing GNNs on five representative datasets. 

This paper aims to establish a new type of attention mechanism for GNNs. Authors propose an attention mechanism which can utilize structural interactions between nodes instead of focusing only on given node features. Given the new attention authors use it create Conjoint Graph Attention Networks to solve node classification and node clustering tasks.   Authors first calculate an external ( w.r.t GNNs ) information matrix and propose two forms in this paper based on Matrix Factorization and Coefficient of Self-Expresiveness. The *Conjoint Attention* layer then calculates two types of attention, using external information matrix and using the node features ( any attention mechanism can be used here, authors use attention mechanism similar to GAT ). Two strategies are used to combine the different attentions calculated in previous step, Implicit and Explicit. Weighted aggregation is used to get the final node embeddings, with an addition of a correction factor.   Experimentation is conducted of several publicly available datasets, and comparisons to several baselines are included which gives a good idea of the expressive power of the proposed attention mechanism. 

The authors propose Graph ConJoint Attention Networks (CATs) as a mechanism for explicitly incorporating structural information in the GATs attention mechanism.  CATs separately learn an "enlightenment" attention matrix which exploits structural correlations between the vertices (based on the adjacency matrix).  Such 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.