Proper binary edge positional encoding for tree GNNs

First, integrate the construction during graph preprocessing, before batching. For every tree, root it arbitrarily and repeatedly identify the current leaves. Store one binary feature z_e on each edge and append d(v), q(v), and optionally s(v) to the initial node feature. Concatenate z_uv to each directed message in the first one or two GNN layers. Use a 3-layer GIN, GraphSAGE, or TreeLSTM so the comparison isolates the positional encoding. Second, construct the labels as follows. For each current leaf batch L adjacent to a surviving vertex v, let u be the other neighbor of v and enumerate j=0,1,...,k. Assign weight 2 to j leaf edges and weight 1 to the other k-j edges. Compute S_j=omega(uv)+(k-j)+2j. Accept the first assignment satisfying S_j != s_omega(u), S_j != 1 when j<k, and S_j != 2 when j>0. Remove the leaves and continue. For k=1 or k=2, try every binary assignment and directly verify all affected adjacent pairs; if a residual conflict remains, backtrack one leaf batch and retry. Finally verify s(u) != s(v) for every edge. The paper supplies the candidate-spacing guarantee and local forbidden-equality test. The implementation estimates no spectral or statistical quantities; it only computes degrees, incident binary counts, and weighted sums. The first experiment should generate random trees with 8 to 64 vertices and targets depending on depth, a distinguished branch, or subtree parity. Train the same GIN with no positional encoding, random fixed edge bits, Laplacian positional features, and the proposed proper labeling, using identical hidden size, optimizer, and parameter count. Evaluate ordinary test accuracy, accuracy after adversarially permuting symmetric branches, and accuracy with 1%, 10%, and 100% of the training data. The expected signal is improved discrimination of locally symmetric branches and higher low-data accuracy than unlabelled and random-edge baselines, with linear-time preprocessing and negligible inference overhead.