A density compensation-based path computing model for measuring semantic similarity

Xinhua Zhu, Fei Li, Hongchao Chen, Peng QiarXiv 2015 · DOI · arXiv

Abstract

Traditional edge-counting methods for measuring semantic similarity in taxonomic ontologies often fail to account for non-uniform concept densities. This paper proposes a novel path computing model based on local area density compensation. By adjusting the shortest path length between concepts using the number of direct hyponyms of their subsumers, the model addresses the non-uniformity problem inherent in large taxonomies like WordNet. Experimental results demonstrate that this model significantly improves the correlation with human judgments on the Miller and Charles (MC30) benchmark, increasing average correlation from below 0.8 to over 0.85. Furthermore, the model offers substantial efficiency advantages over Information Content (IC) methods, particularly in dynamic ontologies.

Introduction

In Natural Language Processing (NLP), determining the semantic similarity between concepts is a fundamental task. Taxonomic ontologies, such as WordNet, provide a structured hierarchy where the distance between nodes (concepts) can be used to estimate similarity. Historically, the "shortest path" or edge-counting method has been the default approach due to its simplicity and low computational cost.

However, large-scale taxonomies are rarely uniform. Some domains are modeled with high granularity (dense clusters), while others are sparse. A single edge in a dense region represents a smaller semantic difference than an edge in a sparse region. While Information Content (IC) methods address this by incorporating corpus-based statistics, they are computationally expensive and difficult to maintain in dynamic environments where the ontology updates frequently.

The Density Compensation Model

This research advocates for separating path computation from similarity algorithms, allowing for modular "path models" that can be plugged into various existing measures. The proposed model introduces a "density compensation" factor based on the local structure of the taxonomy.

The core formula for the compensated path is:

$$Path_{density} = |Edges| + \left( \frac{LocalAreaDensity}{AverageDepth} \right) \times \lambda$$

  • Edges: The raw count of steps between concepts.
  • Local Area Density: Calculated as the number of direct hyponyms (children) of the subsumers along the shortest path. This measures how "branchy" the local neighborhood is.
  • Average Depth: The depth of the concepts' common ancestor, reflecting that semantic distance decreases as concepts become more specific (deeper in the tree).
  • $\\lambda$ (Lambda): A tuning parameter (typically 0.3) that balances the influence of density compensation.

This approach aligns with information theory: as local density increases, the semantic "weight" of an edge changes, and as depth increases, the specificity of concepts reduces the relative impact of that density.

Experimental Evaluation

The model was evaluated using WordNet 3.0 against two primary benchmarks: the Miller and Charles (MC30) set and the Rubenstein and Goodenough (RG65) set. The researchers compared standard edge-counting versions of popular similarity measures (e.g., Rada et al., Leacock et al., Wu et al.) against versions using the proposed density-compensated path.

Comparison of correlation results between edge counting-based and edge weight-based path models on MC30 and RG65 benchmarks.

As shown in the experimental data above, the "Edge weight-based" model consistently improves correlation coefficients across nearly all tested measures. On the MC30 benchmark, the model helped push average correlation scores from the 0.75–0.80 range to over 0.85, nearing the human-to-human agreement threshold of 0.90.

Efficiency in Dynamic Ontologies

A critical advantage of this model is its performance in dynamic ontologies like DBpedia. Unlike IC-based methods that require a global "pretreatment" of the entire taxonomy—a process that can take hundreds of seconds—the density compensation model only requires local information. In tests, the proposed model was dozens of times faster, requiring zero pretreatment time while maintaining high accuracy.

Conclusion

The density compensation-based path model successfully bridges the gap between simple edge-counting and complex information-theoretic methods. By accounting for the "branchiness" of local taxonomic structures, it provides a high-accuracy, high-efficiency solution for semantic similarity tasks, particularly suited for modern, rapidly evolving knowledge bases.

Summary updated

Abstract

The shortest path between two concepts in a taxonomic ontology is commonly used to represent the semantic distance between concepts in the edge-based semantic similarity measures. In the past, the edge counting is considered to be the default method for the path computation, which is simple, intuitive and has low computational complexity. However, a large lexical taxonomy of such as WordNet has the irregular densities of links between concepts due to its broad domain but. The edge counting-based path computation is powerless for this non-uniformity problem. In this paper, we advocate that the path computation is able to be separated from the edge-based similarity measures and form various general computing models. Therefore, in order to solve the problem of non-uniformity of concept density in a large taxonomic ontology, we propose a new path computing model based on the compensation of local area density of concepts, which is equal to the number of direct hyponyms of the subsumers of concepts in their shortest path. This path model considers the local area density of concepts as an extension of the edge-based path and converts the local area density divided by their depth into the compensation for edge-based path with an adjustable parameter, which idea has been proven to be consistent with the information theory. This model is a general path computing model and can be applied in various edge-based similarity algorithms. The experiment results show that the proposed path model improves the average correlation between edge-based measures with human judgments on Miller and Charles benchmark from less than 0.8 to more than 0.85, and has a big advantage in efficiency than information content (IC) computation in a dynamic ontology, thereby successfully solving the non-uniformity problem of taxonomic ontology.
BibTeX
@misc{zhu2015density,
  author = {Xinhua Zhu and Fei Li and Hongchao Chen and Peng Qi},
  title = {{A density compensation-based path computing model for measuring semantic similarity}},
  year = {2015},
  eprint = {1506.01245},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.01245},
}
Figure