SynthCore
✓✓ Beats tuned baseline 2026

Resolving Landmark Bottleneck

Implementation & benchmark of arXiv:2607.05152 — Localization and metric dimension for families of highly structured digraphs

Usefulness6/10
Difficulty5/10
Novelty7/10
Memory MemoryScalabilityAccuracyGraph nnAttentionMemoryCombinatoricsProbabilityGraph theory

Source paper: Localization and metric dimension for families of highly structured digraphs arXiv:2607.05152 ⓘ · analyzed Aug 30, 2026

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

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

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])$$

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.

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

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

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

Agent confidence
8/10
Baseline
Uniform: 49 landmarks, 35 collisions (5.83% of nodes), accuracy 0.761; degree: 49 landmarks, 22 collisions, accuracy 0.789; full 1-hop control accuracy 0.472.
Idea
Greedy: 39 landmarks, 0 collisions, accuracy 0.756. Sweep: greedy reached 0 collisions at s=40 (actually used 39); uniform had mean 6.79 collisions at s=64, 0.05 at s=96, and 0 at s=128. Exact-vs-empirical pairwise probability maximum absolute error was 0.000264.

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.

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

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.05152)

Beats the tuned baseline by 31.5% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark
Graph_landmark_forecast
Model
transformer_tiny
Paired seeds
8
Baseline mean
0.0973
Idea mean
0.0667
Effect (Δ)
-0.0306 (−31.5%; negative = idea better)
Wins
8 / 8 paired seeds
p-value
0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect
±9.5%
Mechanism
Confirmed ✓
Practical effect
Helps
Baseline tuning
swept over 3 configs
Limitations:

The registered custom task is small: a fixed 20-node graph with 400 training and 200 test examples. Large-graph memory, preprocessing, and throughput scaling were not measured. The baseline is a matched transformer with zero structural channels rather than a production full Graphormer adjacency-attention implementation, so the significant MSE win supports the feature mechanism on this graph task but does not by itself establish the claimed O(n^2) to O(ns) systems-level memory reduction. The mechanism bound is loose because c_min=1.

How to run: cd /home/maxwelhelp/all/math2nn/experiments/exp421_resolving-landmark-bottleneck && /home/maxwelhelp/main/bin/python3 stage2_bench.py

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

Stage 2 — Benchmark latest Worked ✓

Agent confidence: 7/10

The registered custom graph-landmark forecasting track was evaluated with identical transformer systems, differing only by the addition of greedy resolving-landmark signatures. The idea achieved lower test MSE on all 8 paired seeds: 0.066688 versus the tuned baseline 0.097288, paired delta -0.030600, permutation p=0.0081. The trained-model mechanism check observed zero idea signature collisions versus 19 baseline collisions, below the independently computed hypergeometric upper bound of 114.

Baseline
make_report baseline block: best_cfg lr=0.003; sweep means lr=0.001: 0.0976012, lr=0.003: 0.0971596, lr=0.01: 0.0978763; full 8-seed mean=0.0972881, std=0.0028138.
Comparison
delta_mean=-0.0305997, idea_wins=8, n_pairs=8, p_value=0.0081, verdict='idea better (significant)', system_worked=true
Idea
Best idea config lr=0.01; per-seed test MSE=[0.0671466,0.0738764,0.0655859,0.0592485,0.0516633,0.0640472,0.0735524,0.0783868], mean=0.0666884, std=0.0081020.

Benchmark result

Beats the tuned baseline by 31.5% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark
Graph_landmark_forecast
Model
transformer_tiny
Paired seeds
8
Baseline mean
0.0973
Idea mean
0.0667
Effect (Δ)
-0.0306 (−31.5%; negative = idea better)
Wins
8 / 8 paired seeds
p-value
0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect
±9.5%
Mechanism
Confirmed ✓
Practical effect
Helps
Baseline tuning
swept over 3 configs
Limitations:

The registered custom task is small: a fixed 20-node graph with 400 training and 200 test examples. Large-graph memory, preprocessing, and throughput scaling were not measured. The baseline is a matched transformer with zero structural channels rather than a production full Graphormer adjacency-attention implementation, so the significant MSE win supports the feature mechanism on this graph task but does not by itself establish the claimed O(n^2) to O(ns) systems-level memory reduction. The mechanism bound is loose because c_min=1.

How to run: cd /home/maxwelhelp/all/math2nn/experiments/exp421_resolving-landmark-bottleneck && /home/maxwelhelp/main/bin/python3 stage2_bench.py

Artifacts

Implementation overview ⬇ Download all as ZIP 9 files · code, reports and structured results

Related ideas