Graph community recovery feasibility audit

Initial decision: Conditional evidence workflow. First dossier, 9 October 2026 Australia/Brisbane. No buyer validation or profitability evidence has been established.

Research finding

Family 229 gives an exact threshold dλ²>1, with nonreconstruction at equality, for three-state symmetric tree broadcasting, and states the corresponding symmetric three-community sparse-SBM weak-recovery threshold using existing graph-transfer and algorithm results. Newer four-state ferromagnetic tree results are separate. The selected formal scope proves only three-state reconstruction above the threshold.

Problem and buyer

A graph analytics team needs to distinguish an algorithm’s failure from insufficient information in its fitted network model. A synthetic-data or community-detection vendor may need calibrated test regimes and an honest explanation of what latent labels can be recovered.

What the finding could enable

A diagnostic app can compute a model-specific signal regime, simulate finite test graphs and compare actual label recovery against random-label baselines. It could introduce theorem-linked graph benchmark generation and a model-fit uncertainty report. The new all-degree result sharpens an existing threshold reference; it does not validate an arbitrary real network.

Technical and commercial limits

The graph consequence is for a symmetric sparse three-community model with positive connectivity parameters and mean degree greater than one. Weak recovery is above-chance correlation, not perfect classification. Estimated model parameters and community imbalance create uncertainty. Observed Poisson-tree advantage is averaged without conditioning on survival. The below-threshold and graph consequences do not inherit the selected formal badge.

Minimal architecture

Graph/model manifest -> parameter-fit and uncertainty import -> threshold calculation -> seeded SBM generator -> baseline recovery runs -> permutation-invariant score -> finite-size report. Clearly distinguish a theoretical model regime, estimated model fit and observed recovery; abstain from categorical impossibility claims for a poorly fitting real graph.

Existing alternatives and differentiation

NetworkX already generates stochastic block models with configurable block sizes and probability matrices. Existing community algorithms can be evaluated on those graphs. The proposed differentiation is exact-model scope, fit uncertainty, finite-size regime coverage and reproducible comparison. NetworkX SBM generator.

Monetization hypothesis

Hypothesis: AUD 4,000–12,000 for a model-and-recovery assessment, with AUD 400–1,500 monthly for recurring synthetic benchmark generation. At an illustrative AUD 7,000 assessment, 30 analyst hours costed at AUD 150/hour consume AUD 4,500 before integration and overhead. A one-off scalar threshold calculator alone is unlikely to justify those prices.

Validation experiment

Use seeded symmetric three-community instances above, at and below the model threshold across several finite sizes. Compare an established spectral or belief-propagation method to random labels, include held-out edge-model checks and repeat with deliberately imbalanced/misspecified data. The report should flag the model mismatch rather than export a universal impossibility verdict.

Conditions to reject or defer

Reject if the buyer’s objective is supervised prediction, if their network is far from the model, or if current benchmark tooling already covers the need. Defer real-world impossibility claims and four-state graph-recovery claims unsupported by the inspected source.

Next concrete action

Extract the precise SBM connectivity-to-d-and-λ mapping and establish a finite synthetic benchmark using an existing algorithm.

Pinned research sources

• Family 229: The exact reconstruction threshold for the three-state symmetric channel.
• Family 229: selected formal scope; not independently checked here.