On maximum likelihood estimation in the β-model for random hypergraphs
Abstract
We study maximum likelihood estimation in the β-model for random hypergraphs, in which a group of vertices succeeds with a probability that depends on the sum of its members' parameters. The data are independent binary outcomes of experiments on groups of vertices, tested according to an arbitrary, possibly incomplete design. Suppose that every tested group has k vertices and success probability in [ε,1−ε]. For complete designs in which every group is tested at least r times, a unique maximum likelihood estimator (MLE) exists with high probability if r≥ Ckε−1log n/nk−1, and for m experiments on uniformly random groups, it suffices that m≥ Ckε−1nlog n, where Ck depends only on k. Both conditions are linear in ε−1 and, for fixed k, cannot be improved in general beyond the constant; they follow from finite-sample bounds for arbitrary designs. We bound the mean squared error of the MLE over a parameter box by the smallest eigenvalue of the correlation matrix of the design, and show that the rate is minimax optimal for balanced complete designs. Among k-uniform designs with a given number of experiments, designs in which every pair of vertices takes part together in the same number of experiments maximize this eigenvalue, and uniform random designs nearly do so with high probability. Finally, the design matrix of a uniform random design has full column rank with high probability if m≥max{n,c(n/k)log n} for fixed c>2 and k=o(n/log n), or m≥ n when k≥(1+ξ)log n. For fixed k, the threshold (n/k)log n is sharp, and above it rank deficiency is asymptotically as likely as some vertex taking part in no experiment.
Related
- Restricted Maximum Likelihood Estimation in Generalized Linear Mixed Models
- Maximum Likelihood Estimation and Likelihood Ratio Tests for the Power Spherical Distribution
- Maximum likelihood estimation in the ergodic Volterra Ornstein-Uhlenbeck process
- A Sharp Signal-to-Noise Threshold for Quasi-Maximum Likelihood Breakpoint Estimation
- Unrestricted conditional maximum likelihood estimation for a Fréchet regression model
BibTeX
@misc{vojnovic2026maximum,
title = {{On maximum likelihood estimation in the $β$-model for random hypergraphs}},
author = {Milan Vojnović and Yiliu Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34443},
eprint = {2610.34443},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34443},
}
RIS
TY - UNPB
TI - On maximum likelihood estimation in the β-model for random hypergraphs
AU - Milan Vojnović
AU - Yiliu Wang
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34443
UR - https://arxiv.org/abs/2610.34443
AB - We study maximum likelihood estimation in the β-model for random hypergraphs, in which a group of vertices succeeds with a probability that depends on the sum of its members' parameters. The data are independent binary outcomes of experiments on groups of vertices, tested according to an arbitrary, possibly incomplete design. Suppose that every tested group has k vertices and success probability in [ε,1−ε]. For complete designs in which every group is tested at least r times, a unique maximum likelihood estimator (MLE) exists with high probability if r≥ C_kε^−1log n/n^k−1, and for m experiments on uniformly random groups, it suffices that m≥ C_kε^−1nlog n, where C_k depends only on k. Both conditions are linear in ε^−1 and, for fixed k, cannot be improved in general beyond the constant; they follow from finite-sample bounds for arbitrary designs. We bound the mean squared error of the MLE over a parameter box by the smallest eigenvalue of the correlation matrix of the design, and show that the rate is minimax optimal for balanced complete designs. Among k-uniform designs with a given number of experiments, designs in which every pair of vertices takes part together in the same number of experiments maximize this eigenvalue, and uniform random designs nearly do so with high probability. Finally, the design matrix of a uniform random design has full column rank with high probability if m≥max{n,c(n/k)log n} for fixed c>2 and k=o(n/log n), or m≥ n when k≥(1+ξ)log n. For fixed k, the threshold (n/k)log n is sharp, and above it rank deficiency is asymptotically as likely as some vertex taking part in no experiment.
ER -