Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs

Seongjun Yun, Minbyul Jeong, Sungdong Yoo, Seunghun Lee, Sean S. Yi, Raehyun Kim, Jaewoo Kang, Hyunwoo J. Kim

Abstract

Graph Neural Networks (GNNs) typically rely on fixed graph structures, which can be problematic for heterogeneous or noisy data. Graph Transformer Networks (GTNs) address this by learning to transform the graph structure itself through the automated construction of meta-paths. We further discuss FastGTNs, an optimized variant that achieves significant speedups and memory efficiency while enabling non-local operations. Extensive experiments show that these models achieve state-of-the-art performance on node classification tasks across both homogeneous and heterogeneous graphs.

Introduction

Standard GNNs aggregate information from neighbors defined by a static input graph. However, real-world graphs are often heterogeneous (containing multiple node and edge types) or misspecified (containing noise). Traditionally, handling heterogeneity required manual "meta-path" engineering—pre-defining sequences of edge types like Author-Paper-Author. GTNs automate this process, treating the graph structure as a learnable parameter that can be optimized for the specific task at hand.

Methodology

The Graph Transformer Layer

The core of the GTN is the Graph Transformer (GT) layer, which generates new graph structures by performing a soft selection of adjacency matrices.

The Graph Transformer (GT) layer mechanism for soft selection and meta-path generation.

As illustrated in Figure 1, the GT layer uses $1 \times 1$ convolutions to learn weights for different edge types. By multiplying these weighted adjacency matrices, the model effectively computes multi-hop connections, or meta-paths, in an end-to-end manner. A key feature is the inclusion of an identity matrix in the selection pool, which allows the model to adaptively learn meta-paths of varying lengths, effectively acting as a denoising filter when the input graph is unreliable.

FastGTNs and Non-local Operations

While powerful, the original GTN architecture faces scalability issues due to the computational cost of explicit matrix multiplications. FastGTNs overcome this by leveraging the associative property of matrix multiplication, applying transformations directly to feature matrices rather than computing large intermediate adjacency matrices.

Architecture of FastGTN layers incorporating non-local operations and efficient channel-wise transformations.

Figure 3 shows the FastGTN architecture, which includes "FastGT" layers that are significantly more efficient. Additionally, the authors extend the framework to include non-local operations. By connecting nodes based on semantic similarity (feature proximity) rather than just existing physical links, the model can capture relationships that are not explicitly present in the original graph topology, further improving representation power.

Key Results and Insights

  • State-of-the-Art Performance: GTNs and FastGTNs outperformed all baselines (including GCN, GAT, and HAN) across 12 benchmark datasets for node classification.
  • Efficiency Gains: FastGTNs achieved a 230x speedup in inference time and used 100x less memory than the original GTN on large-scale datasets like PPI.
  • Automated Discovery: The model successfully "rediscovered" important meta-paths that were previously defined manually by domain experts, such as the "Paper-Conference-Paper" connection in citation networks.

Conclusion

GTNs represent a significant shift from static to learnable graph structures. By automating meta-path discovery and optimizing for scalability with FastGTNs, this research provides a robust framework for handling complex, heterogeneous, and noisy graph data. Future work may extend these capabilities to link prediction and broader graph-level classification tasks.

Summary updated

Abstract

Graph Neural Networks (GNNs) have been widely applied to various fields due to their powerful representations of graph-structured data. Despite the success of GNNs, most existing GNNs are designed to learn node representations on the fixed and homogeneous graphs. The limitations especially become problematic when learning representations on a misspecified graph or a heterogeneous graph that consists of various types of nodes and edges. To address this limitations, we propose Graph Transformer Networks (GTNs) that are capable of generating new graph structures, which preclude noisy connections and include useful connections (e.g., meta-paths) for tasks, while learning effective node representations on the new graphs in an end-to-end fashion. We further propose enhanced version of GTNs, Fast Graph Transformer Networks (FastGTNs), that improve scalability of graph transformations. Compared to GTNs, FastGTNs are 230x faster and use 100x less memory while allowing the identical graph transformations as GTNs. In addition, we extend graph transformations to the semantic proximity of nodes allowing non-local operations beyond meta-paths. Extensive experiments on both homogeneous graphs and heterogeneous graphs show that GTNs and FastGTNs with non-local operations achieve the state-of-the-art performance for node classification tasks. The code is available: https://github.com/seongjunyun/Graph_Transformer_Networks
BibTeX
@article{yun2022graph,
  author = {Seongjun Yun and Minbyul Jeong and Sungdong Yoo and Seunghun Lee and Sean S. Yi and Raehyun Kim and Jaewoo Kang and Hyunwoo J. Kim},
  title = {{Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs}},
  journal = {Neural Networks},
  year = {2022},
  doi = {10.1016/j.neunet.2022.05.026},
}
Figure