This content will become publicly available on April 1, 2025
Title: Random Subgraph Detection Using Queries
The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an Erdös-R{\'e}nyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. 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. more »« less
We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique.
Specifically, let $G \sim G(n,1/2,k)$ be a random graph on $n$ vertices with a planted clique of size $k$. We show that no algorithm that makes at most $q = o(n^2 / k^2 + n)$ adaptive queries to the adjacency matrix of $G$ is likely to find the planted clique. On the other hand, when $k \geq (2+\epsilon) \log_2 n$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $q = O( (n^2 / k^2) \log^2 n + n \log n)$ adaptive queries. For detection, the additive $n$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2 / k^2$ (up to logarithmic factors).
Chen, Yu; Khanna, Sanjeev; Nagda, Sanjeev(
, 48th International Colloquium on Automata, Languages, and Programming)
null
(Ed.)
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε²) such that the weight of every cut in G is preserved to within a (1 ± ε)-factor in G'. The graph G' is referred to as a (1 ± ε)-approximate cut sparsifier of G. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Ω(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.
Specifically, we design an algorithm that constructs a (1 ± ε)-approximate cut sparsifier of a hypergraph H(V,E) in polynomial time in n, independent of the number of hyperedges, when given access to the hypergraph using the following two queries:
1) given any cut (S, ̄S), return the size |δ_E(S)| (cut value queries); and
2) given any cut (S, ̄S), return a uniformly at random edge crossing the cut (cut edge sample queries). Our algorithm outputs a sparsifier with Õ(n/ε²) edges, which is essentially optimal. We then extend our results to show that cut value and cut edge sample queries can also be used to construct hypergraph spectral sparsifiers in poly(n) time, independent of the number of hyperedges.
We complement the algorithmic results above by showing that any algorithm that has access to only one of the above two types of queries can not give a hypergraph cut sparsifier in time that is polynomial in n. Finally, we show that our algorithmic results also hold if we replace the cut edge sample queries with a pair neighbor sample query that for any pair of vertices, returns a random edge incident on them. In contrast, we show that having access only to cut value queries and queries that return a random edge incident on a given single vertex, is not sufficient.
Abstract Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G , with o ( K ) misclassified vertices on average, in the sublinear regime n 1- o (1) ≤ K ≤ o ( n ). A critical parameter is the effective signal-to-noise ratio λ = K 2 ( p - q ) 2 / (( n - K ) q ), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log * n + O (1) iterations, with the total time complexity O (| E |log * n ), where log * n is the iterated logarithm of n . Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ ( n / log n ) (ρ BP + o (1)), where ρ BP is a function of p / q .
Abrishami, Tara; Chudnovsky, Maria; Pilipczuk, Marcin; Rzążewski, Paweł(
, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
Beyersdorff, Olaf; Kanté, Mamadou Moustapha; Kupferman, Orna; Lokshtanov, Daniel
(Ed.)
We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022].
First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.
Fox, Jacob; Li, Ray(
, Random Structures & Algorithms)
An edge‐ordered graph is a graph with a linear ordering of its edges. Two edge‐ordered graphs areequivalentif there is an isomorphism between them preserving the edge‐ordering. Theedge‐ordered Ramsey number redge(H; q) of an edge‐ordered graphHis the smallestNsuch that there exists an edge‐ordered graphGonNvertices such that, for everyq‐coloring of the edges ofG, there is a monochromatic subgraph ofGequivalent toH. Recently, Balko and Vizer proved thatredge(H; q) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constantcsuch thatfor every edge‐ordered graphHonnvertices. We also prove a polynomial bound for the edge‐ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.
Huleihel, W, Mazumdar, A, and Pal, S. Random Subgraph Detection Using Queries. Retrieved from https://par.nsf.gov/biblio/10520716. Journal of machine learning research .
Huleihel, W, Mazumdar, A, & Pal, S. Random Subgraph Detection Using Queries. Journal of machine learning research, (). Retrieved from https://par.nsf.gov/biblio/10520716.
Huleihel, W, Mazumdar, A, and Pal, S.
"Random Subgraph Detection Using Queries". Journal of machine learning research (). Country unknown/Code not available: JMLR. https://par.nsf.gov/biblio/10520716.
@article{osti_10520716,
place = {Country unknown/Code not available},
title = {Random Subgraph Detection Using Queries},
url = {https://par.nsf.gov/biblio/10520716},
abstractNote = {The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an Erdös-R{\'e}nyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. 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.},
journal = {Journal of machine learning research},
publisher = {JMLR},
author = {Huleihel, W and Mazumdar, A and Pal, S},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
