Technical Summary: Reference-Free Evaluation of Taxonomies

Problem Statement

Taxonomies are essential for organizing information, enabling hierarchical classification, enriching machine learning features, and improving zero-shot tasks. While traditionally created manually, the increasing volume of unstructured data has driven the development of automated taxonomy generation and extension methods.

The primary challenge in evaluating these automated methods is the lack of a "ground truth" taxonomy. Traditional evaluation relies on comparing generated taxonomies against a gold standard using metrics like Precision, Recall, and F1. However, if a ground truth existed, there would be no need to generate or extend the taxonomy in the first place. Existing reference-free metrics often fail to account for non-leaf mutations, overlook error severity, rely heavily on priors within backbone models, or ignore logical adequacy (e.g., whether a child concept is truly a subtype of its parent). Consequently, there is a need for robust, reference-free evaluation measures that can assess taxonomy quality without a gold standard.

Methodology

The authors propose two novel reference-free metrics targeting distinct aspects of taxonomy quality: Robustness and Logical Adequacy.

1. Robustness: Concept Similarity Correlation (CSC)

Robustness measures how well a taxonomy distinguishes between concepts and how closely related sibling concepts are.

• Limitation of Existing Metrics: Previous metrics like Semantic Proximity (SP) treat sibling groups as flat clusters, ignoring the hierarchical structure. They are insensitive to errors where non-leaf nodes are misplaced.
• Proposed Approach (CSC): The authors assume that in a high-quality taxonomy, semantic similarity and taxonomic similarity should be monotonically correlated.
  • Taxonomic Similarity: Calculated using Wu & Palmer Similarity (WPS), which considers the path length from the root and the depth of the Least Common Ancestor (LCA).
  • Semantic Similarity: Calculated using cosine similarity between concept embeddings (generated by sentence-transformers).
  • Metric: The Kendall rank correlation ($\tau$) between the semantic similarity scores and the taxonomic similarity scores across all pairs of concepts in the taxonomy. A high positive correlation indicates a robust taxonomy.

2. Logical Adequacy: NLI Verification (NLIV)

Logical adequacy assesses whether parent-child edges represent valid "is-a" relationships (hypernym-hyponym pairs).

• Approach: The metric treats the taxonomy as a graph where a classification is a walk from the root to a leaf. The quality of the taxonomy depends on the probability that these walks are logically valid.
• Edge Probability Estimation: The authors use Natural Language Inference (NLI) models in a zero-shot setting to estimate the probability that a parent-child edge is valid.
  • Prompting: For an edge $\langle c_i, c_{i+1} \rangle$, a premise is constructed using the child's description ($D(c_{i+1})$) and the hypothesis is the relationship statement (e.g., "$c_{i+1}$ is a type of $c_i$").
  • Variants:
    • NLIV-S (Strong): The premise must entail the hypothesis.
    • NLIV-W (Weak): The premise must not contradict the hypothesis.
  • Hearst Patterns: To improve robustness, the authors average estimates over multiple Hearst pattern templates (e.g., "is a kind of," "is an example of").
• Aggregation: The adequacy of the whole taxonomy is calculated as the geometric mean of edge probabilities across random classification walks, weighted to ensure errors at higher levels (affecting more descendants) impact the score more significantly than leaf errors.

Experimental Setup

The authors evaluated these metrics on five taxonomies across diverse domains (Food, Verbs, Medical terms, Wikidata, and a proprietary recipe taxonomy).

• Intrinsic Evaluation: Ground truth taxonomies were artificially degraded by randomly relocating sub-graphs (mutating 2% to 32% of nodes). The proposed metrics were compared against the resulting F1 score (against the original) and existing metrics (SP, RaTE).
• Extrinsic Evaluation: The metrics were tested on their ability to predict downstream performance in hierarchical classification tasks (Web of Science, MN-DS, DBPedia). Label taxonomies were degraded, and the resulting drop in macro F1 classification performance was correlated with the reference-free metric scores.

Key Results

• Correlation with Ground Truth: The proposed metrics (CSC and NLIV-S) demonstrated strong correlations with F1 scores against ground truth taxonomies, outperforming existing metrics like SP and RaTE. Notably, SP failed to detect mutations in non-leaf nodes, whereas CSC and NLIV were sensitive to both leaf and non-leaf errors.
• Downstream Prediction: In extrinsic evaluation, CSC and NLIV metrics showed substantial association with downstream hierarchical classification performance. In contrast, SP showed negative or weak correlations, and RaTE often failed to predict performance on certain datasets (e.g., DBPedia) without domain-specific fine-tuning.
• Sensitivity Analysis:
  • Realistic Errors: When mutations were restricted to semantically similar concepts (top 100 WPS neighbors), NLIV metrics maintained high correlation, while CSC correlation decreased (as expected, since CSC measures global shape).
  • Model Stability: The metrics showed high consistency (Kendall's $\tau$) when using different backbone models for embeddings and NLI, suggesting the ranking of taxonomies remains stable across model choices.
  • Input Perturbation: The metrics remained robust when concept names were replaced with synonyms, though NLIV metrics showed slightly higher sensitivity to input changes compared to CSC.

Significance and Claims

The paper claims to introduce the first reference-free metrics that effectively evaluate both the structural robustness and logical validity of taxonomies without requiring a gold standard.

• Domain Independence: The approach is designed to be domain-independent, relying on pre-trained language models rather than domain-specific heuristics.
• Error Detection: Unlike prior work, these metrics can detect errors in non-leaf nodes and verify the logical validity of parent-child relationships, which is critical for automatically generated taxonomies.
• Practical Utility: The authors demonstrate that these metrics can serve as a proxy for taxonomy quality, predicting how well a taxonomy will perform in downstream hierarchical classification tasks.
• Future Application: The authors suggest these metrics can be used to compare alternative taxonomies, pinpoint individual errors (by identifying unlikely classification walks or high semantic-taxonomic disagreement), and potentially serve as optimization objectives for taxonomy generation algorithms.

The authors remain modest regarding limitations, noting that while the metrics are domain-independent, the underlying pre-trained models are not, potentially introducing biases. They also caution that scores are not directly comparable across different concept spaces due to varying baseline model performances.