The Higher-Order Identifiability Paradox: Learning and Certifying Hypergraph Order

Higher-order hypergraph information can improve out-of-distribution generalization, yet relying on it can also worsen predictions when training environments leave the added interactions unidentified. We study this higher-order identifiability paradox: increasing order preserves more predictive information while requiring evidence about additional effects. Low-order projection can merge contexts whose changing frequencies reverse predictions despite fixed outcome mechanisms. Joint total-variation and likelihood-ratio constraints yield exact score intervals and minimax Brier regret. We then prove that increasing order reduces projection loss but can expose more unidentified effects under fixed source observations. Suitably varied environments can resolve this ambiguity, but learning a mechanism and certifying a sufficient lower order require different evidence. For quadratic mechanisms with $d$ hidden orientations and fixed-budget Gaussian moment observations, $d-\Theta (\sqrt{d})$ suitably designed environments attain the optimal estimation rate. Within centered isotropic designs, the full-span certification rate requires the environment means to leave only $O(d^{1/3})$ directions unspanned. Matching lower bounds and explicit constructions establish both rates. We validate the predicted mechanisms empirically via synthetic experiments. Motivated by this, we further propose Certified Hypergraph Order Selection for Robust Deployment (CHORD), demonstrating its efficacy and performance on real-world hypergraph datasets.