Density Consistency

A julia code to run Density Consistency algorithm.

Installation

The package is not registered. To use it, clone the repository locally:

git clone https://github.com/giovact/DensityConsistency

Package requirements

• ExtractMacro
• LinearAlgebra
• Random
• SparseArrays

Loading

include("src/DC.jl")
using .DC

Usage

DC allows to compute marginal marginal distributions of discrete graphical models:

where σᵢ ∈ {-1,1} and each factor ψa encodes for local interactions between the ∂a variables. This parametrizations encodes any Boltzmann equilibrium measure with arbitrary high-order interaction terms (Ising, p-spin) as well as the set of solutions for a single-instance set of k-SAT formulas.

Each factor node (or compatibility function) ψₐ is parametrized as ψₐ ∝ exp(-E(xₐ)) and defined by:

struct EnergyFun <: Factor

• E::Function: E(xₐ)
• idx::Vector{Int64}: ∂a indeces

Example (Ising Pair): ψ_ij = DC.EnergyFun((x::Vector{Int64}-> -J*x[1]*x[2]) , [i,j])

Run

The algorithm runs by calling the function density_consistency, taking the following arguments:

• Ψ::Vector{<:Factor}: Array of factor nodes ψₐ
• N::Int: number of spins

Some additional named arguments:

• closure::Symbol = :DC: closure protocol
• η::Float64 = 1.0: interpolation parameter (valid on :DC closure) -> η=0 gives BP fixed points
• epsconv::Float64 = 1e-6: precision convergence
• update::Symbol = :par: type of update -> parallel (:par) or random sequential (:seq)
• ρ::Float64 = 0.9: damping for parameters' update (ρ = 0 means no damping)
• convtype::Symbol = :params: convergence criterion on :moments or gaussian factor :params

Check example_Ising.ipynb jupyter notebook for basic usage on the Ising model

Reference

Alfredo Braunstein, Giovanni Catania and Luca Dall’Asta
Loop corrections in spin models through density consistency
2019, Phys. Rev. Lett. 123, 020604, arXiv:1810.10602