△ Mechanism confirmed, baseline not beaten 2026

Subcritical Percolation Jordan Readout

Implementation & benchmark of arXiv:2607.21428 — Subcritical percolation and network archaeology on random recursive tree substrate networks

Usefulness7/10

Difficulty5/10

Novelty7/10

Architecture Accuracy Stability Generalization Graph nn Data augmentation Regularization Probability Graph theory Combinatorics

Source paper: Subcritical percolation and network archaeology on random recursive tree substrate networks arXiv:2607.21428 ⓘ · analyzed Aug 30, 2026

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

Idea description

Use several independently percolated versions of an input graph and rank nodes by Jordan centrality inside the largest retained components. Feed only the consistently high-ranked nodes to a graph readout or source-localization head, making predictions depend on structurally stable regions rather than shortcut edges or fragile local neighborhoods.

Formulas

$$\psi_C(v):=\max\{|D|:D\in\operatorname{Comp}(C\setminus\{v\})\}$$

$$\mathcal{H}_{K,L}(G):=\bigcup_{i=1}^{K}\operatorname{TopJ}_{L}(C_i)$$

$$\mathbb{P}(i\leftrightarrow j\mid W_i,W_j)=1-\left(1-\frac{p\lambda}{n}\right)^{W_iW_j}\approx\frac{p\lambda W_iW_j}{n}$$

$$\rho(p,\lambda)=\frac{p\lambda}{1-2p}<1\quad\Longleftrightarrow\quad p<\frac{1}{\lambda+2}$$

Mathematical statement

For a connected component $C$ and vertex $v$, the graph-Jordan score is $\psi_C(v)=\max\{|D|:D\in\operatorname{Comp}(C\setminus\{v\})\}$, where $\operatorname{Comp}(C\setminus\{v\})$ is the set of connected components after deleting $v$, and $|D|$ is component size. Smaller $\psi_C(v)$ means that deleting $v$ leaves smaller largest fragments, so $v$ is more central. If $C_1,\ldots,C_K$ are the K largest percolated components, the candidate set is $\mathcal{H}_{K,L}(G)=\bigcup_{i=1}^{K}\operatorname{TopJ}_{L}(C_i)$, where $\operatorname{TopJ}_{L}(C)$ contains the L vertices with smallest Jordan scores. The percolation analysis models retained shortcut connections between blobs of masses $W_i,W_j$ with probability $1-(1-p\lambda/n)^{W_iW_j}$, and the effective branching factor $\rho(p,\lambda)=p\lambda/(1-2p)$ is subcritical when $p<1/(\lambda+2)$. The neural adaptation uses these constructions as a stochastic topology-only candidate generator and enforces prediction consistency across percolated views.

Implementation notes

(1) Integration point: add a preprocessing/readout branch before a GNN's global pooling or before a node-level source-localization head. The input is an undirected graph $G=(V,E)$ with node features $X$. Generate $R$ independent auxiliary graphs by retaining each edge with probability $p$. For each retained graph, find connected components, keep the $K$ largest, and compute the Jordan score for every vertex in those components. (2) Pseudocode: for each view $r$, sample $E_r=\{e\in E:\operatorname{Bernoulli}(p)=1\}$; compute components $C$; for every candidate vertex $v\in C$, temporarily remove $v$, run a component-size search, and set $s_v=\max_D|D|$; select the $L$ vertices with smallest $s_v$ in each of the $K$ largest components; run the GNN and pool embeddings over the selected nodes. Average logits across views. Add $L_{\mathrm{cons}}=R^{-1}\sum_r\|z_r-\bar z\|_2^2$, where $z_r$ is the view-specific embedding and $\bar z=R^{-1}\sum_rz_r$. (3) Compute the Jordan scores exactly on small components; for large components, approximate them using two BFS sweeps or evaluate only the top $M$ degree candidates. Estimate $\lambda$ from the mean degree only to select a safe sweep range for $p$. (4) First experiment: train a 3-layer GIN or GraphSAGE on synthetic random-recursive-tree plus Erdos-Renyi graphs for root identification, comparing ordinary mean pooling, degree centrality, and this readout. Use $R=8$, $K=3$, $L=8$, and sweep $p\in\{0.1,0.2,0.3,0.4\}$. Test clean graphs and graphs with added shortcuts. Success is higher top-1/top-8 root accuracy and lower accuracy variance under edge corruption, with preprocessing under twice the baseline runtime.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

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 an exact-Jordan percolated candidate generator and a reproducible toy verification. The branching-process transition occurred at p=0.20–0.25 versus the predicted threshold 1/(lambda+2)=0.20; shortcut-retention simulations matched 1-(1-p lambda/n)^(WiWj), and the linear approximation error increased from 0.95% to 55.9% as qx grew. On corrupted random trees, Jordan top-8 source recall was 0.800 versus 0.767 for degree ranking and 0.150 for random selection, so the proposed structural mechanism showed a modest positive signal.

Agent confidence: 8/10

Baseline: Degree top-8 localization recall: 0.7667; random top-8: 0.1500
Idea: Percolated Jordan consensus top-8 recall: 0.8000; predicted branching threshold 0.200, observed transition interval 0.200–0.250; shortcut formula empirical probabilities were close to prediction

Limitations: This is a toy mechanism study, not a trained GNN comparison. It used 120 corrupted random trees, one lambda and graph size for the branching check, exact Jordan computation only on small graphs, and did not test runtime scaling, clean-versus-corrupted generalization, consistency-loss training, or the full K/L/p sweep.

How to run: python3 experiment.py

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

Ahead of the baseline (−7.7%) but not statistically significant (p=0.2165, wins 4 / 8 paired seeds).

Benchmark: Custom:csbm_radius_graph
Model: GraphNet
Paired seeds: 8
Baseline mean: 0.1184
Idea mean: 0.1094
Effect (Δ): -0.0091 (−7.7%; negative = idea better)
Wins: 4 / 8 paired seeds
p-value: 0.2165 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±12.8%
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 9 configs

Limitations:

Only the registered csbm_radius_graph distribution was tested, with fixed p=0.25, R=8, K=1, L=8 and 24 epochs. Larger graphs, alternate p/K/L sweeps, clean-versus-shortcut robustness, runtime scaling, and consistency-loss training were not tested.

How to run: python3 stage2_bench.py

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

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 10/10

The official benchmark was run on the registered custom:csbm_radius_graph track using the canonical bench training and reporting functions. JordanNet improved mean error from 0.1184375 to 0.1093750, but the paired permutation p-value was 0.2165, so the required significant-win verdict was not reached. The mechanism signature was confirmed, but the system did not establish a reliable benchmark win.

Baseline: Best baseline lr=0.003, gamma=0.0; full 8-seed mean error 0.11843749694526196; sweep over 9 configurations.
Idea: Best JordanNet lr=0.003, gamma=0.5; 8-seed mean error 0.10937499720603228; paired delta=-0.009062499739229679; 4/8 paired wins; p=0.2165.

Benchmark result