Эксперимент: Resolving Landmark Bottleneck (#1294)

{ "worked": true, "confidence": 8, "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.", "metrics": { "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." }, "how_to_run": "/home/maxwelhelp/main/bin/python3 run_experiment.py && /home/maxwelhelp/main/bin/python3 sweep.py", "files": [ "run_experiment.py", "sweep.py", "results.json", "sweep_results.json" ], "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." }