# An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs

arXiv: https://arxiv.org/abs/2108.00953 · HTML: https://mlsanity.com/paper/2108.00953/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 18 references that are in the map.
- First posted on arXiv 26 Jul 2021.

## Builds on (most cited first, 1 of 1)

- [Tree Edit Distance Learning via Adaptive Symbol Embeddings](https://mlsanity.com/paper/1806.05009/) (2018)

## Built on by (most cited first, 1 of 1)

- [StructRe: Rewriting for Structured Shape Modeling](https://mlsanity.com/paper/2311.17510/) (2023)

## Abstract (arXiv)

The unordered tree edit distance is a natural metric to compute distances between trees without intrinsic child order, such as representations of chemical molecules. While the unordered tree edit distance is MAX SNP-hard in principle, it is feasible for small cases, e.g. via an A* algorithm. Unfortunately, current heuristics for the A* algorithm assume unit costs for deletions, insertions, and replacements, which limits our ability to inject domain knowledge. In this paper, we present three novel heuristics for the A* algorithm that work with custom cost functions. In experiments on two chemical data sets, we show that custom costs make the A* computation faster and improve the error of a 5-nearest neighbor regressor, predicting chemical properties. We also show that, on these data, polynomial edit distances can achieve similar results as the unordered tree edit distance.