  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.
