Abstract
Knowledge Graph Embedding (KGE) models face significant scalability challenges as graphs grow in size and complexity. While partitioning strategies can alleviate computational bottlenecks, they often compromise global structural integrity, leading to reduced prediction accuracy. We present CPa-WAC, a novel framework that utilizes "constellation partitioning" to decompose large graphs into localized clusters while preserving topological context. Combined with a Weighted Aggregation Composition (WAC) GNN architecture and a global decoder, CPa-WAC achieves up to a 5x speedup in training time without sacrificing performance, even outperforming state-of-the-art models on dense datasets.
Introduction
Knowledge Graphs (KGs) serve as the backbone for numerous AI applications by representing real-world facts as structured networks. However, the inherent incompleteness of KGs necessitates link prediction via embedding techniques. Modern Graph Neural Networks (GNNs) offer powerful representation learning but suffer from quadratic growth in memory and time requirements relative to graph size. Traditional partitioning methods often "break" the graph's global structure, resulting in a significant drop in accuracy. CPa-WAC addresses this by intelligently partitioning the graph to maintain local connectivity and employing a global stitching mechanism.
Methodology
The CPa-WAC framework consists of three primary components designed to balance efficiency and structural preservation.
Constellation Partitioning (CPa)
Rather than random splitting, CPa employs Louvain clustering to identify natural communities within the KG. A hierarchical "constellation" logic is applied to merge outlier clusters into denser ones based on specific thresholds. This ensures that related entities remain within the same partition, preserving the local context essential for accurate embedding.
Weighted Aggregation Composition (WAC)
The WAC architecture enhances standard message-passing GNNs. It utilizes element-wise multiplication for entity-relation composition and incorporates attention mechanisms. A weighted sum balances an entity’s intrinsic features against aggregated messages from its neighbors, allowing for more nuanced representation learning.
Global Decoder (GD)
To mitigate the information loss inherent in partitioning, a global decoder is introduced. After parallel training on individual partitions, the resulting features are upscaled and processed through a Multi-Layer Perceptron (MLP) trained on the full dataset. This final step "stitches" local knowledge back into a global context for final link prediction.
Experimental Evaluation
The model was evaluated on four standard benchmarks: FB15K, FB15K-237, WN18, and WN18RR. These datasets vary in scale and connectivity, providing a robust test for the framework's scalability and accuracy.
Key Results
CPa-WAC demonstrates substantial improvements in both training efficiency and predictive performance:
- Scalability: The framework achieved up to a 5x speedup compared to standard GCNs. On the FB15K dataset, training time per epoch was reduced from 168 seconds (RAGAT) to 65 seconds.
- Accuracy: On FB15K, CPa-WAC reached a Mean Reciprocal Rank (MRR) of 0.742, significantly higher than Comp-GCN (0.621) and RAGAT (0.637).
- Structural Preservation: The CPa method successfully kept over 70% of related facts (Tail and Head entities) within the same partition, a metric termed THP (Tail and Head in same Partition).
Discussion and Insights
The results indicate that "density is destiny"; the framework performs exceptionally well on dense graphs like FB15K and WN18. In these instances, partitioning acts as a form of structural regularization, sometimes leading to higher accuracy than full-graph training. Furthermore, the ability to train on 2 to 8 partitions in parallel allows the model to bypass memory bottlenecks common in large-scale GNN applications.
Conclusion
CPa-WAC provides a scalable solution for training KGEs on massive graphs. By combining intelligent partitioning with a global decoding strategy, it achieves significant speedups while maintaining or improving state-of-the-art accuracy. Future work will focus on automating hyperparameter tuning for the constellation logic and exploring more advanced reasoning algorithms to replace the global retraining phase.
Summary updated