Leveraging Graph Structure in Seq2Seq Models for Knowledge Graph Link Prediction

Technical Summary: Graph-Augmented Sequence-to-Sequence (GA-S2S) for Knowledge Graph Link Prediction

Problem Statement
Knowledge Graphs (KGs) are inherently incomplete due to data acquisition limits, privacy concerns, and integration errors. Link prediction aims to infer missing facts (triples) within these graphs. While traditional embedding-based and Graph Neural Network (GNN) methods excel at capturing structural patterns, they struggle with unstructured textual information and often incur high computational costs ($O(|E|)$) when ranking candidates for large-scale KGs. Conversely, recent generative Sequence-to-Sequence (Seq2Seq) approaches (e.g., KGT5, KG-S2S) treat link prediction as a text-generation task, offering scalable inference independent of the number of entities. However, these models typically rely solely on verbalized text mentions or flatten neighborhood information into linear sequences, thereby discarding the inherent topological structure and multi-hop relational patterns of the KG.

Methodology: GA-S2S Framework
The authors propose GA-S2S (Graph-Augmented Sequence-to-Sequence), a hybrid framework that integrates a T5-small encoder-decoder with a Relational Graph Attention Network (RGAT). Unlike prior Seq2Seq models that treat inputs as flat text sequences, GA-S2S jointly encodes textual features and the full $k$-hop subgraph topology surrounding a query entity.

The architecture consists of three sequential components:

1. Input Representation: For a query $(e, r, ?)$, the model samples a $k$-hop subgraph $G_{e,k}$. Triples within this subgraph are verbalized into text sequences (e.g., [CLS] head | relation | tail) alongside the query sequence. The subgraph's connectivity is encoded via an adjacency matrix represented by node-index pairs and relation indices.
2. Encoding and Graph Enhancement:
   • Text Encoding: All text sequences (query and subgraph triples) are fed into the T5 encoder to produce hidden state vectors.
   • Entity Aggregation: Since an entity may appear in multiple triples, its representation is aggregated by averaging the [CLS] token vectors of all triples it participates in.
   • RGAT Processing: These aggregated entity features and the adjacency matrix are passed through the RGAT module. This relation-aware GNN propagates and aggregates information across the subgraph, updating the entity embeddings to capture multi-hop relational patterns.
3. Decoding: The decoder receives a concatenation of:
   • Distilled vectors from the raw encoder output (via a lightweight self-attention layer to select salient tokens).
   • The graph-enhanced embeddings from the RGAT module.
     This combined representation allows the T5 decoder to generate the verbalized text mention of the target entity.

The entire pipeline is trained end-to-end from scratch (without pre-trained weights) to minimize cross-entropy loss, preventing negative transfer from natural language priors to the structured KG domain.

Key Contributions

• Hybrid Architecture: The introduction of a framework that seamlessly fuses a generative Seq2Seq backbone with a relation-aware GNN, enabling the model to leverage both textual descriptions and local graph structures simultaneously.
• Topological Encoding: Moving beyond the "flattening" of neighborhoods into linear sequences, GA-S2S explicitly encodes the $k$-hop subgraph topology using RGAT, allowing the model to capture richer multi-hop relational patterns.
• Training Strategy: The decision to initialize the T5 model from scratch rather than using pre-trained weights, acknowledging that pre-trained weights are optimized for natural language syntax rather than the template-based verbalizations and graph embeddings used in KGs.

Experimental Results
The model was evaluated on the CoDEx dataset (S, M, and L variants), which is designed to mitigate train/test leakage.

• Performance: GA-S2S outperformed competitive Seq2Seq-based baselines (KGT5, KG-S2S, KGT5-context).
  • On CoDEx-S, GA-S2S with 2-hop neighborhoods achieved an MRR of 0.331, surpassing KGT5-context (0.277) by 19.5%.
  • On CoDEx-M, it achieved an MRR of 0.289 (2-hop), a 6.6% gain over KGT5-context.
  • On CoDEx-L, GA-S2S (1-hop) achieved an MRR of 0.297, outperforming KGT5-context (0.292) by 1.7%.
• Observations: The performance gain from incorporating 2-hop neighborhoods was most significant on smaller, denser graphs (CoDEx-S) and diminished as graph size increased and sparsity grew. The authors note that while GA-S2S outperforms other generative baselines, it still lags behind leading embedding-based methods (e.g., ComplEx, TuckER) on smaller datasets, though the gap narrows on larger datasets.

Significance and Limitations
The paper claims that GA-S2S demonstrates the clear advantages of explicitly encoding graph structure within generative link prediction models, achieving up to a 19% relative gain in accuracy over competitive Seq2Seq baselines. It establishes a basic hybrid architecture that successfully leverages multi-hop relational reasoning.

However, the authors maintain a modest stance regarding the current state of the work:

• Scalability: The model incurs higher computational costs than standard Seq2Seq models due to the processing of neighborhood structures, presenting scalability challenges for very large KGs.
• Input Complexity: The authors hypothesize that the performance of KGT5-context was lower than KGT5 on some datasets because naively appending linearized neighborhoods creates unwieldy decoder inputs. They suggest that future decoder redesigns accepting structured input could yield further gains.
• Future Directions: The paper identifies open questions regarding balanced neighborhood sampling strategies to manage overhead, the use of hierarchical transformers for scalability, and optimal techniques for integrating textual and structural information throughout encoding and decoding. It suggests that graph transformers may offer a promising direction for deeper integration.