△ Mechanism confirmed, baseline not beaten 2026

Connectivity-Preserving Wedge Token Pooling

Implementation & benchmark of arXiv:2607.08806 — Tonnetz-Driven Graph Wedgelet for Harmonic Complexity Reduction in Music Scores

Usefulness6/10

Difficulty5/10

Novelty6/10

Architecture Memory Speedup Accuracy Graph nn Transformer Attention Memory Graph theory Combinatorics Approximation theory Metric geometry

Source paper: Tonnetz-Driven Graph Wedgelet for Harmonic Complexity Reduction in Music Scores arXiv:2607.08806 ⓘ · analyzed Aug 30, 2026

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

Idea description

Replace a large graph-token set by a smaller set of connected wedge regions generated through adaptive two-seed shortest-path partitions. Each pooled token is the mean of the node features in its region, while the binary partition tree and region sizes are retained for unpooling or skip connections. This provides a deterministic, graph-aware alternative to arbitrary token merging that can be inserted before graph-transformer message passing.

Formulas

$$A=\{v\in S\mid \operatorname{dist}(v,u)\leq \operatorname{dist}(v,w)\},\qquad B=\{v\in S\mid \operatorname{dist}(v,u)>\operatorname{dist}(v,w)\}.$$

$$\mu_R=\frac{1}{|R|}\sum_{v\in R}x_v,\qquad C(R)=\sum_{v\in R}\|x_v-\mu_R\|_2^2.$$

$$\Delta(S;u,w)=C(S)-C(A)-C(B),\qquad (S^*,u^*,w^*)=\arg\max_{S,u,w}\Delta(S;u,w).$$

$$\mathcal{W}_M x(v)=\sum_{i=1}^{M}\mu_{R_i}\,\mathbf{1}[v\in R_i].$$

Mathematical statement

For a connected graph G=(V,E) with shortest-path distance dist and a current connected region S subseteq V, choose distinct seeds u,w in S and define the wedge split A={v in S: dist(v,u)<=dist(v,w)} and B={v in S: dist(v,u)>dist(v,w)}. The paper states that shortest-path wedge children are connected subgraphs. For node features x_v in R^d, the least-squares constant approximation on a region R is its mean mu_R=(1/|R|) sum_{v in R} x_v, with residual cost C(R)=sum_{v in R} ||x_v-mu_R||_2^2. Select the candidate region and seed pair that maximizes the reduction C(S)-C(A)-C(B), and recursively split until M regions remain. The resulting pooled signal is W_M x(v)=sum_{i=1}^M mu_{R_i} 1[v in R_i], where {R_i} is the final partition and 1 is the indicator function. The explicit workhorse is the optimality of the mean for L2 piecewise-constant approximation, while shortest-path Voronoi splitting preserves graph connectivity.

Implementation notes

Integrate this as a graph-token pooling layer immediately before one or more graph-transformer blocks. The input is an adjacency list or sparse graph G, node features X in R^{n x d}, and target token count M<n. First compute shortest-path distances within candidate regions using multi-source BFS; for weighted graphs use Dijkstra. Initialize the partition with S=V. For every current region S eligible for splitting, sample or enumerate seed pairs (u,w), construct A and B by comparing distances, reject empty children, and compute the SSE cost C(S), C(A), and C(B). Store the candidate gain Delta=C(S)-C(A)-C(B). Split the region with the largest positive gain, update only affected candidates, and stop at M regions or when no positive gain remains. Emit pooled features mu_R, pooled adjacency by summing or averaging edges between regions, region sizes, and parent-child IDs for optional unpooling. During backpropagation, treat assignments as stop-gradient discrete routing; gradients to X pass through the regional means. The paper’s mathematics determines the wedge assignment and exact L2 gain. Engineering approximations include limiting each region to k seed pairs, using sampled BFS, and recomputing gains lazily. Begin with a 2-layer Graph Transformer on ogbn-arxiv or a symbolic-score graph task, retaining 25%, 50%, and 75% of nodes. Compare against random pooling, feature-space k-means, and top-score pooling at equal FLOPs. Success means lower attention memory and runtime with no more than 1% absolute accuracy loss, or higher accuracy at the same token budget; also verify that every output region is connected.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

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

Built deterministic greedy Connectivity-Preserving Wedge Token Pooling with exact restricted BFS distances, mean tokens, SSE-gain selection, connectivity validation, region sizes, split history, assignments, and pooled adjacency. The math checks passed: mean optimality had an absolute identity error of 1.4e-14, and 19,470 valid wedge splits across random connected graphs produced no disconnected children. On the toy graph, wedge pooling strongly beat random pooling in reconstruction SSE and preserved connectivity, but k-means was better at 4 and 8 tokens and wedge construction was substantially slower; therefore this is a promising graph-aware pooling MVP, not an established overall speed or accuracy win.

Agent confidence: 8/10

Baseline: Random pooling SSE: 23.985 (M=2), 23.078 (M=4), 21.679 (M=8); k-means SSE: 0.611, 0.356, 0.185. Random pooling time: 0.00021, 0.00029, 0.00044 s/call.
Idea: Wedge pooling SSE: 0.611 (M=2), 0.479 (M=4), 0.320 (M=8); construction time: 0.0665, 0.1254, 0.2241 s/call. Attention quadratic proxy was reduced to (M/24)^2: 0.00694, 0.0278, 0.1111. Connectivity checks passed for all tested target sizes.

Limitations: No graph-transformer training, real benchmark dataset, GPU implementation, weighted-graph Dijkstra, backward-gradient test, or direct attention memory/runtime measurement was performed. The toy graph is deliberately favorable to graph-aware partitioning, and the implementation recomputes candidate BFS distances rather than using incremental or sampled approximations.

How to run: python3 verify_math.py && /home/maxwelhelp/main/bin/python3 run_experiment.py

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

No significant difference vs. the tuned baseline (−-0.0%, p=1, wins 0 / 8 paired seeds).

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

Limitations:

This is a registered synthetic graph-context retrieval track, not a direct shortest-path wedge-partition graph-transformer benchmark. Real graph data, weighted Dijkstra, end-to-end differentiable routing, attention memory/runtime, k-means/top-score pooling, and larger graphs were not tested.

How to run: python3 /home/maxwelhelp/all/math2nn/bench/custom_tracks/graph_context_budget.py > registered_bench_stdout.json

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

Stage 2 — Benchmark Sep 4, 2026 latest Failed ✗

Agent confidence: 9/10

The registered graph_context_budget benchmark completed with the canonical mlp_tiny training path, a tuned baseline learning-rate sweep, and eight paired seeds. The baseline and anchored idea both achieved error 0.0418749985, with paired delta 0 and permutation p=1.0; the retained-evidence signature was confirmed, but there was no standard task-metric win.

Baseline: Best lr=0.003; 8-seed error mean 0.0418749985 ± 0.0060917456.
Comparison: delta_mean=0.0; idea_wins=0/8; p_value=1.0; verdict=no measurable effect.
Idea: Anchored mode lr=0.003; 8-seed error mean 0.0418749985.

Benchmark result