Testing Dependency of Weighted Random Graphs
IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 5040-5058
DOI: 10.1109/tit.2026.3696669 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Mor Oren-Loberman und 2 weiteren Autor:innen. Gefördert von: Israel Science Foundation.
Abstract (Originalsprache)
In this paper, we study the problem of testing for edge dependence between two weighted random graphs observed up to vertex relabeling. We formulate it as a binary hypothesis testing problem: under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are correlated with the edges of a randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing is information-theoretically impossible and possible, in terms of the number of vertices and the underlying weight distributions. Finally, we exhibit a statistical–computational gap for this problem and provide evidence that it is fundamental, using the low-degree polynomial framework.
Förderung
- Israel Science Foundation
Zitieren
APA
Oren-Loberman, M., Paslev, V., & Huleihel, W. (2026). Testing Dependency of Weighted Random Graphs. IEEE Transactions on Information Theory, 72(7), 5040-5058. https://doi.org/10.1109/tit.2026.3696669
Vancouver
Oren-Loberman M, Paslev V, Huleihel W. Testing Dependency of Weighted Random Graphs. IEEE Transactions on Information Theory. 2026;72(7):5040-5058. doi:10.1109/tit.2026.3696669
BibTeX
@article{OrenLoberman2026,
author = {Oren-Loberman, Mor and Paslev, Vered and Huleihel, Wasim},
title = {Testing Dependency of Weighted Random Graphs},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {7},
pages = {5040--5058},
doi = {10.1109/tit.2026.3696669}
}
EUVIMED