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
Phase transitions in the edge/concurrent vertex model
Although it is well known that some exponential family random graph model (ERGM) families exhibit phase transitions (in which small parameter changes lead to qualitative changes in graph structure), the behavior of other models is still poorly understood. Recently, Krivitsky and Morris have reported a previously unobserved phase transition in the edge/concurrent vertex family (a simple starting point for models of sexual contact networks). Here, we examine this phase transition, showing it to be a first-order transition with respect to an order parameter associated with the fraction of concurrent vertices. This transition stems from weak cooperativity in the recruitment of vertices to the concurrent phase, which may not be a desirable property in some applications.
more »
« less
- NSF-PAR ID:
- 10184451
- Date Published:
- Journal Name:
- The Journal of Mathematical Sociology
- ISSN:
- 0022-250X
- Page Range / eLocation ID:
- 1 to 13
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Doty, David and (Ed.)We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response.more » « less
-
ter Beek, Maurice ; Koutny, Maciej ; Rozenberg, Grzegorz (Ed.)For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices.more » « less
-
more » « less
Abstract This paper examines a class of involution-constrained PDEs where some part of the PDE system evolves a vector field whose curl remains zero or grows in proportion to specified source terms. Such PDEs are referred to as curl-free or curl-preserving, respectively. They arise very frequently in equations for hyperelasticity and compressible multiphase flow, in certain formulations of general relativity and in the numerical solution of Schrödinger’s equation. Experience has shown that if nothing special is done to account for the curl-preserving vector field, it can blow up in a finite amount of simulation time. In this paper, we catalogue a class of DG-like schemes for such PDEs. To retain the globally curl-free or curl-preserving constraints, the components of the vector field, as well as their higher moments, must be collocated at the edges of the mesh. They are updated using potentials collocated at the vertices of the mesh. The resulting schemes: (i) do not blow up even after very long integration times, (ii) do not need any special cleaning treatment, (iii) can operate with large explicit timesteps, (iv) do not require the solution of an elliptic system and (v) can be extended to higher orders using DG-like methods. The methods rely on a special curl-preserving reconstruction and they also rely on multidimensional upwinding. The Galerkin projection, highly crucial to the design of a DG method, is now conducted at the edges of the mesh and yields a weak form update that uses potentials obtained at the vertices of the mesh with the help of a multidimensional Riemann solver. A von Neumann stability analysis of the curl-preserving methods is conducted and the limiting CFL numbers of this entire family of methods are catalogued in this work. The stability analysis confirms that with the increasing order of accuracy, our novel curl-free methods have superlative phase accuracy while substantially reducing dissipation. We also show that P
N PM -like methods, which only evolve the lower moments while reconstructing the higher moments, retain much of the excellent wave propagation characteristics of the DG-like methods while offering a much larger CFL number and lower computational complexity. The quadratic energy preservation of these methods is also shown to be excellent, especially at higher orders. The methods are also shown to be curl-preserving over long integration times. -
Suppose a graph G is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing function of their distance. We ask if it is possible to reconstruct the actual positions of the vertices in G by only observing the generated unlabeled graph. We study this question for two natural edge probability functions — one where the probability of an edge decays exponentially with the distance and another where this probability decays only linearly. We initiate our study with the weaker goal of recovering only the order in which vertices appear on the line segment. For a segment of length n and a precision parameter δ, we show that for both exponential and linear decay edge probability functions, there is an efficient algorithm that correctly recovers (up to reflection symmetry) the order of all vertices that are at least δ apart, using only ˜ O( n / δ^2) samples (vertices). Building on this result, we then show that O( n^2 log n / δ^2) vertices (samples) are sufficient to additionally recover the location of each vertex on the line to within a precision of δ. We complement this result with an Ω( n^ 1.5 / δ ) lower bound on samples needed for reconstructing positions (even by a computationally unbounded algorithm), showing that the task of recovering positions is information-theoretically harder than recovering the order. We give experimental results showing that our algorithm recovers the positions of almost all points with high accuracy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1080/0022250X.2020.1746298
