We consider a bipartite stochastic block model on vertex sets @math and @math , with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When @math , multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of mossel2012stochastic,mossel2013proof and massoulie2014community for the stochastic block model. We then show that at a higher edge density, the singular vectors of the rectangular biadjacency matrix exhibit a localization delocalization phase transition, giving recovery above the threshold and no recovery below. Nevertheless, we propose a simple spectral algorithm, Diagonal Deletion SVD, which recovers the partition at a nearly optimal edge density. The bipartite stochastic block model studied here was used by feldman2014algorithm to give a unified algorithm for recovering planted partitions and assignments in random hypergraphs and random @math -SAT formulae respectively. Our results give the best known bounds for the clause density at which solutions can be found efficiently in these models as well as showing a barrier to further improvement via this reduction to the bipartite block model.
The stochastic block model has been a source of considerable recent interest. There are many algorithmic approaches to the problem, including algorithms based on maximum-likelihood methods @cite_7 , belief propagation @cite_15 , spectral methods @cite_32 , modularity maximization @cite_12 , and combinatorial methods @cite_23 , @cite_29 , @cite_10 , @cite_38 . @cite_39 gave the first algorithm to detect partitions in the sparse, constant average degree regime. @cite_15 conjectured the precise achievable constant and subsequent algorithms @cite_40 @cite_8 @cite_9 @cite_26 achieved this bound. Sharp thresholds for full recovery (as opposed to detection) have been found by @cite_25 @cite_24 @cite_33 . @cite_22 used ideas for reconstructing assignments to random @math -SAT formulas in the planted @math -SAT model to show that Goldreich's construction of a one-way function in @cite_18 is not secure when the predicate correlates with either one or two of its inputs. For more on Goldreich's PRG from a cryptographic perspective see the survey of @cite_3 . @cite_36 gave an algorithm to recover the partition of @math in the bipartite stochastic block model to solve instances of planted random @math -SAT and planted hypergraph partitioning using subsampled power iteration.
@cite_22 @cite_36 @cite_29 @cite_3 @cite_15 @cite_10 @cite_38 @cite_18 @cite_8 @cite_39 @cite_23 @cite_26 @cite_7 @cite_32 @cite_40 @cite_25 @cite_12 @cite_33 @cite_9 @cite_24
2002676260 2950319503 2016776056 181881105 2963264680 2024281442 2024128809 2951745592 2133361319 1605711022 2023348178 2093663313
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : 0, 1 n → 0, 1 m where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability. We also prove an amplification claim regarding Goldreich’s construction. Suppose we are given an assignment @math that has correlation @math with the hidden assignment @math . Then, given access to x′, it is possible to invert f on x with high probability, provided @math is sufficiently large. We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used. The time complexity is significantly better than both spectral and SDP-based approaches. The main contribution of the algorithm is in the case of unequal sizes in the bipartition (corresponding to odd uniformity in the CSP). Here our algorithm succeeds at a significantly lower density than the spectral approaches, surpassing a barrier based on the spectral norm of a random matrix. Other significant features of the algorithm and analysis include (i) the critical use of power iteration with subsampling, which might be of independent interest; its analysis requires keeping track of multiple norms of an evolving solution (ii) it can be implemented statistically, i.e., with very limited access to the input distribution (iii) the algorithm is extremely simple to implement and runs in linear time, and thus is practical even for very large instances. Abstract The average-case complexity of recognising some NP-complete properties is examined, when the instances are randomly selected from those which have the property. We carry out this analysis for 1. (1) Graph k -colourability. We describe an O ( n 2 ) expected time algorithm for n -vertex graphs, with k constant. 2. (2) Small equitable cut. We describe an O ( n 3 ) expected time algorithm for finding and verifying , the minimum equitable cut in a 2 n -vertex graph G , condition on G having one with at most (1 − ϵ)n 2 2 edges. 3. (3) Partitioning a 2 n vertex graph into two sparse vertex induced subgraphs of a given class. We describe an O ( n 3 ) expected time algorithm for computing such a partition. 4. (4) The number problem 3-PARTITION. We describe an O ( n 2 ) expected time algorithm for problems with 3 n integers. Constant parallel-time cryptography allows performing complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. The feasibility of such highly efficient cryptographic constructions was widely studied in the last decade via two main research threads. The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability @math within clusters and @math across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of @math to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if @math and @math are constant (with @math ), recovering the communities with high probability is possible if @math and is impossible if $( + 2 ) - . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. We resolve in the affirmative a question of Boppana and Bui: whether simulated annealing can, with high probability and in polynomial time, find the optimal bisection of a random graph in npr when p − R = Θ(nΔ − 2) for Δ 2. (The random graph model npr specifies a “planted” bisection of density r, separating two n 2-vertex subsets of slightly higher density p.) We show that simulated “annealing” at an appropriate fixed temperature (i.e., the Metropolis algorithm) finds the unique smallest bisection in O(n2 + ) steps with very high probability, provided . (By using a slightly modified neighborhood structure, the number of steps can be reduced to O(n1+).) We leave open the question of whether annealing is effective for Δ in the range , whose lower limit represents the threshold at which the planted bisection becomes lost amongst other random small bisections. It also remains open whether hillclimbing (i.e., annealing at temperature 0) solves the same problem; towards the latter result, Juels has recently extended our analysis and shown that random hillclimbing finds the minimum bisection with constant probability, when p − R = Ω(1) (corresponding to Δ=2). The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph l-partition problem is to partition the nodes of an undirected graph into l equal-sized groups so as to minimize the total number of edges that cross between groups. In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a ‘latent’ partition V1,. . ., Vk. Moreover, consider a ‘density matrix’ Ɛ = (Ɛvw)v, sw∈V such that, for v ∈ Vi and w ∈ Vj, the entry Ɛvw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: Ɛ approximates the adjacency matrix of G in the operator norm, for vertices v ∈ Vi, w ∈ Vj ≠ Vi the corresponding column vectors Ɛv, Ɛw are separated, and G is sufficiently ‘regular’ with respect to the matrix Ɛ. This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs. Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident. [1] conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mossel, Neeman and Sly [2] established the negative part of the conjecture, proving impossibility of non-trivial reconstruction below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a modified adjacency matrix B which counts self-avoiding paths of a given length e between pairs of nodes. We then prove that for logarithmic length e, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n -- 2 eigenvalues of a lower order O(ne √ρ(B) for all e 0, ρ(B) denoting B's spectral radius. The planted bisection model is a random graph model in which the nodes are divided into two equal-sized communities and then edges are added randomly in a way that depends on the community membership. We establish necessary and sufficient conditions for the asymptotic recoverability of the planted bisection in this model. When the bisection is asymptotically recoverable, we give an efficient algorithm that successfully recovers it. We also show that the planted bisection is recoverable asymptotically if and only if with high probability every node belongs to the same community as the majority of its neighbors. Our algorithm for finding the planted bisection runs in time almost linear in the number of edges. It has three stages: spectral clustering to compute an initial guess, a "replica" stage to get almost every vertex correct, and then some simple local moves to finish the job. An independent work by Abbe, Bandeira, and Hall establishes similar (slightly weaker) results but only in the sparse case where pn, qn = Θ(log n n).