Distributed Representations of Entities in Open-World Knowledge Graphs

Lingbing Guo, Zhuo Chen, Jiaoyan Chen, Yichi Zhang, Zequn Sun, Zhongpo Bo, Yin Fang, Xiaoze Liu, Huajun Chen, Wen Zhang

This paper addresses a fundamental limitation in how we represent knowledge graphs (KGs): the "closed-world" assumption. While most current models excel at reasoning within a fixed set of entities, they struggle when new entities—like a recently discovered protein or a new startup—are added to the graph.

TL;DR

The authors propose the Decentralized Attention Network (DAN), a new Graph Neural Network (GNN) architecture that generates high-quality entity embeddings without relying on an entity's own initial representation. By using a "neighbor-only" aggregation strategy and a novel self-distillation training objective, DAN achieves state-of-the-art performance on both standard and "open-world" knowledge graph tasks.

What Problem Does This Paper Address?

Most Knowledge Graph embedding methods are transductive: they require all entities to be present during training. In the real world, KGs are dynamic. When a new entity appears, standard GNNs fail because they typically use the entity's own embedding as a "query" to weigh its neighbors. For a new entity, this embedding is just random noise, leading to meaningless attention scores and poor representations.

Existing "inductive" methods often have trade-offs: they might only work for specific tasks (like link prediction but not entity alignment), or they might rely on external features like text or images which aren't always available. The challenge is to create a general-purpose embedding framework that can handle unseen entities using only the graph's structural information.

Methods

The core innovation is the Decentralized Attention Network (DAN).

  1. Decentralized Attention: Unlike standard Graph Attention Networks (GAT) that use the central node to "look" at its neighbors, DAN uses the neighbor context as the query. It essentially asks the neighbors to "vote" on each other's importance to represent the central entity.
  2. Second-Order Mechanism: To keep computation efficient, DAN implements this as a second-order mechanism. It uses the aggregated outputs from previous layers to score neighbors in the current layer, ensuring that the central entity's own (potentially noisy) embedding never pollutes the aggregation process.
  3. Self-Distillation: To train this "neighbor-only" aggregator, the authors use a teacher-student framework. The input embedding of a known entity (the teacher) guides the decentralized output embedding (the student) by maximizing their Mutual Information (MI). This teaches the network how to distill the essence of an entity purely from its surroundings.

The authors draw a clever parallel to natural language processing, comparing their approach to the Continuous Bag-of-Words (CBOW) model, which predicts a word based solely on its context.

Figure 1: A comparison between KG embedding and word embedding. Left: the KG and the sentence contain the same information. Center: the triplet-based models are similar to Skip-gram where each neighbor embedding is used to predict the central element. Right: the GNN-based models resemble CBOW where all neighbor embeddings are aggregated to represent the central element, with the exception that CBOW does not uses the self-entity embedding.

Datasets

The model was evaluated on two primary tasks:

  • Entity Alignment (EA): Using the DBP15K datasets (Chinese-English, Japanese-English, and French-English).
  • Entity Prediction (EP): Using standard benchmarks like FB15K, WN18, FB15K-237, and WN18RR.

Crucially, the authors introduced Open-World Benchmarks for these tasks. They restructured the datasets by sampling 20% of testing entities as "unseen," removing their associated triplets from the training set to simulate a real-world scenario where new data arrives after the model is trained.

Key Insights and Ideas

  • The "Self-Entity" is Redundant for Structure: The authors argue that for encoding relational information, the central entity itself is often unnecessary. If you know W3C was founded by Tim Berners-Lee and developed RDF, you have the "W3C-ness" defined by those relations alone.
  • Collective Voting Mitigates Bias: By using neighbors to score neighbors, the model is less susceptible to the biases or noise inherent in a single entity's embedding.
  • MI vs. Distance: Instead of forcing the output embedding to be exactly like the input (using L2 distance), they maximize Mutual Information. This recognizes that input and output embeddings serve different functional roles in the network.

Key Results

DAN consistently outperformed existing state-of-the-art (SOTA) methods:

  • Conventional Entity Alignment: On the ZH-EN dataset, DAN achieved a Hits@1 of 0.589, significantly higher than AliNet (0.539) and GAT (0.418).
  • Open-World Superiority: The performance gap widened in open-world settings. When 80% of entities were unseen, DAN outperformed AliNet by a staggering 35.9% on Hits@1.
  • Efficiency: Despite the sophisticated attention mechanism, DAN's training time is comparable to or faster than existing GNNs due to faster convergence (averaging 55 epochs vs. 280 for AliNet).

Limitations and Future Work

  • Input Layer Lag: The authors noted that the performance of the very first layer in DAN lags behind standard GNNs because it lacks the central entity's information. They solve this by concatenating embeddings from all layers, but improving the initial layer's representation remains an open question.
  • Generalization: While highly effective for KGs, the authors suggest that decentralized attention could be explored for other graph-based applications where node features are missing or unreliable.

Overall, DAN provides a robust path forward for Knowledge Graphs that need to grow and adapt without constant, expensive retraining.

Summary updated

Abstract

Graph neural network (GNN)-based methods have demonstrated remarkable performance in various knowledge graph (KG) tasks. However, most existing approaches rely on observing all entities during training, posing a challenge in real-world knowledge graphs where new entities emerge frequently. To address this limitation, we introduce Decentralized Attention Network (DAN). DAN leverages neighbor context as the query vector to score the neighbors of an entity, thereby distributing the entity semantics only among its neighbor embeddings. To effectively train a DAN, we introduce self-distillation, a technique that guides the network in generating desired representations. Theoretical analysis validates the effectiveness of our approach. We implement an end-to-end framework and conduct extensive experiments to evaluate our method, showcasing competitive performance on conventional entity alignment and entity prediction tasks. Furthermore, our method significantly outperforms existing methods in open-world settings.
BibTeX
@article{guo2024distributed,
  author = {Lingbing Guo and Zhuo Chen and Jiaoyan Chen and Yichi Zhang and Zequn Sun and Zhongpo Bo and Yin Fang and Xiaoze Liu and Huajun Chen and Wen Zhang},
  title = {{Distributed Representations of Entities in Open-World Knowledge Graphs}},
  journal = {Knowledge-Based Systems},
  year = {2024},
  doi = {10.1016/j.knosys.2024.111582},
}
Figure