# From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 17 Nov 2024.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2010.04029/) (2020)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Relational Message Passing for Knowledge Graph Completion](https://mlsanity.com/paper/2002.06757/) (2020)
- [The structure and dynamics of multilayer networks](https://mlsanity.com/paper/1407.0742/) (2014)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Chains of Reasoning over Entities, Relations, and Text using Recurrent Neural Networks](https://mlsanity.com/paper/1607.01426/) (2016)
- [Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Study](https://mlsanity.com/paper/2003.08001/) (2020)
- [Compositional Vector Space Models for Knowledge Base Completion](https://mlsanity.com/paper/1504.06662/) (2015)
- [TensorLog: A Differentiable Deductive Database](https://mlsanity.com/paper/1605.06523/) (2016)
- [Explainable Biomedical Recommendations via Reinforcement Learning Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2111.10625/) (2021)
- [R5: Rule Discovery with Reinforced and Recurrent Relational Reasoning](https://mlsanity.com/paper/2205.06454/) (2022)
- [Multilayer motif analysis of brain networks](https://mlsanity.com/paper/1606.09115/) (2016)
- [Analysing Biomedical Knowledge Graphs using Prime Adjacency Matrices](https://mlsanity.com/paper/2305.10467/) (2023)

## Abstract (arXiv)

Multi-relational networks capture intricate relationships in data and have diverse applications across fields such as biomedical, financial, and social sciences. As networks derived from increasingly large datasets become more common, identifying efficient methods for representing and analyzing them becomes crucial. This work extends the Prime Adjacency Matrices (PAMs) framework, which employs prime numbers to represent distinct relations within a network uniquely. This enables a compact representation of a complete multi-relational graph using a single adjacency matrix, which, in turn, facilitates quick computation of multi-hop adjacency matrices. In this work, we enhance the framework by introducing a lossless algorithm for calculating the multi-hop matrices and propose the Bag of Paths (BoP) representation, a versatile feature extraction methodology for various graph analytics tasks, at the node, edge, and graph level. We demonstrate the efficiency of the framework across various tasks and datasets, showing that simple BoP-based models perform comparably to or better than commonly used neural models while offering improved speed and interpretability.