Stitch2-FWL: Stitching Global Expressivity from Local Refinement

Dense pair refinement incurs cubic work even on structurally simple components. We introduce \St, which uses block–cut and SPQR decompositions to confine complete computation to rigid R-skeletons and to reduce an $s$-cycle to $4s^2-3s$ interactions per round. When the induced colored R-configurations are separable and Schurian, the resulting local correspondences agree at their interfaces and compose into a graph isomorphism. Within this class Stitch matches dense 2-FWL, and neither the total graph size nor the decomposition depth is bounded. The class contains every graph without R-skeletons and, under an explicit enumeration premise, every graph whose R-skeletons have at most thirteen vertices. All graphs recorded in our ZINC, QM9, ZINC-full, and PCQM4Mv2 audit meet this size criterion. In exact experiments Stitch preserves every dense distinction across 1,008 long-cycle cases, lowers cumulative interactions by 60.98% at the largest tested subdivision level, and reproduces all 400 BREC decisions. We also report prediction and runtime results. A counterexample outside the guaranteed class motivates the one-hop Stitch-Plus variant, which repairs it; whether that variant is generally equivalent remains open.