✓✓ Beats tuned baseline 2026

Branch-Length Polynomial Fingerprint

Implementation & benchmark of arXiv:2607.06591 — Polynomial encoding of rooted trees with branch lengths

Usefulness6/10

Difficulty4/10

Novelty7/10

Architecture Accuracy Sample efficiency Graph nn Embedding Architecture Combinatorics Algebra Graph theory Approximation theory

Source paper: Polynomial encoding of rooted trees with branch lengths arXiv:2607.06591 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Add a deterministic, branch-length-aware fingerprint to a rooted-tree neural encoder using the paper's symmetric product recursion. The fingerprint distinguishes child multisets structurally and incorporates every edge length, providing information that ordinary sum or mean message passing can lose.

Formulas

$$P(v;x,y)=x\quad\text{if }v\text{ is a leaf},$$

$$P(v;x,y)=\prod_{i=1}^{k}\bigl(w_i y+P(v_i;x,y)\bigr)\quad\text{if }v\text{ has children }v_1,\ldots,v_k,$$

$$P(B)=\prod_{i=1}^{k}(w_i y+P(B_i))=\prod_{i=1}^{k}\left(w_i y+\sum_{S\in\mathcal{S}_{B_i}}q(S)\right),$$

$$\phi(B)=\bigoplus_{m=1}^{M}\left(\log\left|P(B;x_m,y_m)\right|,\arg P(B;x_m,y_m)\right),\qquad P(v;x_m,y_m)=\prod_{i=1}^{k}\left(w_i y_m+P(v_i;x_m,y_m)\right).$$

Mathematical statement

For a rooted tree with positive edge lengths, let P(v;x,y) be the recursively computed polynomial at vertex v, where x and y are formal variables. At a leaf v, P(v;x,y)=x. If v has children v_1,...,v_k and edge length w_i>0 from v to v_i, define P(v;x,y)=\prod_{i=1}^{k}(w_i y+P(v_i;x,y)); the root value is P(B;x,y). For an unweighted tree T, the paper gives P(T,x,y)=L(T,x+y,y)-y, where L(v,x,y)=x at leaves and L(v,x,y)=y+\prod_i L(v_i,x,y) at internal vertices. The paper proves that, for rooted trees with no degree-two vertices, P(B_1;x,y)=P(B_2;x,y) as polynomials if and only if the underlying rooted trees are isomorphic and corresponding edge lengths are equal. In a neural implementation, evaluate the polynomial at M pairs (x_m,y_m), with x_m,y_m chosen constants or learned global scalars. The resulting values z_m=P(root;x_m,y_m) form a compressed fingerprint; for positive real evaluations use log z_m, and for signed or complex evaluations use (log|z_m|, arg z_m).

Implementation notes

Integrate the feature at the root of a rooted-tree encoder, immediately before the root classifier or before the global pooling output of a TreeLSTM or graph neural network. The input is a rooted tree with child lists and positive edge lengths w_i. Choose M=8 initially; use fixed pairs x_m=1 and y_m sampled once from signed values such as {-2,-1,-0.5,0.5,1,2}, or use complex points y_m=r_m exp(i theta_m) if complex arithmetic is convenient. Compute bottom-up: (1) for every leaf v and every m set z[v,m]=x_m; (2) for every internal v, initialize z[v,m]=1 and multiply z[v,m] by w_i*y_m+z[v_i,m] for each child; (3) use the numerically stable representation logabs[v,m]=sum_i logabs(w_i*y_m+z[v_i,m]) and phase[v,m]=sum_i angle(w_i*y_m+z[v_i,m]); (4) concatenate the root's 2M values, standardize them over the training set, and concatenate them with the learned root embedding. If only real positive points are used, logabs alone is sufficient but less discriminative; signed or complex points reduce accidental collisions. The exact mathematical computation is the product recursion and its completeness guarantee; the finite evaluation grid, normalization, and projection to a fixed-width feature are engineering approximations. Do not backpropagate through tree topology, but allow gradients through edge lengths if they are learned or estimated, and optionally learn a small affine layer after the fingerprint. The first experiment should use synthetic rooted trees with 10-50 leaves and random positive branch lengths, plus a real phylogenetic classification dataset if available. Compare TreeLSTM and message-passing GNN baselines using sum, mean, and max aggregation against identical models augmented with M=8 polynomial fingerprints. Measure tree-isomorphism classification, branch-length perturbation discrimination, root-label accuracy at equal parameter count, and calibration under edge-length noise. Success is a statistically significant increase in topology/branch-length accuracy or reduced training examples, while monitoring overflow, fingerprint collision rate, and whether the feature remains useful at held-out evaluation points.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Implemented the branch-length polynomial recursion and an M=8 log-magnitude fingerprint in a reusable module. The sanity check showed an exact ordinary-sum collision between two different rooted topologies, while polynomial evaluations differed by up to 49.32; classification accuracy was 0.50 for the baseline versus 1.00 with the fingerprint, and 0.9417 on an independent evaluation grid. This is a clear toy-level win, though not yet evidence for a full neural-encoder improvement.

Agent confidence: 8/10

Baseline: Ordinary scalar sum: exact collision; classification accuracy 0.5000
Idea: M=8 polynomial log-magnitude fingerprint: accuracy 1.0000 on fixed evaluation points, 0.9417 on held-out evaluation points; maximum raw polynomial separation 49.32

Limitations: Only synthetic rooted trees and a scalar logistic-regression probe were tested; no TreeLSTM/GNN integration, real phylogenetic dataset, parameter-matched neural baseline, noise calibration, GPU benchmark, complex-valued features, or large-scale overflow study was performed.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.06591) Sep 4, 2026

Beats the tuned baseline by 100.0% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Rooted_tree_branch_classification
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 0.4762
Idea mean: 0
Effect (Δ): -0.4762 (−100.0%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±8.1%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

The custom fixed-size six-node synthetic track is not a real phylogenetic dataset; no variable-size trees, TreeLSTM/GNN architecture, complex evaluations, calibration under edge noise, or larger-scale overflow study was tested.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 4, 2026 latest Worked ✓

Agent confidence: 8/10

Built a structurally matched custom rooted-tree classification track and paired MLP systems using the canonical benchmark training loop. The M=8 branch-length polynomial fingerprint achieved mean test error 0.0000 versus 0.47625 for the tuned baseline; all 8 paired differences favored the idea and the permutation p-value was 0.0081. The trained-model signature confirmed the predicted mechanism, with output-distance ratio 4.9185.

Baseline: Best lr=0.003; 8-seed mean test error 0.47625, std 0.04292.
Idea: Best lr=0.010; 8-seed mean test error 0.00000, std 0.00000; paired delta=-0.47625, p=0.0081, 8/8 wins.

Benchmark result