{
  "id": "2506.21543",
  "version": "v1",
  "published": "2025-06-26T17:58:22.000Z",
  "updated": "2025-06-26T17:58:22.000Z",
  "title": "Detecting weighted hidden cliques",
  "authors": [
    "Urmisha Chatterjee",
    "Karissa Huang",
    "Ritabrata Karmakar",
    "B. R. Vinay Kumar",
    "Gábor Lugosi",
    "Nandan Malhotra",
    "Anirban Mandal",
    "Maruf Alam Tarafdar"
  ],
  "categories": [
    "math.ST",
    "cs.IT",
    "math.IT",
    "math.PR",
    "stat.TH"
  ],
  "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=\\Omega(\\sqrt{n})$ in both the scenarios.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-06-26T17:58:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "62F03"
    ],
    "keywords": [
      "detecting weighted hidden cliques",
      "hypothesis testing problem",
      "computationally efficient spectral tests",
      "classical hidden clique problem",
      "identically distributed edge weights"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}