Random Subgraph Detection Using Queries
Authors: Wasim Huleihel, Arya Mazumdar, Soumyabrata Pal
JMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph. We also propose a polynomial-time algorithm which is able to detect the planted subgraph, albeit with more queries compared to the above lower bound. We conjecture that in the leftover regime, no polynomial-time algorithms exist. Our results resolve two open questions posed in the past literature. |
| Researcher Affiliation | Collaboration | Wasim Huleihel EMAIL Department of Electrical Engineering-Systems Tel Aviv university Tel Aviv 6997801, Israel Arya Mazumdar EMAIL Halıcıo glu Data Science Institute University of California San Diego La Jolla, CA 92093, USA Soumyabrata Pal EMAIL Adobe Research, India Bangalore, INDIA |
| Pseudocode | Yes | Algorithm 1 Scan Test Require: Gn, Q = M 2 , N0 = (1 ϵ) k M n , and τscan = N0 2 γ, for ϵ (0, 1) and γ [q, p]. 1: Subsample a set S of M elements drawn uniformly at random from [n]. 2: Take all pairwise queries among the elements in S, and obtain Aij, for all i, j S. 3: Compute Sscan max L S:|L|=N0 4: If Sscan > τscan decide H1; otherwise, decide H0. Algorithm 2 Degree Test Require: Gn, n = Ω n2 log n k2χ2(p||q) , M = Ω n k log2 n , and N0 = (1 ϵ) kn n , for ϵ (0, 1). 1: Let S denote a set of n vertices drawn uniformly at random from [n], and GS be the subgraph of G induced by S. 2: Subsample M elements uniformly at random from S, and denote those set of elements by M. 3: Compute j S Aij > n q + N0(p q) 4: If Cdeg > 2 log n decide H1; otherwise, decide H0. |
| Open Source Code | No | The paper does not provide any explicit statements about code release or links to source code repositories. |
| Open Datasets | No | The paper is theoretical and defines mathematical models (e.g., Erdős-Rényi graph, PDS model) for analysis, but does not describe experiments using actual datasets or provide access information for any dataset. |
| Dataset Splits | No | The paper describes theoretical models and algorithms without conducting empirical studies that would require dataset splits. |
| Hardware Specification | No | The paper presents theoretical results and algorithms but does not describe any computational experiments or hardware used to run them. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs; it does not mention specific software dependencies or versions for implementation or experiment execution. |
| Experiment Setup | No | The paper provides theoretical analyses and algorithm descriptions but does not detail any experimental setup, hyperparameters, or training configurations. |