Deep Graph Attention Networks

The graph is a useful data structure to represent various objects in the real world. For example, accounts and links in social networks correspond to nodes and edges in graphs, respectively, and relationships in the networks are represented as graphs. Atoms and chemical bonds in molecules also correspond to nodes and edges in graphs, respectively, and the molecules are thus represented as graphs. Various other objects, such as hyperlink structures and function calls in computer programs, can also be represented by graphs. Because various objects can be stored as graph data, technologies for analyzing such data have been attracting a great deal of attention in recent years [9, 23, 19].

The graph neural network (GNN) [23] is a representative deep learning method for graph data. GNNs convolve features of neighboring nodes of a node $v$ to the representation of $v$. GNNs with $L$ layers repeat this convolution $L$ times, and obtain the representation $\bm{h}_{v}$ of $v$. Once each node is represented in vector form, various conventional machine learning methods such as classification, clustering, and regression can be applied to the graph data, including for node classification, node clustering, and link prediction.

Representative GNNs include the graph convolutional network (GCN) [9] and graph attention network (GAT) [19]. Figure 1 shows the difference between convolutions of GCN and GAT; the features of nodes in the darker blue background greatly affect the representation of $v$. For each node $v$, GCN uniformly convolves the features with $l$ steps from $v$ to the representation of $v$, whereas GAT non-uniformly convolves the features to the representation of $v$ using the attention coefficient. Thus, GCN convolves the features of red nodes in Fig. 1 to the representation of $v$, whereas GAT does not always convolve the features to the representation of $v$, which results in different representations of the structure around $v$ learned by GCNs and GATs.

Most GNNs, including GCNs and GATs, have a common drawback called over-smoothing [13, 15, 2, 29], which is a phenomenon in which the representations of nodes belonging to different classes are similar to each other when the number of layers is increased. This results in degradation of GNN performance. For this reason, low-layer GCNs or GATs with 2-3 layers are often used in actual operations. However, for some graph datasets, even a deep GAT can provide high performance, so we must tune the number of layers $L$ by starting with a low-layer GAT and gradually increasing $L$. This tuning requires considerable time. Therefore, a methodology that can construct a deep GAT for many datasets without spending time tuning $L$ would be useful.

To achieve this, this paper [8] proposes a method for predicting which class each node belongs to at each layer in a deep GAT, in which the prediction error at each layer is incorporated into the loss function. On the basis of the prediction, if a node $v$ has neighbors that belong to the same class as $v$, only features of the neighbors are convolved into the representation of $v$. Unlike the case of over-smoothing, the likelihood that features of nodes belonging to a different class from $v$ are convolved into $v$ is small, and thus the representations of nodes belonging to different classes are not similar to each other; therefore, over-smoothing can be avoided.

The contributions of this paper are summarized as follows:

• •

  First, our proposed method, called DeepGAT, achieves a 15-layer GAT with the same level of performance as a 2-layer GAT. Instead of starting with a small $L$ and gradually increasing its value, the DeepGAT with 15 layers can be constructed without tuning $L$.

• •

  Second, we mathematically show why DeepGAT can avoid over-smoothing, on the basis of the reproductive property of the probability distribution (see Lemma 2). We also show mathematically that the overlap in distributions of representations of nodes belonging to different classes is small, and we demonstrate that this is also true for benchmark datasets.

A graph whose nodes have features is represented as $G=(V,E,X)$, where $V=\{1,2,\ldots,n\}$ is a set of nodes, $E\subseteq V\times V$ is a set of edges, and $X=\{\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}\}\in\mathbb{R}^{d\times n}$ is a set of feature vectors. We define a neighborhood of vertex $v$ as $N_{v}=\{u\mid(v,u)\in E\}\cup\{v\}$. Each node belongs to one of two classes $C=\{0,1\}$¹¹1In this paper, we address the binary classification of nodes, although the proposed method can be extended to multi-class node classification, multi-label node classification, and graph classification., and we denote nodes belonging to the class $c\in C$ as $V_{c}\subset V$. In addition, we assume that feature $\bm{x}_{v}$ of node $v\in V_{c}$ has the following properties: $\mathcal{N}(\bm{\mu}_{c},\Sigma_{c})$.

We call a sequence of edges $\langle(v_{1},v^{\prime}_{1}),(v_{2},v^{\prime}_{2}),\ldots,(v_{l},v^{\prime}_{l})\rangle$ satisfying $v^{\prime}_{i}=v_{i+1}$ a path, and $l$ the length of the path. Paths in this paper are not always simple, and we allow the path to satisfy $v_{i}=v^{\prime}_{i}$. We denote a set of paths of length $l$ from node $v$ to node $u$ as $P_{v\sim u}^{l}$. In addition, we denote a vector representing the numbers of paths of length $l$ from $v$ as $\bm{\pi}_{v}^{l}=\sum_{u\in V}|P_{v\sim u}^{l}|\bm{1}_{n,u}=(|P_{v\sim 1}^{l}|,|P_{v\sim 2}^{l}|,\ldots,|P_{v\sim n}^{l}|)^{T}$, where $\bm{1}_{n,u}$ is the $n$-dimensional one-hot vector whose $u$-th element is 1. By using these notations, we define $\bm{\pi}_{v,c}^{l}=\sum_{u\in V_{c}}|P_{v\sim u}^{l}|\bm{1}_{n,u}$ and $P_{v}^{l}=\bigcup_{c\in C}\bigcup_{u\in V_{c}}P_{v\sim u}^{l}=\bigcup_{c\in C}P_{v,c}^{l}$.

Given a graph $G$ and the ground-truth class labels $C^{\prime}$ for nodes $V^{\prime}\subset V$ as input, the problem addressed in this paper is the accurate prediction of class labels for nodes $V\setminus V^{\prime}$ via learning node representations for $V$ from $G$ and $C^{\prime}$.

We will now discuss GAT, which is a type of GNN in which node representations are obtained from a graph. For each node $v$ in a graph, GAT convolves the features of nodes $N_{v}$ to the feature of $v$. The convolution of GAT consists of Aggregate and Combine, as shown below:

where $W^{l}$ is the learnable matrix and $\sigma$ is the activation function. In addition, $\alpha_{vu}$ is the attention coefficient computed from $\bm{h}_{v}^{l-1}$ and $\bm{h}_{u}^{l-1}$. Starting from $\bm{h}_{v}^{0}=\bm{x}_{v}$, GAT repeats this convolution $L$ times and then outputs $\bm{h}_{v}^{L}$ as the representation for node $v$ ²²2Although GATs usually use multi-head attention, we discuss GATs with single-head attention until Section 4 of this paper. The software used in Section 5 is implemented with $K$ multi-head attention..

GAT is an extension of GCN. $\alpha^{l}_{vu}$ in GCN does not depend on $\bm{h}_{v}^{l}$ and $\bm{h}_{u}^{l}$, and $\alpha^{l}_{vu}$ is $\frac{1}{|N_{v}|}$. In contrast, GAT aggregates features of neighboring nodes with similar features to node $v$ into a representation of $v$. Thus, it does not convolve uniform features of nodes with $l$ steps from $v$, but instead convolves while selecting features of nodes in particular directions, as shown in Fig. 1. The following equations are used for computing attention coefficients between two vectors $\bm{q}$ and $\bm{k}$:

where $\bm{w}$ is a learnable vector, $dim$ is a function to obtain the number of dimensions of a vector, $\langle\cdot,\cdot\rangle$ is a dot product, and $||$ is an operation to concatenate two vectors. Using one of these attention functions, $\alpha_{vu}$ is computed by

GAT has been actively applied to various methods. For example, the gated attention network [26] calculates importance values of $K$ multi-heads. Heterogenous GANs [21] can learn heterogeneous graphs with GAT, and the signed GAN [7] combines directed code networks and GAT. The relational GAN [27] adds new attention networks that can learn the dependencies between emotional polarity and opinion words, called aspects, in sentences.

One of the major challenges for GNNs, including GATs, is over-smoothing. Over-smoothing is a phenomenon in which node representations $\bm{h}_{v}^{L}=\bm{h}_{v}$ are similar to each other when the number of layers $L$ in the GNN is increased, resulting in a decrease in classification accuracy. Yajima and Inokuchi proved with the following lemma that the distribution followed by $\bm{h}_{v}^{l}$ in a GCN is normal, using the reproductive property of probability distributions.

According to Lemma 1, the mean $\bm{\mu}_{L}$ of the distribution followed by $\bm{h}_{v}=\bm{h}_{v}^{L}$ to be used for classification is $\frac{|P_{v,0}^{L}|\bm{\mu}_{0}+|P_{v,1}^{L}|\bm{\mu}_{1}}{|P_{v,0}^{L}|+|P_{v,1}^{L}|}W_{1\sim L}$. For large $L$, because the ratio $\frac{|P_{v,0}^{L}|}{|P_{v,1}^{L}|}$ approaches the class ratio $\frac{|V_{0}|}{|V_{1}|}$, $\bm{\mu}_{L}$ internally divides $\bm{\mu}_{0}$ and $\bm{\mu}_{1}$ in the ratio. Because the representations of nodes belonging to the two classes follow a distribution with an identical mean $\bm{\mu}_{L}$ for large $L$, they are similar to each other. This also holds true for GATs. Therefore, GCNs and GATs often have two or three layers.

The objective of this paper is to extend GAT, i.e., to derive a multiple-layer GAT to achieve high classification accuracy while preventing over-smoothing, by taking advantage of the properties of the representations shown in Lemma 1.

According to the article [11], there are three main approaches to reduce over-smoothing: Normalization, Residual connection, and Change of GNN Dynamics. Typical methods of the first approach are DropEdge [16] and PairNorm [28]. DropEdge randomly removes a certain number of edges from the input graph at each training epoch. PairNorm transfoms input features in prepossessing as follows.

where $s>0$ is the hyper-parameter. In the second approach, the residual connection [6, 12] allows the input to bypass one or more layers and be added directly to the output of a later layer. One of implementations is represented as $\bm{x}_{v}^{l}=\bm{x}_{v}^{l-1}+\sigma(W^{l}\bm{a}_{v}^{l})$. This technique helps mitigate the vanishing gradient problem, enabling the training of deeper networks. GCNII [3] using residual connection demonstrated that the over-smoothing is reduced in 64-layer GNNs. The third approach qualitatively changes the dynamics of message passing propagation. For example, in Gradient Gating (G²) [10], local gradients due to differences between features are harnessed to further modulate convolution as follows.

where $p\leq 0$ is the hyper-parameter and $\odot$ is the Hadamard product.

GNNs tend to suffer from over-smoothing leading to performance degradation. Therefore, this paper introduced DeepGAT for predicting the class to which network nodes belong in a deep GAT. It avoids over-smoothing in a GAT by ensuring that nodes in different classes are not similar at each layer. Using DeepGAT to predict class labels, a 15-layer network could be constructed without the need to tune the number of layers. DeepGAT prevented over-smoothing and achieved a 15-layer GAT with similar performance to a 2-layer GAT, as indicated by the similar attention coefficients. DeepGAT enables the training of a large network to acquire similar attention coefficients to a network with few layers. It avoids the over-smoothing problem and obviates the need to tune the number of layers, thus saving time and enhancing GNN performance.