用质数编码关系，让多关系图分析更快更可解释
From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis
- 用质数唯一表示不同关系，单矩阵存全图
- 无损算法快速计算多跳连接，速度显著提升
- 路径包特征提取法适合各类图分析任务
多关系网络在生物医学、金融和社会科学等领域广泛应用。随着数据规模增大，高效表示与分析方法变得关键。本文扩展了质数邻接矩阵（PAM）框架，利用质数唯一编码网络中的不同关系，实现用单一邻接矩阵紧凑表示完整多关系图，并支持快速计算多跳邻接矩阵。我们提出一种无损算法计算多跳矩阵，并引入路径包（Bag of Paths, BoP）特征提取方法，适用于节点、边和图级别的多种图分析任务。实验表明，基于BoP的简单模型在多个数据集上性能达到或优于主流神经模型，同时具备更快的速度和更强的可解释性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。