Testing Dependency of Weighted Random Graphs
Mor Oren-Loberman, Vered Paslev, Wasim Huleihel · IEEE Transactions on Information Theory · 2024
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.