# Subcritical Percolation Jordan Readout

- ID: 1238
- Canonical URL: https://synthcore.org/idea/1238/subcritical-percolation-jordan-readout
- API JSON: https://synthcore.org/api/idea/1238.json
- API Markdown: https://synthcore.org/api/idea/1238.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.21428](https://arxiv.org/abs/2607.21428)
- Category: architecture
- Solves: accuracy, stability, generalization
- ML areas: graph-nn, data-augmentation, regularization
- Math tags: probability, graph-theory, combinatorics
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

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

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

## Key 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}$$

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

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

### Mechanism check

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

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.2165
- Paired wins: 4/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_local.py](https://synthcore.org/code/498/bench_local.py)
- [bench_report.json](https://synthcore.org/code/498/bench_report.json)
- [custom_track.py](https://synthcore.org/code/498/custom_track.py)
- [experiment.py](https://synthcore.org/code/498/experiment.py)
- [report.md](https://synthcore.org/code/498/report.md)
- [report_bench_2026-08-31T160824.md](https://synthcore.org/code/498/report_bench_2026-08-31T160824.md)
- [stage2_bench.py](https://synthcore.org/code/498/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/498)

## Disclaimer

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