4.7

Trees: Etree and the assignment relaxation

A storyboard of the three edit operations turning a predicted tree into the ground truth
The three edits: contract an edge (merge its two links), substitute the joint on an edge, expand a link into two joined by a new joint. Every cost is an E value, and the welded joint J₀ is the reference for contraction and expansion.

An object is a tree with links as nodes and joints on the edges, and the same object admits many trees: parts can be relabeled, the base re-chosen, a handle welded to a drawer or split off. The tree metric is the cheapest sequence of edits from one tree to the other, Etree(T₁, T₂) = infπ Σo∈π c(o), with substitution costing E(J, J′) and contraction or expansion costing E(J, J₀). A spurious joint that barely moves costs ε‖ξ‖, not a constant penalty, so topology errors and joint errors are priced in the same motion currency and the metric is continuous through the welded boundary. Exactly fixed edges are contracted first (contract_small_edges) because they are representation noise.

A path and a star with the same joint multiset, where the relaxation and the exact distance differ
The two trees carry the same three joints, so the assignment relaxation pairs them one-to-one at zero cost. No tree isomorphism realizes that pairing, so the exact edit distance is positive.

Any edit sequence can be reordered into contract, then substitute along a tree isomorphism, then expand. The exact distance is therefore a minimum over matchings of the edge sets that extend to an isomorphism of the contracted trees. Dropping that realizability condition gives the assignment relaxation: a Hungarian matching over the joint multisets with E(J, J₀) as the unmatched cost (assignment_tree_distance). It is always a lower bound, it is polynomial for any input, and it needs only the multiset of predicted joints. Whenever its optimal matching happens to be realizable, checked in linear time by matching_realizable, the relaxation certifies the exact value. exact_tree_distance returns (distance, certified) and falls back to a small constrained search otherwise.

Exact versus relaxed, in numbers. On the tree ablation the certificate settles 91 % of random corruptions, exact and relaxed agree on 92 %, they agree on every structured sweep, and their rankings correlate at τ = 0.994. The paper states the protocol with the relaxation because unordered tree edit distance is NP-hard in the worst case and because some methods emit joints without a usable tree. The reported tree score is the exact one wherever a tree is available.
Why not a constant topology penalty λ. It jumps by λ the moment a joint appears, is capped at 2λ once unmatching becomes cheaper than matching, and the forced-matching variant escapes the cap only by breaking the triangle inequality. Motion-priced edits have no knob and none of these failures.
The per-link weighting and the metric proof. With one fixed inner product Etree is a metric on representation-equivalence classes. With the kinetic-energy norm instantiated per ground-truth link, contraction and expansion change which body weighs which joint, so that variant is used as a score without the metric claim.