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.
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:
- Rel-KB: A "gold standard" dataset derived from Freebase containing 16,516 relation expressions across six categories.
- 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).
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