Approximation of trees by self-nested trees

Romain Azaïs, Jean-Baptiste Durand, Christophe Godin

TL;DR

This paper introduces "self-nested trees," a highly redundant tree structure that allows for significant compression and faster query processing. The authors develop an algorithm to approximate general trees with these self-nested trees, enabling rapid prediction of tree edit distances, a crucial operation in fields like computational biology.

What Problem Does This Paper Address?

Comparing and analyzing complex tree structures, such as those representing biological data (e.g., RNA secondary structures) or XML documents, often involves computationally expensive operations like calculating edit distance or performing recursive queries. While some tree structures exhibit high redundancy, leading to efficient algorithms, general trees can be quite complex. This paper addresses the challenge of efficiently processing general trees by proposing a method to approximate them with a special class of trees called "self-nested trees." These self-nested trees, characterized by systematic subtree repetition, offer excellent compression and algorithmic properties, making them ideal for speeding up computations on more complex, general trees.

Methods

The core of the paper revolves around the concept of self-nested trees and an approximation algorithm to transform general trees into this form.

  • Self-Nested Trees: The paper defines self-nested trees as those where all subtrees of the same height are isomorphic. This property leads to significant structural redundancy. A key theoretical result (Proposition 1) links self-nested trees to "linear DAGs" (Directed Acyclic Graphs), where the DAG reduction of the tree forms a single path.
  • Tree Reduction: The authors utilize a "tree reduction" process, which transforms a tree into a DAG that captures its essential structure while removing redundancies. This DAG representation is crucial for analyzing and manipulating the trees.
  • Approximation Algorithm (Averaging Method): The paper proposes an "averaging" algorithm to construct a self-nested tree that best approximates a given general tree. This algorithm aims to match the "height profile" of the original tree by calculating weighted averages of subtree distributions. This is presented as an alternative to existing "Nearest Embedding Self-nested Tree" (NEST) methods, claiming better approximation errors and faster computation.
  • Edit Distance Prediction: The approximation algorithm is then applied to predict tree edit distances. Instead of directly computing the edit distance between two large trees, the authors compute the edit distance between their self-nested approximations and use a learned model to predict the original edit distance.

Datasets

The paper describes simulations performed on randomly generated trees.

  • Random General Trees: Generated by iteratively adding a child to a randomly chosen vertex.
  • Random Self-Nested Trees: Generated by creating random linear DAGs, which correspond to self-nested trees.

The authors generated datasets for numerical experiments, including 40,000 random trees (half self-nested) for compression analysis, 40,000 random trees for bottom-up function evaluation, and 20,000 pairs of random trees for edit distance computation. They also mention a training dataset of 2,500 replicates of edit distances for learning a prediction model.

Key Insights and Ideas

  • Self-nested trees are exponentially rare but computationally powerful: Despite being very infrequent compared to general trees, their high redundancy makes them exceptionally efficient for various computational tasks. This rarity is highlighted as a potential advantage in exhaustive search problems.
  • DAG reduction is key to efficiency: The paper emphasizes that representing trees as DAGs (through tree reduction) is fundamental to achieving computational gains, especially for self-nested trees.
  • Approximation offers a practical shortcut: The core idea is that approximating a complex tree with a simpler, self-nested one can drastically speed up computations like edit distance calculation, even if the approximation isn't perfect.
  • Averaging method outperforms NEST: The proposed "averaging" approximation algorithm is shown to achieve better approximation errors and significantly faster computation times compared to the existing NEST method.
  • Edit distance prediction is feasible and effective: By combining self-nested tree approximation with a learned model, the paper demonstrates a way to predict edit distances much faster than direct computation, with a learning-corrected predictor achieving high accuracy.

Key Results

  • Compression: Self-nested trees achieve significantly higher compression rates (around 0.3%) compared to general trees (around 10%) when stored on disk.
  • Bottom-up Recursive Functions: Computing bottom-up functions (like counting vertices) is approximately 4 times faster from a linear DAG (self-nested tree) than from a general DAG reduction, and nearly 20 times faster than from the original tree.
  • Edit Distance:
    • Computing edit distance from self-nested tree approximations is significantly faster than from general trees. For trees of size 1000, it's about 10 times faster.
  • The averaging approximation method shows substantially better approximation errors (around 30 times lower) and computation times (around 50 times lower) compared to the NEST method.
  • A learned predictor for edit distance, using self-nested approximations and additional tree features, achieves an average error of 0% with a small variance (within ±6.5% to 6.9% in 50% of cases).
  • Combinatorics: Self-nested trees are exponentially less frequent than general trees, with their frequency decreasing rapidly as height and outdegree increase.

Limitations and Future Work

  • Worst-case error bound: While the averaging algorithm performs well on average, there's a theoretical worst-case scenario where the approximation error for edit distance can be exponential. The paper highlights this theoretical limitation, though notes it's far from the average behavior.
  • Learning model reliability: The initial linear model for edit distance prediction without additional features showed high variance, making it unreliable. While adding features improved this, the variance still exists.
  • Future Work: The paper suggests investigating the cardinality of self-nested trees of a given size, which remains a difficult combinatorial problem. Further exploration of the "worst-case" scenarios for approximation could also be a direction.

Summary updated

Abstract

The class of self-nested trees presents remarkable compression properties because of the systematic repetition of subtrees in their structure. In this paper, we provide a better combinatorial characterization of this specific family of trees. In particular, we show from both theoretical and practical viewpoints that complex queries can be quickly answered in self-nested trees compared to general trees. We also present an approximation algorithm of a tree by a self-nested one that can be used in fast prediction of edit distance between two trees.
BibTeX
@inproceedings{azais2018approximation,
  author = {Romain Azaïs and Jean-Baptiste Durand and Christophe Godin},
  title = {{Approximation of trees by self-nested trees}},
  booktitle = {HAL},
  year = {2018},
  doi = {10.48550/arxiv.1810.10860},
}

Loading related content...

Figure