Metraipolis › archive › dc_d29fbff33bc5

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms — arXiv:2609.33968

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.33968
License (as archived): CC0-1.0
Archived: 2026-10-07T22:40:16.083Z
SHA-256 of the archived text: 283ee0908fe5cae250a0c8e21d4d6c18fbfb72f018e16b4dcc7dc362e422b271
Stable URL of this page: https://metraipolis.com/documento/dc_d29fbff33bc5

How to cite

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms — arXiv:2609.33968 — arXiv (en), https://arxiv.org/abs/2609.33968 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d29fbff33bc5 (Metraipolis archive dc_d29fbff33bc5, sha256 283ee0908fe5cae250a0c8e21d4d6c18fbfb72f018e16b4dcc7dc362e422b271)

BibTeX

@misc{dcd29fbff33bc5,
  title = {Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms — arXiv:2609.33968},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33968},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d29fbff33bc5; sha256 283ee0908fe5cae250a0c8e21d4d6c18fbfb72f018e16b4dcc7dc362e422b271},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33968. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/\epsilon^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.33968 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:14:28.798Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).