cs.LGSep 28, 2026

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

Authors: Huu Tan Mai, Cuong Xuan Chu, Heiko Paulheim, Daria Stepanova

Organizations: Bosch Center for Artificial Intelligence, Robert-Bosch-Campus 1, 71272 Renningen, Germany · University of Mannheim, Schloss, 68131 Mannheim, Germany

Abstract

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.

Figures & tables

Explore similar work

CardsList
  1. On Efficient Scaling of GNNs via IO-Aware Layers Implementations

    May 29, 2026Daria Fomina, Daniil Krasylnikov, Alexey Boykov +3Graph Neural NetworksGraphics Processing Unit Kernels

  2. CoRe-GNN: Multilevel Message passing on Coarsened graphs

    Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural NetworksGnn-Based Detectors

  3. Reforge: Low-Latency Distributed GNN Serving with Selective Embedding Recomputation

    Jan 15, 2025Geon-Woo Kim, Donghyun Kim, Jeongyoon Moon +5Graph Neural NetworksForge