Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecovery thresholds in the sparse planted matching problem
374
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.
rate research
Read More
Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of $k$-uniform hypergraphs with a density $alpha$ of constraints, and the $q$-coloring of random graphs with average degree $c$. We show that in the large $k,q$ limit the clustering transition occurs for $alpha = frac{2^{k-1}}{k} (ln k + ln ln k + gamma_{rm d} + o(1))$, $c= q (ln q + ln ln q + gamma_{rm d}+ o(1))$, where $gamma_{rm d}$ is the same constant for both models. We characterize $gamma_{rm d}$ via a functional equation, solve the latter numerically to estimate $gamma_{rm d} approx 0.871$, and obtain an analytic lowerbound $gamma_{rm d} ge 1 + ln (2 (sqrt{2}-1)) approx 0.812$. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at $gamma_{rm r}=1$.
We study the problem of reconstructing a perfect matching $M^*$ hidden in a randomly weighted $ntimes n$ bipartite graph. The edge set includes every node pair in $M^*$ and each of the $n(n-1)$ node pairs not in $M^*$ independently with probability $d/n$. The weight of each edge $e$ is independently drawn from the distribution $mathcal{P}$ if $e in M^*$ and from $mathcal{Q}$ if $e otin M^*$. We show that if $sqrt{d} B(mathcal{P},mathcal{Q}) le 1$, where $B(mathcal{P},mathcal{Q})$ stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of $M^*$ converges to $0$ as $nto infty$. Conversely, if $sqrt{d} B(mathcal{P},mathcal{Q}) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$ under both the sparse and dense model, resolving the conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in the special case of complete exponentially weighted graph with $d=n$, $mathcal{P}=exp(lambda)$, and $mathcal{Q}=exp(1/n)$, for which the sharp threshold simplifies to $lambda=4$, we prove that when $lambda le 4-epsilon$, the optimal reconstruction error is $expleft( - Theta(1/sqrt{epsilon}) right)$, confirming the conjectured infinite-order phase transition in [Semerjian et al. 2020].
The typical complexity of Constraint Satisfaction Problems (CSPs) can be investigated by means of random ensembles of instances. The latter exhibit many threshold phenomena besides their satisfiability phase transition, in particular a clustering or dynamic phase transition (related to the tree reconstruction problem) at which their typical solutions shatter into disconnected components. In this paper we study the evolution of this phenomenon under a bias that breaks the uniformity among solutions of one CSP instance, concentrating on the bicoloring of k-uniform random hypergraphs. We show that for small k the clustering transition can be delayed in this way to higher density of constraints, and that this strategy has a positive impact on the performances of Simulated Annealing algorithms. We characterize the modest gain that can be expected in the large k limit from the simple implementation of the biasing idea studied here. This paper contains also a contribution of a more methodological nature, made of a review and extension of the methods to determine numerically the discontinuous dynamic transition threshold.
We investigate the clustering transition undergone by an exemplary random constraint satisfaction problem, the bicoloring of $k$-uniform random hypergraphs, when its solutions are weighted non-uniformly, with a soft interaction between variables belonging to distinct hyperedges. We show that the threshold $alpha_{rm d}(k)$ for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of $alpha_{rm d}(k)$ in the large $k$ limit. We find that $alpha_{rm d}(k) = frac{2^{k-1}}{k}(ln k + ln ln k + gamma_{rm d} + o(1))$, where the constant $gamma_{rm d}$ is strictly larger than for the uniform measure over solutions.
Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For the correlated Erdos-Renyi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erdos-Renyi graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
