Related papers: Testing Dependency of Weighted Random Graphs

URL: http://arxiv.org/abs/2409.14870v2
Date: Tue, 24 Sep 2024 16:07:57 GMT
Title: Testing Dependency of Weighted Random Graphs
Authors: Mor Oren, Vered Paslev, Wasim Huleihel,
Abstract summary: We study the task of detecting the edge dependency between two random graphs. For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible.
Score: 4.0554893636822
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we study the task of detecting the edge dependency between two weighted random graphs. We formulate this task as a simple hypothesis testing problem, where under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are dependent on the edges of a uniformly and randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible, as a function of the total number of nodes in the observed graphs and the generative distributions of the weights. Finally, we identify a statistical-computational gap, and present evidence suggesting that this gap is inherent using the framework of low-degree polynomials.

Err

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.