Detecting weighted hidden cliques

arXiv (Cornell University)

Abstract

We study a generalization of the classical hidden clique problem to graphs with real-valued edge weights. Formally, we define a hypothesis testing problem. Under the null hypothesis, edges of a complete graph on $n$ vertices are associated with independent and identically distributed edge weights from a distribution $P$. Under the alternate hypothesis, $k$ vertices are chosen at random and the edge weights between them are drawn from a distribution $Q$, while the remaining are sampled from $P$. The goal is to decide, upon observing the edge weights, which of the two hypotheses they were generated from. We investigate the problem under two different scenarios: (1) when $P$ and $Q$ are completely known, and (2) when there is only partial information of $P$ and $Q$. In the first scenario, we obtain statistical limits on $k$ when the two hypotheses are distinguishable, and when they are not. Additionally, in each of the scenarios, we provide bounds on the minimal risk of the hypothesis testing problem when $Q$ is not absolutely continuous with respect to $P$. We also provide computationally efficient spectral tests that can distinguish the two hypotheses as long as $k=Ω(\sqrt{n})$ in both the scenarios.

Authors 4

1. Karissa Huang

   University of California, Berkeley

   Affiliation as printed

   University of California , Berkeley , USA

2. Gábor Lugosi

   Universitat Pompeu Fabra

   Affiliation as printed

   Department of Economics and Business , Pom- peu Fabra University , Barcelona , Spain;

3. Nandan Malhotra Aachen

   Leiden University

   Affiliation as printed

   University of Leiden , The Netherlands

4. Maruf Alam Tarafdar

   Institució Catalana de Recerca i Estudis Avançats · Barcelona School of Economics · Indian Statistical Institute, Delhi Centre · Indian Statistical Institute

   Affiliation as printed

   ICREA , Pg. Lluís Companys 23 , 08010 Barcelona , Spain ; Barcelona School of Economics

   Indian Statistical Institute , Delhi , India