# Branch-Length Polynomial Fingerprint

- ID: 485
- Canonical URL: https://synthcore.org/idea/485/branch-length-polynomial-fingerprint
- API JSON: https://synthcore.org/api/idea/485.json
- API Markdown: https://synthcore.org/api/idea/485.md
- Verification status: beats_baseline
- Source: [arXiv:2607.06591](https://arxiv.org/abs/2607.06591)
- Category: architecture
- Solves: accuracy, sample-efficiency
- ML areas: graph-nn, embedding, architecture
- Math tags: combinatorics, algebra, graph-theory, approximation-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## 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.

## 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).

## Key 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).$$

## 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

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/1355/bench_report.json)
- [experiment.py](https://synthcore.org/code/1355/experiment.py)
- [fingerprint.py](https://synthcore.org/code/1355/fingerprint.py)
- [report.md](https://synthcore.org/code/1355/report.md)
- [report_bench_2026-09-04T170605.md](https://synthcore.org/code/1355/report_bench_2026-09-04T170605.md)
- [stage2_bench.py](https://synthcore.org/code/1355/stage2_bench.py)
- [tree_polynomial_track.py](https://synthcore.org/code/1355/tree_polynomial_track.py)
- [Download all files as ZIP](https://synthcore.org/download/1355)

## Disclaimer

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