Graph refinement cost and capability evaluator

Family 133: The computational complexity of Weisfeiler–Leman refinement. First review, 8 October 2026.

Problem and potential new use

Graph-ML and canonicalization teams can understand dimensional refinement's worst-case computational limits and failures.

Applicability and commercial boundary

The sequential adjacency-matrix models and variable-dimensional complexity are specific. This does not establish a general lower bound for all graph neural networks or practical fixed-k tools.

Initial business decision

Research infrastructure. Buyer demand and profitability remain hypotheses. This first pass does not establish a validated commercial market.

Next verification action

Build bounded-treewidth witness fixtures and preserve the exact refinement model in benchmarks.

Evidence scope

Catalog statement reviewed; inspect linked opportunity dossier for any deeper source review. This record alone does not establish full manuscript or proof verification.

Source revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. See source metadata for the exact manuscripts and available scope notes.