Did Your GNN Find Anything? Exact Certification of Deep Graph Clustering

Deep graph clustering pipelines always return a partition. On Erdos-Renyi graphs, whose wiring carries nothing beyond the degree sequence, our DMoN-lite and MAGI-lite reimplementations still return partitions of 16 communities at mean modularity 0.25 (DMoN-lite) and 16 at 0.21 (MAGI-lite). We give an exact, finite-sample certification layer that wraps a trained pipeline and returns a p-value against the null that the wiring carries no structure beyond the degrees. The null is uniform over simple graphs with the observed degree sequence, sampled by a double-edge-swap chain inside the Besag-Clifford parallel construction, and validity holds at any chain length. Carrying that guarantee to trained networks under stochastic and amortized training is what we establish. Training is stochastic, so we give seeding rules under which the score stays exchangeable and the p-value stays exact, and show that the wrapped rule must read the graph rather than the ordering of its edges. A certificate costs M + 1 fits, so we give a hub-conditional warm start that provably preserves exactness, and we show that the natural alternative an implementer would write instead certifies structure in a fraction 1.00 of structureless graphs. Most tests do not reject, so a sequential rule stops the median null test after 19 of 199 fits. Applied recursively, the same test estimates model order, with false splits controlled at level α under an explicit selection-neutrality condition. In the calibration audit's 1800 tests of three deep pipelines at α = 0.05, the wrapper's rejection rate stays between 0.005 and 0.065, the largest cell's Wilson interval [0.038, 0.108] covering α, while a Bickel-Sarkar-style threshold applied outside its stated regime rejects a fraction 1.000 of 200 structureless Erdos-Renyi graphs, every rejection a type-I error under its own null. Significance and recovery come apart: pipelines earn certificates on graphs whose planted partitions they do not recover, so a certificate belongs to a (graph, pipeline, configuration) triple rather than to a graph.