Introduction
Knowledge Graphs (KGs) such as Wikidata, Freebase, and WordNet serve as the backbone for numerous downstream applications, including recommendation systems and question-answering. However, these graphs are inherently incomplete. While traditional Knowledge Graph Completion (KGC) methods have focused on the transductive setting—where all entities are known during training—real-world KGs are dynamic. New entities are constantly added, necessitating inductive KGC capabilities to predict relationships for entities the model has never encountered before.
This paper introduces NORAN (iNfOmax RelAtion Network), a novel framework designed to overcome the limitations of current inductive methods. By shifting the focus from entity-centric representations to a relation-centric "Hyper-View," NORAN captures entity-independent logical patterns, achieving state-of-the-art performance across multiple benchmarks.
The Challenge: Entity-Centric Bias and Data Sparsity
Current inductive KGC approaches primarily rely on Message Passing (MP) neural networks. While effective in some scenarios, these methods face two significant hurdles:
- Data Sparsity: New entities often possess very few initial connections, making it difficult for models to aggregate enough information to form robust representations.
- Entity-Centric Bias: Most MP-based models focus on gathering information from neighboring entities. This makes it challenging to learn generalizable logical rules (e.g., if X works at Y and Y is located in Z, then X likely lives in Z) that remain valid regardless of the specific entities involved.
The NORAN Framework
NORAN addresses these challenges through three core innovations that prioritize relational logic over entity identity.
1. The Relation Network (A "Hyper-View")
In a departure from standard graph representations where entities are nodes and relations are edges, NORAN constructs a Relation Network. In this structure, every triple from the original KG is treated as a node. Two nodes in the Relation Network are connected if their corresponding triples share a common entity. This transformation explicitly highlights the correlations between different relations, allowing the model to reason about the "grammar" of the graph independently of specific entities.
2. Relational Message Passing
NORAN is designed to be model-agnostic, supporting various Graph Neural Network (GNN) backbones such as GAT, GIN, or GraphSAGE. By performing message passing over the Relation Network, the model aggregates "logical evidence" from neighboring triples. This process refines the representation of a target relationship by considering the structural context of the relations surrounding it.
3. Logic Evidence Information Maximization (LEIM)
To ensure the model captures meaningful logical rules rather than noise, the authors introduce LEIM. This training objective utilizes Mutual Information Maximization (via a Jensen-Shannon estimator) to maximize the correlation between a triple’s individual embedding and the collective "logic evidence" gathered from its $k$-hop neighborhood. LEIM encourages the model to recognize latent logical patterns that persist even when the entities are entirely new.
Experimental Evaluation
The framework was evaluated on five diverse benchmarks adapted for inductive settings: FB15K-237, WN18RR, NELL995, and the large-scale OGBL-WIKIKG2 and OGBL-BIOKG datasets.
Key Results
- State-of-the-Art Performance: NORAN consistently outperformed established baselines like GraIL and PATHCON. On FB15K-237, NORAN achieved a Mean Reciprocal Rank (MRR) of 0.499, surpassing the best MP-based baseline (0.483).
- Scalability: The model demonstrated significant gains on large-scale OGB datasets, outperforming competitors by an average of 11.2%.
- Backbone Flexibility: While compatible with multiple GNNs, the GAT (Graph Attention Network) version of NORAN generally yielded the best results, confirming that learnable attention helps the model weigh relevant logical evidence more effectively.
Insights and Discussion
- Relations as the Foundation for Induction: The success of NORAN suggests that while entities are transient, the underlying logic of relations is stable. By centering the graph on relations, models can learn universal rules that generalize to unseen parts of the KG.
- The Importance of Head-Tail Patterns: Ablation studies indicated that "head-tail" sharing patterns—where the tail of one triple serves as the head of another—are the most critical for reasoning. These patterns represent the logical chains essential for multi-hop inference.
- Learnable Weights vs. Fixed Convolutions: Theoretical analysis showed that GNNs with learnable convolution matrices are superior for inductive tasks. Unlike fixed-weight models (like GCN) that treat all neighbors equally, learnable models can adaptively focus on the most pertinent logical evidence.
Conclusion and Future Work
NORAN represents a significant step forward in inductive knowledge graph completion by prioritizing relational logic over entity-centric message passing. While the construction of the Relation Network introduces some computational overhead—as the number of nodes scales with the number of triples—the gains in accuracy and generalizability are substantial.
Future research directions include extending NORAN to handle fully-inductive scenarios (where both entities and relations are unseen) and exploring its application in real-world systems such as KG-enhanced recommendation engines and complex automated reasoning.
Summary updated