MOHONE: Modeling Higher Order Network Effects in KnowledgeGraphs via Network Infused Embeddings

Hao Yu, Vivek Kulkarni, William Yang WangarXiv 2018 · OpenReview

TL;DR

This paper introduces MOHONE, a novel framework that enhances knowledge graph embeddings by incorporating higher-order network effects. By modeling both shared local neighborhoods and structural roles of entities at various scales, MOHONE significantly boosts the performance of existing knowledge graph embedding methods on link prediction tasks.

What Problem Does This Paper Address?

Knowledge graphs (KGs) are powerful structures for organizing information, and representing them as dense embeddings in vector spaces has become a popular approach for various AI applications. However, most existing KG embedding methods primarily focus on individual triples (subject-predicate-object), which limits them to a very local view of the KG. This "local view" prevents them from fully leveraging the rich, interconnected structure of the entire graph, including higher-order relationships and global patterns. The paper aims to address this limitation by developing a framework that explicitly models these higher-order network effects to create more informed and effective KG embeddings.

Methods

MOHONE is a two-component framework:

  1. Learning Higher Order Network Embeddings: This component focuses on capturing network properties of entities. It models two key aspects of network similarity:
  2. Shared Neighborhood Similarity: Entities that share many common neighbors are considered similar.
  3. Structural Role Similarity: Entities that play similar roles within the network structure are considered similar. The framework uses a unified approach based on diffusion heat kernels to model these similarities at different "scales" of network connectivity, from local to global. This is achieved by leveraging the properties of the graph Laplacian and its associated heat diffusion patterns.

  4. Infusing Knowledge Graph Embeddings with Network Embeddings: Once the network embeddings are learned, MOHONE provides a fast and efficient iterative update mechanism to integrate this information into existing KG embeddings. This process aims to preserve the original KG embedding similarities while incorporating the network-based similarities. The method formulates this as a convex optimization problem, allowing for efficient training.

A key aspect of MOHONE is its model-agnostic nature, meaning it can be applied to improve a wide range of existing KG embedding techniques.

Datasets

The paper evaluates MOHONE on two standard datasets for knowledge graph link prediction:

  • FB15K-237
  • WN18RR

These datasets are commonly used in the field for evaluating KG embedding methods.

Key Insights and Ideas

  • Beyond Triples: The core insight is that KG embeddings can be significantly improved by looking beyond individual triples and considering the broader network structure and connectivity patterns.
  • Scale Matters: Explicitly modeling different scales of network connectivity (local vs. global) is crucial for capturing richer entity representations.
  • Two Faces of Similarity: Both shared local neighborhoods and structural roles are important aspects of network similarity, and a unified framework can capture both.
  • Shared Neighborhood Superiority for Link Prediction: For the task of link prediction, modeling shared local neighborhood similarity appears to be more beneficial than modeling structural role similarity alone.
  • Generalizability: MOHONE's ability to improve various baseline KG embedding methods highlights its broad applicability and effectiveness.

Key Results

MOHONE consistently and significantly improves the performance of several state-of-the-art KG embedding methods on link prediction tasks.

  • On the FB15K-237 dataset, incorporating MOHONE led to an average improvement of 2.76 points (or 10.63%) in Mean Reciprocal Rank (MRR) across all baseline models.
  • Specific improvements include a 17.8% MRR increase for TransH and a 15.5% MRR increase for TransD.
  • The paper also reports improvements in Hits@10, with an average relative improvement of 5.7%.
  • When compared to NODE2VEC (a strong network embedding method), MOHONE-SHNB yielded an average relative improvement of 3.8%, suggesting the importance of explicitly modeling scale.

Limitations and Future Work

  • Limitations:
    • The paper makes a simplifying assumption that modeling the aggregate network structure is useful, leaving the more refined case of directed graphs for future work.
  • While both shared neighborhood and structural similarity yield improvements, the paper notes that shared neighborhood similarity is generally more informative for link prediction.
  • Future Work:
    • Investigating how fine-grained node measures and network characteristics (like clustering coefficients, modularity) correlate with performance improvements.
  • Developing scalable joint training approaches to infuse network cues into KG embedding training procedures.
  • Analyzing the trade-offs of modeling different aspects of network similarity on other predictive tasks beyond link prediction.

Summary updated

Abstract

Many knowledge graph embedding methods operate on triples and are therefore implicitly limited by a very local view of the entire knowledge graph. We present a new framework MOHONE to effectively model higher order network effects in knowledge-graphs, thus enabling one to capture varying degrees of network connectivity (from the local to the global). Our framework is generic, explicitly models the network scale, and captures two different aspects of similarity in networks: (a) shared local neighborhood and (b) structural role-based similarity. First, we introduce methods that learn network representations of entities in the knowledge graph capturing these varied aspects of similarity. We then propose a fast, efficient method to incorporate the information captured by these network representations into existing knowledge graph embeddings. We show that our method consistently and significantly improves the performance on link prediction of several different knowledge-graph embedding methods including TRANSE, TRANSD, DISTMULT, and COMPLEX(by at least 4 points or 17% in some cases).
BibTeX
@misc{yu2018mohone,
  author = {Hao Yu and Vivek Kulkarni and William Yang Wang},
  title = {{MOHONE: Modeling Higher Order Network Effects in KnowledgeGraphs via Network Infused Embeddings}},
  year = {2018},
  eprint = {1811.00198},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.00198},
}
Figure