High-Degree Jordan Anchor
Implementation & benchmark of arXiv:2607.18201 — Finding Adam in noisy trees
Source paper: Finding Adam in noisy trees arXiv:2607.18201 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Preprocess a noisy input graph into a high-degree core and compute a Jordan-center anchor in that core. Feed each node its distance to the anchor, and optionally use the anchor to bias graph-transformer attention; the hypothesis is that this suppresses spurious low-degree noise and gives the network a stable global coordinate system.
Formulas
Mathematical statement
The paper models the offspring count of vertex i by X_i=\sum_{j=i}^{n}B_j, where B_j are independent Bernoulli random variables with P(B_j=1)=1/j. It keeps vertices whose degree or offspring count exceeds the threshold (1-\alpha)\log n, using the truncated variable \xi_v=X_v\mathbf{1}_{\{X_v>(1-\alpha)\log n\}}. Lemma 3.12 states that the size of the retained forest is stochastically dominated by a Bienaymé-Galton-Watson tree with offspring distribution \xi_v, while Proposition 3.11 bounds the relevant connected component size by n^{\alpha'} with probability tending to zero for any \alpha'>\alpha. We adapt only the structural principle: for an observed graph G=(V,E), define H_ au=G[\{v:d_G(v)\ge au\}], retain its largest connected component C, and select a Jordan center a\in\arg\min_{u\in C}\max_{v\in C}d_C(u,v). Here d_G and d_C are shortest-path distances, au is a degree threshold, and a is the anchor. The neural feature is the normalized distance r_v=d_G(v,a)/(1+\max_{u\in V}d_G(v,a)).
Implementation notes
1. Integration point: apply this to each training graph before the graph encoder. For a graph with adjacency list E and node features x_v, compute degrees d_G(v), construct the induced subgraph H_tau using tau equal to a fixed degree quantile (start with the 75th percentile, and also test tau=(1-alpha)log(|V|+1) when graph degrees have a tree-like scale), and retain its largest connected component C. Compute shortest-path distances inside C from every candidate u, choose the candidate minimizing the maximum distance to C, and use it as anchor a. For disconnected or empty cores, fall back to the ordinary graph medoid or the highest-degree node. 2. Pseudocode: deg=degree(G); S={v:deg[v]>=tau}; H=induced_subgraph(G,S); C=largest_component(H); for u in C: ecc[u]=max_shortest_path_distance(C,u); a=argmin(ecc); dist=multi_source_bfs(G,[a]); r=dist/(1+max(dist)); x_v=MLP([x_v,r_v,1[v==a]]); in a graph transformer, add an attention-logit bias b_uv=-lambda*abs(r_u-r_v) or concatenate r_u,r_v to the attention input. 3. Mathematics computed exactly: induced-core construction, connected components, shortest-path distances, and Jordan eccentricity. The paper's probability model is not assumed for arbitrary datasets; estimate robustness empirically by injecting random edge additions/deletions and measuring whether the anchor remains close to the clean anchor. 4. First experiment: use Cora, CiteSeer, and synthetic stochastic-block-model graphs with 5%, 10%, and 20% random edge noise. Compare a 3-layer GIN and a small Graph Transformer with standard features against the same models augmented by r_v and the anchor indicator. Track node-classification accuracy, accuracy degradation under noise, anchor displacement from the clean graph, preprocessing time, and ablations for degree threshold, Jordan center, highest-degree anchor, and random anchor. Success means at least 1-2 percentage points higher noisy accuracy or substantially smaller degradation at equal model size, without excessive preprocessing cost.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.