mbi.approximate_oracles

Approximate marginal oracles with convex counting numbers.

See the paper [“Relaxed Marginal Consistency for Differentially Private Query Answering”](https://arxiv.org/pdf/2109.06153) for more details.

This file implements one approximate marginal inference oracle: Convex-GBP with fixed counting numbers of 1.0 for all regions. We experimented with others, but do not officially support them in this library. If interested, please see the following snapshot of this repository:

https://github.com/ryan112358/private-pgm/tree/approx-experiments-snapshot

Pull requests are welcome to add support for other approximate oracles.

Functions

build_graph

Builds the region graph for convex generalized belief propagation.

convex_generalized_belief_propagation

Convex generalized belief propagation for approximmate marginal inference.

Classes

StatefulMarginalOracle

Defines the callable signature for stateful marginal oracle functions.
class mbi.approximate_oracles.StatefulMarginalOracle(*args, **kwargs)[source]

Bases: Protocol

Defines the callable signature for stateful marginal oracle functions.

A stateful marginal oracle computes (approximate) marginals from log-space potentials while also managing an internal state, often for optimization in iterative algorithms (e.g., preserving messages in message passing).

mbi.approximate_oracles.build_graph(domain: Domain, cliques: list[tuple[str, ...]])[source]

Builds the region graph for convex generalized belief propagation.

mbi.approximate_oracles.convex_generalized_belief_propagation(potentials: CliqueVector, total: float = 1, state: dict[tuple[tuple[str, ...], tuple[str, ...]], Factor] | None = None, mesh: Mesh | None = None, iters: int = 1, damping: float = 0.5) → tuple[CliqueVector, dict[tuple[tuple[str, ...], tuple[str, ...]], Factor]][source]

Convex generalized belief propagation for approximmate marginal inference.

The algorithms implements the Algorithm 2 in our paper [“Relaxed Marginal Consistency for Differentially Private Query Answering”](https://arxiv.org/pdf/2109.06153), which itself is based on the paper titled [“Tightening Fractional Covering Upper Bounds on the Partition

Function for High-Order Region Graphs”](https://arxiv.org/pdf/1210.4881).

Parameters:

  • potentials – A CliqueVector object containing the potentials of the graphical model.

  • total – The total number of records in the dataset.

  • state – The state of the message passing algorithm (i.e., the messages). Useful when calling this within an iterative procedure for warm starting purposes.

  • mesh – Specifies how the computation will be sharded across machines.

  • iters – The number of iterations to run the algorithm.

  • damping – The damping factor for the messages.

Returns:

A CliqueVector of pseudo-marginals for the cliques in the graphical model.