River of No Return: Graph Percolation Embeddings for Efficient Knowledge Graph Reasoning
This addresses efficiency and accuracy issues in knowledge graph reasoning for AI applications, representing a novel method for a known bottleneck.
The paper tackles the problem of path redundancy in knowledge graph reasoning by linking it to transformation error, proposing Graph Percolation Embeddings (GraPE) to remove redundant paths and maintain shortest ones for efficient message passing. It outperforms state-of-the-art methods in transductive and inductive reasoning tasks with fewer parameters and less inference time.
We study Graph Neural Networks (GNNs)-based embedding techniques for knowledge graph (KG) reasoning. For the first time, we link the path redundancy issue in the state-of-the-art KG reasoning models based on path encoding and message passing to the transformation error in model training, which brings us new theoretical insights into KG reasoning, as well as high efficacy in practice. On the theoretical side, we analyze the entropy of transformation error in KG paths and point out query-specific redundant paths causing entropy increases. These findings guide us to maintain the shortest paths and remove redundant paths for minimized-entropy message passing. To achieve this goal, on the practical side, we propose an efficient Graph Percolation Process motivated by the percolation model in Fluid Mechanics, and design a lightweight GNN-based KG reasoning framework called Graph Percolation Embeddings (GraPE). GraPE outperforms previous state-of-the-art methods in both transductive and inductive reasoning tasks while requiring fewer training parameters and less inference time.