Universal Inference for model selection on networks

Model selection is an important task on networks, but a key challenge is that typically only a single realization is observed. Thus, existing methods only come with asymptotic theoretical guarantees. In this work, we propose a general model selection framework using Universal Inference. We employ edge sampling to obtain networks with tractable dependence and prove that the proposed statistic is an e-value. To our knowledge, this is the first Universal Inference-type statistic constructed from dependent splits of data and the first finite-sample testing guarantee for hypothesis testing on networks. We also prove that the test statistic diverges to positive infinity under various alternative models. On simulated and real-world networks, the proposed method performs well on various model selection tasks.