Optimizing Graph Transformer Networks with Graph-based Techniques
  Graph transformer networks (GTN) are a variant of graph convolutional
networks (GCN) that are targeted to heterogeneous graphs in which nodes and
edges have associated type information that can be exploited to improve
inference accuracy. GTNs learn important metapaths in the graph, create
weighted edges for these metapaths, and use the resulting graph in a GCN.
Currently, the only available implementation of GTNs uses dense matrix
multiplication to find metapaths. Unfortunately, the space overhead of this
approach can be large, so in practice it is used only for small graphs. In
addition, the matrix-based implementation is not fine-grained enough to use
random-walk based methods to optimize metapath finding. In this paper, we
present a graph-based formulation and implementation of the GTN metapath
finding problem. This graph-based formulation has two advantages over the
matrix-based approach. First, it is more space efficient than the original GTN
implementation and more compute-efficient for metapath sizes of practical
interest. Second, it permits us to implement a sampling method that reduces the
number of metapaths that must be enumerated, allowing the implementation to be
used for larger graphs and larger metapath sizes. Experimental results show
that our implementation is $6.5\times$ faster than the original GTN
implementation on average for a metapath length of 4, and our sampling
implementation is $155\times$ faster on average than this implementation
without compromising on the accuracy of the GTN.
