An official website of the United States government
ABSTRACT Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergraph version of the problem. Let denote the ‐uniform Erdős–Rényi hypergraph model with vertices and edge density . We consider detecting the presence of a planted subhypergraph in a hypergraph, where and . Focusing on tests that are degree‐ polynomials of the entries of the adjacency tensor, we determine the threshold between the easy and hard regimes for the detection problem. More precisely, for , the threshold is given by , and for , the threshold is given by . Our results are already new in the graph case , as we consider the subtlelog‐density regimewhere hardness based on average‐case reductions is not known. Our proof of low‐degree hardness is based on aconditionalvariant of the standard low‐degree likelihood calculation.
more »
« less
Estimation in tensor Ising models
Abstract The $$p$$-tensor Ising model is a one-parameter discrete exponential family for modeling dependent binary data, where the sufficient statistic is a multi-linear form of degree $$p \geqslant 2$$. This is a natural generalization of the matrix Ising model that provides a convenient mathematical framework for capturing, not just pairwise, but higher-order dependencies in complex relational data. In this paper, we consider the problem of estimating the natural parameter of the $$p$$-tensor Ising model given a single sample from the distribution on $$N$$ nodes. Our estimate is based on the maximum pseudolikelihood (MPL) method, which provides a computationally efficient algorithm for estimating the parameter that avoids computing the intractable partition function. We derive general conditions under which the MPL estimate is $$\sqrt N$$-consistent, that is, it converges to the true parameter at rate $$1/\sqrt N$$. Our conditions are robust enough to handle a variety of commonly used tensor Ising models, including spin glass models with random interactions and models where the rate of estimation undergoes a phase transition. In particular, this includes results on $$\sqrt N$$-consistency of the MPL estimate in the well-known $$p$$-spin Sherrington–Kirkpatrick model, spin systems on general $$p$$-uniform hypergraphs and Ising models on the hypergraph stochastic block model (HSBM). In fact, for the HSBM we pin down the exact location of the phase transition threshold, which is determined by the positivity of a certain mean-field variational problem, such that above this threshold the MPL estimate is $$\sqrt N$$-consistent, whereas below the threshold no estimator is consistent. Finally, we derive the precise fluctuations of the MPL estimate in the special case of the $$p$$-tensor Curie–Weiss model, which is the Ising model on the complete $$p$$-uniform hypergraph. An interesting consequence of our results is that the MPL estimate in the Curie–Weiss model saturates the Cramer–Rao lower bound at all points above the estimation threshold, that is, the MPL estimate incurs no loss in asymptotic statistical efficiency in the estimability regime, even though it is obtained by minimizing only an approximation of the true likelihood function for computational tractability.
more »
« less
- Award ID(s):
- 2046393
- PAR ID:
- 10333719
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- ISSN:
- 2049-8772
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, prior work on designing dynamical systems as Ising machines has primarily considered quadratic interactions among the nodes. Dynamical systems and models considering higher order interactions among the Ising spins remain largely unexplored, particularly for applications in computing. Therefore, in this work, we propose Ising spin-based dynamical systems that consider higher order (> 2) interactions among the Ising spins, which subsequently, enables us to develop computational models to directly solve many COPs that entail such higher order interactions (i.e., COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K ≥ 4) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired ‘toolbox’ for solving COPs.more » « less
-
We report results of magnetization and 19F NMR measurements in the normal state of as-grown vacuum-annealed LaO0.5F0.5BiS2. The magnetization is dominated by a temperature-independent diamagnetic component and a field- and temperature-dependent paramagnetic contribution 𝑀𝜇(𝐻,𝑇) from a ∼1000 ppm concentration of local moments, an order of magnitude higher than can be accounted for by measured rare-earth impurity concentrations. 𝑀𝜇(𝐻,𝑇) can be fit by the Brillouin function 𝐵𝐽(𝑥) or, perhaps more realistically, a two-level tanh(𝑥) model for magnetic Bi 6𝑝 ions in defect crystal fields. Both fits require a phenomenological Curie-Weiss argument 𝑥=𝜇eff𝐻/(𝑇+𝑇𝑊), 𝑇𝑊≈1.7 K. There is no evidence for magnetic order down to 2 K, and the origin of 𝑇𝑊 is not clear. 19F frequency shifts, linewidths, and spin-lattice relaxation rates are consistent with purely dipolar 19F/defect-spin interactions. The defect-spin correlation time 𝜏𝑐(𝑇) obtained from 19F spin-lattice relaxation rates obeys the Korringa relation 𝜏𝑐𝑇=const, indicating the relaxation is dominated by conduction-band fluctuations.more » « less
-
Megow, Nicole; Smith, Adam (Ed.)We consider spin systems on general n-vertex graphs of unbounded degree and explore the effects of spectral independence on the rate of convergence to equilibrium of global Markov chains. Spectral independence is a novel way of quantifying the decay of correlations in spin system models, which has significantly advanced the study of Markov chains for spin systems. We prove that whenever spectral independence holds, the popular Swendsen-Wang dynamics for the q-state ferromagnetic Potts model on graphs of maximum degree Δ, where Δ is allowed to grow with n, converges in O((Δ log n)^c) steps where c > 0 is a constant independent of Δ and n. We also show a similar mixing time bound for the block dynamics of general spin systems, again assuming that spectral independence holds. Finally, for monotone spin systems such as the Ising model and the hardcore model on bipartite graphs, we show that spectral independence implies that the mixing time of the systematic scan dynamics is O(Δ^c log n) for a constant c > 0 independent of Δ and n. Systematic scan dynamics are widely popular but are notoriously difficult to analyze. This result implies optimal O(log n) mixing time bounds for any systematic scan dynamics of the ferromagnetic Ising model on general graphs up to the tree uniqueness threshold. Our main technical contribution is an improved factorization of the entropy functional: this is the common starting point for all our proofs. Specifically, we establish the so-called k-partite factorization of entropy with a constant that depends polynomially on the maximum degree of the graph.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imaiai/iaac007
