Double-Branch Multi-Attention based Graph Neural Network for Knowledge Graph Completion

Hongcai Xu, Junpeng Bao, Wenbo LiuACL 2023 · DOI

Double-Branch Multi-Attention based Graph Neural Network for Knowledge Graph Completion

Introduction: The Challenge of Incomplete Knowledge Graphs

Knowledge Graphs (KGs) such as Freebase and DBpedia serve as critical backbones for various AI applications by storing structured facts. However, these graphs are inherently incomplete. Knowledge Graph Completion (KGC) aims to address this by predicting missing links between entities. While Graph Neural Networks (GNNs) have become a standard approach for KGC, they often suffer from two primary limitations: locality bias and the "isolated subgraph" problem.

Knowledge Graph structure illustrating local neighborhoods and isolated subgraphs.

Standard GNNs typically aggregate information only from immediate (1-hop) neighbors, failing to capture the broader global structure. Furthermore, large KGs frequently contain small, disconnected clusters of entities. For these "lonely" nodes, traditional GNNs struggle to learn meaningful representations due to the lack of a dense local neighborhood to aggregate information from.

MA-GNN: A Dual-Branch Multi-Attention Framework

To overcome these hurdles, the authors propose MA-GNN (Double-Branch Multi-Attention Graph Neural Network). This model utilizes a dual-branch encoder designed to capture information at multiple scales simultaneously.

The MA-GNN architecture, showcasing the dual-branch encoder and feature fusion mechanism.

The Local Branch and Snowball Attention

The local branch employs a Graph Attention Network (GAT) for 1-hop neighbors and introduces a novel Snowball Local Attention mechanism. This module calculates semantic similarity among 2-hop neighbors, allowing the model to gather richer features from a wider radius without the "over-smoothing" effect common in deep GNNs. By focusing on semantic similarity, the Snowball mechanism effectively filters noise from the high volume of 2-hop neighbors.

The Global Branch

Complementing the local view, the global branch uses a Transformer-based self-attention module. By processing sequences obtained via random walks, the Transformer allows any entity to attend to any other, capturing long-range dependencies and global context. This is particularly beneficial for entities in sparse or isolated subgraphs, as they can still learn from the rest of the graph.

Feature Fusion and Decoding

The outputs from both branches are fused to create a comprehensive entity embedding that reflects both local neighborhood details and global trends. Finally, the ConvE decoder scores the plausibility of triples based on these learned embeddings.

Experimental Results and Key Insights

MA-GNN was evaluated on five standard benchmarks, including FB15K-237, WN18RR, and NELL-995. The results demonstrate significant performance gains, particularly on sparse graphs:

  • WN18RR: Achieved a Hits@10 of 0.679, representing a 12.7% improvement over previous state-of-the-art methods.
  • FB15K: Outperformed baselines by 15.1% on Hits@10.
  • NELL-995: Improved Hits@10 by 4.3%, reaching 0.823.

These results highlight that 2-hop neighbors provide crucial discriminative features when filtered correctly, and that a well-designed multi-attention approach can outperform more complex specialized GNN architectures.

Conclusion and Future Directions

MA-GNN effectively bridges the gap between local and global graph representation learning for KGC. While highly effective for multi-type relation graphs, future work will explore its performance on single-type relations and investigate more computationally efficient global attention mechanisms to scale to even larger KGs. Additionally, extending this global-local fusion to transductive reasoning remains a promising research path.

Summary updated

BibTeX
@inproceedings{xu2023double,
  author = {Hongcai Xu and Junpeng Bao and Wenbo Liu},
  title = {{Double-Branch Multi-Attention based Graph Neural Network for Knowledge Graph Completion}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  doi = {10.18653/v1/2023.acl-long.850},
}
Figure