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.
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.
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