# Resolving Landmark Bottleneck

- ID: 421
- Canonical URL: https://synthcore.org/idea/421/resolving-landmark-bottleneck
- API JSON: https://synthcore.org/api/idea/421.json
- API Markdown: https://synthcore.org/api/idea/421.md
- Verification status: beats_baseline
- Source: [arXiv:2607.05152](https://arxiv.org/abs/2607.05152)
- Category: memory
- Solves: memory, scalability, accuracy
- ML areas: graph-nn, attention, memory
- Math tags: combinatorics, probability, graph-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Compress a directed graph into a small set of landmark vertices while guaranteeing that every node receives a distinct restricted adjacency signature. Use these signatures as structural positional features and as the only graph-to-token interface for a graph transformer, reducing landmark-mediated connectivity from O(n^2) to O(ns).

## Mathematical statement

For a directed graph D=(V,A) with n=|V|, let N^-(u) be the in-neighborhood of vertex u and let c be a lower bound on |N^-(u)    riangle N^-(v)| for every distinct pair u,v, where     riangle is symmetric difference. A landmark set S of size s distinguishes u and v when N^-(u)\cap S
eq N^-(v)\cap S; equivalently, the binary signatures z_u=(1[x\in N^-(u)])_{x\in S} and z_v differ. The paper bounds the collision probability for a uniformly sampled fixed-size S by P(u,v)\leq {n-c\choose s}/{n\choose s}. If N is the number of indistinguished unordered vertex pairs, then E[N]\leq {n\choose 2}{n-c\choose s}/{n\choose s}. Therefore, whenever this expectation is below 1, at least one resolving set exists; the paper uses s=\lceil 2n\log n/c\rceil under c>2\log n as a sufficient scale. The implementation exploits the same hypergeometric collision bound, while allowing greedy landmark swaps to improve task utility.

## Key formulas

- $$P(u,v)\leq\binom{n-c}{s}\middle/\binom{n}{s}$$
- $$\mathbb{E}[N]=\sum_{\{u,v\}}P(u,v)\leq\binom{n}{2}\binom{n-c}{s}\middle/\binom{n}{s}$$
- $$s=\left\lceil\frac{2n\log n}{c}\right\rceil,\qquad |N^-(u)\triangle N^-(v)|\geq c$$
- $$z_v\in\{0,1\}^{s},\qquad (z_v)_j=\mathbf{1}\{\ell_j\in N^-(v)\},\qquad h_v=\operatorname{MLP}([x_v,z_v])$$

## Implementation notes

1. Integration point: use this before or at the input stage of a graph transformer or message-passing GNN. Given a directed graph with node features x_v and adjacency lists, select s landmarks L={\ell_1,...,\ell_s}; do not build the full n-by-n attention matrix. For every node v, construct its binary landmark signature z_v[j]=1 if there is an edge \ell_j    o v, or use a weighted variant z_v[j]=A_{\ell_j,v}. Concatenate z_v, or a learned projection of z_v, to x_v before the first GNN layer. 2. Pseudocode: estimate c_hat as the minimum, over sampled node pairs (u,v), of |N^-(u)    riangle N^-(v)|; set s=min(n, ceil(2*n*log(n)/max(c_hat,1))); sample s vertices uniformly without replacement; compute all z_v by scanning incoming adjacency lists; encode h_v=MLP([x_v,z_v]); run the downstream transformer on h_v. Measure the empirical collision count C=sum_{u<v} 1[z_u=z_v]. If C>0, add landmarks greedily: for each candidate q, count currently colliding pairs whose neighborhood membership differs at q, select the best candidate, and update signatures. Stop when C=0 or the landmark budget is exhausted. 3. Computed from the paper are the fixed-size sampling rule, hypergeometric collision probability, expected-collision diagnostic, and n log n/c landmark scale. Estimated empirically are c_hat, collision count, and task-optimal greedy additions; on large graphs estimate c_hat from 10,000 random pairs. 4. First experiment: use ogbn-arxiv or a directed stochastic block model with n=5k-50k, comparing full Graphormer-style structural attention against uniform landmarks, degree-centrality landmarks, and the resolving-landmark rule, with s in {sqrt(n), 2sqrt(n)log n, 4sqrt(n)log n}. Train the same 3-layer encoder for node classification. Record accuracy, signature collision rate, peak memory, preprocessing time, and training throughput. Success means near-baseline accuracy with at least 2x lower peak memory or substantially higher nodes per second; the prediction is that collision rate drops sharply near the estimated 2n log(n)/c_hat scale.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a directed stochastic-block MVP implementing binary incoming-neighborhood landmark signatures, greedy collision-resolving landmark selection, the hypergeometric bound check, and a fixed-budget classifier comparison. Monte Carlo pairwise collision probabilities matched the exact formula closely; collision counts decreased sharply with landmark budget, and greedy landmarks achieved zero collisions using 39 landmarks versus uniform sampling requiring roughly 96-128 in this graph. The proposed structural bottleneck reduction is supported, but the task experiment showed no accuracy win: greedy accuracy was 0.756 versus 0.789 for degree landmarks and 0.761 for uniform landmarks.

### Mechanism check

- Verdict: Built a directed stochastic-block MVP implementing binary incoming-neighborhood landmark signatures, greedy collision-resolving landmark selection, the hypergeometric bound check, and a fixed-budget classifier comparison. Monte Carlo pairwise collision probabilities matched the exact formula closely; collision counts decreased sharply with landmark budget, and greedy landmarks achieved zero collisions using 39 landmarks versus uniform sampling requiring roughly 96-128 in this graph. The proposed structural bottleneck reduction is supported, but the task experiment showed no accuracy win: greedy accuracy was 0.756 versus 0.789 for degree landmarks and 0.761 for uniform landmarks.
- Confidence: 8/10
- Limitations: Only a 600-node synthetic directed stochastic-block graph and a small MLP classifier were tested; no Graphormer, ogbn-arxiv, large-scale memory benchmark, GPU benchmark, weighted signatures, multiple random seeds, or rigorous accuracy comparison across datasets was performed. The theoretical c was computed exactly rather than estimated from sampled pairs.

### 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/1294/bench_report.json)
- [graph_landmark_track.py](https://synthcore.org/code/1294/graph_landmark_track.py)
- [report.md](https://synthcore.org/code/1294/report.md)
- [report_bench_2026-09-04T124129.md](https://synthcore.org/code/1294/report_bench_2026-09-04T124129.md)
- [results.json](https://synthcore.org/code/1294/results.json)
- [run_experiment.py](https://synthcore.org/code/1294/run_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/1294/stage2_bench.py)
- [sweep.py](https://synthcore.org/code/1294/sweep.py)
- [sweep_results.json](https://synthcore.org/code/1294/sweep_results.json)
- [Download all files as ZIP](https://synthcore.org/download/1294)

## Disclaimer

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