# Connectivity-Preserving Wedge Token Pooling

- ID: 594
- Canonical URL: https://synthcore.org/idea/594/connectivity-preserving-wedge-token-pooling
- API JSON: https://synthcore.org/api/idea/594.json
- API Markdown: https://synthcore.org/api/idea/594.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.08806](https://arxiv.org/abs/2607.08806)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: graph-nn, transformer, attention, memory
- Math tags: graph-theory, combinatorics, approximation-theory, metric-geometry
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

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

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

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

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

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

### Mechanism check

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

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_output.json](https://synthcore.org/code/1403/bench_output.json)
- [bench_report.json](https://synthcore.org/code/1403/bench_report.json)
- [graph_wedge_bench.py](https://synthcore.org/code/1403/graph_wedge_bench.py)
- [registered_bench_stdout.json](https://synthcore.org/code/1403/registered_bench_stdout.json)
- [report.md](https://synthcore.org/code/1403/report.md)
- [report_bench_2026-09-04T202228.md](https://synthcore.org/code/1403/report_bench_2026-09-04T202228.md)
- [run_experiment.py](https://synthcore.org/code/1403/run_experiment.py)
- [verify_math.py](https://synthcore.org/code/1403/verify_math.py)
- [wedge_pool.py](https://synthcore.org/code/1403/wedge_pool.py)
- [Download all files as ZIP](https://synthcore.org/download/1403)

## Disclaimer

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