Abstract
Taxonomy induction is a critical task in Natural Language Processing, yet the impact of specific organizational constraints—such as transitivity and synonymy—is often obscured by the end-to-end nature of existing systems. This paper presents a controlled comparison of six algorithms for taxonomic organization. We find that while transitive models offer high accuracy, they suffer from extreme computational overhead. In contrast, a simpler tree-based approach augmented with synonym clustering (DMST+Clus) achieves comparable performance with a 6,800-fold increase in speed, suggesting that explicit synonym handling is a more efficient path to structural coherence than complex global constraints.
Introduction
Building a taxonomy—a hierarchical map of concepts where, for example, a "car" is a type of "vehicle"—is foundational for structured knowledge representation. The process typically follows a three-stage pipeline: entity extraction, relation prediction, and taxonomic organization. Most research evaluates these stages in tandem, making it difficult to determine whether performance gains stem from better relation scores or superior organizational logic. This study isolates the third step, evaluating how mathematical constraints like "no cycles" or "transitivity" influence the quality of the final taxonomy.
Methodology: Isolating Organizational Constraints
The researchers compared six algorithms across three primary dimensions: transitivity, graph structure (DAG vs. Tree), and synonymy handling. The algorithms range from basic cycle-breaking (NoCyc) and Directed Maximum Spanning Trees (DMST) to sophisticated Integer Linear Programming (ILP) models (MaxTransGraph and MaxTransForest) that enforce transitivity.
A key contribution is the introduction of DMST+Clus. This method utilizes a standard, non-transitive tree algorithm (Chu-Liu-Edmonds) but adds a pre-processing step to collapse predicted synonyms into single nodes (clusters). This approach aims to capture the structural benefits of complex models without their NP-hard computational costs.
Key Insights: The Power of Simplicity
The evaluation, conducted using WordNet 3.0 as a gold standard and HypeNET for initial relation scores, revealed several critical trade-offs:
- The Efficiency Wall: Transitive models like
MaxTransForestare logically consistent but prohibitively slow. In tests with just 50 entities,MaxTransForesttimed out (exceeding 5 minutes) on 24% of cases. - The Synonymy Advantage: Explicitly handling synonyms proved more impactful than enforcing complex transitivity. By collapsing Strongly Connected Components (SCCs) into single nodes, algorithms can resolve logical contradictions early.
- Robustness to Noise: Interestingly, transitive models were found to be more sensitive to errors in the initial relation prediction phase. A single incorrect "is-a" link can force a transitive model to make multiple erroneous inferences to maintain consistency.
Results and Performance
In terms of accuracy, MaxTransForest achieved the highest F1-score (0.21), but DMST+Clus followed closely at 0.20. The real differentiator was runtime: DMST+Clus averaged 0.02 seconds per taxonomy, making it approximately 6,800 times faster than the 136.83-second average of MaxTransForest.
Conclusion
This "apples-to-apples" comparison demonstrates that for practical taxonomy induction, complex global constraints may not be necessary. The success of DMST+Clus suggests that future research should prioritize high-quality synonym detection and local clustering. While absolute F1-scores remain low—highlighting the difficulty of the task—this work provides a clear roadmap for building scalable, efficient taxonomic systems.
Summary updated