Communicative Message Passing for Inductive Relation Reasoning

Sijie Mai, Shuangjia Zheng, Yuedong Yang, Haifeng Hu

Abstract

Knowledge Graph (KG) completion traditionally relies on transductive models that cannot handle unseen entities. This paper introduces CoMPILE, a novel framework for inductive relation reasoning. By leveraging directed subgraph extraction and a communicative message-passing mechanism where node and edge embeddings are updated bidirectionally, CoMPILE effectively captures structural and semantic information. Experimental results on standard benchmarks demonstrate that CoMPILE significantly outperforms existing state-of-the-art models, particularly in handling asymmetric relations and generalizing to new entities.

Introduction

Knowledge Graphs (KGs) such as Freebase and WordNet represent facts as triplets: (head entity, relation, tail entity). Despite their scale, these graphs are often incomplete. Traditional link prediction models are transductive, meaning they are limited to predicting relationships between entities present during training. However, real-world KGs are dynamic, with new entities (e.g., users, proteins, or concepts) constantly emerging.

Inductive reasoning—the ability to predict relationships for entirely new entities based on local graph structure—is therefore critical. While previous models like GraIL attempted inductive reasoning using subgraphs, they suffered from two primary limitations: they often ignored edge directionality and treated relations as secondary weights rather than active components of the reasoning process.

Methodology: CoMPILE

The authors propose CoMPILE (Communicative Message Passing for Inductive reLation rEasoning) to address these flaws through three core innovations.

Directed Subgraph Extraction

CoMPILE extracts a directed enclosing subgraph instead of a standard $h$-hop neighborhood. This approach focuses on the logical paths connecting the head and tail entities, preserving the "flow" of reasoning while reducing computational noise from irrelevant neighbors.

Comparison of different subgraph extraction strategies. The enclosing subgraph (top right) focuses on the relevant paths between target entities.

Communicative Message Passing

Unlike standard Graph Neural Networks (GNNs) that primarily update node features, CoMPILE employs a "communicative kernel." In this architecture, nodes update edges and edges update nodes in an iterative loop. This ensures that the semantic meaning of relations is deeply integrated into the structural representation of entities.

The CoMPILE architecture showing the communicative message passing (MP) flow between nodes (N) and relations (R).

Enhanced Scoring and Attention

The model utilizes the entire target triplet—head, relation, and tail—to compute edge attention, prioritizing the most relevant paths in the local neighborhood. For final prediction, it uses a TransE-style scoring function ($h + r \approx t$), which is inherently asymmetric and better suited for directional reasoning than the symmetric functions used in prior work.

Experimental Evaluation

CoMPILE was evaluated on inductive versions of three standard benchmarks: WN18RR, FB15k-237, and NELL-995.

A significant contribution of this work is the release of post-processed datasets. The authors discovered that existing inductive benchmarks contained many "empty-subgraph" triplets where no logical path exists between entities. Their filtered versions provide a more rigorous measure of a model's reasoning capabilities.

Key Results

CoMPILE achieved state-of-the-art (SOTA) performance across nearly all metrics:

  • WN18RR: Achieved an AUC-PR of ~98-99%, a substantial improvement over GraIL’s ~92-94%.
  • FB15k-237: Showed significant gains in Hits@10 (e.g., 67.64 vs. GraIL's 64.15 on version 1).
  • Efficiency: Despite a slightly higher parameter count (~36k vs. ~29k), the directed subgraph approach improves inference efficiency by processing smaller, more relevant subgraphs.

Discussion and Future Work

The success of CoMPILE highlights that relations are first-class citizens in inductive settings. Since entity IDs are unavailable, the model must rely on the evolving semantic meaning of relations. Furthermore, the "pruning" effect of directed subgraphs demonstrates that structural precision is often more valuable than raw data volume.

Future research directions include:

  • Node-Free Reasoning: Exploring models that rely entirely on relation-only message passing.
  • Scalability: Improving the efficiency of subgraph extraction for extremely dense graphs.
  • Long-Range Dependencies: Developing methods to incorporate dependencies beyond the fixed $h$-hop limit without exponential complexity.

Summary updated

Abstract

Relation prediction for knowledge graphs aims at predicting missing relationships between entities. Despite the importance of inductive relation prediction, most previous works are limited to a transductive setting and cannot process previously unseen entities. The recent proposed subgraph-based relation reasoning models provided alternatives to predict links from the subgraph structure surrounding a candidate triplet inductively. However, we observe that these methods often neglect the directed nature of the extracted subgraph and weaken the role of relation information in the subgraph modeling. As a result, they fail to effectively handle the asymmetric/anti-symmetric triplets and produce insufficient embeddings for the target triplets. To this end, we introduce a Communicative Message Passing neural network for Inductive reLation rEasoning, CoMPILE, that reasons over local directed subgraph structures and has a vigorous inductive bias to process entity-independent semantic relations. In contrast to existing models, CoMPILE strengthens the message interactions between edges and entitles through a communicative kernel and enables a sufficient flow of relation information. Moreover, we demonstrate that CoMPILE can naturally handle asymmetric/anti-symmetric relations without the need for explosively increasing the number of model parameters by extracting the directed enclosing subgraphs. Extensive experiments show substantial performance gains in comparison to state-of-the-art methods on commonly used benchmark datasets with variant inductive settings.
BibTeX
@inproceedings{mai2021communicative,
  author = {Sijie Mai and Shuangjia Zheng and Yuedong Yang and Haifeng Hu},
  title = {{Communicative Message Passing for Inductive Relation Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16554},
}
Figure