Source-linked AI summary
Graph Transformer Networks
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, Hyunwoo J. Kim
TL;DR
Most GNNs assume fixed, homogeneous graph structures, while heterogeneous or misspecified graphs make effective representation learning difficult. GTNs learn task-specific meta-path graphs and node representations jointly, achieving the best performance across three benchmark heterogeneous-graph node-classification tasks without predefined meta-paths. The framework also learns interpretable meta-path importance and adapts meta-path length to the dataset.
Problem
Most GNNs assume fixed, homogeneous graph structures, whereas heterogeneous graphs and misspecified connections complicate effective graph representation learning.
Method
GTNs use graph transformer layers to softly select edge types and generate meta-path graphs while learning node representations on those graphs end-to-end.
Results
GTNs achieved the best performance on all three benchmark heterogeneous-graph node-classification tasks, without predefined meta-paths from domain knowledge.
Takeaways & Limitations
GTNs can learn useful and interpretable graph structures from data and tasks, including meta-paths and lengths not specified by domain knowledge.
Takeaways & Limitations
The framework considers heterogeneous graphs with more than one edge type and represents them through typed adjacency matrices.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have been widely used in representation learning on graphs and achieved state-of-the-art performance in tasks such as node classification and link prediction. However, 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. In this paper, we propose Graph Transformer Networks (GTNs) that are capable of generating new graph structures, which involve identifying useful connections between unconnected nodes on the original graph, while learning effective node representation on the new graphs in an end-to-end fashion. Graph Transformer layer, a core layer of GTNs, learns a soft selection of edge types and composite relations for generating useful multi-hop connections so-called meta-paths. Our experiments show that GTNs learn new graph structures, based on data and tasks without domain knowledge, and yield powerful node representation via convolution on the new graphs. Without domain-specific graph preprocessing, GTNs achieved the best performance in all three benchmark node classification tasks against the state-of-the-art methods that require pre-defined meta-paths from domain knowledge.
1 Introduction
Most GNNs operate on fixed, homogeneous graphs, limiting their effectiveness on noisy or heterogeneous graphs. GTNs address this by learning useful meta-path-based graph structures and node representations jointly.
- Fixed graph assumptions can produce ineffective convolutions when graphs contain missing or spurious connections.
- Heterogeneous graphs contain multiple node and edge types, making suitable graph construction nontrivial.
- Two-stage methods convert heterogeneous graphs into homogeneous graphs using hand-crafted meta-paths, whose choice can significantly affect downstream accuracy.
- GTNs learn useful meta-paths and multi-hop connections while learning node representations on the resulting graphs end-to-end.
- GTNs achieved the best performance on three benchmark heterogeneous-graph node-classification tasks against methods using domain knowledge.
2 Related Works
Existing approaches often transform heterogeneous graphs using manually selected meta-paths before representation learning. GTNs instead learn task-specific graph transformations and representations jointly.
- Meta-path-based preprocessing converts heterogeneous graphs into homogeneous graphs before conventional representation learning.
- Methods such as metapath2vec and HAN rely on meta-paths manually selected by domain experts, potentially missing meaningful task-specific relations.
- GTNs transform heterogeneous graphs for each task while learning node representations on the transformed graphs end-to-end.
3 Method
GTNs generate task-specific meta-path graph structures from heterogeneous inputs and learn node representations on those graphs end-to-end. GT layers softly select and compose edge-type adjacency matrices, while GCNs process multiple learned graph channels.
- Input representation: GTNs accept heterogeneous graphs represented by multiple edge-type adjacency matrices and node features.Each edge type has an adjacency matrix, and the collection can be represented as a tensor.
- Meta-path representation: A meta-path is a composite relation formed by multiplying adjacency matrices for a sequence of heterogeneous edge types.This represents multi-hop connections as new graph structures.
- End-to-end learning: Unlike prior two-stage methods with manually defined meta-paths, GTNs learn meta-paths from data and tasks while performing graph convolution on the learned graphs.This removes the requirement for domain-specific meta-path preprocessing.
- Graph Transformer layer: Each Graph Transformer layer softly selects candidate adjacency matrices and composes two selected relations through matrix multiplication.The selections are convex combinations produced by 1×1 convolution with softmax weights, followed by degree normalization.
- Meta-path generation: Stacked GT layers learn weighted combinations of meta-paths with varying edge types and lengths, while identity connections preserve shorter paths and original edges.With l GT layers, the architecture can learn paths up to length l + 1.
- Graph Transformer Networks: GTNs generate multiple meta-path channels, apply a GCN to each learned graph, and concatenate the resulting node representations for classification.The shared-weight multi-channel architecture acts as an ensemble of GCNs over learned meta-path graphs.
4 Experiments
GTNs are evaluated on heterogeneous-graph node classification through baseline comparisons, ablations, and analyses of learned meta-paths and attention scores. They achieve the highest performance across all datasets and reveal task-relevant graph structures, including adaptive path lengths and previously unspecified relations.
- Datasets and baselines: The experiments evaluate GTNs on heterogeneous DBLP, ACM, and IMDB graphs for node classification, comparing them with network-embedding and GNN-based baselines.The evaluation includes DeepWalk, metapath2vec, GCN, GAT, and HAN, with results reported using F1 score.
- Node classification results: GTN achieves the highest performance on all datasets against all network-embedding and graph-neural-network baselines.The comparison includes methods that operate on homogeneous graphs and HAN, which uses manually selected meta-paths.
- Ablation study: Removing the identity matrix makes GTN−I consistently perform worse than GTN, supporting the inclusion of identity edges for learning variable-length meta-paths.The identity matrix allows the model to retain shorter paths while stacking Graph Transformer layers.
- Graph transformation: GTN generates adjacency matrices as weighted combinations of input edge types, allowing stacked layers to represent meta-paths from original edges to multi-hop relations.The learned weights are produced through softmax and determine the contribution of edge types and composite paths.
- Interpretability: Attention scores rank predefined target-node meta-paths highly while also identifying new relevant paths, such as CPCPA in DBLP.The learned scores provide an interpretable measure of meta-path importance for prediction.
- Adaptive path length: Higher identity-matrix attention in IMDB indicates that GTN adaptively favors shorter meta-paths when they are more effective for the dataset.This contrasts with DBLP and demonstrates adaptive selection of effective meta-path length.
5 Conclusion
GTNs learn heterogeneous graph structures and node representations jointly, achieving state-of-the-art node-classification performance without predefined domain-specific meta-paths.
- GTNs transform heterogeneous graphs into multiple meta-path graphs with arbitrary edge types and lengths, while learning node representations through convolution.Meta-path length can reach one less than the number of Graph Transformer layers.
- GTNs achieve state-of-the-art performance on all three benchmark heterogeneous-graph node-classification tasks without predefined meta-paths from domain knowledge.
- GT layers can combine with existing GNNs, enabling graph structures to be optimized according to data and tasks without manual efforts.The paper identifies combining GT layers with different GNN classes as a future direction.