Constrained Information-Theoretic Tripartite Graph Clustering to Identify Semantically Similar Relations

Chenguang Wang, Yangqiu Song, Dan Roth, Chi Wang, Jiawei Han, Heng Ji, Ming Zhang

Introduction

In Natural Language Processing (NLP) and Knowledge Base (KB) management, identifying semantically equivalent relations is a critical challenge. A single real-world relationship can be expressed through numerous surface patterns; for instance, "(Larry Page, wrote, book)" and "(Larry Page, is author of, book)" represent the same semantic link despite using different strings. Traditional clustering methods often struggle with this task. One-dimensional clustering (like K-means) ignores relational structure, while co-clustering typically only considers one side of a relation. Even 3D tensor decomposition, which accounts for both entities, is frequently hampered by data sparsity, as most entities do not interact with most relations.

The CTGC Framework

To address these limitations, this paper proposes Constrained Tripartite Graph Clustering (CTGC). This framework models data as a tripartite graph consisting of three types of nodes: Left Entities ($E^1$), Relations ($R$), and Right Entities ($E^2$). By condensing the data into two related matrices ($E^1 \times R$ and $R \times E^2$), the model becomes more robust against the sparsity inherent in large-scale knowledge bases.

The tripartite graph model representing relations (R) between two entity sets (E1, E2), with associated constraint sets (L).

Information-Theoretic Objective

CTGC utilizes an objective function based on Kullback-Leibler (KL) divergence. The goal is to find a compressed representation—clusters—that minimizes the loss of information regarding the original co-occurrence probabilities between entities and relations.

Semi-Supervised Constraints

A key innovation of CTGC is the integration of "side information" as constraints:

  • Relation Constraints: Derived from string similarity (e.g., "founder of" and "founded by").
  • Entity Constraints: Leverages entity types (e.g., Person, Company). If a relation consistently connects specific entity types, it provides a strong signal for its semantic category.

These are implemented as "soft" must-link and cannot-link constraints, allowing the algorithm to prioritize data-driven patterns while being guided by background knowledge.

Experimental Evaluation

The authors evaluated CTGC on two datasets:

  1. Rel-KB: A "gold standard" dataset derived from Freebase containing 16,516 relation expressions across six categories.
  2. Rel-OIE: A noisy, real-world dataset built using the ReVerb Open Information Extraction system on Wikipedia, containing over 137,000 unique relation expressions.

Key Results and Insights

Performance was measured using Normalized Mutual Information (NMI). CTGC consistently outperformed baseline methods, including K-means, standard Information-Theoretic Co-Clustering (ITCC), and Tensor Factorization (TFBC).

Performance comparison (NMI) showing the effects of relation and entity constraints on clustering accuracy across different models.

As shown in the results, the addition of constraints significantly boosts accuracy. On the Rel-KB dataset, incorporating entity constraints improved the NMI from 0.69 to 0.85. The tripartite structure proved superior to tensors because it effectively pools information from both sides of a relation, making it more resilient to noise. Furthermore, the study demonstrates that constraints can be generated automatically using Named Entity Recognizers (NER), removing the need for manual human labeling.

Conclusion

CTGC provides a robust framework for identifying semantically similar relations by leveraging the structural context of entities and automated side information. By moving from 3D tensors to tripartite graphs and incorporating semi-supervised constraints, the model achieves high accuracy even in the presence of sparse and noisy data. Future work may involve exploring multi-hop relations and integrating deeper linguistic features to further refine relation clustering.

Summary updated

Abstract

In knowledge bases or information extraction results, differently expressed relations can be semantically similar (e.g., (X, wrote, Y) and (X, 's written work, Y)). Therefore, grouping semantically similar relations into clusters would facilitate and improve many applications, including knowledge base completion, information extraction, information retrieval, and more. This paper formulates relation clustering as a constrained tripartite graph clustering problem, presents an efficient clustering algorithm and exhibits the advantage of the constrained framework. We introduce several ways that provide side information via must-link and cannot-link constraints to improve the clustering results. Different from traditional semi-supervised learning approaches, we propose to use the similarity of relation expressions and the knowledge of entity types to automatically construct the constraints for the algorithm. We show improved relation clustering results on two datasets extracted from human annotated knowledge base (i.e., Freebase) and open information extraction results (i.e., ReVerb data).
BibTeX
@inproceedings{wang2015constrained,
  author = {Chenguang Wang and Yangqiu Song and Dan Roth and Chi Wang and Jiawei Han and Heng Ji and Ming Zhang},
  title = {{Constrained Information-Theoretic Tripartite Graph Clustering to Identify Semantically Similar Relations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure