Papers › From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis
From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis
Konstantinos Bougiatiotis, Georgios Paliouras
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
| Task | Dataset | Model | Metric | Value | Rank at snapshot | Leaderboard | Report |
|---|---|---|---|---|---|---|---|
| Graph Regression | Peptides-struct | BoP | MAE | 0.25 | #23 of 39 | Archive leaderboard | report |
| Graph Regression | ZINC | BoP | MAE | 0.297 | #24 of 27 | Archive leaderboard | report |
| Node Classification | AIFB | BoP | Accuracy | 92.22 | #4 of 7 | Archive leaderboard | report |
| Node Classification | AM | BoP | Accuracy | 92.41 | #1 of 8 | Archive leaderboard | report |
| Node Classification | BGS | BoP | Accuracy | 90.34 | #2 of 7 | Archive leaderboard | report |
| Node Classification | MUTAG | BoP | Accuracy | 91.17 | #1 of 6 | Archive leaderboard | report |
Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections