# Scalable GNN-based Knowledge Graph Representation Learning with Efficient Message Passing

arXiv: https://arxiv.org/abs/2609.34499 · HTML: https://mlsanity.com/paper/2609.34499/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 46 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 29 of 29)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation](https://mlsanity.com/paper/1911.06136/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Low-Dimensional Hyperbolic Knowledge Graph Embeddings](https://mlsanity.com/paper/2005.00545/) (2020)
- [Holographic Embeddings of Knowledge Graphs](https://mlsanity.com/paper/1510.04935/) (2015)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [Learning Attention-based Embeddings for Relation Prediction in Knowledge Graphs](https://mlsanity.com/paper/1906.01195/) (2019)
- [PyTorch-BigGraph: A Large-scale Graph Embedding System](https://mlsanity.com/paper/1903.12287/) (2019)
- [SimKGC: Simple Contrastive Knowledge Graph Completion with Pre-trained Language Models](https://mlsanity.com/paper/2203.02167/) (2022)
- [NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs](https://mlsanity.com/paper/2106.12144/) (2021)
- [DGL-KE: Training Knowledge Graph Embeddings at Scale](https://mlsanity.com/paper/2004.08532/) (2020)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks](https://mlsanity.com/paper/2007.03179/) (2020)
- [GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding](https://mlsanity.com/paper/1903.00757/) (2019)
- [LargeEA: Aligning Entities for Large-scale Knowledge Graphs](https://mlsanity.com/paper/2108.05211/) (2021)
- [ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion](https://mlsanity.com/paper/2206.04192/) (2022)
- [r-GAT: Relational Graph Attention Network for Multi-Relational Graphs](https://mlsanity.com/paper/2109.05922/) (2021)
- [Relation Matters in Sampling: A Scalable Multi-Relational Graph Neural Network for Drug-Drug Interaction Prediction](https://mlsanity.com/paper/2105.13975/) (2021)
- [StarGraph: Knowledge Representation Learning based on Incomplete Two-hop Subgraph](https://mlsanity.com/paper/2205.14209/) (2022)

## Abstract (arXiv)

Graph neural networks (GNNs) excel at representation learning on Knowledge Graphs (KGs), achieving stateof-the-art performance on tasks like link prediction or entity classification. However, their high computational complexity, inherent to their user-defined message passing (MP) algorithm, still prohibits their widespread adoption, especially for large KGs. Current efforts to mitigate the scalability bottlenecks of GNNs on KGs, such as subgraph sampling, are often task- and model-specific, and do not reliably guarantee lossless (if applicable) runtime/space reductions. To address this, we extend Relational Sparse Matrix Multiplication (RSPMM), originally designed to losslessly lower the space complexity of composition-based MP with pointwise composition functions, to support more expressive functions (e.g., 2x2 block-diagonal matrix multiplication, Givens rotation, circular correlation). Our method delivers significant task-independent reductions in runtime and space for current GNNs on KGs and facilitates efficient re-implementations of GNNs that maintain near state-of-the-art performance on challenging KG tasks, for a fraction of computational costs.