CPa-WAC: Constellation Partitioning-based Scalable Weighted Aggregation Composition for Knowledge Graph Embedding

Sudipta Modak, Aakarsh Malhotra, Sarthak Malik, Anil Surisetty, Esam Abdel-RaheemIJCAI 2024 · OpenReview

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.

Overview of the CPa-WAC architecture, illustrating the partitionwise training and global inference stages.

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).
Comprehensive performance analysis showing MRR, Hit@10, training time, and speedup relative to the number of clusters.

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

Abstract

Scalability and training time are crucial for any graph neural network model processing a knowledge graph (KG). While partitioning knowledge graphs helps reduce the training time, the prediction accuracy reduces significantly compared to training the model on the whole graph. In this paper, we propose CPa-WAC: a lightweight architecture that incorporates graph convolutional networks and modularity maximization-based constellation partitioning to harness the power of local graph topology. The proposed CPa-WAC method reduces the training time and memory cost of knowledge graph embedding, making the learning model scalable. The results from our experiments on standard databases, such as Wordnet and Freebase, show that by achieving meaningful partitioning, any knowledge graph can be broken down into subgraphs and processed separately to learn embeddings. Furthermore, these learned embeddings can be used for knowledge graph completion, retaining similar performance compared to training a GCN on the whole KG, while speeding up the training process by upto five times. Additionally, the proposed CPa-WAC method outperforms several other state-of-the-art KG in terms of prediction accuracy.
BibTeX
@inproceedings{modak2024cpa,
  author = {Sudipta Modak and Aakarsh Malhotra and Sarthak Malik and Anil Surisetty and Esam Abdel-Raheem},
  title = {{CPa-WAC: Constellation Partitioning-based Scalable Weighted Aggregation Composition for Knowledge Graph Embedding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=aAywyJUNQf},
}
Figure