From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis
It addresses the need for efficient representation and analysis of large multi-relational networks in fields like biomedical and social sciences, though it is incremental as it builds on an existing framework.
This work extends the Prime Adjacency Matrices framework to enable fast analysis of multi-relational graphs by introducing a lossless algorithm for multi-hop matrices and the Bag of Paths representation, demonstrating that BoP-based models perform comparably to or better than neural models with improved speed and interpretability.
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.