Testing Dependency of Weighted Random Graphs
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Testing correlation of unlabeled random graphs
We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independe…
Two-sample testingDistributed Convex Optimization with State-Dependent (Social) Interactions over Random Networks
This paper aims at distributed multi-agent convex optimization where the communications network among the agents are presented by a random sequence of possibly state-dependent weighted graphs. This is the first work to c…
Distributed OptimizationWeighted Random Dot Product Graphs
Modeling of intricate relational patterns has become a cornerstone of contemporary statistical research and related data science fields. Networks, represented as graphs, offer a natural framework for this analysis. This …
Accurately Modeling Biased Random Walks on Weighted Graphs Using $\textit{Node2vec+}$
Node embedding is a powerful approach for representing the structural role of each node in a graph. $\textit{Node2vec}$ is a widely used method for node embedding that works by exploring the local neighborhoods via biase…
Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs
Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint…
Dependency ParsingSentence