Graph Transformer Networks

Introduction

In recent years, Graph Neural Networks (GNNs) have been widely adopted in various tasks over graphs, such as graph classification , link prediction and node classification . The representation learnt by GNNs has been proven to be effective in achieving state-of-the-art performance in a variety of graph datasets such as social networks , citation networks , functional structure of brains , recommender systems . The underlying graph structure is utilized by GNNs to operate convolution directly on graphs by passing node features to neighbors, or perform convolution in the spectral domain using the Fourier basis of a given graph, i.e., eigenfunctions of the Laplacian operator .

However, one limitation of most GNNs is that they assume the graph structure to operate GNNs on is fixed and homogeneous. Since the graph convolutions discussed above are determined by the fixed graph structure, a noisy graph with missing/spurious connections results in ineffective convolution with wrong neighbors on the graph. In addition, in some applications, constructing a graph to operate GNNs is not trivial. For example, a citation network has multiple types of nodes (e.g., authors, papers, conferences) and edges defined by their relations (e.g., author-paper, paper-conference), and it is called a heterogeneous graph. A naïve approach is to ignore the node/edge types and treat them as in a homogeneous graph (a standard graph with one type of nodes and edges). This, apparently, is suboptimal since models cannot exploit the type information. A more recent remedy is to manually design meta-paths, which are paths connected with heterogeneous edges, and transform a heterogeneous graph into a homogeneous graph defined by the meta-paths. Then conventional GNNs can operate on the transformed homogeneous graphs . This is a two-stage approach and requires hand-crafted meta-paths for each problem. The accuracy of downstream analysis can be significantly affected by the choice of these meta-paths.

Here, we develop Graph Transformer Network (GTN) that learns to transform a heterogeneous input graph into useful meta-path graphs for each task and learn node representation on the graphs in an end-to-end fashion. GTNs can be viewed as a graph analogue of Spatial Transformer Networks which explicitly learn spatial transformations of input images or features. The main challenge to transform a heterogeneous graph into new graph structure defined by meta-paths is that meta-paths may have an arbitrary length and edge types. For example, author classification in citation networks may benefit from meta-paths which are Author-Paper-Author (APA) or Author-Paper-Conference-Paper-Author (APCPA). Also, the citation networks are directed graphs where relatively less graph neural networks can operate on. In order to address the challenges, we require a model that generates new graph structures based on composite relations connected with softly chosen edge types in a heterogeneous graph and learns node representations via convolution on the learnt graph structures for a given problem.

Our contributions are as follows: (i) We propose a novel framework Graph Transformer Networks, to learn a new graph structure which involves identifying useful meta-paths and multi-hop connections for learning effective node representation on graphs. (ii) The graph generation is interpretable and the model is able to provide insight on effective meta-paths for prediction. (iii) We prove the effectiveness of node representation learnt by Graph Transformer Networks resulting in the best performance against state-of-the-art methods that additionally use domain knowledge in all three benchmark node classification on heterogeneous graphs.

Related Works

Graph Neural Networks. In recent years, many classes of GNNs have been developed for a wide range of tasks. They are categorized into two approaches: spectral and non-spectral methods . Based on spectral graph theory, Bruna et al. proposed a way to perform convolution in the spectral domain using the Fourier basis of a given graph. Kipf et al. simplified GNNs using the first-order approximation of the spectral graph convolution. On the other hand, non-spectral approaches define convolution operations directly on the graph, utilizing spatially close neighbors. For instance, Veličković et al. applies different weight matrices for nodes with different degrees and Hamilton et al. has proposed learnable aggregator functions which summarize neighbors’ information for graph representation learning.

Node classification with GNNs. Node classification has been studied for decades. Conventionally, hand-crafted features have been used such as simple graph statistics , graph kernel , and engineered features from a local neighbor structure . These features are not flexible and suffer from poor performance. To overcome the drawback, recently node representation learning methods via random walks on graphs have been proposed in DeepWalk , LINE , and node2vec with tricks from deep learning models (e.g., skip-gram) and have gained some improvement in performance. However, all of these methods learn node representation solely based on the graph structure. The representations are not optimized for a specific task. As CNNs have achieved remarkable success in representation learning, GNNs learn a powerful representation for given tasks and data. To improve performance or scalability, generalized convolution based on spectral convolution , attention mechanism on neighbors , subsampling and inductive representation for a large graph have been studied. Although these methods show outstanding results, all these methods have a common limitation which only deals with a homogeneous graph.

However, many real-world problems often cannot be represented by a single homogeneous graph. The graphs come as a heterogeneous graph with various types of nodes and edges. Since most GNNs are designed for a single homogeneous graph, one simple solution is a two-stage approach. Using meta-paths that are the composite relations of multiple edge types, as a preprocessing, it converts the heterogeneous graph into a homogeneous graph and then learns representation. The metapath2vec learns graph representations by using meta-path based random walk and HAN learns graph representation learning by transforming a heterogeneous graph into a homogeneous graph constructed by meta-paths. However, these approaches manually select meta-paths by domain experts and thus might not be able to capture all meaningful relations for each problem. Also, performance can be significantly affected by the choice of meta-paths. Unlike these approaches, our Graph Transformer Networks can operate on a heterogeneous graph and transform the graph for tasks while learning node representation on the transformed graphs in an end-to-end fashion.

Method

The goal of our framework, Graph Transformer Networks, is to generate new graph structures and learn node representations on the learned graphs simultaneously. Unlike most CNNs on graphs that assume the graph is given, GTNs seek for new graph structures using multiple candidate adjacency matrices to perform more effective graph convolutions and learn more powerful node representations. Learning new graph structures involves identifying useful meta-paths, which are paths connected with heterogeneous edges, and multi-hop connections. Before introducing our framework, we briefly summarize the basic concepts of meta-paths and graph convolution in GCNs.

Meta-Path denoted by $p$ is a path on the heterogeneous graph $G$ that is connected with heterogeneous edges, i.e., ${v}_{1}\xrightarrow{t_{1}}{v}_{2}\xrightarrow{t_{2}}\ldots\xrightarrow{t_{l}}{v}_{l+1}$, where $t_{l}\in\mathcal{T}^{e}$ denotes an $l$-th edge type of meta-path. It defines a composite relation $R=t_{1}\circ t_{2}\ldots\circ t_{l}$ between node ${v}_{1}$ and ${v}_{l+1}$, where $R_{1}\circ R_{2}$ denotes the composition of relation $R_{1}$ and $R_{2}$. Given the composite relation $R$ or the sequence of edge types $(t_{1},t_{2},\ldots,t_{l})$, the adjacency matrix ${A}_{\mathcal{P}}$ of the meta-path $P$ is obtained by the multiplications of adjacency matrices as

The notion of meta-path subsumes multi-hop connections and new graph structures in our framework are represented by adjacency matrices. For example, the meta-path Author-Paper-Conference (APC), which can be represented as $A\xrightarrow{AP}P\xrightarrow{PC}C$, generates an adjacency matrix $A_{APC}$ by the multipication of $A_{AP}$ and $A_{PC}$.

Graph Convolutional network (GCN). In this work, a graph convolutional network (GCN) is used to learn useful representations for node classification in an end-to-end fashion. Let $H^{(l)}$ be the feature representations of the $l$th layer in GCNs, the forward propagation becomes

2 Meta-Path Generation

Previous works require manually defined meta-paths and perform Graph Neural Networks on the meta-path graphs. Instead, our Graph Transformer Networks (GTNs) learn meta-paths for given data and tasks and operate graph convolution on the learned meta-path graphs. This gives a chance to find more useful meta-paths and lead to virtually various graph convolutions using multiple meta-path graphs.

It computes the convex combination of adjacency matrices as $\sum_{t_{l}\in\mathcal{T}^{e}}{\alpha_{t_{l}}^{(l)}A_{t_{l}}}$ in (4) by 1x1 convolution as in Fig. 1 with the weights from softmax function as

where $\phi$ is the convolution layer and $W_{\phi}\in\textbf{R}^{1\times 1\times K}$ is the parameter of $\phi$. This trick is similar to channel attention pooling for low-cost image/action recognition in . Given two softly chosen adjacency matrices $Q_{1}$ and $Q_{2}$, the meta-path adjacency matrix is computed by matrix multiplication, $Q_{1}Q_{2}$. For numerical stability, the matrix is normalized by its degree matrix as $A^{(l)}=D^{-1}Q_{1}Q_{2}$.

Now, we need to check whether GTN can learn an arbitrary meta-path with respect to edge types and path length. The adjacency matrix of arbitrary length $l$ meta-paths can be calculated by

3 Graph Transformer Networks

Experiments

In this section, we evaluate the benefits of our method against a variety of state-of-the-art models on node classification. We conduct experiments and analysis to answer the following research questions: Q1. Are the new graph structures generated by GTN effective for learning node representation? Q2. Can GTN adaptively produce a variable length of meta-paths depending on datasets? Q3. How can we interpret the importance of each meta-path from the adjacency matrix generated by GTNs?

Datasets. To evaluate the effectiveness of meta-paths generated by Graph Transformer Networks, we used heterogeneous graph datasets that have multiple types of nodes and edges. The main task is node classification. We use two citation network datasets DBLP and ACM, and a movie dataset IMDB. The statistics of the heterogeneous graphs used in our experiments are shown in Table 1. DBLP contains three types of nodes (papers (P), authors (A), conferences (C)), four types of edges (PA, AP, PC, CP), and research areas of authors as labels. ACM contains three types of nodes (papers (P), authors (A), subject (S)), four types of edges (PA, AP, PS, SP), and categories of papers as labels. Each node in the two datasets is represented as bag-of-words of keywords. On the other hand, IMDB contains three types of nodes (movies (M), actors (A), and directors (D)) and labels are genres of movies. Node features are given as bag-of-words representations of plots.

Implementation details. We set the embedding dimension to 64 for all the above methods for a fair comparison. The Adam optimizer was used and the hyperparameters (e.g., learning rate, weight decay etc.) are respectively chosen so that each baseline yields its best performance. For random walk based models, a walk length is set to 100 per node for 1000 iterations and the window size is set to 5 with 7 negative samples. For GCN, GAT, and HAN, the parameters are optimized using the validation set, respectively. For our model GTN, we used three GT layers for DBLP and IMDB datasets, two GT layers for ACM dataset. We initialized parameters for $1\times 1$ convolution layers in the GT layer with a constant value. Our code is publicly available at https://github.com/seongjunyun/Graph_Transformer_Networks.

To evaluate the effectiveness of representations learnt by the Graph Transformer Networks in node classification, we compare GTNs with conventional random walk based baselines as well as state-of-the-art GNN based methods.

Conventional Network Embedding methods have been studied and recently DeepWalk and metapath2vec have shown predominant performance among random walk based approaches. DeepWalk is a random walk based network embedding method which is originally designed for homogeneous graphs. Here we ignore the heterogeneity of nodes/edges and perform DeepWalk on the whole heterogeneous graph. However, metapath2vec is a heterogeneous graph embedding method which performs meta-path based random walk and utilizes skip-gram with negative sampling to generate embeddings.

2 Results on Node Classification

Effectiveness of the representation learnt from new graph structures. Table 2. shows the performances of GTN and other node classification baselines. By analysing the result of our experiment, we will answer the research Q1 and Q2. We observe that our GTN achieves the highest performance on all the datasets against all network embedding methods and graph neural network methods. GNN-based methods, e.g., GCN, GAT, HAN, and the GTN perform better than random walk-based network embedding methods. Furthermore, the GAT usually performs better than the GCN. This is because the GAT can specify different weights to neighbor nodes while the GCN simply averages over neighbor nodes. Interestingly, though the HAN is a modified GAT for a heterogeneous graph, the GAT usually performs better than the HAN. This result shows that using the pre-defined meta-paths as the HAN may cause adverse effects on performance. In contrast, Our GTN model achieved the best performance compared to all other baselines on all the datasets even though the GTN model uses only one GCN layer whereas GCN, GAT and HAN use at least two layers. It demonstrates that the GTN can learn a new graph structure which consists of useful meta-paths for learning more effective node representation. Also compared to a simple meta-path adjacency matrix with a constant in the baselines, e.g., HAN, the GTN is capable of assigning variable weights to edges.

3 Interpretation of Graph Transformer Networks

where $\mathcal{T}^{e}$ denotes a set of edge types and $\alpha_{t_{l}}^{(l)}$ is an attention score for edge type $t_{l}$ at the $l$th GT layer. So, $A^{(l)}$ can be viewed as a weighted sum of all meta-paths including $1$-length (original edges) to $l$-length meta-paths. The contribution of a meta-path $t_{l},t_{l-1},\ldots,t_{0}$, is obtained by $\prod_{i=0}^{l}\alpha_{t_{i}}^{(i)}$.

Now we can interpret new graph structures learnt by GTNs. The weight $\prod_{i=0}^{l}\alpha_{t_{i}}^{(i)}$ for a meta-path ($t_{0},t_{1},\ldots t_{l}$) is an attention score and it provides the importance of the meta-path in the prediction task. In Table 3 we summarized predefined meta-paths, that are widely used in literature, and the meta-paths with high attention scores learnt by GTNs.

As shown in Table 3, between target nodes, that have class labels to predict, the predefined meta-paths by domain knowledge are consistently top-ranked by GTNs as well. This shows that GTNs are capable of learning the importance of meta-paths for tasks. More interestingly, GTNs discovered important meta-paths that are not in the predefined meta-path set. For example, in the DBLP dataset GTN ranks CPCPA as most importance meta-paths, which is not included in the predefined meta-path set. It makes sense that author’s research area (label to predict) is relevant to the venues where the author publishes. We believe that the interpretability of GTNs provides useful insight in node classification by the attention scores on meta-paths.

Fig.3 shows the attention scores of adjacency matrices (edge type) from each Graph Transformer Layer. Compared to the result of DBLP, identity matrices have higher attention scores in IMDB. As discussed in Section 3.3, a GTN is capable of learning shorter meta-paths than the number of GT layers, which they are more effective as in IMDB. By assigning higher attention scores to the identity matrix, the GTN tries to stick to the shorter meta-paths even in the deeper layer. This result demonstrates that the GTN has ability to adaptively learns most effective meta-path length depending on the dataset.

Conclusion

We proposed Graph Transformer Networks for learning node representation on a heterogeneous graph. Our approach transforms a heterogeneous graph into multiple new graphs defined by meta-paths with arbitrary edge types and arbitrary length up to one less than the number of Graph Transformer layers while it learns node representation via convolution on the learnt meta-path graphs. The learnt graph structures lead to more effective node representation resulting in state-of-the art performance, without any predefined meta-paths from domain knowledge, on all three benchmark node classification on heterogeneous graphs. Since our Graph Transformer layers can be combined with existing GNNs, we believe that our framework opens up new ways for GNNs to optimize graph structures by themselves to operate convolution depending on data and tasks without any manual efforts. Interesting future directions include studying the efficacy of GT layers combined with different classes of GNNs rather than GCNs. Also, as several heterogeneous graph datasets have been recently studied for other network analysis tasks, such as link prediction and graph classification , applying our GTNs to the other tasks can be interesting future directions.

Acknowledgement

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (NRF-2019R1G1A1100626, NRF-2016M3A9A7916996, NRF-2017R1A2A1A17069645).

References